1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* This program is used to produce insn-recog.c, which contains a
24 function called `recog' plus its subroutines. These functions
25 contain a decision tree that recognizes whether an rtx, the
26 argument given to recog, is a valid instruction.
28 recog returns -1 if the rtx is not valid. If the rtx is valid,
29 recog returns a nonnegative number which is the insn code number
30 for the pattern that matched. This is the same as the order in the
31 machine description of the entry that matched. This number can be
32 used as an index into various insn_* tables, such as insn_template,
33 insn_outfun, and insn_n_operands (found in insn-output.c).
35 The third argument to recog is an optional pointer to an int. If
36 present, recog will accept a pattern if it matches except for
37 missing CLOBBER expressions at the end. In that case, the value
38 pointed to by the optional pointer will be set to the number of
39 CLOBBERs that need to be added (it should be initialized to zero by
40 the caller). If it is set nonzero, the caller should allocate a
41 PARALLEL of the appropriate size, copy the initial entries, and
42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
44 This program also generates the function `split_insns', which
45 returns 0 if the rtl could not be split, or it returns the split
48 This program also generates the function `peephole2_insns', which
49 returns 0 if the rtl could not be matched. If there was a match,
50 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
57 #include "gensupport.h"
60 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
61 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
63 /* Holds an array of names indexed by insn_code_number. */
64 static char **insn_name_ptr = 0;
65 static int insn_name_ptr_size = 0;
67 /* A listhead of decision trees. The alternatives to a node are kept
68 in a doublely-linked list so we can easily add nodes to the proper
69 place when merging. */
73 struct decision *first;
74 struct decision *last;
77 /* A single test. The two accept types aren't tests per-se, but
78 their equality (or lack thereof) does affect tree merging so
79 it is convenient to keep them here. */
83 /* A linked list through the tests attached to a node. */
84 struct decision_test *next;
86 /* These types are roughly in the order in which we'd like to test them. */
88 DT_mode, DT_code, DT_veclen,
89 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide,
90 DT_dup, DT_pred, DT_c_test,
91 DT_accept_op, DT_accept_insn
96 enum machine_mode mode; /* Machine mode of node. */
97 RTX_CODE code; /* Code to test. */
101 const char *name; /* Predicate to call. */
102 int index; /* Index into `preds' or -1. */
103 enum machine_mode mode; /* Machine mode for node. */
106 const char *c_test; /* Additional test to perform. */
107 int veclen; /* Length of vector. */
108 int dup; /* Number of operand to compare against. */
109 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
110 int opno; /* Operand number matched. */
113 int code_number; /* Insn number matched. */
114 int lineno; /* Line number of the insn. */
115 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
120 /* Data structure for decision tree for recognizing legitimate insns. */
124 struct decision_head success; /* Nodes to test on success. */
125 struct decision *next; /* Node to test on failure. */
126 struct decision *prev; /* Node whose failure tests us. */
127 struct decision *afterward; /* Node to test on success,
128 but failure of successor nodes. */
130 const char *position; /* String denoting position in pattern. */
132 struct decision_test *tests; /* The tests for this node. */
134 int number; /* Node number, used for labels */
135 int subroutine_number; /* Number of subroutine this node starts */
136 int need_label; /* Label needs to be output. */
139 #define SUBROUTINE_THRESHOLD 100
141 static int next_subroutine_number;
143 /* We can write three types of subroutines: One for insn recognition,
144 one to split insns, and one for peephole-type optimizations. This
145 defines which type is being written. */
148 RECOG, SPLIT, PEEPHOLE2
151 #define IS_SPLIT(X) ((X) != RECOG)
153 /* Next available node number for tree nodes. */
155 static int next_number;
157 /* Next number to use as an insn_code. */
159 static int next_insn_code;
161 /* Similar, but counts all expressions in the MD file; used for
164 static int next_index;
166 /* Record the highest depth we ever have so we know how many variables to
167 allocate in each subroutine we make. */
169 static int max_depth;
171 /* The line number of the start of the pattern currently being processed. */
172 static int pattern_lineno;
174 /* Count of errors. */
175 static int error_count;
177 /* This table contains a list of the rtl codes that can possibly match a
178 predicate defined in recog.c. The function `maybe_both_true' uses it to
179 deduce that there are no expressions that can be matches by certain pairs
180 of tree nodes. Also, if a predicate can match only one code, we can
181 hardwire that code into the node testing the predicate. */
183 static struct pred_table
186 RTX_CODE codes[NUM_RTX_CODE];
188 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
189 LABEL_REF, SUBREG, REG, MEM}},
190 #ifdef PREDICATE_CODES
193 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
194 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
195 {"register_operand", {SUBREG, REG}},
196 {"pmode_register_operand", {SUBREG, REG}},
197 {"scratch_operand", {SCRATCH, REG}},
198 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
200 {"const_int_operand", {CONST_INT}},
201 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
202 {"nonimmediate_operand", {SUBREG, REG, MEM}},
203 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
204 LABEL_REF, SUBREG, REG}},
205 {"push_operand", {MEM}},
206 {"pop_operand", {MEM}},
207 {"memory_operand", {SUBREG, MEM}},
208 {"indirect_operand", {SUBREG, MEM}},
209 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
210 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
212 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
213 LABEL_REF, SUBREG, REG, MEM}}
216 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
218 static const char * special_mode_pred_table[] = {
219 #ifdef SPECIAL_MODE_PREDICATES
220 SPECIAL_MODE_PREDICATES
222 "pmode_register_operand"
225 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
227 static struct decision *new_decision
228 PARAMS ((const char *, struct decision_head *));
229 static struct decision_test *new_decision_test
230 PARAMS ((enum decision_type, struct decision_test ***));
231 static rtx find_operand
233 static void validate_pattern
234 PARAMS ((rtx, rtx, rtx, int));
235 static struct decision *add_to_sequence
236 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
238 static int maybe_both_true_2
239 PARAMS ((struct decision_test *, struct decision_test *));
240 static int maybe_both_true_1
241 PARAMS ((struct decision_test *, struct decision_test *));
242 static int maybe_both_true
243 PARAMS ((struct decision *, struct decision *, int));
245 static int nodes_identical_1
246 PARAMS ((struct decision_test *, struct decision_test *));
247 static int nodes_identical
248 PARAMS ((struct decision *, struct decision *));
249 static void merge_accept_insn
250 PARAMS ((struct decision *, struct decision *));
251 static void merge_trees
252 PARAMS ((struct decision_head *, struct decision_head *));
254 static void factor_tests
255 PARAMS ((struct decision_head *));
256 static void simplify_tests
257 PARAMS ((struct decision_head *));
258 static int break_out_subroutines
259 PARAMS ((struct decision_head *, int));
260 static void find_afterward
261 PARAMS ((struct decision_head *, struct decision *));
263 static void change_state
264 PARAMS ((const char *, const char *, struct decision *, const char *));
265 static void print_code
266 PARAMS ((enum rtx_code));
267 static void write_afterward
268 PARAMS ((struct decision *, struct decision *, const char *));
269 static struct decision *write_switch
270 PARAMS ((struct decision *, int));
271 static void write_cond
272 PARAMS ((struct decision_test *, int, enum routine_type));
273 static void write_action
274 PARAMS ((struct decision *, struct decision_test *, int, int,
275 struct decision *, enum routine_type));
276 static int is_unconditional
277 PARAMS ((struct decision_test *, enum routine_type));
278 static int write_node
279 PARAMS ((struct decision *, int, enum routine_type));
280 static void write_tree_1
281 PARAMS ((struct decision_head *, int, enum routine_type));
282 static void write_tree
283 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
284 static void write_subroutine
285 PARAMS ((struct decision_head *, enum routine_type));
286 static void write_subroutines
287 PARAMS ((struct decision_head *, enum routine_type));
288 static void write_header
291 static struct decision_head make_insn_sequence
292 PARAMS ((rtx, enum routine_type));
293 static void process_tree
294 PARAMS ((struct decision_head *, enum routine_type));
296 static void record_insn_name
297 PARAMS ((int, const char *));
299 static void debug_decision_0
300 PARAMS ((struct decision *, int, int));
301 static void debug_decision_1
302 PARAMS ((struct decision *, int));
303 static void debug_decision_2
304 PARAMS ((struct decision_test *));
305 extern void debug_decision
306 PARAMS ((struct decision *));
307 extern void debug_decision_list
308 PARAMS ((struct decision *));
310 /* Create a new node in sequence after LAST. */
312 static struct decision *
313 new_decision (position, last)
314 const char *position;
315 struct decision_head *last;
317 register struct decision *new
318 = (struct decision *) xmalloc (sizeof (struct decision));
320 memset (new, 0, sizeof (*new));
321 new->success = *last;
322 new->position = xstrdup (position);
323 new->number = next_number++;
325 last->first = last->last = new;
329 /* Create a new test and link it in at PLACE. */
331 static struct decision_test *
332 new_decision_test (type, pplace)
333 enum decision_type type;
334 struct decision_test ***pplace;
336 struct decision_test **place = *pplace;
337 struct decision_test *test;
339 test = (struct decision_test *) xmalloc (sizeof (*test));
350 /* Search for and return operand N. */
353 find_operand (pattern, n)
362 code = GET_CODE (pattern);
363 if ((code == MATCH_SCRATCH
364 || code == MATCH_INSN
365 || code == MATCH_OPERAND
366 || code == MATCH_OPERATOR
367 || code == MATCH_PARALLEL)
368 && XINT (pattern, 0) == n)
371 fmt = GET_RTX_FORMAT (code);
372 len = GET_RTX_LENGTH (code);
373 for (i = 0; i < len; i++)
378 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
383 for (j = 0; j < XVECLEN (pattern, i); j++)
384 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
388 case 'i': case 'w': case '0': case 's':
399 /* Check for various errors in patterns. SET is nonnull for a destination,
400 and is the complete set pattern. SET_CODE is '=' for normal sets, and
401 '+' within a context that requires in-out constraints. */
404 validate_pattern (pattern, insn, set, set_code)
415 code = GET_CODE (pattern);
425 const char *pred_name = XSTR (pattern, 1);
426 int allows_non_lvalue = 1, allows_non_const = 1;
427 int special_mode_pred = 0;
430 if (GET_CODE (insn) == DEFINE_INSN)
431 c_test = XSTR (insn, 2);
433 c_test = XSTR (insn, 1);
435 if (pred_name[0] != 0)
437 for (i = 0; i < NUM_KNOWN_PREDS; i++)
438 if (! strcmp (preds[i].name, pred_name))
441 if (i < NUM_KNOWN_PREDS)
445 allows_non_lvalue = allows_non_const = 0;
446 for (j = 0; preds[i].codes[j] != 0; j++)
448 RTX_CODE c = preds[i].codes[j];
455 && c != CONSTANT_P_RTX)
456 allows_non_const = 1;
463 && c != STRICT_LOW_PART)
464 allows_non_lvalue = 1;
469 #ifdef PREDICATE_CODES
470 /* If the port has a list of the predicates it uses but
472 message_with_line (pattern_lineno,
473 "warning: `%s' not in PREDICATE_CODES",
478 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
479 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
481 special_mode_pred = 1;
486 /* A MATCH_OPERAND that is a SET should have an output reload. */
487 if (set && code == MATCH_OPERAND)
490 && XSTR (pattern, 2)[0] != '\0'
491 && XSTR (pattern, 2)[0] != '+')
493 message_with_line (pattern_lineno,
494 "operand %d missing in-out reload",
498 else if (XSTR (pattern, 2)[0] != '\0'
499 && XSTR (pattern, 2)[0] != '='
500 && XSTR (pattern, 2)[0] != '+')
502 message_with_line (pattern_lineno,
503 "operand %d missing output reload",
509 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
510 while not likely to occur at runtime, results in less efficient
511 code from insn-recog.c. */
513 && pred_name[0] != '\0'
514 && allows_non_lvalue)
516 message_with_line (pattern_lineno,
517 "warning: destination operand %d allows non-lvalue",
521 /* A modeless MATCH_OPERAND can be handy when we can
522 check for multiple modes in the c_test. In most other cases,
523 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
524 and PEEP2 can FAIL within the output pattern. Exclude
525 address_operand, since its mode is related to the mode of
526 the memory not the operand. Exclude the SET_DEST of a call
527 instruction, as that is a common idiom. */
529 if (GET_MODE (pattern) == VOIDmode
530 && code == MATCH_OPERAND
531 && GET_CODE (insn) == DEFINE_INSN
533 && ! special_mode_pred
534 && pred_name[0] != '\0'
535 && strcmp (pred_name, "address_operand") != 0
536 && strstr (c_test, "operands") == NULL
538 && GET_CODE (set) == SET
539 && GET_CODE (SET_SRC (set)) == CALL))
541 message_with_line (pattern_lineno,
542 "warning: operand %d missing mode?",
550 enum machine_mode dmode, smode;
553 dest = SET_DEST (pattern);
554 src = SET_SRC (pattern);
556 /* Find the referant for a DUP. */
558 if (GET_CODE (dest) == MATCH_DUP
559 || GET_CODE (dest) == MATCH_OP_DUP
560 || GET_CODE (dest) == MATCH_PAR_DUP)
561 dest = find_operand (insn, XINT (dest, 0));
563 if (GET_CODE (src) == MATCH_DUP
564 || GET_CODE (src) == MATCH_OP_DUP
565 || GET_CODE (src) == MATCH_PAR_DUP)
566 src = find_operand (insn, XINT (src, 0));
568 /* STRICT_LOW_PART is a wrapper. Its argument is the real
569 destination, and it's mode should match the source. */
570 if (GET_CODE (dest) == STRICT_LOW_PART)
571 dest = XEXP (dest, 0);
573 dmode = GET_MODE (dest);
574 smode = GET_MODE (src);
576 /* The mode of an ADDRESS_OPERAND is the mode of the memory
577 reference, not the mode of the address. */
578 if (GET_CODE (src) == MATCH_OPERAND
579 && ! strcmp (XSTR (src, 1), "address_operand"))
582 /* The operands of a SET must have the same mode unless one
584 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
586 message_with_line (pattern_lineno,
587 "mode mismatch in set: %smode vs %smode",
588 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
592 /* If only one of the operands is VOIDmode, and PC or CC0 is
593 not involved, it's probably a mistake. */
594 else if (dmode != smode
595 && GET_CODE (dest) != PC
596 && GET_CODE (dest) != CC0
597 && GET_CODE (src) != PC
598 && GET_CODE (src) != CC0
599 && GET_CODE (src) != CONST_INT)
602 which = (dmode == VOIDmode ? "destination" : "source");
603 message_with_line (pattern_lineno,
604 "warning: %s missing a mode?", which);
607 if (dest != SET_DEST (pattern))
608 validate_pattern (dest, insn, pattern, '=');
609 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
610 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
615 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
619 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
620 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
621 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
624 case STRICT_LOW_PART:
625 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
626 validate_pattern (XEXP (pattern, 1), insn, NULL, 0);
630 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
632 message_with_line (pattern_lineno,
633 "operand to label_ref %smode not VOIDmode",
634 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
643 fmt = GET_RTX_FORMAT (code);
644 len = GET_RTX_LENGTH (code);
645 for (i = 0; i < len; i++)
650 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
654 for (j = 0; j < XVECLEN (pattern, i); j++)
655 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
658 case 'i': case 'w': case '0': case 's':
667 /* Create a chain of nodes to verify that an rtl expression matches
670 LAST is a pointer to the listhead in the previous node in the chain (or
671 in the calling function, for the first node).
673 POSITION is the string representing the current position in the insn.
675 INSN_TYPE is the type of insn for which we are emitting code.
677 A pointer to the final node in the chain is returned. */
679 static struct decision *
680 add_to_sequence (pattern, last, position, insn_type, top)
682 struct decision_head *last;
683 const char *position;
684 enum routine_type insn_type;
688 struct decision *this, *sub;
689 struct decision_test *test;
690 struct decision_test **place;
693 register const char *fmt;
694 int depth = strlen (position);
696 enum machine_mode mode;
698 if (depth > max_depth)
701 subpos = (char *) alloca (depth + 2);
702 strcpy (subpos, position);
703 subpos[depth + 1] = 0;
705 sub = this = new_decision (position, last);
706 place = &this->tests;
709 mode = GET_MODE (pattern);
710 code = GET_CODE (pattern);
715 /* Toplevel peephole pattern. */
716 if (insn_type == PEEPHOLE2 && top)
718 /* We don't need the node we just created -- unlink it. */
719 last->first = last->last = NULL;
721 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
723 /* Which insn we're looking at is represented by A-Z. We don't
724 ever use 'A', however; it is always implied. */
726 subpos[depth] = (i > 0 ? 'A' + i : 0);
727 sub = add_to_sequence (XVECEXP (pattern, 0, i),
728 last, subpos, insn_type, 0);
729 last = &sub->success;
734 /* Else nothing special. */
743 const char *pred_name;
744 RTX_CODE was_code = code;
745 int allows_const_int = 1;
747 if (code == MATCH_SCRATCH)
749 pred_name = "scratch_operand";
754 pred_name = XSTR (pattern, 1);
755 if (code == MATCH_PARALLEL)
761 /* We know exactly what const_int_operand matches -- any CONST_INT. */
762 if (strcmp ("const_int_operand", pred_name) == 0)
767 else if (pred_name[0] != 0)
769 test = new_decision_test (DT_pred, &place);
770 test->u.pred.name = pred_name;
771 test->u.pred.mode = mode;
773 /* See if we know about this predicate and save its number. If
774 we do, and it only accepts one code, note that fact. The
775 predicate `const_int_operand' only tests for a CONST_INT, so
776 if we do so we can avoid calling it at all.
778 Finally, if we know that the predicate does not allow
779 CONST_INT, we know that the only way the predicate can match
780 is if the modes match (here we use the kludge of relying on
781 the fact that "address_operand" accepts CONST_INT; otherwise,
782 it would have to be a special case), so we can test the mode
783 (but we need not). This fact should considerably simplify the
786 for (i = 0; i < NUM_KNOWN_PREDS; i++)
787 if (! strcmp (preds[i].name, pred_name))
790 if (i < NUM_KNOWN_PREDS)
794 test->u.pred.index = i;
796 if (preds[i].codes[1] == 0 && code == UNKNOWN)
797 code = preds[i].codes[0];
799 allows_const_int = 0;
800 for (j = 0; preds[i].codes[j] != 0; j++)
801 if (preds[i].codes[j] == CONST_INT)
803 allows_const_int = 1;
808 test->u.pred.index = -1;
811 /* Can't enforce a mode if we allow const_int. */
812 if (allows_const_int)
815 /* Accept the operand, ie. record it in `operands'. */
816 test = new_decision_test (DT_accept_op, &place);
817 test->u.opno = XINT (pattern, 0);
819 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
821 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
822 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
824 subpos[depth] = i + base;
825 sub = add_to_sequence (XVECEXP (pattern, 2, i),
826 &sub->success, subpos, insn_type, 0);
835 test = new_decision_test (DT_dup, &place);
836 test->u.dup = XINT (pattern, 0);
838 test = new_decision_test (DT_accept_op, &place);
839 test->u.opno = XINT (pattern, 0);
841 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
843 subpos[depth] = i + '0';
844 sub = add_to_sequence (XVECEXP (pattern, 1, i),
845 &sub->success, subpos, insn_type, 0);
853 test = new_decision_test (DT_dup, &place);
854 test->u.dup = XINT (pattern, 0);
858 pattern = XEXP (pattern, 0);
865 fmt = GET_RTX_FORMAT (code);
866 len = GET_RTX_LENGTH (code);
868 /* Do tests against the current node first. */
869 for (i = 0; i < (size_t) len; i++)
875 test = new_decision_test (DT_elt_zero_int, &place);
876 test->u.intval = XINT (pattern, i);
880 test = new_decision_test (DT_elt_one_int, &place);
881 test->u.intval = XINT (pattern, i);
886 else if (fmt[i] == 'w')
891 test = new_decision_test (DT_elt_zero_wide, &place);
892 test->u.intval = XWINT (pattern, i);
894 else if (fmt[i] == 'E')
899 test = new_decision_test (DT_veclen, &place);
900 test->u.veclen = XVECLEN (pattern, i);
904 /* Now test our sub-patterns. */
905 for (i = 0; i < (size_t) len; i++)
910 subpos[depth] = '0' + i;
911 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
912 subpos, insn_type, 0);
918 for (j = 0; j < XVECLEN (pattern, i); j++)
920 subpos[depth] = 'a' + j;
921 sub = add_to_sequence (XVECEXP (pattern, i, j),
922 &sub->success, subpos, insn_type, 0);
939 /* Insert nodes testing mode and code, if they're still relevant,
940 before any of the nodes we may have added above. */
943 place = &this->tests;
944 test = new_decision_test (DT_code, &place);
948 if (mode != VOIDmode)
950 place = &this->tests;
951 test = new_decision_test (DT_mode, &place);
955 /* If we didn't insert any tests or accept nodes, hork. */
956 if (this->tests == NULL)
962 /* A subroutine of maybe_both_true; examines only one test.
963 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
966 maybe_both_true_2 (d1, d2)
967 struct decision_test *d1, *d2;
969 if (d1->type == d2->type)
974 return d1->u.mode == d2->u.mode;
977 return d1->u.code == d2->u.code;
980 return d1->u.veclen == d2->u.veclen;
982 case DT_elt_zero_int:
984 case DT_elt_zero_wide:
985 return d1->u.intval == d2->u.intval;
992 /* If either has a predicate that we know something about, set
993 things up so that D1 is the one that always has a known
994 predicate. Then see if they have any codes in common. */
996 if (d1->type == DT_pred || d2->type == DT_pred)
998 if (d2->type == DT_pred)
1000 struct decision_test *tmp;
1001 tmp = d1, d1 = d2, d2 = tmp;
1004 /* If D2 tests a mode, see if it matches D1. */
1005 if (d1->u.pred.mode != VOIDmode)
1007 if (d2->type == DT_mode)
1009 if (d1->u.pred.mode != d2->u.mode
1010 /* The mode of an address_operand predicate is the
1011 mode of the memory, not the operand. It can only
1012 be used for testing the predicate, so we must
1014 && strcmp (d1->u.pred.name, "address_operand") != 0)
1017 /* Don't check two predicate modes here, because if both predicates
1018 accept CONST_INT, then both can still be true even if the modes
1019 are different. If they don't accept CONST_INT, there will be a
1020 separate DT_mode that will make maybe_both_true_1 return 0. */
1023 if (d1->u.pred.index >= 0)
1025 /* If D2 tests a code, see if it is in the list of valid
1026 codes for D1's predicate. */
1027 if (d2->type == DT_code)
1029 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1032 if (*c == d2->u.code)
1040 /* Otherwise see if the predicates have any codes in common. */
1041 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1043 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1046 while (*c1 != 0 && !common)
1048 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1049 while (*c2 != 0 && !common)
1051 common = (*c1 == *c2);
1066 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1067 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1070 maybe_both_true_1 (d1, d2)
1071 struct decision_test *d1, *d2;
1073 struct decision_test *t1, *t2;
1075 /* A match_operand with no predicate can match anything. Recognize
1076 this by the existance of a lone DT_accept_op test. */
1077 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1080 /* Eliminate pairs of tests while they can exactly match. */
1081 while (d1 && d2 && d1->type == d2->type)
1083 if (maybe_both_true_2 (d1, d2) == 0)
1085 d1 = d1->next, d2 = d2->next;
1088 /* After that, consider all pairs. */
1089 for (t1 = d1; t1 ; t1 = t1->next)
1090 for (t2 = d2; t2 ; t2 = t2->next)
1091 if (maybe_both_true_2 (t1, t2) == 0)
1097 /* Return 0 if we can prove that there is no RTL that can match both
1098 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1099 can match both or just that we couldn't prove there wasn't such an RTL).
1101 TOPLEVEL is non-zero if we are to only look at the top level and not
1102 recursively descend. */
1105 maybe_both_true (d1, d2, toplevel)
1106 struct decision *d1, *d2;
1109 struct decision *p1, *p2;
1112 /* Don't compare strings on the different positions in insn. Doing so
1113 is incorrect and results in false matches from constructs like
1115 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1116 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1118 [(set (match_operand:HI "register_operand" "r")
1119 (match_operand:HI "register_operand" "r"))]
1121 If we are presented with such, we are recursing through the remainder
1122 of a node's success nodes (from the loop at the end of this function).
1123 Skip forward until we come to a position that matches.
1125 Due to the way position strings are constructed, we know that iterating
1126 forward from the lexically lower position (e.g. "00") will run into
1127 the lexically higher position (e.g. "1") and not the other way around.
1128 This saves a bit of effort. */
1130 cmp = strcmp (d1->position, d2->position);
1136 /* If the d2->position was lexically lower, swap. */
1138 p1 = d1, d1 = d2, d2 = p1;
1140 if (d1->success.first == 0)
1142 for (p1 = d1->success.first; p1; p1 = p1->next)
1143 if (maybe_both_true (p1, d2, 0))
1149 /* Test the current level. */
1150 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1154 /* We can't prove that D1 and D2 cannot both be true. If we are only
1155 to check the top level, return 1. Otherwise, see if we can prove
1156 that all choices in both successors are mutually exclusive. If
1157 either does not have any successors, we can't prove they can't both
1160 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1163 for (p1 = d1->success.first; p1; p1 = p1->next)
1164 for (p2 = d2->success.first; p2; p2 = p2->next)
1165 if (maybe_both_true (p1, p2, 0))
1171 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1174 nodes_identical_1 (d1, d2)
1175 struct decision_test *d1, *d2;
1180 return d1->u.mode == d2->u.mode;
1183 return d1->u.code == d2->u.code;
1186 return (d1->u.pred.mode == d2->u.pred.mode
1187 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1190 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1193 return d1->u.veclen == d2->u.veclen;
1196 return d1->u.dup == d2->u.dup;
1198 case DT_elt_zero_int:
1199 case DT_elt_one_int:
1200 case DT_elt_zero_wide:
1201 return d1->u.intval == d2->u.intval;
1204 return d1->u.opno == d2->u.opno;
1206 case DT_accept_insn:
1207 /* Differences will be handled in merge_accept_insn. */
1215 /* True iff the two nodes are identical (on one level only). Due
1216 to the way these lists are constructed, we shouldn't have to
1217 consider different orderings on the tests. */
1220 nodes_identical (d1, d2)
1221 struct decision *d1, *d2;
1223 struct decision_test *t1, *t2;
1225 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1227 if (t1->type != t2->type)
1229 if (! nodes_identical_1 (t1, t2))
1233 /* For success, they should now both be null. */
1237 /* Check that their subnodes are at the same position, as any one set
1238 of sibling decisions must be at the same position. */
1239 if (d1->success.first
1240 && d2->success.first
1241 && strcmp (d1->success.first->position, d2->success.first->position))
1247 /* A subroutine of merge_trees; given two nodes that have been declared
1248 identical, cope with two insn accept states. If they differ in the
1249 number of clobbers, then the conflict was created by make_insn_sequence
1250 and we can drop the with-clobbers version on the floor. If both
1251 nodes have no additional clobbers, we have found an ambiguity in the
1252 source machine description. */
1255 merge_accept_insn (oldd, addd)
1256 struct decision *oldd, *addd;
1258 struct decision_test *old, *add;
1260 for (old = oldd->tests; old; old = old->next)
1261 if (old->type == DT_accept_insn)
1266 for (add = addd->tests; add; add = add->next)
1267 if (add->type == DT_accept_insn)
1272 /* If one node is for a normal insn and the second is for the base
1273 insn with clobbers stripped off, the second node should be ignored. */
1275 if (old->u.insn.num_clobbers_to_add == 0
1276 && add->u.insn.num_clobbers_to_add > 0)
1278 /* Nothing to do here. */
1280 else if (old->u.insn.num_clobbers_to_add > 0
1281 && add->u.insn.num_clobbers_to_add == 0)
1283 /* In this case, replace OLD with ADD. */
1284 old->u.insn = add->u.insn;
1288 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1289 get_insn_name (add->u.insn.code_number),
1290 get_insn_name (old->u.insn.code_number));
1291 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1292 get_insn_name (old->u.insn.code_number));
1297 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1300 merge_trees (oldh, addh)
1301 struct decision_head *oldh, *addh;
1303 struct decision *next, *add;
1305 if (addh->first == 0)
1307 if (oldh->first == 0)
1313 /* Trying to merge bits at different positions isn't possible. */
1314 if (strcmp (oldh->first->position, addh->first->position))
1317 for (add = addh->first; add ; add = next)
1319 struct decision *old, *insert_before = NULL;
1323 /* The semantics of pattern matching state that the tests are
1324 done in the order given in the MD file so that if an insn
1325 matches two patterns, the first one will be used. However,
1326 in practice, most, if not all, patterns are unambiguous so
1327 that their order is independent. In that case, we can merge
1328 identical tests and group all similar modes and codes together.
1330 Scan starting from the end of OLDH until we reach a point
1331 where we reach the head of the list or where we pass a
1332 pattern that could also be true if NEW is true. If we find
1333 an identical pattern, we can merge them. Also, record the
1334 last node that tests the same code and mode and the last one
1335 that tests just the same mode.
1337 If we have no match, place NEW after the closest match we found. */
1339 for (old = oldh->last; old; old = old->prev)
1341 if (nodes_identical (old, add))
1343 merge_accept_insn (old, add);
1344 merge_trees (&old->success, &add->success);
1348 if (maybe_both_true (old, add, 0))
1351 /* Insert the nodes in DT test type order, which is roughly
1352 how expensive/important the test is. Given that the tests
1353 are also ordered within the list, examining the first is
1355 if (add->tests->type < old->tests->type)
1356 insert_before = old;
1359 if (insert_before == NULL)
1362 add->prev = oldh->last;
1363 oldh->last->next = add;
1368 if ((add->prev = insert_before->prev) != NULL)
1369 add->prev->next = add;
1372 add->next = insert_before;
1373 insert_before->prev = add;
1380 /* Walk the tree looking for sub-nodes that perform common tests.
1381 Factor out the common test into a new node. This enables us
1382 (depending on the test type) to emit switch statements later. */
1386 struct decision_head *head;
1388 struct decision *first, *next;
1390 for (first = head->first; first && first->next; first = next)
1392 enum decision_type type;
1393 struct decision *new, *old_last;
1395 type = first->tests->type;
1398 /* Want at least two compatible sequential nodes. */
1399 if (next->tests->type != type)
1402 /* Don't want all node types, just those we can turn into
1403 switch statements. */
1406 && type != DT_veclen
1407 && type != DT_elt_zero_int
1408 && type != DT_elt_one_int
1409 && type != DT_elt_zero_wide)
1412 /* If we'd been performing more than one test, create a new node
1413 below our first test. */
1414 if (first->tests->next != NULL)
1416 new = new_decision (first->position, &first->success);
1417 new->tests = first->tests->next;
1418 first->tests->next = NULL;
1421 /* Crop the node tree off after our first test. */
1423 old_last = head->last;
1426 /* For each compatible test, adjust to perform only one test in
1427 the top level node, then merge the node back into the tree. */
1430 struct decision_head h;
1432 if (next->tests->next != NULL)
1434 new = new_decision (next->position, &next->success);
1435 new->tests = next->tests->next;
1436 next->tests->next = NULL;
1441 h.first = h.last = new;
1443 merge_trees (head, &h);
1445 while (next && next->tests->type == type);
1447 /* After we run out of compatible tests, graft the remaining nodes
1448 back onto the tree. */
1451 next->prev = head->last;
1452 head->last->next = next;
1453 head->last = old_last;
1458 for (first = head->first; first; first = first->next)
1459 factor_tests (&first->success);
1462 /* After factoring, try to simplify the tests on any one node.
1463 Tests that are useful for switch statements are recognizable
1464 by having only a single test on a node -- we'll be manipulating
1465 nodes with multiple tests:
1467 If we have mode tests or code tests that are redundant with
1468 predicates, remove them. */
1471 simplify_tests (head)
1472 struct decision_head *head;
1474 struct decision *tree;
1476 for (tree = head->first; tree; tree = tree->next)
1478 struct decision_test *a, *b;
1485 /* Find a predicate node. */
1486 while (b && b->type != DT_pred)
1490 /* Due to how these tests are constructed, we don't even need
1491 to check that the mode and code are compatible -- they were
1492 generated from the predicate in the first place. */
1493 while (a->type == DT_mode || a->type == DT_code)
1500 for (tree = head->first; tree; tree = tree->next)
1501 simplify_tests (&tree->success);
1504 /* Count the number of subnodes of HEAD. If the number is high enough,
1505 make the first node in HEAD start a separate subroutine in the C code
1506 that is generated. */
1509 break_out_subroutines (head, initial)
1510 struct decision_head *head;
1514 struct decision *sub;
1516 for (sub = head->first; sub; sub = sub->next)
1517 size += 1 + break_out_subroutines (&sub->success, 0);
1519 if (size > SUBROUTINE_THRESHOLD && ! initial)
1521 head->first->subroutine_number = ++next_subroutine_number;
1527 /* For each node p, find the next alternative that might be true
1531 find_afterward (head, real_afterward)
1532 struct decision_head *head;
1533 struct decision *real_afterward;
1535 struct decision *p, *q, *afterward;
1537 /* We can't propogate alternatives across subroutine boundaries.
1538 This is not incorrect, merely a minor optimization loss. */
1541 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1543 for ( ; p ; p = p->next)
1545 /* Find the next node that might be true if this one fails. */
1546 for (q = p->next; q ; q = q->next)
1547 if (maybe_both_true (p, q, 1))
1550 /* If we reached the end of the list without finding one,
1551 use the incoming afterward position. */
1560 for (p = head->first; p ; p = p->next)
1561 if (p->success.first)
1562 find_afterward (&p->success, p->afterward);
1564 /* When we are generating a subroutine, record the real afterward
1565 position in the first node where write_tree can find it, and we
1566 can do the right thing at the subroutine call site. */
1568 if (p->subroutine_number > 0)
1569 p->afterward = real_afterward;
1572 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1573 actions are necessary to move to NEWPOS. If we fail to move to the
1574 new state, branch to node AFTERWARD if non-zero, otherwise return.
1576 Failure to move to the new state can only occur if we are trying to
1577 match multiple insns and we try to step past the end of the stream. */
1580 change_state (oldpos, newpos, afterward, indent)
1583 struct decision *afterward;
1586 int odepth = strlen (oldpos);
1587 int ndepth = strlen (newpos);
1589 int old_has_insn, new_has_insn;
1591 /* Pop up as many levels as necessary. */
1592 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1595 /* Hunt for the last [A-Z] in both strings. */
1596 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1597 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1599 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1600 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1603 /* Go down to desired level. */
1604 while (depth < ndepth)
1606 /* It's a different insn from the first one. */
1607 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1609 /* We can only fail if we're moving down the tree. */
1610 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1612 printf ("%stem = peep2_next_insn (%d);\n",
1613 indent, newpos[depth] - 'A');
1617 printf ("%stem = peep2_next_insn (%d);\n",
1618 indent, newpos[depth] - 'A');
1619 printf ("%sif (tem == NULL_RTX)\n", indent);
1621 printf ("%s goto L%d;\n", indent, afterward->number);
1623 printf ("%s goto ret0;\n", indent);
1625 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1627 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1628 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1629 indent, depth + 1, depth, newpos[depth] - 'a');
1631 printf ("%sx%d = XEXP (x%d, %c);\n",
1632 indent, depth + 1, depth, newpos[depth]);
1637 /* Print the enumerator constant for CODE -- the upcase version of
1644 register const char *p;
1645 for (p = GET_RTX_NAME (code); *p; p++)
1646 putchar (TOUPPER (*p));
1649 /* Emit code to cross an afterward link -- change state and branch. */
1652 write_afterward (start, afterward, indent)
1653 struct decision *start;
1654 struct decision *afterward;
1657 if (!afterward || start->subroutine_number > 0)
1658 printf("%sgoto ret0;\n", indent);
1661 change_state (start->position, afterward->position, NULL, indent);
1662 printf ("%sgoto L%d;\n", indent, afterward->number);
1666 /* Emit a switch statement, if possible, for an initial sequence of
1667 nodes at START. Return the first node yet untested. */
1669 static struct decision *
1670 write_switch (start, depth)
1671 struct decision *start;
1674 struct decision *p = start;
1675 enum decision_type type = p->tests->type;
1676 struct decision *needs_label = NULL;
1678 /* If we have two or more nodes in sequence that test the same one
1679 thing, we may be able to use a switch statement. */
1683 || p->next->tests->type != type
1684 || p->next->tests->next)
1687 /* DT_code is special in that we can do interesting things with
1688 known predicates at the same time. */
1689 if (type == DT_code)
1691 char codemap[NUM_RTX_CODE];
1692 struct decision *ret;
1695 memset (codemap, 0, sizeof(codemap));
1697 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1698 code = p->tests->u.code;
1701 if (p != start && p->need_label && needs_label == NULL)
1706 printf (":\n goto L%d;\n", p->success.first->number);
1707 p->success.first->need_label = 1;
1714 && p->tests->type == DT_code
1715 && ! codemap[code = p->tests->u.code]);
1717 /* If P is testing a predicate that we know about and we haven't
1718 seen any of the codes that are valid for the predicate, we can
1719 write a series of "case" statement, one for each possible code.
1720 Since we are already in a switch, these redundant tests are very
1721 cheap and will reduce the number of predicates called. */
1723 /* Note that while we write out cases for these predicates here,
1724 we don't actually write the test here, as it gets kinda messy.
1725 It is trivial to leave this to later by telling our caller that
1726 we only processed the CODE tests. */
1727 if (needs_label != NULL)
1732 while (p && p->tests->type == DT_pred
1733 && p->tests->u.pred.index >= 0)
1737 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1738 if (codemap[(int) *c] != 0)
1741 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1746 codemap[(int) *c] = 1;
1749 printf (" goto L%d;\n", p->number);
1755 /* Make the default case skip the predicates we managed to match. */
1757 printf (" default:\n");
1762 printf (" goto L%d;\n", p->number);
1766 write_afterward (start, start->afterward, " ");
1769 printf (" break;\n");
1774 else if (type == DT_mode
1775 || type == DT_veclen
1776 || type == DT_elt_zero_int
1777 || type == DT_elt_one_int
1778 || type == DT_elt_zero_wide)
1780 printf (" switch (");
1784 printf ("GET_MODE (x%d)", depth);
1787 printf ("XVECLEN (x%d, 0)", depth);
1789 case DT_elt_zero_int:
1790 printf ("XINT (x%d, 0)", depth);
1792 case DT_elt_one_int:
1793 printf ("XINT (x%d, 1)", depth);
1795 case DT_elt_zero_wide:
1796 /* Convert result of XWINT to int for portability since some C
1797 compilers won't do it and some will. */
1798 printf ("(int) XWINT (x%d, 0)", depth);
1807 if (p != start && p->need_label && needs_label == NULL)
1814 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1817 printf ("%d", p->tests->u.veclen);
1819 case DT_elt_zero_int:
1820 case DT_elt_one_int:
1821 case DT_elt_zero_wide:
1822 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1827 printf (":\n goto L%d;\n", p->success.first->number);
1828 p->success.first->need_label = 1;
1832 while (p && p->tests->type == type && !p->tests->next);
1834 printf (" default:\n break;\n }\n");
1836 return needs_label != NULL ? needs_label : p;
1840 /* None of the other tests are ameanable. */
1845 /* Emit code for one test. */
1848 write_cond (p, depth, subroutine_type)
1849 struct decision_test *p;
1851 enum routine_type subroutine_type;
1856 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1860 printf ("GET_CODE (x%d) == ", depth);
1861 print_code (p->u.code);
1865 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1868 case DT_elt_zero_int:
1869 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1872 case DT_elt_one_int:
1873 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1876 case DT_elt_zero_wide:
1877 printf ("XWINT (x%d, 0) == ", depth);
1878 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1882 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1886 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1887 GET_MODE_NAME (p->u.pred.mode));
1891 printf ("(%s)", p->u.c_test);
1894 case DT_accept_insn:
1895 switch (subroutine_type)
1898 if (p->u.insn.num_clobbers_to_add == 0)
1900 printf ("pnum_clobbers != NULL");
1913 /* Emit code for one action. The previous tests have succeeded;
1914 TEST is the last of the chain. In the normal case we simply
1915 perform a state change. For the `accept' tests we must do more work. */
1918 write_action (p, test, depth, uncond, success, subroutine_type)
1920 struct decision_test *test;
1922 struct decision *success;
1923 enum routine_type subroutine_type;
1930 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1932 fputs (" {\n", stdout);
1939 if (test->type == DT_accept_op)
1941 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1943 /* Only allow DT_accept_insn to follow. */
1947 if (test->type != DT_accept_insn)
1952 /* Sanity check that we're now at the end of the list of tests. */
1956 if (test->type == DT_accept_insn)
1958 switch (subroutine_type)
1961 if (test->u.insn.num_clobbers_to_add != 0)
1962 printf ("%s*pnum_clobbers = %d;\n",
1963 indent, test->u.insn.num_clobbers_to_add);
1964 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
1968 printf ("%sreturn gen_split_%d (operands);\n",
1969 indent, test->u.insn.code_number);
1974 int match_len = 0, i;
1976 for (i = strlen (p->position) - 1; i >= 0; --i)
1977 if (p->position[i] >= 'A' && p->position[i] <= 'Z')
1979 match_len = p->position[i] - 'A';
1982 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
1983 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1984 indent, test->u.insn.code_number);
1985 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
1995 printf("%sgoto L%d;\n", indent, success->number);
1996 success->need_label = 1;
2000 fputs (" }\n", stdout);
2003 /* Return 1 if the test is always true and has no fallthru path. Return -1
2004 if the test does have a fallthru path, but requires that the condition be
2005 terminated. Otherwise return 0 for a normal test. */
2006 /* ??? is_unconditional is a stupid name for a tri-state function. */
2009 is_unconditional (t, subroutine_type)
2010 struct decision_test *t;
2011 enum routine_type subroutine_type;
2013 if (t->type == DT_accept_op)
2016 if (t->type == DT_accept_insn)
2018 switch (subroutine_type)
2021 return (t->u.insn.num_clobbers_to_add == 0);
2034 /* Emit code for one node -- the conditional and the accompanying action.
2035 Return true if there is no fallthru path. */
2038 write_node (p, depth, subroutine_type)
2041 enum routine_type subroutine_type;
2043 struct decision_test *test, *last_test;
2046 last_test = test = p->tests;
2047 uncond = is_unconditional (test, subroutine_type);
2051 write_cond (test, depth, subroutine_type);
2053 while ((test = test->next) != NULL)
2058 uncond2 = is_unconditional (test, subroutine_type);
2063 write_cond (test, depth, subroutine_type);
2069 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2074 /* Emit code for all of the sibling nodes of HEAD. */
2077 write_tree_1 (head, depth, subroutine_type)
2078 struct decision_head *head;
2080 enum routine_type subroutine_type;
2082 struct decision *p, *next;
2085 for (p = head->first; p ; p = next)
2087 /* The label for the first element was printed in write_tree. */
2088 if (p != head->first && p->need_label)
2089 OUTPUT_LABEL (" ", p->number);
2091 /* Attempt to write a switch statement for a whole sequence. */
2092 next = write_switch (p, depth);
2097 /* Failed -- fall back and write one node. */
2098 uncond = write_node (p, depth, subroutine_type);
2103 /* Finished with this chain. Close a fallthru path by branching
2104 to the afterward node. */
2106 write_afterward (head->last, head->last->afterward, " ");
2109 /* Write out the decision tree starting at HEAD. PREVPOS is the
2110 position at the node that branched to this node. */
2113 write_tree (head, prevpos, type, initial)
2114 struct decision_head *head;
2115 const char *prevpos;
2116 enum routine_type type;
2119 register struct decision *p = head->first;
2123 OUTPUT_LABEL (" ", p->number);
2125 if (! initial && p->subroutine_number > 0)
2127 static const char * const name_prefix[] = {
2128 "recog", "split", "peephole2"
2131 static const char * const call_suffix[] = {
2132 ", pnum_clobbers", "", ", _pmatch_len"
2135 /* This node has been broken out into a separate subroutine.
2136 Call it, test the result, and branch accordingly. */
2140 printf (" tem = %s_%d (x0, insn%s);\n",
2141 name_prefix[type], p->subroutine_number, call_suffix[type]);
2142 if (IS_SPLIT (type))
2143 printf (" if (tem != 0)\n return tem;\n");
2145 printf (" if (tem >= 0)\n return tem;\n");
2147 change_state (p->position, p->afterward->position, NULL, " ");
2148 printf (" goto L%d;\n", p->afterward->number);
2152 printf (" return %s_%d (x0, insn%s);\n",
2153 name_prefix[type], p->subroutine_number, call_suffix[type]);
2158 int depth = strlen (p->position);
2160 change_state (prevpos, p->position, head->last->afterward, " ");
2161 write_tree_1 (head, depth, type);
2163 for (p = head->first; p; p = p->next)
2164 if (p->success.first)
2165 write_tree (&p->success, p->position, type, 0);
2169 /* Write out a subroutine of type TYPE to do comparisons starting at
2173 write_subroutine (head, type)
2174 struct decision_head *head;
2175 enum routine_type type;
2177 int subfunction = head->first ? head->first->subroutine_number : 0;
2182 s_or_e = subfunction ? "static " : "";
2185 sprintf (extension, "_%d", subfunction);
2186 else if (type == RECOG)
2187 extension[0] = '\0';
2189 strcpy (extension, "_insns");
2194 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2196 recog%s (x0, insn, pnum_clobbers)\n\
2198 rtx insn ATTRIBUTE_UNUSED;\n\
2199 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2202 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2204 split%s (x0, insn)\n\
2206 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2209 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2212 peephole2%s (x0, insn, _pmatch_len)\n\
2214 rtx insn ATTRIBUTE_UNUSED;\n\
2215 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2219 printf ("{\n register rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2220 for (i = 1; i <= max_depth; i++)
2221 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
2223 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2226 printf (" recog_data.insn = NULL_RTX;\n");
2229 write_tree (head, "", type, 1);
2231 printf (" goto ret0;\n");
2233 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2236 /* In break_out_subroutines, we discovered the boundaries for the
2237 subroutines, but did not write them out. Do so now. */
2240 write_subroutines (head, type)
2241 struct decision_head *head;
2242 enum routine_type type;
2246 for (p = head->first; p ; p = p->next)
2247 if (p->success.first)
2248 write_subroutines (&p->success, type);
2250 if (head->first->subroutine_number > 0)
2251 write_subroutine (head, type);
2254 /* Begin the output file. */
2260 /* Generated automatically by the program `genrecog' from the target\n\
2261 machine description file. */\n\
2263 #include \"config.h\"\n\
2264 #include \"system.h\"\n\
2265 #include \"rtl.h\"\n\
2266 #include \"tm_p.h\"\n\
2267 #include \"function.h\"\n\
2268 #include \"insn-config.h\"\n\
2269 #include \"recog.h\"\n\
2270 #include \"real.h\"\n\
2271 #include \"output.h\"\n\
2272 #include \"flags.h\"\n\
2273 #include \"hard-reg-set.h\"\n\
2274 #include \"resource.h\"\n\
2278 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2279 X0 is a valid instruction.\n\
2281 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2282 returns a nonnegative number which is the insn code number for the\n\
2283 pattern that matched. This is the same as the order in the machine\n\
2284 description of the entry that matched. This number can be used as an\n\
2285 index into `insn_data' and other tables.\n");
2287 The third argument to recog is an optional pointer to an int. If\n\
2288 present, recog will accept a pattern if it matches except for missing\n\
2289 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2290 the optional pointer will be set to the number of CLOBBERs that need\n\
2291 to be added (it should be initialized to zero by the caller). If it");
2293 is set nonzero, the caller should allocate a PARALLEL of the\n\
2294 appropriate size, copy the initial entries, and call add_clobbers\n\
2295 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2299 The function split_insns returns 0 if the rtl could not\n\
2300 be split or the split rtl in a SEQUENCE if it can be.\n\
2302 The function peephole2_insns returns 0 if the rtl could not\n\
2303 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2304 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2309 /* Construct and return a sequence of decisions
2310 that will recognize INSN.
2312 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2314 static struct decision_head
2315 make_insn_sequence (insn, type)
2317 enum routine_type type;
2320 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2321 struct decision *last;
2322 struct decision_test *test, **place;
2323 struct decision_head head;
2326 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2328 c_test_pos[0] = '\0';
2329 if (type == PEEPHOLE2)
2333 /* peephole2 gets special treatment:
2334 - X always gets an outer parallel even if it's only one entry
2335 - we remove all traces of outer-level match_scratch and match_dup
2336 expressions here. */
2337 x = rtx_alloc (PARALLEL);
2338 PUT_MODE (x, VOIDmode);
2339 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2340 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2342 rtx tmp = XVECEXP (insn, 0, i);
2343 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2345 XVECEXP (x, 0, j) = tmp;
2351 c_test_pos[0] = 'A' + j - 1;
2352 c_test_pos[1] = '\0';
2354 else if (XVECLEN (insn, type == RECOG) == 1)
2355 x = XVECEXP (insn, type == RECOG, 0);
2358 x = rtx_alloc (PARALLEL);
2359 XVEC (x, 0) = XVEC (insn, type == RECOG);
2360 PUT_MODE (x, VOIDmode);
2363 validate_pattern (x, insn, NULL_RTX, 0);
2365 memset(&head, 0, sizeof(head));
2366 last = add_to_sequence (x, &head, "", type, 1);
2368 /* Find the end of the test chain on the last node. */
2369 for (test = last->tests; test->next; test = test->next)
2371 place = &test->next;
2375 /* Need a new node if we have another test to add. */
2376 if (test->type == DT_accept_op)
2378 last = new_decision (c_test_pos, &last->success);
2379 place = &last->tests;
2381 test = new_decision_test (DT_c_test, &place);
2382 test->u.c_test = c_test;
2385 test = new_decision_test (DT_accept_insn, &place);
2386 test->u.insn.code_number = next_insn_code;
2387 test->u.insn.lineno = pattern_lineno;
2388 test->u.insn.num_clobbers_to_add = 0;
2393 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2394 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2395 If so, set up to recognize the pattern without these CLOBBERs. */
2397 if (GET_CODE (x) == PARALLEL)
2401 /* Find the last non-clobber in the parallel. */
2402 for (i = XVECLEN (x, 0); i > 0; i--)
2404 rtx y = XVECEXP (x, 0, i - 1);
2405 if (GET_CODE (y) != CLOBBER
2406 || (GET_CODE (XEXP (y, 0)) != REG
2407 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2411 if (i != XVECLEN (x, 0))
2414 struct decision_head clobber_head;
2416 /* Build a similar insn without the clobbers. */
2418 new = XVECEXP (x, 0, 0);
2423 new = rtx_alloc (PARALLEL);
2424 XVEC (new, 0) = rtvec_alloc (i);
2425 for (j = i - 1; j >= 0; j--)
2426 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2430 memset (&clobber_head, 0, sizeof(clobber_head));
2431 last = add_to_sequence (new, &clobber_head, "", type, 1);
2433 /* Find the end of the test chain on the last node. */
2434 for (test = last->tests; test->next; test = test->next)
2437 /* We definitely have a new test to add -- create a new
2439 place = &test->next;
2440 if (test->type == DT_accept_op)
2442 last = new_decision ("", &last->success);
2443 place = &last->tests;
2448 test = new_decision_test (DT_c_test, &place);
2449 test->u.c_test = c_test;
2452 test = new_decision_test (DT_accept_insn, &place);
2453 test->u.insn.code_number = next_insn_code;
2454 test->u.insn.lineno = pattern_lineno;
2455 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2457 merge_trees (&head, &clobber_head);
2463 /* Define the subroutine we will call below and emit in genemit. */
2464 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2468 /* Define the subroutine we will call below and emit in genemit. */
2469 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2478 process_tree (head, subroutine_type)
2479 struct decision_head *head;
2480 enum routine_type subroutine_type;
2482 if (head->first == NULL)
2484 /* We can elide peephole2_insns, but not recog or split_insns. */
2485 if (subroutine_type == PEEPHOLE2)
2490 factor_tests (head);
2492 next_subroutine_number = 0;
2493 break_out_subroutines (head, 1);
2494 find_afterward (head, NULL);
2496 /* We run this after find_afterward, because find_afterward needs
2497 the redundant DT_mode tests on predicates to determine whether
2498 two tests can both be true or not. */
2499 simplify_tests(head);
2501 write_subroutines (head, subroutine_type);
2504 write_subroutine (head, subroutine_type);
2507 extern int main PARAMS ((int, char **));
2515 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2517 progname = "genrecog";
2519 memset (&recog_tree, 0, sizeof recog_tree);
2520 memset (&split_tree, 0, sizeof split_tree);
2521 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2524 fatal ("No input file name.");
2526 if (init_md_reader (argv[1]) != SUCCESS_EXIT_CODE)
2527 return (FATAL_EXIT_CODE);
2534 /* Read the machine description. */
2538 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2542 if (GET_CODE (desc) == DEFINE_INSN)
2544 h = make_insn_sequence (desc, RECOG);
2545 merge_trees (&recog_tree, &h);
2547 else if (GET_CODE (desc) == DEFINE_SPLIT)
2549 h = make_insn_sequence (desc, SPLIT);
2550 merge_trees (&split_tree, &h);
2552 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2554 h = make_insn_sequence (desc, PEEPHOLE2);
2555 merge_trees (&peephole2_tree, &h);
2562 return FATAL_EXIT_CODE;
2566 process_tree (&recog_tree, RECOG);
2567 process_tree (&split_tree, SPLIT);
2568 process_tree (&peephole2_tree, PEEPHOLE2);
2571 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2574 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2576 get_insn_name (code)
2579 if (code < insn_name_ptr_size)
2580 return insn_name_ptr[code];
2586 record_insn_name (code, name)
2590 static const char *last_real_name = "insn";
2591 static int last_real_code = 0;
2594 if (insn_name_ptr_size <= code)
2597 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2599 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2600 memset (insn_name_ptr + insn_name_ptr_size, 0,
2601 sizeof(char *) * (new_size - insn_name_ptr_size));
2602 insn_name_ptr_size = new_size;
2605 if (!name || name[0] == '\0')
2607 new = xmalloc (strlen (last_real_name) + 10);
2608 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2612 last_real_name = new = xstrdup (name);
2613 last_real_code = code;
2616 insn_name_ptr[code] = new;
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);