1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* This program is used to produce insn-recog.c, which contains a
24 function called `recog' plus its subroutines. These functions
25 contain a decision tree that recognizes whether an rtx, the
26 argument given to recog, is a valid instruction.
28 recog returns -1 if the rtx is not valid. If the rtx is valid,
29 recog returns a nonnegative number which is the insn code number
30 for the pattern that matched. This is the same as the order in the
31 machine description of the entry that matched. This number can be
32 used as an index into various insn_* tables, such as insn_template,
33 insn_outfun, and insn_n_operands (found in insn-output.c).
35 The third argument to recog is an optional pointer to an int. If
36 present, recog will accept a pattern if it matches except for
37 missing CLOBBER expressions at the end. In that case, the value
38 pointed to by the optional pointer will be set to the number of
39 CLOBBERs that need to be added (it should be initialized to zero by
40 the caller). If it is set nonzero, the caller should allocate a
41 PARALLEL of the appropriate size, copy the initial entries, and
42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
44 This program also generates the function `split_insns', which
45 returns 0 if the rtl could not be split, or it returns the split
48 This program also generates the function `peephole2_insns', which
49 returns 0 if the rtl could not be matched. If there was a match,
50 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
59 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
60 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
62 static struct obstack obstack;
63 struct obstack *rtl_obstack = &obstack;
65 #define obstack_chunk_alloc xmalloc
66 #define obstack_chunk_free free
68 /* Holds an array of names indexed by insn_code_number. */
69 static char **insn_name_ptr = 0;
70 static int insn_name_ptr_size = 0;
72 /* A listhead of decision trees. The alternatives to a node are kept
73 in a doublely-linked list so we can easily add nodes to the proper
74 place when merging. */
78 struct decision *first;
79 struct decision *last;
82 /* A single test. The two accept types aren't tests per-se, but
83 their equality (or lack thereof) does affect tree merging so
84 it is convenient to keep them here. */
88 /* A linked list through the tests attached to a node. */
89 struct decision_test *next;
91 /* These types are roughly in the order in which we'd like to test them. */
93 DT_mode, DT_code, DT_veclen,
94 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide,
95 DT_dup, DT_pred, DT_c_test,
96 DT_accept_op, DT_accept_insn
101 enum machine_mode mode; /* Machine mode of node. */
102 RTX_CODE code; /* Code to test. */
106 const char *name; /* Predicate to call. */
107 int index; /* Index into `preds' or -1. */
108 enum machine_mode mode; /* Machine mode for node. */
111 const char *c_test; /* Additional test to perform. */
112 int veclen; /* Length of vector. */
113 int dup; /* Number of operand to compare against. */
114 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
115 int opno; /* Operand number matched. */
118 int code_number; /* Insn number matched. */
119 int lineno; /* Line number of the insn. */
120 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
125 /* Data structure for decision tree for recognizing legitimate insns. */
129 struct decision_head success; /* Nodes to test on success. */
130 struct decision *next; /* Node to test on failure. */
131 struct decision *prev; /* Node whose failure tests us. */
132 struct decision *afterward; /* Node to test on success,
133 but failure of successor nodes. */
135 const char *position; /* String denoting position in pattern. */
137 struct decision_test *tests; /* The tests for this node. */
139 int number; /* Node number, used for labels */
140 int subroutine_number; /* Number of subroutine this node starts */
141 int need_label; /* Label needs to be output. */
144 #define SUBROUTINE_THRESHOLD 100
146 static int next_subroutine_number;
148 /* We can write three types of subroutines: One for insn recognition,
149 one to split insns, and one for peephole-type optimizations. This
150 defines which type is being written. */
153 RECOG, SPLIT, PEEPHOLE2
156 #define IS_SPLIT(X) ((X) != RECOG)
158 /* Next available node number for tree nodes. */
160 static int next_number;
162 /* Next number to use as an insn_code. */
164 static int next_insn_code;
166 /* Similar, but counts all expressions in the MD file; used for
169 static int next_index;
171 /* Record the highest depth we ever have so we know how many variables to
172 allocate in each subroutine we make. */
174 static int max_depth;
176 /* The line number of the start of the pattern currently being processed. */
177 static int pattern_lineno;
179 /* Count of errors. */
180 static int error_count;
182 /* This table contains a list of the rtl codes that can possibly match a
183 predicate defined in recog.c. The function `maybe_both_true' uses it to
184 deduce that there are no expressions that can be matches by certain pairs
185 of tree nodes. Also, if a predicate can match only one code, we can
186 hardwire that code into the node testing the predicate. */
188 static struct pred_table
191 RTX_CODE codes[NUM_RTX_CODE];
193 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
194 LABEL_REF, SUBREG, REG, MEM}},
195 #ifdef PREDICATE_CODES
198 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
199 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
200 {"register_operand", {SUBREG, REG}},
201 {"pmode_register_operand", {SUBREG, REG}},
202 {"scratch_operand", {SCRATCH, REG}},
203 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
205 {"const_int_operand", {CONST_INT}},
206 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
207 {"nonimmediate_operand", {SUBREG, REG, MEM}},
208 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
209 LABEL_REF, SUBREG, REG}},
210 {"push_operand", {MEM}},
211 {"pop_operand", {MEM}},
212 {"memory_operand", {SUBREG, MEM}},
213 {"indirect_operand", {SUBREG, MEM}},
214 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
215 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
217 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
218 LABEL_REF, SUBREG, REG, MEM}}
221 #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
223 static const char * special_mode_pred_table[] = {
224 #ifdef SPECIAL_MODE_PREDICATES
225 SPECIAL_MODE_PREDICATES
227 "pmode_register_operand"
230 #define NUM_SPECIAL_MODE_PREDS \
231 (sizeof (special_mode_pred_table) / sizeof (special_mode_pred_table[0]))
233 static void message_with_line
234 PARAMS ((int, const char *, ...)) ATTRIBUTE_PRINTF_2;
236 static struct decision *new_decision
237 PARAMS ((const char *, struct decision_head *));
238 static struct decision_test *new_decision_test
239 PARAMS ((enum decision_type, struct decision_test ***));
240 static rtx find_operand
242 static void validate_pattern
243 PARAMS ((rtx, rtx, rtx));
244 static struct decision *add_to_sequence
245 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
247 static int maybe_both_true_2
248 PARAMS ((struct decision_test *, struct decision_test *));
249 static int maybe_both_true_1
250 PARAMS ((struct decision_test *, struct decision_test *));
251 static int maybe_both_true
252 PARAMS ((struct decision *, struct decision *, int));
254 static int nodes_identical_1
255 PARAMS ((struct decision_test *, struct decision_test *));
256 static int nodes_identical
257 PARAMS ((struct decision *, struct decision *));
258 static void merge_accept_insn
259 PARAMS ((struct decision *, struct decision *));
260 static void merge_trees
261 PARAMS ((struct decision_head *, struct decision_head *));
263 static void factor_tests
264 PARAMS ((struct decision_head *));
265 static void simplify_tests
266 PARAMS ((struct decision_head *));
267 static int break_out_subroutines
268 PARAMS ((struct decision_head *, int));
269 static void find_afterward
270 PARAMS ((struct decision_head *, struct decision *));
272 static void change_state
273 PARAMS ((const char *, const char *, struct decision *, const char *));
274 static void print_code
275 PARAMS ((enum rtx_code));
276 static void write_afterward
277 PARAMS ((struct decision *, struct decision *, const char *));
278 static struct decision *write_switch
279 PARAMS ((struct decision *, int));
280 static void write_cond
281 PARAMS ((struct decision_test *, int, enum routine_type));
282 static void write_action
283 PARAMS ((struct decision_test *, int, int, struct decision *,
285 static int is_unconditional
286 PARAMS ((struct decision_test *, enum routine_type));
287 static int write_node
288 PARAMS ((struct decision *, int, enum routine_type));
289 static void write_tree_1
290 PARAMS ((struct decision_head *, int, enum routine_type));
291 static void write_tree
292 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
293 static void write_subroutine
294 PARAMS ((struct decision_head *, enum routine_type));
295 static void write_subroutines
296 PARAMS ((struct decision_head *, enum routine_type));
297 static void write_header
300 static struct decision_head make_insn_sequence
301 PARAMS ((rtx, enum routine_type));
302 static void process_tree
303 PARAMS ((struct decision_head *, enum routine_type));
305 static void record_insn_name
306 PARAMS ((int, const char *));
308 static void debug_decision_0
309 PARAMS ((struct decision *, int, int));
310 static void debug_decision_1
311 PARAMS ((struct decision *, int));
312 static void debug_decision_2
313 PARAMS ((struct decision_test *));
314 extern void debug_decision
315 PARAMS ((struct decision *));
316 extern void debug_decision_list
317 PARAMS ((struct decision *));
320 message_with_line VPARAMS ((int lineno, const char *msg, ...))
322 #ifndef ANSI_PROTOTYPES
330 #ifndef ANSI_PROTOTYPES
331 lineno = va_arg (ap, int);
332 msg = va_arg (ap, const char *);
335 fprintf (stderr, "%s:%d: ", read_rtx_filename, lineno);
336 vfprintf (stderr, msg, ap);
337 fputc ('\n', stderr);
342 /* Create a new node in sequence after LAST. */
344 static struct decision *
345 new_decision (position, last)
346 const char *position;
347 struct decision_head *last;
349 register struct decision *new
350 = (struct decision *) xmalloc (sizeof (struct decision));
352 memset (new, 0, sizeof (*new));
353 new->success = *last;
354 new->position = xstrdup (position);
355 new->number = next_number++;
357 last->first = last->last = new;
361 /* Create a new test and link it in at PLACE. */
363 static struct decision_test *
364 new_decision_test (type, pplace)
365 enum decision_type type;
366 struct decision_test ***pplace;
368 struct decision_test **place = *pplace;
369 struct decision_test *test;
371 test = (struct decision_test *) xmalloc (sizeof (*test));
382 /* Search for and return operand N. */
385 find_operand (pattern, n)
394 code = GET_CODE (pattern);
395 if ((code == MATCH_SCRATCH
396 || code == MATCH_INSN
397 || code == MATCH_OPERAND
398 || code == MATCH_OPERATOR
399 || code == MATCH_PARALLEL)
400 && XINT (pattern, 0) == n)
403 fmt = GET_RTX_FORMAT (code);
404 len = GET_RTX_LENGTH (code);
405 for (i = 0; i < len; i++)
410 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
415 for (j = 0; j < XVECLEN (pattern, i); j++)
416 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
420 case 'i': case 'w': case '0': case 's':
431 /* Check for various errors in patterns. SET is nonnull for a destination,
432 and is the complete set pattern. */
435 validate_pattern (pattern, insn, set)
445 code = GET_CODE (pattern);
455 const char *pred_name = XSTR (pattern, 1);
456 int allows_non_lvalue = 1, allows_non_const = 1;
457 int special_mode_pred = 0;
460 if (GET_CODE (insn) == DEFINE_INSN)
461 c_test = XSTR (insn, 2);
463 c_test = XSTR (insn, 1);
465 if (pred_name[0] != 0)
467 for (i = 0; i < NUM_KNOWN_PREDS; i++)
468 if (! strcmp (preds[i].name, pred_name))
471 if (i < NUM_KNOWN_PREDS)
475 allows_non_lvalue = allows_non_const = 0;
476 for (j = 0; preds[i].codes[j] != 0; j++)
478 RTX_CODE c = preds[i].codes[j];
485 && c != CONSTANT_P_RTX)
486 allows_non_const = 1;
493 && c != STRICT_LOW_PART)
494 allows_non_lvalue = 1;
499 #ifdef PREDICATE_CODES
500 /* If the port has a list of the predicates it uses but
502 message_with_line (pattern_lineno,
503 "warning: `%s' not in PREDICATE_CODES",
508 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
509 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
511 special_mode_pred = 1;
516 /* A MATCH_OPERAND that is a SET should have an output reload. */
518 && code == MATCH_OPERAND
519 && XSTR (pattern, 2)[0] != '\0'
520 && XSTR (pattern, 2)[0] != '='
521 && XSTR (pattern, 2)[0] != '+')
523 message_with_line (pattern_lineno,
524 "operand %d missing output reload",
529 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
530 while not likely to occur at runtime, results in less efficient
531 code from insn-recog.c. */
533 && pred_name[0] != '\0'
534 && allows_non_lvalue)
536 message_with_line (pattern_lineno,
537 "warning: destination operand %d allows non-lvalue",
541 /* A modeless MATCH_OPERAND can be handy when we can
542 check for multiple modes in the c_test. In most other cases,
543 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
544 and PEEP2 can FAIL within the output pattern. Exclude
545 address_operand, since its mode is related to the mode of
546 the memory not the operand. Exclude the SET_DEST of a call
547 instruction, as that is a common idiom. */
549 if (GET_MODE (pattern) == VOIDmode
550 && code == MATCH_OPERAND
551 && GET_CODE (insn) == DEFINE_INSN
553 && ! special_mode_pred
554 && pred_name[0] != '\0'
555 && strcmp (pred_name, "address_operand") != 0
556 && strstr (c_test, "operands") == NULL
558 && GET_CODE (set) == SET
559 && GET_CODE (SET_SRC (set)) == CALL))
561 message_with_line (pattern_lineno,
562 "warning: operand %d missing mode?",
570 enum machine_mode dmode, smode;
573 dest = SET_DEST (pattern);
574 src = SET_SRC (pattern);
576 /* Find the referant for a DUP. */
578 if (GET_CODE (dest) == MATCH_DUP
579 || GET_CODE (dest) == MATCH_OP_DUP
580 || GET_CODE (dest) == MATCH_PAR_DUP)
581 dest = find_operand (insn, XINT (dest, 0));
583 if (GET_CODE (src) == MATCH_DUP
584 || GET_CODE (src) == MATCH_OP_DUP
585 || GET_CODE (src) == MATCH_PAR_DUP)
586 src = find_operand (insn, XINT (src, 0));
588 /* STRICT_LOW_PART is a wrapper. Its argument is the real
589 destination, and it's mode should match the source. */
590 if (GET_CODE (dest) == STRICT_LOW_PART)
591 dest = XEXP (dest, 0);
593 dmode = GET_MODE (dest);
594 smode = GET_MODE (src);
596 /* The mode of an ADDRESS_OPERAND is the mode of the memory
597 reference, not the mode of the address. */
598 if (GET_CODE (src) == MATCH_OPERAND
599 && ! strcmp (XSTR (src, 1), "address_operand"))
602 /* The operands of a SET must have the same mode unless one
604 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
606 message_with_line (pattern_lineno,
607 "mode mismatch in set: %smode vs %smode",
608 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
612 /* If only one of the operands is VOIDmode, and PC or CC0 is
613 not involved, it's probably a mistake. */
614 else if (dmode != smode
615 && GET_CODE (dest) != PC
616 && GET_CODE (dest) != CC0
617 && GET_CODE (src) != PC
618 && GET_CODE (src) != CC0
619 && GET_CODE (src) != CONST_INT)
622 which = (dmode == VOIDmode ? "destination" : "source");
623 message_with_line (pattern_lineno,
624 "warning: %s missing a mode?", which);
627 if (dest != SET_DEST (pattern))
628 validate_pattern (dest, insn, pattern);
629 validate_pattern (SET_DEST (pattern), insn, pattern);
630 validate_pattern (SET_SRC (pattern), insn, NULL_RTX);
635 validate_pattern (SET_DEST (pattern), insn, pattern);
639 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
641 message_with_line (pattern_lineno,
642 "operand to label_ref %smode not VOIDmode",
643 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
652 fmt = GET_RTX_FORMAT (code);
653 len = GET_RTX_LENGTH (code);
654 for (i = 0; i < len; i++)
659 validate_pattern (XEXP (pattern, i), insn, NULL_RTX);
663 for (j = 0; j < XVECLEN (pattern, i); j++)
664 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX);
667 case 'i': case 'w': case '0': case 's':
676 /* Create a chain of nodes to verify that an rtl expression matches
679 LAST is a pointer to the listhead in the previous node in the chain (or
680 in the calling function, for the first node).
682 POSITION is the string representing the current position in the insn.
684 INSN_TYPE is the type of insn for which we are emitting code.
686 A pointer to the final node in the chain is returned. */
688 static struct decision *
689 add_to_sequence (pattern, last, position, insn_type, top)
691 struct decision_head *last;
692 const char *position;
693 enum routine_type insn_type;
697 struct decision *this, *sub;
698 struct decision_test *test;
699 struct decision_test **place;
702 register const char *fmt;
703 int depth = strlen (position);
705 enum machine_mode mode;
707 if (depth > max_depth)
710 subpos = (char *) alloca (depth + 2);
711 strcpy (subpos, position);
712 subpos[depth + 1] = 0;
714 sub = this = new_decision (position, last);
715 place = &this->tests;
718 mode = GET_MODE (pattern);
719 code = GET_CODE (pattern);
724 /* Toplevel peephole pattern. */
725 if (insn_type == PEEPHOLE2 && top)
727 /* We don't need the node we just created -- unlink it. */
728 last->first = last->last = NULL;
730 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
732 /* Which insn we're looking at is represented by A-Z. We don't
733 ever use 'A', however; it is always implied. */
735 subpos[depth] = (i > 0 ? 'A' + i : 0);
736 sub = add_to_sequence (XVECEXP (pattern, 0, i),
737 last, subpos, insn_type, 0);
738 last = &sub->success;
743 /* Else nothing special. */
752 const char *pred_name;
753 RTX_CODE was_code = code;
754 int allows_const_int = 1;
756 if (code == MATCH_SCRATCH)
758 pred_name = "scratch_operand";
763 pred_name = XSTR (pattern, 1);
764 if (code == MATCH_PARALLEL)
770 /* We know exactly what const_int_operand matches -- any CONST_INT. */
771 if (strcmp ("const_int_operand", pred_name) == 0)
776 else if (pred_name[0] != 0)
778 test = new_decision_test (DT_pred, &place);
779 test->u.pred.name = pred_name;
780 test->u.pred.mode = mode;
782 /* See if we know about this predicate and save its number. If
783 we do, and it only accepts one code, note that fact. The
784 predicate `const_int_operand' only tests for a CONST_INT, so
785 if we do so we can avoid calling it at all.
787 Finally, if we know that the predicate does not allow
788 CONST_INT, we know that the only way the predicate can match
789 is if the modes match (here we use the kludge of relying on
790 the fact that "address_operand" accepts CONST_INT; otherwise,
791 it would have to be a special case), so we can test the mode
792 (but we need not). This fact should considerably simplify the
795 for (i = 0; i < NUM_KNOWN_PREDS; i++)
796 if (! strcmp (preds[i].name, pred_name))
799 if (i < NUM_KNOWN_PREDS)
803 test->u.pred.index = i;
805 if (preds[i].codes[1] == 0 && code == UNKNOWN)
806 code = preds[i].codes[0];
808 allows_const_int = 0;
809 for (j = 0; preds[i].codes[j] != 0; j++)
810 if (preds[i].codes[j] == CONST_INT)
812 allows_const_int = 1;
817 test->u.pred.index = -1;
820 /* Can't enforce a mode if we allow const_int. */
821 if (allows_const_int)
824 /* Accept the operand, ie. record it in `operands'. */
825 test = new_decision_test (DT_accept_op, &place);
826 test->u.opno = XINT (pattern, 0);
828 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
830 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
831 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
833 subpos[depth] = i + base;
834 sub = add_to_sequence (XVECEXP (pattern, 2, i),
835 &sub->success, subpos, insn_type, 0);
844 test = new_decision_test (DT_dup, &place);
845 test->u.dup = XINT (pattern, 0);
847 test = new_decision_test (DT_accept_op, &place);
848 test->u.opno = XINT (pattern, 0);
850 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
852 subpos[depth] = i + '0';
853 sub = add_to_sequence (XVECEXP (pattern, 1, i),
854 &sub->success, subpos, insn_type, 0);
862 test = new_decision_test (DT_dup, &place);
863 test->u.dup = XINT (pattern, 0);
867 pattern = XEXP (pattern, 0);
874 fmt = GET_RTX_FORMAT (code);
875 len = GET_RTX_LENGTH (code);
877 /* Do tests against the current node first. */
878 for (i = 0; i < (size_t) len; i++)
884 test = new_decision_test (DT_elt_zero_int, &place);
885 test->u.intval = XINT (pattern, i);
889 test = new_decision_test (DT_elt_one_int, &place);
890 test->u.intval = XINT (pattern, i);
895 else if (fmt[i] == 'w')
900 test = new_decision_test (DT_elt_zero_wide, &place);
901 test->u.intval = XWINT (pattern, i);
903 else if (fmt[i] == 'E')
908 test = new_decision_test (DT_veclen, &place);
909 test->u.veclen = XVECLEN (pattern, i);
913 /* Now test our sub-patterns. */
914 for (i = 0; i < (size_t) len; i++)
919 subpos[depth] = '0' + i;
920 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
921 subpos, insn_type, 0);
927 for (j = 0; j < XVECLEN (pattern, i); j++)
929 subpos[depth] = 'a' + j;
930 sub = add_to_sequence (XVECEXP (pattern, i, j),
931 &sub->success, subpos, insn_type, 0);
948 /* Insert nodes testing mode and code, if they're still relevant,
949 before any of the nodes we may have added above. */
952 place = &this->tests;
953 test = new_decision_test (DT_code, &place);
957 if (mode != VOIDmode)
959 place = &this->tests;
960 test = new_decision_test (DT_mode, &place);
964 /* If we didn't insert any tests or accept nodes, hork. */
965 if (this->tests == NULL)
971 /* A subroutine of maybe_both_true; examines only one test.
972 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
975 maybe_both_true_2 (d1, d2)
976 struct decision_test *d1, *d2;
978 if (d1->type == d2->type)
983 return d1->u.mode == d2->u.mode;
986 return d1->u.code == d2->u.code;
989 return d1->u.veclen == d2->u.veclen;
991 case DT_elt_zero_int:
993 case DT_elt_zero_wide:
994 return d1->u.intval == d2->u.intval;
1001 /* If either has a predicate that we know something about, set
1002 things up so that D1 is the one that always has a known
1003 predicate. Then see if they have any codes in common. */
1005 if (d1->type == DT_pred || d2->type == DT_pred)
1007 if (d2->type == DT_pred)
1009 struct decision_test *tmp;
1010 tmp = d1, d1 = d2, d2 = tmp;
1013 /* If D2 tests a mode, see if it matches D1. */
1014 if (d1->u.pred.mode != VOIDmode)
1016 if (d2->type == DT_mode)
1018 if (d1->u.pred.mode != d2->u.mode
1019 /* The mode of an address_operand predicate is the
1020 mode of the memory, not the operand. It can only
1021 be used for testing the predicate, so we must
1023 && strcmp (d1->u.pred.name, "address_operand") != 0)
1026 /* Don't check two predicate modes here, because if both predicates
1027 accept CONST_INT, then both can still be true even if the modes
1028 are different. If they don't accept CONST_INT, there will be a
1029 separate DT_mode that will make maybe_both_true_1 return 0. */
1032 if (d1->u.pred.index >= 0)
1034 /* If D2 tests a code, see if it is in the list of valid
1035 codes for D1's predicate. */
1036 if (d2->type == DT_code)
1038 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1041 if (*c == d2->u.code)
1049 /* Otherwise see if the predicates have any codes in common. */
1050 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1052 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1055 while (*c1 != 0 && !common)
1057 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1058 while (*c2 != 0 && !common)
1060 common = (*c1 == *c2);
1075 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1076 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1079 maybe_both_true_1 (d1, d2)
1080 struct decision_test *d1, *d2;
1082 struct decision_test *t1, *t2;
1084 /* A match_operand with no predicate can match anything. Recognize
1085 this by the existance of a lone DT_accept_op test. */
1086 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1089 /* Eliminate pairs of tests while they can exactly match. */
1090 while (d1 && d2 && d1->type == d2->type)
1092 if (maybe_both_true_2 (d1, d2) == 0)
1094 d1 = d1->next, d2 = d2->next;
1097 /* After that, consider all pairs. */
1098 for (t1 = d1; t1 ; t1 = t1->next)
1099 for (t2 = d2; t2 ; t2 = t2->next)
1100 if (maybe_both_true_2 (t1, t2) == 0)
1106 /* Return 0 if we can prove that there is no RTL that can match both
1107 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1108 can match both or just that we couldn't prove there wasn't such an RTL).
1110 TOPLEVEL is non-zero if we are to only look at the top level and not
1111 recursively descend. */
1114 maybe_both_true (d1, d2, toplevel)
1115 struct decision *d1, *d2;
1118 struct decision *p1, *p2;
1121 /* Don't compare strings on the different positions in insn. Doing so
1122 is incorrect and results in false matches from constructs like
1124 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1125 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1127 [(set (match_operand:HI "register_operand" "r")
1128 (match_operand:HI "register_operand" "r"))]
1130 If we are presented with such, we are recursing through the remainder
1131 of a node's success nodes (from the loop at the end of this function).
1132 Skip forward until we come to a position that matches.
1134 Due to the way position strings are constructed, we know that iterating
1135 forward from the lexically lower position (e.g. "00") will run into
1136 the lexically higher position (e.g. "1") and not the other way around.
1137 This saves a bit of effort. */
1139 cmp = strcmp (d1->position, d2->position);
1145 /* If the d2->position was lexically lower, swap. */
1147 p1 = d1, d1 = d2, d2 = p1;
1149 if (d1->success.first == 0)
1151 for (p1 = d1->success.first; p1; p1 = p1->next)
1152 if (maybe_both_true (p1, d2, 0))
1158 /* Test the current level. */
1159 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1163 /* We can't prove that D1 and D2 cannot both be true. If we are only
1164 to check the top level, return 1. Otherwise, see if we can prove
1165 that all choices in both successors are mutually exclusive. If
1166 either does not have any successors, we can't prove they can't both
1169 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1172 for (p1 = d1->success.first; p1; p1 = p1->next)
1173 for (p2 = d2->success.first; p2; p2 = p2->next)
1174 if (maybe_both_true (p1, p2, 0))
1180 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1183 nodes_identical_1 (d1, d2)
1184 struct decision_test *d1, *d2;
1189 return d1->u.mode == d2->u.mode;
1192 return d1->u.code == d2->u.code;
1195 return (d1->u.pred.mode == d2->u.pred.mode
1196 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1199 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1202 return d1->u.veclen == d2->u.veclen;
1205 return d1->u.dup == d2->u.dup;
1207 case DT_elt_zero_int:
1208 case DT_elt_one_int:
1209 case DT_elt_zero_wide:
1210 return d1->u.intval == d2->u.intval;
1213 return d1->u.opno == d2->u.opno;
1215 case DT_accept_insn:
1216 /* Differences will be handled in merge_accept_insn. */
1224 /* True iff the two nodes are identical (on one level only). Due
1225 to the way these lists are constructed, we shouldn't have to
1226 consider different orderings on the tests. */
1229 nodes_identical (d1, d2)
1230 struct decision *d1, *d2;
1232 struct decision_test *t1, *t2;
1234 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1236 if (t1->type != t2->type)
1238 if (! nodes_identical_1 (t1, t2))
1242 /* For success, they should now both be null. */
1246 /* Check that their subnodes are at the same position, as any one set
1247 of sibling decisions must be at the same position. */
1248 if (d1->success.first
1249 && d2->success.first
1250 && strcmp (d1->success.first->position, d2->success.first->position))
1256 /* A subroutine of merge_trees; given two nodes that have been declared
1257 identical, cope with two insn accept states. If they differ in the
1258 number of clobbers, then the conflict was created by make_insn_sequence
1259 and we can drop the with-clobbers version on the floor. If both
1260 nodes have no additional clobbers, we have found an ambiguity in the
1261 source machine description. */
1264 merge_accept_insn (oldd, addd)
1265 struct decision *oldd, *addd;
1267 struct decision_test *old, *add;
1269 for (old = oldd->tests; old; old = old->next)
1270 if (old->type == DT_accept_insn)
1275 for (add = addd->tests; add; add = add->next)
1276 if (add->type == DT_accept_insn)
1281 /* If one node is for a normal insn and the second is for the base
1282 insn with clobbers stripped off, the second node should be ignored. */
1284 if (old->u.insn.num_clobbers_to_add == 0
1285 && add->u.insn.num_clobbers_to_add > 0)
1287 /* Nothing to do here. */
1289 else if (old->u.insn.num_clobbers_to_add > 0
1290 && add->u.insn.num_clobbers_to_add == 0)
1292 /* In this case, replace OLD with ADD. */
1293 old->u.insn = add->u.insn;
1297 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1298 get_insn_name (add->u.insn.code_number),
1299 get_insn_name (old->u.insn.code_number));
1300 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1301 get_insn_name (old->u.insn.code_number));
1306 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1309 merge_trees (oldh, addh)
1310 struct decision_head *oldh, *addh;
1312 struct decision *next, *add;
1314 if (addh->first == 0)
1316 if (oldh->first == 0)
1322 /* Trying to merge bits at different positions isn't possible. */
1323 if (strcmp (oldh->first->position, addh->first->position))
1326 for (add = addh->first; add ; add = next)
1328 struct decision *old, *insert_before = NULL;
1332 /* The semantics of pattern matching state that the tests are
1333 done in the order given in the MD file so that if an insn
1334 matches two patterns, the first one will be used. However,
1335 in practice, most, if not all, patterns are unambiguous so
1336 that their order is independent. In that case, we can merge
1337 identical tests and group all similar modes and codes together.
1339 Scan starting from the end of OLDH until we reach a point
1340 where we reach the head of the list or where we pass a
1341 pattern that could also be true if NEW is true. If we find
1342 an identical pattern, we can merge them. Also, record the
1343 last node that tests the same code and mode and the last one
1344 that tests just the same mode.
1346 If we have no match, place NEW after the closest match we found. */
1348 for (old = oldh->last; old; old = old->prev)
1350 if (nodes_identical (old, add))
1352 merge_accept_insn (old, add);
1353 merge_trees (&old->success, &add->success);
1357 if (maybe_both_true (old, add, 0))
1360 /* Insert the nodes in DT test type order, which is roughly
1361 how expensive/important the test is. Given that the tests
1362 are also ordered within the list, examining the first is
1364 if (add->tests->type < old->tests->type)
1365 insert_before = old;
1368 if (insert_before == NULL)
1371 add->prev = oldh->last;
1372 oldh->last->next = add;
1377 if ((add->prev = insert_before->prev) != NULL)
1378 add->prev->next = add;
1381 add->next = insert_before;
1382 insert_before->prev = add;
1389 /* Walk the tree looking for sub-nodes that perform common tests.
1390 Factor out the common test into a new node. This enables us
1391 (depending on the test type) to emit switch statements later. */
1395 struct decision_head *head;
1397 struct decision *first, *next;
1399 for (first = head->first; first && first->next; first = next)
1401 enum decision_type type;
1402 struct decision *new, *old_last;
1404 type = first->tests->type;
1407 /* Want at least two compatible sequential nodes. */
1408 if (next->tests->type != type)
1411 /* Don't want all node types, just those we can turn into
1412 switch statements. */
1415 && type != DT_veclen
1416 && type != DT_elt_zero_int
1417 && type != DT_elt_one_int
1418 && type != DT_elt_zero_wide)
1421 /* If we'd been performing more than one test, create a new node
1422 below our first test. */
1423 if (first->tests->next != NULL)
1425 new = new_decision (first->position, &first->success);
1426 new->tests = first->tests->next;
1427 first->tests->next = NULL;
1430 /* Crop the node tree off after our first test. */
1432 old_last = head->last;
1435 /* For each compatible test, adjust to perform only one test in
1436 the top level node, then merge the node back into the tree. */
1439 struct decision_head h;
1441 if (next->tests->next != NULL)
1443 new = new_decision (next->position, &next->success);
1444 new->tests = next->tests->next;
1445 next->tests->next = NULL;
1450 h.first = h.last = new;
1452 merge_trees (head, &h);
1454 while (next && next->tests->type == type);
1456 /* After we run out of compatible tests, graft the remaining nodes
1457 back onto the tree. */
1460 next->prev = head->last;
1461 head->last->next = next;
1462 head->last = old_last;
1467 for (first = head->first; first; first = first->next)
1468 factor_tests (&first->success);
1471 /* After factoring, try to simplify the tests on any one node.
1472 Tests that are useful for switch statements are recognizable
1473 by having only a single test on a node -- we'll be manipulating
1474 nodes with multiple tests:
1476 If we have mode tests or code tests that are redundant with
1477 predicates, remove them. */
1480 simplify_tests (head)
1481 struct decision_head *head;
1483 struct decision *tree;
1485 for (tree = head->first; tree; tree = tree->next)
1487 struct decision_test *a, *b;
1494 /* Find a predicate node. */
1495 while (b && b->type != DT_pred)
1499 /* Due to how these tests are constructed, we don't even need
1500 to check that the mode and code are compatible -- they were
1501 generated from the predicate in the first place. */
1502 while (a->type == DT_mode || a->type == DT_code)
1509 for (tree = head->first; tree; tree = tree->next)
1510 simplify_tests (&tree->success);
1513 /* Count the number of subnodes of HEAD. If the number is high enough,
1514 make the first node in HEAD start a separate subroutine in the C code
1515 that is generated. */
1518 break_out_subroutines (head, initial)
1519 struct decision_head *head;
1523 struct decision *sub;
1525 for (sub = head->first; sub; sub = sub->next)
1526 size += 1 + break_out_subroutines (&sub->success, 0);
1528 if (size > SUBROUTINE_THRESHOLD && ! initial)
1530 head->first->subroutine_number = ++next_subroutine_number;
1536 /* For each node p, find the next alternative that might be true
1540 find_afterward (head, real_afterward)
1541 struct decision_head *head;
1542 struct decision *real_afterward;
1544 struct decision *p, *q, *afterward;
1546 /* We can't propogate alternatives across subroutine boundaries.
1547 This is not incorrect, merely a minor optimization loss. */
1550 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1552 for ( ; p ; p = p->next)
1554 /* Find the next node that might be true if this one fails. */
1555 for (q = p->next; q ; q = q->next)
1556 if (maybe_both_true (p, q, 1))
1559 /* If we reached the end of the list without finding one,
1560 use the incoming afterward position. */
1569 for (p = head->first; p ; p = p->next)
1570 if (p->success.first)
1571 find_afterward (&p->success, p->afterward);
1573 /* When we are generating a subroutine, record the real afterward
1574 position in the first node where write_tree can find it, and we
1575 can do the right thing at the subroutine call site. */
1577 if (p->subroutine_number > 0)
1578 p->afterward = real_afterward;
1581 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1582 actions are necessary to move to NEWPOS. If we fail to move to the
1583 new state, branch to node AFTERWARD if non-zero, otherwise return.
1585 Failure to move to the new state can only occur if we are trying to
1586 match multiple insns and we try to step past the end of the stream. */
1589 change_state (oldpos, newpos, afterward, indent)
1592 struct decision *afterward;
1595 int odepth = strlen (oldpos);
1596 int ndepth = strlen (newpos);
1598 int old_has_insn, new_has_insn;
1600 /* Pop up as many levels as necessary. */
1601 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1604 /* Hunt for the last [A-Z] in both strings. */
1605 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1606 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1608 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1609 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1612 /* Make sure to reset the last_insn pointer when popping back up. */
1613 if (old_has_insn >= 0 && new_has_insn < 0)
1614 printf ("%slast_insn = insn;\n", indent);
1616 /* Go down to desired level. */
1617 while (depth < ndepth)
1619 /* It's a different insn from the first one. */
1620 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1622 /* We can only fail if we're moving down the tree. */
1623 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1625 printf ("%slast_insn = recog_next_insn (insn, %d);\n",
1626 indent, newpos[depth] - 'A');
1630 printf ("%stem = recog_next_insn (insn, %d);\n",
1631 indent, newpos[depth] - 'A');
1632 printf ("%sif (tem == NULL_RTX)\n", indent);
1634 printf ("%s goto L%d;\n", indent, afterward->number);
1636 printf ("%s goto ret0;\n", indent);
1637 printf ("%slast_insn = tem;\n", indent);
1639 printf ("%sx%d = PATTERN (last_insn);\n", indent, depth + 1);
1641 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1642 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1643 indent, depth + 1, depth, newpos[depth] - 'a');
1645 printf ("%sx%d = XEXP (x%d, %c);\n",
1646 indent, depth + 1, depth, newpos[depth]);
1651 /* Print the enumerator constant for CODE -- the upcase version of
1658 register const char *p;
1659 for (p = GET_RTX_NAME (code); *p; p++)
1660 putchar (TOUPPER (*p));
1663 /* Emit code to cross an afterward link -- change state and branch. */
1666 write_afterward (start, afterward, indent)
1667 struct decision *start;
1668 struct decision *afterward;
1671 if (!afterward || start->subroutine_number > 0)
1672 printf("%sgoto ret0;\n", indent);
1675 change_state (start->position, afterward->position, NULL, indent);
1676 printf ("%sgoto L%d;\n", indent, afterward->number);
1680 /* Emit a switch statement, if possible, for an initial sequence of
1681 nodes at START. Return the first node yet untested. */
1683 static struct decision *
1684 write_switch (start, depth)
1685 struct decision *start;
1688 struct decision *p = start;
1689 enum decision_type type = p->tests->type;
1691 /* If we have two or more nodes in sequence that test the same one
1692 thing, we may be able to use a switch statement. */
1696 || p->next->tests->type != type
1697 || p->next->tests->next)
1700 /* DT_code is special in that we can do interesting things with
1701 known predicates at the same time. */
1702 if (type == DT_code)
1704 char codemap[NUM_RTX_CODE];
1705 struct decision *ret;
1708 memset (codemap, 0, sizeof(codemap));
1710 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1711 code = p->tests->u.code;
1716 printf (":\n goto L%d;\n", p->success.first->number);
1717 p->success.first->need_label = 1;
1724 && p->tests->type == DT_code
1725 && ! codemap[code = p->tests->u.code]);
1727 /* If P is testing a predicate that we know about and we haven't
1728 seen any of the codes that are valid for the predicate, we can
1729 write a series of "case" statement, one for each possible code.
1730 Since we are already in a switch, these redundant tests are very
1731 cheap and will reduce the number of predicates called. */
1733 /* Note that while we write out cases for these predicates here,
1734 we don't actually write the test here, as it gets kinda messy.
1735 It is trivial to leave this to later by telling our caller that
1736 we only processed the CODE tests. */
1739 while (p && p->tests->type == DT_pred
1740 && p->tests->u.pred.index >= 0)
1744 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1745 if (codemap[(int) *c] != 0)
1748 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1753 codemap[(int) *c] = 1;
1756 printf (" goto L%d;\n", p->number);
1762 /* Make the default case skip the predicates we managed to match. */
1764 printf (" default:\n");
1769 printf (" goto L%d;\n", p->number);
1773 write_afterward (start, start->afterward, " ");
1776 printf (" break;\n");
1781 else if (type == DT_mode
1782 || type == DT_veclen
1783 || type == DT_elt_zero_int
1784 || type == DT_elt_one_int
1785 || type == DT_elt_zero_wide)
1787 printf (" switch (");
1791 printf ("GET_MODE (x%d)", depth);
1794 printf ("XVECLEN (x%d, 0)", depth);
1796 case DT_elt_zero_int:
1797 printf ("XINT (x%d, 0)", depth);
1799 case DT_elt_one_int:
1800 printf ("XINT (x%d, 1)", depth);
1802 case DT_elt_zero_wide:
1803 /* Convert result of XWINT to int for portability since some C
1804 compilers won't do it and some will. */
1805 printf ("(int) XWINT (x%d, 0)", depth);
1818 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1821 printf ("%d", p->tests->u.veclen);
1823 case DT_elt_zero_int:
1824 case DT_elt_one_int:
1825 case DT_elt_zero_wide:
1826 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1831 printf (":\n goto L%d;\n", p->success.first->number);
1832 p->success.first->need_label = 1;
1836 while (p && p->tests->type == type && !p->tests->next);
1838 printf (" default:\n break;\n }\n");
1844 /* None of the other tests are ameanable. */
1849 /* Emit code for one test. */
1852 write_cond (p, depth, subroutine_type)
1853 struct decision_test *p;
1855 enum routine_type subroutine_type;
1860 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1864 printf ("GET_CODE (x%d) == ", depth);
1865 print_code (p->u.code);
1869 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1872 case DT_elt_zero_int:
1873 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1876 case DT_elt_one_int:
1877 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1880 case DT_elt_zero_wide:
1881 printf ("XWINT (x%d, 0) == ", depth);
1882 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1886 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1890 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1891 GET_MODE_NAME (p->u.pred.mode));
1895 printf ("(%s)", p->u.c_test);
1898 case DT_accept_insn:
1899 switch (subroutine_type)
1902 if (p->u.insn.num_clobbers_to_add == 0)
1904 printf ("pnum_clobbers != NULL");
1917 /* Emit code for one action. The previous tests have succeeded;
1918 TEST is the last of the chain. In the normal case we simply
1919 perform a state change. For the `accept' tests we must do more work. */
1922 write_action (test, depth, uncond, success, subroutine_type)
1923 struct decision_test *test;
1925 struct decision *success;
1926 enum routine_type subroutine_type;
1933 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1935 fputs (" {\n", stdout);
1942 if (test->type == DT_accept_op)
1944 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1946 /* Only allow DT_accept_insn to follow. */
1950 if (test->type != DT_accept_insn)
1955 /* Sanity check that we're now at the end of the list of tests. */
1959 if (test->type == DT_accept_insn)
1961 switch (subroutine_type)
1964 if (test->u.insn.num_clobbers_to_add != 0)
1965 printf ("%s*pnum_clobbers = %d;\n",
1966 indent, test->u.insn.num_clobbers_to_add);
1967 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
1971 printf ("%sreturn gen_split_%d (operands);\n",
1972 indent, test->u.insn.code_number);
1976 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1977 indent, test->u.insn.code_number);
1978 printf ("%sif (tem != 0)\n%s goto ret1;\n", indent, indent);
1987 printf("%sgoto L%d;\n", indent, success->number);
1988 success->need_label = 1;
1992 fputs (" }\n", stdout);
1995 /* Return 1 if the test is always true and has no fallthru path. Return -1
1996 if the test does have a fallthru path, but requires that the condition be
1997 terminated. Otherwise return 0 for a normal test. */
1998 /* ??? is_unconditional is a stupid name for a tri-state function. */
2001 is_unconditional (t, subroutine_type)
2002 struct decision_test *t;
2003 enum routine_type subroutine_type;
2005 if (t->type == DT_accept_op)
2008 if (t->type == DT_accept_insn)
2010 switch (subroutine_type)
2013 return (t->u.insn.num_clobbers_to_add == 0);
2026 /* Emit code for one node -- the conditional and the accompanying action.
2027 Return true if there is no fallthru path. */
2030 write_node (p, depth, subroutine_type)
2033 enum routine_type subroutine_type;
2035 struct decision_test *test, *last_test;
2038 last_test = test = p->tests;
2039 uncond = is_unconditional (test, subroutine_type);
2043 write_cond (test, depth, subroutine_type);
2045 while ((test = test->next) != NULL)
2050 uncond2 = is_unconditional (test, subroutine_type);
2055 write_cond (test, depth, subroutine_type);
2061 write_action (last_test, depth, uncond, p->success.first, subroutine_type);
2066 /* Emit code for all of the sibling nodes of HEAD. */
2069 write_tree_1 (head, depth, subroutine_type)
2070 struct decision_head *head;
2072 enum routine_type subroutine_type;
2074 struct decision *p, *next;
2077 for (p = head->first; p ; p = next)
2079 /* The label for the first element was printed in write_tree. */
2080 if (p != head->first && p->need_label)
2081 OUTPUT_LABEL (" ", p->number);
2083 /* Attempt to write a switch statement for a whole sequence. */
2084 next = write_switch (p, depth);
2089 /* Failed -- fall back and write one node. */
2090 uncond = write_node (p, depth, subroutine_type);
2095 /* Finished with this chain. Close a fallthru path by branching
2096 to the afterward node. */
2098 write_afterward (head->last, head->last->afterward, " ");
2101 /* Write out the decision tree starting at HEAD. PREVPOS is the
2102 position at the node that branched to this node. */
2105 write_tree (head, prevpos, type, initial)
2106 struct decision_head *head;
2107 const char *prevpos;
2108 enum routine_type type;
2111 register struct decision *p = head->first;
2115 OUTPUT_LABEL (" ", p->number);
2117 if (! initial && p->subroutine_number > 0)
2119 static const char * const name_prefix[] = {
2120 "recog", "split", "peephole2"
2123 static const char * const call_suffix[] = {
2124 ", pnum_clobbers", "", ", _plast_insn"
2127 /* This node has been broken out into a separate subroutine.
2128 Call it, test the result, and branch accordingly. */
2132 printf (" tem = %s_%d (x0, insn%s);\n",
2133 name_prefix[type], p->subroutine_number, call_suffix[type]);
2134 if (IS_SPLIT (type))
2135 printf (" if (tem != 0)\n return tem;\n");
2137 printf (" if (tem >= 0)\n return tem;\n");
2139 change_state (p->position, p->afterward->position, NULL, " ");
2140 printf (" goto L%d;\n", p->afterward->number);
2144 printf (" return %s_%d (x0, insn%s);\n",
2145 name_prefix[type], p->subroutine_number, call_suffix[type]);
2150 int depth = strlen (p->position);
2152 change_state (prevpos, p->position, head->last->afterward, " ");
2153 write_tree_1 (head, depth, type);
2155 for (p = head->first; p; p = p->next)
2156 if (p->success.first)
2157 write_tree (&p->success, p->position, type, 0);
2161 /* Write out a subroutine of type TYPE to do comparisons starting at
2165 write_subroutine (head, type)
2166 struct decision_head *head;
2167 enum routine_type type;
2169 int subfunction = head->first ? head->first->subroutine_number : 0;
2174 s_or_e = subfunction ? "static " : "";
2177 sprintf (extension, "_%d", subfunction);
2178 else if (type == RECOG)
2179 extension[0] = '\0';
2181 strcpy (extension, "_insns");
2186 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2188 recog%s (x0, insn, pnum_clobbers)\n\
2190 rtx insn ATTRIBUTE_UNUSED;\n\
2191 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2194 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2196 split%s (x0, insn)\n\
2198 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2201 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, rtx *));\n", s_or_e, extension);
2203 peephole2%s (x0, insn, _plast_insn)\n\
2205 rtx insn ATTRIBUTE_UNUSED;\n\
2206 rtx *_plast_insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2210 printf ("{\n register rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2211 for (i = 1; i <= max_depth; i++)
2212 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
2214 if (type == PEEPHOLE2)
2215 printf (" register rtx last_insn = insn;\n");
2216 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2219 write_tree (head, "", type, 1);
2221 printf (" goto ret0;\n");
2223 if (type == PEEPHOLE2)
2224 printf (" ret1:\n *_plast_insn = last_insn;\n return tem;\n");
2225 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2228 /* In break_out_subroutines, we discovered the boundaries for the
2229 subroutines, but did not write them out. Do so now. */
2232 write_subroutines (head, type)
2233 struct decision_head *head;
2234 enum routine_type type;
2238 for (p = head->first; p ; p = p->next)
2239 if (p->success.first)
2240 write_subroutines (&p->success, type);
2242 if (head->first->subroutine_number > 0)
2243 write_subroutine (head, type);
2246 /* Begin the output file. */
2252 /* Generated automatically by the program `genrecog' from the target\n\
2253 machine description file. */\n\
2255 #include \"config.h\"\n\
2256 #include \"system.h\"\n\
2257 #include \"rtl.h\"\n\
2258 #include \"tm_p.h\"\n\
2259 #include \"function.h\"\n\
2260 #include \"insn-config.h\"\n\
2261 #include \"recog.h\"\n\
2262 #include \"real.h\"\n\
2263 #include \"output.h\"\n\
2264 #include \"flags.h\"\n\
2265 #include \"hard-reg-set.h\"\n\
2266 #include \"resource.h\"\n\
2270 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2271 X0 is a valid instruction.\n\
2273 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2274 returns a nonnegative number which is the insn code number for the\n\
2275 pattern that matched. This is the same as the order in the machine\n\
2276 description of the entry that matched. This number can be used as an\n\
2277 index into `insn_data' and other tables.\n\
2279 The third argument to recog is an optional pointer to an int. If\n\
2280 present, recog will accept a pattern if it matches except for missing\n\
2281 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2282 the optional pointer will be set to the number of CLOBBERs that need\n\
2283 to be added (it should be initialized to zero by the caller). If it\n\
2284 is set nonzero, the caller should allocate a PARALLEL of the\n\
2285 appropriate size, copy the initial entries, and call add_clobbers\n\
2286 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2290 The function split_insns returns 0 if the rtl could not\n\
2291 be split or the split rtl in a SEQUENCE if it can be.\n\
2293 The function peephole2_insns returns 0 if the rtl could not\n\
2294 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2295 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2300 /* Construct and return a sequence of decisions
2301 that will recognize INSN.
2303 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2305 static struct decision_head
2306 make_insn_sequence (insn, type)
2308 enum routine_type type;
2311 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2312 struct decision *last;
2313 struct decision_test *test, **place;
2314 struct decision_head head;
2315 char *c_test_pos = "";
2317 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2319 if (type == PEEPHOLE2)
2323 /* peephole2 gets special treatment:
2324 - X always gets an outer parallel even if it's only one entry
2325 - we remove all traces of outer-level match_scratch and match_dup
2326 expressions here. */
2327 x = rtx_alloc (PARALLEL);
2328 PUT_MODE (x, VOIDmode);
2329 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2330 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2332 rtx tmp = XVECEXP (insn, 0, i);
2333 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2335 XVECEXP (x, 0, j) = tmp;
2341 c_test_pos = alloca (2);
2342 c_test_pos[0] = 'A' + j - 1;
2343 c_test_pos[1] = '\0';
2345 else if (XVECLEN (insn, type == RECOG) == 1)
2346 x = XVECEXP (insn, type == RECOG, 0);
2349 x = rtx_alloc (PARALLEL);
2350 XVEC (x, 0) = XVEC (insn, type == RECOG);
2351 PUT_MODE (x, VOIDmode);
2354 validate_pattern (x, insn, NULL_RTX);
2356 memset(&head, 0, sizeof(head));
2357 last = add_to_sequence (x, &head, "", type, 1);
2359 /* Find the end of the test chain on the last node. */
2360 for (test = last->tests; test->next; test = test->next)
2362 place = &test->next;
2366 /* Need a new node if we have another test to add. */
2367 if (test->type == DT_accept_op)
2369 last = new_decision (c_test_pos, &last->success);
2370 place = &last->tests;
2372 test = new_decision_test (DT_c_test, &place);
2373 test->u.c_test = c_test;
2376 test = new_decision_test (DT_accept_insn, &place);
2377 test->u.insn.code_number = next_insn_code;
2378 test->u.insn.lineno = pattern_lineno;
2379 test->u.insn.num_clobbers_to_add = 0;
2384 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2385 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2386 If so, set up to recognize the pattern without these CLOBBERs. */
2388 if (GET_CODE (x) == PARALLEL)
2392 /* Find the last non-clobber in the parallel. */
2393 for (i = XVECLEN (x, 0); i > 0; i--)
2395 rtx y = XVECEXP (x, 0, i - 1);
2396 if (GET_CODE (y) != CLOBBER
2397 || (GET_CODE (XEXP (y, 0)) != REG
2398 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2402 if (i != XVECLEN (x, 0))
2405 struct decision_head clobber_head;
2407 /* Build a similar insn without the clobbers. */
2409 new = XVECEXP (x, 0, 0);
2414 new = rtx_alloc (PARALLEL);
2415 XVEC (new, 0) = rtvec_alloc (i);
2416 for (j = i - 1; j >= 0; j--)
2417 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2421 memset (&clobber_head, 0, sizeof(clobber_head));
2422 last = add_to_sequence (new, &clobber_head, "", type, 1);
2424 /* Find the end of the test chain on the last node. */
2425 for (test = last->tests; test->next; test = test->next)
2428 /* We definitely have a new test to add -- create a new
2430 place = &test->next;
2431 if (test->type == DT_accept_op)
2433 last = new_decision ("", &last->success);
2434 place = &last->tests;
2439 test = new_decision_test (DT_c_test, &place);
2440 test->u.c_test = c_test;
2443 test = new_decision_test (DT_accept_insn, &place);
2444 test->u.insn.code_number = next_insn_code;
2445 test->u.insn.lineno = pattern_lineno;
2446 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2448 merge_trees (&head, &clobber_head);
2454 /* Define the subroutine we will call below and emit in genemit. */
2455 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2459 /* Define the subroutine we will call below and emit in genemit. */
2460 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2470 process_tree (head, subroutine_type)
2471 struct decision_head *head;
2472 enum routine_type subroutine_type;
2474 if (head->first == NULL)
2476 /* We can elide peephole2_insns, but not recog or split_insns. */
2477 if (subroutine_type == PEEPHOLE2)
2482 factor_tests (head);
2484 next_subroutine_number = 0;
2485 break_out_subroutines (head, 1);
2486 find_afterward (head, NULL);
2488 /* We run this after find_afterward, because find_afterward needs
2489 the redundant DT_mode tests on predicates to determine whether
2490 two tests can both be true or not. */
2491 simplify_tests(head);
2493 write_subroutines (head, subroutine_type);
2496 write_subroutine (head, subroutine_type);
2499 extern int main PARAMS ((int, char **));
2507 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2511 progname = "genrecog";
2512 obstack_init (rtl_obstack);
2514 memset (&recog_tree, 0, sizeof recog_tree);
2515 memset (&split_tree, 0, sizeof split_tree);
2516 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2519 fatal ("No input file name.");
2521 infile = fopen (argv[1], "r");
2525 return FATAL_EXIT_CODE;
2527 read_rtx_filename = argv[1];
2534 /* Read the machine description. */
2538 c = read_skip_spaces (infile);
2542 pattern_lineno = read_rtx_lineno;
2544 desc = read_rtx (infile);
2545 if (GET_CODE (desc) == DEFINE_INSN)
2547 h = make_insn_sequence (desc, RECOG);
2548 merge_trees (&recog_tree, &h);
2550 else if (GET_CODE (desc) == DEFINE_SPLIT)
2552 h = make_insn_sequence (desc, SPLIT);
2553 merge_trees (&split_tree, &h);
2555 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2557 h = make_insn_sequence (desc, PEEPHOLE2);
2558 merge_trees (&peephole2_tree, &h);
2561 if (GET_CODE (desc) == DEFINE_PEEPHOLE
2562 || GET_CODE (desc) == DEFINE_EXPAND)
2568 return FATAL_EXIT_CODE;
2572 process_tree (&recog_tree, RECOG);
2573 process_tree (&split_tree, SPLIT);
2574 process_tree (&peephole2_tree, PEEPHOLE2);
2577 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2580 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2582 get_insn_name (code)
2585 if (code < insn_name_ptr_size)
2586 return insn_name_ptr[code];
2592 record_insn_name (code, name)
2596 static const char *last_real_name = "insn";
2597 static int last_real_code = 0;
2600 if (insn_name_ptr_size <= code)
2603 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2605 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2606 memset (insn_name_ptr + insn_name_ptr_size, 0,
2607 sizeof(char *) * (new_size - insn_name_ptr_size));
2608 insn_name_ptr_size = new_size;
2611 if (!name || name[0] == '\0')
2613 new = xmalloc (strlen (last_real_name) + 10);
2614 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2618 last_real_name = new = xstrdup (name);
2619 last_real_code = code;
2622 insn_name_ptr[code] = new;
2629 register size_t len = strlen (input) + 1;
2630 register char *output = xmalloc (len);
2631 memcpy (output, input, len);
2636 xrealloc (old, size)
2642 ptr = (PTR) realloc (old, size);
2644 ptr = (PTR) malloc (size);
2646 fatal ("virtual memory exhausted");
2654 register PTR val = (PTR) malloc (size);
2657 fatal ("virtual memory exhausted");
2662 debug_decision_2 (test)
2663 struct decision_test *test;
2668 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2671 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2674 fprintf (stderr, "veclen=%d", test->u.veclen);
2676 case DT_elt_zero_int:
2677 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2679 case DT_elt_one_int:
2680 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2682 case DT_elt_zero_wide:
2683 fprintf (stderr, "elt0_w=");
2684 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2687 fprintf (stderr, "dup=%d", test->u.dup);
2690 fprintf (stderr, "pred=(%s,%s)",
2691 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2696 strncpy (sub, test->u.c_test, sizeof(sub));
2697 memcpy (sub+16, "...", 4);
2698 fprintf (stderr, "c_test=\"%s\"", sub);
2702 fprintf (stderr, "A_op=%d", test->u.opno);
2704 case DT_accept_insn:
2705 fprintf (stderr, "A_insn=(%d,%d)",
2706 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2715 debug_decision_1 (d, indent)
2720 struct decision_test *test;
2724 for (i = 0; i < indent; ++i)
2726 fputs ("(nil)\n", stderr);
2730 for (i = 0; i < indent; ++i)
2737 debug_decision_2 (test);
2738 while ((test = test->next) != NULL)
2740 fputs (" + ", stderr);
2741 debug_decision_2 (test);
2744 fprintf (stderr, "} %d n %d a %d\n", d->number,
2745 (d->next ? d->next->number : -1),
2746 (d->afterward ? d->afterward->number : -1));
2750 debug_decision_0 (d, indent, maxdepth)
2752 int indent, maxdepth;
2761 for (i = 0; i < indent; ++i)
2763 fputs ("(nil)\n", stderr);
2767 debug_decision_1 (d, indent);
2768 for (n = d->success.first; n ; n = n->next)
2769 debug_decision_0 (n, indent + 2, maxdepth - 1);
2776 debug_decision_0 (d, 0, 1000000);
2780 debug_decision_list (d)
2785 debug_decision_0 (d, 0, 0);