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, 2005 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, 51 Franklin Street, Fifth Floor, 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 /* A listhead of decision trees. The alternatives to a node are kept
65 in a doubly-linked list so we can easily add nodes to the proper
66 place when merging. */
70 struct decision *first;
71 struct decision *last;
74 /* A single test. The two accept types aren't tests per-se, but
75 their equality (or lack thereof) does affect tree merging so
76 it is convenient to keep them here. */
80 /* A linked list through the tests attached to a node. */
81 struct decision_test *next;
83 /* These types are roughly in the order in which we'd like to test them. */
87 DT_mode, DT_code, DT_veclen,
88 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
90 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
91 DT_accept_op, DT_accept_insn
96 int num_insns; /* Number if insn in a define_peephole2. */
97 enum machine_mode mode; /* Machine mode of node. */
98 RTX_CODE code; /* Code to test. */
102 const char *name; /* Predicate to call. */
103 const struct pred_data *data;
104 /* Optimization hints for this predicate. */
105 enum machine_mode mode; /* Machine mode for node. */
108 const char *c_test; /* Additional test to perform. */
109 int veclen; /* Length of vector. */
110 int dup; /* Number of operand to compare against. */
111 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
112 int opno; /* Operand number matched. */
115 int code_number; /* Insn number matched. */
116 int lineno; /* Line number of the insn. */
117 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
122 /* Data structure for decision tree for recognizing legitimate insns. */
126 struct decision_head success; /* Nodes to test on success. */
127 struct decision *next; /* Node to test on failure. */
128 struct decision *prev; /* Node whose failure tests us. */
129 struct decision *afterward; /* Node to test on success,
130 but failure of successor nodes. */
132 const char *position; /* String denoting position in pattern. */
134 struct decision_test *tests; /* The tests for this node. */
136 int number; /* Node number, used for labels */
137 int subroutine_number; /* Number of subroutine this node starts */
138 int need_label; /* Label needs to be output. */
141 #define SUBROUTINE_THRESHOLD 100
143 static int next_subroutine_number;
145 /* We can write three types of subroutines: One for insn recognition,
146 one to split insns, and one for peephole-type optimizations. This
147 defines which type is being written. */
150 RECOG, SPLIT, PEEPHOLE2
153 #define IS_SPLIT(X) ((X) != RECOG)
155 /* Next available node number for tree nodes. */
157 static int next_number;
159 /* Next number to use as an insn_code. */
161 static int next_insn_code;
163 /* Record the highest depth we ever have so we know how many variables to
164 allocate in each subroutine we make. */
166 static int max_depth;
168 /* The line number of the start of the pattern currently being processed. */
169 static int pattern_lineno;
171 /* Count of errors. */
172 static int error_count;
174 /* Predicate handling.
176 We construct from the machine description a table mapping each
177 predicate to a list of the rtl codes it can possibly match. The
178 function 'maybe_both_true' uses it to deduce that there are no
179 expressions that can be matches by certain pairs of tree nodes.
180 Also, if a predicate can match only one code, we can hardwire that
181 code into the node testing the predicate.
183 Some predicates are flagged as special. validate_pattern will not
184 warn about modeless match_operand expressions if they have a
185 special predicate. Predicates that allow only constants are also
186 treated as special, for this purpose.
188 validate_pattern will warn about predicates that allow non-lvalues
189 when they appear in destination operands.
191 Calculating the set of rtx codes that can possibly be accepted by a
192 predicate expression EXP requires a three-state logic: any given
193 subexpression may definitively accept a code C (Y), definitively
194 reject a code C (N), or may have an indeterminate effect (I). N
195 and I is N; Y or I is Y; Y and I, N or I are both I. Here are full
206 We represent Y with 1, N with 0, I with 2. If any code is left in
207 an I state by the complete expression, we must assume that that
208 code can be accepted. */
214 #define TRISTATE_AND(a,b) \
215 ((a) == I ? ((b) == N ? N : I) : \
216 (b) == I ? ((a) == N ? N : I) : \
219 #define TRISTATE_OR(a,b) \
220 ((a) == I ? ((b) == Y ? Y : I) : \
221 (b) == I ? ((a) == Y ? Y : I) : \
224 #define TRISTATE_NOT(a) \
225 ((a) == I ? I : !(a))
227 /* 0 means no warning about that code yet, 1 means warned. */
228 static char did_you_mean_codes[NUM_RTX_CODE];
230 /* Recursively calculate the set of rtx codes accepted by the
231 predicate expression EXP, writing the result to CODES. */
233 compute_predicate_codes (rtx exp, char codes[NUM_RTX_CODE])
235 char op0_codes[NUM_RTX_CODE];
236 char op1_codes[NUM_RTX_CODE];
237 char op2_codes[NUM_RTX_CODE];
240 switch (GET_CODE (exp))
243 compute_predicate_codes (XEXP (exp, 0), op0_codes);
244 compute_predicate_codes (XEXP (exp, 1), op1_codes);
245 for (i = 0; i < NUM_RTX_CODE; i++)
246 codes[i] = TRISTATE_AND (op0_codes[i], op1_codes[i]);
250 compute_predicate_codes (XEXP (exp, 0), op0_codes);
251 compute_predicate_codes (XEXP (exp, 1), op1_codes);
252 for (i = 0; i < NUM_RTX_CODE; i++)
253 codes[i] = TRISTATE_OR (op0_codes[i], op1_codes[i]);
256 compute_predicate_codes (XEXP (exp, 0), op0_codes);
257 for (i = 0; i < NUM_RTX_CODE; i++)
258 codes[i] = TRISTATE_NOT (op0_codes[i]);
262 /* a ? b : c accepts the same codes as (a & b) | (!a & c). */
263 compute_predicate_codes (XEXP (exp, 0), op0_codes);
264 compute_predicate_codes (XEXP (exp, 1), op1_codes);
265 compute_predicate_codes (XEXP (exp, 2), op2_codes);
266 for (i = 0; i < NUM_RTX_CODE; i++)
267 codes[i] = TRISTATE_OR (TRISTATE_AND (op0_codes[i], op1_codes[i]),
268 TRISTATE_AND (TRISTATE_NOT (op0_codes[i]),
273 /* MATCH_CODE allows a specified list of codes. */
274 memset (codes, N, NUM_RTX_CODE);
276 const char *next_code = XSTR (exp, 0);
279 if (*next_code == '\0')
281 message_with_line (pattern_lineno, "empty match_code expression");
286 while ((code = scan_comma_elt (&next_code)) != 0)
288 size_t n = next_code - code;
291 for (i = 0; i < NUM_RTX_CODE; i++)
292 if (!strncmp (code, GET_RTX_NAME (i), n)
293 && GET_RTX_NAME (i)[n] == '\0')
301 message_with_line (pattern_lineno, "match_code \"%.*s\" matches nothing",
304 for (i = 0; i < NUM_RTX_CODE; i++)
305 if (!strncasecmp (code, GET_RTX_NAME (i), n)
306 && GET_RTX_NAME (i)[n] == '\0'
307 && !did_you_mean_codes[i])
309 did_you_mean_codes[i] = 1;
310 message_with_line (pattern_lineno, "(did you mean \"%s\"?)", GET_RTX_NAME (i));
319 /* MATCH_OPERAND disallows the set of codes that the named predicate
320 disallows, and is indeterminate for the codes that it does allow. */
322 struct pred_data *p = lookup_predicate (XSTR (exp, 1));
325 message_with_line (pattern_lineno,
326 "reference to unknown predicate '%s'",
331 for (i = 0; i < NUM_RTX_CODE; i++)
332 codes[i] = p->codes[i] ? I : N;
338 /* (match_test WHATEVER) is completely indeterminate. */
339 memset (codes, I, NUM_RTX_CODE);
343 message_with_line (pattern_lineno,
344 "'%s' cannot be used in a define_predicate expression",
345 GET_RTX_NAME (GET_CODE (exp)));
347 memset (codes, I, NUM_RTX_CODE);
356 /* Process a define_predicate expression: compute the set of predicates
357 that can be matched, and record this as a known predicate. */
359 process_define_predicate (rtx desc)
361 struct pred_data *pred = xcalloc (sizeof (struct pred_data), 1);
362 char codes[NUM_RTX_CODE];
363 bool seen_one = false;
366 pred->name = XSTR (desc, 0);
367 if (GET_CODE (desc) == DEFINE_SPECIAL_PREDICATE)
370 compute_predicate_codes (XEXP (desc, 1), codes);
372 for (i = 0; i < NUM_RTX_CODE; i++)
375 pred->codes[i] = true;
376 if (GET_RTX_CLASS (i) != RTX_CONST_OBJ)
377 pred->allows_non_const = true;
383 && i != STRICT_LOW_PART)
384 pred->allows_non_lvalue = true;
387 pred->singleton = UNKNOWN;
394 add_predicate (pred);
401 static struct decision *new_decision
402 (const char *, struct decision_head *);
403 static struct decision_test *new_decision_test
404 (enum decision_type, struct decision_test ***);
405 static rtx find_operand
407 static rtx find_matching_operand
409 static void validate_pattern
410 (rtx, rtx, rtx, int);
411 static struct decision *add_to_sequence
412 (rtx, struct decision_head *, const char *, enum routine_type, int);
414 static int maybe_both_true_2
415 (struct decision_test *, struct decision_test *);
416 static int maybe_both_true_1
417 (struct decision_test *, struct decision_test *);
418 static int maybe_both_true
419 (struct decision *, struct decision *, int);
421 static int nodes_identical_1
422 (struct decision_test *, struct decision_test *);
423 static int nodes_identical
424 (struct decision *, struct decision *);
425 static void merge_accept_insn
426 (struct decision *, struct decision *);
427 static void merge_trees
428 (struct decision_head *, struct decision_head *);
430 static void factor_tests
431 (struct decision_head *);
432 static void simplify_tests
433 (struct decision_head *);
434 static int break_out_subroutines
435 (struct decision_head *, int);
436 static void find_afterward
437 (struct decision_head *, struct decision *);
439 static void change_state
440 (const char *, const char *, const char *);
441 static void print_code
443 static void write_afterward
444 (struct decision *, struct decision *, const char *);
445 static struct decision *write_switch
446 (struct decision *, int);
447 static void write_cond
448 (struct decision_test *, int, enum routine_type);
449 static void write_action
450 (struct decision *, struct decision_test *, int, int,
451 struct decision *, enum routine_type);
452 static int is_unconditional
453 (struct decision_test *, enum routine_type);
454 static int write_node
455 (struct decision *, int, enum routine_type);
456 static void write_tree_1
457 (struct decision_head *, int, enum routine_type);
458 static void write_tree
459 (struct decision_head *, const char *, enum routine_type, int);
460 static void write_subroutine
461 (struct decision_head *, enum routine_type);
462 static void write_subroutines
463 (struct decision_head *, enum routine_type);
464 static void write_header
467 static struct decision_head make_insn_sequence
468 (rtx, enum routine_type);
469 static void process_tree
470 (struct decision_head *, enum routine_type);
472 static void debug_decision_0
473 (struct decision *, int, int);
474 static void debug_decision_1
475 (struct decision *, int);
476 static void debug_decision_2
477 (struct decision_test *);
478 extern void debug_decision
480 extern void debug_decision_list
483 /* Create a new node in sequence after LAST. */
485 static struct decision *
486 new_decision (const char *position, struct decision_head *last)
488 struct decision *new = xcalloc (1, sizeof (struct decision));
490 new->success = *last;
491 new->position = xstrdup (position);
492 new->number = next_number++;
494 last->first = last->last = new;
498 /* Create a new test and link it in at PLACE. */
500 static struct decision_test *
501 new_decision_test (enum decision_type type, struct decision_test ***pplace)
503 struct decision_test **place = *pplace;
504 struct decision_test *test;
506 test = xmalloc (sizeof (*test));
517 /* Search for and return operand N, stop when reaching node STOP. */
520 find_operand (rtx pattern, int n, rtx stop)
530 code = GET_CODE (pattern);
531 if ((code == MATCH_SCRATCH
532 || code == MATCH_OPERAND
533 || code == MATCH_OPERATOR
534 || code == MATCH_PARALLEL)
535 && XINT (pattern, 0) == n)
538 fmt = GET_RTX_FORMAT (code);
539 len = GET_RTX_LENGTH (code);
540 for (i = 0; i < len; i++)
545 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
550 if (! XVEC (pattern, i))
555 for (j = 0; j < XVECLEN (pattern, i); j++)
556 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
561 case 'i': case 'w': case '0': case 's':
572 /* Search for and return operand M, such that it has a matching
573 constraint for operand N. */
576 find_matching_operand (rtx pattern, int n)
583 code = GET_CODE (pattern);
584 if (code == MATCH_OPERAND
585 && (XSTR (pattern, 2)[0] == '0' + n
586 || (XSTR (pattern, 2)[0] == '%'
587 && XSTR (pattern, 2)[1] == '0' + n)))
590 fmt = GET_RTX_FORMAT (code);
591 len = GET_RTX_LENGTH (code);
592 for (i = 0; i < len; i++)
597 if ((r = find_matching_operand (XEXP (pattern, i), n)))
602 if (! XVEC (pattern, i))
607 for (j = 0; j < XVECLEN (pattern, i); j++)
608 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
612 case 'i': case 'w': case '0': case 's':
624 /* Check for various errors in patterns. SET is nonnull for a destination,
625 and is the complete set pattern. SET_CODE is '=' for normal sets, and
626 '+' within a context that requires in-out constraints. */
629 validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
636 code = GET_CODE (pattern);
644 if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
646 message_with_line (pattern_lineno,
647 "operand %i duplicated before defined",
655 const char *pred_name = XSTR (pattern, 1);
656 const struct pred_data *pred;
659 if (GET_CODE (insn) == DEFINE_INSN)
660 c_test = XSTR (insn, 2);
662 c_test = XSTR (insn, 1);
664 if (pred_name[0] != 0)
666 pred = lookup_predicate (pred_name);
668 message_with_line (pattern_lineno,
669 "warning: unknown predicate '%s'",
675 if (code == MATCH_OPERAND)
677 const char constraints0 = XSTR (pattern, 2)[0];
679 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
680 don't use the MATCH_OPERAND constraint, only the predicate.
681 This is confusing to folks doing new ports, so help them
682 not make the mistake. */
683 if (GET_CODE (insn) == DEFINE_EXPAND
684 || GET_CODE (insn) == DEFINE_SPLIT
685 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
688 message_with_line (pattern_lineno,
689 "warning: constraints not supported in %s",
690 rtx_name[GET_CODE (insn)]);
693 /* A MATCH_OPERAND that is a SET should have an output reload. */
694 else if (set && constraints0)
698 if (constraints0 == '+')
700 /* If we've only got an output reload for this operand,
701 we'd better have a matching input operand. */
702 else if (constraints0 == '='
703 && find_matching_operand (insn, XINT (pattern, 0)))
707 message_with_line (pattern_lineno,
708 "operand %d missing in-out reload",
713 else if (constraints0 != '=' && constraints0 != '+')
715 message_with_line (pattern_lineno,
716 "operand %d missing output reload",
723 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
724 while not likely to occur at runtime, results in less efficient
725 code from insn-recog.c. */
726 if (set && pred && pred->allows_non_lvalue)
727 message_with_line (pattern_lineno,
728 "warning: destination operand %d "
732 /* A modeless MATCH_OPERAND can be handy when we can check for
733 multiple modes in the c_test. In most other cases, it is a
734 mistake. Only DEFINE_INSN is eligible, since SPLIT and
735 PEEP2 can FAIL within the output pattern. Exclude special
736 predicates, which check the mode themselves. Also exclude
737 predicates that allow only constants. Exclude the SET_DEST
738 of a call instruction, as that is a common idiom. */
740 if (GET_MODE (pattern) == VOIDmode
741 && code == MATCH_OPERAND
742 && GET_CODE (insn) == DEFINE_INSN
745 && pred->allows_non_const
746 && strstr (c_test, "operands") == NULL
748 && GET_CODE (set) == SET
749 && GET_CODE (SET_SRC (set)) == CALL))
750 message_with_line (pattern_lineno,
751 "warning: operand %d missing mode?",
758 enum machine_mode dmode, smode;
761 dest = SET_DEST (pattern);
762 src = SET_SRC (pattern);
764 /* STRICT_LOW_PART is a wrapper. Its argument is the real
765 destination, and it's mode should match the source. */
766 if (GET_CODE (dest) == STRICT_LOW_PART)
767 dest = XEXP (dest, 0);
769 /* Find the referent for a DUP. */
771 if (GET_CODE (dest) == MATCH_DUP
772 || GET_CODE (dest) == MATCH_OP_DUP
773 || GET_CODE (dest) == MATCH_PAR_DUP)
774 dest = find_operand (insn, XINT (dest, 0), NULL);
776 if (GET_CODE (src) == MATCH_DUP
777 || GET_CODE (src) == MATCH_OP_DUP
778 || GET_CODE (src) == MATCH_PAR_DUP)
779 src = find_operand (insn, XINT (src, 0), NULL);
781 dmode = GET_MODE (dest);
782 smode = GET_MODE (src);
784 /* The mode of an ADDRESS_OPERAND is the mode of the memory
785 reference, not the mode of the address. */
786 if (GET_CODE (src) == MATCH_OPERAND
787 && ! strcmp (XSTR (src, 1), "address_operand"))
790 /* The operands of a SET must have the same mode unless one
792 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
794 message_with_line (pattern_lineno,
795 "mode mismatch in set: %smode vs %smode",
796 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
800 /* If only one of the operands is VOIDmode, and PC or CC0 is
801 not involved, it's probably a mistake. */
802 else if (dmode != smode
803 && GET_CODE (dest) != PC
804 && GET_CODE (dest) != CC0
805 && GET_CODE (src) != PC
806 && GET_CODE (src) != CC0
807 && GET_CODE (src) != CONST_INT)
810 which = (dmode == VOIDmode ? "destination" : "source");
811 message_with_line (pattern_lineno,
812 "warning: %s missing a mode?", which);
815 if (dest != SET_DEST (pattern))
816 validate_pattern (dest, insn, pattern, '=');
817 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
818 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
823 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
827 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
828 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
829 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
832 case STRICT_LOW_PART:
833 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
837 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
839 message_with_line (pattern_lineno,
840 "operand to label_ref %smode not VOIDmode",
841 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
850 fmt = GET_RTX_FORMAT (code);
851 len = GET_RTX_LENGTH (code);
852 for (i = 0; i < len; i++)
857 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
861 for (j = 0; j < XVECLEN (pattern, i); j++)
862 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
865 case 'i': case 'w': case '0': case 's':
874 /* Create a chain of nodes to verify that an rtl expression matches
877 LAST is a pointer to the listhead in the previous node in the chain (or
878 in the calling function, for the first node).
880 POSITION is the string representing the current position in the insn.
882 INSN_TYPE is the type of insn for which we are emitting code.
884 A pointer to the final node in the chain is returned. */
886 static struct decision *
887 add_to_sequence (rtx pattern, struct decision_head *last, const char *position,
888 enum routine_type insn_type, int top)
891 struct decision *this, *sub;
892 struct decision_test *test;
893 struct decision_test **place;
897 int depth = strlen (position);
899 enum machine_mode mode;
901 if (depth > max_depth)
904 subpos = xmalloc (depth + 2);
905 strcpy (subpos, position);
906 subpos[depth + 1] = 0;
908 sub = this = new_decision (position, last);
909 place = &this->tests;
912 mode = GET_MODE (pattern);
913 code = GET_CODE (pattern);
918 /* Toplevel peephole pattern. */
919 if (insn_type == PEEPHOLE2 && top)
923 /* Check we have sufficient insns. This avoids complications
924 because we then know peep2_next_insn never fails. */
925 num_insns = XVECLEN (pattern, 0);
928 test = new_decision_test (DT_num_insns, &place);
929 test->u.num_insns = num_insns;
930 last = &sub->success;
934 /* We don't need the node we just created -- unlink it. */
935 last->first = last->last = NULL;
938 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
940 /* Which insn we're looking at is represented by A-Z. We don't
941 ever use 'A', however; it is always implied. */
943 subpos[depth] = (i > 0 ? 'A' + i : 0);
944 sub = add_to_sequence (XVECEXP (pattern, 0, i),
945 last, subpos, insn_type, 0);
946 last = &sub->success;
951 /* Else nothing special. */
955 /* The explicit patterns within a match_parallel enforce a minimum
956 length on the vector. The match_parallel predicate may allow
957 for more elements. We do need to check for this minimum here
958 or the code generated to match the internals may reference data
959 beyond the end of the vector. */
960 test = new_decision_test (DT_veclen_ge, &place);
961 test->u.veclen = XVECLEN (pattern, 2);
968 RTX_CODE was_code = code;
969 const char *pred_name;
970 bool allows_const_int = true;
972 if (code == MATCH_SCRATCH)
974 pred_name = "scratch_operand";
979 pred_name = XSTR (pattern, 1);
980 if (code == MATCH_PARALLEL)
986 if (pred_name[0] != 0)
988 const struct pred_data *pred;
990 test = new_decision_test (DT_pred, &place);
991 test->u.pred.name = pred_name;
992 test->u.pred.mode = mode;
994 /* See if we know about this predicate.
995 If we do, remember it for use below.
997 We can optimize the generated code a little if either
998 (a) the predicate only accepts one code, or (b) the
999 predicate does not allow CONST_INT, in which case it
1000 can match only if the modes match. */
1001 pred = lookup_predicate (pred_name);
1004 test->u.pred.data = pred;
1005 allows_const_int = pred->codes[CONST_INT];
1006 if (was_code == MATCH_PARALLEL
1007 && pred->singleton != PARALLEL)
1008 message_with_line (pattern_lineno,
1009 "predicate '%s' used in match_parallel "
1010 "does not allow only PARALLEL", pred->name);
1012 code = pred->singleton;
1015 message_with_line (pattern_lineno,
1016 "warning: unknown predicate '%s' in '%s' expression",
1017 pred_name, GET_RTX_NAME (was_code));
1020 /* Can't enforce a mode if we allow const_int. */
1021 if (allows_const_int)
1024 /* Accept the operand, i.e. record it in `operands'. */
1025 test = new_decision_test (DT_accept_op, &place);
1026 test->u.opno = XINT (pattern, 0);
1028 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
1030 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
1031 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
1033 subpos[depth] = i + base;
1034 sub = add_to_sequence (XVECEXP (pattern, 2, i),
1035 &sub->success, subpos, insn_type, 0);
1044 test = new_decision_test (DT_dup, &place);
1045 test->u.dup = XINT (pattern, 0);
1047 test = new_decision_test (DT_accept_op, &place);
1048 test->u.opno = XINT (pattern, 0);
1050 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
1052 subpos[depth] = i + '0';
1053 sub = add_to_sequence (XVECEXP (pattern, 1, i),
1054 &sub->success, subpos, insn_type, 0);
1062 test = new_decision_test (DT_dup, &place);
1063 test->u.dup = XINT (pattern, 0);
1067 pattern = XEXP (pattern, 0);
1074 fmt = GET_RTX_FORMAT (code);
1075 len = GET_RTX_LENGTH (code);
1077 /* Do tests against the current node first. */
1078 for (i = 0; i < (size_t) len; i++)
1086 test = new_decision_test (DT_elt_zero_int, &place);
1087 test->u.intval = XINT (pattern, i);
1091 test = new_decision_test (DT_elt_one_int, &place);
1092 test->u.intval = XINT (pattern, i);
1095 else if (fmt[i] == 'w')
1097 /* If this value actually fits in an int, we can use a switch
1098 statement here, so indicate that. */
1099 enum decision_type type
1100 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
1101 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
1105 test = new_decision_test (type, &place);
1106 test->u.intval = XWINT (pattern, i);
1108 else if (fmt[i] == 'E')
1112 test = new_decision_test (DT_veclen, &place);
1113 test->u.veclen = XVECLEN (pattern, i);
1117 /* Now test our sub-patterns. */
1118 for (i = 0; i < (size_t) len; i++)
1123 subpos[depth] = '0' + i;
1124 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1125 subpos, insn_type, 0);
1131 for (j = 0; j < XVECLEN (pattern, i); j++)
1133 subpos[depth] = 'a' + j;
1134 sub = add_to_sequence (XVECEXP (pattern, i, j),
1135 &sub->success, subpos, insn_type, 0);
1141 /* Handled above. */
1152 /* Insert nodes testing mode and code, if they're still relevant,
1153 before any of the nodes we may have added above. */
1154 if (code != UNKNOWN)
1156 place = &this->tests;
1157 test = new_decision_test (DT_code, &place);
1158 test->u.code = code;
1161 if (mode != VOIDmode)
1163 place = &this->tests;
1164 test = new_decision_test (DT_mode, &place);
1165 test->u.mode = mode;
1168 /* If we didn't insert any tests or accept nodes, hork. */
1169 gcc_assert (this->tests);
1176 /* A subroutine of maybe_both_true; examines only one test.
1177 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1180 maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
1182 if (d1->type == d2->type)
1187 if (d1->u.num_insns == d2->u.num_insns)
1193 return d1->u.mode == d2->u.mode;
1196 return d1->u.code == d2->u.code;
1199 return d1->u.veclen == d2->u.veclen;
1201 case DT_elt_zero_int:
1202 case DT_elt_one_int:
1203 case DT_elt_zero_wide:
1204 case DT_elt_zero_wide_safe:
1205 return d1->u.intval == d2->u.intval;
1212 /* If either has a predicate that we know something about, set
1213 things up so that D1 is the one that always has a known
1214 predicate. Then see if they have any codes in common. */
1216 if (d1->type == DT_pred || d2->type == DT_pred)
1218 if (d2->type == DT_pred)
1220 struct decision_test *tmp;
1221 tmp = d1, d1 = d2, d2 = tmp;
1224 /* If D2 tests a mode, see if it matches D1. */
1225 if (d1->u.pred.mode != VOIDmode)
1227 if (d2->type == DT_mode)
1229 if (d1->u.pred.mode != d2->u.mode
1230 /* The mode of an address_operand predicate is the
1231 mode of the memory, not the operand. It can only
1232 be used for testing the predicate, so we must
1234 && strcmp (d1->u.pred.name, "address_operand") != 0)
1237 /* Don't check two predicate modes here, because if both predicates
1238 accept CONST_INT, then both can still be true even if the modes
1239 are different. If they don't accept CONST_INT, there will be a
1240 separate DT_mode that will make maybe_both_true_1 return 0. */
1243 if (d1->u.pred.data)
1245 /* If D2 tests a code, see if it is in the list of valid
1246 codes for D1's predicate. */
1247 if (d2->type == DT_code)
1249 if (!d1->u.pred.data->codes[d2->u.code])
1253 /* Otherwise see if the predicates have any codes in common. */
1254 else if (d2->type == DT_pred && d2->u.pred.data)
1256 bool common = false;
1259 for (c = 0; c < NUM_RTX_CODE; c++)
1260 if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c])
1272 /* Tests vs veclen may be known when strict equality is involved. */
1273 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1274 return d1->u.veclen >= d2->u.veclen;
1275 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1276 return d2->u.veclen >= d1->u.veclen;
1281 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1282 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1285 maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
1287 struct decision_test *t1, *t2;
1289 /* A match_operand with no predicate can match anything. Recognize
1290 this by the existence of a lone DT_accept_op test. */
1291 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1294 /* Eliminate pairs of tests while they can exactly match. */
1295 while (d1 && d2 && d1->type == d2->type)
1297 if (maybe_both_true_2 (d1, d2) == 0)
1299 d1 = d1->next, d2 = d2->next;
1302 /* After that, consider all pairs. */
1303 for (t1 = d1; t1 ; t1 = t1->next)
1304 for (t2 = d2; t2 ; t2 = t2->next)
1305 if (maybe_both_true_2 (t1, t2) == 0)
1311 /* Return 0 if we can prove that there is no RTL that can match both
1312 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1313 can match both or just that we couldn't prove there wasn't such an RTL).
1315 TOPLEVEL is nonzero if we are to only look at the top level and not
1316 recursively descend. */
1319 maybe_both_true (struct decision *d1, struct decision *d2,
1322 struct decision *p1, *p2;
1325 /* Don't compare strings on the different positions in insn. Doing so
1326 is incorrect and results in false matches from constructs like
1328 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1329 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1331 [(set (match_operand:HI "register_operand" "r")
1332 (match_operand:HI "register_operand" "r"))]
1334 If we are presented with such, we are recursing through the remainder
1335 of a node's success nodes (from the loop at the end of this function).
1336 Skip forward until we come to a position that matches.
1338 Due to the way position strings are constructed, we know that iterating
1339 forward from the lexically lower position (e.g. "00") will run into
1340 the lexically higher position (e.g. "1") and not the other way around.
1341 This saves a bit of effort. */
1343 cmp = strcmp (d1->position, d2->position);
1346 gcc_assert (!toplevel);
1348 /* If the d2->position was lexically lower, swap. */
1350 p1 = d1, d1 = d2, d2 = p1;
1352 if (d1->success.first == 0)
1354 for (p1 = d1->success.first; p1; p1 = p1->next)
1355 if (maybe_both_true (p1, d2, 0))
1361 /* Test the current level. */
1362 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1366 /* We can't prove that D1 and D2 cannot both be true. If we are only
1367 to check the top level, return 1. Otherwise, see if we can prove
1368 that all choices in both successors are mutually exclusive. If
1369 either does not have any successors, we can't prove they can't both
1372 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1375 for (p1 = d1->success.first; p1; p1 = p1->next)
1376 for (p2 = d2->success.first; p2; p2 = p2->next)
1377 if (maybe_both_true (p1, p2, 0))
1383 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1386 nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
1391 return d1->u.num_insns == d2->u.num_insns;
1394 return d1->u.mode == d2->u.mode;
1397 return d1->u.code == d2->u.code;
1400 return (d1->u.pred.mode == d2->u.pred.mode
1401 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1404 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1408 return d1->u.veclen == d2->u.veclen;
1411 return d1->u.dup == d2->u.dup;
1413 case DT_elt_zero_int:
1414 case DT_elt_one_int:
1415 case DT_elt_zero_wide:
1416 case DT_elt_zero_wide_safe:
1417 return d1->u.intval == d2->u.intval;
1420 return d1->u.opno == d2->u.opno;
1422 case DT_accept_insn:
1423 /* Differences will be handled in merge_accept_insn. */
1431 /* True iff the two nodes are identical (on one level only). Due
1432 to the way these lists are constructed, we shouldn't have to
1433 consider different orderings on the tests. */
1436 nodes_identical (struct decision *d1, struct decision *d2)
1438 struct decision_test *t1, *t2;
1440 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1442 if (t1->type != t2->type)
1444 if (! nodes_identical_1 (t1, t2))
1448 /* For success, they should now both be null. */
1452 /* Check that their subnodes are at the same position, as any one set
1453 of sibling decisions must be at the same position. Allowing this
1454 requires complications to find_afterward and when change_state is
1456 if (d1->success.first
1457 && d2->success.first
1458 && strcmp (d1->success.first->position, d2->success.first->position))
1464 /* A subroutine of merge_trees; given two nodes that have been declared
1465 identical, cope with two insn accept states. If they differ in the
1466 number of clobbers, then the conflict was created by make_insn_sequence
1467 and we can drop the with-clobbers version on the floor. If both
1468 nodes have no additional clobbers, we have found an ambiguity in the
1469 source machine description. */
1472 merge_accept_insn (struct decision *oldd, struct decision *addd)
1474 struct decision_test *old, *add;
1476 for (old = oldd->tests; old; old = old->next)
1477 if (old->type == DT_accept_insn)
1482 for (add = addd->tests; add; add = add->next)
1483 if (add->type == DT_accept_insn)
1488 /* If one node is for a normal insn and the second is for the base
1489 insn with clobbers stripped off, the second node should be ignored. */
1491 if (old->u.insn.num_clobbers_to_add == 0
1492 && add->u.insn.num_clobbers_to_add > 0)
1494 /* Nothing to do here. */
1496 else if (old->u.insn.num_clobbers_to_add > 0
1497 && add->u.insn.num_clobbers_to_add == 0)
1499 /* In this case, replace OLD with ADD. */
1500 old->u.insn = add->u.insn;
1504 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1505 get_insn_name (add->u.insn.code_number),
1506 get_insn_name (old->u.insn.code_number));
1507 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1508 get_insn_name (old->u.insn.code_number));
1513 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1516 merge_trees (struct decision_head *oldh, struct decision_head *addh)
1518 struct decision *next, *add;
1520 if (addh->first == 0)
1522 if (oldh->first == 0)
1528 /* Trying to merge bits at different positions isn't possible. */
1529 gcc_assert (!strcmp (oldh->first->position, addh->first->position));
1531 for (add = addh->first; add ; add = next)
1533 struct decision *old, *insert_before = NULL;
1537 /* The semantics of pattern matching state that the tests are
1538 done in the order given in the MD file so that if an insn
1539 matches two patterns, the first one will be used. However,
1540 in practice, most, if not all, patterns are unambiguous so
1541 that their order is independent. In that case, we can merge
1542 identical tests and group all similar modes and codes together.
1544 Scan starting from the end of OLDH until we reach a point
1545 where we reach the head of the list or where we pass a
1546 pattern that could also be true if NEW is true. If we find
1547 an identical pattern, we can merge them. Also, record the
1548 last node that tests the same code and mode and the last one
1549 that tests just the same mode.
1551 If we have no match, place NEW after the closest match we found. */
1553 for (old = oldh->last; old; old = old->prev)
1555 if (nodes_identical (old, add))
1557 merge_accept_insn (old, add);
1558 merge_trees (&old->success, &add->success);
1562 if (maybe_both_true (old, add, 0))
1565 /* Insert the nodes in DT test type order, which is roughly
1566 how expensive/important the test is. Given that the tests
1567 are also ordered within the list, examining the first is
1569 if ((int) add->tests->type < (int) old->tests->type)
1570 insert_before = old;
1573 if (insert_before == NULL)
1576 add->prev = oldh->last;
1577 oldh->last->next = add;
1582 if ((add->prev = insert_before->prev) != NULL)
1583 add->prev->next = add;
1586 add->next = insert_before;
1587 insert_before->prev = add;
1594 /* Walk the tree looking for sub-nodes that perform common tests.
1595 Factor out the common test into a new node. This enables us
1596 (depending on the test type) to emit switch statements later. */
1599 factor_tests (struct decision_head *head)
1601 struct decision *first, *next;
1603 for (first = head->first; first && first->next; first = next)
1605 enum decision_type type;
1606 struct decision *new, *old_last;
1608 type = first->tests->type;
1611 /* Want at least two compatible sequential nodes. */
1612 if (next->tests->type != type)
1615 /* Don't want all node types, just those we can turn into
1616 switch statements. */
1619 && type != DT_veclen
1620 && type != DT_elt_zero_int
1621 && type != DT_elt_one_int
1622 && type != DT_elt_zero_wide_safe)
1625 /* If we'd been performing more than one test, create a new node
1626 below our first test. */
1627 if (first->tests->next != NULL)
1629 new = new_decision (first->position, &first->success);
1630 new->tests = first->tests->next;
1631 first->tests->next = NULL;
1634 /* Crop the node tree off after our first test. */
1636 old_last = head->last;
1639 /* For each compatible test, adjust to perform only one test in
1640 the top level node, then merge the node back into the tree. */
1643 struct decision_head h;
1645 if (next->tests->next != NULL)
1647 new = new_decision (next->position, &next->success);
1648 new->tests = next->tests->next;
1649 next->tests->next = NULL;
1654 h.first = h.last = new;
1656 merge_trees (head, &h);
1658 while (next && next->tests->type == type);
1660 /* After we run out of compatible tests, graft the remaining nodes
1661 back onto the tree. */
1664 next->prev = head->last;
1665 head->last->next = next;
1666 head->last = old_last;
1671 for (first = head->first; first; first = first->next)
1672 factor_tests (&first->success);
1675 /* After factoring, try to simplify the tests on any one node.
1676 Tests that are useful for switch statements are recognizable
1677 by having only a single test on a node -- we'll be manipulating
1678 nodes with multiple tests:
1680 If we have mode tests or code tests that are redundant with
1681 predicates, remove them. */
1684 simplify_tests (struct decision_head *head)
1686 struct decision *tree;
1688 for (tree = head->first; tree; tree = tree->next)
1690 struct decision_test *a, *b;
1697 /* Find a predicate node. */
1698 while (b && b->type != DT_pred)
1702 /* Due to how these tests are constructed, we don't even need
1703 to check that the mode and code are compatible -- they were
1704 generated from the predicate in the first place. */
1705 while (a->type == DT_mode || a->type == DT_code)
1712 for (tree = head->first; tree; tree = tree->next)
1713 simplify_tests (&tree->success);
1716 /* Count the number of subnodes of HEAD. If the number is high enough,
1717 make the first node in HEAD start a separate subroutine in the C code
1718 that is generated. */
1721 break_out_subroutines (struct decision_head *head, int initial)
1724 struct decision *sub;
1726 for (sub = head->first; sub; sub = sub->next)
1727 size += 1 + break_out_subroutines (&sub->success, 0);
1729 if (size > SUBROUTINE_THRESHOLD && ! initial)
1731 head->first->subroutine_number = ++next_subroutine_number;
1737 /* For each node p, find the next alternative that might be true
1741 find_afterward (struct decision_head *head, struct decision *real_afterward)
1743 struct decision *p, *q, *afterward;
1745 /* We can't propagate alternatives across subroutine boundaries.
1746 This is not incorrect, merely a minor optimization loss. */
1749 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1751 for ( ; p ; p = p->next)
1753 /* Find the next node that might be true if this one fails. */
1754 for (q = p->next; q ; q = q->next)
1755 if (maybe_both_true (p, q, 1))
1758 /* If we reached the end of the list without finding one,
1759 use the incoming afterward position. */
1768 for (p = head->first; p ; p = p->next)
1769 if (p->success.first)
1770 find_afterward (&p->success, p->afterward);
1772 /* When we are generating a subroutine, record the real afterward
1773 position in the first node where write_tree can find it, and we
1774 can do the right thing at the subroutine call site. */
1776 if (p->subroutine_number > 0)
1777 p->afterward = real_afterward;
1780 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1781 actions are necessary to move to NEWPOS. If we fail to move to the
1782 new state, branch to node AFTERWARD if nonzero, otherwise return.
1784 Failure to move to the new state can only occur if we are trying to
1785 match multiple insns and we try to step past the end of the stream. */
1788 change_state (const char *oldpos, const char *newpos, const char *indent)
1790 int odepth = strlen (oldpos);
1791 int ndepth = strlen (newpos);
1793 int old_has_insn, new_has_insn;
1795 /* Pop up as many levels as necessary. */
1796 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1799 /* Hunt for the last [A-Z] in both strings. */
1800 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1801 if (ISUPPER (oldpos[old_has_insn]))
1803 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1804 if (ISUPPER (newpos[new_has_insn]))
1807 /* Go down to desired level. */
1808 while (depth < ndepth)
1810 /* It's a different insn from the first one. */
1811 if (ISUPPER (newpos[depth]))
1813 printf ("%stem = peep2_next_insn (%d);\n",
1814 indent, newpos[depth] - 'A');
1815 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1817 else if (ISLOWER (newpos[depth]))
1818 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1819 indent, depth + 1, depth, newpos[depth] - 'a');
1821 printf ("%sx%d = XEXP (x%d, %c);\n",
1822 indent, depth + 1, depth, newpos[depth]);
1827 /* Print the enumerator constant for CODE -- the upcase version of
1831 print_code (enum rtx_code code)
1834 for (p = GET_RTX_NAME (code); *p; p++)
1835 putchar (TOUPPER (*p));
1838 /* Emit code to cross an afterward link -- change state and branch. */
1841 write_afterward (struct decision *start, struct decision *afterward,
1844 if (!afterward || start->subroutine_number > 0)
1845 printf("%sgoto ret0;\n", indent);
1848 change_state (start->position, afterward->position, indent);
1849 printf ("%sgoto L%d;\n", indent, afterward->number);
1853 /* Emit a HOST_WIDE_INT as an integer constant expression. We need to take
1854 special care to avoid "decimal constant is so large that it is unsigned"
1855 warnings in the resulting code. */
1858 print_host_wide_int (HOST_WIDE_INT val)
1860 HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
1862 printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
1864 printf (HOST_WIDE_INT_PRINT_DEC_C, val);
1867 /* Emit a switch statement, if possible, for an initial sequence of
1868 nodes at START. Return the first node yet untested. */
1870 static struct decision *
1871 write_switch (struct decision *start, int depth)
1873 struct decision *p = start;
1874 enum decision_type type = p->tests->type;
1875 struct decision *needs_label = NULL;
1877 /* If we have two or more nodes in sequence that test the same one
1878 thing, we may be able to use a switch statement. */
1882 || p->next->tests->type != type
1883 || p->next->tests->next
1884 || nodes_identical_1 (p->tests, p->next->tests))
1887 /* DT_code is special in that we can do interesting things with
1888 known predicates at the same time. */
1889 if (type == DT_code)
1891 char codemap[NUM_RTX_CODE];
1892 struct decision *ret;
1895 memset (codemap, 0, sizeof(codemap));
1897 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1898 code = p->tests->u.code;
1901 if (p != start && p->need_label && needs_label == NULL)
1906 printf (":\n goto L%d;\n", p->success.first->number);
1907 p->success.first->need_label = 1;
1914 && p->tests->type == DT_code
1915 && ! codemap[code = p->tests->u.code]);
1917 /* If P is testing a predicate that we know about and we haven't
1918 seen any of the codes that are valid for the predicate, we can
1919 write a series of "case" statement, one for each possible code.
1920 Since we are already in a switch, these redundant tests are very
1921 cheap and will reduce the number of predicates called. */
1923 /* Note that while we write out cases for these predicates here,
1924 we don't actually write the test here, as it gets kinda messy.
1925 It is trivial to leave this to later by telling our caller that
1926 we only processed the CODE tests. */
1927 if (needs_label != NULL)
1932 while (p && p->tests->type == DT_pred && p->tests->u.pred.data)
1934 const struct pred_data *data = p->tests->u.pred.data;
1936 for (c = 0; c < NUM_RTX_CODE; c++)
1937 if (codemap[c] && data->codes[c])
1940 for (c = 0; c < NUM_RTX_CODE; c++)
1943 fputs (" case ", stdout);
1945 fputs (":\n", stdout);
1949 printf (" goto L%d;\n", p->number);
1955 /* Make the default case skip the predicates we managed to match. */
1957 printf (" default:\n");
1962 printf (" goto L%d;\n", p->number);
1966 write_afterward (start, start->afterward, " ");
1969 printf (" break;\n");
1974 else if (type == DT_mode
1975 || type == DT_veclen
1976 || type == DT_elt_zero_int
1977 || type == DT_elt_one_int
1978 || type == DT_elt_zero_wide_safe)
1980 const char *indent = "";
1982 /* We cast switch parameter to integer, so we must ensure that the value
1984 if (type == DT_elt_zero_wide_safe)
1987 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1989 printf ("%s switch (", indent);
1993 printf ("GET_MODE (x%d)", depth);
1996 printf ("XVECLEN (x%d, 0)", depth);
1998 case DT_elt_zero_int:
1999 printf ("XINT (x%d, 0)", depth);
2001 case DT_elt_one_int:
2002 printf ("XINT (x%d, 1)", depth);
2004 case DT_elt_zero_wide_safe:
2005 /* Convert result of XWINT to int for portability since some C
2006 compilers won't do it and some will. */
2007 printf ("(int) XWINT (x%d, 0)", depth);
2012 printf (")\n%s {\n", indent);
2016 /* Merge trees will not unify identical nodes if their
2017 sub-nodes are at different levels. Thus we must check
2018 for duplicate cases. */
2020 for (q = start; q != p; q = q->next)
2021 if (nodes_identical_1 (p->tests, q->tests))
2024 if (p != start && p->need_label && needs_label == NULL)
2027 printf ("%s case ", indent);
2031 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
2034 printf ("%d", p->tests->u.veclen);
2036 case DT_elt_zero_int:
2037 case DT_elt_one_int:
2038 case DT_elt_zero_wide:
2039 case DT_elt_zero_wide_safe:
2040 print_host_wide_int (p->tests->u.intval);
2045 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
2046 p->success.first->need_label = 1;
2050 while (p && p->tests->type == type && !p->tests->next);
2053 printf ("%s default:\n%s break;\n%s }\n",
2054 indent, indent, indent);
2056 return needs_label != NULL ? needs_label : p;
2060 /* None of the other tests are amenable. */
2065 /* Emit code for one test. */
2068 write_cond (struct decision_test *p, int depth,
2069 enum routine_type subroutine_type)
2074 printf ("peep2_current_count >= %d", p->u.num_insns);
2078 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
2082 printf ("GET_CODE (x%d) == ", depth);
2083 print_code (p->u.code);
2087 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
2090 case DT_elt_zero_int:
2091 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
2094 case DT_elt_one_int:
2095 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
2098 case DT_elt_zero_wide:
2099 case DT_elt_zero_wide_safe:
2100 printf ("XWINT (x%d, 0) == ", depth);
2101 print_host_wide_int (p->u.intval);
2105 printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
2106 depth, (int) p->u.intval);
2110 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2114 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2118 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2119 GET_MODE_NAME (p->u.pred.mode));
2123 print_c_condition (p->u.c_test);
2126 case DT_accept_insn:
2127 gcc_assert (subroutine_type == RECOG);
2128 gcc_assert (p->u.insn.num_clobbers_to_add);
2129 printf ("pnum_clobbers != NULL");
2137 /* Emit code for one action. The previous tests have succeeded;
2138 TEST is the last of the chain. In the normal case we simply
2139 perform a state change. For the `accept' tests we must do more work. */
2142 write_action (struct decision *p, struct decision_test *test,
2143 int depth, int uncond, struct decision *success,
2144 enum routine_type subroutine_type)
2151 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2153 fputs (" {\n", stdout);
2160 if (test->type == DT_accept_op)
2162 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2164 /* Only allow DT_accept_insn to follow. */
2168 gcc_assert (test->type == DT_accept_insn);
2172 /* Sanity check that we're now at the end of the list of tests. */
2173 gcc_assert (!test->next);
2175 if (test->type == DT_accept_insn)
2177 switch (subroutine_type)
2180 if (test->u.insn.num_clobbers_to_add != 0)
2181 printf ("%s*pnum_clobbers = %d;\n",
2182 indent, test->u.insn.num_clobbers_to_add);
2183 printf ("%sreturn %d; /* %s */\n", indent,
2184 test->u.insn.code_number,
2185 get_insn_name (test->u.insn.code_number));
2189 printf ("%sreturn gen_split_%d (insn, operands);\n",
2190 indent, test->u.insn.code_number);
2195 int match_len = 0, i;
2197 for (i = strlen (p->position) - 1; i >= 0; --i)
2198 if (ISUPPER (p->position[i]))
2200 match_len = p->position[i] - 'A';
2203 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2204 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2205 indent, test->u.insn.code_number);
2206 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2216 printf("%sgoto L%d;\n", indent, success->number);
2217 success->need_label = 1;
2221 fputs (" }\n", stdout);
2224 /* Return 1 if the test is always true and has no fallthru path. Return -1
2225 if the test does have a fallthru path, but requires that the condition be
2226 terminated. Otherwise return 0 for a normal test. */
2227 /* ??? is_unconditional is a stupid name for a tri-state function. */
2230 is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
2232 if (t->type == DT_accept_op)
2235 if (t->type == DT_accept_insn)
2237 switch (subroutine_type)
2240 return (t->u.insn.num_clobbers_to_add == 0);
2253 /* Emit code for one node -- the conditional and the accompanying action.
2254 Return true if there is no fallthru path. */
2257 write_node (struct decision *p, int depth,
2258 enum routine_type subroutine_type)
2260 struct decision_test *test, *last_test;
2263 /* Scan the tests and simplify comparisons against small
2265 for (test = p->tests; test; test = test->next)
2267 if (test->type == DT_code
2268 && test->u.code == CONST_INT
2270 && test->next->type == DT_elt_zero_wide_safe
2271 && -MAX_SAVED_CONST_INT <= test->next->u.intval
2272 && test->next->u.intval <= MAX_SAVED_CONST_INT)
2274 test->type = DT_const_int;
2275 test->u.intval = test->next->u.intval;
2276 test->next = test->next->next;
2280 last_test = test = p->tests;
2281 uncond = is_unconditional (test, subroutine_type);
2285 write_cond (test, depth, subroutine_type);
2287 while ((test = test->next) != NULL)
2290 if (is_unconditional (test, subroutine_type))
2294 write_cond (test, depth, subroutine_type);
2300 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2305 /* Emit code for all of the sibling nodes of HEAD. */
2308 write_tree_1 (struct decision_head *head, int depth,
2309 enum routine_type subroutine_type)
2311 struct decision *p, *next;
2314 for (p = head->first; p ; p = next)
2316 /* The label for the first element was printed in write_tree. */
2317 if (p != head->first && p->need_label)
2318 OUTPUT_LABEL (" ", p->number);
2320 /* Attempt to write a switch statement for a whole sequence. */
2321 next = write_switch (p, depth);
2326 /* Failed -- fall back and write one node. */
2327 uncond = write_node (p, depth, subroutine_type);
2332 /* Finished with this chain. Close a fallthru path by branching
2333 to the afterward node. */
2335 write_afterward (head->last, head->last->afterward, " ");
2338 /* Write out the decision tree starting at HEAD. PREVPOS is the
2339 position at the node that branched to this node. */
2342 write_tree (struct decision_head *head, const char *prevpos,
2343 enum routine_type type, int initial)
2345 struct decision *p = head->first;
2349 OUTPUT_LABEL (" ", p->number);
2351 if (! initial && p->subroutine_number > 0)
2353 static const char * const name_prefix[] = {
2354 "recog", "split", "peephole2"
2357 static const char * const call_suffix[] = {
2358 ", pnum_clobbers", "", ", _pmatch_len"
2361 /* This node has been broken out into a separate subroutine.
2362 Call it, test the result, and branch accordingly. */
2366 printf (" tem = %s_%d (x0, insn%s);\n",
2367 name_prefix[type], p->subroutine_number, call_suffix[type]);
2368 if (IS_SPLIT (type))
2369 printf (" if (tem != 0)\n return tem;\n");
2371 printf (" if (tem >= 0)\n return tem;\n");
2373 change_state (p->position, p->afterward->position, " ");
2374 printf (" goto L%d;\n", p->afterward->number);
2378 printf (" return %s_%d (x0, insn%s);\n",
2379 name_prefix[type], p->subroutine_number, call_suffix[type]);
2384 int depth = strlen (p->position);
2386 change_state (prevpos, p->position, " ");
2387 write_tree_1 (head, depth, type);
2389 for (p = head->first; p; p = p->next)
2390 if (p->success.first)
2391 write_tree (&p->success, p->position, type, 0);
2395 /* Write out a subroutine of type TYPE to do comparisons starting at
2399 write_subroutine (struct decision_head *head, enum routine_type type)
2401 int subfunction = head->first ? head->first->subroutine_number : 0;
2406 s_or_e = subfunction ? "static " : "";
2409 sprintf (extension, "_%d", subfunction);
2410 else if (type == RECOG)
2411 extension[0] = '\0';
2413 strcpy (extension, "_insns");
2419 recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
2423 split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
2428 peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
2433 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2434 for (i = 1; i <= max_depth; i++)
2435 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2437 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2440 printf (" recog_data.insn = NULL_RTX;\n");
2443 write_tree (head, "", type, 1);
2445 printf (" goto ret0;\n");
2447 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2450 /* In break_out_subroutines, we discovered the boundaries for the
2451 subroutines, but did not write them out. Do so now. */
2454 write_subroutines (struct decision_head *head, enum routine_type type)
2458 for (p = head->first; p ; p = p->next)
2459 if (p->success.first)
2460 write_subroutines (&p->success, type);
2462 if (head->first->subroutine_number > 0)
2463 write_subroutine (head, type);
2466 /* Begin the output file. */
2472 /* Generated automatically by the program `genrecog' from the target\n\
2473 machine description file. */\n\
2475 #include \"config.h\"\n\
2476 #include \"system.h\"\n\
2477 #include \"coretypes.h\"\n\
2478 #include \"tm.h\"\n\
2479 #include \"rtl.h\"\n\
2480 #include \"tm_p.h\"\n\
2481 #include \"function.h\"\n\
2482 #include \"insn-config.h\"\n\
2483 #include \"recog.h\"\n\
2484 #include \"real.h\"\n\
2485 #include \"output.h\"\n\
2486 #include \"flags.h\"\n\
2487 #include \"hard-reg-set.h\"\n\
2488 #include \"resource.h\"\n\
2489 #include \"toplev.h\"\n\
2490 #include \"reload.h\"\n\
2494 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2495 X0 is a valid instruction.\n\
2497 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2498 returns a nonnegative number which is the insn code number for the\n\
2499 pattern that matched. This is the same as the order in the machine\n\
2500 description of the entry that matched. This number can be used as an\n\
2501 index into `insn_data' and other tables.\n");
2503 The third argument to recog is an optional pointer to an int. If\n\
2504 present, recog will accept a pattern if it matches except for missing\n\
2505 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2506 the optional pointer will be set to the number of CLOBBERs that need\n\
2507 to be added (it should be initialized to zero by the caller). If it");
2509 is set nonzero, the caller should allocate a PARALLEL of the\n\
2510 appropriate size, copy the initial entries, and call add_clobbers\n\
2511 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2515 The function split_insns returns 0 if the rtl could not\n\
2516 be split or the split rtl as an INSN list if it can be.\n\
2518 The function peephole2_insns returns 0 if the rtl could not\n\
2519 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2520 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2525 /* Construct and return a sequence of decisions
2526 that will recognize INSN.
2528 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2530 static struct decision_head
2531 make_insn_sequence (rtx insn, enum routine_type type)
2534 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2535 int truth = maybe_eval_c_test (c_test);
2536 struct decision *last;
2537 struct decision_test *test, **place;
2538 struct decision_head head;
2541 /* We should never see an insn whose C test is false at compile time. */
2544 c_test_pos[0] = '\0';
2545 if (type == PEEPHOLE2)
2549 /* peephole2 gets special treatment:
2550 - X always gets an outer parallel even if it's only one entry
2551 - we remove all traces of outer-level match_scratch and match_dup
2552 expressions here. */
2553 x = rtx_alloc (PARALLEL);
2554 PUT_MODE (x, VOIDmode);
2555 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2556 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2558 rtx tmp = XVECEXP (insn, 0, i);
2559 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2561 XVECEXP (x, 0, j) = tmp;
2567 c_test_pos[0] = 'A' + j - 1;
2568 c_test_pos[1] = '\0';
2570 else if (XVECLEN (insn, type == RECOG) == 1)
2571 x = XVECEXP (insn, type == RECOG, 0);
2574 x = rtx_alloc (PARALLEL);
2575 XVEC (x, 0) = XVEC (insn, type == RECOG);
2576 PUT_MODE (x, VOIDmode);
2579 validate_pattern (x, insn, NULL_RTX, 0);
2581 memset(&head, 0, sizeof(head));
2582 last = add_to_sequence (x, &head, "", type, 1);
2584 /* Find the end of the test chain on the last node. */
2585 for (test = last->tests; test->next; test = test->next)
2587 place = &test->next;
2589 /* Skip the C test if it's known to be true at compile time. */
2592 /* Need a new node if we have another test to add. */
2593 if (test->type == DT_accept_op)
2595 last = new_decision (c_test_pos, &last->success);
2596 place = &last->tests;
2598 test = new_decision_test (DT_c_test, &place);
2599 test->u.c_test = c_test;
2602 test = new_decision_test (DT_accept_insn, &place);
2603 test->u.insn.code_number = next_insn_code;
2604 test->u.insn.lineno = pattern_lineno;
2605 test->u.insn.num_clobbers_to_add = 0;
2610 /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
2611 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2612 If so, set up to recognize the pattern without these CLOBBERs. */
2614 if (GET_CODE (x) == PARALLEL)
2618 /* Find the last non-clobber in the parallel. */
2619 for (i = XVECLEN (x, 0); i > 0; i--)
2621 rtx y = XVECEXP (x, 0, i - 1);
2622 if (GET_CODE (y) != CLOBBER
2623 || (!REG_P (XEXP (y, 0))
2624 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2628 if (i != XVECLEN (x, 0))
2631 struct decision_head clobber_head;
2633 /* Build a similar insn without the clobbers. */
2635 new = XVECEXP (x, 0, 0);
2640 new = rtx_alloc (PARALLEL);
2641 XVEC (new, 0) = rtvec_alloc (i);
2642 for (j = i - 1; j >= 0; j--)
2643 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2647 memset (&clobber_head, 0, sizeof(clobber_head));
2648 last = add_to_sequence (new, &clobber_head, "", type, 1);
2650 /* Find the end of the test chain on the last node. */
2651 for (test = last->tests; test->next; test = test->next)
2654 /* We definitely have a new test to add -- create a new
2656 place = &test->next;
2657 if (test->type == DT_accept_op)
2659 last = new_decision ("", &last->success);
2660 place = &last->tests;
2663 /* Skip the C test if it's known to be true at compile
2667 test = new_decision_test (DT_c_test, &place);
2668 test->u.c_test = c_test;
2671 test = new_decision_test (DT_accept_insn, &place);
2672 test->u.insn.code_number = next_insn_code;
2673 test->u.insn.lineno = pattern_lineno;
2674 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2676 merge_trees (&head, &clobber_head);
2682 /* Define the subroutine we will call below and emit in genemit. */
2683 printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code);
2687 /* Define the subroutine we will call below and emit in genemit. */
2688 printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
2697 process_tree (struct decision_head *head, enum routine_type subroutine_type)
2699 if (head->first == NULL)
2701 /* We can elide peephole2_insns, but not recog or split_insns. */
2702 if (subroutine_type == PEEPHOLE2)
2707 factor_tests (head);
2709 next_subroutine_number = 0;
2710 break_out_subroutines (head, 1);
2711 find_afterward (head, NULL);
2713 /* We run this after find_afterward, because find_afterward needs
2714 the redundant DT_mode tests on predicates to determine whether
2715 two tests can both be true or not. */
2716 simplify_tests(head);
2718 write_subroutines (head, subroutine_type);
2721 write_subroutine (head, subroutine_type);
2724 extern int main (int, char **);
2727 main (int argc, char **argv)
2730 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2732 progname = "genrecog";
2734 memset (&recog_tree, 0, sizeof recog_tree);
2735 memset (&split_tree, 0, sizeof split_tree);
2736 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2738 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2739 return (FATAL_EXIT_CODE);
2745 /* Read the machine description. */
2749 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2753 switch (GET_CODE (desc))
2755 case DEFINE_PREDICATE:
2756 case DEFINE_SPECIAL_PREDICATE:
2757 process_define_predicate (desc);
2761 h = make_insn_sequence (desc, RECOG);
2762 merge_trees (&recog_tree, &h);
2766 h = make_insn_sequence (desc, SPLIT);
2767 merge_trees (&split_tree, &h);
2770 case DEFINE_PEEPHOLE2:
2771 h = make_insn_sequence (desc, PEEPHOLE2);
2772 merge_trees (&peephole2_tree, &h);
2779 if (error_count || have_error)
2780 return FATAL_EXIT_CODE;
2784 process_tree (&recog_tree, RECOG);
2785 process_tree (&split_tree, SPLIT);
2786 process_tree (&peephole2_tree, PEEPHOLE2);
2789 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2793 debug_decision_2 (struct decision_test *test)
2798 fprintf (stderr, "num_insns=%d", test->u.num_insns);
2801 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2804 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2807 fprintf (stderr, "veclen=%d", test->u.veclen);
2809 case DT_elt_zero_int:
2810 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2812 case DT_elt_one_int:
2813 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2815 case DT_elt_zero_wide:
2816 fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2818 case DT_elt_zero_wide_safe:
2819 fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2822 fprintf (stderr, "veclen>=%d", test->u.veclen);
2825 fprintf (stderr, "dup=%d", test->u.dup);
2828 fprintf (stderr, "pred=(%s,%s)",
2829 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2834 strncpy (sub, test->u.c_test, sizeof(sub));
2835 memcpy (sub+16, "...", 4);
2836 fprintf (stderr, "c_test=\"%s\"", sub);
2840 fprintf (stderr, "A_op=%d", test->u.opno);
2842 case DT_accept_insn:
2843 fprintf (stderr, "A_insn=(%d,%d)",
2844 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2853 debug_decision_1 (struct decision *d, int indent)
2856 struct decision_test *test;
2860 for (i = 0; i < indent; ++i)
2862 fputs ("(nil)\n", stderr);
2866 for (i = 0; i < indent; ++i)
2873 debug_decision_2 (test);
2874 while ((test = test->next) != NULL)
2876 fputs (" + ", stderr);
2877 debug_decision_2 (test);
2880 fprintf (stderr, "} %d n %d a %d\n", d->number,
2881 (d->next ? d->next->number : -1),
2882 (d->afterward ? d->afterward->number : -1));
2886 debug_decision_0 (struct decision *d, int indent, int maxdepth)
2895 for (i = 0; i < indent; ++i)
2897 fputs ("(nil)\n", stderr);
2901 debug_decision_1 (d, indent);
2902 for (n = d->success.first; n ; n = n->next)
2903 debug_decision_0 (n, indent + 2, maxdepth - 1);
2907 debug_decision (struct decision *d)
2909 debug_decision_0 (d, 0, 1000000);
2913 debug_decision_list (struct decision *d)
2917 debug_decision_0 (d, 0, 0);