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. */
59 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
60 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
62 static struct obstack obstack;
63 struct obstack *rtl_obstack = &obstack;
65 #define obstack_chunk_alloc xmalloc
66 #define obstack_chunk_free free
68 /* Holds an array of names indexed by insn_code_number. */
69 static char **insn_name_ptr = 0;
70 static int insn_name_ptr_size = 0;
72 /* A listhead of decision trees. The alternatives to a node are kept
73 in a doublely-linked list so we can easily add nodes to the proper
74 place when merging. */
78 struct decision *first;
79 struct decision *last;
82 /* A single test. The two accept types aren't tests per-se, but
83 their equality (or lack thereof) does affect tree merging so
84 it is convenient to keep them here. */
88 /* A linked list through the tests attached to a node. */
89 struct decision_test *next;
91 /* These types are roughly in the order in which we'd like to test them. */
93 DT_mode, DT_code, DT_veclen,
94 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide,
95 DT_dup, DT_pred, DT_c_test,
96 DT_accept_op, DT_accept_insn
101 enum machine_mode mode; /* Machine mode of node. */
102 RTX_CODE code; /* Code to test. */
106 const char *name; /* Predicate to call. */
107 int index; /* Index into `preds' or -1. */
108 enum machine_mode mode; /* Machine mode for node. */
111 const char *c_test; /* Additional test to perform. */
112 int veclen; /* Length of vector. */
113 int dup; /* Number of operand to compare against. */
114 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
115 int opno; /* Operand number matched. */
118 int code_number; /* Insn number matched. */
119 int lineno; /* Line number of the insn. */
120 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
125 /* Data structure for decision tree for recognizing legitimate insns. */
129 struct decision_head success; /* Nodes to test on success. */
130 struct decision *next; /* Node to test on failure. */
131 struct decision *prev; /* Node whose failure tests us. */
132 struct decision *afterward; /* Node to test on success,
133 but failure of successor nodes. */
135 const char *position; /* String denoting position in pattern. */
137 struct decision_test *tests; /* The tests for this node. */
139 int number; /* Node number, used for labels */
140 int subroutine_number; /* Number of subroutine this node starts */
141 int need_label; /* Label needs to be output. */
144 #define SUBROUTINE_THRESHOLD 100
146 static int next_subroutine_number;
148 /* We can write three types of subroutines: One for insn recognition,
149 one to split insns, and one for peephole-type optimizations. This
150 defines which type is being written. */
153 RECOG, SPLIT, PEEPHOLE2
156 #define IS_SPLIT(X) ((X) != RECOG)
158 /* Next available node number for tree nodes. */
160 static int next_number;
162 /* Next number to use as an insn_code. */
164 static int next_insn_code;
166 /* Similar, but counts all expressions in the MD file; used for
169 static int next_index;
171 /* Record the highest depth we ever have so we know how many variables to
172 allocate in each subroutine we make. */
174 static int max_depth;
176 /* The line number of the start of the pattern currently being processed. */
177 static int pattern_lineno;
179 /* Count of errors. */
180 static int error_count;
182 /* This table contains a list of the rtl codes that can possibly match a
183 predicate defined in recog.c. The function `maybe_both_true' uses it to
184 deduce that there are no expressions that can be matches by certain pairs
185 of tree nodes. Also, if a predicate can match only one code, we can
186 hardwire that code into the node testing the predicate. */
188 static struct pred_table
191 RTX_CODE codes[NUM_RTX_CODE];
193 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
194 LABEL_REF, SUBREG, REG, MEM}},
195 #ifdef PREDICATE_CODES
198 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
199 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
200 {"register_operand", {SUBREG, REG}},
201 {"pmode_register_operand", {SUBREG, REG}},
202 {"scratch_operand", {SCRATCH, REG}},
203 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
205 {"const_int_operand", {CONST_INT}},
206 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
207 {"nonimmediate_operand", {SUBREG, REG, MEM}},
208 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
209 LABEL_REF, SUBREG, REG}},
210 {"push_operand", {MEM}},
211 {"pop_operand", {MEM}},
212 {"memory_operand", {SUBREG, MEM}},
213 {"indirect_operand", {SUBREG, MEM}},
214 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}},
215 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
216 LABEL_REF, SUBREG, REG, MEM}}
219 #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
221 static const char * special_mode_pred_table[] = {
222 #ifdef SPECIAL_MODE_PREDICATES
223 SPECIAL_MODE_PREDICATES
225 "pmode_register_operand"
228 #define NUM_SPECIAL_MODE_PREDS \
229 (sizeof (special_mode_pred_table) / sizeof (special_mode_pred_table[0]))
231 static void message_with_line
232 PARAMS ((int, const char *, ...)) ATTRIBUTE_PRINTF_2;
234 static struct decision *new_decision
235 PARAMS ((const char *, struct decision_head *));
236 static struct decision_test *new_decision_test
237 PARAMS ((enum decision_type, struct decision_test ***));
238 static rtx find_operand
240 static void validate_pattern
241 PARAMS ((rtx, rtx, rtx));
242 static struct decision *add_to_sequence
243 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
245 static int maybe_both_true_2
246 PARAMS ((struct decision_test *, struct decision_test *));
247 static int maybe_both_true_1
248 PARAMS ((struct decision_test *, struct decision_test *));
249 static int maybe_both_true
250 PARAMS ((struct decision *, struct decision *, int));
252 static int nodes_identical_1
253 PARAMS ((struct decision_test *, struct decision_test *));
254 static int nodes_identical
255 PARAMS ((struct decision *, struct decision *));
256 static void merge_accept_insn
257 PARAMS ((struct decision *, struct decision *));
258 static void merge_trees
259 PARAMS ((struct decision_head *, struct decision_head *));
261 static void factor_tests
262 PARAMS ((struct decision_head *));
263 static void simplify_tests
264 PARAMS ((struct decision_head *));
265 static int break_out_subroutines
266 PARAMS ((struct decision_head *, int));
267 static void find_afterward
268 PARAMS ((struct decision_head *, struct decision *));
270 static void change_state
271 PARAMS ((const char *, const char *, struct decision *, const char *));
272 static void print_code
273 PARAMS ((enum rtx_code));
274 static void write_afterward
275 PARAMS ((struct decision *, struct decision *, const char *));
276 static struct decision *write_switch
277 PARAMS ((struct decision *, int));
278 static void write_cond
279 PARAMS ((struct decision_test *, int, enum routine_type));
280 static void write_action
281 PARAMS ((struct decision_test *, int, int, struct decision *,
283 static int is_unconditional
284 PARAMS ((struct decision_test *, enum routine_type));
285 static int write_node
286 PARAMS ((struct decision *, int, enum routine_type));
287 static void write_tree_1
288 PARAMS ((struct decision_head *, int, enum routine_type));
289 static void write_tree
290 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
291 static void write_subroutine
292 PARAMS ((struct decision_head *, enum routine_type));
293 static void write_subroutines
294 PARAMS ((struct decision_head *, enum routine_type));
295 static void write_header
298 static struct decision_head make_insn_sequence
299 PARAMS ((rtx, enum routine_type));
300 static void process_tree
301 PARAMS ((struct decision_head *, enum routine_type));
303 static void record_insn_name
304 PARAMS ((int, const char *));
306 static void debug_decision_0
307 PARAMS ((struct decision *, int, int));
308 static void debug_decision_1
309 PARAMS ((struct decision *, int));
310 static void debug_decision_2
311 PARAMS ((struct decision_test *));
312 extern void debug_decision
313 PARAMS ((struct decision *));
314 extern void debug_decision_list
315 PARAMS ((struct decision *));
318 message_with_line VPARAMS ((int lineno, const char *msg, ...))
320 #ifndef ANSI_PROTOTYPES
328 #ifndef ANSI_PROTOTYPES
329 lineno = va_arg (ap, int);
330 msg = va_arg (ap, const char *);
333 fprintf (stderr, "%s:%d: ", read_rtx_filename, lineno);
334 vfprintf (stderr, msg, ap);
335 fputc ('\n', stderr);
340 /* Create a new node in sequence after LAST. */
342 static struct decision *
343 new_decision (position, last)
344 const char *position;
345 struct decision_head *last;
347 register struct decision *new
348 = (struct decision *) xmalloc (sizeof (struct decision));
350 memset (new, 0, sizeof (*new));
351 new->success = *last;
352 new->position = xstrdup (position);
353 new->number = next_number++;
355 last->first = last->last = new;
359 /* Create a new test and link it in at PLACE. */
361 static struct decision_test *
362 new_decision_test (type, pplace)
363 enum decision_type type;
364 struct decision_test ***pplace;
366 struct decision_test **place = *pplace;
367 struct decision_test *test;
369 test = (struct decision_test *) xmalloc (sizeof (*test));
380 /* Search for and return operand N. */
383 find_operand (pattern, n)
392 code = GET_CODE (pattern);
393 if ((code == MATCH_SCRATCH
394 || code == MATCH_INSN
395 || code == MATCH_OPERAND
396 || code == MATCH_OPERATOR
397 || code == MATCH_PARALLEL)
398 && XINT (pattern, 0) == n)
401 fmt = GET_RTX_FORMAT (code);
402 len = GET_RTX_LENGTH (code);
403 for (i = 0; i < len; i++)
408 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
413 for (j = 0; j < XVECLEN (pattern, i); j++)
414 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
418 case 'i': case 'w': case '0': case 's':
429 /* Check for various errors in patterns. SET is nonnull for a destination,
430 and is the complete set pattern. */
433 validate_pattern (pattern, insn, set)
443 code = GET_CODE (pattern);
453 const char *pred_name = XSTR (pattern, 1);
454 int allows_non_lvalue = 1, allows_non_const = 1;
455 int special_mode_pred = 0;
458 if (GET_CODE (insn) == DEFINE_INSN)
459 c_test = XSTR (insn, 2);
461 c_test = XSTR (insn, 1);
463 if (pred_name[0] != 0)
465 for (i = 0; i < NUM_KNOWN_PREDS; i++)
466 if (! strcmp (preds[i].name, pred_name))
469 if (i < NUM_KNOWN_PREDS)
473 allows_non_lvalue = allows_non_const = 0;
474 for (j = 0; preds[i].codes[j] != 0; j++)
476 RTX_CODE c = preds[i].codes[j];
483 && c != CONSTANT_P_RTX)
484 allows_non_const = 1;
491 && c != STRICT_LOW_PART)
492 allows_non_lvalue = 1;
497 #ifdef PREDICATE_CODES
498 /* If the port has a list of the predicates it uses but
500 message_with_line (pattern_lineno,
501 "warning: `%s' not in PREDICATE_CODES",
506 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
507 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
509 special_mode_pred = 1;
514 /* A MATCH_OPERAND that is a SET should have an output reload. */
516 && code == MATCH_OPERAND
517 && XSTR (pattern, 2)[0] != '\0'
518 && XSTR (pattern, 2)[0] != '='
519 && XSTR (pattern, 2)[0] != '+')
521 message_with_line (pattern_lineno,
522 "operand %d missing output reload",
527 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
528 while not likely to occur at runtime, results in less efficient
529 code from insn-recog.c. */
531 && pred_name[0] != '\0'
532 && allows_non_lvalue)
534 message_with_line (pattern_lineno,
535 "warning: destination operand %d allows non-lvalue",
539 /* A modeless MATCH_OPERAND can be handy when we can
540 check for multiple modes in the c_test. In most other cases,
541 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
542 and PEEP2 can FAIL within the output pattern. Exclude
543 address_operand, since its mode is related to the mode of
544 the memory not the operand. Exclude the SET_DEST of a call
545 instruction, as that is a common idiom. */
547 if (GET_MODE (pattern) == VOIDmode
548 && code == MATCH_OPERAND
549 && GET_CODE (insn) == DEFINE_INSN
551 && ! special_mode_pred
552 && pred_name[0] != '\0'
553 && strcmp (pred_name, "address_operand") != 0
554 && strstr (c_test, "operands") == NULL
556 && GET_CODE (set) == SET
557 && GET_CODE (SET_SRC (set)) == CALL))
559 message_with_line (pattern_lineno,
560 "warning: operand %d missing mode?",
568 enum machine_mode dmode, smode;
571 dest = SET_DEST (pattern);
572 src = SET_SRC (pattern);
574 /* Find the referant for a DUP. */
576 if (GET_CODE (dest) == MATCH_DUP
577 || GET_CODE (dest) == MATCH_OP_DUP
578 || GET_CODE (dest) == MATCH_PAR_DUP)
579 dest = find_operand (insn, XINT (dest, 0));
581 if (GET_CODE (src) == MATCH_DUP
582 || GET_CODE (src) == MATCH_OP_DUP
583 || GET_CODE (src) == MATCH_PAR_DUP)
584 src = find_operand (insn, XINT (src, 0));
586 /* STRICT_LOW_PART is a wrapper. Its argument is the real
587 destination, and it's mode should match the source. */
588 if (GET_CODE (dest) == STRICT_LOW_PART)
589 dest = XEXP (dest, 0);
591 dmode = GET_MODE (dest);
592 smode = GET_MODE (src);
594 /* The mode of an ADDRESS_OPERAND is the mode of the memory
595 reference, not the mode of the address. */
596 if (GET_CODE (src) == MATCH_OPERAND
597 && ! strcmp (XSTR (src, 1), "address_operand"))
600 /* The operands of a SET must have the same mode unless one
602 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
604 message_with_line (pattern_lineno,
605 "mode mismatch in set: %smode vs %smode",
606 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
610 /* If only one of the operands is VOIDmode, and PC or CC0 is
611 not involved, it's probably a mistake. */
612 else if (dmode != smode
613 && GET_CODE (dest) != PC
614 && GET_CODE (dest) != CC0
615 && GET_CODE (src) != PC
616 && GET_CODE (src) != CC0
617 && GET_CODE (src) != CONST_INT)
620 which = (dmode == VOIDmode ? "destination" : "source");
621 message_with_line (pattern_lineno,
622 "warning: %s missing a mode?", which);
625 if (dest != SET_DEST (pattern))
626 validate_pattern (dest, insn, pattern);
627 validate_pattern (SET_DEST (pattern), insn, pattern);
628 validate_pattern (SET_SRC (pattern), insn, NULL_RTX);
633 validate_pattern (SET_DEST (pattern), insn, pattern);
637 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
639 message_with_line (pattern_lineno,
640 "operand to label_ref %smode not VOIDmode",
641 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
650 fmt = GET_RTX_FORMAT (code);
651 len = GET_RTX_LENGTH (code);
652 for (i = 0; i < len; i++)
657 validate_pattern (XEXP (pattern, i), insn, NULL_RTX);
661 for (j = 0; j < XVECLEN (pattern, i); j++)
662 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX);
665 case 'i': case 'w': case '0': case 's':
674 /* Create a chain of nodes to verify that an rtl expression matches
677 LAST is a pointer to the listhead in the previous node in the chain (or
678 in the calling function, for the first node).
680 POSITION is the string representing the current position in the insn.
682 INSN_TYPE is the type of insn for which we are emitting code.
684 A pointer to the final node in the chain is returned. */
686 static struct decision *
687 add_to_sequence (pattern, last, position, insn_type, top)
689 struct decision_head *last;
690 const char *position;
691 enum routine_type insn_type;
695 struct decision *this, *sub;
696 struct decision_test *test;
697 struct decision_test **place;
700 register const char *fmt;
701 int depth = strlen (position);
703 enum machine_mode mode;
705 if (depth > max_depth)
708 subpos = (char *) alloca (depth + 2);
709 strcpy (subpos, position);
710 subpos[depth + 1] = 0;
712 sub = this = new_decision (position, last);
713 place = &this->tests;
716 mode = GET_MODE (pattern);
717 code = GET_CODE (pattern);
722 /* Toplevel peephole pattern. */
723 if (insn_type == PEEPHOLE2 && top)
725 /* We don't need the node we just created -- unlink it. */
726 last->first = last->last = NULL;
728 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
730 /* Which insn we're looking at is represented by A-Z. We don't
731 ever use 'A', however; it is always implied. */
733 subpos[depth] = (i > 0 ? 'A' + i : 0);
734 sub = add_to_sequence (XVECEXP (pattern, 0, i),
735 last, subpos, insn_type, 0);
736 last = &sub->success;
741 /* Else nothing special. */
750 const char *pred_name;
751 RTX_CODE was_code = code;
752 int allows_const_int = 1;
754 if (code == MATCH_SCRATCH)
756 pred_name = "scratch_operand";
761 pred_name = XSTR (pattern, 1);
762 if (code == MATCH_PARALLEL)
768 /* We know exactly what const_int_operand matches -- any CONST_INT. */
769 if (strcmp ("const_int_operand", pred_name) == 0)
774 else if (pred_name[0] != 0)
776 test = new_decision_test (DT_pred, &place);
777 test->u.pred.name = pred_name;
778 test->u.pred.mode = mode;
780 /* See if we know about this predicate and save its number. If
781 we do, and it only accepts one code, note that fact. The
782 predicate `const_int_operand' only tests for a CONST_INT, so
783 if we do so we can avoid calling it at all.
785 Finally, if we know that the predicate does not allow
786 CONST_INT, we know that the only way the predicate can match
787 is if the modes match (here we use the kludge of relying on
788 the fact that "address_operand" accepts CONST_INT; otherwise,
789 it would have to be a special case), so we can test the mode
790 (but we need not). This fact should considerably simplify the
793 for (i = 0; i < NUM_KNOWN_PREDS; i++)
794 if (! strcmp (preds[i].name, pred_name))
797 if (i < NUM_KNOWN_PREDS)
801 test->u.pred.index = i;
803 if (preds[i].codes[1] == 0 && code == UNKNOWN)
804 code = preds[i].codes[0];
806 allows_const_int = 0;
807 for (j = 0; preds[i].codes[j] != 0; j++)
808 if (preds[i].codes[j] == CONST_INT)
810 allows_const_int = 1;
815 test->u.pred.index = -1;
818 /* Can't enforce a mode if we allow const_int. */
819 if (allows_const_int)
822 /* Accept the operand, ie. record it in `operands'. */
823 test = new_decision_test (DT_accept_op, &place);
824 test->u.opno = XINT (pattern, 0);
826 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
828 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
829 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
831 subpos[depth] = i + base;
832 sub = add_to_sequence (XVECEXP (pattern, 2, i),
833 &sub->success, subpos, insn_type, 0);
842 test = new_decision_test (DT_dup, &place);
843 test->u.dup = XINT (pattern, 0);
845 test = new_decision_test (DT_accept_op, &place);
846 test->u.opno = XINT (pattern, 0);
848 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
850 subpos[depth] = i + '0';
851 sub = add_to_sequence (XVECEXP (pattern, 1, i),
852 &sub->success, subpos, insn_type, 0);
860 test = new_decision_test (DT_dup, &place);
861 test->u.dup = XINT (pattern, 0);
865 pattern = XEXP (pattern, 0);
872 fmt = GET_RTX_FORMAT (code);
873 len = GET_RTX_LENGTH (code);
875 /* Do tests against the current node first. */
876 for (i = 0; i < (size_t) len; i++)
882 test = new_decision_test (DT_elt_zero_int, &place);
883 test->u.intval = XINT (pattern, i);
887 test = new_decision_test (DT_elt_one_int, &place);
888 test->u.intval = XINT (pattern, i);
893 else if (fmt[i] == 'w')
898 test = new_decision_test (DT_elt_zero_wide, &place);
899 test->u.intval = XWINT (pattern, i);
901 else if (fmt[i] == 'E')
906 test = new_decision_test (DT_veclen, &place);
907 test->u.veclen = XVECLEN (pattern, i);
911 /* Now test our sub-patterns. */
912 for (i = 0; i < (size_t) len; i++)
917 subpos[depth] = '0' + i;
918 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
919 subpos, insn_type, 0);
925 for (j = 0; j < XVECLEN (pattern, i); j++)
927 subpos[depth] = 'a' + j;
928 sub = add_to_sequence (XVECEXP (pattern, i, j),
929 &sub->success, subpos, insn_type, 0);
946 /* Insert nodes testing mode and code, if they're still relevant,
947 before any of the nodes we may have added above. */
950 place = &this->tests;
951 test = new_decision_test (DT_code, &place);
955 if (mode != VOIDmode)
957 place = &this->tests;
958 test = new_decision_test (DT_mode, &place);
962 /* If we didn't insert any tests or accept nodes, hork. */
963 if (this->tests == NULL)
969 /* A subroutine of maybe_both_true; examines only one test.
970 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
973 maybe_both_true_2 (d1, d2)
974 struct decision_test *d1, *d2;
976 if (d1->type == d2->type)
981 return d1->u.mode == d2->u.mode;
984 return d1->u.code == d2->u.code;
987 return d1->u.veclen == d2->u.veclen;
989 case DT_elt_zero_int:
991 case DT_elt_zero_wide:
992 return d1->u.intval == d2->u.intval;
999 /* If either has a predicate that we know something about, set
1000 things up so that D1 is the one that always has a known
1001 predicate. Then see if they have any codes in common. */
1003 if (d1->type == DT_pred || d2->type == DT_pred)
1005 if (d2->type == DT_pred)
1007 struct decision_test *tmp;
1008 tmp = d1, d1 = d2, d2 = tmp;
1011 /* If D2 tests a mode, see if it matches D1. */
1012 if (d1->u.pred.mode != VOIDmode)
1014 if (d2->type == DT_mode)
1016 if (d1->u.pred.mode != d2->u.mode
1017 /* The mode of an address_operand predicate is the
1018 mode of the memory, not the operand. It can only
1019 be used for testing the predicate, so we must
1021 && strcmp (d1->u.pred.name, "address_operand") != 0)
1024 /* Don't check two predicate modes here, because if both predicates
1025 accept CONST_INT, then both can still be true even if the modes
1026 are different. If they don't accept CONST_INT, there will be a
1027 separate DT_mode that will make maybe_both_true_1 return 0. */
1030 if (d1->u.pred.index >= 0)
1032 /* If D2 tests a code, see if it is in the list of valid
1033 codes for D1's predicate. */
1034 if (d2->type == DT_code)
1036 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1039 if (*c == d2->u.code)
1047 /* Otherwise see if the predicates have any codes in common. */
1048 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1050 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1053 while (*c1 != 0 && !common)
1055 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1056 while (*c2 != 0 && !common)
1058 common = (*c1 == *c2);
1073 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1074 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1077 maybe_both_true_1 (d1, d2)
1078 struct decision_test *d1, *d2;
1080 struct decision_test *t1, *t2;
1082 /* A match_operand with no predicate can match anything. Recognize
1083 this by the existance of a lone DT_accept_op test. */
1084 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1087 /* Eliminate pairs of tests while they can exactly match. */
1088 while (d1 && d2 && d1->type == d2->type)
1090 if (maybe_both_true_2 (d1, d2) == 0)
1092 d1 = d1->next, d2 = d2->next;
1095 /* After that, consider all pairs. */
1096 for (t1 = d1; t1 ; t1 = t1->next)
1097 for (t2 = d2; t2 ; t2 = t2->next)
1098 if (maybe_both_true_2 (t1, t2) == 0)
1104 /* Return 0 if we can prove that there is no RTL that can match both
1105 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1106 can match both or just that we couldn't prove there wasn't such an RTL).
1108 TOPLEVEL is non-zero if we are to only look at the top level and not
1109 recursively descend. */
1112 maybe_both_true (d1, d2, toplevel)
1113 struct decision *d1, *d2;
1116 struct decision *p1, *p2;
1119 /* Don't compare strings on the different positions in insn. Doing so
1120 is incorrect and results in false matches from constructs like
1122 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1123 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1125 [(set (match_operand:HI "register_operand" "r")
1126 (match_operand:HI "register_operand" "r"))]
1128 If we are presented with such, we are recursing through the remainder
1129 of a node's success nodes (from the loop at the end of this function).
1130 Skip forward until we come to a position that matches.
1132 Due to the way position strings are constructed, we know that iterating
1133 forward from the lexically lower position (e.g. "00") will run into
1134 the lexically higher position (e.g. "1") and not the other way around.
1135 This saves a bit of effort. */
1137 cmp = strcmp (d1->position, d2->position);
1143 /* If the d2->position was lexically lower, swap. */
1145 p1 = d1, d1 = d2, d2 = p1;
1147 if (d1->success.first == 0)
1149 for (p1 = d1->success.first; p1; p1 = p1->next)
1150 if (maybe_both_true (p1, d2, 0))
1156 /* Test the current level. */
1157 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1161 /* We can't prove that D1 and D2 cannot both be true. If we are only
1162 to check the top level, return 1. Otherwise, see if we can prove
1163 that all choices in both successors are mutually exclusive. If
1164 either does not have any successors, we can't prove they can't both
1167 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1170 for (p1 = d1->success.first; p1; p1 = p1->next)
1171 for (p2 = d2->success.first; p2; p2 = p2->next)
1172 if (maybe_both_true (p1, p2, 0))
1178 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1181 nodes_identical_1 (d1, d2)
1182 struct decision_test *d1, *d2;
1187 return d1->u.mode == d2->u.mode;
1190 return d1->u.code == d2->u.code;
1193 return (d1->u.pred.mode == d2->u.pred.mode
1194 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1197 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1200 return d1->u.veclen == d2->u.veclen;
1203 return d1->u.dup == d2->u.dup;
1205 case DT_elt_zero_int:
1206 case DT_elt_one_int:
1207 case DT_elt_zero_wide:
1208 return d1->u.intval == d2->u.intval;
1211 return d1->u.opno == d2->u.opno;
1213 case DT_accept_insn:
1214 /* Differences will be handled in merge_accept_insn. */
1222 /* True iff the two nodes are identical (on one level only). Due
1223 to the way these lists are constructed, we shouldn't have to
1224 consider different orderings on the tests. */
1227 nodes_identical (d1, d2)
1228 struct decision *d1, *d2;
1230 struct decision_test *t1, *t2;
1232 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1234 if (t1->type != t2->type)
1236 if (! nodes_identical_1 (t1, t2))
1240 /* For success, they should now both be null. */
1244 /* Check that their subnodes are at the same position, as any one set
1245 of sibling decisions must be at the same position. */
1246 if (d1->success.first
1247 && d2->success.first
1248 && strcmp (d1->success.first->position, d2->success.first->position))
1254 /* A subroutine of merge_trees; given two nodes that have been declared
1255 identical, cope with two insn accept states. If they differ in the
1256 number of clobbers, then the conflict was created by make_insn_sequence
1257 and we can drop the with-clobbers version on the floor. If both
1258 nodes have no additional clobbers, we have found an ambiguity in the
1259 source machine description. */
1262 merge_accept_insn (oldd, addd)
1263 struct decision *oldd, *addd;
1265 struct decision_test *old, *add;
1267 for (old = oldd->tests; old; old = old->next)
1268 if (old->type == DT_accept_insn)
1273 for (add = addd->tests; add; add = add->next)
1274 if (add->type == DT_accept_insn)
1279 /* If one node is for a normal insn and the second is for the base
1280 insn with clobbers stripped off, the second node should be ignored. */
1282 if (old->u.insn.num_clobbers_to_add == 0
1283 && add->u.insn.num_clobbers_to_add > 0)
1285 /* Nothing to do here. */
1287 else if (old->u.insn.num_clobbers_to_add > 0
1288 && add->u.insn.num_clobbers_to_add == 0)
1290 /* In this case, replace OLD with ADD. */
1291 old->u.insn = add->u.insn;
1295 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1296 get_insn_name (add->u.insn.code_number),
1297 get_insn_name (old->u.insn.code_number));
1298 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1299 get_insn_name (old->u.insn.code_number));
1304 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1307 merge_trees (oldh, addh)
1308 struct decision_head *oldh, *addh;
1310 struct decision *next, *add;
1312 if (addh->first == 0)
1314 if (oldh->first == 0)
1320 /* Trying to merge bits at different positions isn't possible. */
1321 if (strcmp (oldh->first->position, addh->first->position))
1324 for (add = addh->first; add ; add = next)
1326 struct decision *old, *insert_before = NULL;
1330 /* The semantics of pattern matching state that the tests are
1331 done in the order given in the MD file so that if an insn
1332 matches two patterns, the first one will be used. However,
1333 in practice, most, if not all, patterns are unambiguous so
1334 that their order is independent. In that case, we can merge
1335 identical tests and group all similar modes and codes together.
1337 Scan starting from the end of OLDH until we reach a point
1338 where we reach the head of the list or where we pass a
1339 pattern that could also be true if NEW is true. If we find
1340 an identical pattern, we can merge them. Also, record the
1341 last node that tests the same code and mode and the last one
1342 that tests just the same mode.
1344 If we have no match, place NEW after the closest match we found. */
1346 for (old = oldh->last; old; old = old->prev)
1348 if (nodes_identical (old, add))
1350 merge_accept_insn (old, add);
1351 merge_trees (&old->success, &add->success);
1355 if (maybe_both_true (old, add, 0))
1358 /* Insert the nodes in DT test type order, which is roughly
1359 how expensive/important the test is. Given that the tests
1360 are also ordered within the list, examining the first is
1362 if (add->tests->type < old->tests->type)
1363 insert_before = old;
1366 if (insert_before == NULL)
1369 add->prev = oldh->last;
1370 oldh->last->next = add;
1375 if ((add->prev = insert_before->prev) != NULL)
1376 add->prev->next = add;
1379 add->next = insert_before;
1380 insert_before->prev = add;
1387 /* Walk the tree looking for sub-nodes that perform common tests.
1388 Factor out the common test into a new node. This enables us
1389 (depending on the test type) to emit switch statements later. */
1393 struct decision_head *head;
1395 struct decision *first, *next;
1397 for (first = head->first; first && first->next; first = next)
1399 enum decision_type type;
1400 struct decision *new, *old_last;
1402 type = first->tests->type;
1405 /* Want at least two compatible sequential nodes. */
1406 if (next->tests->type != type)
1409 /* Don't want all node types, just those we can turn into
1410 switch statements. */
1413 && type != DT_veclen
1414 && type != DT_elt_zero_int
1415 && type != DT_elt_one_int
1416 && type != DT_elt_zero_wide)
1419 /* If we'd been performing more than one test, create a new node
1420 below our first test. */
1421 if (first->tests->next != NULL)
1423 new = new_decision (first->position, &first->success);
1424 new->tests = first->tests->next;
1425 first->tests->next = NULL;
1428 /* Crop the node tree off after our first test. */
1430 old_last = head->last;
1433 /* For each compatible test, adjust to perform only one test in
1434 the top level node, then merge the node back into the tree. */
1437 struct decision_head h;
1439 if (next->tests->next != NULL)
1441 new = new_decision (next->position, &next->success);
1442 new->tests = next->tests->next;
1443 next->tests->next = NULL;
1448 h.first = h.last = new;
1450 merge_trees (head, &h);
1452 while (next && next->tests->type == type);
1454 /* After we run out of compatible tests, graft the remaining nodes
1455 back onto the tree. */
1458 next->prev = head->last;
1459 head->last->next = next;
1460 head->last = old_last;
1465 for (first = head->first; first; first = first->next)
1466 factor_tests (&first->success);
1469 /* After factoring, try to simplify the tests on any one node.
1470 Tests that are useful for switch statements are recognizable
1471 by having only a single test on a node -- we'll be manipulating
1472 nodes with multiple tests:
1474 If we have mode tests or code tests that are redundant with
1475 predicates, remove them. */
1478 simplify_tests (head)
1479 struct decision_head *head;
1481 struct decision *tree;
1483 for (tree = head->first; tree; tree = tree->next)
1485 struct decision_test *a, *b;
1492 /* Find a predicate node. */
1493 while (b && b->type != DT_pred)
1497 /* Due to how these tests are constructed, we don't even need
1498 to check that the mode and code are compatible -- they were
1499 generated from the predicate in the first place. */
1500 while (a->type == DT_mode || a->type == DT_code)
1507 for (tree = head->first; tree; tree = tree->next)
1508 simplify_tests (&tree->success);
1511 /* Count the number of subnodes of HEAD. If the number is high enough,
1512 make the first node in HEAD start a separate subroutine in the C code
1513 that is generated. */
1516 break_out_subroutines (head, initial)
1517 struct decision_head *head;
1521 struct decision *sub;
1523 for (sub = head->first; sub; sub = sub->next)
1524 size += 1 + break_out_subroutines (&sub->success, 0);
1526 if (size > SUBROUTINE_THRESHOLD && ! initial)
1528 head->first->subroutine_number = ++next_subroutine_number;
1534 /* For each node p, find the next alternative that might be true
1538 find_afterward (head, real_afterward)
1539 struct decision_head *head;
1540 struct decision *real_afterward;
1542 struct decision *p, *q, *afterward;
1544 /* We can't propogate alternatives across subroutine boundaries.
1545 This is not incorrect, merely a minor optimization loss. */
1548 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1550 for ( ; p ; p = p->next)
1552 /* Find the next node that might be true if this one fails. */
1553 for (q = p->next; q ; q = q->next)
1554 if (maybe_both_true (p, q, 1))
1557 /* If we reached the end of the list without finding one,
1558 use the incoming afterward position. */
1567 for (p = head->first; p ; p = p->next)
1568 if (p->success.first)
1569 find_afterward (&p->success, p->afterward);
1571 /* When we are generating a subroutine, record the real afterward
1572 position in the first node where write_tree can find it, and we
1573 can do the right thing at the subroutine call site. */
1575 if (p->subroutine_number > 0)
1576 p->afterward = real_afterward;
1579 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1580 actions are necessary to move to NEWPOS. If we fail to move to the
1581 new state, branch to node AFTERWARD if non-zero, otherwise return.
1583 Failure to move to the new state can only occur if we are trying to
1584 match multiple insns and we try to step past the end of the stream. */
1587 change_state (oldpos, newpos, afterward, indent)
1590 struct decision *afterward;
1593 int odepth = strlen (oldpos);
1594 int ndepth = strlen (newpos);
1596 int old_has_insn, new_has_insn;
1598 /* Pop up as many levels as necessary. */
1599 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1602 /* Hunt for the last [A-Z] in both strings. */
1603 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1604 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1606 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1607 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1610 /* Make sure to reset the last_insn pointer when popping back up. */
1611 if (old_has_insn >= 0 && new_has_insn < 0)
1612 printf ("%slast_insn = insn;\n", indent);
1614 /* Go down to desired level. */
1615 while (depth < ndepth)
1617 /* It's a different insn from the first one. */
1618 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1620 /* We can only fail if we're moving down the tree. */
1621 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1623 printf ("%slast_insn = recog_next_insn (insn, %d);\n",
1624 indent, newpos[depth] - 'A');
1628 printf ("%stem = recog_next_insn (insn, %d);\n",
1629 indent, newpos[depth] - 'A');
1630 printf ("%sif (tem == NULL_RTX)\n", indent);
1632 printf ("%s goto L%d;\n", indent, afterward->number);
1634 printf ("%s goto ret0;\n", indent);
1635 printf ("%slast_insn = tem;\n", indent);
1637 printf ("%sx%d = PATTERN (last_insn);\n", indent, depth + 1);
1639 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1640 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1641 indent, depth + 1, depth, newpos[depth] - 'a');
1643 printf ("%sx%d = XEXP (x%d, %c);\n",
1644 indent, depth + 1, depth, newpos[depth]);
1649 /* Print the enumerator constant for CODE -- the upcase version of
1656 register const char *p;
1657 for (p = GET_RTX_NAME (code); *p; p++)
1658 putchar (TOUPPER (*p));
1661 /* Emit code to cross an afterward link -- change state and branch. */
1664 write_afterward (start, afterward, indent)
1665 struct decision *start;
1666 struct decision *afterward;
1669 if (!afterward || start->subroutine_number > 0)
1670 printf("%sgoto ret0;\n", indent);
1673 change_state (start->position, afterward->position, NULL, indent);
1674 printf ("%sgoto L%d;\n", indent, afterward->number);
1678 /* Emit a switch statement, if possible, for an initial sequence of
1679 nodes at START. Return the first node yet untested. */
1681 static struct decision *
1682 write_switch (start, depth)
1683 struct decision *start;
1686 struct decision *p = start;
1687 enum decision_type type = p->tests->type;
1689 /* If we have two or more nodes in sequence that test the same one
1690 thing, we may be able to use a switch statement. */
1694 || p->next->tests->type != type
1695 || p->next->tests->next)
1698 /* DT_code is special in that we can do interesting things with
1699 known predicates at the same time. */
1700 if (type == DT_code)
1702 char codemap[NUM_RTX_CODE];
1703 struct decision *ret;
1706 memset (codemap, 0, sizeof(codemap));
1708 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1709 code = p->tests->u.code;
1714 printf (":\n goto L%d;\n", p->success.first->number);
1715 p->success.first->need_label = 1;
1722 && p->tests->type == DT_code
1723 && ! codemap[code = p->tests->u.code]);
1725 /* If P is testing a predicate that we know about and we haven't
1726 seen any of the codes that are valid for the predicate, we can
1727 write a series of "case" statement, one for each possible code.
1728 Since we are already in a switch, these redundant tests are very
1729 cheap and will reduce the number of predicates called. */
1731 /* Note that while we write out cases for these predicates here,
1732 we don't actually write the test here, as it gets kinda messy.
1733 It is trivial to leave this to later by telling our caller that
1734 we only processed the CODE tests. */
1737 while (p && p->tests->type == DT_pred
1738 && p->tests->u.pred.index >= 0)
1742 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1743 if (codemap[(int) *c] != 0)
1746 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1751 codemap[(int) *c] = 1;
1754 printf (" goto L%d;\n", p->number);
1760 /* Make the default case skip the predicates we managed to match. */
1762 printf (" default:\n");
1767 printf (" goto L%d;\n", p->number);
1771 write_afterward (start, start->afterward, " ");
1774 printf (" break;\n");
1779 else if (type == DT_mode
1780 || type == DT_veclen
1781 || type == DT_elt_zero_int
1782 || type == DT_elt_one_int
1783 || type == DT_elt_zero_wide)
1785 printf (" switch (");
1789 printf ("GET_MODE (x%d)", depth);
1792 printf ("XVECLEN (x%d, 0)", depth);
1794 case DT_elt_zero_int:
1795 printf ("XINT (x%d, 0)", depth);
1797 case DT_elt_one_int:
1798 printf ("XINT (x%d, 1)", depth);
1800 case DT_elt_zero_wide:
1801 /* Convert result of XWINT to int for portability since some C
1802 compilers won't do it and some will. */
1803 printf ("(int) XWINT (x%d, 0)", depth);
1816 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1819 printf ("%d", p->tests->u.veclen);
1821 case DT_elt_zero_int:
1822 case DT_elt_one_int:
1823 case DT_elt_zero_wide:
1824 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1829 printf (":\n goto L%d;\n", p->success.first->number);
1830 p->success.first->need_label = 1;
1834 while (p && p->tests->type == type && !p->tests->next);
1836 printf (" default:\n break;\n }\n");
1842 /* None of the other tests are ameanable. */
1847 /* Emit code for one test. */
1850 write_cond (p, depth, subroutine_type)
1851 struct decision_test *p;
1853 enum routine_type subroutine_type;
1858 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1862 printf ("GET_CODE (x%d) == ", depth);
1863 print_code (p->u.code);
1867 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1870 case DT_elt_zero_int:
1871 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1874 case DT_elt_one_int:
1875 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1878 case DT_elt_zero_wide:
1879 printf ("XWINT (x%d, 0) == ", depth);
1880 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1884 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1888 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1889 GET_MODE_NAME (p->u.pred.mode));
1893 printf ("(%s)", p->u.c_test);
1896 case DT_accept_insn:
1897 switch (subroutine_type)
1900 if (p->u.insn.num_clobbers_to_add == 0)
1902 printf ("pnum_clobbers != NULL");
1915 /* Emit code for one action. The previous tests have succeeded;
1916 TEST is the last of the chain. In the normal case we simply
1917 perform a state change. For the `accept' tests we must do more work. */
1920 write_action (test, depth, uncond, success, subroutine_type)
1921 struct decision_test *test;
1923 struct decision *success;
1924 enum routine_type subroutine_type;
1931 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1933 fputs (" {\n", stdout);
1940 if (test->type == DT_accept_op)
1942 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1944 /* Only allow DT_accept_insn to follow. */
1948 if (test->type != DT_accept_insn)
1953 /* Sanity check that we're now at the end of the list of tests. */
1957 if (test->type == DT_accept_insn)
1959 switch (subroutine_type)
1962 if (test->u.insn.num_clobbers_to_add != 0)
1963 printf ("%s*pnum_clobbers = %d;\n",
1964 indent, test->u.insn.num_clobbers_to_add);
1965 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
1969 printf ("%sreturn gen_split_%d (operands);\n",
1970 indent, test->u.insn.code_number);
1974 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1975 indent, test->u.insn.code_number);
1976 printf ("%sif (tem != 0)\n%s goto ret1;\n", indent, indent);
1985 printf("%sgoto L%d;\n", indent, success->number);
1986 success->need_label = 1;
1990 fputs (" }\n", stdout);
1993 /* Return 1 if the test is always true and has no fallthru path. Return -1
1994 if the test does have a fallthru path, but requires that the condition be
1995 terminated. Otherwise return 0 for a normal test. */
1996 /* ??? is_unconditional is a stupid name for a tri-state function. */
1999 is_unconditional (t, subroutine_type)
2000 struct decision_test *t;
2001 enum routine_type subroutine_type;
2003 if (t->type == DT_accept_op)
2006 if (t->type == DT_accept_insn)
2008 switch (subroutine_type)
2011 return (t->u.insn.num_clobbers_to_add == 0);
2024 /* Emit code for one node -- the conditional and the accompanying action.
2025 Return true if there is no fallthru path. */
2028 write_node (p, depth, subroutine_type)
2031 enum routine_type subroutine_type;
2033 struct decision_test *test, *last_test;
2036 last_test = test = p->tests;
2037 uncond = is_unconditional (test, subroutine_type);
2041 write_cond (test, depth, subroutine_type);
2043 while ((test = test->next) != NULL)
2048 uncond2 = is_unconditional (test, subroutine_type);
2053 write_cond (test, depth, subroutine_type);
2059 write_action (last_test, depth, uncond, p->success.first, subroutine_type);
2064 /* Emit code for all of the sibling nodes of HEAD. */
2067 write_tree_1 (head, depth, subroutine_type)
2068 struct decision_head *head;
2070 enum routine_type subroutine_type;
2072 struct decision *p, *next;
2075 for (p = head->first; p ; p = next)
2077 /* The label for the first element was printed in write_tree. */
2078 if (p != head->first && p->need_label)
2079 OUTPUT_LABEL (" ", p->number);
2081 /* Attempt to write a switch statement for a whole sequence. */
2082 next = write_switch (p, depth);
2087 /* Failed -- fall back and write one node. */
2088 uncond = write_node (p, depth, subroutine_type);
2093 /* Finished with this chain. Close a fallthru path by branching
2094 to the afterward node. */
2096 write_afterward (head->last, head->last->afterward, " ");
2099 /* Write out the decision tree starting at HEAD. PREVPOS is the
2100 position at the node that branched to this node. */
2103 write_tree (head, prevpos, type, initial)
2104 struct decision_head *head;
2105 const char *prevpos;
2106 enum routine_type type;
2109 register struct decision *p = head->first;
2113 OUTPUT_LABEL (" ", p->number);
2115 if (! initial && p->subroutine_number > 0)
2117 static const char * const name_prefix[] = {
2118 "recog", "split", "peephole2"
2121 static const char * const call_suffix[] = {
2122 ", pnum_clobbers", "", ", _plast_insn"
2125 /* This node has been broken out into a separate subroutine.
2126 Call it, test the result, and branch accordingly. */
2130 printf (" tem = %s_%d (x0, insn%s);\n",
2131 name_prefix[type], p->subroutine_number, call_suffix[type]);
2132 if (IS_SPLIT (type))
2133 printf (" if (tem != 0)\n return tem;\n");
2135 printf (" if (tem >= 0)\n return tem;\n");
2137 change_state (p->position, p->afterward->position, NULL, " ");
2138 printf (" goto L%d;\n", p->afterward->number);
2142 printf (" return %s_%d (x0, insn%s);\n",
2143 name_prefix[type], p->subroutine_number, call_suffix[type]);
2148 int depth = strlen (p->position);
2150 change_state (prevpos, p->position, head->last->afterward, " ");
2151 write_tree_1 (head, depth, type);
2153 for (p = head->first; p; p = p->next)
2154 if (p->success.first)
2155 write_tree (&p->success, p->position, type, 0);
2159 /* Write out a subroutine of type TYPE to do comparisons starting at
2163 write_subroutine (head, type)
2164 struct decision_head *head;
2165 enum routine_type type;
2167 int subfunction = head->first ? head->first->subroutine_number : 0;
2172 s_or_e = subfunction ? "static " : "";
2175 sprintf (extension, "_%d", subfunction);
2176 else if (type == RECOG)
2177 extension[0] = '\0';
2179 strcpy (extension, "_insns");
2184 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2186 recog%s (x0, insn, pnum_clobbers)\n\
2188 rtx insn ATTRIBUTE_UNUSED;\n\
2189 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2192 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2194 split%s (x0, insn)\n\
2196 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2199 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, rtx *));\n", s_or_e, extension);
2201 peephole2%s (x0, insn, _plast_insn)\n\
2203 rtx insn ATTRIBUTE_UNUSED;\n\
2204 rtx *_plast_insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2208 printf ("{\n register rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2209 for (i = 1; i <= max_depth; i++)
2210 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
2212 if (type == PEEPHOLE2)
2213 printf (" register rtx last_insn = insn;\n");
2214 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2217 write_tree (head, "", type, 1);
2219 printf (" goto ret0;\n");
2221 if (type == PEEPHOLE2)
2222 printf (" ret1:\n *_plast_insn = last_insn;\n return tem;\n");
2223 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2226 /* In break_out_subroutines, we discovered the boundaries for the
2227 subroutines, but did not write them out. Do so now. */
2230 write_subroutines (head, type)
2231 struct decision_head *head;
2232 enum routine_type type;
2236 for (p = head->first; p ; p = p->next)
2237 if (p->success.first)
2238 write_subroutines (&p->success, type);
2240 if (head->first->subroutine_number > 0)
2241 write_subroutine (head, type);
2244 /* Begin the output file. */
2250 /* Generated automatically by the program `genrecog' from the target\n\
2251 machine description file. */\n\
2253 #include \"config.h\"\n\
2254 #include \"system.h\"\n\
2255 #include \"rtl.h\"\n\
2256 #include \"tm_p.h\"\n\
2257 #include \"function.h\"\n\
2258 #include \"insn-config.h\"\n\
2259 #include \"recog.h\"\n\
2260 #include \"real.h\"\n\
2261 #include \"output.h\"\n\
2262 #include \"flags.h\"\n\
2263 #include \"hard-reg-set.h\"\n\
2264 #include \"resource.h\"\n\
2268 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2269 X0 is a valid instruction.\n\
2271 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2272 returns a nonnegative number which is the insn code number for the\n\
2273 pattern that matched. This is the same as the order in the machine\n\
2274 description of the entry that matched. This number can be used as an\n\
2275 index into `insn_data' and other tables.\n\
2277 The third argument to recog is an optional pointer to an int. If\n\
2278 present, recog will accept a pattern if it matches except for missing\n\
2279 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2280 the optional pointer will be set to the number of CLOBBERs that need\n\
2281 to be added (it should be initialized to zero by the caller). If it\n\
2282 is set nonzero, the caller should allocate a PARALLEL of the\n\
2283 appropriate size, copy the initial entries, and call add_clobbers\n\
2284 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2288 The function split_insns returns 0 if the rtl could not\n\
2289 be split or the split rtl in a SEQUENCE if it can be.\n\
2291 The function peephole2_insns returns 0 if the rtl could not\n\
2292 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2293 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2298 /* Construct and return a sequence of decisions
2299 that will recognize INSN.
2301 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2303 static struct decision_head
2304 make_insn_sequence (insn, type)
2306 enum routine_type type;
2309 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2310 struct decision *last;
2311 struct decision_test *test, **place;
2312 struct decision_head head;
2313 char *c_test_pos = "";
2315 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2317 if (type == PEEPHOLE2)
2321 /* peephole2 gets special treatment:
2322 - X always gets an outer parallel even if it's only one entry
2323 - we remove all traces of outer-level match_scratch and match_dup
2324 expressions here. */
2325 x = rtx_alloc (PARALLEL);
2326 PUT_MODE (x, VOIDmode);
2327 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2328 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2330 rtx tmp = XVECEXP (insn, 0, i);
2331 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2333 XVECEXP (x, 0, j) = tmp;
2339 c_test_pos = alloca (2);
2340 c_test_pos[0] = 'A' + j - 1;
2341 c_test_pos[1] = '\0';
2343 else if (XVECLEN (insn, type == RECOG) == 1)
2344 x = XVECEXP (insn, type == RECOG, 0);
2347 x = rtx_alloc (PARALLEL);
2348 XVEC (x, 0) = XVEC (insn, type == RECOG);
2349 PUT_MODE (x, VOIDmode);
2352 validate_pattern (x, insn, NULL_RTX);
2354 memset(&head, 0, sizeof(head));
2355 last = add_to_sequence (x, &head, "", type, 1);
2357 /* Find the end of the test chain on the last node. */
2358 for (test = last->tests; test->next; test = test->next)
2360 place = &test->next;
2364 /* Need a new node if we have another test to add. */
2365 if (test->type == DT_accept_op)
2367 last = new_decision (c_test_pos, &last->success);
2368 place = &last->tests;
2370 test = new_decision_test (DT_c_test, &place);
2371 test->u.c_test = c_test;
2374 test = new_decision_test (DT_accept_insn, &place);
2375 test->u.insn.code_number = next_insn_code;
2376 test->u.insn.lineno = pattern_lineno;
2377 test->u.insn.num_clobbers_to_add = 0;
2382 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2383 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2384 If so, set up to recognize the pattern without these CLOBBERs. */
2386 if (GET_CODE (x) == PARALLEL)
2390 /* Find the last non-clobber in the parallel. */
2391 for (i = XVECLEN (x, 0); i > 0; i--)
2393 rtx y = XVECEXP (x, 0, i - 1);
2394 if (GET_CODE (y) != CLOBBER
2395 || (GET_CODE (XEXP (y, 0)) != REG
2396 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2400 if (i != XVECLEN (x, 0))
2403 struct decision_head clobber_head;
2405 /* Build a similar insn without the clobbers. */
2407 new = XVECEXP (x, 0, 0);
2412 new = rtx_alloc (PARALLEL);
2413 XVEC (new, 0) = rtvec_alloc (i);
2414 for (j = i - 1; j >= 0; j--)
2415 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2419 memset (&clobber_head, 0, sizeof(clobber_head));
2420 last = add_to_sequence (new, &clobber_head, "", type, 1);
2422 /* Find the end of the test chain on the last node. */
2423 for (test = last->tests; test->next; test = test->next)
2426 /* We definitely have a new test to add -- create a new
2428 place = &test->next;
2429 if (test->type == DT_accept_op)
2431 last = new_decision ("", &last->success);
2432 place = &last->tests;
2437 test = new_decision_test (DT_c_test, &place);
2438 test->u.c_test = c_test;
2441 test = new_decision_test (DT_accept_insn, &place);
2442 test->u.insn.code_number = next_insn_code;
2443 test->u.insn.lineno = pattern_lineno;
2444 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2446 merge_trees (&head, &clobber_head);
2452 /* Define the subroutine we will call below and emit in genemit. */
2453 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2457 /* Define the subroutine we will call below and emit in genemit. */
2458 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2468 process_tree (head, subroutine_type)
2469 struct decision_head *head;
2470 enum routine_type subroutine_type;
2472 if (head->first == NULL)
2474 /* We can elide peephole2_insns, but not recog or split_insns. */
2475 if (subroutine_type == PEEPHOLE2)
2480 factor_tests (head);
2482 next_subroutine_number = 0;
2483 break_out_subroutines (head, 1);
2484 find_afterward (head, NULL);
2486 /* We run this after find_afterward, because find_afterward needs
2487 the redundant DT_mode tests on predicates to determine whether
2488 two tests can both be true or not. */
2489 simplify_tests(head);
2491 write_subroutines (head, subroutine_type);
2494 write_subroutine (head, subroutine_type);
2497 extern int main PARAMS ((int, char **));
2505 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2509 progname = "genrecog";
2510 obstack_init (rtl_obstack);
2512 memset (&recog_tree, 0, sizeof recog_tree);
2513 memset (&split_tree, 0, sizeof split_tree);
2514 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2517 fatal ("No input file name.");
2519 infile = fopen (argv[1], "r");
2523 return FATAL_EXIT_CODE;
2525 read_rtx_filename = argv[1];
2532 /* Read the machine description. */
2536 c = read_skip_spaces (infile);
2540 pattern_lineno = read_rtx_lineno;
2542 desc = read_rtx (infile);
2543 if (GET_CODE (desc) == DEFINE_INSN)
2545 h = make_insn_sequence (desc, RECOG);
2546 merge_trees (&recog_tree, &h);
2548 else if (GET_CODE (desc) == DEFINE_SPLIT)
2550 h = make_insn_sequence (desc, SPLIT);
2551 merge_trees (&split_tree, &h);
2553 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2555 h = make_insn_sequence (desc, PEEPHOLE2);
2556 merge_trees (&peephole2_tree, &h);
2559 if (GET_CODE (desc) == DEFINE_PEEPHOLE
2560 || GET_CODE (desc) == DEFINE_EXPAND)
2566 return FATAL_EXIT_CODE;
2570 process_tree (&recog_tree, RECOG);
2571 process_tree (&split_tree, SPLIT);
2572 process_tree (&peephole2_tree, PEEPHOLE2);
2575 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2578 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2580 get_insn_name (code)
2583 if (code < insn_name_ptr_size)
2584 return insn_name_ptr[code];
2590 record_insn_name (code, name)
2594 static const char *last_real_name = "insn";
2595 static int last_real_code = 0;
2598 if (insn_name_ptr_size <= code)
2601 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2603 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2604 memset (insn_name_ptr + insn_name_ptr_size, 0,
2605 sizeof(char *) * (new_size - insn_name_ptr_size));
2606 insn_name_ptr_size = new_size;
2609 if (!name || name[0] == '\0')
2611 new = xmalloc (strlen (last_real_name) + 10);
2612 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2616 last_real_name = new = xstrdup (name);
2617 last_real_code = code;
2620 insn_name_ptr[code] = new;
2627 register size_t len = strlen (input) + 1;
2628 register char *output = xmalloc (len);
2629 memcpy (output, input, len);
2634 xrealloc (old, size)
2640 ptr = (PTR) realloc (old, size);
2642 ptr = (PTR) malloc (size);
2644 fatal ("virtual memory exhausted");
2652 register PTR val = (PTR) malloc (size);
2655 fatal ("virtual memory exhausted");
2660 debug_decision_2 (test)
2661 struct decision_test *test;
2666 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2669 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2672 fprintf (stderr, "veclen=%d", test->u.veclen);
2674 case DT_elt_zero_int:
2675 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2677 case DT_elt_one_int:
2678 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2680 case DT_elt_zero_wide:
2681 fprintf (stderr, "elt0_w=");
2682 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2685 fprintf (stderr, "dup=%d", test->u.dup);
2688 fprintf (stderr, "pred=(%s,%s)",
2689 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2694 strncpy (sub, test->u.c_test, sizeof(sub));
2695 memcpy (sub+16, "...", 4);
2696 fprintf (stderr, "c_test=\"%s\"", sub);
2700 fprintf (stderr, "A_op=%d", test->u.opno);
2702 case DT_accept_insn:
2703 fprintf (stderr, "A_insn=(%d,%d)",
2704 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2713 debug_decision_1 (d, indent)
2718 struct decision_test *test;
2722 for (i = 0; i < indent; ++i)
2724 fputs ("(nil)\n", stderr);
2728 for (i = 0; i < indent; ++i)
2735 debug_decision_2 (test);
2736 while ((test = test->next) != NULL)
2738 fputs (" + ", stderr);
2739 debug_decision_2 (test);
2742 fprintf (stderr, "} %d n %d a %d\n", d->number,
2743 (d->next ? d->next->number : -1),
2744 (d->afterward ? d->afterward->number : -1));
2748 debug_decision_0 (d, indent, maxdepth)
2750 int indent, maxdepth;
2759 for (i = 0; i < indent; ++i)
2761 fputs ("(nil)\n", stderr);
2765 debug_decision_1 (d, indent);
2766 for (n = d->success.first; n ; n = n->next)
2767 debug_decision_0 (n, indent + 2, maxdepth - 1);
2774 debug_decision_0 (d, 0, 1000000);
2778 debug_decision_list (d)
2783 debug_decision_0 (d, 0, 0);