1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* This program is used to produce insn-recog.c, which contains a
24 function called `recog' plus its subroutines. These functions
25 contain a decision tree that recognizes whether an rtx, the
26 argument given to recog, is a valid instruction.
28 recog returns -1 if the rtx is not valid. If the rtx is valid,
29 recog returns a nonnegative number which is the insn code number
30 for the pattern that matched. This is the same as the order in the
31 machine description of the entry that matched. This number can be
32 used as an index into various insn_* tables, such as insn_template,
33 insn_outfun, and insn_n_operands (found in insn-output.c).
35 The third argument to recog is an optional pointer to an int. If
36 present, recog will accept a pattern if it matches except for
37 missing CLOBBER expressions at the end. In that case, the value
38 pointed to by the optional pointer will be set to the number of
39 CLOBBERs that need to be added (it should be initialized to zero by
40 the caller). If it is set nonzero, the caller should allocate a
41 PARALLEL of the appropriate size, copy the initial entries, and
42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
44 This program also generates the function `split_insns', which
45 returns 0 if the rtl could not be split, or it returns the split
48 This program also generates the function `peephole2_insns', which
49 returns 0 if the rtl could not be matched. If there was a match,
50 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
57 #include "gensupport.h"
60 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
61 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
63 /* Holds an array of names indexed by insn_code_number. */
64 static char **insn_name_ptr = 0;
65 static int insn_name_ptr_size = 0;
67 /* A listhead of decision trees. The alternatives to a node are kept
68 in a doublely-linked list so we can easily add nodes to the proper
69 place when merging. */
73 struct decision *first;
74 struct decision *last;
77 /* A single test. The two accept types aren't tests per-se, but
78 their equality (or lack thereof) does affect tree merging so
79 it is convenient to keep them here. */
83 /* A linked list through the tests attached to a node. */
84 struct decision_test *next;
86 /* These types are roughly in the order in which we'd like to test them. */
89 DT_mode, DT_code, DT_veclen,
90 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
91 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
92 DT_accept_op, DT_accept_insn
97 enum machine_mode mode; /* Machine mode of node. */
98 RTX_CODE code; /* Code to test. */
102 const char *name; /* Predicate to call. */
103 int index; /* Index into `preds' or -1. */
104 enum machine_mode mode; /* Machine mode for node. */
107 const char *c_test; /* Additional test to perform. */
108 int veclen; /* Length of vector. */
109 int dup; /* Number of operand to compare against. */
110 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
111 int opno; /* Operand number matched. */
114 int code_number; /* Insn number matched. */
115 int lineno; /* Line number of the insn. */
116 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
121 /* Data structure for decision tree for recognizing legitimate insns. */
125 struct decision_head success; /* Nodes to test on success. */
126 struct decision *next; /* Node to test on failure. */
127 struct decision *prev; /* Node whose failure tests us. */
128 struct decision *afterward; /* Node to test on success,
129 but failure of successor nodes. */
131 const char *position; /* String denoting position in pattern. */
133 struct decision_test *tests; /* The tests for this node. */
135 int number; /* Node number, used for labels */
136 int subroutine_number; /* Number of subroutine this node starts */
137 int need_label; /* Label needs to be output. */
140 #define SUBROUTINE_THRESHOLD 100
142 static int next_subroutine_number;
144 /* We can write three types of subroutines: One for insn recognition,
145 one to split insns, and one for peephole-type optimizations. This
146 defines which type is being written. */
149 RECOG, SPLIT, PEEPHOLE2
152 #define IS_SPLIT(X) ((X) != RECOG)
154 /* Next available node number for tree nodes. */
156 static int next_number;
158 /* Next number to use as an insn_code. */
160 static int next_insn_code;
162 /* Similar, but counts all expressions in the MD file; used for
165 static int next_index;
167 /* Record the highest depth we ever have so we know how many variables to
168 allocate in each subroutine we make. */
170 static int max_depth;
172 /* The line number of the start of the pattern currently being processed. */
173 static int pattern_lineno;
175 /* Count of errors. */
176 static int error_count;
178 /* This table contains a list of the rtl codes that can possibly match a
179 predicate defined in recog.c. The function `maybe_both_true' uses it to
180 deduce that there are no expressions that can be matches by certain pairs
181 of tree nodes. Also, if a predicate can match only one code, we can
182 hardwire that code into the node testing the predicate. */
184 static struct pred_table
187 RTX_CODE codes[NUM_RTX_CODE];
189 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
190 LABEL_REF, SUBREG, REG, MEM}},
191 #ifdef PREDICATE_CODES
194 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
195 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
196 {"register_operand", {SUBREG, REG}},
197 {"pmode_register_operand", {SUBREG, REG}},
198 {"scratch_operand", {SCRATCH, REG}},
199 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
201 {"const_int_operand", {CONST_INT}},
202 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
203 {"nonimmediate_operand", {SUBREG, REG, MEM}},
204 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
205 LABEL_REF, SUBREG, REG}},
206 {"push_operand", {MEM}},
207 {"pop_operand", {MEM}},
208 {"memory_operand", {SUBREG, MEM}},
209 {"indirect_operand", {SUBREG, MEM}},
210 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
211 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
213 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
214 LABEL_REF, SUBREG, REG, MEM}}
217 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
219 static const char * special_mode_pred_table[] = {
220 #ifdef SPECIAL_MODE_PREDICATES
221 SPECIAL_MODE_PREDICATES
223 "pmode_register_operand"
226 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
228 static struct decision *new_decision
229 PARAMS ((const char *, struct decision_head *));
230 static struct decision_test *new_decision_test
231 PARAMS ((enum decision_type, struct decision_test ***));
232 static rtx find_operand
234 static rtx find_matching_operand
236 static void validate_pattern
237 PARAMS ((rtx, rtx, rtx, int));
238 static struct decision *add_to_sequence
239 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
241 static int maybe_both_true_2
242 PARAMS ((struct decision_test *, struct decision_test *));
243 static int maybe_both_true_1
244 PARAMS ((struct decision_test *, struct decision_test *));
245 static int maybe_both_true
246 PARAMS ((struct decision *, struct decision *, int));
248 static int nodes_identical_1
249 PARAMS ((struct decision_test *, struct decision_test *));
250 static int nodes_identical
251 PARAMS ((struct decision *, struct decision *));
252 static void merge_accept_insn
253 PARAMS ((struct decision *, struct decision *));
254 static void merge_trees
255 PARAMS ((struct decision_head *, struct decision_head *));
257 static void factor_tests
258 PARAMS ((struct decision_head *));
259 static void simplify_tests
260 PARAMS ((struct decision_head *));
261 static int break_out_subroutines
262 PARAMS ((struct decision_head *, int));
263 static void find_afterward
264 PARAMS ((struct decision_head *, struct decision *));
266 static void change_state
267 PARAMS ((const char *, const char *, struct decision *, const char *));
268 static void print_code
269 PARAMS ((enum rtx_code));
270 static void write_afterward
271 PARAMS ((struct decision *, struct decision *, const char *));
272 static struct decision *write_switch
273 PARAMS ((struct decision *, int));
274 static void write_cond
275 PARAMS ((struct decision_test *, int, enum routine_type));
276 static void write_action
277 PARAMS ((struct decision *, struct decision_test *, int, int,
278 struct decision *, enum routine_type));
279 static int is_unconditional
280 PARAMS ((struct decision_test *, enum routine_type));
281 static int write_node
282 PARAMS ((struct decision *, int, enum routine_type));
283 static void write_tree_1
284 PARAMS ((struct decision_head *, int, enum routine_type));
285 static void write_tree
286 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
287 static void write_subroutine
288 PARAMS ((struct decision_head *, enum routine_type));
289 static void write_subroutines
290 PARAMS ((struct decision_head *, enum routine_type));
291 static void write_header
294 static struct decision_head make_insn_sequence
295 PARAMS ((rtx, enum routine_type));
296 static void process_tree
297 PARAMS ((struct decision_head *, enum routine_type));
299 static void record_insn_name
300 PARAMS ((int, const char *));
302 static void debug_decision_0
303 PARAMS ((struct decision *, int, int));
304 static void debug_decision_1
305 PARAMS ((struct decision *, int));
306 static void debug_decision_2
307 PARAMS ((struct decision_test *));
308 extern void debug_decision
309 PARAMS ((struct decision *));
310 extern void debug_decision_list
311 PARAMS ((struct decision *));
313 /* Create a new node in sequence after LAST. */
315 static struct decision *
316 new_decision (position, last)
317 const char *position;
318 struct decision_head *last;
320 register struct decision *new
321 = (struct decision *) xmalloc (sizeof (struct decision));
323 memset (new, 0, sizeof (*new));
324 new->success = *last;
325 new->position = xstrdup (position);
326 new->number = next_number++;
328 last->first = last->last = new;
332 /* Create a new test and link it in at PLACE. */
334 static struct decision_test *
335 new_decision_test (type, pplace)
336 enum decision_type type;
337 struct decision_test ***pplace;
339 struct decision_test **place = *pplace;
340 struct decision_test *test;
342 test = (struct decision_test *) xmalloc (sizeof (*test));
353 /* Search for and return operand N. */
356 find_operand (pattern, n)
365 code = GET_CODE (pattern);
366 if ((code == MATCH_SCRATCH
367 || code == MATCH_INSN
368 || code == MATCH_OPERAND
369 || code == MATCH_OPERATOR
370 || code == MATCH_PARALLEL)
371 && XINT (pattern, 0) == n)
374 fmt = GET_RTX_FORMAT (code);
375 len = GET_RTX_LENGTH (code);
376 for (i = 0; i < len; i++)
381 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
386 if (! XVEC (pattern, i))
391 for (j = 0; j < XVECLEN (pattern, i); j++)
392 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
396 case 'i': case 'w': case '0': case 's':
407 /* Search for and return operand M, such that it has a matching
408 constraint for operand N. */
411 find_matching_operand (pattern, n)
420 code = GET_CODE (pattern);
421 if (code == MATCH_OPERAND
422 && (XSTR (pattern, 2)[0] == '0' + n
423 || (XSTR (pattern, 2)[0] == '%'
424 && XSTR (pattern, 2)[1] == '0' + n)))
427 fmt = GET_RTX_FORMAT (code);
428 len = GET_RTX_LENGTH (code);
429 for (i = 0; i < len; i++)
434 if ((r = find_matching_operand (XEXP (pattern, i), n)))
439 if (! XVEC (pattern, i))
444 for (j = 0; j < XVECLEN (pattern, i); j++)
445 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
449 case 'i': case 'w': case '0': case 's':
461 /* Check for various errors in patterns. SET is nonnull for a destination,
462 and is the complete set pattern. SET_CODE is '=' for normal sets, and
463 '+' within a context that requires in-out constraints. */
466 validate_pattern (pattern, insn, set, set_code)
477 code = GET_CODE (pattern);
487 const char *pred_name = XSTR (pattern, 1);
488 int allows_non_lvalue = 1, allows_non_const = 1;
489 int special_mode_pred = 0;
492 if (GET_CODE (insn) == DEFINE_INSN)
493 c_test = XSTR (insn, 2);
495 c_test = XSTR (insn, 1);
497 if (pred_name[0] != 0)
499 for (i = 0; i < NUM_KNOWN_PREDS; i++)
500 if (! strcmp (preds[i].name, pred_name))
503 if (i < NUM_KNOWN_PREDS)
507 allows_non_lvalue = allows_non_const = 0;
508 for (j = 0; preds[i].codes[j] != 0; j++)
510 RTX_CODE c = preds[i].codes[j];
517 && c != CONSTANT_P_RTX)
518 allows_non_const = 1;
525 && c != STRICT_LOW_PART)
526 allows_non_lvalue = 1;
531 #ifdef PREDICATE_CODES
532 /* If the port has a list of the predicates it uses but
534 message_with_line (pattern_lineno,
535 "warning: `%s' not in PREDICATE_CODES",
540 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
541 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
543 special_mode_pred = 1;
548 /* A MATCH_OPERAND that is a SET should have an output reload. */
549 if (set && code == MATCH_OPERAND
550 && XSTR (pattern, 2)[0] != '\0')
554 if (XSTR (pattern, 2)[0] == '+')
556 /* If we've only got an output reload for this operand,
557 we'd better have a matching input operand. */
558 else if (XSTR (pattern, 2)[0] == '='
559 && find_matching_operand (insn, XINT (pattern, 0)))
563 message_with_line (pattern_lineno,
564 "operand %d missing in-out reload",
569 else if (XSTR (pattern, 2)[0] != '='
570 && XSTR (pattern, 2)[0] != '+')
572 message_with_line (pattern_lineno,
573 "operand %d missing output reload",
579 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
580 while not likely to occur at runtime, results in less efficient
581 code from insn-recog.c. */
583 && pred_name[0] != '\0'
584 && allows_non_lvalue)
586 message_with_line (pattern_lineno,
587 "warning: destination operand %d allows non-lvalue",
591 /* A modeless MATCH_OPERAND can be handy when we can
592 check for multiple modes in the c_test. In most other cases,
593 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
594 and PEEP2 can FAIL within the output pattern. Exclude
595 address_operand, since its mode is related to the mode of
596 the memory not the operand. Exclude the SET_DEST of a call
597 instruction, as that is a common idiom. */
599 if (GET_MODE (pattern) == VOIDmode
600 && code == MATCH_OPERAND
601 && GET_CODE (insn) == DEFINE_INSN
603 && ! special_mode_pred
604 && pred_name[0] != '\0'
605 && strcmp (pred_name, "address_operand") != 0
606 && strstr (c_test, "operands") == NULL
608 && GET_CODE (set) == SET
609 && GET_CODE (SET_SRC (set)) == CALL))
611 message_with_line (pattern_lineno,
612 "warning: operand %d missing mode?",
620 enum machine_mode dmode, smode;
623 dest = SET_DEST (pattern);
624 src = SET_SRC (pattern);
626 /* Find the referant for a DUP. */
628 if (GET_CODE (dest) == MATCH_DUP
629 || GET_CODE (dest) == MATCH_OP_DUP
630 || GET_CODE (dest) == MATCH_PAR_DUP)
631 dest = find_operand (insn, XINT (dest, 0));
633 if (GET_CODE (src) == MATCH_DUP
634 || GET_CODE (src) == MATCH_OP_DUP
635 || GET_CODE (src) == MATCH_PAR_DUP)
636 src = find_operand (insn, XINT (src, 0));
638 /* STRICT_LOW_PART is a wrapper. Its argument is the real
639 destination, and it's mode should match the source. */
640 if (GET_CODE (dest) == STRICT_LOW_PART)
641 dest = XEXP (dest, 0);
643 dmode = GET_MODE (dest);
644 smode = GET_MODE (src);
646 /* The mode of an ADDRESS_OPERAND is the mode of the memory
647 reference, not the mode of the address. */
648 if (GET_CODE (src) == MATCH_OPERAND
649 && ! strcmp (XSTR (src, 1), "address_operand"))
652 /* The operands of a SET must have the same mode unless one
654 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
656 message_with_line (pattern_lineno,
657 "mode mismatch in set: %smode vs %smode",
658 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
662 /* If only one of the operands is VOIDmode, and PC or CC0 is
663 not involved, it's probably a mistake. */
664 else if (dmode != smode
665 && GET_CODE (dest) != PC
666 && GET_CODE (dest) != CC0
667 && GET_CODE (src) != PC
668 && GET_CODE (src) != CC0
669 && GET_CODE (src) != CONST_INT)
672 which = (dmode == VOIDmode ? "destination" : "source");
673 message_with_line (pattern_lineno,
674 "warning: %s missing a mode?", which);
677 if (dest != SET_DEST (pattern))
678 validate_pattern (dest, insn, pattern, '=');
679 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
680 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
685 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
689 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
690 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
691 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
694 case STRICT_LOW_PART:
695 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
699 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
701 message_with_line (pattern_lineno,
702 "operand to label_ref %smode not VOIDmode",
703 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
712 fmt = GET_RTX_FORMAT (code);
713 len = GET_RTX_LENGTH (code);
714 for (i = 0; i < len; i++)
719 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
723 for (j = 0; j < XVECLEN (pattern, i); j++)
724 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
727 case 'i': case 'w': case '0': case 's':
736 /* Create a chain of nodes to verify that an rtl expression matches
739 LAST is a pointer to the listhead in the previous node in the chain (or
740 in the calling function, for the first node).
742 POSITION is the string representing the current position in the insn.
744 INSN_TYPE is the type of insn for which we are emitting code.
746 A pointer to the final node in the chain is returned. */
748 static struct decision *
749 add_to_sequence (pattern, last, position, insn_type, top)
751 struct decision_head *last;
752 const char *position;
753 enum routine_type insn_type;
757 struct decision *this, *sub;
758 struct decision_test *test;
759 struct decision_test **place;
762 register const char *fmt;
763 int depth = strlen (position);
765 enum machine_mode mode;
767 if (depth > max_depth)
770 subpos = (char *) xmalloc (depth + 2);
771 strcpy (subpos, position);
772 subpos[depth + 1] = 0;
774 sub = this = new_decision (position, last);
775 place = &this->tests;
778 mode = GET_MODE (pattern);
779 code = GET_CODE (pattern);
784 /* Toplevel peephole pattern. */
785 if (insn_type == PEEPHOLE2 && top)
787 /* We don't need the node we just created -- unlink it. */
788 last->first = last->last = NULL;
790 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
792 /* Which insn we're looking at is represented by A-Z. We don't
793 ever use 'A', however; it is always implied. */
795 subpos[depth] = (i > 0 ? 'A' + i : 0);
796 sub = add_to_sequence (XVECEXP (pattern, 0, i),
797 last, subpos, insn_type, 0);
798 last = &sub->success;
803 /* Else nothing special. */
807 /* The explicit patterns within a match_parallel enforce a minimum
808 length on the vector. The match_parallel predicate may allow
809 for more elements. We do need to check for this minimum here
810 or the code generated to match the internals may reference data
811 beyond the end of the vector. */
812 test = new_decision_test (DT_veclen_ge, &place);
813 test->u.veclen = XVECLEN (pattern, 2);
821 const char *pred_name;
822 RTX_CODE was_code = code;
823 int allows_const_int = 1;
825 if (code == MATCH_SCRATCH)
827 pred_name = "scratch_operand";
832 pred_name = XSTR (pattern, 1);
833 if (code == MATCH_PARALLEL)
839 if (pred_name[0] != 0)
841 test = new_decision_test (DT_pred, &place);
842 test->u.pred.name = pred_name;
843 test->u.pred.mode = mode;
845 /* See if we know about this predicate and save its number. If
846 we do, and it only accepts one code, note that fact. The
847 predicate `const_int_operand' only tests for a CONST_INT, so
848 if we do so we can avoid calling it at all.
850 Finally, if we know that the predicate does not allow
851 CONST_INT, we know that the only way the predicate can match
852 is if the modes match (here we use the kludge of relying on
853 the fact that "address_operand" accepts CONST_INT; otherwise,
854 it would have to be a special case), so we can test the mode
855 (but we need not). This fact should considerably simplify the
858 for (i = 0; i < NUM_KNOWN_PREDS; i++)
859 if (! strcmp (preds[i].name, pred_name))
862 if (i < NUM_KNOWN_PREDS)
866 test->u.pred.index = i;
868 if (preds[i].codes[1] == 0 && code == UNKNOWN)
869 code = preds[i].codes[0];
871 allows_const_int = 0;
872 for (j = 0; preds[i].codes[j] != 0; j++)
873 if (preds[i].codes[j] == CONST_INT)
875 allows_const_int = 1;
880 test->u.pred.index = -1;
883 /* Can't enforce a mode if we allow const_int. */
884 if (allows_const_int)
887 /* Accept the operand, ie. record it in `operands'. */
888 test = new_decision_test (DT_accept_op, &place);
889 test->u.opno = XINT (pattern, 0);
891 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
893 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
894 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
896 subpos[depth] = i + base;
897 sub = add_to_sequence (XVECEXP (pattern, 2, i),
898 &sub->success, subpos, insn_type, 0);
907 test = new_decision_test (DT_dup, &place);
908 test->u.dup = XINT (pattern, 0);
910 test = new_decision_test (DT_accept_op, &place);
911 test->u.opno = XINT (pattern, 0);
913 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
915 subpos[depth] = i + '0';
916 sub = add_to_sequence (XVECEXP (pattern, 1, i),
917 &sub->success, subpos, insn_type, 0);
925 test = new_decision_test (DT_dup, &place);
926 test->u.dup = XINT (pattern, 0);
930 pattern = XEXP (pattern, 0);
937 fmt = GET_RTX_FORMAT (code);
938 len = GET_RTX_LENGTH (code);
940 /* Do tests against the current node first. */
941 for (i = 0; i < (size_t) len; i++)
947 test = new_decision_test (DT_elt_zero_int, &place);
948 test->u.intval = XINT (pattern, i);
952 test = new_decision_test (DT_elt_one_int, &place);
953 test->u.intval = XINT (pattern, i);
958 else if (fmt[i] == 'w')
960 /* If this value actually fits in an int, we can use a switch
961 statement here, so indicate that. */
962 enum decision_type type
963 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
964 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
969 test = new_decision_test (type, &place);
970 test->u.intval = XWINT (pattern, i);
972 else if (fmt[i] == 'E')
977 test = new_decision_test (DT_veclen, &place);
978 test->u.veclen = XVECLEN (pattern, i);
982 /* Now test our sub-patterns. */
983 for (i = 0; i < (size_t) len; i++)
988 subpos[depth] = '0' + i;
989 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
990 subpos, insn_type, 0);
996 for (j = 0; j < XVECLEN (pattern, i); j++)
998 subpos[depth] = 'a' + j;
999 sub = add_to_sequence (XVECEXP (pattern, i, j),
1000 &sub->success, subpos, insn_type, 0);
1006 /* Handled above. */
1017 /* Insert nodes testing mode and code, if they're still relevant,
1018 before any of the nodes we may have added above. */
1019 if (code != UNKNOWN)
1021 place = &this->tests;
1022 test = new_decision_test (DT_code, &place);
1023 test->u.code = code;
1026 if (mode != VOIDmode)
1028 place = &this->tests;
1029 test = new_decision_test (DT_mode, &place);
1030 test->u.mode = mode;
1033 /* If we didn't insert any tests or accept nodes, hork. */
1034 if (this->tests == NULL)
1042 /* A subroutine of maybe_both_true; examines only one test.
1043 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1046 maybe_both_true_2 (d1, d2)
1047 struct decision_test *d1, *d2;
1049 if (d1->type == d2->type)
1054 return d1->u.mode == d2->u.mode;
1057 return d1->u.code == d2->u.code;
1060 return d1->u.veclen == d2->u.veclen;
1062 case DT_elt_zero_int:
1063 case DT_elt_one_int:
1064 case DT_elt_zero_wide:
1065 case DT_elt_zero_wide_safe:
1066 return d1->u.intval == d2->u.intval;
1073 /* If either has a predicate that we know something about, set
1074 things up so that D1 is the one that always has a known
1075 predicate. Then see if they have any codes in common. */
1077 if (d1->type == DT_pred || d2->type == DT_pred)
1079 if (d2->type == DT_pred)
1081 struct decision_test *tmp;
1082 tmp = d1, d1 = d2, d2 = tmp;
1085 /* If D2 tests a mode, see if it matches D1. */
1086 if (d1->u.pred.mode != VOIDmode)
1088 if (d2->type == DT_mode)
1090 if (d1->u.pred.mode != d2->u.mode
1091 /* The mode of an address_operand predicate is the
1092 mode of the memory, not the operand. It can only
1093 be used for testing the predicate, so we must
1095 && strcmp (d1->u.pred.name, "address_operand") != 0)
1098 /* Don't check two predicate modes here, because if both predicates
1099 accept CONST_INT, then both can still be true even if the modes
1100 are different. If they don't accept CONST_INT, there will be a
1101 separate DT_mode that will make maybe_both_true_1 return 0. */
1104 if (d1->u.pred.index >= 0)
1106 /* If D2 tests a code, see if it is in the list of valid
1107 codes for D1's predicate. */
1108 if (d2->type == DT_code)
1110 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1113 if (*c == d2->u.code)
1121 /* Otherwise see if the predicates have any codes in common. */
1122 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1124 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1127 while (*c1 != 0 && !common)
1129 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1130 while (*c2 != 0 && !common)
1132 common = (*c1 == *c2);
1144 /* Tests vs veclen may be known when strict equality is involved. */
1145 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1146 return d1->u.veclen >= d2->u.veclen;
1147 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1148 return d2->u.veclen >= d1->u.veclen;
1153 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1154 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1157 maybe_both_true_1 (d1, d2)
1158 struct decision_test *d1, *d2;
1160 struct decision_test *t1, *t2;
1162 /* A match_operand with no predicate can match anything. Recognize
1163 this by the existance of a lone DT_accept_op test. */
1164 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1167 /* Eliminate pairs of tests while they can exactly match. */
1168 while (d1 && d2 && d1->type == d2->type)
1170 if (maybe_both_true_2 (d1, d2) == 0)
1172 d1 = d1->next, d2 = d2->next;
1175 /* After that, consider all pairs. */
1176 for (t1 = d1; t1 ; t1 = t1->next)
1177 for (t2 = d2; t2 ; t2 = t2->next)
1178 if (maybe_both_true_2 (t1, t2) == 0)
1184 /* Return 0 if we can prove that there is no RTL that can match both
1185 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1186 can match both or just that we couldn't prove there wasn't such an RTL).
1188 TOPLEVEL is non-zero if we are to only look at the top level and not
1189 recursively descend. */
1192 maybe_both_true (d1, d2, toplevel)
1193 struct decision *d1, *d2;
1196 struct decision *p1, *p2;
1199 /* Don't compare strings on the different positions in insn. Doing so
1200 is incorrect and results in false matches from constructs like
1202 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1203 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1205 [(set (match_operand:HI "register_operand" "r")
1206 (match_operand:HI "register_operand" "r"))]
1208 If we are presented with such, we are recursing through the remainder
1209 of a node's success nodes (from the loop at the end of this function).
1210 Skip forward until we come to a position that matches.
1212 Due to the way position strings are constructed, we know that iterating
1213 forward from the lexically lower position (e.g. "00") will run into
1214 the lexically higher position (e.g. "1") and not the other way around.
1215 This saves a bit of effort. */
1217 cmp = strcmp (d1->position, d2->position);
1223 /* If the d2->position was lexically lower, swap. */
1225 p1 = d1, d1 = d2, d2 = p1;
1227 if (d1->success.first == 0)
1229 for (p1 = d1->success.first; p1; p1 = p1->next)
1230 if (maybe_both_true (p1, d2, 0))
1236 /* Test the current level. */
1237 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1241 /* We can't prove that D1 and D2 cannot both be true. If we are only
1242 to check the top level, return 1. Otherwise, see if we can prove
1243 that all choices in both successors are mutually exclusive. If
1244 either does not have any successors, we can't prove they can't both
1247 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1250 for (p1 = d1->success.first; p1; p1 = p1->next)
1251 for (p2 = d2->success.first; p2; p2 = p2->next)
1252 if (maybe_both_true (p1, p2, 0))
1258 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1261 nodes_identical_1 (d1, d2)
1262 struct decision_test *d1, *d2;
1267 return d1->u.mode == d2->u.mode;
1270 return d1->u.code == d2->u.code;
1273 return (d1->u.pred.mode == d2->u.pred.mode
1274 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1277 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1281 return d1->u.veclen == d2->u.veclen;
1284 return d1->u.dup == d2->u.dup;
1286 case DT_elt_zero_int:
1287 case DT_elt_one_int:
1288 case DT_elt_zero_wide:
1289 case DT_elt_zero_wide_safe:
1290 return d1->u.intval == d2->u.intval;
1293 return d1->u.opno == d2->u.opno;
1295 case DT_accept_insn:
1296 /* Differences will be handled in merge_accept_insn. */
1304 /* True iff the two nodes are identical (on one level only). Due
1305 to the way these lists are constructed, we shouldn't have to
1306 consider different orderings on the tests. */
1309 nodes_identical (d1, d2)
1310 struct decision *d1, *d2;
1312 struct decision_test *t1, *t2;
1314 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1316 if (t1->type != t2->type)
1318 if (! nodes_identical_1 (t1, t2))
1322 /* For success, they should now both be null. */
1326 /* Check that their subnodes are at the same position, as any one set
1327 of sibling decisions must be at the same position. Allowing this
1328 requires complications to find_afterward and when change_state is
1330 if (d1->success.first
1331 && d2->success.first
1332 && strcmp (d1->success.first->position, d2->success.first->position))
1338 /* A subroutine of merge_trees; given two nodes that have been declared
1339 identical, cope with two insn accept states. If they differ in the
1340 number of clobbers, then the conflict was created by make_insn_sequence
1341 and we can drop the with-clobbers version on the floor. If both
1342 nodes have no additional clobbers, we have found an ambiguity in the
1343 source machine description. */
1346 merge_accept_insn (oldd, addd)
1347 struct decision *oldd, *addd;
1349 struct decision_test *old, *add;
1351 for (old = oldd->tests; old; old = old->next)
1352 if (old->type == DT_accept_insn)
1357 for (add = addd->tests; add; add = add->next)
1358 if (add->type == DT_accept_insn)
1363 /* If one node is for a normal insn and the second is for the base
1364 insn with clobbers stripped off, the second node should be ignored. */
1366 if (old->u.insn.num_clobbers_to_add == 0
1367 && add->u.insn.num_clobbers_to_add > 0)
1369 /* Nothing to do here. */
1371 else if (old->u.insn.num_clobbers_to_add > 0
1372 && add->u.insn.num_clobbers_to_add == 0)
1374 /* In this case, replace OLD with ADD. */
1375 old->u.insn = add->u.insn;
1379 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1380 get_insn_name (add->u.insn.code_number),
1381 get_insn_name (old->u.insn.code_number));
1382 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1383 get_insn_name (old->u.insn.code_number));
1388 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1391 merge_trees (oldh, addh)
1392 struct decision_head *oldh, *addh;
1394 struct decision *next, *add;
1396 if (addh->first == 0)
1398 if (oldh->first == 0)
1404 /* Trying to merge bits at different positions isn't possible. */
1405 if (strcmp (oldh->first->position, addh->first->position))
1408 for (add = addh->first; add ; add = next)
1410 struct decision *old, *insert_before = NULL;
1414 /* The semantics of pattern matching state that the tests are
1415 done in the order given in the MD file so that if an insn
1416 matches two patterns, the first one will be used. However,
1417 in practice, most, if not all, patterns are unambiguous so
1418 that their order is independent. In that case, we can merge
1419 identical tests and group all similar modes and codes together.
1421 Scan starting from the end of OLDH until we reach a point
1422 where we reach the head of the list or where we pass a
1423 pattern that could also be true if NEW is true. If we find
1424 an identical pattern, we can merge them. Also, record the
1425 last node that tests the same code and mode and the last one
1426 that tests just the same mode.
1428 If we have no match, place NEW after the closest match we found. */
1430 for (old = oldh->last; old; old = old->prev)
1432 if (nodes_identical (old, add))
1434 merge_accept_insn (old, add);
1435 merge_trees (&old->success, &add->success);
1439 if (maybe_both_true (old, add, 0))
1442 /* Insert the nodes in DT test type order, which is roughly
1443 how expensive/important the test is. Given that the tests
1444 are also ordered within the list, examining the first is
1446 if ((int) add->tests->type < (int) old->tests->type)
1447 insert_before = old;
1450 if (insert_before == NULL)
1453 add->prev = oldh->last;
1454 oldh->last->next = add;
1459 if ((add->prev = insert_before->prev) != NULL)
1460 add->prev->next = add;
1463 add->next = insert_before;
1464 insert_before->prev = add;
1471 /* Walk the tree looking for sub-nodes that perform common tests.
1472 Factor out the common test into a new node. This enables us
1473 (depending on the test type) to emit switch statements later. */
1477 struct decision_head *head;
1479 struct decision *first, *next;
1481 for (first = head->first; first && first->next; first = next)
1483 enum decision_type type;
1484 struct decision *new, *old_last;
1486 type = first->tests->type;
1489 /* Want at least two compatible sequential nodes. */
1490 if (next->tests->type != type)
1493 /* Don't want all node types, just those we can turn into
1494 switch statements. */
1497 && type != DT_veclen
1498 && type != DT_elt_zero_int
1499 && type != DT_elt_one_int
1500 && type != DT_elt_zero_wide_safe)
1503 /* If we'd been performing more than one test, create a new node
1504 below our first test. */
1505 if (first->tests->next != NULL)
1507 new = new_decision (first->position, &first->success);
1508 new->tests = first->tests->next;
1509 first->tests->next = NULL;
1512 /* Crop the node tree off after our first test. */
1514 old_last = head->last;
1517 /* For each compatible test, adjust to perform only one test in
1518 the top level node, then merge the node back into the tree. */
1521 struct decision_head h;
1523 if (next->tests->next != NULL)
1525 new = new_decision (next->position, &next->success);
1526 new->tests = next->tests->next;
1527 next->tests->next = NULL;
1532 h.first = h.last = new;
1534 merge_trees (head, &h);
1536 while (next && next->tests->type == type);
1538 /* After we run out of compatible tests, graft the remaining nodes
1539 back onto the tree. */
1542 next->prev = head->last;
1543 head->last->next = next;
1544 head->last = old_last;
1549 for (first = head->first; first; first = first->next)
1550 factor_tests (&first->success);
1553 /* After factoring, try to simplify the tests on any one node.
1554 Tests that are useful for switch statements are recognizable
1555 by having only a single test on a node -- we'll be manipulating
1556 nodes with multiple tests:
1558 If we have mode tests or code tests that are redundant with
1559 predicates, remove them. */
1562 simplify_tests (head)
1563 struct decision_head *head;
1565 struct decision *tree;
1567 for (tree = head->first; tree; tree = tree->next)
1569 struct decision_test *a, *b;
1576 /* Find a predicate node. */
1577 while (b && b->type != DT_pred)
1581 /* Due to how these tests are constructed, we don't even need
1582 to check that the mode and code are compatible -- they were
1583 generated from the predicate in the first place. */
1584 while (a->type == DT_mode || a->type == DT_code)
1591 for (tree = head->first; tree; tree = tree->next)
1592 simplify_tests (&tree->success);
1595 /* Count the number of subnodes of HEAD. If the number is high enough,
1596 make the first node in HEAD start a separate subroutine in the C code
1597 that is generated. */
1600 break_out_subroutines (head, initial)
1601 struct decision_head *head;
1605 struct decision *sub;
1607 for (sub = head->first; sub; sub = sub->next)
1608 size += 1 + break_out_subroutines (&sub->success, 0);
1610 if (size > SUBROUTINE_THRESHOLD && ! initial)
1612 head->first->subroutine_number = ++next_subroutine_number;
1618 /* For each node p, find the next alternative that might be true
1622 find_afterward (head, real_afterward)
1623 struct decision_head *head;
1624 struct decision *real_afterward;
1626 struct decision *p, *q, *afterward;
1628 /* We can't propogate alternatives across subroutine boundaries.
1629 This is not incorrect, merely a minor optimization loss. */
1632 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1634 for ( ; p ; p = p->next)
1636 /* Find the next node that might be true if this one fails. */
1637 for (q = p->next; q ; q = q->next)
1638 if (maybe_both_true (p, q, 1))
1641 /* If we reached the end of the list without finding one,
1642 use the incoming afterward position. */
1651 for (p = head->first; p ; p = p->next)
1652 if (p->success.first)
1653 find_afterward (&p->success, p->afterward);
1655 /* When we are generating a subroutine, record the real afterward
1656 position in the first node where write_tree can find it, and we
1657 can do the right thing at the subroutine call site. */
1659 if (p->subroutine_number > 0)
1660 p->afterward = real_afterward;
1663 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1664 actions are necessary to move to NEWPOS. If we fail to move to the
1665 new state, branch to node AFTERWARD if non-zero, otherwise return.
1667 Failure to move to the new state can only occur if we are trying to
1668 match multiple insns and we try to step past the end of the stream. */
1671 change_state (oldpos, newpos, afterward, indent)
1674 struct decision *afterward;
1677 int odepth = strlen (oldpos);
1678 int ndepth = strlen (newpos);
1680 int old_has_insn, new_has_insn;
1682 /* Pop up as many levels as necessary. */
1683 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1686 /* Hunt for the last [A-Z] in both strings. */
1687 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1688 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1690 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1691 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1694 /* Go down to desired level. */
1695 while (depth < ndepth)
1697 /* It's a different insn from the first one. */
1698 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1700 /* We can only fail if we're moving down the tree. */
1701 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1703 printf ("%stem = peep2_next_insn (%d);\n",
1704 indent, newpos[depth] - 'A');
1708 printf ("%stem = peep2_next_insn (%d);\n",
1709 indent, newpos[depth] - 'A');
1710 printf ("%sif (tem == NULL_RTX)\n", indent);
1712 printf ("%s goto L%d;\n", indent, afterward->number);
1714 printf ("%s goto ret0;\n", indent);
1716 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1718 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1719 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1720 indent, depth + 1, depth, newpos[depth] - 'a');
1722 printf ("%sx%d = XEXP (x%d, %c);\n",
1723 indent, depth + 1, depth, newpos[depth]);
1728 /* Print the enumerator constant for CODE -- the upcase version of
1735 register const char *p;
1736 for (p = GET_RTX_NAME (code); *p; p++)
1737 putchar (TOUPPER (*p));
1740 /* Emit code to cross an afterward link -- change state and branch. */
1743 write_afterward (start, afterward, indent)
1744 struct decision *start;
1745 struct decision *afterward;
1748 if (!afterward || start->subroutine_number > 0)
1749 printf("%sgoto ret0;\n", indent);
1752 change_state (start->position, afterward->position, NULL, indent);
1753 printf ("%sgoto L%d;\n", indent, afterward->number);
1757 /* Emit a switch statement, if possible, for an initial sequence of
1758 nodes at START. Return the first node yet untested. */
1760 static struct decision *
1761 write_switch (start, depth)
1762 struct decision *start;
1765 struct decision *p = start;
1766 enum decision_type type = p->tests->type;
1767 struct decision *needs_label = NULL;
1769 /* If we have two or more nodes in sequence that test the same one
1770 thing, we may be able to use a switch statement. */
1774 || p->next->tests->type != type
1775 || p->next->tests->next
1776 || nodes_identical_1 (p->tests, p->next->tests))
1779 /* DT_code is special in that we can do interesting things with
1780 known predicates at the same time. */
1781 if (type == DT_code)
1783 char codemap[NUM_RTX_CODE];
1784 struct decision *ret;
1787 memset (codemap, 0, sizeof(codemap));
1789 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1790 code = p->tests->u.code;
1793 if (p != start && p->need_label && needs_label == NULL)
1798 printf (":\n goto L%d;\n", p->success.first->number);
1799 p->success.first->need_label = 1;
1806 && p->tests->type == DT_code
1807 && ! codemap[code = p->tests->u.code]);
1809 /* If P is testing a predicate that we know about and we haven't
1810 seen any of the codes that are valid for the predicate, we can
1811 write a series of "case" statement, one for each possible code.
1812 Since we are already in a switch, these redundant tests are very
1813 cheap and will reduce the number of predicates called. */
1815 /* Note that while we write out cases for these predicates here,
1816 we don't actually write the test here, as it gets kinda messy.
1817 It is trivial to leave this to later by telling our caller that
1818 we only processed the CODE tests. */
1819 if (needs_label != NULL)
1824 while (p && p->tests->type == DT_pred
1825 && p->tests->u.pred.index >= 0)
1829 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1830 if (codemap[(int) *c] != 0)
1833 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1838 codemap[(int) *c] = 1;
1841 printf (" goto L%d;\n", p->number);
1847 /* Make the default case skip the predicates we managed to match. */
1849 printf (" default:\n");
1854 printf (" goto L%d;\n", p->number);
1858 write_afterward (start, start->afterward, " ");
1861 printf (" break;\n");
1866 else if (type == DT_mode
1867 || type == DT_veclen
1868 || type == DT_elt_zero_int
1869 || type == DT_elt_one_int
1870 || type == DT_elt_zero_wide_safe)
1872 printf (" switch (");
1876 printf ("GET_MODE (x%d)", depth);
1879 printf ("XVECLEN (x%d, 0)", depth);
1881 case DT_elt_zero_int:
1882 printf ("XINT (x%d, 0)", depth);
1884 case DT_elt_one_int:
1885 printf ("XINT (x%d, 1)", depth);
1887 case DT_elt_zero_wide_safe:
1888 /* Convert result of XWINT to int for portability since some C
1889 compilers won't do it and some will. */
1890 printf ("(int) XWINT (x%d, 0)", depth);
1899 /* Merge trees will not unify identical nodes if their
1900 sub-nodes are at different levels. Thus we must check
1901 for duplicate cases. */
1903 for (q = start; q != p; q = q->next)
1904 if (nodes_identical_1 (p->tests, q->tests))
1907 if (p != start && p->need_label && needs_label == NULL)
1914 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1917 printf ("%d", p->tests->u.veclen);
1919 case DT_elt_zero_int:
1920 case DT_elt_one_int:
1921 case DT_elt_zero_wide:
1922 case DT_elt_zero_wide_safe:
1923 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1928 printf (":\n goto L%d;\n", p->success.first->number);
1929 p->success.first->need_label = 1;
1933 while (p && p->tests->type == type && !p->tests->next);
1936 printf (" default:\n break;\n }\n");
1938 return needs_label != NULL ? needs_label : p;
1942 /* None of the other tests are ameanable. */
1947 /* Emit code for one test. */
1950 write_cond (p, depth, subroutine_type)
1951 struct decision_test *p;
1953 enum routine_type subroutine_type;
1958 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1962 printf ("GET_CODE (x%d) == ", depth);
1963 print_code (p->u.code);
1967 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1970 case DT_elt_zero_int:
1971 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1974 case DT_elt_one_int:
1975 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1978 case DT_elt_zero_wide:
1979 case DT_elt_zero_wide_safe:
1980 printf ("XWINT (x%d, 0) == ", depth);
1981 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1985 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
1989 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1993 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1994 GET_MODE_NAME (p->u.pred.mode));
1998 printf ("(%s)", p->u.c_test);
2001 case DT_accept_insn:
2002 switch (subroutine_type)
2005 if (p->u.insn.num_clobbers_to_add == 0)
2007 printf ("pnum_clobbers != NULL");
2020 /* Emit code for one action. The previous tests have succeeded;
2021 TEST is the last of the chain. In the normal case we simply
2022 perform a state change. For the `accept' tests we must do more work. */
2025 write_action (p, test, depth, uncond, success, subroutine_type)
2027 struct decision_test *test;
2029 struct decision *success;
2030 enum routine_type subroutine_type;
2037 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2039 fputs (" {\n", stdout);
2046 if (test->type == DT_accept_op)
2048 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2050 /* Only allow DT_accept_insn to follow. */
2054 if (test->type != DT_accept_insn)
2059 /* Sanity check that we're now at the end of the list of tests. */
2063 if (test->type == DT_accept_insn)
2065 switch (subroutine_type)
2068 if (test->u.insn.num_clobbers_to_add != 0)
2069 printf ("%s*pnum_clobbers = %d;\n",
2070 indent, test->u.insn.num_clobbers_to_add);
2071 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2075 printf ("%sreturn gen_split_%d (operands);\n",
2076 indent, test->u.insn.code_number);
2081 int match_len = 0, i;
2083 for (i = strlen (p->position) - 1; i >= 0; --i)
2084 if (p->position[i] >= 'A' && p->position[i] <= 'Z')
2086 match_len = p->position[i] - 'A';
2089 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2090 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2091 indent, test->u.insn.code_number);
2092 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2102 printf("%sgoto L%d;\n", indent, success->number);
2103 success->need_label = 1;
2107 fputs (" }\n", stdout);
2110 /* Return 1 if the test is always true and has no fallthru path. Return -1
2111 if the test does have a fallthru path, but requires that the condition be
2112 terminated. Otherwise return 0 for a normal test. */
2113 /* ??? is_unconditional is a stupid name for a tri-state function. */
2116 is_unconditional (t, subroutine_type)
2117 struct decision_test *t;
2118 enum routine_type subroutine_type;
2120 if (t->type == DT_accept_op)
2123 if (t->type == DT_accept_insn)
2125 switch (subroutine_type)
2128 return (t->u.insn.num_clobbers_to_add == 0);
2141 /* Emit code for one node -- the conditional and the accompanying action.
2142 Return true if there is no fallthru path. */
2145 write_node (p, depth, subroutine_type)
2148 enum routine_type subroutine_type;
2150 struct decision_test *test, *last_test;
2153 last_test = test = p->tests;
2154 uncond = is_unconditional (test, subroutine_type);
2158 write_cond (test, depth, subroutine_type);
2160 while ((test = test->next) != NULL)
2165 uncond2 = is_unconditional (test, subroutine_type);
2170 write_cond (test, depth, subroutine_type);
2176 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2181 /* Emit code for all of the sibling nodes of HEAD. */
2184 write_tree_1 (head, depth, subroutine_type)
2185 struct decision_head *head;
2187 enum routine_type subroutine_type;
2189 struct decision *p, *next;
2192 for (p = head->first; p ; p = next)
2194 /* The label for the first element was printed in write_tree. */
2195 if (p != head->first && p->need_label)
2196 OUTPUT_LABEL (" ", p->number);
2198 /* Attempt to write a switch statement for a whole sequence. */
2199 next = write_switch (p, depth);
2204 /* Failed -- fall back and write one node. */
2205 uncond = write_node (p, depth, subroutine_type);
2210 /* Finished with this chain. Close a fallthru path by branching
2211 to the afterward node. */
2213 write_afterward (head->last, head->last->afterward, " ");
2216 /* Write out the decision tree starting at HEAD. PREVPOS is the
2217 position at the node that branched to this node. */
2220 write_tree (head, prevpos, type, initial)
2221 struct decision_head *head;
2222 const char *prevpos;
2223 enum routine_type type;
2226 register struct decision *p = head->first;
2230 OUTPUT_LABEL (" ", p->number);
2232 if (! initial && p->subroutine_number > 0)
2234 static const char * const name_prefix[] = {
2235 "recog", "split", "peephole2"
2238 static const char * const call_suffix[] = {
2239 ", pnum_clobbers", "", ", _pmatch_len"
2242 /* This node has been broken out into a separate subroutine.
2243 Call it, test the result, and branch accordingly. */
2247 printf (" tem = %s_%d (x0, insn%s);\n",
2248 name_prefix[type], p->subroutine_number, call_suffix[type]);
2249 if (IS_SPLIT (type))
2250 printf (" if (tem != 0)\n return tem;\n");
2252 printf (" if (tem >= 0)\n return tem;\n");
2254 change_state (p->position, p->afterward->position, NULL, " ");
2255 printf (" goto L%d;\n", p->afterward->number);
2259 printf (" return %s_%d (x0, insn%s);\n",
2260 name_prefix[type], p->subroutine_number, call_suffix[type]);
2265 int depth = strlen (p->position);
2267 change_state (prevpos, p->position, head->last->afterward, " ");
2268 write_tree_1 (head, depth, type);
2270 for (p = head->first; p; p = p->next)
2271 if (p->success.first)
2272 write_tree (&p->success, p->position, type, 0);
2276 /* Write out a subroutine of type TYPE to do comparisons starting at
2280 write_subroutine (head, type)
2281 struct decision_head *head;
2282 enum routine_type type;
2284 int subfunction = head->first ? head->first->subroutine_number : 0;
2289 s_or_e = subfunction ? "static " : "";
2292 sprintf (extension, "_%d", subfunction);
2293 else if (type == RECOG)
2294 extension[0] = '\0';
2296 strcpy (extension, "_insns");
2301 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2303 recog%s (x0, insn, pnum_clobbers)\n\
2305 rtx insn ATTRIBUTE_UNUSED;\n\
2306 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2309 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2311 split%s (x0, insn)\n\
2313 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2316 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2319 peephole2%s (x0, insn, _pmatch_len)\n\
2321 rtx insn ATTRIBUTE_UNUSED;\n\
2322 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2326 printf ("{\n register rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2327 for (i = 1; i <= max_depth; i++)
2328 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
2330 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2333 printf (" recog_data.insn = NULL_RTX;\n");
2336 write_tree (head, "", type, 1);
2338 printf (" goto ret0;\n");
2340 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2343 /* In break_out_subroutines, we discovered the boundaries for the
2344 subroutines, but did not write them out. Do so now. */
2347 write_subroutines (head, type)
2348 struct decision_head *head;
2349 enum routine_type type;
2353 for (p = head->first; p ; p = p->next)
2354 if (p->success.first)
2355 write_subroutines (&p->success, type);
2357 if (head->first->subroutine_number > 0)
2358 write_subroutine (head, type);
2361 /* Begin the output file. */
2367 /* Generated automatically by the program `genrecog' from the target\n\
2368 machine description file. */\n\
2370 #include \"config.h\"\n\
2371 #include \"system.h\"\n\
2372 #include \"rtl.h\"\n\
2373 #include \"tm_p.h\"\n\
2374 #include \"function.h\"\n\
2375 #include \"insn-config.h\"\n\
2376 #include \"recog.h\"\n\
2377 #include \"real.h\"\n\
2378 #include \"output.h\"\n\
2379 #include \"flags.h\"\n\
2380 #include \"hard-reg-set.h\"\n\
2381 #include \"resource.h\"\n\
2382 #include \"toplev.h\"\n\
2386 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2387 X0 is a valid instruction.\n\
2389 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2390 returns a nonnegative number which is the insn code number for the\n\
2391 pattern that matched. This is the same as the order in the machine\n\
2392 description of the entry that matched. This number can be used as an\n\
2393 index into `insn_data' and other tables.\n");
2395 The third argument to recog is an optional pointer to an int. If\n\
2396 present, recog will accept a pattern if it matches except for missing\n\
2397 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2398 the optional pointer will be set to the number of CLOBBERs that need\n\
2399 to be added (it should be initialized to zero by the caller). If it");
2401 is set nonzero, the caller should allocate a PARALLEL of the\n\
2402 appropriate size, copy the initial entries, and call add_clobbers\n\
2403 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2407 The function split_insns returns 0 if the rtl could not\n\
2408 be split or the split rtl in a SEQUENCE if it can be.\n\
2410 The function peephole2_insns returns 0 if the rtl could not\n\
2411 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2412 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2417 /* Construct and return a sequence of decisions
2418 that will recognize INSN.
2420 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2422 static struct decision_head
2423 make_insn_sequence (insn, type)
2425 enum routine_type type;
2428 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2429 struct decision *last;
2430 struct decision_test *test, **place;
2431 struct decision_head head;
2434 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2436 c_test_pos[0] = '\0';
2437 if (type == PEEPHOLE2)
2441 /* peephole2 gets special treatment:
2442 - X always gets an outer parallel even if it's only one entry
2443 - we remove all traces of outer-level match_scratch and match_dup
2444 expressions here. */
2445 x = rtx_alloc (PARALLEL);
2446 PUT_MODE (x, VOIDmode);
2447 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2448 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2450 rtx tmp = XVECEXP (insn, 0, i);
2451 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2453 XVECEXP (x, 0, j) = tmp;
2459 c_test_pos[0] = 'A' + j - 1;
2460 c_test_pos[1] = '\0';
2462 else if (XVECLEN (insn, type == RECOG) == 1)
2463 x = XVECEXP (insn, type == RECOG, 0);
2466 x = rtx_alloc (PARALLEL);
2467 XVEC (x, 0) = XVEC (insn, type == RECOG);
2468 PUT_MODE (x, VOIDmode);
2471 validate_pattern (x, insn, NULL_RTX, 0);
2473 memset(&head, 0, sizeof(head));
2474 last = add_to_sequence (x, &head, "", type, 1);
2476 /* Find the end of the test chain on the last node. */
2477 for (test = last->tests; test->next; test = test->next)
2479 place = &test->next;
2483 /* Need a new node if we have another test to add. */
2484 if (test->type == DT_accept_op)
2486 last = new_decision (c_test_pos, &last->success);
2487 place = &last->tests;
2489 test = new_decision_test (DT_c_test, &place);
2490 test->u.c_test = c_test;
2493 test = new_decision_test (DT_accept_insn, &place);
2494 test->u.insn.code_number = next_insn_code;
2495 test->u.insn.lineno = pattern_lineno;
2496 test->u.insn.num_clobbers_to_add = 0;
2501 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2502 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2503 If so, set up to recognize the pattern without these CLOBBERs. */
2505 if (GET_CODE (x) == PARALLEL)
2509 /* Find the last non-clobber in the parallel. */
2510 for (i = XVECLEN (x, 0); i > 0; i--)
2512 rtx y = XVECEXP (x, 0, i - 1);
2513 if (GET_CODE (y) != CLOBBER
2514 || (GET_CODE (XEXP (y, 0)) != REG
2515 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2519 if (i != XVECLEN (x, 0))
2522 struct decision_head clobber_head;
2524 /* Build a similar insn without the clobbers. */
2526 new = XVECEXP (x, 0, 0);
2531 new = rtx_alloc (PARALLEL);
2532 XVEC (new, 0) = rtvec_alloc (i);
2533 for (j = i - 1; j >= 0; j--)
2534 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2538 memset (&clobber_head, 0, sizeof(clobber_head));
2539 last = add_to_sequence (new, &clobber_head, "", type, 1);
2541 /* Find the end of the test chain on the last node. */
2542 for (test = last->tests; test->next; test = test->next)
2545 /* We definitely have a new test to add -- create a new
2547 place = &test->next;
2548 if (test->type == DT_accept_op)
2550 last = new_decision ("", &last->success);
2551 place = &last->tests;
2556 test = new_decision_test (DT_c_test, &place);
2557 test->u.c_test = c_test;
2560 test = new_decision_test (DT_accept_insn, &place);
2561 test->u.insn.code_number = next_insn_code;
2562 test->u.insn.lineno = pattern_lineno;
2563 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2565 merge_trees (&head, &clobber_head);
2571 /* Define the subroutine we will call below and emit in genemit. */
2572 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2576 /* Define the subroutine we will call below and emit in genemit. */
2577 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2586 process_tree (head, subroutine_type)
2587 struct decision_head *head;
2588 enum routine_type subroutine_type;
2590 if (head->first == NULL)
2592 /* We can elide peephole2_insns, but not recog or split_insns. */
2593 if (subroutine_type == PEEPHOLE2)
2598 factor_tests (head);
2600 next_subroutine_number = 0;
2601 break_out_subroutines (head, 1);
2602 find_afterward (head, NULL);
2604 /* We run this after find_afterward, because find_afterward needs
2605 the redundant DT_mode tests on predicates to determine whether
2606 two tests can both be true or not. */
2607 simplify_tests(head);
2609 write_subroutines (head, subroutine_type);
2612 write_subroutine (head, subroutine_type);
2615 extern int main PARAMS ((int, char **));
2623 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2625 progname = "genrecog";
2627 memset (&recog_tree, 0, sizeof recog_tree);
2628 memset (&split_tree, 0, sizeof split_tree);
2629 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2632 fatal ("No input file name.");
2634 if (init_md_reader (argv[1]) != SUCCESS_EXIT_CODE)
2635 return (FATAL_EXIT_CODE);
2642 /* Read the machine description. */
2646 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2650 if (GET_CODE (desc) == DEFINE_INSN)
2652 h = make_insn_sequence (desc, RECOG);
2653 merge_trees (&recog_tree, &h);
2655 else if (GET_CODE (desc) == DEFINE_SPLIT)
2657 h = make_insn_sequence (desc, SPLIT);
2658 merge_trees (&split_tree, &h);
2660 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2662 h = make_insn_sequence (desc, PEEPHOLE2);
2663 merge_trees (&peephole2_tree, &h);
2670 return FATAL_EXIT_CODE;
2674 process_tree (&recog_tree, RECOG);
2675 process_tree (&split_tree, SPLIT);
2676 process_tree (&peephole2_tree, PEEPHOLE2);
2679 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2682 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2684 get_insn_name (code)
2687 if (code < insn_name_ptr_size)
2688 return insn_name_ptr[code];
2694 record_insn_name (code, name)
2698 static const char *last_real_name = "insn";
2699 static int last_real_code = 0;
2702 if (insn_name_ptr_size <= code)
2705 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2707 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2708 memset (insn_name_ptr + insn_name_ptr_size, 0,
2709 sizeof(char *) * (new_size - insn_name_ptr_size));
2710 insn_name_ptr_size = new_size;
2713 if (!name || name[0] == '\0')
2715 new = xmalloc (strlen (last_real_name) + 10);
2716 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2720 last_real_name = new = xstrdup (name);
2721 last_real_code = code;
2724 insn_name_ptr[code] = new;
2728 debug_decision_2 (test)
2729 struct decision_test *test;
2734 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2737 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2740 fprintf (stderr, "veclen=%d", test->u.veclen);
2742 case DT_elt_zero_int:
2743 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2745 case DT_elt_one_int:
2746 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2748 case DT_elt_zero_wide:
2749 fprintf (stderr, "elt0_w=");
2750 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2752 case DT_elt_zero_wide_safe:
2753 fprintf (stderr, "elt0_ws=");
2754 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2757 fprintf (stderr, "veclen>=%d", test->u.veclen);
2760 fprintf (stderr, "dup=%d", test->u.dup);
2763 fprintf (stderr, "pred=(%s,%s)",
2764 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2769 strncpy (sub, test->u.c_test, sizeof(sub));
2770 memcpy (sub+16, "...", 4);
2771 fprintf (stderr, "c_test=\"%s\"", sub);
2775 fprintf (stderr, "A_op=%d", test->u.opno);
2777 case DT_accept_insn:
2778 fprintf (stderr, "A_insn=(%d,%d)",
2779 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2788 debug_decision_1 (d, indent)
2793 struct decision_test *test;
2797 for (i = 0; i < indent; ++i)
2799 fputs ("(nil)\n", stderr);
2803 for (i = 0; i < indent; ++i)
2810 debug_decision_2 (test);
2811 while ((test = test->next) != NULL)
2813 fputs (" + ", stderr);
2814 debug_decision_2 (test);
2817 fprintf (stderr, "} %d n %d a %d\n", d->number,
2818 (d->next ? d->next->number : -1),
2819 (d->afterward ? d->afterward->number : -1));
2823 debug_decision_0 (d, indent, maxdepth)
2825 int indent, maxdepth;
2834 for (i = 0; i < indent; ++i)
2836 fputs ("(nil)\n", stderr);
2840 debug_decision_1 (d, indent);
2841 for (n = d->success.first; n ; n = n->next)
2842 debug_decision_0 (n, indent + 2, maxdepth - 1);
2849 debug_decision_0 (d, 0, 1000000);
2853 debug_decision_list (d)
2858 debug_decision_0 (d, 0, 0);