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, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 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 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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 an INSN list, 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 const struct pred_table
186 const char *const name;
187 const RTX_CODE codes[NUM_RTX_CODE];
189 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
190 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}},
191 #ifdef PREDICATE_CODES
194 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
195 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF,
197 {"register_operand", {SUBREG, REG, ADDRESSOF}},
198 {"pmode_register_operand", {SUBREG, REG, ADDRESSOF}},
199 {"scratch_operand", {SCRATCH, REG}},
200 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
202 {"const_int_operand", {CONST_INT}},
203 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
204 {"nonimmediate_operand", {SUBREG, REG, MEM, ADDRESSOF}},
205 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
206 LABEL_REF, SUBREG, REG, ADDRESSOF}},
207 {"push_operand", {MEM}},
208 {"pop_operand", {MEM}},
209 {"memory_operand", {SUBREG, MEM}},
210 {"indirect_operand", {SUBREG, MEM}},
211 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
212 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
214 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
215 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}}
218 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
220 static const char *const special_mode_pred_table[] = {
221 #ifdef SPECIAL_MODE_PREDICATES
222 SPECIAL_MODE_PREDICATES
224 "pmode_register_operand"
227 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
229 static struct decision *new_decision
230 PARAMS ((const char *, struct decision_head *));
231 static struct decision_test *new_decision_test
232 PARAMS ((enum decision_type, struct decision_test ***));
233 static rtx find_operand
235 static rtx find_matching_operand
237 static void validate_pattern
238 PARAMS ((rtx, rtx, rtx, int));
239 static struct decision *add_to_sequence
240 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
242 static int maybe_both_true_2
243 PARAMS ((struct decision_test *, struct decision_test *));
244 static int maybe_both_true_1
245 PARAMS ((struct decision_test *, struct decision_test *));
246 static int maybe_both_true
247 PARAMS ((struct decision *, struct decision *, int));
249 static int nodes_identical_1
250 PARAMS ((struct decision_test *, struct decision_test *));
251 static int nodes_identical
252 PARAMS ((struct decision *, struct decision *));
253 static void merge_accept_insn
254 PARAMS ((struct decision *, struct decision *));
255 static void merge_trees
256 PARAMS ((struct decision_head *, struct decision_head *));
258 static void factor_tests
259 PARAMS ((struct decision_head *));
260 static void simplify_tests
261 PARAMS ((struct decision_head *));
262 static int break_out_subroutines
263 PARAMS ((struct decision_head *, int));
264 static void find_afterward
265 PARAMS ((struct decision_head *, struct decision *));
267 static void change_state
268 PARAMS ((const char *, const char *, struct decision *, const char *));
269 static void print_code
270 PARAMS ((enum rtx_code));
271 static void write_afterward
272 PARAMS ((struct decision *, struct decision *, const char *));
273 static struct decision *write_switch
274 PARAMS ((struct decision *, int));
275 static void write_cond
276 PARAMS ((struct decision_test *, int, enum routine_type));
277 static void write_action
278 PARAMS ((struct decision *, struct decision_test *, int, int,
279 struct decision *, enum routine_type));
280 static int is_unconditional
281 PARAMS ((struct decision_test *, enum routine_type));
282 static int write_node
283 PARAMS ((struct decision *, int, enum routine_type));
284 static void write_tree_1
285 PARAMS ((struct decision_head *, int, enum routine_type));
286 static void write_tree
287 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
288 static void write_subroutine
289 PARAMS ((struct decision_head *, enum routine_type));
290 static void write_subroutines
291 PARAMS ((struct decision_head *, enum routine_type));
292 static void write_header
295 static struct decision_head make_insn_sequence
296 PARAMS ((rtx, enum routine_type));
297 static void process_tree
298 PARAMS ((struct decision_head *, enum routine_type));
300 static void record_insn_name
301 PARAMS ((int, const char *));
303 static void debug_decision_0
304 PARAMS ((struct decision *, int, int));
305 static void debug_decision_1
306 PARAMS ((struct decision *, int));
307 static void debug_decision_2
308 PARAMS ((struct decision_test *));
309 extern void debug_decision
310 PARAMS ((struct decision *));
311 extern void debug_decision_list
312 PARAMS ((struct decision *));
314 /* Create a new node in sequence after LAST. */
316 static struct decision *
317 new_decision (position, last)
318 const char *position;
319 struct decision_head *last;
322 = (struct decision *) xmalloc (sizeof (struct decision));
324 memset (new, 0, sizeof (*new));
325 new->success = *last;
326 new->position = xstrdup (position);
327 new->number = next_number++;
329 last->first = last->last = new;
333 /* Create a new test and link it in at PLACE. */
335 static struct decision_test *
336 new_decision_test (type, pplace)
337 enum decision_type type;
338 struct decision_test ***pplace;
340 struct decision_test **place = *pplace;
341 struct decision_test *test;
343 test = (struct decision_test *) xmalloc (sizeof (*test));
354 /* Search for and return operand N. */
357 find_operand (pattern, n)
366 code = GET_CODE (pattern);
367 if ((code == MATCH_SCRATCH
368 || code == MATCH_INSN
369 || code == MATCH_OPERAND
370 || code == MATCH_OPERATOR
371 || code == MATCH_PARALLEL)
372 && XINT (pattern, 0) == n)
375 fmt = GET_RTX_FORMAT (code);
376 len = GET_RTX_LENGTH (code);
377 for (i = 0; i < len; i++)
382 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
387 if (! XVEC (pattern, i))
392 for (j = 0; j < XVECLEN (pattern, i); j++)
393 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
397 case 'i': case 'w': case '0': case 's':
408 /* Search for and return operand M, such that it has a matching
409 constraint for operand N. */
412 find_matching_operand (pattern, n)
421 code = GET_CODE (pattern);
422 if (code == MATCH_OPERAND
423 && (XSTR (pattern, 2)[0] == '0' + n
424 || (XSTR (pattern, 2)[0] == '%'
425 && XSTR (pattern, 2)[1] == '0' + n)))
428 fmt = GET_RTX_FORMAT (code);
429 len = GET_RTX_LENGTH (code);
430 for (i = 0; i < len; i++)
435 if ((r = find_matching_operand (XEXP (pattern, i), n)))
440 if (! XVEC (pattern, i))
445 for (j = 0; j < XVECLEN (pattern, i); j++)
446 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
450 case 'i': case 'w': case '0': case 's':
462 /* Check for various errors in patterns. SET is nonnull for a destination,
463 and is the complete set pattern. SET_CODE is '=' for normal sets, and
464 '+' within a context that requires in-out constraints. */
467 validate_pattern (pattern, insn, set, set_code)
478 code = GET_CODE (pattern);
488 const char *pred_name = XSTR (pattern, 1);
489 int allows_non_lvalue = 1, allows_non_const = 1;
490 int special_mode_pred = 0;
493 if (GET_CODE (insn) == DEFINE_INSN)
494 c_test = XSTR (insn, 2);
496 c_test = XSTR (insn, 1);
498 if (pred_name[0] != 0)
500 for (i = 0; i < NUM_KNOWN_PREDS; i++)
501 if (! strcmp (preds[i].name, pred_name))
504 if (i < NUM_KNOWN_PREDS)
508 allows_non_lvalue = allows_non_const = 0;
509 for (j = 0; preds[i].codes[j] != 0; j++)
511 RTX_CODE c = preds[i].codes[j];
518 && c != CONSTANT_P_RTX)
519 allows_non_const = 1;
527 && c != STRICT_LOW_PART)
528 allows_non_lvalue = 1;
533 #ifdef PREDICATE_CODES
534 /* If the port has a list of the predicates it uses but
536 message_with_line (pattern_lineno,
537 "warning: `%s' not in PREDICATE_CODES",
542 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
543 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
545 special_mode_pred = 1;
550 if (code == MATCH_OPERAND)
552 const char constraints0 = XSTR (pattern, 2)[0];
554 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
555 don't use the MATCH_OPERAND constraint, only the predicate.
556 This is confusing to folks doing new ports, so help them
557 not make the mistake. */
558 if (GET_CODE (insn) == DEFINE_EXPAND
559 || GET_CODE (insn) == DEFINE_SPLIT
560 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
563 message_with_line (pattern_lineno,
564 "warning: constraints not supported in %s",
565 rtx_name[GET_CODE (insn)]);
568 /* A MATCH_OPERAND that is a SET should have an output reload. */
569 else if (set && constraints0)
573 if (constraints0 == '+')
575 /* If we've only got an output reload for this operand,
576 we'd better have a matching input operand. */
577 else if (constraints0 == '='
578 && find_matching_operand (insn, XINT (pattern, 0)))
582 message_with_line (pattern_lineno,
583 "operand %d missing in-out reload",
588 else if (constraints0 != '=' && constraints0 != '+')
590 message_with_line (pattern_lineno,
591 "operand %d missing output reload",
598 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
599 while not likely to occur at runtime, results in less efficient
600 code from insn-recog.c. */
602 && pred_name[0] != '\0'
603 && allows_non_lvalue)
605 message_with_line (pattern_lineno,
606 "warning: destination operand %d allows non-lvalue",
610 /* A modeless MATCH_OPERAND can be handy when we can
611 check for multiple modes in the c_test. In most other cases,
612 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
613 and PEEP2 can FAIL within the output pattern. Exclude
614 address_operand, since its mode is related to the mode of
615 the memory not the operand. Exclude the SET_DEST of a call
616 instruction, as that is a common idiom. */
618 if (GET_MODE (pattern) == VOIDmode
619 && code == MATCH_OPERAND
620 && GET_CODE (insn) == DEFINE_INSN
622 && ! special_mode_pred
623 && pred_name[0] != '\0'
624 && strcmp (pred_name, "address_operand") != 0
625 && strstr (c_test, "operands") == NULL
627 && GET_CODE (set) == SET
628 && GET_CODE (SET_SRC (set)) == CALL))
630 message_with_line (pattern_lineno,
631 "warning: operand %d missing mode?",
639 enum machine_mode dmode, smode;
642 dest = SET_DEST (pattern);
643 src = SET_SRC (pattern);
645 /* STRICT_LOW_PART is a wrapper. Its argument is the real
646 destination, and it's mode should match the source. */
647 if (GET_CODE (dest) == STRICT_LOW_PART)
648 dest = XEXP (dest, 0);
650 /* Find the referant for a DUP. */
652 if (GET_CODE (dest) == MATCH_DUP
653 || GET_CODE (dest) == MATCH_OP_DUP
654 || GET_CODE (dest) == MATCH_PAR_DUP)
655 dest = find_operand (insn, XINT (dest, 0));
657 if (GET_CODE (src) == MATCH_DUP
658 || GET_CODE (src) == MATCH_OP_DUP
659 || GET_CODE (src) == MATCH_PAR_DUP)
660 src = find_operand (insn, XINT (src, 0));
662 dmode = GET_MODE (dest);
663 smode = GET_MODE (src);
665 /* The mode of an ADDRESS_OPERAND is the mode of the memory
666 reference, not the mode of the address. */
667 if (GET_CODE (src) == MATCH_OPERAND
668 && ! strcmp (XSTR (src, 1), "address_operand"))
671 /* The operands of a SET must have the same mode unless one
673 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
675 message_with_line (pattern_lineno,
676 "mode mismatch in set: %smode vs %smode",
677 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
681 /* If only one of the operands is VOIDmode, and PC or CC0 is
682 not involved, it's probably a mistake. */
683 else if (dmode != smode
684 && GET_CODE (dest) != PC
685 && GET_CODE (dest) != CC0
686 && GET_CODE (src) != PC
687 && GET_CODE (src) != CC0
688 && GET_CODE (src) != CONST_INT)
691 which = (dmode == VOIDmode ? "destination" : "source");
692 message_with_line (pattern_lineno,
693 "warning: %s missing a mode?", which);
696 if (dest != SET_DEST (pattern))
697 validate_pattern (dest, insn, pattern, '=');
698 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
699 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
704 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
708 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
709 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
710 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
713 case STRICT_LOW_PART:
714 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
718 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
720 message_with_line (pattern_lineno,
721 "operand to label_ref %smode not VOIDmode",
722 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
731 fmt = GET_RTX_FORMAT (code);
732 len = GET_RTX_LENGTH (code);
733 for (i = 0; i < len; i++)
738 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
742 for (j = 0; j < XVECLEN (pattern, i); j++)
743 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
746 case 'i': case 'w': case '0': case 's':
755 /* Create a chain of nodes to verify that an rtl expression matches
758 LAST is a pointer to the listhead in the previous node in the chain (or
759 in the calling function, for the first node).
761 POSITION is the string representing the current position in the insn.
763 INSN_TYPE is the type of insn for which we are emitting code.
765 A pointer to the final node in the chain is returned. */
767 static struct decision *
768 add_to_sequence (pattern, last, position, insn_type, top)
770 struct decision_head *last;
771 const char *position;
772 enum routine_type insn_type;
776 struct decision *this, *sub;
777 struct decision_test *test;
778 struct decision_test **place;
782 int depth = strlen (position);
784 enum machine_mode mode;
786 if (depth > max_depth)
789 subpos = (char *) xmalloc (depth + 2);
790 strcpy (subpos, position);
791 subpos[depth + 1] = 0;
793 sub = this = new_decision (position, last);
794 place = &this->tests;
797 mode = GET_MODE (pattern);
798 code = GET_CODE (pattern);
803 /* Toplevel peephole pattern. */
804 if (insn_type == PEEPHOLE2 && top)
806 /* We don't need the node we just created -- unlink it. */
807 last->first = last->last = NULL;
809 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
811 /* Which insn we're looking at is represented by A-Z. We don't
812 ever use 'A', however; it is always implied. */
814 subpos[depth] = (i > 0 ? 'A' + i : 0);
815 sub = add_to_sequence (XVECEXP (pattern, 0, i),
816 last, subpos, insn_type, 0);
817 last = &sub->success;
822 /* Else nothing special. */
826 /* The explicit patterns within a match_parallel enforce a minimum
827 length on the vector. The match_parallel predicate may allow
828 for more elements. We do need to check for this minimum here
829 or the code generated to match the internals may reference data
830 beyond the end of the vector. */
831 test = new_decision_test (DT_veclen_ge, &place);
832 test->u.veclen = XVECLEN (pattern, 2);
840 const char *pred_name;
841 RTX_CODE was_code = code;
842 int allows_const_int = 1;
844 if (code == MATCH_SCRATCH)
846 pred_name = "scratch_operand";
851 pred_name = XSTR (pattern, 1);
852 if (code == MATCH_PARALLEL)
858 if (pred_name[0] != 0)
860 test = new_decision_test (DT_pred, &place);
861 test->u.pred.name = pred_name;
862 test->u.pred.mode = mode;
864 /* See if we know about this predicate and save its number.
865 If we do, and it only accepts one code, note that fact.
867 If we know that the predicate does not allow CONST_INT,
868 we know that the only way the predicate can match is if
869 the modes match (here we use the kludge of relying on the
870 fact that "address_operand" accepts CONST_INT; otherwise,
871 it would have to be a special case), so we can test the
872 mode (but we need not). This fact should considerably
873 simplify the generated code. */
875 for (i = 0; i < NUM_KNOWN_PREDS; i++)
876 if (! strcmp (preds[i].name, pred_name))
879 if (i < NUM_KNOWN_PREDS)
883 test->u.pred.index = i;
885 if (preds[i].codes[1] == 0 && code == UNKNOWN)
886 code = preds[i].codes[0];
888 allows_const_int = 0;
889 for (j = 0; preds[i].codes[j] != 0; j++)
890 if (preds[i].codes[j] == CONST_INT)
892 allows_const_int = 1;
897 test->u.pred.index = -1;
900 /* Can't enforce a mode if we allow const_int. */
901 if (allows_const_int)
904 /* Accept the operand, ie. record it in `operands'. */
905 test = new_decision_test (DT_accept_op, &place);
906 test->u.opno = XINT (pattern, 0);
908 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
910 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
911 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
913 subpos[depth] = i + base;
914 sub = add_to_sequence (XVECEXP (pattern, 2, i),
915 &sub->success, subpos, insn_type, 0);
924 test = new_decision_test (DT_dup, &place);
925 test->u.dup = XINT (pattern, 0);
927 test = new_decision_test (DT_accept_op, &place);
928 test->u.opno = XINT (pattern, 0);
930 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
932 subpos[depth] = i + '0';
933 sub = add_to_sequence (XVECEXP (pattern, 1, i),
934 &sub->success, subpos, insn_type, 0);
942 test = new_decision_test (DT_dup, &place);
943 test->u.dup = XINT (pattern, 0);
947 pattern = XEXP (pattern, 0);
954 fmt = GET_RTX_FORMAT (code);
955 len = GET_RTX_LENGTH (code);
957 /* Do tests against the current node first. */
958 for (i = 0; i < (size_t) len; i++)
964 test = new_decision_test (DT_elt_zero_int, &place);
965 test->u.intval = XINT (pattern, i);
969 test = new_decision_test (DT_elt_one_int, &place);
970 test->u.intval = XINT (pattern, i);
975 else if (fmt[i] == 'w')
977 /* If this value actually fits in an int, we can use a switch
978 statement here, so indicate that. */
979 enum decision_type type
980 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
981 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
986 test = new_decision_test (type, &place);
987 test->u.intval = XWINT (pattern, i);
989 else if (fmt[i] == 'E')
994 test = new_decision_test (DT_veclen, &place);
995 test->u.veclen = XVECLEN (pattern, i);
999 /* Now test our sub-patterns. */
1000 for (i = 0; i < (size_t) len; i++)
1005 subpos[depth] = '0' + i;
1006 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1007 subpos, insn_type, 0);
1013 for (j = 0; j < XVECLEN (pattern, i); j++)
1015 subpos[depth] = 'a' + j;
1016 sub = add_to_sequence (XVECEXP (pattern, i, j),
1017 &sub->success, subpos, insn_type, 0);
1023 /* Handled above. */
1034 /* Insert nodes testing mode and code, if they're still relevant,
1035 before any of the nodes we may have added above. */
1036 if (code != UNKNOWN)
1038 place = &this->tests;
1039 test = new_decision_test (DT_code, &place);
1040 test->u.code = code;
1043 if (mode != VOIDmode)
1045 place = &this->tests;
1046 test = new_decision_test (DT_mode, &place);
1047 test->u.mode = mode;
1050 /* If we didn't insert any tests or accept nodes, hork. */
1051 if (this->tests == NULL)
1059 /* A subroutine of maybe_both_true; examines only one test.
1060 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1063 maybe_both_true_2 (d1, d2)
1064 struct decision_test *d1, *d2;
1066 if (d1->type == d2->type)
1071 return d1->u.mode == d2->u.mode;
1074 return d1->u.code == d2->u.code;
1077 return d1->u.veclen == d2->u.veclen;
1079 case DT_elt_zero_int:
1080 case DT_elt_one_int:
1081 case DT_elt_zero_wide:
1082 case DT_elt_zero_wide_safe:
1083 return d1->u.intval == d2->u.intval;
1090 /* If either has a predicate that we know something about, set
1091 things up so that D1 is the one that always has a known
1092 predicate. Then see if they have any codes in common. */
1094 if (d1->type == DT_pred || d2->type == DT_pred)
1096 if (d2->type == DT_pred)
1098 struct decision_test *tmp;
1099 tmp = d1, d1 = d2, d2 = tmp;
1102 /* If D2 tests a mode, see if it matches D1. */
1103 if (d1->u.pred.mode != VOIDmode)
1105 if (d2->type == DT_mode)
1107 if (d1->u.pred.mode != d2->u.mode
1108 /* The mode of an address_operand predicate is the
1109 mode of the memory, not the operand. It can only
1110 be used for testing the predicate, so we must
1112 && strcmp (d1->u.pred.name, "address_operand") != 0)
1115 /* Don't check two predicate modes here, because if both predicates
1116 accept CONST_INT, then both can still be true even if the modes
1117 are different. If they don't accept CONST_INT, there will be a
1118 separate DT_mode that will make maybe_both_true_1 return 0. */
1121 if (d1->u.pred.index >= 0)
1123 /* If D2 tests a code, see if it is in the list of valid
1124 codes for D1's predicate. */
1125 if (d2->type == DT_code)
1127 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1130 if (*c == d2->u.code)
1138 /* Otherwise see if the predicates have any codes in common. */
1139 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1141 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1144 while (*c1 != 0 && !common)
1146 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1147 while (*c2 != 0 && !common)
1149 common = (*c1 == *c2);
1161 /* Tests vs veclen may be known when strict equality is involved. */
1162 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1163 return d1->u.veclen >= d2->u.veclen;
1164 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1165 return d2->u.veclen >= d1->u.veclen;
1170 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1171 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1174 maybe_both_true_1 (d1, d2)
1175 struct decision_test *d1, *d2;
1177 struct decision_test *t1, *t2;
1179 /* A match_operand with no predicate can match anything. Recognize
1180 this by the existence of a lone DT_accept_op test. */
1181 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1184 /* Eliminate pairs of tests while they can exactly match. */
1185 while (d1 && d2 && d1->type == d2->type)
1187 if (maybe_both_true_2 (d1, d2) == 0)
1189 d1 = d1->next, d2 = d2->next;
1192 /* After that, consider all pairs. */
1193 for (t1 = d1; t1 ; t1 = t1->next)
1194 for (t2 = d2; t2 ; t2 = t2->next)
1195 if (maybe_both_true_2 (t1, t2) == 0)
1201 /* Return 0 if we can prove that there is no RTL that can match both
1202 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1203 can match both or just that we couldn't prove there wasn't such an RTL).
1205 TOPLEVEL is nonzero if we are to only look at the top level and not
1206 recursively descend. */
1209 maybe_both_true (d1, d2, toplevel)
1210 struct decision *d1, *d2;
1213 struct decision *p1, *p2;
1216 /* Don't compare strings on the different positions in insn. Doing so
1217 is incorrect and results in false matches from constructs like
1219 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1220 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1222 [(set (match_operand:HI "register_operand" "r")
1223 (match_operand:HI "register_operand" "r"))]
1225 If we are presented with such, we are recursing through the remainder
1226 of a node's success nodes (from the loop at the end of this function).
1227 Skip forward until we come to a position that matches.
1229 Due to the way position strings are constructed, we know that iterating
1230 forward from the lexically lower position (e.g. "00") will run into
1231 the lexically higher position (e.g. "1") and not the other way around.
1232 This saves a bit of effort. */
1234 cmp = strcmp (d1->position, d2->position);
1240 /* If the d2->position was lexically lower, swap. */
1242 p1 = d1, d1 = d2, d2 = p1;
1244 if (d1->success.first == 0)
1246 for (p1 = d1->success.first; p1; p1 = p1->next)
1247 if (maybe_both_true (p1, d2, 0))
1253 /* Test the current level. */
1254 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1258 /* We can't prove that D1 and D2 cannot both be true. If we are only
1259 to check the top level, return 1. Otherwise, see if we can prove
1260 that all choices in both successors are mutually exclusive. If
1261 either does not have any successors, we can't prove they can't both
1264 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1267 for (p1 = d1->success.first; p1; p1 = p1->next)
1268 for (p2 = d2->success.first; p2; p2 = p2->next)
1269 if (maybe_both_true (p1, p2, 0))
1275 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1278 nodes_identical_1 (d1, d2)
1279 struct decision_test *d1, *d2;
1284 return d1->u.mode == d2->u.mode;
1287 return d1->u.code == d2->u.code;
1290 return (d1->u.pred.mode == d2->u.pred.mode
1291 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1294 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1298 return d1->u.veclen == d2->u.veclen;
1301 return d1->u.dup == d2->u.dup;
1303 case DT_elt_zero_int:
1304 case DT_elt_one_int:
1305 case DT_elt_zero_wide:
1306 case DT_elt_zero_wide_safe:
1307 return d1->u.intval == d2->u.intval;
1310 return d1->u.opno == d2->u.opno;
1312 case DT_accept_insn:
1313 /* Differences will be handled in merge_accept_insn. */
1321 /* True iff the two nodes are identical (on one level only). Due
1322 to the way these lists are constructed, we shouldn't have to
1323 consider different orderings on the tests. */
1326 nodes_identical (d1, d2)
1327 struct decision *d1, *d2;
1329 struct decision_test *t1, *t2;
1331 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1333 if (t1->type != t2->type)
1335 if (! nodes_identical_1 (t1, t2))
1339 /* For success, they should now both be null. */
1343 /* Check that their subnodes are at the same position, as any one set
1344 of sibling decisions must be at the same position. Allowing this
1345 requires complications to find_afterward and when change_state is
1347 if (d1->success.first
1348 && d2->success.first
1349 && strcmp (d1->success.first->position, d2->success.first->position))
1355 /* A subroutine of merge_trees; given two nodes that have been declared
1356 identical, cope with two insn accept states. If they differ in the
1357 number of clobbers, then the conflict was created by make_insn_sequence
1358 and we can drop the with-clobbers version on the floor. If both
1359 nodes have no additional clobbers, we have found an ambiguity in the
1360 source machine description. */
1363 merge_accept_insn (oldd, addd)
1364 struct decision *oldd, *addd;
1366 struct decision_test *old, *add;
1368 for (old = oldd->tests; old; old = old->next)
1369 if (old->type == DT_accept_insn)
1374 for (add = addd->tests; add; add = add->next)
1375 if (add->type == DT_accept_insn)
1380 /* If one node is for a normal insn and the second is for the base
1381 insn with clobbers stripped off, the second node should be ignored. */
1383 if (old->u.insn.num_clobbers_to_add == 0
1384 && add->u.insn.num_clobbers_to_add > 0)
1386 /* Nothing to do here. */
1388 else if (old->u.insn.num_clobbers_to_add > 0
1389 && add->u.insn.num_clobbers_to_add == 0)
1391 /* In this case, replace OLD with ADD. */
1392 old->u.insn = add->u.insn;
1396 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1397 get_insn_name (add->u.insn.code_number),
1398 get_insn_name (old->u.insn.code_number));
1399 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1400 get_insn_name (old->u.insn.code_number));
1405 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1408 merge_trees (oldh, addh)
1409 struct decision_head *oldh, *addh;
1411 struct decision *next, *add;
1413 if (addh->first == 0)
1415 if (oldh->first == 0)
1421 /* Trying to merge bits at different positions isn't possible. */
1422 if (strcmp (oldh->first->position, addh->first->position))
1425 for (add = addh->first; add ; add = next)
1427 struct decision *old, *insert_before = NULL;
1431 /* The semantics of pattern matching state that the tests are
1432 done in the order given in the MD file so that if an insn
1433 matches two patterns, the first one will be used. However,
1434 in practice, most, if not all, patterns are unambiguous so
1435 that their order is independent. In that case, we can merge
1436 identical tests and group all similar modes and codes together.
1438 Scan starting from the end of OLDH until we reach a point
1439 where we reach the head of the list or where we pass a
1440 pattern that could also be true if NEW is true. If we find
1441 an identical pattern, we can merge them. Also, record the
1442 last node that tests the same code and mode and the last one
1443 that tests just the same mode.
1445 If we have no match, place NEW after the closest match we found. */
1447 for (old = oldh->last; old; old = old->prev)
1449 if (nodes_identical (old, add))
1451 merge_accept_insn (old, add);
1452 merge_trees (&old->success, &add->success);
1456 if (maybe_both_true (old, add, 0))
1459 /* Insert the nodes in DT test type order, which is roughly
1460 how expensive/important the test is. Given that the tests
1461 are also ordered within the list, examining the first is
1463 if ((int) add->tests->type < (int) old->tests->type)
1464 insert_before = old;
1467 if (insert_before == NULL)
1470 add->prev = oldh->last;
1471 oldh->last->next = add;
1476 if ((add->prev = insert_before->prev) != NULL)
1477 add->prev->next = add;
1480 add->next = insert_before;
1481 insert_before->prev = add;
1488 /* Walk the tree looking for sub-nodes that perform common tests.
1489 Factor out the common test into a new node. This enables us
1490 (depending on the test type) to emit switch statements later. */
1494 struct decision_head *head;
1496 struct decision *first, *next;
1498 for (first = head->first; first && first->next; first = next)
1500 enum decision_type type;
1501 struct decision *new, *old_last;
1503 type = first->tests->type;
1506 /* Want at least two compatible sequential nodes. */
1507 if (next->tests->type != type)
1510 /* Don't want all node types, just those we can turn into
1511 switch statements. */
1514 && type != DT_veclen
1515 && type != DT_elt_zero_int
1516 && type != DT_elt_one_int
1517 && type != DT_elt_zero_wide_safe)
1520 /* If we'd been performing more than one test, create a new node
1521 below our first test. */
1522 if (first->tests->next != NULL)
1524 new = new_decision (first->position, &first->success);
1525 new->tests = first->tests->next;
1526 first->tests->next = NULL;
1529 /* Crop the node tree off after our first test. */
1531 old_last = head->last;
1534 /* For each compatible test, adjust to perform only one test in
1535 the top level node, then merge the node back into the tree. */
1538 struct decision_head h;
1540 if (next->tests->next != NULL)
1542 new = new_decision (next->position, &next->success);
1543 new->tests = next->tests->next;
1544 next->tests->next = NULL;
1549 h.first = h.last = new;
1551 merge_trees (head, &h);
1553 while (next && next->tests->type == type);
1555 /* After we run out of compatible tests, graft the remaining nodes
1556 back onto the tree. */
1559 next->prev = head->last;
1560 head->last->next = next;
1561 head->last = old_last;
1566 for (first = head->first; first; first = first->next)
1567 factor_tests (&first->success);
1570 /* After factoring, try to simplify the tests on any one node.
1571 Tests that are useful for switch statements are recognizable
1572 by having only a single test on a node -- we'll be manipulating
1573 nodes with multiple tests:
1575 If we have mode tests or code tests that are redundant with
1576 predicates, remove them. */
1579 simplify_tests (head)
1580 struct decision_head *head;
1582 struct decision *tree;
1584 for (tree = head->first; tree; tree = tree->next)
1586 struct decision_test *a, *b;
1593 /* Find a predicate node. */
1594 while (b && b->type != DT_pred)
1598 /* Due to how these tests are constructed, we don't even need
1599 to check that the mode and code are compatible -- they were
1600 generated from the predicate in the first place. */
1601 while (a->type == DT_mode || a->type == DT_code)
1608 for (tree = head->first; tree; tree = tree->next)
1609 simplify_tests (&tree->success);
1612 /* Count the number of subnodes of HEAD. If the number is high enough,
1613 make the first node in HEAD start a separate subroutine in the C code
1614 that is generated. */
1617 break_out_subroutines (head, initial)
1618 struct decision_head *head;
1622 struct decision *sub;
1624 for (sub = head->first; sub; sub = sub->next)
1625 size += 1 + break_out_subroutines (&sub->success, 0);
1627 if (size > SUBROUTINE_THRESHOLD && ! initial)
1629 head->first->subroutine_number = ++next_subroutine_number;
1635 /* For each node p, find the next alternative that might be true
1639 find_afterward (head, real_afterward)
1640 struct decision_head *head;
1641 struct decision *real_afterward;
1643 struct decision *p, *q, *afterward;
1645 /* We can't propagate alternatives across subroutine boundaries.
1646 This is not incorrect, merely a minor optimization loss. */
1649 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1651 for ( ; p ; p = p->next)
1653 /* Find the next node that might be true if this one fails. */
1654 for (q = p->next; q ; q = q->next)
1655 if (maybe_both_true (p, q, 1))
1658 /* If we reached the end of the list without finding one,
1659 use the incoming afterward position. */
1668 for (p = head->first; p ; p = p->next)
1669 if (p->success.first)
1670 find_afterward (&p->success, p->afterward);
1672 /* When we are generating a subroutine, record the real afterward
1673 position in the first node where write_tree can find it, and we
1674 can do the right thing at the subroutine call site. */
1676 if (p->subroutine_number > 0)
1677 p->afterward = real_afterward;
1680 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1681 actions are necessary to move to NEWPOS. If we fail to move to the
1682 new state, branch to node AFTERWARD if nonzero, otherwise return.
1684 Failure to move to the new state can only occur if we are trying to
1685 match multiple insns and we try to step past the end of the stream. */
1688 change_state (oldpos, newpos, afterward, indent)
1691 struct decision *afterward;
1694 int odepth = strlen (oldpos);
1695 int ndepth = strlen (newpos);
1697 int old_has_insn, new_has_insn;
1699 /* Pop up as many levels as necessary. */
1700 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1703 /* Hunt for the last [A-Z] in both strings. */
1704 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1705 if (ISUPPER (oldpos[old_has_insn]))
1707 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1708 if (ISUPPER (newpos[new_has_insn]))
1711 /* Go down to desired level. */
1712 while (depth < ndepth)
1714 /* It's a different insn from the first one. */
1715 if (ISUPPER (newpos[depth]))
1717 /* We can only fail if we're moving down the tree. */
1718 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1720 printf ("%stem = peep2_next_insn (%d);\n",
1721 indent, newpos[depth] - 'A');
1725 printf ("%stem = peep2_next_insn (%d);\n",
1726 indent, newpos[depth] - 'A');
1727 printf ("%sif (tem == NULL_RTX)\n", indent);
1729 printf ("%s goto L%d;\n", indent, afterward->number);
1731 printf ("%s goto ret0;\n", indent);
1733 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1735 else if (ISLOWER (newpos[depth]))
1736 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1737 indent, depth + 1, depth, newpos[depth] - 'a');
1739 printf ("%sx%d = XEXP (x%d, %c);\n",
1740 indent, depth + 1, depth, newpos[depth]);
1745 /* Print the enumerator constant for CODE -- the upcase version of
1753 for (p = GET_RTX_NAME (code); *p; p++)
1754 putchar (TOUPPER (*p));
1757 /* Emit code to cross an afterward link -- change state and branch. */
1760 write_afterward (start, afterward, indent)
1761 struct decision *start;
1762 struct decision *afterward;
1765 if (!afterward || start->subroutine_number > 0)
1766 printf("%sgoto ret0;\n", indent);
1769 change_state (start->position, afterward->position, NULL, indent);
1770 printf ("%sgoto L%d;\n", indent, afterward->number);
1774 /* Emit a switch statement, if possible, for an initial sequence of
1775 nodes at START. Return the first node yet untested. */
1777 static struct decision *
1778 write_switch (start, depth)
1779 struct decision *start;
1782 struct decision *p = start;
1783 enum decision_type type = p->tests->type;
1784 struct decision *needs_label = NULL;
1786 /* If we have two or more nodes in sequence that test the same one
1787 thing, we may be able to use a switch statement. */
1791 || p->next->tests->type != type
1792 || p->next->tests->next
1793 || nodes_identical_1 (p->tests, p->next->tests))
1796 /* DT_code is special in that we can do interesting things with
1797 known predicates at the same time. */
1798 if (type == DT_code)
1800 char codemap[NUM_RTX_CODE];
1801 struct decision *ret;
1804 memset (codemap, 0, sizeof(codemap));
1806 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1807 code = p->tests->u.code;
1810 if (p != start && p->need_label && needs_label == NULL)
1815 printf (":\n goto L%d;\n", p->success.first->number);
1816 p->success.first->need_label = 1;
1823 && p->tests->type == DT_code
1824 && ! codemap[code = p->tests->u.code]);
1826 /* If P is testing a predicate that we know about and we haven't
1827 seen any of the codes that are valid for the predicate, we can
1828 write a series of "case" statement, one for each possible code.
1829 Since we are already in a switch, these redundant tests are very
1830 cheap and will reduce the number of predicates called. */
1832 /* Note that while we write out cases for these predicates here,
1833 we don't actually write the test here, as it gets kinda messy.
1834 It is trivial to leave this to later by telling our caller that
1835 we only processed the CODE tests. */
1836 if (needs_label != NULL)
1841 while (p && p->tests->type == DT_pred
1842 && p->tests->u.pred.index >= 0)
1846 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1847 if (codemap[(int) *c] != 0)
1850 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1855 codemap[(int) *c] = 1;
1858 printf (" goto L%d;\n", p->number);
1864 /* Make the default case skip the predicates we managed to match. */
1866 printf (" default:\n");
1871 printf (" goto L%d;\n", p->number);
1875 write_afterward (start, start->afterward, " ");
1878 printf (" break;\n");
1883 else if (type == DT_mode
1884 || type == DT_veclen
1885 || type == DT_elt_zero_int
1886 || type == DT_elt_one_int
1887 || type == DT_elt_zero_wide_safe)
1889 const char *indent = "";
1891 /* We cast switch parameter to integer, so we must ensure that the value
1893 if (type == DT_elt_zero_wide_safe)
1896 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1898 printf ("%s switch (", indent);
1902 printf ("GET_MODE (x%d)", depth);
1905 printf ("XVECLEN (x%d, 0)", depth);
1907 case DT_elt_zero_int:
1908 printf ("XINT (x%d, 0)", depth);
1910 case DT_elt_one_int:
1911 printf ("XINT (x%d, 1)", depth);
1913 case DT_elt_zero_wide_safe:
1914 /* Convert result of XWINT to int for portability since some C
1915 compilers won't do it and some will. */
1916 printf ("(int) XWINT (x%d, 0)", depth);
1921 printf (")\n%s {\n", indent);
1925 /* Merge trees will not unify identical nodes if their
1926 sub-nodes are at different levels. Thus we must check
1927 for duplicate cases. */
1929 for (q = start; q != p; q = q->next)
1930 if (nodes_identical_1 (p->tests, q->tests))
1933 if (p != start && p->need_label && needs_label == NULL)
1936 printf ("%s case ", indent);
1940 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1943 printf ("%d", p->tests->u.veclen);
1945 case DT_elt_zero_int:
1946 case DT_elt_one_int:
1947 case DT_elt_zero_wide:
1948 case DT_elt_zero_wide_safe:
1949 printf (HOST_WIDE_INT_PRINT_DEC_C, p->tests->u.intval);
1954 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1955 p->success.first->need_label = 1;
1959 while (p && p->tests->type == type && !p->tests->next);
1962 printf ("%s default:\n%s break;\n%s }\n",
1963 indent, indent, indent);
1965 return needs_label != NULL ? needs_label : p;
1969 /* None of the other tests are ameanable. */
1974 /* Emit code for one test. */
1977 write_cond (p, depth, subroutine_type)
1978 struct decision_test *p;
1980 enum routine_type subroutine_type;
1985 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1989 printf ("GET_CODE (x%d) == ", depth);
1990 print_code (p->u.code);
1994 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1997 case DT_elt_zero_int:
1998 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
2001 case DT_elt_one_int:
2002 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
2005 case DT_elt_zero_wide:
2006 case DT_elt_zero_wide_safe:
2007 printf ("XWINT (x%d, 0) == ", depth);
2008 printf (HOST_WIDE_INT_PRINT_DEC_C, p->u.intval);
2012 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2016 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2020 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2021 GET_MODE_NAME (p->u.pred.mode));
2025 printf ("(%s)", p->u.c_test);
2028 case DT_accept_insn:
2029 switch (subroutine_type)
2032 if (p->u.insn.num_clobbers_to_add == 0)
2034 printf ("pnum_clobbers != NULL");
2047 /* Emit code for one action. The previous tests have succeeded;
2048 TEST is the last of the chain. In the normal case we simply
2049 perform a state change. For the `accept' tests we must do more work. */
2052 write_action (p, test, depth, uncond, success, subroutine_type)
2054 struct decision_test *test;
2056 struct decision *success;
2057 enum routine_type subroutine_type;
2064 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2066 fputs (" {\n", stdout);
2073 if (test->type == DT_accept_op)
2075 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2077 /* Only allow DT_accept_insn to follow. */
2081 if (test->type != DT_accept_insn)
2086 /* Sanity check that we're now at the end of the list of tests. */
2090 if (test->type == DT_accept_insn)
2092 switch (subroutine_type)
2095 if (test->u.insn.num_clobbers_to_add != 0)
2096 printf ("%s*pnum_clobbers = %d;\n",
2097 indent, test->u.insn.num_clobbers_to_add);
2098 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2102 printf ("%sreturn gen_split_%d (operands);\n",
2103 indent, test->u.insn.code_number);
2108 int match_len = 0, i;
2110 for (i = strlen (p->position) - 1; i >= 0; --i)
2111 if (ISUPPER (p->position[i]))
2113 match_len = p->position[i] - 'A';
2116 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2117 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2118 indent, test->u.insn.code_number);
2119 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2129 printf("%sgoto L%d;\n", indent, success->number);
2130 success->need_label = 1;
2134 fputs (" }\n", stdout);
2137 /* Return 1 if the test is always true and has no fallthru path. Return -1
2138 if the test does have a fallthru path, but requires that the condition be
2139 terminated. Otherwise return 0 for a normal test. */
2140 /* ??? is_unconditional is a stupid name for a tri-state function. */
2143 is_unconditional (t, subroutine_type)
2144 struct decision_test *t;
2145 enum routine_type subroutine_type;
2147 if (t->type == DT_accept_op)
2150 if (t->type == DT_accept_insn)
2152 switch (subroutine_type)
2155 return (t->u.insn.num_clobbers_to_add == 0);
2168 /* Emit code for one node -- the conditional and the accompanying action.
2169 Return true if there is no fallthru path. */
2172 write_node (p, depth, subroutine_type)
2175 enum routine_type subroutine_type;
2177 struct decision_test *test, *last_test;
2180 last_test = test = p->tests;
2181 uncond = is_unconditional (test, subroutine_type);
2185 write_cond (test, depth, subroutine_type);
2187 while ((test = test->next) != NULL)
2192 uncond2 = is_unconditional (test, subroutine_type);
2197 write_cond (test, depth, subroutine_type);
2203 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2208 /* Emit code for all of the sibling nodes of HEAD. */
2211 write_tree_1 (head, depth, subroutine_type)
2212 struct decision_head *head;
2214 enum routine_type subroutine_type;
2216 struct decision *p, *next;
2219 for (p = head->first; p ; p = next)
2221 /* The label for the first element was printed in write_tree. */
2222 if (p != head->first && p->need_label)
2223 OUTPUT_LABEL (" ", p->number);
2225 /* Attempt to write a switch statement for a whole sequence. */
2226 next = write_switch (p, depth);
2231 /* Failed -- fall back and write one node. */
2232 uncond = write_node (p, depth, subroutine_type);
2237 /* Finished with this chain. Close a fallthru path by branching
2238 to the afterward node. */
2240 write_afterward (head->last, head->last->afterward, " ");
2243 /* Write out the decision tree starting at HEAD. PREVPOS is the
2244 position at the node that branched to this node. */
2247 write_tree (head, prevpos, type, initial)
2248 struct decision_head *head;
2249 const char *prevpos;
2250 enum routine_type type;
2253 struct decision *p = head->first;
2257 OUTPUT_LABEL (" ", p->number);
2259 if (! initial && p->subroutine_number > 0)
2261 static const char * const name_prefix[] = {
2262 "recog", "split", "peephole2"
2265 static const char * const call_suffix[] = {
2266 ", pnum_clobbers", "", ", _pmatch_len"
2269 /* This node has been broken out into a separate subroutine.
2270 Call it, test the result, and branch accordingly. */
2274 printf (" tem = %s_%d (x0, insn%s);\n",
2275 name_prefix[type], p->subroutine_number, call_suffix[type]);
2276 if (IS_SPLIT (type))
2277 printf (" if (tem != 0)\n return tem;\n");
2279 printf (" if (tem >= 0)\n return tem;\n");
2281 change_state (p->position, p->afterward->position, NULL, " ");
2282 printf (" goto L%d;\n", p->afterward->number);
2286 printf (" return %s_%d (x0, insn%s);\n",
2287 name_prefix[type], p->subroutine_number, call_suffix[type]);
2292 int depth = strlen (p->position);
2294 change_state (prevpos, p->position, head->last->afterward, " ");
2295 write_tree_1 (head, depth, type);
2297 for (p = head->first; p; p = p->next)
2298 if (p->success.first)
2299 write_tree (&p->success, p->position, type, 0);
2303 /* Write out a subroutine of type TYPE to do comparisons starting at
2307 write_subroutine (head, type)
2308 struct decision_head *head;
2309 enum routine_type type;
2311 int subfunction = head->first ? head->first->subroutine_number : 0;
2316 s_or_e = subfunction ? "static " : "";
2319 sprintf (extension, "_%d", subfunction);
2320 else if (type == RECOG)
2321 extension[0] = '\0';
2323 strcpy (extension, "_insns");
2328 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2330 recog%s (x0, insn, pnum_clobbers)\n\
2331 rtx x0 ATTRIBUTE_UNUSED;\n\
2332 rtx insn ATTRIBUTE_UNUSED;\n\
2333 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2336 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2338 split%s (x0, insn)\n\
2339 rtx x0 ATTRIBUTE_UNUSED;\n\
2340 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2343 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2346 peephole2%s (x0, insn, _pmatch_len)\n\
2347 rtx x0 ATTRIBUTE_UNUSED;\n\
2348 rtx insn ATTRIBUTE_UNUSED;\n\
2349 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2353 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2354 for (i = 1; i <= max_depth; i++)
2355 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2357 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2360 printf (" recog_data.insn = NULL_RTX;\n");
2363 write_tree (head, "", type, 1);
2365 printf (" goto ret0;\n");
2367 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2370 /* In break_out_subroutines, we discovered the boundaries for the
2371 subroutines, but did not write them out. Do so now. */
2374 write_subroutines (head, type)
2375 struct decision_head *head;
2376 enum routine_type type;
2380 for (p = head->first; p ; p = p->next)
2381 if (p->success.first)
2382 write_subroutines (&p->success, type);
2384 if (head->first->subroutine_number > 0)
2385 write_subroutine (head, type);
2388 /* Begin the output file. */
2394 /* Generated automatically by the program `genrecog' from the target\n\
2395 machine description file. */\n\
2397 #include \"config.h\"\n\
2398 #include \"system.h\"\n\
2399 #include \"rtl.h\"\n\
2400 #include \"tm_p.h\"\n\
2401 #include \"function.h\"\n\
2402 #include \"insn-config.h\"\n\
2403 #include \"recog.h\"\n\
2404 #include \"real.h\"\n\
2405 #include \"output.h\"\n\
2406 #include \"flags.h\"\n\
2407 #include \"hard-reg-set.h\"\n\
2408 #include \"resource.h\"\n\
2409 #include \"toplev.h\"\n\
2410 #include \"reload.h\"\n\
2414 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2415 X0 is a valid instruction.\n\
2417 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2418 returns a nonnegative number which is the insn code number for the\n\
2419 pattern that matched. This is the same as the order in the machine\n\
2420 description of the entry that matched. This number can be used as an\n\
2421 index into `insn_data' and other tables.\n");
2423 The third argument to recog is an optional pointer to an int. If\n\
2424 present, recog will accept a pattern if it matches except for missing\n\
2425 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2426 the optional pointer will be set to the number of CLOBBERs that need\n\
2427 to be added (it should be initialized to zero by the caller). If it");
2429 is set nonzero, the caller should allocate a PARALLEL of the\n\
2430 appropriate size, copy the initial entries, and call add_clobbers\n\
2431 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2435 The function split_insns returns 0 if the rtl could not\n\
2436 be split or the split rtl as an INSN list if it can be.\n\
2438 The function peephole2_insns returns 0 if the rtl could not\n\
2439 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2440 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2445 /* Construct and return a sequence of decisions
2446 that will recognize INSN.
2448 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2450 static struct decision_head
2451 make_insn_sequence (insn, type)
2453 enum routine_type type;
2456 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2457 int truth = maybe_eval_c_test (c_test);
2458 struct decision *last;
2459 struct decision_test *test, **place;
2460 struct decision_head head;
2463 /* We should never see an insn whose C test is false at compile time. */
2467 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2469 c_test_pos[0] = '\0';
2470 if (type == PEEPHOLE2)
2474 /* peephole2 gets special treatment:
2475 - X always gets an outer parallel even if it's only one entry
2476 - we remove all traces of outer-level match_scratch and match_dup
2477 expressions here. */
2478 x = rtx_alloc (PARALLEL);
2479 PUT_MODE (x, VOIDmode);
2480 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2481 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2483 rtx tmp = XVECEXP (insn, 0, i);
2484 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2486 XVECEXP (x, 0, j) = tmp;
2492 c_test_pos[0] = 'A' + j - 1;
2493 c_test_pos[1] = '\0';
2495 else if (XVECLEN (insn, type == RECOG) == 1)
2496 x = XVECEXP (insn, type == RECOG, 0);
2499 x = rtx_alloc (PARALLEL);
2500 XVEC (x, 0) = XVEC (insn, type == RECOG);
2501 PUT_MODE (x, VOIDmode);
2504 validate_pattern (x, insn, NULL_RTX, 0);
2506 memset(&head, 0, sizeof(head));
2507 last = add_to_sequence (x, &head, "", type, 1);
2509 /* Find the end of the test chain on the last node. */
2510 for (test = last->tests; test->next; test = test->next)
2512 place = &test->next;
2514 /* Skip the C test if it's known to be true at compile time. */
2517 /* Need a new node if we have another test to add. */
2518 if (test->type == DT_accept_op)
2520 last = new_decision (c_test_pos, &last->success);
2521 place = &last->tests;
2523 test = new_decision_test (DT_c_test, &place);
2524 test->u.c_test = c_test;
2527 test = new_decision_test (DT_accept_insn, &place);
2528 test->u.insn.code_number = next_insn_code;
2529 test->u.insn.lineno = pattern_lineno;
2530 test->u.insn.num_clobbers_to_add = 0;
2535 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2536 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2537 If so, set up to recognize the pattern without these CLOBBERs. */
2539 if (GET_CODE (x) == PARALLEL)
2543 /* Find the last non-clobber in the parallel. */
2544 for (i = XVECLEN (x, 0); i > 0; i--)
2546 rtx y = XVECEXP (x, 0, i - 1);
2547 if (GET_CODE (y) != CLOBBER
2548 || (GET_CODE (XEXP (y, 0)) != REG
2549 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2553 if (i != XVECLEN (x, 0))
2556 struct decision_head clobber_head;
2558 /* Build a similar insn without the clobbers. */
2560 new = XVECEXP (x, 0, 0);
2565 new = rtx_alloc (PARALLEL);
2566 XVEC (new, 0) = rtvec_alloc (i);
2567 for (j = i - 1; j >= 0; j--)
2568 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2572 memset (&clobber_head, 0, sizeof(clobber_head));
2573 last = add_to_sequence (new, &clobber_head, "", type, 1);
2575 /* Find the end of the test chain on the last node. */
2576 for (test = last->tests; test->next; test = test->next)
2579 /* We definitely have a new test to add -- create a new
2581 place = &test->next;
2582 if (test->type == DT_accept_op)
2584 last = new_decision ("", &last->success);
2585 place = &last->tests;
2588 /* Skip the C test if it's known to be true at compile
2592 test = new_decision_test (DT_c_test, &place);
2593 test->u.c_test = c_test;
2596 test = new_decision_test (DT_accept_insn, &place);
2597 test->u.insn.code_number = next_insn_code;
2598 test->u.insn.lineno = pattern_lineno;
2599 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2601 merge_trees (&head, &clobber_head);
2607 /* Define the subroutine we will call below and emit in genemit. */
2608 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2612 /* Define the subroutine we will call below and emit in genemit. */
2613 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2622 process_tree (head, subroutine_type)
2623 struct decision_head *head;
2624 enum routine_type subroutine_type;
2626 if (head->first == NULL)
2628 /* We can elide peephole2_insns, but not recog or split_insns. */
2629 if (subroutine_type == PEEPHOLE2)
2634 factor_tests (head);
2636 next_subroutine_number = 0;
2637 break_out_subroutines (head, 1);
2638 find_afterward (head, NULL);
2640 /* We run this after find_afterward, because find_afterward needs
2641 the redundant DT_mode tests on predicates to determine whether
2642 two tests can both be true or not. */
2643 simplify_tests(head);
2645 write_subroutines (head, subroutine_type);
2648 write_subroutine (head, subroutine_type);
2651 extern int main PARAMS ((int, char **));
2659 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2661 progname = "genrecog";
2663 memset (&recog_tree, 0, sizeof recog_tree);
2664 memset (&split_tree, 0, sizeof split_tree);
2665 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2668 fatal ("no input file name");
2670 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2671 return (FATAL_EXIT_CODE);
2678 /* Read the machine description. */
2682 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2686 if (GET_CODE (desc) == DEFINE_INSN)
2688 h = make_insn_sequence (desc, RECOG);
2689 merge_trees (&recog_tree, &h);
2691 else if (GET_CODE (desc) == DEFINE_SPLIT)
2693 h = make_insn_sequence (desc, SPLIT);
2694 merge_trees (&split_tree, &h);
2696 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2698 h = make_insn_sequence (desc, PEEPHOLE2);
2699 merge_trees (&peephole2_tree, &h);
2706 return FATAL_EXIT_CODE;
2710 process_tree (&recog_tree, RECOG);
2711 process_tree (&split_tree, SPLIT);
2712 process_tree (&peephole2_tree, PEEPHOLE2);
2715 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2718 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2720 get_insn_name (code)
2723 if (code < insn_name_ptr_size)
2724 return insn_name_ptr[code];
2730 record_insn_name (code, name)
2734 static const char *last_real_name = "insn";
2735 static int last_real_code = 0;
2738 if (insn_name_ptr_size <= code)
2741 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2743 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2744 memset (insn_name_ptr + insn_name_ptr_size, 0,
2745 sizeof(char *) * (new_size - insn_name_ptr_size));
2746 insn_name_ptr_size = new_size;
2749 if (!name || name[0] == '\0')
2751 new = xmalloc (strlen (last_real_name) + 10);
2752 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2756 last_real_name = new = xstrdup (name);
2757 last_real_code = code;
2760 insn_name_ptr[code] = new;
2764 debug_decision_2 (test)
2765 struct decision_test *test;
2770 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2773 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2776 fprintf (stderr, "veclen=%d", test->u.veclen);
2778 case DT_elt_zero_int:
2779 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2781 case DT_elt_one_int:
2782 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2784 case DT_elt_zero_wide:
2785 fprintf (stderr, "elt0_w=");
2786 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2788 case DT_elt_zero_wide_safe:
2789 fprintf (stderr, "elt0_ws=");
2790 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2793 fprintf (stderr, "veclen>=%d", test->u.veclen);
2796 fprintf (stderr, "dup=%d", test->u.dup);
2799 fprintf (stderr, "pred=(%s,%s)",
2800 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2805 strncpy (sub, test->u.c_test, sizeof(sub));
2806 memcpy (sub+16, "...", 4);
2807 fprintf (stderr, "c_test=\"%s\"", sub);
2811 fprintf (stderr, "A_op=%d", test->u.opno);
2813 case DT_accept_insn:
2814 fprintf (stderr, "A_insn=(%d,%d)",
2815 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2824 debug_decision_1 (d, indent)
2829 struct decision_test *test;
2833 for (i = 0; i < indent; ++i)
2835 fputs ("(nil)\n", stderr);
2839 for (i = 0; i < indent; ++i)
2846 debug_decision_2 (test);
2847 while ((test = test->next) != NULL)
2849 fputs (" + ", stderr);
2850 debug_decision_2 (test);
2853 fprintf (stderr, "} %d n %d a %d\n", d->number,
2854 (d->next ? d->next->number : -1),
2855 (d->afterward ? d->afterward->number : -1));
2859 debug_decision_0 (d, indent, maxdepth)
2861 int indent, maxdepth;
2870 for (i = 0; i < indent; ++i)
2872 fputs ("(nil)\n", stderr);
2876 debug_decision_1 (d, indent);
2877 for (n = d->success.first; n ; n = n->next)
2878 debug_decision_0 (n, indent + 2, maxdepth - 1);
2885 debug_decision_0 (d, 0, 1000000);
2889 debug_decision_list (d)
2894 debug_decision_0 (d, 0, 0);