1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* This program is used to produce insn-recog.c, which contains a
24 function called `recog' plus its subroutines. These functions
25 contain a decision tree that recognizes whether an rtx, the
26 argument given to recog, is a valid instruction.
28 recog returns -1 if the rtx is not valid. If the rtx is valid,
29 recog returns a nonnegative number which is the insn code number
30 for the pattern that matched. This is the same as the order in the
31 machine description of the entry that matched. This number can be
32 used as an index into various insn_* tables, such as insn_template,
33 insn_outfun, and insn_n_operands (found in insn-output.c).
35 The third argument to recog is an optional pointer to an int. If
36 present, recog will accept a pattern if it matches except for
37 missing CLOBBER expressions at the end. In that case, the value
38 pointed to by the optional pointer will be set to the number of
39 CLOBBERs that need to be added (it should be initialized to zero by
40 the caller). If it is set nonzero, the caller should allocate a
41 PARALLEL of the appropriate size, copy the initial entries, and
42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
44 This program also generates the function `split_insns', which
45 returns 0 if the rtl could not be split, or it returns the split
48 This program also generates the function `peephole2_insns', which
49 returns 0 if the rtl could not be matched. If there was a match,
50 the new rtl is returned in an INSN list, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
55 #include "coretypes.h"
59 #include "gensupport.h"
61 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
62 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
64 /* Holds an array of names indexed by insn_code_number. */
65 static char **insn_name_ptr = 0;
66 static int insn_name_ptr_size = 0;
68 /* A listhead of decision trees. The alternatives to a node are kept
69 in a doubly-linked list so we can easily add nodes to the proper
70 place when merging. */
74 struct decision *first;
75 struct decision *last;
78 /* A single test. The two accept types aren't tests per-se, but
79 their equality (or lack thereof) does affect tree merging so
80 it is convenient to keep them here. */
84 /* A linked list through the tests attached to a node. */
85 struct decision_test *next;
87 /* These types are roughly in the order in which we'd like to test them. */
90 DT_mode, DT_code, DT_veclen,
91 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
93 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
94 DT_accept_op, DT_accept_insn
99 enum machine_mode mode; /* Machine mode of node. */
100 RTX_CODE code; /* Code to test. */
104 const char *name; /* Predicate to call. */
105 const struct pred_data *data;
106 /* Optimization hints for this predicate. */
107 enum machine_mode mode; /* Machine mode for node. */
110 const char *c_test; /* Additional test to perform. */
111 int veclen; /* Length of vector. */
112 int dup; /* Number of operand to compare against. */
113 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
114 int opno; /* Operand number matched. */
117 int code_number; /* Insn number matched. */
118 int lineno; /* Line number of the insn. */
119 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
124 /* Data structure for decision tree for recognizing legitimate insns. */
128 struct decision_head success; /* Nodes to test on success. */
129 struct decision *next; /* Node to test on failure. */
130 struct decision *prev; /* Node whose failure tests us. */
131 struct decision *afterward; /* Node to test on success,
132 but failure of successor nodes. */
134 const char *position; /* String denoting position in pattern. */
136 struct decision_test *tests; /* The tests for this node. */
138 int number; /* Node number, used for labels */
139 int subroutine_number; /* Number of subroutine this node starts */
140 int need_label; /* Label needs to be output. */
143 #define SUBROUTINE_THRESHOLD 100
145 static int next_subroutine_number;
147 /* We can write three types of subroutines: One for insn recognition,
148 one to split insns, and one for peephole-type optimizations. This
149 defines which type is being written. */
152 RECOG, SPLIT, PEEPHOLE2
155 #define IS_SPLIT(X) ((X) != RECOG)
157 /* Next available node number for tree nodes. */
159 static int next_number;
161 /* Next number to use as an insn_code. */
163 static int next_insn_code;
165 /* Record the highest depth we ever have so we know how many variables to
166 allocate in each subroutine we make. */
168 static int max_depth;
170 /* The line number of the start of the pattern currently being processed. */
171 static int pattern_lineno;
173 /* Count of errors. */
174 static int error_count;
176 /* Predicate handling.
178 We construct from the machine description a table mapping each
179 predicate to a list of the rtl codes it can possibly match. The
180 function 'maybe_both_true' uses it to deduce that there are no
181 expressions that can be matches by certain pairs of tree nodes.
182 Also, if a predicate can match only one code, we can hardwire that
183 code into the node testing the predicate.
185 Some predicates are flagged as special. validate_pattern will not
186 warn about modeless match_operand expressions if they have a
187 special predicate. Predicates that allow only constants are also
188 treated as special, for this purpose.
190 validate_pattern will warn about predicates that allow non-lvalues
191 when they appear in destination operands.
193 Calculating the set of rtx codes that can possibly be accepted by a
194 predicate expression EXP requires a three-state logic: any given
195 subexpression may definitively accept a code C (Y), definitively
196 reject a code C (N), or may have an indeterminate effect (I). N
197 and I is N; Y or I is Y; Y and I, N or I are both I. Here are full
208 We represent Y with 1, N with 0, I with 2. If any code is left in
209 an I state by the complete expression, we must assume that that
210 code can be accepted. */
216 #define TRISTATE_AND(a,b) \
217 ((a) == I ? ((b) == N ? N : I) : \
218 (b) == I ? ((a) == N ? N : I) : \
221 #define TRISTATE_OR(a,b) \
222 ((a) == I ? ((b) == Y ? Y : I) : \
223 (b) == I ? ((a) == Y ? Y : I) : \
226 #define TRISTATE_NOT(a) \
227 ((a) == I ? I : !(a))
229 /* Recursively calculate the set of rtx codes accepted by the
230 predicate expression EXP, writing the result to CODES. */
232 compute_predicate_codes (rtx exp, char codes[NUM_RTX_CODE])
234 char op0_codes[NUM_RTX_CODE];
235 char op1_codes[NUM_RTX_CODE];
236 char op2_codes[NUM_RTX_CODE];
239 switch (GET_CODE (exp))
242 compute_predicate_codes (XEXP (exp, 0), op0_codes);
243 compute_predicate_codes (XEXP (exp, 1), op1_codes);
244 for (i = 0; i < NUM_RTX_CODE; i++)
245 codes[i] = TRISTATE_AND (op0_codes[i], op1_codes[i]);
249 compute_predicate_codes (XEXP (exp, 0), op0_codes);
250 compute_predicate_codes (XEXP (exp, 1), op1_codes);
251 for (i = 0; i < NUM_RTX_CODE; i++)
252 codes[i] = TRISTATE_OR (op0_codes[i], op1_codes[i]);
255 compute_predicate_codes (XEXP (exp, 0), op0_codes);
256 for (i = 0; i < NUM_RTX_CODE; i++)
257 codes[i] = TRISTATE_NOT (codes[i]);
261 /* a ? b : c accepts the same codes as (a & b) | (!a & c). */
262 compute_predicate_codes (XEXP (exp, 0), op0_codes);
263 compute_predicate_codes (XEXP (exp, 1), op1_codes);
264 compute_predicate_codes (XEXP (exp, 2), op2_codes);
265 for (i = 0; i < NUM_RTX_CODE; i++)
266 codes[i] = TRISTATE_OR (TRISTATE_AND (op0_codes[i], op1_codes[i]),
267 TRISTATE_AND (TRISTATE_NOT (op0_codes[i]),
272 /* MATCH_CODE allows a specified list of codes. */
273 memset (codes, N, NUM_RTX_CODE);
275 const char *next_code = XSTR (exp, 0);
278 if (*next_code == '\0')
280 message_with_line (pattern_lineno, "empty match_code expression");
285 while ((code = scan_comma_elt (&next_code)) != 0)
287 size_t n = next_code - code;
289 for (i = 0; i < NUM_RTX_CODE; i++)
290 if (!strncmp (code, GET_RTX_NAME (i), n)
291 && GET_RTX_NAME (i)[n] == '\0')
301 /* MATCH_OPERAND disallows the set of codes that the named predicate
302 disallows, and is indeterminate for the codes that it does allow. */
304 struct pred_data *p = lookup_predicate (XSTR (exp, 1));
307 message_with_line (pattern_lineno,
308 "reference to unknown predicate '%s'",
313 for (i = 0; i < NUM_RTX_CODE; i++)
314 codes[i] = p->codes[i] ? I : N;
320 /* (match_test WHATEVER) is completely indeterminate. */
321 memset (codes, I, NUM_RTX_CODE);
325 message_with_line (pattern_lineno,
326 "'%s' cannot be used in a define_predicate expression",
327 GET_RTX_NAME (GET_CODE (exp)));
329 memset (codes, I, NUM_RTX_CODE);
338 /* Process a define_predicate expression: compute the set of predicates
339 that can be matched, and record this as a known predicate. */
341 process_define_predicate (rtx desc)
343 struct pred_data *pred = xcalloc (sizeof (struct pred_data), 1);
344 char codes[NUM_RTX_CODE];
345 bool seen_one = false;
348 pred->name = XSTR (desc, 0);
349 if (GET_CODE (desc) == DEFINE_SPECIAL_PREDICATE)
352 compute_predicate_codes (XEXP (desc, 1), codes);
354 for (i = 0; i < NUM_RTX_CODE; i++)
357 pred->codes[i] = true;
358 if (GET_RTX_CLASS (i) != RTX_CONST_OBJ)
359 pred->allows_non_const = true;
365 && i != STRICT_LOW_PART)
366 pred->allows_non_lvalue = true;
369 pred->singleton = UNKNOWN;
376 add_predicate (pred);
383 static struct decision *new_decision
384 (const char *, struct decision_head *);
385 static struct decision_test *new_decision_test
386 (enum decision_type, struct decision_test ***);
387 static rtx find_operand
389 static rtx find_matching_operand
391 static void validate_pattern
392 (rtx, rtx, rtx, int);
393 static struct decision *add_to_sequence
394 (rtx, struct decision_head *, const char *, enum routine_type, int);
396 static int maybe_both_true_2
397 (struct decision_test *, struct decision_test *);
398 static int maybe_both_true_1
399 (struct decision_test *, struct decision_test *);
400 static int maybe_both_true
401 (struct decision *, struct decision *, int);
403 static int nodes_identical_1
404 (struct decision_test *, struct decision_test *);
405 static int nodes_identical
406 (struct decision *, struct decision *);
407 static void merge_accept_insn
408 (struct decision *, struct decision *);
409 static void merge_trees
410 (struct decision_head *, struct decision_head *);
412 static void factor_tests
413 (struct decision_head *);
414 static void simplify_tests
415 (struct decision_head *);
416 static int break_out_subroutines
417 (struct decision_head *, int);
418 static void find_afterward
419 (struct decision_head *, struct decision *);
421 static void change_state
422 (const char *, const char *, struct decision *, const char *);
423 static void print_code
425 static void write_afterward
426 (struct decision *, struct decision *, const char *);
427 static struct decision *write_switch
428 (struct decision *, int);
429 static void write_cond
430 (struct decision_test *, int, enum routine_type);
431 static void write_action
432 (struct decision *, struct decision_test *, int, int,
433 struct decision *, enum routine_type);
434 static int is_unconditional
435 (struct decision_test *, enum routine_type);
436 static int write_node
437 (struct decision *, int, enum routine_type);
438 static void write_tree_1
439 (struct decision_head *, int, enum routine_type);
440 static void write_tree
441 (struct decision_head *, const char *, enum routine_type, int);
442 static void write_subroutine
443 (struct decision_head *, enum routine_type);
444 static void write_subroutines
445 (struct decision_head *, enum routine_type);
446 static void write_header
449 static struct decision_head make_insn_sequence
450 (rtx, enum routine_type);
451 static void process_tree
452 (struct decision_head *, enum routine_type);
454 static void record_insn_name
457 static void debug_decision_0
458 (struct decision *, int, int);
459 static void debug_decision_1
460 (struct decision *, int);
461 static void debug_decision_2
462 (struct decision_test *);
463 extern void debug_decision
465 extern void debug_decision_list
468 /* Create a new node in sequence after LAST. */
470 static struct decision *
471 new_decision (const char *position, struct decision_head *last)
473 struct decision *new = xcalloc (1, sizeof (struct decision));
475 new->success = *last;
476 new->position = xstrdup (position);
477 new->number = next_number++;
479 last->first = last->last = new;
483 /* Create a new test and link it in at PLACE. */
485 static struct decision_test *
486 new_decision_test (enum decision_type type, struct decision_test ***pplace)
488 struct decision_test **place = *pplace;
489 struct decision_test *test;
491 test = xmalloc (sizeof (*test));
502 /* Search for and return operand N, stop when reaching node STOP. */
505 find_operand (rtx pattern, int n, rtx stop)
515 code = GET_CODE (pattern);
516 if ((code == MATCH_SCRATCH
517 || code == MATCH_OPERAND
518 || code == MATCH_OPERATOR
519 || code == MATCH_PARALLEL)
520 && XINT (pattern, 0) == n)
523 fmt = GET_RTX_FORMAT (code);
524 len = GET_RTX_LENGTH (code);
525 for (i = 0; i < len; i++)
530 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
535 if (! XVEC (pattern, i))
540 for (j = 0; j < XVECLEN (pattern, i); j++)
541 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
546 case 'i': case 'w': case '0': case 's':
557 /* Search for and return operand M, such that it has a matching
558 constraint for operand N. */
561 find_matching_operand (rtx pattern, int n)
568 code = GET_CODE (pattern);
569 if (code == MATCH_OPERAND
570 && (XSTR (pattern, 2)[0] == '0' + n
571 || (XSTR (pattern, 2)[0] == '%'
572 && XSTR (pattern, 2)[1] == '0' + n)))
575 fmt = GET_RTX_FORMAT (code);
576 len = GET_RTX_LENGTH (code);
577 for (i = 0; i < len; i++)
582 if ((r = find_matching_operand (XEXP (pattern, i), n)))
587 if (! XVEC (pattern, i))
592 for (j = 0; j < XVECLEN (pattern, i); j++)
593 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
597 case 'i': case 'w': case '0': case 's':
609 /* Check for various errors in patterns. SET is nonnull for a destination,
610 and is the complete set pattern. SET_CODE is '=' for normal sets, and
611 '+' within a context that requires in-out constraints. */
614 validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
621 code = GET_CODE (pattern);
629 if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
631 message_with_line (pattern_lineno,
632 "operand %i duplicated before defined",
640 const char *pred_name = XSTR (pattern, 1);
641 const struct pred_data *pred;
644 if (GET_CODE (insn) == DEFINE_INSN)
645 c_test = XSTR (insn, 2);
647 c_test = XSTR (insn, 1);
649 if (pred_name[0] != 0)
651 pred = lookup_predicate (pred_name);
653 message_with_line (pattern_lineno,
654 "warning: unknown predicate '%s'",
660 if (code == MATCH_OPERAND)
662 const char constraints0 = XSTR (pattern, 2)[0];
664 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
665 don't use the MATCH_OPERAND constraint, only the predicate.
666 This is confusing to folks doing new ports, so help them
667 not make the mistake. */
668 if (GET_CODE (insn) == DEFINE_EXPAND
669 || GET_CODE (insn) == DEFINE_SPLIT
670 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
673 message_with_line (pattern_lineno,
674 "warning: constraints not supported in %s",
675 rtx_name[GET_CODE (insn)]);
678 /* A MATCH_OPERAND that is a SET should have an output reload. */
679 else if (set && constraints0)
683 if (constraints0 == '+')
685 /* If we've only got an output reload for this operand,
686 we'd better have a matching input operand. */
687 else if (constraints0 == '='
688 && find_matching_operand (insn, XINT (pattern, 0)))
692 message_with_line (pattern_lineno,
693 "operand %d missing in-out reload",
698 else if (constraints0 != '=' && constraints0 != '+')
700 message_with_line (pattern_lineno,
701 "operand %d missing output reload",
708 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
709 while not likely to occur at runtime, results in less efficient
710 code from insn-recog.c. */
711 if (set && pred && pred->allows_non_lvalue)
712 message_with_line (pattern_lineno,
713 "warning: destination operand %d "
717 /* A modeless MATCH_OPERAND can be handy when we can check for
718 multiple modes in the c_test. In most other cases, it is a
719 mistake. Only DEFINE_INSN is eligible, since SPLIT and
720 PEEP2 can FAIL within the output pattern. Exclude special
721 predicates, which check the mode themselves. Also exclude
722 predicates that allow only constants. Exclude the SET_DEST
723 of a call instruction, as that is a common idiom. */
725 if (GET_MODE (pattern) == VOIDmode
726 && code == MATCH_OPERAND
727 && GET_CODE (insn) == DEFINE_INSN
730 && pred->allows_non_const
731 && strstr (c_test, "operands") == NULL
733 && GET_CODE (set) == SET
734 && GET_CODE (SET_SRC (set)) == CALL))
735 message_with_line (pattern_lineno,
736 "warning: operand %d missing mode?",
743 enum machine_mode dmode, smode;
746 dest = SET_DEST (pattern);
747 src = SET_SRC (pattern);
749 /* STRICT_LOW_PART is a wrapper. Its argument is the real
750 destination, and it's mode should match the source. */
751 if (GET_CODE (dest) == STRICT_LOW_PART)
752 dest = XEXP (dest, 0);
754 /* Find the referent for a DUP. */
756 if (GET_CODE (dest) == MATCH_DUP
757 || GET_CODE (dest) == MATCH_OP_DUP
758 || GET_CODE (dest) == MATCH_PAR_DUP)
759 dest = find_operand (insn, XINT (dest, 0), NULL);
761 if (GET_CODE (src) == MATCH_DUP
762 || GET_CODE (src) == MATCH_OP_DUP
763 || GET_CODE (src) == MATCH_PAR_DUP)
764 src = find_operand (insn, XINT (src, 0), NULL);
766 dmode = GET_MODE (dest);
767 smode = GET_MODE (src);
769 /* The mode of an ADDRESS_OPERAND is the mode of the memory
770 reference, not the mode of the address. */
771 if (GET_CODE (src) == MATCH_OPERAND
772 && ! strcmp (XSTR (src, 1), "address_operand"))
775 /* The operands of a SET must have the same mode unless one
777 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
779 message_with_line (pattern_lineno,
780 "mode mismatch in set: %smode vs %smode",
781 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
785 /* If only one of the operands is VOIDmode, and PC or CC0 is
786 not involved, it's probably a mistake. */
787 else if (dmode != smode
788 && GET_CODE (dest) != PC
789 && GET_CODE (dest) != CC0
790 && GET_CODE (src) != PC
791 && GET_CODE (src) != CC0
792 && GET_CODE (src) != CONST_INT)
795 which = (dmode == VOIDmode ? "destination" : "source");
796 message_with_line (pattern_lineno,
797 "warning: %s missing a mode?", which);
800 if (dest != SET_DEST (pattern))
801 validate_pattern (dest, insn, pattern, '=');
802 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
803 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
808 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
812 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
813 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
814 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
817 case STRICT_LOW_PART:
818 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
822 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
824 message_with_line (pattern_lineno,
825 "operand to label_ref %smode not VOIDmode",
826 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
835 fmt = GET_RTX_FORMAT (code);
836 len = GET_RTX_LENGTH (code);
837 for (i = 0; i < len; i++)
842 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
846 for (j = 0; j < XVECLEN (pattern, i); j++)
847 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
850 case 'i': case 'w': case '0': case 's':
859 /* Create a chain of nodes to verify that an rtl expression matches
862 LAST is a pointer to the listhead in the previous node in the chain (or
863 in the calling function, for the first node).
865 POSITION is the string representing the current position in the insn.
867 INSN_TYPE is the type of insn for which we are emitting code.
869 A pointer to the final node in the chain is returned. */
871 static struct decision *
872 add_to_sequence (rtx pattern, struct decision_head *last, const char *position,
873 enum routine_type insn_type, int top)
876 struct decision *this, *sub;
877 struct decision_test *test;
878 struct decision_test **place;
882 int depth = strlen (position);
884 enum machine_mode mode;
886 if (depth > max_depth)
889 subpos = xmalloc (depth + 2);
890 strcpy (subpos, position);
891 subpos[depth + 1] = 0;
893 sub = this = new_decision (position, last);
894 place = &this->tests;
897 mode = GET_MODE (pattern);
898 code = GET_CODE (pattern);
903 /* Toplevel peephole pattern. */
904 if (insn_type == PEEPHOLE2 && top)
906 /* We don't need the node we just created -- unlink it. */
907 last->first = last->last = NULL;
909 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
911 /* Which insn we're looking at is represented by A-Z. We don't
912 ever use 'A', however; it is always implied. */
914 subpos[depth] = (i > 0 ? 'A' + i : 0);
915 sub = add_to_sequence (XVECEXP (pattern, 0, i),
916 last, subpos, insn_type, 0);
917 last = &sub->success;
922 /* Else nothing special. */
926 /* The explicit patterns within a match_parallel enforce a minimum
927 length on the vector. The match_parallel predicate may allow
928 for more elements. We do need to check for this minimum here
929 or the code generated to match the internals may reference data
930 beyond the end of the vector. */
931 test = new_decision_test (DT_veclen_ge, &place);
932 test->u.veclen = XVECLEN (pattern, 2);
939 RTX_CODE was_code = code;
940 const char *pred_name;
941 bool allows_const_int = true;
943 if (code == MATCH_SCRATCH)
945 pred_name = "scratch_operand";
950 pred_name = XSTR (pattern, 1);
951 if (code == MATCH_PARALLEL)
957 if (pred_name[0] != 0)
959 const struct pred_data *pred;
961 test = new_decision_test (DT_pred, &place);
962 test->u.pred.name = pred_name;
963 test->u.pred.mode = mode;
965 /* See if we know about this predicate.
966 If we do, remember it for use below.
968 We can optimize the generated code a little if either
969 (a) the predicate only accepts one code, or (b) the
970 predicate does not allow CONST_INT, in which case it
971 can match only if the modes match. */
972 pred = lookup_predicate (pred_name);
975 test->u.pred.data = pred;
976 allows_const_int = pred->codes[CONST_INT];
977 code = pred->singleton;
981 /* Can't enforce a mode if we allow const_int. */
982 if (allows_const_int)
985 /* Accept the operand, ie. record it in `operands'. */
986 test = new_decision_test (DT_accept_op, &place);
987 test->u.opno = XINT (pattern, 0);
989 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
991 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
992 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
994 subpos[depth] = i + base;
995 sub = add_to_sequence (XVECEXP (pattern, 2, i),
996 &sub->success, subpos, insn_type, 0);
1005 test = new_decision_test (DT_dup, &place);
1006 test->u.dup = XINT (pattern, 0);
1008 test = new_decision_test (DT_accept_op, &place);
1009 test->u.opno = XINT (pattern, 0);
1011 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
1013 subpos[depth] = i + '0';
1014 sub = add_to_sequence (XVECEXP (pattern, 1, i),
1015 &sub->success, subpos, insn_type, 0);
1023 test = new_decision_test (DT_dup, &place);
1024 test->u.dup = XINT (pattern, 0);
1028 pattern = XEXP (pattern, 0);
1035 fmt = GET_RTX_FORMAT (code);
1036 len = GET_RTX_LENGTH (code);
1038 /* Do tests against the current node first. */
1039 for (i = 0; i < (size_t) len; i++)
1045 test = new_decision_test (DT_elt_zero_int, &place);
1046 test->u.intval = XINT (pattern, i);
1050 test = new_decision_test (DT_elt_one_int, &place);
1051 test->u.intval = XINT (pattern, i);
1056 else if (fmt[i] == 'w')
1058 /* If this value actually fits in an int, we can use a switch
1059 statement here, so indicate that. */
1060 enum decision_type type
1061 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
1062 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
1067 test = new_decision_test (type, &place);
1068 test->u.intval = XWINT (pattern, i);
1070 else if (fmt[i] == 'E')
1075 test = new_decision_test (DT_veclen, &place);
1076 test->u.veclen = XVECLEN (pattern, i);
1080 /* Now test our sub-patterns. */
1081 for (i = 0; i < (size_t) len; i++)
1086 subpos[depth] = '0' + i;
1087 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1088 subpos, insn_type, 0);
1094 for (j = 0; j < XVECLEN (pattern, i); j++)
1096 subpos[depth] = 'a' + j;
1097 sub = add_to_sequence (XVECEXP (pattern, i, j),
1098 &sub->success, subpos, insn_type, 0);
1104 /* Handled above. */
1115 /* Insert nodes testing mode and code, if they're still relevant,
1116 before any of the nodes we may have added above. */
1117 if (code != UNKNOWN)
1119 place = &this->tests;
1120 test = new_decision_test (DT_code, &place);
1121 test->u.code = code;
1124 if (mode != VOIDmode)
1126 place = &this->tests;
1127 test = new_decision_test (DT_mode, &place);
1128 test->u.mode = mode;
1131 /* If we didn't insert any tests or accept nodes, hork. */
1132 if (this->tests == NULL)
1140 /* A subroutine of maybe_both_true; examines only one test.
1141 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1144 maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
1146 if (d1->type == d2->type)
1151 return d1->u.mode == d2->u.mode;
1154 return d1->u.code == d2->u.code;
1157 return d1->u.veclen == d2->u.veclen;
1159 case DT_elt_zero_int:
1160 case DT_elt_one_int:
1161 case DT_elt_zero_wide:
1162 case DT_elt_zero_wide_safe:
1163 return d1->u.intval == d2->u.intval;
1170 /* If either has a predicate that we know something about, set
1171 things up so that D1 is the one that always has a known
1172 predicate. Then see if they have any codes in common. */
1174 if (d1->type == DT_pred || d2->type == DT_pred)
1176 if (d2->type == DT_pred)
1178 struct decision_test *tmp;
1179 tmp = d1, d1 = d2, d2 = tmp;
1182 /* If D2 tests a mode, see if it matches D1. */
1183 if (d1->u.pred.mode != VOIDmode)
1185 if (d2->type == DT_mode)
1187 if (d1->u.pred.mode != d2->u.mode
1188 /* The mode of an address_operand predicate is the
1189 mode of the memory, not the operand. It can only
1190 be used for testing the predicate, so we must
1192 && strcmp (d1->u.pred.name, "address_operand") != 0)
1195 /* Don't check two predicate modes here, because if both predicates
1196 accept CONST_INT, then both can still be true even if the modes
1197 are different. If they don't accept CONST_INT, there will be a
1198 separate DT_mode that will make maybe_both_true_1 return 0. */
1201 if (d1->u.pred.data)
1203 /* If D2 tests a code, see if it is in the list of valid
1204 codes for D1's predicate. */
1205 if (d2->type == DT_code)
1207 if (!d1->u.pred.data->codes[d2->u.code])
1211 /* Otherwise see if the predicates have any codes in common. */
1212 else if (d2->type == DT_pred && d2->u.pred.data)
1214 bool common = false;
1217 for (c = 0; c < NUM_RTX_CODE; c++)
1218 if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c])
1230 /* Tests vs veclen may be known when strict equality is involved. */
1231 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1232 return d1->u.veclen >= d2->u.veclen;
1233 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1234 return d2->u.veclen >= d1->u.veclen;
1239 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1240 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1243 maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
1245 struct decision_test *t1, *t2;
1247 /* A match_operand with no predicate can match anything. Recognize
1248 this by the existence of a lone DT_accept_op test. */
1249 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1252 /* Eliminate pairs of tests while they can exactly match. */
1253 while (d1 && d2 && d1->type == d2->type)
1255 if (maybe_both_true_2 (d1, d2) == 0)
1257 d1 = d1->next, d2 = d2->next;
1260 /* After that, consider all pairs. */
1261 for (t1 = d1; t1 ; t1 = t1->next)
1262 for (t2 = d2; t2 ; t2 = t2->next)
1263 if (maybe_both_true_2 (t1, t2) == 0)
1269 /* Return 0 if we can prove that there is no RTL that can match both
1270 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1271 can match both or just that we couldn't prove there wasn't such an RTL).
1273 TOPLEVEL is nonzero if we are to only look at the top level and not
1274 recursively descend. */
1277 maybe_both_true (struct decision *d1, struct decision *d2,
1280 struct decision *p1, *p2;
1283 /* Don't compare strings on the different positions in insn. Doing so
1284 is incorrect and results in false matches from constructs like
1286 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1287 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1289 [(set (match_operand:HI "register_operand" "r")
1290 (match_operand:HI "register_operand" "r"))]
1292 If we are presented with such, we are recursing through the remainder
1293 of a node's success nodes (from the loop at the end of this function).
1294 Skip forward until we come to a position that matches.
1296 Due to the way position strings are constructed, we know that iterating
1297 forward from the lexically lower position (e.g. "00") will run into
1298 the lexically higher position (e.g. "1") and not the other way around.
1299 This saves a bit of effort. */
1301 cmp = strcmp (d1->position, d2->position);
1307 /* If the d2->position was lexically lower, swap. */
1309 p1 = d1, d1 = d2, d2 = p1;
1311 if (d1->success.first == 0)
1313 for (p1 = d1->success.first; p1; p1 = p1->next)
1314 if (maybe_both_true (p1, d2, 0))
1320 /* Test the current level. */
1321 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1325 /* We can't prove that D1 and D2 cannot both be true. If we are only
1326 to check the top level, return 1. Otherwise, see if we can prove
1327 that all choices in both successors are mutually exclusive. If
1328 either does not have any successors, we can't prove they can't both
1331 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1334 for (p1 = d1->success.first; p1; p1 = p1->next)
1335 for (p2 = d2->success.first; p2; p2 = p2->next)
1336 if (maybe_both_true (p1, p2, 0))
1342 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1345 nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
1350 return d1->u.mode == d2->u.mode;
1353 return d1->u.code == d2->u.code;
1356 return (d1->u.pred.mode == d2->u.pred.mode
1357 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1360 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1364 return d1->u.veclen == d2->u.veclen;
1367 return d1->u.dup == d2->u.dup;
1369 case DT_elt_zero_int:
1370 case DT_elt_one_int:
1371 case DT_elt_zero_wide:
1372 case DT_elt_zero_wide_safe:
1373 return d1->u.intval == d2->u.intval;
1376 return d1->u.opno == d2->u.opno;
1378 case DT_accept_insn:
1379 /* Differences will be handled in merge_accept_insn. */
1387 /* True iff the two nodes are identical (on one level only). Due
1388 to the way these lists are constructed, we shouldn't have to
1389 consider different orderings on the tests. */
1392 nodes_identical (struct decision *d1, struct decision *d2)
1394 struct decision_test *t1, *t2;
1396 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1398 if (t1->type != t2->type)
1400 if (! nodes_identical_1 (t1, t2))
1404 /* For success, they should now both be null. */
1408 /* Check that their subnodes are at the same position, as any one set
1409 of sibling decisions must be at the same position. Allowing this
1410 requires complications to find_afterward and when change_state is
1412 if (d1->success.first
1413 && d2->success.first
1414 && strcmp (d1->success.first->position, d2->success.first->position))
1420 /* A subroutine of merge_trees; given two nodes that have been declared
1421 identical, cope with two insn accept states. If they differ in the
1422 number of clobbers, then the conflict was created by make_insn_sequence
1423 and we can drop the with-clobbers version on the floor. If both
1424 nodes have no additional clobbers, we have found an ambiguity in the
1425 source machine description. */
1428 merge_accept_insn (struct decision *oldd, struct decision *addd)
1430 struct decision_test *old, *add;
1432 for (old = oldd->tests; old; old = old->next)
1433 if (old->type == DT_accept_insn)
1438 for (add = addd->tests; add; add = add->next)
1439 if (add->type == DT_accept_insn)
1444 /* If one node is for a normal insn and the second is for the base
1445 insn with clobbers stripped off, the second node should be ignored. */
1447 if (old->u.insn.num_clobbers_to_add == 0
1448 && add->u.insn.num_clobbers_to_add > 0)
1450 /* Nothing to do here. */
1452 else if (old->u.insn.num_clobbers_to_add > 0
1453 && add->u.insn.num_clobbers_to_add == 0)
1455 /* In this case, replace OLD with ADD. */
1456 old->u.insn = add->u.insn;
1460 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1461 get_insn_name (add->u.insn.code_number),
1462 get_insn_name (old->u.insn.code_number));
1463 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1464 get_insn_name (old->u.insn.code_number));
1469 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1472 merge_trees (struct decision_head *oldh, struct decision_head *addh)
1474 struct decision *next, *add;
1476 if (addh->first == 0)
1478 if (oldh->first == 0)
1484 /* Trying to merge bits at different positions isn't possible. */
1485 if (strcmp (oldh->first->position, addh->first->position))
1488 for (add = addh->first; add ; add = next)
1490 struct decision *old, *insert_before = NULL;
1494 /* The semantics of pattern matching state that the tests are
1495 done in the order given in the MD file so that if an insn
1496 matches two patterns, the first one will be used. However,
1497 in practice, most, if not all, patterns are unambiguous so
1498 that their order is independent. In that case, we can merge
1499 identical tests and group all similar modes and codes together.
1501 Scan starting from the end of OLDH until we reach a point
1502 where we reach the head of the list or where we pass a
1503 pattern that could also be true if NEW is true. If we find
1504 an identical pattern, we can merge them. Also, record the
1505 last node that tests the same code and mode and the last one
1506 that tests just the same mode.
1508 If we have no match, place NEW after the closest match we found. */
1510 for (old = oldh->last; old; old = old->prev)
1512 if (nodes_identical (old, add))
1514 merge_accept_insn (old, add);
1515 merge_trees (&old->success, &add->success);
1519 if (maybe_both_true (old, add, 0))
1522 /* Insert the nodes in DT test type order, which is roughly
1523 how expensive/important the test is. Given that the tests
1524 are also ordered within the list, examining the first is
1526 if ((int) add->tests->type < (int) old->tests->type)
1527 insert_before = old;
1530 if (insert_before == NULL)
1533 add->prev = oldh->last;
1534 oldh->last->next = add;
1539 if ((add->prev = insert_before->prev) != NULL)
1540 add->prev->next = add;
1543 add->next = insert_before;
1544 insert_before->prev = add;
1551 /* Walk the tree looking for sub-nodes that perform common tests.
1552 Factor out the common test into a new node. This enables us
1553 (depending on the test type) to emit switch statements later. */
1556 factor_tests (struct decision_head *head)
1558 struct decision *first, *next;
1560 for (first = head->first; first && first->next; first = next)
1562 enum decision_type type;
1563 struct decision *new, *old_last;
1565 type = first->tests->type;
1568 /* Want at least two compatible sequential nodes. */
1569 if (next->tests->type != type)
1572 /* Don't want all node types, just those we can turn into
1573 switch statements. */
1576 && type != DT_veclen
1577 && type != DT_elt_zero_int
1578 && type != DT_elt_one_int
1579 && type != DT_elt_zero_wide_safe)
1582 /* If we'd been performing more than one test, create a new node
1583 below our first test. */
1584 if (first->tests->next != NULL)
1586 new = new_decision (first->position, &first->success);
1587 new->tests = first->tests->next;
1588 first->tests->next = NULL;
1591 /* Crop the node tree off after our first test. */
1593 old_last = head->last;
1596 /* For each compatible test, adjust to perform only one test in
1597 the top level node, then merge the node back into the tree. */
1600 struct decision_head h;
1602 if (next->tests->next != NULL)
1604 new = new_decision (next->position, &next->success);
1605 new->tests = next->tests->next;
1606 next->tests->next = NULL;
1611 h.first = h.last = new;
1613 merge_trees (head, &h);
1615 while (next && next->tests->type == type);
1617 /* After we run out of compatible tests, graft the remaining nodes
1618 back onto the tree. */
1621 next->prev = head->last;
1622 head->last->next = next;
1623 head->last = old_last;
1628 for (first = head->first; first; first = first->next)
1629 factor_tests (&first->success);
1632 /* After factoring, try to simplify the tests on any one node.
1633 Tests that are useful for switch statements are recognizable
1634 by having only a single test on a node -- we'll be manipulating
1635 nodes with multiple tests:
1637 If we have mode tests or code tests that are redundant with
1638 predicates, remove them. */
1641 simplify_tests (struct decision_head *head)
1643 struct decision *tree;
1645 for (tree = head->first; tree; tree = tree->next)
1647 struct decision_test *a, *b;
1654 /* Find a predicate node. */
1655 while (b && b->type != DT_pred)
1659 /* Due to how these tests are constructed, we don't even need
1660 to check that the mode and code are compatible -- they were
1661 generated from the predicate in the first place. */
1662 while (a->type == DT_mode || a->type == DT_code)
1669 for (tree = head->first; tree; tree = tree->next)
1670 simplify_tests (&tree->success);
1673 /* Count the number of subnodes of HEAD. If the number is high enough,
1674 make the first node in HEAD start a separate subroutine in the C code
1675 that is generated. */
1678 break_out_subroutines (struct decision_head *head, int initial)
1681 struct decision *sub;
1683 for (sub = head->first; sub; sub = sub->next)
1684 size += 1 + break_out_subroutines (&sub->success, 0);
1686 if (size > SUBROUTINE_THRESHOLD && ! initial)
1688 head->first->subroutine_number = ++next_subroutine_number;
1694 /* For each node p, find the next alternative that might be true
1698 find_afterward (struct decision_head *head, struct decision *real_afterward)
1700 struct decision *p, *q, *afterward;
1702 /* We can't propagate alternatives across subroutine boundaries.
1703 This is not incorrect, merely a minor optimization loss. */
1706 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1708 for ( ; p ; p = p->next)
1710 /* Find the next node that might be true if this one fails. */
1711 for (q = p->next; q ; q = q->next)
1712 if (maybe_both_true (p, q, 1))
1715 /* If we reached the end of the list without finding one,
1716 use the incoming afterward position. */
1725 for (p = head->first; p ; p = p->next)
1726 if (p->success.first)
1727 find_afterward (&p->success, p->afterward);
1729 /* When we are generating a subroutine, record the real afterward
1730 position in the first node where write_tree can find it, and we
1731 can do the right thing at the subroutine call site. */
1733 if (p->subroutine_number > 0)
1734 p->afterward = real_afterward;
1737 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1738 actions are necessary to move to NEWPOS. If we fail to move to the
1739 new state, branch to node AFTERWARD if nonzero, otherwise return.
1741 Failure to move to the new state can only occur if we are trying to
1742 match multiple insns and we try to step past the end of the stream. */
1745 change_state (const char *oldpos, const char *newpos,
1746 struct decision *afterward, const char *indent)
1748 int odepth = strlen (oldpos);
1749 int ndepth = strlen (newpos);
1751 int old_has_insn, new_has_insn;
1753 /* Pop up as many levels as necessary. */
1754 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1757 /* Hunt for the last [A-Z] in both strings. */
1758 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1759 if (ISUPPER (oldpos[old_has_insn]))
1761 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1762 if (ISUPPER (newpos[new_has_insn]))
1765 /* Go down to desired level. */
1766 while (depth < ndepth)
1768 /* It's a different insn from the first one. */
1769 if (ISUPPER (newpos[depth]))
1771 /* We can only fail if we're moving down the tree. */
1772 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1774 printf ("%stem = peep2_next_insn (%d);\n",
1775 indent, newpos[depth] - 'A');
1779 printf ("%stem = peep2_next_insn (%d);\n",
1780 indent, newpos[depth] - 'A');
1781 printf ("%sif (tem == NULL_RTX)\n", indent);
1783 printf ("%s goto L%d;\n", indent, afterward->number);
1785 printf ("%s goto ret0;\n", indent);
1787 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1789 else if (ISLOWER (newpos[depth]))
1790 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1791 indent, depth + 1, depth, newpos[depth] - 'a');
1793 printf ("%sx%d = XEXP (x%d, %c);\n",
1794 indent, depth + 1, depth, newpos[depth]);
1799 /* Print the enumerator constant for CODE -- the upcase version of
1803 print_code (enum rtx_code code)
1806 for (p = GET_RTX_NAME (code); *p; p++)
1807 putchar (TOUPPER (*p));
1810 /* Emit code to cross an afterward link -- change state and branch. */
1813 write_afterward (struct decision *start, struct decision *afterward,
1816 if (!afterward || start->subroutine_number > 0)
1817 printf("%sgoto ret0;\n", indent);
1820 change_state (start->position, afterward->position, NULL, indent);
1821 printf ("%sgoto L%d;\n", indent, afterward->number);
1825 /* Emit a HOST_WIDE_INT as an integer constant expression. We need to take
1826 special care to avoid "decimal constant is so large that it is unsigned"
1827 warnings in the resulting code. */
1830 print_host_wide_int (HOST_WIDE_INT val)
1832 HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
1834 printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
1836 printf (HOST_WIDE_INT_PRINT_DEC_C, val);
1839 /* Emit a switch statement, if possible, for an initial sequence of
1840 nodes at START. Return the first node yet untested. */
1842 static struct decision *
1843 write_switch (struct decision *start, int depth)
1845 struct decision *p = start;
1846 enum decision_type type = p->tests->type;
1847 struct decision *needs_label = NULL;
1849 /* If we have two or more nodes in sequence that test the same one
1850 thing, we may be able to use a switch statement. */
1854 || p->next->tests->type != type
1855 || p->next->tests->next
1856 || nodes_identical_1 (p->tests, p->next->tests))
1859 /* DT_code is special in that we can do interesting things with
1860 known predicates at the same time. */
1861 if (type == DT_code)
1863 char codemap[NUM_RTX_CODE];
1864 struct decision *ret;
1867 memset (codemap, 0, sizeof(codemap));
1869 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1870 code = p->tests->u.code;
1873 if (p != start && p->need_label && needs_label == NULL)
1878 printf (":\n goto L%d;\n", p->success.first->number);
1879 p->success.first->need_label = 1;
1886 && p->tests->type == DT_code
1887 && ! codemap[code = p->tests->u.code]);
1889 /* If P is testing a predicate that we know about and we haven't
1890 seen any of the codes that are valid for the predicate, we can
1891 write a series of "case" statement, one for each possible code.
1892 Since we are already in a switch, these redundant tests are very
1893 cheap and will reduce the number of predicates called. */
1895 /* Note that while we write out cases for these predicates here,
1896 we don't actually write the test here, as it gets kinda messy.
1897 It is trivial to leave this to later by telling our caller that
1898 we only processed the CODE tests. */
1899 if (needs_label != NULL)
1904 while (p && p->tests->type == DT_pred && p->tests->u.pred.data)
1906 const struct pred_data *data = p->tests->u.pred.data;
1908 for (c = 0; c < NUM_RTX_CODE; c++)
1909 if (codemap[c] && data->codes[c])
1912 for (c = 0; c < NUM_RTX_CODE; c++)
1915 fputs (" case ", stdout);
1917 fputs (":\n", stdout);
1921 printf (" goto L%d;\n", p->number);
1927 /* Make the default case skip the predicates we managed to match. */
1929 printf (" default:\n");
1934 printf (" goto L%d;\n", p->number);
1938 write_afterward (start, start->afterward, " ");
1941 printf (" break;\n");
1946 else if (type == DT_mode
1947 || type == DT_veclen
1948 || type == DT_elt_zero_int
1949 || type == DT_elt_one_int
1950 || type == DT_elt_zero_wide_safe)
1952 const char *indent = "";
1954 /* We cast switch parameter to integer, so we must ensure that the value
1956 if (type == DT_elt_zero_wide_safe)
1959 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1961 printf ("%s switch (", indent);
1965 printf ("GET_MODE (x%d)", depth);
1968 printf ("XVECLEN (x%d, 0)", depth);
1970 case DT_elt_zero_int:
1971 printf ("XINT (x%d, 0)", depth);
1973 case DT_elt_one_int:
1974 printf ("XINT (x%d, 1)", depth);
1976 case DT_elt_zero_wide_safe:
1977 /* Convert result of XWINT to int for portability since some C
1978 compilers won't do it and some will. */
1979 printf ("(int) XWINT (x%d, 0)", depth);
1984 printf (")\n%s {\n", indent);
1988 /* Merge trees will not unify identical nodes if their
1989 sub-nodes are at different levels. Thus we must check
1990 for duplicate cases. */
1992 for (q = start; q != p; q = q->next)
1993 if (nodes_identical_1 (p->tests, q->tests))
1996 if (p != start && p->need_label && needs_label == NULL)
1999 printf ("%s case ", indent);
2003 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
2006 printf ("%d", p->tests->u.veclen);
2008 case DT_elt_zero_int:
2009 case DT_elt_one_int:
2010 case DT_elt_zero_wide:
2011 case DT_elt_zero_wide_safe:
2012 print_host_wide_int (p->tests->u.intval);
2017 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
2018 p->success.first->need_label = 1;
2022 while (p && p->tests->type == type && !p->tests->next);
2025 printf ("%s default:\n%s break;\n%s }\n",
2026 indent, indent, indent);
2028 return needs_label != NULL ? needs_label : p;
2032 /* None of the other tests are amenable. */
2037 /* Emit code for one test. */
2040 write_cond (struct decision_test *p, int depth,
2041 enum routine_type subroutine_type)
2046 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
2050 printf ("GET_CODE (x%d) == ", depth);
2051 print_code (p->u.code);
2055 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
2058 case DT_elt_zero_int:
2059 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
2062 case DT_elt_one_int:
2063 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
2066 case DT_elt_zero_wide:
2067 case DT_elt_zero_wide_safe:
2068 printf ("XWINT (x%d, 0) == ", depth);
2069 print_host_wide_int (p->u.intval);
2073 printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
2074 depth, (int) p->u.intval);
2078 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2082 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2086 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2087 GET_MODE_NAME (p->u.pred.mode));
2091 printf ("(%s)", p->u.c_test);
2094 case DT_accept_insn:
2095 switch (subroutine_type)
2098 if (p->u.insn.num_clobbers_to_add == 0)
2100 printf ("pnum_clobbers != NULL");
2113 /* Emit code for one action. The previous tests have succeeded;
2114 TEST is the last of the chain. In the normal case we simply
2115 perform a state change. For the `accept' tests we must do more work. */
2118 write_action (struct decision *p, struct decision_test *test,
2119 int depth, int uncond, struct decision *success,
2120 enum routine_type subroutine_type)
2127 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2129 fputs (" {\n", stdout);
2136 if (test->type == DT_accept_op)
2138 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2140 /* Only allow DT_accept_insn to follow. */
2144 if (test->type != DT_accept_insn)
2149 /* Sanity check that we're now at the end of the list of tests. */
2153 if (test->type == DT_accept_insn)
2155 switch (subroutine_type)
2158 if (test->u.insn.num_clobbers_to_add != 0)
2159 printf ("%s*pnum_clobbers = %d;\n",
2160 indent, test->u.insn.num_clobbers_to_add);
2161 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2165 printf ("%sreturn gen_split_%d (insn, operands);\n",
2166 indent, test->u.insn.code_number);
2171 int match_len = 0, i;
2173 for (i = strlen (p->position) - 1; i >= 0; --i)
2174 if (ISUPPER (p->position[i]))
2176 match_len = p->position[i] - 'A';
2179 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2180 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2181 indent, test->u.insn.code_number);
2182 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2192 printf("%sgoto L%d;\n", indent, success->number);
2193 success->need_label = 1;
2197 fputs (" }\n", stdout);
2200 /* Return 1 if the test is always true and has no fallthru path. Return -1
2201 if the test does have a fallthru path, but requires that the condition be
2202 terminated. Otherwise return 0 for a normal test. */
2203 /* ??? is_unconditional is a stupid name for a tri-state function. */
2206 is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
2208 if (t->type == DT_accept_op)
2211 if (t->type == DT_accept_insn)
2213 switch (subroutine_type)
2216 return (t->u.insn.num_clobbers_to_add == 0);
2229 /* Emit code for one node -- the conditional and the accompanying action.
2230 Return true if there is no fallthru path. */
2233 write_node (struct decision *p, int depth,
2234 enum routine_type subroutine_type)
2236 struct decision_test *test, *last_test;
2239 /* Scan the tests and simplify comparisons against small
2241 for (test = p->tests; test; test = test->next)
2243 if (test->type == DT_code
2244 && test->u.code == CONST_INT
2246 && test->next->type == DT_elt_zero_wide_safe
2247 && -MAX_SAVED_CONST_INT <= test->next->u.intval
2248 && test->next->u.intval <= MAX_SAVED_CONST_INT)
2250 test->type = DT_const_int;
2251 test->u.intval = test->next->u.intval;
2252 test->next = test->next->next;
2256 last_test = test = p->tests;
2257 uncond = is_unconditional (test, subroutine_type);
2261 write_cond (test, depth, subroutine_type);
2263 while ((test = test->next) != NULL)
2266 if (is_unconditional (test, subroutine_type))
2270 write_cond (test, depth, subroutine_type);
2276 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2281 /* Emit code for all of the sibling nodes of HEAD. */
2284 write_tree_1 (struct decision_head *head, int depth,
2285 enum routine_type subroutine_type)
2287 struct decision *p, *next;
2290 for (p = head->first; p ; p = next)
2292 /* The label for the first element was printed in write_tree. */
2293 if (p != head->first && p->need_label)
2294 OUTPUT_LABEL (" ", p->number);
2296 /* Attempt to write a switch statement for a whole sequence. */
2297 next = write_switch (p, depth);
2302 /* Failed -- fall back and write one node. */
2303 uncond = write_node (p, depth, subroutine_type);
2308 /* Finished with this chain. Close a fallthru path by branching
2309 to the afterward node. */
2311 write_afterward (head->last, head->last->afterward, " ");
2314 /* Write out the decision tree starting at HEAD. PREVPOS is the
2315 position at the node that branched to this node. */
2318 write_tree (struct decision_head *head, const char *prevpos,
2319 enum routine_type type, int initial)
2321 struct decision *p = head->first;
2325 OUTPUT_LABEL (" ", p->number);
2327 if (! initial && p->subroutine_number > 0)
2329 static const char * const name_prefix[] = {
2330 "recog", "split", "peephole2"
2333 static const char * const call_suffix[] = {
2334 ", pnum_clobbers", "", ", _pmatch_len"
2337 /* This node has been broken out into a separate subroutine.
2338 Call it, test the result, and branch accordingly. */
2342 printf (" tem = %s_%d (x0, insn%s);\n",
2343 name_prefix[type], p->subroutine_number, call_suffix[type]);
2344 if (IS_SPLIT (type))
2345 printf (" if (tem != 0)\n return tem;\n");
2347 printf (" if (tem >= 0)\n return tem;\n");
2349 change_state (p->position, p->afterward->position, NULL, " ");
2350 printf (" goto L%d;\n", p->afterward->number);
2354 printf (" return %s_%d (x0, insn%s);\n",
2355 name_prefix[type], p->subroutine_number, call_suffix[type]);
2360 int depth = strlen (p->position);
2362 change_state (prevpos, p->position, head->last->afterward, " ");
2363 write_tree_1 (head, depth, type);
2365 for (p = head->first; p; p = p->next)
2366 if (p->success.first)
2367 write_tree (&p->success, p->position, type, 0);
2371 /* Write out a subroutine of type TYPE to do comparisons starting at
2375 write_subroutine (struct decision_head *head, enum routine_type type)
2377 int subfunction = head->first ? head->first->subroutine_number : 0;
2382 s_or_e = subfunction ? "static " : "";
2385 sprintf (extension, "_%d", subfunction);
2386 else if (type == RECOG)
2387 extension[0] = '\0';
2389 strcpy (extension, "_insns");
2395 recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
2399 split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
2404 peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
2409 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2410 for (i = 1; i <= max_depth; i++)
2411 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2413 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2416 printf (" recog_data.insn = NULL_RTX;\n");
2419 write_tree (head, "", type, 1);
2421 printf (" goto ret0;\n");
2423 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2426 /* In break_out_subroutines, we discovered the boundaries for the
2427 subroutines, but did not write them out. Do so now. */
2430 write_subroutines (struct decision_head *head, enum routine_type type)
2434 for (p = head->first; p ; p = p->next)
2435 if (p->success.first)
2436 write_subroutines (&p->success, type);
2438 if (head->first->subroutine_number > 0)
2439 write_subroutine (head, type);
2442 /* Begin the output file. */
2448 /* Generated automatically by the program `genrecog' from the target\n\
2449 machine description file. */\n\
2451 #include \"config.h\"\n\
2452 #include \"system.h\"\n\
2453 #include \"coretypes.h\"\n\
2454 #include \"tm.h\"\n\
2455 #include \"rtl.h\"\n\
2456 #include \"tm_p.h\"\n\
2457 #include \"function.h\"\n\
2458 #include \"insn-config.h\"\n\
2459 #include \"recog.h\"\n\
2460 #include \"real.h\"\n\
2461 #include \"output.h\"\n\
2462 #include \"flags.h\"\n\
2463 #include \"hard-reg-set.h\"\n\
2464 #include \"resource.h\"\n\
2465 #include \"toplev.h\"\n\
2466 #include \"reload.h\"\n\
2470 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2471 X0 is a valid instruction.\n\
2473 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2474 returns a nonnegative number which is the insn code number for the\n\
2475 pattern that matched. This is the same as the order in the machine\n\
2476 description of the entry that matched. This number can be used as an\n\
2477 index into `insn_data' and other tables.\n");
2479 The third argument to recog is an optional pointer to an int. If\n\
2480 present, recog will accept a pattern if it matches except for missing\n\
2481 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2482 the optional pointer will be set to the number of CLOBBERs that need\n\
2483 to be added (it should be initialized to zero by the caller). If it");
2485 is set nonzero, the caller should allocate a PARALLEL of the\n\
2486 appropriate size, copy the initial entries, and call add_clobbers\n\
2487 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2491 The function split_insns returns 0 if the rtl could not\n\
2492 be split or the split rtl as an INSN list if it can be.\n\
2494 The function peephole2_insns returns 0 if the rtl could not\n\
2495 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2496 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2501 /* Construct and return a sequence of decisions
2502 that will recognize INSN.
2504 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2506 static struct decision_head
2507 make_insn_sequence (rtx insn, enum routine_type type)
2510 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2511 int truth = maybe_eval_c_test (c_test);
2512 struct decision *last;
2513 struct decision_test *test, **place;
2514 struct decision_head head;
2517 /* We should never see an insn whose C test is false at compile time. */
2521 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2523 c_test_pos[0] = '\0';
2524 if (type == PEEPHOLE2)
2528 /* peephole2 gets special treatment:
2529 - X always gets an outer parallel even if it's only one entry
2530 - we remove all traces of outer-level match_scratch and match_dup
2531 expressions here. */
2532 x = rtx_alloc (PARALLEL);
2533 PUT_MODE (x, VOIDmode);
2534 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2535 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2537 rtx tmp = XVECEXP (insn, 0, i);
2538 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2540 XVECEXP (x, 0, j) = tmp;
2546 c_test_pos[0] = 'A' + j - 1;
2547 c_test_pos[1] = '\0';
2549 else if (XVECLEN (insn, type == RECOG) == 1)
2550 x = XVECEXP (insn, type == RECOG, 0);
2553 x = rtx_alloc (PARALLEL);
2554 XVEC (x, 0) = XVEC (insn, type == RECOG);
2555 PUT_MODE (x, VOIDmode);
2558 validate_pattern (x, insn, NULL_RTX, 0);
2560 memset(&head, 0, sizeof(head));
2561 last = add_to_sequence (x, &head, "", type, 1);
2563 /* Find the end of the test chain on the last node. */
2564 for (test = last->tests; test->next; test = test->next)
2566 place = &test->next;
2568 /* Skip the C test if it's known to be true at compile time. */
2571 /* Need a new node if we have another test to add. */
2572 if (test->type == DT_accept_op)
2574 last = new_decision (c_test_pos, &last->success);
2575 place = &last->tests;
2577 test = new_decision_test (DT_c_test, &place);
2578 test->u.c_test = c_test;
2581 test = new_decision_test (DT_accept_insn, &place);
2582 test->u.insn.code_number = next_insn_code;
2583 test->u.insn.lineno = pattern_lineno;
2584 test->u.insn.num_clobbers_to_add = 0;
2589 /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
2590 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2591 If so, set up to recognize the pattern without these CLOBBERs. */
2593 if (GET_CODE (x) == PARALLEL)
2597 /* Find the last non-clobber in the parallel. */
2598 for (i = XVECLEN (x, 0); i > 0; i--)
2600 rtx y = XVECEXP (x, 0, i - 1);
2601 if (GET_CODE (y) != CLOBBER
2602 || (!REG_P (XEXP (y, 0))
2603 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2607 if (i != XVECLEN (x, 0))
2610 struct decision_head clobber_head;
2612 /* Build a similar insn without the clobbers. */
2614 new = XVECEXP (x, 0, 0);
2619 new = rtx_alloc (PARALLEL);
2620 XVEC (new, 0) = rtvec_alloc (i);
2621 for (j = i - 1; j >= 0; j--)
2622 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2626 memset (&clobber_head, 0, sizeof(clobber_head));
2627 last = add_to_sequence (new, &clobber_head, "", type, 1);
2629 /* Find the end of the test chain on the last node. */
2630 for (test = last->tests; test->next; test = test->next)
2633 /* We definitely have a new test to add -- create a new
2635 place = &test->next;
2636 if (test->type == DT_accept_op)
2638 last = new_decision ("", &last->success);
2639 place = &last->tests;
2642 /* Skip the C test if it's known to be true at compile
2646 test = new_decision_test (DT_c_test, &place);
2647 test->u.c_test = c_test;
2650 test = new_decision_test (DT_accept_insn, &place);
2651 test->u.insn.code_number = next_insn_code;
2652 test->u.insn.lineno = pattern_lineno;
2653 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2655 merge_trees (&head, &clobber_head);
2661 /* Define the subroutine we will call below and emit in genemit. */
2662 printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code);
2666 /* Define the subroutine we will call below and emit in genemit. */
2667 printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
2676 process_tree (struct decision_head *head, enum routine_type subroutine_type)
2678 if (head->first == NULL)
2680 /* We can elide peephole2_insns, but not recog or split_insns. */
2681 if (subroutine_type == PEEPHOLE2)
2686 factor_tests (head);
2688 next_subroutine_number = 0;
2689 break_out_subroutines (head, 1);
2690 find_afterward (head, NULL);
2692 /* We run this after find_afterward, because find_afterward needs
2693 the redundant DT_mode tests on predicates to determine whether
2694 two tests can both be true or not. */
2695 simplify_tests(head);
2697 write_subroutines (head, subroutine_type);
2700 write_subroutine (head, subroutine_type);
2703 extern int main (int, char **);
2706 main (int argc, char **argv)
2709 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2711 progname = "genrecog";
2713 memset (&recog_tree, 0, sizeof recog_tree);
2714 memset (&split_tree, 0, sizeof split_tree);
2715 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2717 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2718 return (FATAL_EXIT_CODE);
2724 /* Read the machine description. */
2728 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2732 switch (GET_CODE (desc))
2734 case DEFINE_PREDICATE:
2735 case DEFINE_SPECIAL_PREDICATE:
2736 process_define_predicate (desc);
2740 h = make_insn_sequence (desc, RECOG);
2741 merge_trees (&recog_tree, &h);
2745 h = make_insn_sequence (desc, SPLIT);
2746 merge_trees (&split_tree, &h);
2749 case DEFINE_PEEPHOLE2:
2750 h = make_insn_sequence (desc, PEEPHOLE2);
2751 merge_trees (&peephole2_tree, &h);
2758 if (error_count || have_error)
2759 return FATAL_EXIT_CODE;
2763 process_tree (&recog_tree, RECOG);
2764 process_tree (&split_tree, SPLIT);
2765 process_tree (&peephole2_tree, PEEPHOLE2);
2768 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2771 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2773 get_insn_name (int code)
2775 if (code < insn_name_ptr_size)
2776 return insn_name_ptr[code];
2782 record_insn_name (int code, const char *name)
2784 static const char *last_real_name = "insn";
2785 static int last_real_code = 0;
2788 if (insn_name_ptr_size <= code)
2791 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2792 insn_name_ptr = xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2793 memset (insn_name_ptr + insn_name_ptr_size, 0,
2794 sizeof(char *) * (new_size - insn_name_ptr_size));
2795 insn_name_ptr_size = new_size;
2798 if (!name || name[0] == '\0')
2800 new = xmalloc (strlen (last_real_name) + 10);
2801 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2805 last_real_name = new = xstrdup (name);
2806 last_real_code = code;
2809 insn_name_ptr[code] = new;
2813 debug_decision_2 (struct decision_test *test)
2818 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2821 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2824 fprintf (stderr, "veclen=%d", test->u.veclen);
2826 case DT_elt_zero_int:
2827 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2829 case DT_elt_one_int:
2830 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2832 case DT_elt_zero_wide:
2833 fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2835 case DT_elt_zero_wide_safe:
2836 fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2839 fprintf (stderr, "veclen>=%d", test->u.veclen);
2842 fprintf (stderr, "dup=%d", test->u.dup);
2845 fprintf (stderr, "pred=(%s,%s)",
2846 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2851 strncpy (sub, test->u.c_test, sizeof(sub));
2852 memcpy (sub+16, "...", 4);
2853 fprintf (stderr, "c_test=\"%s\"", sub);
2857 fprintf (stderr, "A_op=%d", test->u.opno);
2859 case DT_accept_insn:
2860 fprintf (stderr, "A_insn=(%d,%d)",
2861 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2870 debug_decision_1 (struct decision *d, int indent)
2873 struct decision_test *test;
2877 for (i = 0; i < indent; ++i)
2879 fputs ("(nil)\n", stderr);
2883 for (i = 0; i < indent; ++i)
2890 debug_decision_2 (test);
2891 while ((test = test->next) != NULL)
2893 fputs (" + ", stderr);
2894 debug_decision_2 (test);
2897 fprintf (stderr, "} %d n %d a %d\n", d->number,
2898 (d->next ? d->next->number : -1),
2899 (d->afterward ? d->afterward->number : -1));
2903 debug_decision_0 (struct decision *d, int indent, int maxdepth)
2912 for (i = 0; i < indent; ++i)
2914 fputs ("(nil)\n", stderr);
2918 debug_decision_1 (d, indent);
2919 for (n = d->success.first; n ; n = n->next)
2920 debug_decision_0 (n, indent + 2, maxdepth - 1);
2924 debug_decision (struct decision *d)
2926 debug_decision_0 (d, 0, 1000000);
2930 debug_decision_list (struct decision *d)
2934 debug_decision_0 (d, 0, 0);