1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 88, 92-95, 97-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This program is used to produce insn-recog.c, which contains a
23 function called `recog' plus its subroutines. These functions
24 contain a decision tree that recognizes whether an rtx, the
25 argument given to recog, is a valid instruction.
27 recog returns -1 if the rtx is not valid. If the rtx is valid,
28 recog returns a nonnegative number which is the insn code number
29 for the pattern that matched. This is the same as the order in the
30 machine description of the entry that matched. This number can be
31 used as an index into various insn_* tables, such as insn_template,
32 insn_outfun, and insn_n_operands (found in insn-output.c).
34 The third argument to recog is an optional pointer to an int. If
35 present, recog will accept a pattern if it matches except for
36 missing CLOBBER expressions at the end. In that case, the value
37 pointed to by the optional pointer will be set to the number of
38 CLOBBERs that need to be added (it should be initialized to zero by
39 the caller). If it is set nonzero, the caller should allocate a
40 PARALLEL of the appropriate size, copy the initial entries, and
41 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
43 This program also generates the function `split_insns', which
44 returns 0 if the rtl could not be split, or it returns the split
47 This program also generates the function `peephole2_insns', which
48 returns 0 if the rtl could not be matched. If there was a match,
49 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
50 to the last recognized insn in the old sequence. */
58 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
59 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
61 static struct obstack obstack;
62 struct obstack *rtl_obstack = &obstack;
64 #define obstack_chunk_alloc xmalloc
65 #define obstack_chunk_free free
67 /* Holds an array of names indexed by insn_code_number. */
68 static char **insn_name_ptr = 0;
69 static int insn_name_ptr_size = 0;
71 /* A listhead of decision trees. The alternatives to a node are kept
72 in a doublely-linked list so we can easily add nodes to the proper
73 place when merging. */
77 struct decision *first;
78 struct decision *last;
81 /* A single test. The two accept types aren't tests per-se, but
82 their equality (or lack thereof) does affect tree merging so
83 it is convenient to keep them here. */
87 /* A linked list through the tests attached to a node. */
88 struct decision_test *next;
90 /* These types are roughly in the order in which we'd like to test them. */
92 DT_mode, DT_code, DT_veclen,
93 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide,
94 DT_dup, DT_pred, DT_c_test,
95 DT_accept_op, DT_accept_insn
100 enum machine_mode mode; /* Machine mode of node. */
101 RTX_CODE code; /* Code to test. */
105 const char *name; /* Predicate to call. */
106 int index; /* Index into `preds' or -1. */
107 enum machine_mode mode; /* Machine mode for node. */
110 const char *c_test; /* Additional test to perform. */
111 int veclen; /* Length of vector. */
112 int dup; /* Number of operand to compare against. */
113 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
114 int opno; /* Operand number matched. */
117 int code_number; /* Insn number matched. */
118 int lineno; /* Line number of the insn. */
119 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
124 /* Data structure for decision tree for recognizing legitimate insns. */
128 struct decision_head success; /* Nodes to test on success. */
129 struct decision *next; /* Node to test on failure. */
130 struct decision *prev; /* Node whose failure tests us. */
131 struct decision *afterward; /* Node to test on success,
132 but failure of successor nodes. */
134 const char *position; /* String denoting position in pattern. */
136 struct decision_test *tests; /* The tests for this node. */
138 int number; /* Node number, used for labels */
139 int subroutine_number; /* Number of subroutine this node starts */
140 int need_label; /* Label needs to be output. */
143 #define SUBROUTINE_THRESHOLD 100
145 static int next_subroutine_number;
147 /* We can write three types of subroutines: One for insn recognition,
148 one to split insns, and one for peephole-type optimizations. This
149 defines which type is being written. */
152 RECOG, SPLIT, PEEPHOLE2
155 #define IS_SPLIT(X) ((X) != RECOG)
157 /* Next available node number for tree nodes. */
159 static int next_number;
161 /* Next number to use as an insn_code. */
163 static int next_insn_code;
165 /* Similar, but counts all expressions in the MD file; used for
168 static int next_index;
170 /* Record the highest depth we ever have so we know how many variables to
171 allocate in each subroutine we make. */
173 static int max_depth;
175 /* The line number of the start of the pattern currently being processed. */
176 static int pattern_lineno;
178 /* Count of errors. */
179 static int error_count;
181 /* This table contains a list of the rtl codes that can possibly match a
182 predicate defined in recog.c. The function `maybe_both_true' uses it to
183 deduce that there are no expressions that can be matches by certain pairs
184 of tree nodes. Also, if a predicate can match only one code, we can
185 hardwire that code into the node testing the predicate. */
187 static struct pred_table
190 RTX_CODE codes[NUM_RTX_CODE];
192 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
193 LABEL_REF, SUBREG, REG, MEM}},
194 #ifdef PREDICATE_CODES
197 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
198 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
199 {"register_operand", {SUBREG, REG}},
200 {"scratch_operand", {SCRATCH, REG}},
201 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
203 {"const_int_operand", {CONST_INT}},
204 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
205 {"nonimmediate_operand", {SUBREG, REG, MEM}},
206 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
207 LABEL_REF, SUBREG, REG}},
208 {"push_operand", {MEM}},
209 {"pop_operand", {MEM}},
210 {"memory_operand", {SUBREG, MEM}},
211 {"indirect_operand", {SUBREG, MEM}},
212 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}},
213 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
214 LABEL_REF, SUBREG, REG, MEM}}
217 #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
219 static const char * special_mode_pred_table[] = {
220 #ifdef SPECIAL_MODE_PREDICATES
221 SPECIAL_MODE_PREDICATES
226 #define NUM_SPECIAL_MODE_PREDS \
227 (sizeof (special_mode_pred_table) / sizeof (const char *) - 1)
229 static struct decision *new_decision
230 PROTO((const char *, struct decision_head *));
231 static struct decision_test *new_decision_test
232 PROTO((enum decision_type, struct decision_test ***));
233 static rtx find_operand
235 static void validate_pattern
236 PROTO((rtx, rtx, int));
237 static struct decision *add_to_sequence
238 PROTO((rtx, struct decision_head *, const char *, enum routine_type, int));
240 static int maybe_both_true_2
241 PROTO((struct decision_test *, struct decision_test *));
242 static int maybe_both_true_1
243 PROTO((struct decision_test *, struct decision_test *));
244 static int maybe_both_true
245 PROTO((struct decision *, struct decision *, int));
247 static int nodes_identical_1
248 PROTO((struct decision_test *, struct decision_test *));
249 static int nodes_identical
250 PROTO((struct decision *, struct decision *));
251 static void merge_accept_insn
252 PROTO((struct decision *, struct decision *));
253 static void merge_trees
254 PROTO((struct decision_head *, struct decision_head *));
256 static void factor_tests
257 PROTO((struct decision_head *));
258 static void simplify_tests
259 PROTO((struct decision_head *));
260 static int break_out_subroutines
261 PROTO((struct decision_head *, int));
262 static void find_afterward
263 PROTO((struct decision_head *, struct decision *));
265 static void change_state
266 PROTO((const char *, const char *, struct decision *, const char *));
267 static void print_code
268 PROTO((enum rtx_code));
269 static void write_afterward
270 PROTO((struct decision *, struct decision *, const char *));
271 static struct decision *write_switch
272 PROTO((struct decision *, int));
273 static void write_cond
274 PROTO((struct decision_test *, int, enum routine_type));
275 static void write_action
276 PROTO((struct decision_test *, int, int, struct decision *,
278 static int is_unconditional
279 PROTO((struct decision_test *, enum routine_type));
280 static int write_node
281 PROTO((struct decision *, int, enum routine_type));
282 static void write_tree_1
283 PROTO((struct decision_head *, int, enum routine_type));
284 static void write_tree
285 PROTO((struct decision_head *, const char *, enum routine_type, int));
286 static void write_subroutine
287 PROTO((struct decision_head *, enum routine_type));
288 static void write_subroutines
289 PROTO((struct decision_head *, enum routine_type));
290 static void write_header
293 static struct decision_head make_insn_sequence
294 PROTO((rtx, enum routine_type));
295 static void process_tree
296 PROTO((struct decision_head *, enum routine_type));
298 static void record_insn_name
299 PROTO((int, const char *));
301 static void debug_decision_1
302 PROTO((struct decision *, int));
303 static void debug_decision_2
304 PROTO((struct decision_test *));
305 extern void debug_decision
306 PROTO((struct decision *));
309 message_with_line VPROTO ((int lineno, const char *msg, ...))
311 #ifndef ANSI_PROTOTYPES
319 #ifndef ANSI_PROTOTYPES
320 lineno = va_arg (ap, int);
321 msg = va_arg (ap, const char *);
324 fprintf (stderr, "%s:%d: ", read_rtx_filename, lineno);
325 vfprintf (stderr, msg, ap);
326 fputc ('\n', stderr);
331 /* Create a new node in sequence after LAST. */
333 static struct decision *
334 new_decision (position, last)
335 const char *position;
336 struct decision_head *last;
338 register struct decision *new
339 = (struct decision *) xmalloc (sizeof (struct decision));
341 memset (new, 0, sizeof (*new));
342 new->success = *last;
343 new->position = xstrdup (position);
344 new->number = next_number++;
346 last->first = last->last = new;
350 /* Create a new test and link it in at PLACE. */
352 static struct decision_test *
353 new_decision_test (type, pplace)
354 enum decision_type type;
355 struct decision_test ***pplace;
357 struct decision_test **place = *pplace;
358 struct decision_test *test;
360 test = (struct decision_test *) xmalloc (sizeof (*test));
371 /* Search for and return operand N. */
374 find_operand (pattern, n)
383 code = GET_CODE (pattern);
384 if ((code == MATCH_SCRATCH
385 || code == MATCH_INSN
386 || code == MATCH_OPERAND
387 || code == MATCH_OPERATOR
388 || code == MATCH_PARALLEL)
389 && XINT (pattern, 0) == n)
392 fmt = GET_RTX_FORMAT (code);
393 len = GET_RTX_LENGTH (code);
394 for (i = 0; i < len; i++)
399 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
404 for (j = 0; j < XVECLEN (pattern, i); j++)
405 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
409 case 'i': case 'w': case '0': case 's':
420 /* Check for various errors in patterns. */
423 validate_pattern (pattern, insn, set_dest)
433 code = GET_CODE (pattern);
443 const char *pred_name = XSTR (pattern, 1);
444 int allows_non_lvalue = 1, allows_non_const = 1;
445 int special_mode_pred = 0;
448 if (GET_CODE (insn) == DEFINE_INSN)
449 c_test = XSTR (insn, 2);
451 c_test = XSTR (insn, 1);
453 if (pred_name[0] != 0)
455 for (i = 0; i < NUM_KNOWN_PREDS; i++)
456 if (! strcmp (preds[i].name, pred_name))
459 if (i < NUM_KNOWN_PREDS)
463 allows_non_lvalue = allows_non_const = 0;
464 for (j = 0; preds[i].codes[j] != 0; j++)
466 RTX_CODE c = preds[i].codes[j];
473 && c != CONSTANT_P_RTX)
474 allows_non_const = 1;
481 && c != STRICT_LOW_PART)
482 allows_non_lvalue = 1;
487 #ifdef PREDICATE_CODES
488 /* If the port has a list of the predicates it uses but
490 message_with_line (pattern_lineno,
491 "warning: `%s' not in PREDICATE_CODES",
496 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
497 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
499 special_mode_pred = 1;
504 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
505 while not likely to occur at runtime, results in less efficient
506 code from insn-recog.c. */
508 && pred_name[0] != '\0'
509 && allows_non_lvalue)
511 message_with_line (pattern_lineno,
512 "warning: `%s' allows non-lvalue,",
514 message_with_line (pattern_lineno,
515 " and used as destination of a set");
518 /* A modeless MATCH_OPERAND can be handy when we can
519 check for multiple modes in the c_test. In most other cases,
520 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
521 and PEEP2 can FAIL within the output pattern. */
523 if (GET_MODE (pattern) == VOIDmode
524 && code == MATCH_OPERAND
525 && pred_name[0] != '\0'
527 && ! special_mode_pred
528 && strstr (c_test, "operands") == NULL
529 && GET_CODE (insn) == DEFINE_INSN)
531 message_with_line (pattern_lineno,
532 "warning: operand %d missing mode?",
536 /* A MATCH_OPERAND that is a SET should have an output reload. */
538 && code == MATCH_OPERAND
539 && XSTR (pattern, 2)[0] != '\0'
540 && XSTR (pattern, 2)[0] != '='
541 && XSTR (pattern, 2)[0] != '+')
543 message_with_line (pattern_lineno,
544 "operand %d missing output reload",
554 enum machine_mode dmode, smode;
557 dest = SET_DEST (pattern);
558 src = SET_SRC (pattern);
560 /* Find the referant for a DUP. */
562 if (GET_CODE (dest) == MATCH_DUP
563 || GET_CODE (dest) == MATCH_OP_DUP
564 || GET_CODE (dest) == MATCH_PAR_DUP)
565 dest = find_operand (insn, XINT (dest, 0));
567 if (GET_CODE (src) == MATCH_DUP
568 || GET_CODE (src) == MATCH_OP_DUP
569 || GET_CODE (src) == MATCH_PAR_DUP)
570 src = find_operand (insn, XINT (src, 0));
572 /* STRICT_LOW_PART is a wrapper. Its argument is the real
573 destination, and it's mode should match the source. */
574 if (GET_CODE (dest) == STRICT_LOW_PART)
575 dest = XEXP (dest, 0);
577 dmode = GET_MODE (dest);
578 smode = GET_MODE (src);
580 /* The mode of an ADDRESS_OPERAND is the mode of the memory
581 reference, not the mode of the address. */
582 if (GET_CODE (src) == MATCH_OPERAND
583 && ! strcmp (XSTR (src, 1), "address_operand"))
586 /* The operands of a SET must have the same mode unless one
588 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
590 message_with_line (pattern_lineno,
591 "mode mismatch in set: %smode vs %smode",
592 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
596 /* If only one of the operands is VOIDmode, and PC or CC0 is
597 not involved, it's probably a mistake. */
598 else if (dmode != smode
599 && GET_CODE (dest) != PC
600 && GET_CODE (dest) != CC0
601 && GET_CODE (src) != CONST_INT)
604 which = (dmode == VOIDmode ? "destination" : "source");
605 message_with_line (pattern_lineno,
606 "warning: %s missing a mode?", which);
609 if (dest != SET_DEST (pattern))
610 validate_pattern (dest, insn, 1);
611 validate_pattern (SET_DEST (pattern), insn, 1);
612 validate_pattern (SET_SRC (pattern), insn, 0);
617 validate_pattern (SET_DEST (pattern), insn, 1);
621 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
623 message_with_line (pattern_lineno,
624 "operand to label_ref %smode not VOIDmode",
625 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
634 fmt = GET_RTX_FORMAT (code);
635 len = GET_RTX_LENGTH (code);
636 for (i = 0; i < len; i++)
641 validate_pattern (XEXP (pattern, i), insn, 0);
645 for (j = 0; j < XVECLEN (pattern, i); j++)
646 validate_pattern (XVECEXP (pattern, i, j), insn, 0);
649 case 'i': case 'w': case '0': case 's':
658 /* Create a chain of nodes to verify that an rtl expression matches
661 LAST is a pointer to the listhead in the previous node in the chain (or
662 in the calling function, for the first node).
664 POSITION is the string representing the current position in the insn.
666 INSN_TYPE is the type of insn for which we are emitting code.
668 A pointer to the final node in the chain is returned. */
670 static struct decision *
671 add_to_sequence (pattern, last, position, insn_type, top)
673 struct decision_head *last;
674 const char *position;
675 enum routine_type insn_type;
679 struct decision *this, *sub;
680 struct decision_test *test;
681 struct decision_test **place;
684 register const char *fmt;
685 int depth = strlen (position);
687 enum machine_mode mode;
689 if (depth > max_depth)
692 subpos = (char *) alloca (depth + 2);
693 strcpy (subpos, position);
694 subpos[depth + 1] = 0;
696 sub = this = new_decision (position, last);
697 place = &this->tests;
700 mode = GET_MODE (pattern);
701 code = GET_CODE (pattern);
706 /* Toplevel peephole pattern. */
707 if (insn_type == PEEPHOLE2 && top)
709 /* We don't need the node we just created -- unlink it. */
710 last->first = last->last = NULL;
712 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
714 /* Which insn we're looking at is represented by A-Z. We don't
715 ever use 'A', however; it is always implied. */
717 subpos[depth] = (i > 0 ? 'A' + i : 0);
718 sub = add_to_sequence (XVECEXP (pattern, 0, i),
719 last, subpos, insn_type, 0);
720 last = &sub->success;
725 /* Else nothing special. */
734 const char *pred_name;
735 RTX_CODE was_code = code;
736 int allows_const_int = 1;
738 if (code == MATCH_SCRATCH)
740 pred_name = "scratch_operand";
745 pred_name = XSTR (pattern, 1);
746 if (code == MATCH_PARALLEL)
752 /* We know exactly what const_int_operand matches -- any CONST_INT. */
753 if (strcmp ("const_int_operand", pred_name) == 0)
758 else if (pred_name[0] != 0)
760 test = new_decision_test (DT_pred, &place);
761 test->u.pred.name = pred_name;
762 test->u.pred.mode = mode;
764 /* See if we know about this predicate and save its number. If
765 we do, and it only accepts one code, note that fact. The
766 predicate `const_int_operand' only tests for a CONST_INT, so
767 if we do so we can avoid calling it at all.
769 Finally, if we know that the predicate does not allow
770 CONST_INT, we know that the only way the predicate can match
771 is if the modes match (here we use the kludge of relying on
772 the fact that "address_operand" accepts CONST_INT; otherwise,
773 it would have to be a special case), so we can test the mode
774 (but we need not). This fact should considerably simplify the
777 for (i = 0; i < NUM_KNOWN_PREDS; i++)
778 if (! strcmp (preds[i].name, pred_name))
781 if (i < NUM_KNOWN_PREDS)
785 test->u.pred.index = i;
787 if (preds[i].codes[1] == 0 && code == UNKNOWN)
788 code = preds[i].codes[0];
790 allows_const_int = 0;
791 for (j = 0; preds[i].codes[j] != 0; j++)
792 if (preds[i].codes[j] == CONST_INT)
794 allows_const_int = 1;
799 test->u.pred.index = -1;
802 /* Can't enforce a mode if we allow const_int. */
803 if (allows_const_int)
806 /* Accept the operand, ie. record it in `operands'. */
807 test = new_decision_test (DT_accept_op, &place);
808 test->u.opno = XINT (pattern, 0);
810 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
812 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
813 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
815 subpos[depth] = i + base;
816 sub = add_to_sequence (XVECEXP (pattern, 2, i),
817 &sub->success, subpos, insn_type, 0);
826 test = new_decision_test (DT_dup, &place);
827 test->u.dup = XINT (pattern, 0);
829 test = new_decision_test (DT_accept_op, &place);
830 test->u.opno = XINT (pattern, 0);
832 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
834 subpos[depth] = i + '0';
835 sub = add_to_sequence (XVECEXP (pattern, 1, i),
836 &sub->success, subpos, insn_type, 0);
844 test = new_decision_test (DT_dup, &place);
845 test->u.dup = XINT (pattern, 0);
849 pattern = XEXP (pattern, 0);
856 fmt = GET_RTX_FORMAT (code);
857 len = GET_RTX_LENGTH (code);
859 /* Do tests against the current node first. */
860 for (i = 0; i < (size_t) len; i++)
866 test = new_decision_test (DT_elt_zero_int, &place);
867 test->u.intval = XINT (pattern, i);
871 test = new_decision_test (DT_elt_one_int, &place);
872 test->u.intval = XINT (pattern, i);
877 else if (fmt[i] == 'w')
882 test = new_decision_test (DT_elt_zero_wide, &place);
883 test->u.intval = XWINT (pattern, i);
885 else if (fmt[i] == 'E')
890 test = new_decision_test (DT_veclen, &place);
891 test->u.veclen = XVECLEN (pattern, i);
895 /* Now test our sub-patterns. */
896 for (i = 0; i < (size_t) len; i++)
901 subpos[depth] = '0' + i;
902 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
903 subpos, insn_type, 0);
909 for (j = 0; j < XVECLEN (pattern, i); j++)
911 subpos[depth] = 'a' + j;
912 sub = add_to_sequence (XVECEXP (pattern, i, j),
913 &sub->success, subpos, insn_type, 0);
930 /* Insert nodes testing mode and code, if they're still relevant,
931 before any of the nodes we may have added above. */
934 place = &this->tests;
935 test = new_decision_test (DT_code, &place);
939 if (mode != VOIDmode)
941 place = &this->tests;
942 test = new_decision_test (DT_mode, &place);
946 /* If we didn't insert any tests or accept nodes, hork. */
947 if (this->tests == NULL)
953 /* A subroutine of maybe_both_true; examines only one test.
954 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
957 maybe_both_true_2 (d1, d2)
958 struct decision_test *d1, *d2;
960 if (d1->type == d2->type)
965 return d1->u.mode == d2->u.mode;
968 return d1->u.code == d2->u.code;
971 return d1->u.veclen == d2->u.veclen;
973 case DT_elt_zero_int:
975 case DT_elt_zero_wide:
976 return d1->u.intval == d2->u.intval;
983 /* If either has a predicate that we know something about, set
984 things up so that D1 is the one that always has a known
985 predicate. Then see if they have any codes in common. */
987 if (d1->type == DT_pred || d2->type == DT_pred)
989 if (d2->type == DT_pred)
991 struct decision_test *tmp;
992 tmp = d1, d1 = d2, d2 = tmp;
995 /* If D2 tests a mode, see if it matches D1. */
996 if (d1->u.pred.mode != VOIDmode)
998 if (d2->type == DT_mode)
1000 if (d1->u.pred.mode != d2->u.mode)
1003 /* Don't check two predicate modes here, because if both predicates
1004 accept CONST_INT, then both can still be true even if the modes
1005 are different. If they don't accept CONST_INT, there will be a
1006 separate DT_mode that will make maybe_both_true_1 return 0. */
1009 if (d1->u.pred.index >= 0)
1011 /* If D2 tests a code, see if it is in the list of valid
1012 codes for D1's predicate. */
1013 if (d2->type == DT_code)
1015 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1018 if (*c == d2->u.code)
1026 /* Otherwise see if the predicates have any codes in common. */
1027 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1029 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1032 while (*c1 != 0 && !common)
1034 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1035 while (*c2 != 0 && !common)
1037 common = (*c1 == *c2);
1052 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1053 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1056 maybe_both_true_1 (d1, d2)
1057 struct decision_test *d1, *d2;
1059 struct decision_test *t1, *t2;
1061 /* A match_operand with no predicate can match anything. Recognize
1062 this by the existance of a lone DT_accept_op test. */
1063 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1066 /* Eliminate pairs of tests while they can exactly match. */
1067 while (d1 && d2 && d1->type == d2->type)
1069 if (maybe_both_true_2 (d1, d2) == 0)
1071 d1 = d1->next, d2 = d2->next;
1074 /* After that, consider all pairs. */
1075 for (t1 = d1; t1 ; t1 = t1->next)
1076 for (t2 = d2; t2 ; t2 = t2->next)
1077 if (maybe_both_true_2 (t1, t2) == 0)
1083 /* Return 0 if we can prove that there is no RTL that can match both
1084 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1085 can match both or just that we couldn't prove there wasn't such an RTL).
1087 TOPLEVEL is non-zero if we are to only look at the top level and not
1088 recursively descend. */
1091 maybe_both_true (d1, d2, toplevel)
1092 struct decision *d1, *d2;
1095 struct decision *p1, *p2;
1098 /* Don't compare strings on the different positions in insn. Doing so
1099 is incorrect and results in false matches from constructs like
1101 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1102 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1104 [(set (match_operand:HI "register_operand" "r")
1105 (match_operand:HI "register_operand" "r"))]
1107 If we are presented with such, we are recursing through the remainder
1108 of a node's success nodes (from the loop at the end of this function).
1109 Skip forward until we come to a position that matches.
1111 Due to the way position strings are constructed, we know that iterating
1112 forward from the lexically lower position (e.g. "00") will run into
1113 the lexically higher position (e.g. "1") and not the other way around.
1114 This saves a bit of effort. */
1116 cmp = strcmp (d1->position, d2->position);
1122 /* If the d2->position was lexically lower, swap. */
1124 p1 = d1, d1 = d2, d2 = p1;
1126 if (d1->success.first == 0)
1128 for (p1 = d1->success.first; p1; p1 = p1->next)
1129 if (maybe_both_true (p1, d2, 0))
1135 /* Test the current level. */
1136 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1140 /* We can't prove that D1 and D2 cannot both be true. If we are only
1141 to check the top level, return 1. Otherwise, see if we can prove
1142 that all choices in both successors are mutually exclusive. If
1143 either does not have any successors, we can't prove they can't both
1146 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1149 for (p1 = d1->success.first; p1; p1 = p1->next)
1150 for (p2 = d2->success.first; p2; p2 = p2->next)
1151 if (maybe_both_true (p1, p2, 0))
1157 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1160 nodes_identical_1 (d1, d2)
1161 struct decision_test *d1, *d2;
1166 return d1->u.mode == d2->u.mode;
1169 return d1->u.code == d2->u.code;
1172 return (d1->u.pred.mode == d2->u.pred.mode
1173 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1176 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1179 return d1->u.veclen == d2->u.veclen;
1182 return d1->u.dup == d2->u.dup;
1184 case DT_elt_zero_int:
1185 case DT_elt_one_int:
1186 case DT_elt_zero_wide:
1187 return d1->u.intval == d2->u.intval;
1190 return d1->u.opno == d2->u.opno;
1192 case DT_accept_insn:
1193 /* Differences will be handled in merge_accept_insn. */
1201 /* True iff the two nodes are identical (on one level only). Due
1202 to the way these lists are constructed, we shouldn't have to
1203 consider different orderings on the tests. */
1206 nodes_identical (d1, d2)
1207 struct decision *d1, *d2;
1209 struct decision_test *t1, *t2;
1211 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1213 if (t1->type != t2->type)
1215 if (! nodes_identical_1 (t1, t2))
1219 /* For success, they should now both be null. */
1223 /* A subroutine of merge_trees; given two nodes that have been declared
1224 identical, cope with two insn accept states. If they differ in the
1225 number of clobbers, then the conflict was created by make_insn_sequence
1226 and we can drop the with-clobbers version on the floor. If both
1227 nodes have no additional clobbers, we have found an ambiguity in the
1228 source machine description. */
1231 merge_accept_insn (oldd, addd)
1232 struct decision *oldd, *addd;
1234 struct decision_test *old, *add;
1236 for (old = oldd->tests; old; old = old->next)
1237 if (old->type == DT_accept_insn)
1242 for (add = addd->tests; add; add = add->next)
1243 if (add->type == DT_accept_insn)
1248 /* If one node is for a normal insn and the second is for the base
1249 insn with clobbers stripped off, the second node should be ignored. */
1251 if (old->u.insn.num_clobbers_to_add == 0
1252 && add->u.insn.num_clobbers_to_add > 0)
1254 /* Nothing to do here. */
1256 else if (old->u.insn.num_clobbers_to_add > 0
1257 && add->u.insn.num_clobbers_to_add == 0)
1259 /* In this case, replace OLD with ADD. */
1260 old->u.insn = add->u.insn;
1264 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1265 get_insn_name (add->u.insn.code_number),
1266 get_insn_name (old->u.insn.code_number));
1267 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1268 get_insn_name (old->u.insn.code_number));
1273 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1276 merge_trees (oldh, addh)
1277 struct decision_head *oldh, *addh;
1279 struct decision *next, *add;
1281 if (addh->first == 0)
1283 if (oldh->first == 0)
1289 /* Trying to merge bits at different positions isn't possible. */
1290 if (strcmp (oldh->first->position, addh->first->position))
1293 for (add = addh->first; add ; add = next)
1295 struct decision *old, *insert_before = NULL;
1299 /* The semantics of pattern matching state that the tests are
1300 done in the order given in the MD file so that if an insn
1301 matches two patterns, the first one will be used. However,
1302 in practice, most, if not all, patterns are unambiguous so
1303 that their order is independent. In that case, we can merge
1304 identical tests and group all similar modes and codes together.
1306 Scan starting from the end of OLDH until we reach a point
1307 where we reach the head of the list or where we pass a
1308 pattern that could also be true if NEW is true. If we find
1309 an identical pattern, we can merge them. Also, record the
1310 last node that tests the same code and mode and the last one
1311 that tests just the same mode.
1313 If we have no match, place NEW after the closest match we found. */
1315 for (old = oldh->last; old; old = old->prev)
1317 if (nodes_identical (old, add))
1319 merge_accept_insn (old, add);
1320 merge_trees (&old->success, &add->success);
1324 if (maybe_both_true (old, add, 0))
1327 /* Insert the nodes in DT test type order, which is roughly
1328 how expensive/important the test is. Given that the tests
1329 are also ordered within the list, examining the first is
1331 if (add->tests->type < old->tests->type)
1332 insert_before = old;
1335 if (insert_before == NULL)
1338 add->prev = oldh->last;
1339 oldh->last->next = add;
1344 if ((add->prev = insert_before->prev) != NULL)
1345 add->prev->next = add;
1348 add->next = insert_before;
1349 insert_before->prev = add;
1356 /* Walk the tree looking for sub-nodes that perform common tests.
1357 Factor out the common test into a new node. This enables us
1358 (depending on the test type) to emit switch statements later. */
1362 struct decision_head *head;
1364 struct decision *first, *next;
1366 for (first = head->first; first && first->next; first = next)
1368 enum decision_type type;
1369 struct decision *new, *old_last;
1371 type = first->tests->type;
1374 /* Want at least two compatible sequential nodes. */
1375 if (next->tests->type != type)
1378 /* Don't want all node types, just those we can turn into
1379 switch statements. */
1382 && type != DT_veclen
1383 && type != DT_elt_zero_int
1384 && type != DT_elt_one_int
1385 && type != DT_elt_zero_wide)
1388 /* If we'd been performing more than one test, create a new node
1389 below our first test. */
1390 if (first->tests->next != NULL)
1392 new = new_decision (first->position, &first->success);
1393 new->tests = first->tests->next;
1394 first->tests->next = NULL;
1397 /* Crop the node tree off after our first test. */
1399 old_last = head->last;
1402 /* For each compatible test, adjust to perform only one test in
1403 the top level node, then merge the node back into the tree. */
1406 struct decision_head h;
1408 if (next->tests->next != NULL)
1410 new = new_decision (next->position, &next->success);
1411 new->tests = next->tests->next;
1412 next->tests->next = NULL;
1417 h.first = h.last = new;
1419 merge_trees (head, &h);
1421 while (next && next->tests->type == type);
1423 /* After we run out of compatible tests, graft the remaining nodes
1424 back onto the tree. */
1427 next->prev = head->last;
1428 head->last->next = next;
1429 head->last = old_last;
1434 for (first = head->first; first; first = first->next)
1435 factor_tests (&first->success);
1438 /* After factoring, try to simplify the tests on any one node.
1439 Tests that are useful for switch statements are recognizable
1440 by having only a single test on a node -- we'll be manipulating
1441 nodes with multiple tests:
1443 If we have mode tests or code tests that are redundant with
1444 predicates, remove them. */
1447 simplify_tests (head)
1448 struct decision_head *head;
1450 struct decision *tree;
1452 for (tree = head->first; tree; tree = tree->next)
1454 struct decision_test *a, *b;
1461 /* Find a predicate node. */
1462 while (b && b->type != DT_pred)
1466 /* Due to how these tests are constructed, we don't even need
1467 to check that the mode and code are compatible -- they were
1468 generated from the predicate in the first place. */
1469 while (a->type == DT_mode || a->type == DT_code)
1476 for (tree = head->first; tree; tree = tree->next)
1477 simplify_tests (&tree->success);
1480 /* Count the number of subnodes of HEAD. If the number is high enough,
1481 make the first node in HEAD start a separate subroutine in the C code
1482 that is generated. */
1485 break_out_subroutines (head, initial)
1486 struct decision_head *head;
1490 struct decision *sub;
1492 for (sub = head->first; sub; sub = sub->next)
1493 size += 1 + break_out_subroutines (&sub->success, 0);
1495 if (size > SUBROUTINE_THRESHOLD && ! initial)
1497 head->first->subroutine_number = ++next_subroutine_number;
1503 /* For each node p, find the next alternative that might be true
1507 find_afterward (head, real_afterward)
1508 struct decision_head *head;
1509 struct decision *real_afterward;
1511 struct decision *p, *q, *afterward;
1513 /* We can't propogate alternatives across subroutine boundaries.
1514 This is not incorrect, merely a minor optimization loss. */
1517 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1519 for ( ; p ; p = p->next)
1521 /* Find the next node that might be true if this one fails. */
1522 for (q = p->next; q ; q = q->next)
1523 if (maybe_both_true (p, q, 1))
1526 /* If we reached the end of the list without finding one,
1527 use the incoming afterward position. */
1536 for (p = head->first; p ; p = p->next)
1537 if (p->success.first)
1538 find_afterward (&p->success, p->afterward);
1540 /* When we are generating a subroutine, record the real afterward
1541 position in the first node where write_tree can find it, and we
1542 can do the right thing at the subroutine call site. */
1544 if (p->subroutine_number > 0)
1545 p->afterward = real_afterward;
1548 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1549 actions are necessary to move to NEWPOS. If we fail to move to the
1550 new state, branch to node AFTERWARD if non-zero, otherwise return.
1552 Failure to move to the new state can only occur if we are trying to
1553 match multiple insns and we try to step past the end of the stream. */
1556 change_state (oldpos, newpos, afterward, indent)
1559 struct decision *afterward;
1562 int odepth = strlen (oldpos);
1563 int ndepth = strlen (newpos);
1565 int old_has_insn, new_has_insn;
1567 /* Pop up as many levels as necessary. */
1568 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1571 /* Hunt for the last [A-Z] in both strings. */
1572 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1573 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1575 for (new_has_insn = odepth - 1; new_has_insn >= 0; --new_has_insn)
1576 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1579 /* Make sure to reset the _last_insn pointer when popping back up. */
1580 if (old_has_insn >= 0 && new_has_insn < 0)
1581 printf ("%s_last_insn = insn;\n", indent);
1583 /* Go down to desired level. */
1584 while (depth < ndepth)
1586 /* It's a different insn from the first one. */
1587 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1589 /* We can only fail if we're moving down the tree. */
1590 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1592 printf ("%s_last_insn = recog_next_insn (insn, %d);\n",
1593 indent, newpos[depth] - 'A');
1597 printf ("%stem = recog_next_insn (insn, %d);\n",
1598 indent, newpos[depth] - 'A');
1599 printf ("%sif (tem == NULL_RTX)\n", indent);
1601 printf ("%s goto L%d;\n", indent, afterward->number);
1603 printf ("%s goto ret0;\n", indent);
1604 printf ("%s_last_insn = tem;\n", indent);
1606 printf ("%sx%d = PATTERN (_last_insn);\n", indent, depth + 1);
1608 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1609 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1610 indent, depth + 1, depth, newpos[depth] - 'a');
1612 printf ("%sx%d = XEXP (x%d, %c);\n",
1613 indent, depth + 1, depth, newpos[depth]);
1618 /* Print the enumerator constant for CODE -- the upcase version of
1625 register const char *p;
1626 for (p = GET_RTX_NAME (code); *p; p++)
1627 putchar (TOUPPER (*p));
1630 /* Emit code to cross an afterward link -- change state and branch. */
1633 write_afterward (start, afterward, indent)
1634 struct decision *start;
1635 struct decision *afterward;
1638 if (!afterward || start->subroutine_number > 0)
1639 printf("%sgoto ret0;\n", indent);
1642 change_state (start->position, afterward->position, NULL, indent);
1643 printf ("%sgoto L%d;\n", indent, afterward->number);
1647 /* Emit a switch statement, if possible, for an initial sequence of
1648 nodes at START. Return the first node yet untested. */
1650 static struct decision *
1651 write_switch (start, depth)
1652 struct decision *start;
1655 struct decision *p = start;
1656 enum decision_type type = p->tests->type;
1658 /* If we have two or more nodes in sequence that test the same one
1659 thing, we may be able to use a switch statement. */
1663 || p->next->tests->type != type
1664 || p->next->tests->next)
1667 /* DT_code is special in that we can do interesting things with
1668 known predicates at the same time. */
1669 if (type == DT_code)
1671 char codemap[NUM_RTX_CODE];
1672 struct decision *ret;
1674 memset (codemap, 0, sizeof(codemap));
1676 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1679 RTX_CODE code = p->tests->u.code;
1682 printf (":\n goto L%d;\n", p->success.first->number);
1683 p->success.first->need_label = 1;
1688 while (p && p->tests->type == DT_code && !p->tests->next);
1690 /* If P is testing a predicate that we know about and we haven't
1691 seen any of the codes that are valid for the predicate, we can
1692 write a series of "case" statement, one for each possible code.
1693 Since we are already in a switch, these redundant tests are very
1694 cheap and will reduce the number of predicates called. */
1696 /* Note that while we write out cases for these predicates here,
1697 we don't actually write the test here, as it gets kinda messy.
1698 It is trivial to leave this to later by telling our caller that
1699 we only processed the CODE tests. */
1702 while (p && p->tests->type == DT_pred
1703 && p->tests->u.pred.index >= 0)
1707 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1708 if (codemap[(int) *c] != 0)
1711 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1716 codemap[(int) *c] = 1;
1719 printf (" goto L%d;\n", p->number);
1725 /* Make the default case skip the predicates we managed to match. */
1727 printf (" default:\n");
1732 printf (" goto L%d;\n", p->number);
1736 write_afterward (start, start->afterward, " ");
1739 printf (" break;\n");
1744 else if (type == DT_mode
1745 || type == DT_veclen
1746 || type == DT_elt_zero_int
1747 || type == DT_elt_one_int
1748 || type == DT_elt_zero_wide)
1752 printf (" switch (");
1756 str = "GET_MODE (x%d)";
1759 str = "XVECLEN (x%d, 0)";
1761 case DT_elt_zero_int:
1762 str = "XINT (x%d, 0)";
1764 case DT_elt_one_int:
1765 str = "XINT (x%d, 1)";
1767 case DT_elt_zero_wide:
1768 str = "XWINT (x%d, 0)";
1773 printf (str, depth);
1782 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1785 printf ("%d", p->tests->u.veclen);
1787 case DT_elt_zero_int:
1788 case DT_elt_one_int:
1789 case DT_elt_zero_wide:
1790 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1795 printf (":\n goto L%d;\n", p->success.first->number);
1796 p->success.first->need_label = 1;
1800 while (p && p->tests->type == type && !p->tests->next);
1802 printf (" default:\n break;\n }\n");
1808 /* None of the other tests are ameanable. */
1813 /* Emit code for one test. */
1816 write_cond (p, depth, subroutine_type)
1817 struct decision_test *p;
1819 enum routine_type subroutine_type;
1824 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1828 printf ("GET_CODE (x%d) == ", depth);
1829 print_code (p->u.code);
1833 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1836 case DT_elt_zero_int:
1837 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1840 case DT_elt_one_int:
1841 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1844 case DT_elt_zero_wide:
1845 printf ("XWINT (x%d, 0) == ", depth);
1846 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1850 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1854 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1855 GET_MODE_NAME (p->u.pred.mode));
1859 printf ("(%s)", p->u.c_test);
1862 case DT_accept_insn:
1863 switch (subroutine_type)
1866 if (p->u.insn.num_clobbers_to_add == 0)
1868 printf ("pnum_clobbers != NULL");
1881 /* Emit code for one action. The previous tests have succeeded;
1882 TEST is the last of the chain. In the normal case we simply
1883 perform a state change. For the `accept' tests we must do more work. */
1886 write_action (test, depth, uncond, success, subroutine_type)
1887 struct decision_test *test;
1889 struct decision *success;
1890 enum routine_type subroutine_type;
1897 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1899 fputs (" {\n", stdout);
1906 if (test->type == DT_accept_op)
1908 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1910 /* Only allow DT_accept_insn to follow. */
1914 if (test->type != DT_accept_insn)
1919 /* Sanity check that we're now at the end of the list of tests. */
1923 if (test->type == DT_accept_insn)
1925 switch (subroutine_type)
1928 if (test->u.insn.num_clobbers_to_add != 0)
1929 printf ("%s*pnum_clobbers = %d;\n",
1930 indent, test->u.insn.num_clobbers_to_add);
1931 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
1935 printf ("%sreturn gen_split_%d (operands);\n",
1936 indent, test->u.insn.code_number);
1940 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1941 indent, test->u.insn.code_number);
1942 printf ("%sif (tem != 0)\n%s goto ret1;\n", indent, indent);
1951 printf("%sgoto L%d;\n", indent, success->number);
1952 success->need_label = 1;
1956 fputs (" }\n", stdout);
1959 /* Return 1 if the test is always true and has no fallthru path. Return -1
1960 if the test does have a fallthru path, but requires that the condition be
1961 terminated. Otherwise return 0 for a normal test. */
1962 /* ??? is_unconditional is a stupid name for a tri-state function. */
1965 is_unconditional (t, subroutine_type)
1966 struct decision_test *t;
1967 enum routine_type subroutine_type;
1969 if (t->type == DT_accept_op)
1972 if (t->type == DT_accept_insn)
1974 switch (subroutine_type)
1977 return (t->u.insn.num_clobbers_to_add == 0);
1990 /* Emit code for one node -- the conditional and the accompanying action.
1991 Return true if there is no fallthru path. */
1994 write_node (p, depth, subroutine_type)
1997 enum routine_type subroutine_type;
1999 struct decision_test *test, *last_test;
2002 last_test = test = p->tests;
2003 uncond = is_unconditional (test, subroutine_type);
2007 write_cond (test, depth, subroutine_type);
2009 while ((test = test->next) != NULL)
2014 uncond2 = is_unconditional (test, subroutine_type);
2019 write_cond (test, depth, subroutine_type);
2025 write_action (last_test, depth, uncond, p->success.first, subroutine_type);
2030 /* Emit code for all of the sibling nodes of HEAD. */
2033 write_tree_1 (head, depth, subroutine_type)
2034 struct decision_head *head;
2036 enum routine_type subroutine_type;
2038 struct decision *p, *next;
2041 for (p = head->first; p ; p = next)
2043 /* The label for the first element was printed in write_tree. */
2044 if (p != head->first && p->need_label)
2045 OUTPUT_LABEL (" ", p->number);
2047 /* Attempt to write a switch statement for a whole sequence. */
2048 next = write_switch (p, depth);
2053 /* Failed -- fall back and write one node. */
2054 uncond = write_node (p, depth, subroutine_type);
2059 /* Finished with this chain. Close a fallthru path by branching
2060 to the afterward node. */
2062 write_afterward (head->last, head->last->afterward, " ");
2065 /* Write out the decision tree starting at HEAD. PREVPOS is the
2066 position at the node that branched to this node. */
2069 write_tree (head, prevpos, type, initial)
2070 struct decision_head *head;
2071 const char *prevpos;
2072 enum routine_type type;
2075 register struct decision *p = head->first;
2079 OUTPUT_LABEL (" ", p->number);
2081 if (! initial && p->subroutine_number > 0)
2083 static const char * const name_prefix[] = {
2084 "recog", "split", "peephole2"
2087 static const char * const call_suffix[] = {
2088 ", pnum_clobbers", "", ", _plast_insn"
2091 /* This node has been broken out into a separate subroutine.
2092 Call it, test the result, and branch accordingly. */
2096 printf (" tem = %s_%d (x0, insn%s);\n",
2097 name_prefix[type], p->subroutine_number, call_suffix[type]);
2098 if (IS_SPLIT (type))
2099 printf (" if (tem != 0)\n return tem;\n");
2101 printf (" if (tem >= 0)\n return tem;\n");
2103 change_state (p->position, p->afterward->position, NULL, " ");
2104 printf (" goto L%d;\n", p->afterward->number);
2108 printf (" return %s_%d (x0, insn%s);\n",
2109 name_prefix[type], p->subroutine_number, call_suffix[type]);
2114 int depth = strlen (p->position);
2116 change_state (prevpos, p->position, head->last->afterward, " ");
2117 write_tree_1 (head, depth, type);
2119 for (p = head->first; p; p = p->next)
2120 if (p->success.first)
2121 write_tree (&p->success, p->position, type, 0);
2125 /* Write out a subroutine of type TYPE to do comparisons starting at
2129 write_subroutine (head, type)
2130 struct decision_head *head;
2131 enum routine_type type;
2133 static const char * const proto_pattern[] = {
2134 "%sint recog%s PROTO ((rtx, rtx, int *));\n",
2135 "%srtx split%s PROTO ((rtx, rtx));\n",
2136 "%srtx peephole2%s PROTO ((rtx, rtx, rtx *));\n"
2139 static const char * const decl_pattern[] = {
2141 recog%s (x0, insn, pnum_clobbers)\n\
2143 rtx insn ATTRIBUTE_UNUSED;\n\
2144 int *pnum_clobbers ATTRIBUTE_UNUSED;\n",
2147 split%s (x0, insn)\n\
2149 rtx insn ATTRIBUTE_UNUSED;\n",
2152 peephole2%s (x0, insn, _plast_insn)\n\
2154 rtx insn ATTRIBUTE_UNUSED;\n\
2155 rtx *_plast_insn ATTRIBUTE_UNUSED;\n"
2158 int subfunction = head->first ? head->first->subroutine_number : 0;
2163 s_or_e = subfunction ? "static " : "";
2166 sprintf (extension, "_%d", subfunction);
2167 else if (type == RECOG)
2168 extension[0] = '\0';
2170 strcpy (extension, "_insns");
2172 printf (proto_pattern[type], s_or_e, extension);
2173 printf (decl_pattern[type], s_or_e, extension);
2175 printf ("{\n register rtx * const operands = &recog_data.operand[0];\n");
2176 for (i = 1; i <= max_depth; i++)
2177 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
2179 if (type == PEEPHOLE2)
2180 printf (" register rtx _last_insn = insn;\n");
2181 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2184 write_tree (head, "", type, 1);
2186 printf (" goto ret0;\n");
2188 if (type == PEEPHOLE2)
2189 printf (" ret1:\n *_plast_insn = _last_insn;\n return tem;\n");
2190 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2193 /* In break_out_subroutines, we discovered the boundaries for the
2194 subroutines, but did not write them out. Do so now. */
2197 write_subroutines (head, type)
2198 struct decision_head *head;
2199 enum routine_type type;
2203 for (p = head->first; p ; p = p->next)
2204 if (p->success.first)
2205 write_subroutines (&p->success, type);
2207 if (head->first->subroutine_number > 0)
2208 write_subroutine (head, type);
2211 /* Begin the output file. */
2217 /* Generated automatically by the program `genrecog' from the target\n\
2218 machine description file. */\n\
2220 #include \"config.h\"\n\
2221 #include \"system.h\"\n\
2222 #include \"rtl.h\"\n\
2223 #include \"tm_p.h\"\n\
2224 #include \"function.h\"\n\
2225 #include \"insn-config.h\"\n\
2226 #include \"recog.h\"\n\
2227 #include \"real.h\"\n\
2228 #include \"output.h\"\n\
2229 #include \"flags.h\"\n\
2230 #include \"hard-reg-set.h\"\n\
2231 #include \"resource.h\"\n\
2235 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2236 X0 is a valid instruction.\n\
2238 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2239 returns a nonnegative number which is the insn code number for the\n\
2240 pattern that matched. This is the same as the order in the machine\n\
2241 description of the entry that matched. This number can be used as an\n\
2242 index into `insn_data' and other tables.\n\
2244 The third argument to recog is an optional pointer to an int. If\n\
2245 present, recog will accept a pattern if it matches except for missing\n\
2246 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2247 the optional pointer will be set to the number of CLOBBERs that need\n\
2248 to be added (it should be initialized to zero by the caller). If it\n\
2249 is set nonzero, the caller should allocate a PARALLEL of the\n\
2250 appropriate size, copy the initial entries, and call add_clobbers\n\
2251 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2255 The function split_insns returns 0 if the rtl could not\n\
2256 be split or the split rtl in a SEQUENCE if it can be.\n\
2258 The function peephole2_insns returns 0 if the rtl could not\n\
2259 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2260 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2265 /* Construct and return a sequence of decisions
2266 that will recognize INSN.
2268 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2270 static struct decision_head
2271 make_insn_sequence (insn, type)
2273 enum routine_type type;
2276 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2277 struct decision *last;
2278 struct decision_test *test, **place;
2279 struct decision_head head;
2281 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2283 if (type == PEEPHOLE2)
2287 /* peephole2 gets special treatment:
2288 - X always gets an outer parallel even if it's only one entry
2289 - we remove all traces of outer-level match_scratch and match_dup
2290 expressions here. */
2291 x = rtx_alloc (PARALLEL);
2292 PUT_MODE (x, VOIDmode);
2293 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2294 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2296 rtx tmp = XVECEXP (insn, 0, i);
2297 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2299 XVECEXP (x, 0, j) = tmp;
2305 else if (XVECLEN (insn, type == RECOG) == 1)
2306 x = XVECEXP (insn, type == RECOG, 0);
2309 x = rtx_alloc (PARALLEL);
2310 XVEC (x, 0) = XVEC (insn, type == RECOG);
2311 PUT_MODE (x, VOIDmode);
2314 validate_pattern (x, insn, 0);
2316 memset(&head, 0, sizeof(head));
2317 last = add_to_sequence (x, &head, "", type, 1);
2319 /* Find the end of the test chain on the last node. */
2320 for (test = last->tests; test->next; test = test->next)
2322 place = &test->next;
2326 /* Need a new node if we have another test to add. */
2327 if (test->type == DT_accept_op)
2329 last = new_decision ("", &last->success);
2330 place = &last->tests;
2332 test = new_decision_test (DT_c_test, &place);
2333 test->u.c_test = c_test;
2336 test = new_decision_test (DT_accept_insn, &place);
2337 test->u.insn.code_number = next_insn_code;
2338 test->u.insn.lineno = pattern_lineno;
2339 test->u.insn.num_clobbers_to_add = 0;
2344 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2345 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2346 If so, set up to recognize the pattern without these CLOBBERs. */
2348 if (GET_CODE (x) == PARALLEL)
2352 /* Find the last non-clobber in the parallel. */
2353 for (i = XVECLEN (x, 0); i > 0; i--)
2355 rtx y = XVECEXP (x, 0, i - 1);
2356 if (GET_CODE (y) != CLOBBER
2357 || (GET_CODE (XEXP (y, 0)) != REG
2358 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2362 if (i != XVECLEN (x, 0))
2365 struct decision_head clobber_head;
2367 /* Build a similar insn without the clobbers. */
2369 new = XVECEXP (x, 0, 0);
2374 new = rtx_alloc (PARALLEL);
2375 XVEC (new, 0) = rtvec_alloc (i);
2376 for (j = i - 1; j >= 0; j--)
2377 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2381 memset (&clobber_head, 0, sizeof(clobber_head));
2382 last = add_to_sequence (new, &clobber_head, "", type, 1);
2384 /* Find the end of the test chain on the last node. */
2385 for (test = last->tests; test->next; test = test->next)
2388 /* We definitely have a new test to add -- create a new
2390 place = &test->next;
2391 if (test->type == DT_accept_op)
2393 last = new_decision ("", &last->success);
2394 place = &last->tests;
2399 test = new_decision_test (DT_c_test, &place);
2400 test->u.c_test = c_test;
2403 test = new_decision_test (DT_accept_insn, &place);
2404 test->u.insn.code_number = next_insn_code;
2405 test->u.insn.lineno = pattern_lineno;
2406 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2408 merge_trees (&head, &clobber_head);
2414 /* Define the subroutine we will call below and emit in genemit. */
2415 printf ("extern rtx gen_split_%d PROTO ((rtx *));\n", next_insn_code);
2419 /* Define the subroutine we will call below and emit in genemit. */
2420 printf ("extern rtx gen_peephole2_%d PROTO ((rtx, rtx *));\n",
2430 process_tree (head, subroutine_type)
2431 struct decision_head *head;
2432 enum routine_type subroutine_type;
2434 if (head->first == NULL)
2436 /* We can elide peephole2_insns, but not recog or split_insns. */
2437 if (subroutine_type == PEEPHOLE2)
2442 factor_tests (head);
2444 next_subroutine_number = 0;
2445 break_out_subroutines (head, 1);
2446 find_afterward (head, NULL);
2448 /* We run this after find_afterward, because find_afterward needs
2449 the redundant DT_mode tests on predicates to determine whether
2450 two tests can both be true or not. */
2451 simplify_tests(head);
2453 write_subroutines (head, subroutine_type);
2456 write_subroutine (head, subroutine_type);
2465 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2469 progname = "genrecog";
2470 obstack_init (rtl_obstack);
2472 memset (&recog_tree, 0, sizeof recog_tree);
2473 memset (&split_tree, 0, sizeof split_tree);
2474 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2477 fatal ("No input file name.");
2479 infile = fopen (argv[1], "r");
2483 return FATAL_EXIT_CODE;
2485 read_rtx_filename = argv[1];
2492 /* Read the machine description. */
2496 c = read_skip_spaces (infile);
2500 pattern_lineno = read_rtx_lineno;
2502 desc = read_rtx (infile);
2503 if (GET_CODE (desc) == DEFINE_INSN)
2505 h = make_insn_sequence (desc, RECOG);
2506 merge_trees (&recog_tree, &h);
2508 else if (GET_CODE (desc) == DEFINE_SPLIT)
2510 h = make_insn_sequence (desc, SPLIT);
2511 merge_trees (&split_tree, &h);
2513 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2515 h = make_insn_sequence (desc, PEEPHOLE2);
2516 merge_trees (&peephole2_tree, &h);
2519 if (GET_CODE (desc) == DEFINE_PEEPHOLE
2520 || GET_CODE (desc) == DEFINE_EXPAND)
2526 return FATAL_EXIT_CODE;
2530 process_tree (&recog_tree, RECOG);
2531 process_tree (&split_tree, SPLIT);
2532 process_tree (&peephole2_tree, PEEPHOLE2);
2535 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2538 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2540 get_insn_name (code)
2543 if (code < insn_name_ptr_size)
2544 return insn_name_ptr[code];
2550 record_insn_name (code, name)
2554 static const char *last_real_name = "insn";
2555 static int last_real_code = 0;
2558 if (insn_name_ptr_size <= code)
2561 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2563 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2564 memset (insn_name_ptr + insn_name_ptr_size, 0,
2565 sizeof(char *) * (new_size - insn_name_ptr_size));
2566 insn_name_ptr_size = new_size;
2569 if (!name || name[0] == '\0')
2571 new = xmalloc (strlen (last_real_name) + 10);
2572 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2576 last_real_name = new = xstrdup (name);
2577 last_real_code = code;
2580 insn_name_ptr[code] = new;
2587 register size_t len = strlen (input) + 1;
2588 register char *output = xmalloc (len);
2589 memcpy (output, input, len);
2594 xrealloc (old, size)
2600 ptr = (PTR) realloc (old, size);
2602 ptr = (PTR) malloc (size);
2604 fatal ("virtual memory exhausted");
2612 register PTR val = (PTR) malloc (size);
2615 fatal ("virtual memory exhausted");
2620 debug_decision_2 (test)
2621 struct decision_test *test;
2626 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2629 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2632 fprintf (stderr, "veclen=%d", test->u.veclen);
2634 case DT_elt_zero_int:
2635 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2637 case DT_elt_one_int:
2638 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2640 case DT_elt_zero_wide:
2641 fprintf (stderr, "elt0_w=");
2642 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2645 fprintf (stderr, "dup=%d", test->u.dup);
2648 fprintf (stderr, "pred=(%s,%s)",
2649 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2654 strncpy (sub, test->u.c_test, sizeof(sub));
2655 memcpy (sub+16, "...", 4);
2656 fprintf (stderr, "c_test=\"%s\"", sub);
2660 fprintf (stderr, "A_op=%d", test->u.opno);
2662 case DT_accept_insn:
2663 fprintf (stderr, "A_insn=(%d,%d)",
2664 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2673 debug_decision_1 (d, indent)
2678 struct decision_test *test;
2682 for (i = 0; i < indent; ++i)
2684 fputs ("(nil)\n", stderr);
2688 for (i = 0; i < indent; ++i)
2695 debug_decision_2 (test);
2696 while ((test = test->next) != NULL)
2698 fputs (" + ", stderr);
2699 debug_decision_2 (test);
2702 fprintf (stderr, "} %d n %d a %d\n", d->number,
2703 (d->next ? d->next->number : -1),
2704 (d->afterward ? d->afterward->number : -1));
2708 debug_decision_0 (d, indent, maxdepth)
2710 int indent, maxdepth;
2719 for (i = 0; i < indent; ++i)
2721 fputs ("(nil)\n", stderr);
2725 debug_decision_1 (d, indent);
2726 for (n = d->success.first; n ; n = n->next)
2727 debug_decision_0 (n, indent + 2, maxdepth - 1);
2734 debug_decision_0 (d, 0, 1000000);
2738 debug_decision_list (d)
2743 debug_decision_0 (d, 0, 0);