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, 2007, 2008, 2009, 2010
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
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"
60 #include "gensupport.h"
62 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
63 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
65 /* Ways of obtaining an rtx to be tested. */
67 /* PATTERN (peep2_next_insn (ARG)). */
70 /* XEXP (BASE, ARG). */
73 /* XVECEXP (BASE, 0, ARG). */
77 /* The position of an rtx relative to X0. Each useful position is
78 represented by exactly one instance of this structure. */
81 /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
82 struct position *base;
84 /* A position with the same BASE and TYPE, but with the next value
86 struct position *next;
88 /* A list of all POS_XEXP positions that use this one as their base,
89 chained by NEXT fields. The first entry represents XEXP (this, 0),
90 the second represents XEXP (this, 1), and so on. */
91 struct position *xexps;
93 /* A list of POS_XVECEXP0 positions that use this one as their base,
94 chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0),
95 the second represents XVECEXP (this, 0, 1), and so on. */
96 struct position *xvecexp0s;
98 /* The type of position. */
99 enum position_type type;
101 /* The argument to TYPE (shown as ARG in the position_type comments). */
104 /* The depth of this position, with 0 as the root. */
108 /* A listhead of decision trees. The alternatives to a node are kept
109 in a doubly-linked list so we can easily add nodes to the proper
110 place when merging. */
114 struct decision *first;
115 struct decision *last;
118 /* These types are roughly in the order in which we'd like to test them. */
122 DT_mode, DT_code, DT_veclen,
123 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
125 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
126 DT_accept_op, DT_accept_insn
129 /* A single test. The two accept types aren't tests per-se, but
130 their equality (or lack thereof) does affect tree merging so
131 it is convenient to keep them here. */
135 /* A linked list through the tests attached to a node. */
136 struct decision_test *next;
138 enum decision_type type;
142 int num_insns; /* Number if insn in a define_peephole2. */
143 enum machine_mode mode; /* Machine mode of node. */
144 RTX_CODE code; /* Code to test. */
148 const char *name; /* Predicate to call. */
149 const struct pred_data *data;
150 /* Optimization hints for this predicate. */
151 enum machine_mode mode; /* Machine mode for node. */
154 const char *c_test; /* Additional test to perform. */
155 int veclen; /* Length of vector. */
156 int dup; /* Number of operand to compare against. */
157 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
158 int opno; /* Operand number matched. */
161 int code_number; /* Insn number matched. */
162 int lineno; /* Line number of the insn. */
163 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
168 /* Data structure for decision tree for recognizing legitimate insns. */
172 struct decision_head success; /* Nodes to test on success. */
173 struct decision *next; /* Node to test on failure. */
174 struct decision *prev; /* Node whose failure tests us. */
175 struct decision *afterward; /* Node to test on success,
176 but failure of successor nodes. */
178 struct position *position; /* Position in pattern. */
180 struct decision_test *tests; /* The tests for this node. */
182 int number; /* Node number, used for labels */
183 int subroutine_number; /* Number of subroutine this node starts */
184 int need_label; /* Label needs to be output. */
187 #define SUBROUTINE_THRESHOLD 100
189 static int next_subroutine_number;
191 /* We can write three types of subroutines: One for insn recognition,
192 one to split insns, and one for peephole-type optimizations. This
193 defines which type is being written. */
196 RECOG, SPLIT, PEEPHOLE2
199 #define IS_SPLIT(X) ((X) != RECOG)
201 /* Next available node number for tree nodes. */
203 static int next_number;
205 /* Next number to use as an insn_code. */
207 static int next_insn_code;
209 /* Record the highest depth we ever have so we know how many variables to
210 allocate in each subroutine we make. */
212 static int max_depth;
214 /* The line number of the start of the pattern currently being processed. */
215 static int pattern_lineno;
217 /* The root position (x0). */
218 static struct position root_pos;
220 /* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
221 since we are given that instruction's pattern as x0. */
222 static struct position *peep2_insn_pos_list = &root_pos;
224 static struct decision *new_decision
225 (struct position *, struct decision_head *);
226 static struct decision_test *new_decision_test
227 (enum decision_type, struct decision_test ***);
228 static rtx find_operand
230 static rtx find_matching_operand
232 static void validate_pattern
233 (rtx, rtx, rtx, int);
234 static struct decision *add_to_sequence
235 (rtx, struct decision_head *, struct position *, enum routine_type, int);
237 static int maybe_both_true_2
238 (struct decision_test *, struct decision_test *);
239 static int maybe_both_true_1
240 (struct decision_test *, struct decision_test *);
241 static int maybe_both_true
242 (struct decision *, struct decision *, int);
244 static int nodes_identical_1
245 (struct decision_test *, struct decision_test *);
246 static int nodes_identical
247 (struct decision *, struct decision *);
248 static void merge_accept_insn
249 (struct decision *, struct decision *);
250 static void merge_trees
251 (struct decision_head *, struct decision_head *);
253 static void factor_tests
254 (struct decision_head *);
255 static void simplify_tests
256 (struct decision_head *);
257 static int break_out_subroutines
258 (struct decision_head *, int);
259 static void find_afterward
260 (struct decision_head *, struct decision *);
262 static void change_state
263 (struct position *, struct position *, const char *);
264 static void print_code
266 static void write_afterward
267 (struct decision *, struct decision *, const char *);
268 static struct decision *write_switch
269 (struct decision *, int);
270 static void write_cond
271 (struct decision_test *, int, enum routine_type);
272 static void write_action
273 (struct decision *, struct decision_test *, int, int,
274 struct decision *, enum routine_type);
275 static int is_unconditional
276 (struct decision_test *, enum routine_type);
277 static int write_node
278 (struct decision *, int, enum routine_type);
279 static void write_tree_1
280 (struct decision_head *, int, enum routine_type);
281 static void write_tree
282 (struct decision_head *, struct position *, enum routine_type, int);
283 static void write_subroutine
284 (struct decision_head *, enum routine_type);
285 static void write_subroutines
286 (struct decision_head *, enum routine_type);
287 static void write_header
290 static struct decision_head make_insn_sequence
291 (rtx, enum routine_type);
292 static void process_tree
293 (struct decision_head *, enum routine_type);
295 static void debug_decision_0
296 (struct decision *, int, int);
297 static void debug_decision_1
298 (struct decision *, int);
299 static void debug_decision_2
300 (struct decision_test *);
301 extern void debug_decision
303 extern void debug_decision_list
306 /* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
307 points to where the unique object that represents the position
308 should be stored. Create the object if it doesn't already exist,
309 otherwise reuse the object that is already there. */
311 static struct position *
312 next_position (struct position **next_ptr, struct position *base,
313 enum position_type type, int arg)
315 struct position *pos;
320 pos = XCNEW (struct position);
324 pos->depth = base->depth + 1;
330 /* Compare positions POS1 and POS2 lexicographically. */
333 compare_positions (struct position *pos1, struct position *pos2)
337 diff = pos1->depth - pos2->depth;
341 while (pos1->depth != pos2->depth);
345 while (pos1->depth != pos2->depth);
348 diff = (int) pos1->type - (int) pos2->type;
350 diff = pos1->arg - pos2->arg;
357 /* Create a new node in sequence after LAST. */
359 static struct decision *
360 new_decision (struct position *pos, struct decision_head *last)
362 struct decision *new_decision = XCNEW (struct decision);
364 new_decision->success = *last;
365 new_decision->position = pos;
366 new_decision->number = next_number++;
368 last->first = last->last = new_decision;
372 /* Create a new test and link it in at PLACE. */
374 static struct decision_test *
375 new_decision_test (enum decision_type type, struct decision_test ***pplace)
377 struct decision_test **place = *pplace;
378 struct decision_test *test;
380 test = XNEW (struct decision_test);
391 /* Search for and return operand N, stop when reaching node STOP. */
394 find_operand (rtx pattern, int n, rtx stop)
404 code = GET_CODE (pattern);
405 if ((code == MATCH_SCRATCH
406 || code == MATCH_OPERAND
407 || code == MATCH_OPERATOR
408 || code == MATCH_PARALLEL)
409 && XINT (pattern, 0) == n)
412 fmt = GET_RTX_FORMAT (code);
413 len = GET_RTX_LENGTH (code);
414 for (i = 0; i < len; i++)
419 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
424 if (! XVEC (pattern, i))
429 for (j = 0; j < XVECLEN (pattern, i); j++)
430 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
435 case 'i': case 'w': case '0': case 's':
446 /* Search for and return operand M, such that it has a matching
447 constraint for operand N. */
450 find_matching_operand (rtx pattern, int n)
457 code = GET_CODE (pattern);
458 if (code == MATCH_OPERAND
459 && (XSTR (pattern, 2)[0] == '0' + n
460 || (XSTR (pattern, 2)[0] == '%'
461 && XSTR (pattern, 2)[1] == '0' + n)))
464 fmt = GET_RTX_FORMAT (code);
465 len = GET_RTX_LENGTH (code);
466 for (i = 0; i < len; i++)
471 if ((r = find_matching_operand (XEXP (pattern, i), n)))
476 if (! XVEC (pattern, i))
481 for (j = 0; j < XVECLEN (pattern, i); j++)
482 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
486 case 'i': case 'w': case '0': case 's':
498 /* Check for various errors in patterns. SET is nonnull for a destination,
499 and is the complete set pattern. SET_CODE is '=' for normal sets, and
500 '+' within a context that requires in-out constraints. */
503 validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
510 code = GET_CODE (pattern);
518 if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
519 error_with_line (pattern_lineno,
520 "operand %i duplicated before defined",
526 const char *pred_name = XSTR (pattern, 1);
527 const struct pred_data *pred;
530 if (GET_CODE (insn) == DEFINE_INSN)
531 c_test = XSTR (insn, 2);
533 c_test = XSTR (insn, 1);
535 if (pred_name[0] != 0)
537 pred = lookup_predicate (pred_name);
539 message_with_line (pattern_lineno,
540 "warning: unknown predicate '%s'",
546 if (code == MATCH_OPERAND)
548 const char constraints0 = XSTR (pattern, 2)[0];
550 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
551 don't use the MATCH_OPERAND constraint, only the predicate.
552 This is confusing to folks doing new ports, so help them
553 not make the mistake. */
554 if (GET_CODE (insn) == DEFINE_EXPAND
555 || GET_CODE (insn) == DEFINE_SPLIT
556 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
559 message_with_line (pattern_lineno,
560 "warning: constraints not supported in %s",
561 rtx_name[GET_CODE (insn)]);
564 /* A MATCH_OPERAND that is a SET should have an output reload. */
565 else if (set && constraints0)
569 if (constraints0 == '+')
571 /* If we've only got an output reload for this operand,
572 we'd better have a matching input operand. */
573 else if (constraints0 == '='
574 && find_matching_operand (insn, XINT (pattern, 0)))
577 error_with_line (pattern_lineno,
578 "operand %d missing in-out reload",
581 else if (constraints0 != '=' && constraints0 != '+')
582 error_with_line (pattern_lineno,
583 "operand %d missing output reload",
588 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
589 while not likely to occur at runtime, results in less efficient
590 code from insn-recog.c. */
591 if (set && pred && pred->allows_non_lvalue)
592 message_with_line (pattern_lineno,
593 "warning: destination operand %d "
597 /* A modeless MATCH_OPERAND can be handy when we can check for
598 multiple modes in the c_test. In most other cases, it is a
599 mistake. Only DEFINE_INSN is eligible, since SPLIT and
600 PEEP2 can FAIL within the output pattern. Exclude special
601 predicates, which check the mode themselves. Also exclude
602 predicates that allow only constants. Exclude the SET_DEST
603 of a call instruction, as that is a common idiom. */
605 if (GET_MODE (pattern) == VOIDmode
606 && code == MATCH_OPERAND
607 && GET_CODE (insn) == DEFINE_INSN
610 && pred->allows_non_const
611 && strstr (c_test, "operands") == NULL
613 && GET_CODE (set) == SET
614 && GET_CODE (SET_SRC (set)) == CALL))
615 message_with_line (pattern_lineno,
616 "warning: operand %d missing mode?",
623 enum machine_mode dmode, smode;
626 dest = SET_DEST (pattern);
627 src = SET_SRC (pattern);
629 /* STRICT_LOW_PART is a wrapper. Its argument is the real
630 destination, and it's mode should match the source. */
631 if (GET_CODE (dest) == STRICT_LOW_PART)
632 dest = XEXP (dest, 0);
634 /* Find the referent for a DUP. */
636 if (GET_CODE (dest) == MATCH_DUP
637 || GET_CODE (dest) == MATCH_OP_DUP
638 || GET_CODE (dest) == MATCH_PAR_DUP)
639 dest = find_operand (insn, XINT (dest, 0), NULL);
641 if (GET_CODE (src) == MATCH_DUP
642 || GET_CODE (src) == MATCH_OP_DUP
643 || GET_CODE (src) == MATCH_PAR_DUP)
644 src = find_operand (insn, XINT (src, 0), NULL);
646 dmode = GET_MODE (dest);
647 smode = GET_MODE (src);
649 /* The mode of an ADDRESS_OPERAND is the mode of the memory
650 reference, not the mode of the address. */
651 if (GET_CODE (src) == MATCH_OPERAND
652 && ! strcmp (XSTR (src, 1), "address_operand"))
655 /* The operands of a SET must have the same mode unless one
657 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
658 error_with_line (pattern_lineno,
659 "mode mismatch in set: %smode vs %smode",
660 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
662 /* If only one of the operands is VOIDmode, and PC or CC0 is
663 not involved, it's probably a mistake. */
664 else if (dmode != smode
665 && GET_CODE (dest) != PC
666 && GET_CODE (dest) != CC0
667 && GET_CODE (src) != PC
668 && GET_CODE (src) != CC0
669 && !CONST_INT_P (src)
670 && GET_CODE (src) != CALL)
673 which = (dmode == VOIDmode ? "destination" : "source");
674 message_with_line (pattern_lineno,
675 "warning: %s missing a mode?", which);
678 if (dest != SET_DEST (pattern))
679 validate_pattern (dest, insn, pattern, '=');
680 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
681 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
686 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
690 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
691 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
692 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
695 case STRICT_LOW_PART:
696 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
700 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
701 error_with_line (pattern_lineno,
702 "operand to label_ref %smode not VOIDmode",
703 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
710 fmt = GET_RTX_FORMAT (code);
711 len = GET_RTX_LENGTH (code);
712 for (i = 0; i < len; i++)
717 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
721 for (j = 0; j < XVECLEN (pattern, i); j++)
722 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
725 case 'i': case 'w': case '0': case 's':
734 /* Create a chain of nodes to verify that an rtl expression matches
737 LAST is a pointer to the listhead in the previous node in the chain (or
738 in the calling function, for the first node).
740 POSITION is the current position in the insn.
742 INSN_TYPE is the type of insn for which we are emitting code.
744 A pointer to the final node in the chain is returned. */
746 static struct decision *
747 add_to_sequence (rtx pattern, struct decision_head *last,
748 struct position *pos, enum routine_type insn_type, int top)
751 struct decision *this_decision, *sub;
752 struct decision_test *test;
753 struct decision_test **place;
754 struct position *subpos, **subpos_ptr;
758 enum machine_mode mode;
759 enum position_type pos_type;
761 if (pos->depth > max_depth)
762 max_depth = pos->depth;
764 sub = this_decision = new_decision (pos, last);
765 place = &this_decision->tests;
768 mode = GET_MODE (pattern);
769 code = GET_CODE (pattern);
774 /* Toplevel peephole pattern. */
775 if (insn_type == PEEPHOLE2 && top)
779 /* Check we have sufficient insns. This avoids complications
780 because we then know peep2_next_insn never fails. */
781 num_insns = XVECLEN (pattern, 0);
784 test = new_decision_test (DT_num_insns, &place);
785 test->u.num_insns = num_insns;
786 last = &sub->success;
790 /* We don't need the node we just created -- unlink it. */
791 last->first = last->last = NULL;
794 subpos_ptr = &peep2_insn_pos_list;
795 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
797 subpos = next_position (subpos_ptr, &root_pos,
799 sub = add_to_sequence (XVECEXP (pattern, 0, i),
800 last, subpos, insn_type, 0);
801 last = &sub->success;
802 subpos_ptr = &subpos->next;
807 /* Else nothing special. */
811 /* The explicit patterns within a match_parallel enforce a minimum
812 length on the vector. The match_parallel predicate may allow
813 for more elements. We do need to check for this minimum here
814 or the code generated to match the internals may reference data
815 beyond the end of the vector. */
816 test = new_decision_test (DT_veclen_ge, &place);
817 test->u.veclen = XVECLEN (pattern, 2);
824 RTX_CODE was_code = code;
825 const char *pred_name;
826 bool allows_const_int = true;
828 if (code == MATCH_SCRATCH)
830 pred_name = "scratch_operand";
835 pred_name = XSTR (pattern, 1);
836 if (code == MATCH_PARALLEL)
842 if (pred_name[0] != 0)
844 const struct pred_data *pred;
846 test = new_decision_test (DT_pred, &place);
847 test->u.pred.name = pred_name;
848 test->u.pred.mode = mode;
850 /* See if we know about this predicate.
851 If we do, remember it for use below.
853 We can optimize the generated code a little if either
854 (a) the predicate only accepts one code, or (b) the
855 predicate does not allow CONST_INT, in which case it
856 can match only if the modes match. */
857 pred = lookup_predicate (pred_name);
860 test->u.pred.data = pred;
861 allows_const_int = pred->codes[CONST_INT];
862 if (was_code == MATCH_PARALLEL
863 && pred->singleton != PARALLEL)
864 message_with_line (pattern_lineno,
865 "predicate '%s' used in match_parallel "
866 "does not allow only PARALLEL", pred->name);
868 code = pred->singleton;
871 message_with_line (pattern_lineno,
872 "warning: unknown predicate '%s' in '%s' expression",
873 pred_name, GET_RTX_NAME (was_code));
876 /* Can't enforce a mode if we allow const_int. */
877 if (allows_const_int)
880 /* Accept the operand, i.e. record it in `operands'. */
881 test = new_decision_test (DT_accept_op, &place);
882 test->u.opno = XINT (pattern, 0);
884 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
886 if (was_code == MATCH_OPERATOR)
889 subpos_ptr = &pos->xexps;
893 pos_type = POS_XVECEXP0;
894 subpos_ptr = &pos->xvecexp0s;
896 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
898 subpos = next_position (subpos_ptr, pos, pos_type, i);
899 sub = add_to_sequence (XVECEXP (pattern, 2, i),
900 &sub->success, subpos, insn_type, 0);
901 subpos_ptr = &subpos->next;
910 test = new_decision_test (DT_dup, &place);
911 test->u.dup = XINT (pattern, 0);
913 test = new_decision_test (DT_accept_op, &place);
914 test->u.opno = XINT (pattern, 0);
916 subpos_ptr = &pos->xvecexp0s;
917 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
919 subpos = next_position (subpos_ptr, pos, POS_XVECEXP0, i);
920 sub = add_to_sequence (XVECEXP (pattern, 1, i),
921 &sub->success, subpos, insn_type, 0);
922 subpos_ptr = &subpos->next;
930 test = new_decision_test (DT_dup, &place);
931 test->u.dup = XINT (pattern, 0);
935 pattern = XEXP (pattern, 0);
942 fmt = GET_RTX_FORMAT (code);
943 len = GET_RTX_LENGTH (code);
945 /* Do tests against the current node first. */
946 for (i = 0; i < (size_t) len; i++)
954 test = new_decision_test (DT_elt_zero_int, &place);
955 test->u.intval = XINT (pattern, i);
959 test = new_decision_test (DT_elt_one_int, &place);
960 test->u.intval = XINT (pattern, i);
963 else if (fmt[i] == 'w')
965 /* If this value actually fits in an int, we can use a switch
966 statement here, so indicate that. */
967 enum decision_type type
968 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
969 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
973 test = new_decision_test (type, &place);
974 test->u.intval = XWINT (pattern, i);
976 else if (fmt[i] == 'E')
980 test = new_decision_test (DT_veclen, &place);
981 test->u.veclen = XVECLEN (pattern, i);
985 /* Now test our sub-patterns. */
986 subpos_ptr = &pos->xexps;
987 for (i = 0; i < (size_t) len; i++)
989 subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
993 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
994 subpos, insn_type, 0);
999 struct position *subpos2, **subpos2_ptr;
1002 subpos2_ptr = &pos->xvecexp0s;
1003 for (j = 0; j < XVECLEN (pattern, i); j++)
1005 subpos2 = next_position (subpos2_ptr, pos, POS_XVECEXP0, j);
1006 sub = add_to_sequence (XVECEXP (pattern, i, j),
1007 &sub->success, subpos2, insn_type, 0);
1008 subpos2_ptr = &subpos2->next;
1014 /* Handled above. */
1022 subpos_ptr = &subpos->next;
1026 /* Insert nodes testing mode and code, if they're still relevant,
1027 before any of the nodes we may have added above. */
1028 if (code != UNKNOWN)
1030 place = &this_decision->tests;
1031 test = new_decision_test (DT_code, &place);
1032 test->u.code = code;
1035 if (mode != VOIDmode)
1037 place = &this_decision->tests;
1038 test = new_decision_test (DT_mode, &place);
1039 test->u.mode = mode;
1042 /* If we didn't insert any tests or accept nodes, hork. */
1043 gcc_assert (this_decision->tests);
1049 /* A subroutine of maybe_both_true; examines only one test.
1050 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1053 maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
1055 if (d1->type == d2->type)
1060 if (d1->u.num_insns == d2->u.num_insns)
1066 return d1->u.mode == d2->u.mode;
1069 return d1->u.code == d2->u.code;
1072 return d1->u.veclen == d2->u.veclen;
1074 case DT_elt_zero_int:
1075 case DT_elt_one_int:
1076 case DT_elt_zero_wide:
1077 case DT_elt_zero_wide_safe:
1078 return d1->u.intval == d2->u.intval;
1085 /* If either has a predicate that we know something about, set
1086 things up so that D1 is the one that always has a known
1087 predicate. Then see if they have any codes in common. */
1089 if (d1->type == DT_pred || d2->type == DT_pred)
1091 if (d2->type == DT_pred)
1093 struct decision_test *tmp;
1094 tmp = d1, d1 = d2, d2 = tmp;
1097 /* If D2 tests a mode, see if it matches D1. */
1098 if (d1->u.pred.mode != VOIDmode)
1100 if (d2->type == DT_mode)
1102 if (d1->u.pred.mode != d2->u.mode
1103 /* The mode of an address_operand predicate is the
1104 mode of the memory, not the operand. It can only
1105 be used for testing the predicate, so we must
1107 && strcmp (d1->u.pred.name, "address_operand") != 0)
1110 /* Don't check two predicate modes here, because if both predicates
1111 accept CONST_INT, then both can still be true even if the modes
1112 are different. If they don't accept CONST_INT, there will be a
1113 separate DT_mode that will make maybe_both_true_1 return 0. */
1116 if (d1->u.pred.data)
1118 /* If D2 tests a code, see if it is in the list of valid
1119 codes for D1's predicate. */
1120 if (d2->type == DT_code)
1122 if (!d1->u.pred.data->codes[d2->u.code])
1126 /* Otherwise see if the predicates have any codes in common. */
1127 else if (d2->type == DT_pred && d2->u.pred.data)
1129 bool common = false;
1132 for (c = 0; c < NUM_RTX_CODE; c++)
1133 if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c])
1145 /* Tests vs veclen may be known when strict equality is involved. */
1146 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1147 return d1->u.veclen >= d2->u.veclen;
1148 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1149 return d2->u.veclen >= d1->u.veclen;
1154 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1155 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1158 maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
1160 struct decision_test *t1, *t2;
1162 /* A match_operand with no predicate can match anything. Recognize
1163 this by the existence of a lone DT_accept_op test. */
1164 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1167 /* Eliminate pairs of tests while they can exactly match. */
1168 while (d1 && d2 && d1->type == d2->type)
1170 if (maybe_both_true_2 (d1, d2) == 0)
1172 d1 = d1->next, d2 = d2->next;
1175 /* After that, consider all pairs. */
1176 for (t1 = d1; t1 ; t1 = t1->next)
1177 for (t2 = d2; t2 ; t2 = t2->next)
1178 if (maybe_both_true_2 (t1, t2) == 0)
1184 /* Return 0 if we can prove that there is no RTL that can match both
1185 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1186 can match both or just that we couldn't prove there wasn't such an RTL).
1188 TOPLEVEL is nonzero if we are to only look at the top level and not
1189 recursively descend. */
1192 maybe_both_true (struct decision *d1, struct decision *d2,
1195 struct decision *p1, *p2;
1198 /* Don't compare strings on the different positions in insn. Doing so
1199 is incorrect and results in false matches from constructs like
1201 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1202 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1204 [(set (match_operand:HI "register_operand" "r")
1205 (match_operand:HI "register_operand" "r"))]
1207 If we are presented with such, we are recursing through the remainder
1208 of a node's success nodes (from the loop at the end of this function).
1209 Skip forward until we come to a position that matches.
1211 Due to the way positions are constructed, we know that iterating
1212 forward from the lexically lower position will run into the lexically
1213 higher position and not the other way around. This saves a bit
1216 cmp = compare_positions (d1->position, d2->position);
1219 gcc_assert (!toplevel);
1221 /* If the d2->position was lexically lower, swap. */
1223 p1 = d1, d1 = d2, d2 = p1;
1225 if (d1->success.first == 0)
1227 for (p1 = d1->success.first; p1; p1 = p1->next)
1228 if (maybe_both_true (p1, d2, 0))
1234 /* Test the current level. */
1235 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1239 /* We can't prove that D1 and D2 cannot both be true. If we are only
1240 to check the top level, return 1. Otherwise, see if we can prove
1241 that all choices in both successors are mutually exclusive. If
1242 either does not have any successors, we can't prove they can't both
1245 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1248 for (p1 = d1->success.first; p1; p1 = p1->next)
1249 for (p2 = d2->success.first; p2; p2 = p2->next)
1250 if (maybe_both_true (p1, p2, 0))
1256 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1259 nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
1264 return d1->u.num_insns == d2->u.num_insns;
1267 return d1->u.mode == d2->u.mode;
1270 return d1->u.code == d2->u.code;
1273 return (d1->u.pred.mode == d2->u.pred.mode
1274 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1277 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1281 return d1->u.veclen == d2->u.veclen;
1284 return d1->u.dup == d2->u.dup;
1286 case DT_elt_zero_int:
1287 case DT_elt_one_int:
1288 case DT_elt_zero_wide:
1289 case DT_elt_zero_wide_safe:
1290 return d1->u.intval == d2->u.intval;
1293 return d1->u.opno == d2->u.opno;
1295 case DT_accept_insn:
1296 /* Differences will be handled in merge_accept_insn. */
1304 /* True iff the two nodes are identical (on one level only). Due
1305 to the way these lists are constructed, we shouldn't have to
1306 consider different orderings on the tests. */
1309 nodes_identical (struct decision *d1, struct decision *d2)
1311 struct decision_test *t1, *t2;
1313 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1315 if (t1->type != t2->type)
1317 if (! nodes_identical_1 (t1, t2))
1321 /* For success, they should now both be null. */
1325 /* Check that their subnodes are at the same position, as any one set
1326 of sibling decisions must be at the same position. Allowing this
1327 requires complications to find_afterward and when change_state is
1329 if (d1->success.first
1330 && d2->success.first
1331 && d1->success.first->position != d2->success.first->position)
1337 /* A subroutine of merge_trees; given two nodes that have been declared
1338 identical, cope with two insn accept states. If they differ in the
1339 number of clobbers, then the conflict was created by make_insn_sequence
1340 and we can drop the with-clobbers version on the floor. If both
1341 nodes have no additional clobbers, we have found an ambiguity in the
1342 source machine description. */
1345 merge_accept_insn (struct decision *oldd, struct decision *addd)
1347 struct decision_test *old, *add;
1349 for (old = oldd->tests; old; old = old->next)
1350 if (old->type == DT_accept_insn)
1355 for (add = addd->tests; add; add = add->next)
1356 if (add->type == DT_accept_insn)
1361 /* If one node is for a normal insn and the second is for the base
1362 insn with clobbers stripped off, the second node should be ignored. */
1364 if (old->u.insn.num_clobbers_to_add == 0
1365 && add->u.insn.num_clobbers_to_add > 0)
1367 /* Nothing to do here. */
1369 else if (old->u.insn.num_clobbers_to_add > 0
1370 && add->u.insn.num_clobbers_to_add == 0)
1372 /* In this case, replace OLD with ADD. */
1373 old->u.insn = add->u.insn;
1377 error_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1378 get_insn_name (add->u.insn.code_number),
1379 get_insn_name (old->u.insn.code_number));
1380 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1381 get_insn_name (old->u.insn.code_number));
1385 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1388 merge_trees (struct decision_head *oldh, struct decision_head *addh)
1390 struct decision *next, *add;
1392 if (addh->first == 0)
1394 if (oldh->first == 0)
1400 /* Trying to merge bits at different positions isn't possible. */
1401 gcc_assert (oldh->first->position == addh->first->position);
1403 for (add = addh->first; add ; add = next)
1405 struct decision *old, *insert_before = NULL;
1409 /* The semantics of pattern matching state that the tests are
1410 done in the order given in the MD file so that if an insn
1411 matches two patterns, the first one will be used. However,
1412 in practice, most, if not all, patterns are unambiguous so
1413 that their order is independent. In that case, we can merge
1414 identical tests and group all similar modes and codes together.
1416 Scan starting from the end of OLDH until we reach a point
1417 where we reach the head of the list or where we pass a
1418 pattern that could also be true if NEW is true. If we find
1419 an identical pattern, we can merge them. Also, record the
1420 last node that tests the same code and mode and the last one
1421 that tests just the same mode.
1423 If we have no match, place NEW after the closest match we found. */
1425 for (old = oldh->last; old; old = old->prev)
1427 if (nodes_identical (old, add))
1429 merge_accept_insn (old, add);
1430 merge_trees (&old->success, &add->success);
1434 if (maybe_both_true (old, add, 0))
1437 /* Insert the nodes in DT test type order, which is roughly
1438 how expensive/important the test is. Given that the tests
1439 are also ordered within the list, examining the first is
1441 if ((int) add->tests->type < (int) old->tests->type)
1442 insert_before = old;
1445 if (insert_before == NULL)
1448 add->prev = oldh->last;
1449 oldh->last->next = add;
1454 if ((add->prev = insert_before->prev) != NULL)
1455 add->prev->next = add;
1458 add->next = insert_before;
1459 insert_before->prev = add;
1466 /* Walk the tree looking for sub-nodes that perform common tests.
1467 Factor out the common test into a new node. This enables us
1468 (depending on the test type) to emit switch statements later. */
1471 factor_tests (struct decision_head *head)
1473 struct decision *first, *next;
1475 for (first = head->first; first && first->next; first = next)
1477 enum decision_type type;
1478 struct decision *new_dec, *old_last;
1480 type = first->tests->type;
1483 /* Want at least two compatible sequential nodes. */
1484 if (next->tests->type != type)
1487 /* Don't want all node types, just those we can turn into
1488 switch statements. */
1491 && type != DT_veclen
1492 && type != DT_elt_zero_int
1493 && type != DT_elt_one_int
1494 && type != DT_elt_zero_wide_safe)
1497 /* If we'd been performing more than one test, create a new node
1498 below our first test. */
1499 if (first->tests->next != NULL)
1501 new_dec = new_decision (first->position, &first->success);
1502 new_dec->tests = first->tests->next;
1503 first->tests->next = NULL;
1506 /* Crop the node tree off after our first test. */
1508 old_last = head->last;
1511 /* For each compatible test, adjust to perform only one test in
1512 the top level node, then merge the node back into the tree. */
1515 struct decision_head h;
1517 if (next->tests->next != NULL)
1519 new_dec = new_decision (next->position, &next->success);
1520 new_dec->tests = next->tests->next;
1521 next->tests->next = NULL;
1525 new_dec->next = NULL;
1526 h.first = h.last = new_dec;
1528 merge_trees (head, &h);
1530 while (next && next->tests->type == type);
1532 /* After we run out of compatible tests, graft the remaining nodes
1533 back onto the tree. */
1536 next->prev = head->last;
1537 head->last->next = next;
1538 head->last = old_last;
1543 for (first = head->first; first; first = first->next)
1544 factor_tests (&first->success);
1547 /* After factoring, try to simplify the tests on any one node.
1548 Tests that are useful for switch statements are recognizable
1549 by having only a single test on a node -- we'll be manipulating
1550 nodes with multiple tests:
1552 If we have mode tests or code tests that are redundant with
1553 predicates, remove them. */
1556 simplify_tests (struct decision_head *head)
1558 struct decision *tree;
1560 for (tree = head->first; tree; tree = tree->next)
1562 struct decision_test *a, *b;
1569 /* Find a predicate node. */
1570 while (b && b->type != DT_pred)
1574 /* Due to how these tests are constructed, we don't even need
1575 to check that the mode and code are compatible -- they were
1576 generated from the predicate in the first place. */
1577 while (a->type == DT_mode || a->type == DT_code)
1584 for (tree = head->first; tree; tree = tree->next)
1585 simplify_tests (&tree->success);
1588 /* Count the number of subnodes of HEAD. If the number is high enough,
1589 make the first node in HEAD start a separate subroutine in the C code
1590 that is generated. */
1593 break_out_subroutines (struct decision_head *head, int initial)
1596 struct decision *sub;
1598 for (sub = head->first; sub; sub = sub->next)
1599 size += 1 + break_out_subroutines (&sub->success, 0);
1601 if (size > SUBROUTINE_THRESHOLD && ! initial)
1603 head->first->subroutine_number = ++next_subroutine_number;
1609 /* For each node p, find the next alternative that might be true
1613 find_afterward (struct decision_head *head, struct decision *real_afterward)
1615 struct decision *p, *q, *afterward;
1617 /* We can't propagate alternatives across subroutine boundaries.
1618 This is not incorrect, merely a minor optimization loss. */
1621 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1623 for ( ; p ; p = p->next)
1625 /* Find the next node that might be true if this one fails. */
1626 for (q = p->next; q ; q = q->next)
1627 if (maybe_both_true (p, q, 1))
1630 /* If we reached the end of the list without finding one,
1631 use the incoming afterward position. */
1640 for (p = head->first; p ; p = p->next)
1641 if (p->success.first)
1642 find_afterward (&p->success, p->afterward);
1644 /* When we are generating a subroutine, record the real afterward
1645 position in the first node where write_tree can find it, and we
1646 can do the right thing at the subroutine call site. */
1648 if (p->subroutine_number > 0)
1649 p->afterward = real_afterward;
1652 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1653 actions are necessary to move to NEWPOS. If we fail to move to the
1654 new state, branch to node AFTERWARD if nonzero, otherwise return.
1656 Failure to move to the new state can only occur if we are trying to
1657 match multiple insns and we try to step past the end of the stream. */
1660 change_state (struct position *oldpos, struct position *newpos,
1663 while (oldpos->depth > newpos->depth)
1664 oldpos = oldpos->base;
1666 if (oldpos != newpos)
1667 switch (newpos->type)
1669 case POS_PEEP2_INSN:
1670 printf ("%stem = peep2_next_insn (%d);\n", indent, newpos->arg);
1671 printf ("%sx%d = PATTERN (tem);\n", indent, newpos->depth);
1675 change_state (oldpos, newpos->base, indent);
1676 printf ("%sx%d = XEXP (x%d, %d);\n",
1677 indent, newpos->depth, newpos->depth - 1, newpos->arg);
1681 change_state (oldpos, newpos->base, indent);
1682 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1683 indent, newpos->depth, newpos->depth - 1, newpos->arg);
1688 /* Print the enumerator constant for CODE -- the upcase version of
1692 print_code (enum rtx_code code)
1695 for (p = GET_RTX_NAME (code); *p; p++)
1696 putchar (TOUPPER (*p));
1699 /* Emit code to cross an afterward link -- change state and branch. */
1702 write_afterward (struct decision *start, struct decision *afterward,
1705 if (!afterward || start->subroutine_number > 0)
1706 printf("%sgoto ret0;\n", indent);
1709 change_state (start->position, afterward->position, indent);
1710 printf ("%sgoto L%d;\n", indent, afterward->number);
1714 /* Emit a HOST_WIDE_INT as an integer constant expression. We need to take
1715 special care to avoid "decimal constant is so large that it is unsigned"
1716 warnings in the resulting code. */
1719 print_host_wide_int (HOST_WIDE_INT val)
1721 HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
1723 printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
1725 printf (HOST_WIDE_INT_PRINT_DEC_C, val);
1728 /* Emit a switch statement, if possible, for an initial sequence of
1729 nodes at START. Return the first node yet untested. */
1731 static struct decision *
1732 write_switch (struct decision *start, int depth)
1734 struct decision *p = start;
1735 enum decision_type type = p->tests->type;
1736 struct decision *needs_label = NULL;
1738 /* If we have two or more nodes in sequence that test the same one
1739 thing, we may be able to use a switch statement. */
1743 || p->next->tests->type != type
1744 || p->next->tests->next
1745 || nodes_identical_1 (p->tests, p->next->tests))
1748 /* DT_code is special in that we can do interesting things with
1749 known predicates at the same time. */
1750 if (type == DT_code)
1752 char codemap[NUM_RTX_CODE];
1753 struct decision *ret;
1756 memset (codemap, 0, sizeof(codemap));
1758 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1759 code = p->tests->u.code;
1762 if (p != start && p->need_label && needs_label == NULL)
1767 printf (":\n goto L%d;\n", p->success.first->number);
1768 p->success.first->need_label = 1;
1775 && p->tests->type == DT_code
1776 && ! codemap[code = p->tests->u.code]);
1778 /* If P is testing a predicate that we know about and we haven't
1779 seen any of the codes that are valid for the predicate, we can
1780 write a series of "case" statement, one for each possible code.
1781 Since we are already in a switch, these redundant tests are very
1782 cheap and will reduce the number of predicates called. */
1784 /* Note that while we write out cases for these predicates here,
1785 we don't actually write the test here, as it gets kinda messy.
1786 It is trivial to leave this to later by telling our caller that
1787 we only processed the CODE tests. */
1788 if (needs_label != NULL)
1793 while (p && p->tests->type == DT_pred && p->tests->u.pred.data)
1795 const struct pred_data *data = p->tests->u.pred.data;
1798 for (c = 0; c < NUM_RTX_CODE; c++)
1799 if (codemap[c] && data->codes[c])
1802 for (c = 0; c < NUM_RTX_CODE; c++)
1805 fputs (" case ", stdout);
1806 print_code ((enum rtx_code) c);
1807 fputs (":\n", stdout);
1811 printf (" goto L%d;\n", p->number);
1817 /* Make the default case skip the predicates we managed to match. */
1819 printf (" default:\n");
1824 printf (" goto L%d;\n", p->number);
1828 write_afterward (start, start->afterward, " ");
1831 printf (" break;\n");
1836 else if (type == DT_mode
1837 || type == DT_veclen
1838 || type == DT_elt_zero_int
1839 || type == DT_elt_one_int
1840 || type == DT_elt_zero_wide_safe)
1842 const char *indent = "";
1844 /* We cast switch parameter to integer, so we must ensure that the value
1846 if (type == DT_elt_zero_wide_safe)
1849 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1851 printf ("%s switch (", indent);
1855 printf ("GET_MODE (x%d)", depth);
1858 printf ("XVECLEN (x%d, 0)", depth);
1860 case DT_elt_zero_int:
1861 printf ("XINT (x%d, 0)", depth);
1863 case DT_elt_one_int:
1864 printf ("XINT (x%d, 1)", depth);
1866 case DT_elt_zero_wide_safe:
1867 /* Convert result of XWINT to int for portability since some C
1868 compilers won't do it and some will. */
1869 printf ("(int) XWINT (x%d, 0)", depth);
1874 printf (")\n%s {\n", indent);
1878 /* Merge trees will not unify identical nodes if their
1879 sub-nodes are at different levels. Thus we must check
1880 for duplicate cases. */
1882 for (q = start; q != p; q = q->next)
1883 if (nodes_identical_1 (p->tests, q->tests))
1886 if (p != start && p->need_label && needs_label == NULL)
1889 printf ("%s case ", indent);
1893 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1896 printf ("%d", p->tests->u.veclen);
1898 case DT_elt_zero_int:
1899 case DT_elt_one_int:
1900 case DT_elt_zero_wide:
1901 case DT_elt_zero_wide_safe:
1902 print_host_wide_int (p->tests->u.intval);
1907 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1908 p->success.first->need_label = 1;
1912 while (p && p->tests->type == type && !p->tests->next);
1915 printf ("%s default:\n%s break;\n%s }\n",
1916 indent, indent, indent);
1918 return needs_label != NULL ? needs_label : p;
1922 /* None of the other tests are amenable. */
1927 /* Emit code for one test. */
1930 write_cond (struct decision_test *p, int depth,
1931 enum routine_type subroutine_type)
1936 printf ("peep2_current_count >= %d", p->u.num_insns);
1940 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1944 printf ("GET_CODE (x%d) == ", depth);
1945 print_code (p->u.code);
1949 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1952 case DT_elt_zero_int:
1953 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1956 case DT_elt_one_int:
1957 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1960 case DT_elt_zero_wide:
1961 case DT_elt_zero_wide_safe:
1962 printf ("XWINT (x%d, 0) == ", depth);
1963 print_host_wide_int (p->u.intval);
1967 printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
1968 depth, (int) p->u.intval);
1972 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
1976 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1980 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1981 GET_MODE_NAME (p->u.pred.mode));
1985 print_c_condition (p->u.c_test);
1988 case DT_accept_insn:
1989 gcc_assert (subroutine_type == RECOG);
1990 gcc_assert (p->u.insn.num_clobbers_to_add);
1991 printf ("pnum_clobbers != NULL");
1999 /* Emit code for one action. The previous tests have succeeded;
2000 TEST is the last of the chain. In the normal case we simply
2001 perform a state change. For the `accept' tests we must do more work. */
2004 write_action (struct decision *p, struct decision_test *test,
2005 int depth, int uncond, struct decision *success,
2006 enum routine_type subroutine_type)
2013 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2015 fputs (" {\n", stdout);
2022 if (test->type == DT_accept_op)
2024 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2026 /* Only allow DT_accept_insn to follow. */
2030 gcc_assert (test->type == DT_accept_insn);
2034 /* Sanity check that we're now at the end of the list of tests. */
2035 gcc_assert (!test->next);
2037 if (test->type == DT_accept_insn)
2039 switch (subroutine_type)
2042 if (test->u.insn.num_clobbers_to_add != 0)
2043 printf ("%s*pnum_clobbers = %d;\n",
2044 indent, test->u.insn.num_clobbers_to_add);
2045 printf ("%sreturn %d; /* %s */\n", indent,
2046 test->u.insn.code_number,
2047 get_insn_name (test->u.insn.code_number));
2051 printf ("%sreturn gen_split_%d (insn, operands);\n",
2052 indent, test->u.insn.code_number);
2058 struct position *pos;
2060 for (pos = p->position; pos; pos = pos->base)
2061 if (pos->type == POS_PEEP2_INSN)
2063 match_len = pos->arg;
2066 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2067 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2068 indent, test->u.insn.code_number);
2069 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2079 printf("%sgoto L%d;\n", indent, success->number);
2080 success->need_label = 1;
2084 fputs (" }\n", stdout);
2087 /* Return 1 if the test is always true and has no fallthru path. Return -1
2088 if the test does have a fallthru path, but requires that the condition be
2089 terminated. Otherwise return 0 for a normal test. */
2090 /* ??? is_unconditional is a stupid name for a tri-state function. */
2093 is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
2095 if (t->type == DT_accept_op)
2098 if (t->type == DT_accept_insn)
2100 switch (subroutine_type)
2103 return (t->u.insn.num_clobbers_to_add == 0);
2116 /* Emit code for one node -- the conditional and the accompanying action.
2117 Return true if there is no fallthru path. */
2120 write_node (struct decision *p, int depth,
2121 enum routine_type subroutine_type)
2123 struct decision_test *test, *last_test;
2126 /* Scan the tests and simplify comparisons against small
2128 for (test = p->tests; test; test = test->next)
2130 if (test->type == DT_code
2131 && test->u.code == CONST_INT
2133 && test->next->type == DT_elt_zero_wide_safe
2134 && -MAX_SAVED_CONST_INT <= test->next->u.intval
2135 && test->next->u.intval <= MAX_SAVED_CONST_INT)
2137 test->type = DT_const_int;
2138 test->u.intval = test->next->u.intval;
2139 test->next = test->next->next;
2143 last_test = test = p->tests;
2144 uncond = is_unconditional (test, subroutine_type);
2148 write_cond (test, depth, subroutine_type);
2150 while ((test = test->next) != NULL)
2153 if (is_unconditional (test, subroutine_type))
2157 write_cond (test, depth, subroutine_type);
2163 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2168 /* Emit code for all of the sibling nodes of HEAD. */
2171 write_tree_1 (struct decision_head *head, int depth,
2172 enum routine_type subroutine_type)
2174 struct decision *p, *next;
2177 for (p = head->first; p ; p = next)
2179 /* The label for the first element was printed in write_tree. */
2180 if (p != head->first && p->need_label)
2181 OUTPUT_LABEL (" ", p->number);
2183 /* Attempt to write a switch statement for a whole sequence. */
2184 next = write_switch (p, depth);
2189 /* Failed -- fall back and write one node. */
2190 uncond = write_node (p, depth, subroutine_type);
2195 /* Finished with this chain. Close a fallthru path by branching
2196 to the afterward node. */
2198 write_afterward (head->last, head->last->afterward, " ");
2201 /* Write out the decision tree starting at HEAD. PREVPOS is the
2202 position at the node that branched to this node. */
2205 write_tree (struct decision_head *head, struct position *prevpos,
2206 enum routine_type type, int initial)
2208 struct decision *p = head->first;
2212 OUTPUT_LABEL (" ", p->number);
2214 if (! initial && p->subroutine_number > 0)
2216 static const char * const name_prefix[] = {
2217 "recog", "split", "peephole2"
2220 static const char * const call_suffix[] = {
2221 ", pnum_clobbers", "", ", _pmatch_len"
2224 /* This node has been broken out into a separate subroutine.
2225 Call it, test the result, and branch accordingly. */
2229 printf (" tem = %s_%d (x0, insn%s);\n",
2230 name_prefix[type], p->subroutine_number, call_suffix[type]);
2231 if (IS_SPLIT (type))
2232 printf (" if (tem != 0)\n return tem;\n");
2234 printf (" if (tem >= 0)\n return tem;\n");
2236 change_state (p->position, p->afterward->position, " ");
2237 printf (" goto L%d;\n", p->afterward->number);
2241 printf (" return %s_%d (x0, insn%s);\n",
2242 name_prefix[type], p->subroutine_number, call_suffix[type]);
2247 change_state (prevpos, p->position, " ");
2248 write_tree_1 (head, p->position->depth, type);
2250 for (p = head->first; p; p = p->next)
2251 if (p->success.first)
2252 write_tree (&p->success, p->position, type, 0);
2256 /* Write out a subroutine of type TYPE to do comparisons starting at
2260 write_subroutine (struct decision_head *head, enum routine_type type)
2262 int subfunction = head->first ? head->first->subroutine_number : 0;
2267 s_or_e = subfunction ? "static " : "";
2270 sprintf (extension, "_%d", subfunction);
2271 else if (type == RECOG)
2272 extension[0] = '\0';
2274 strcpy (extension, "_insns");
2280 recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
2284 split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
2289 peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
2294 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2295 for (i = 1; i <= max_depth; i++)
2296 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2298 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2301 printf (" recog_data.insn = NULL_RTX;\n");
2304 write_tree (head, &root_pos, type, 1);
2306 printf (" goto ret0;\n");
2308 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2311 /* In break_out_subroutines, we discovered the boundaries for the
2312 subroutines, but did not write them out. Do so now. */
2315 write_subroutines (struct decision_head *head, enum routine_type type)
2319 for (p = head->first; p ; p = p->next)
2320 if (p->success.first)
2321 write_subroutines (&p->success, type);
2323 if (head->first->subroutine_number > 0)
2324 write_subroutine (head, type);
2327 /* Begin the output file. */
2333 /* Generated automatically by the program `genrecog' from the target\n\
2334 machine description file. */\n\
2336 #include \"config.h\"\n\
2337 #include \"system.h\"\n\
2338 #include \"coretypes.h\"\n\
2339 #include \"tm.h\"\n\
2340 #include \"rtl.h\"\n\
2341 #include \"tm_p.h\"\n\
2342 #include \"function.h\"\n\
2343 #include \"insn-config.h\"\n\
2344 #include \"recog.h\"\n\
2345 #include \"output.h\"\n\
2346 #include \"flags.h\"\n\
2347 #include \"hard-reg-set.h\"\n\
2348 #include \"resource.h\"\n\
2349 #include \"diagnostic-core.h\"\n\
2350 #include \"reload.h\"\n\
2351 #include \"regs.h\"\n\
2352 #include \"tm-constrs.h\"\n\
2356 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2357 X0 is a valid instruction.\n\
2359 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2360 returns a nonnegative number which is the insn code number for the\n\
2361 pattern that matched. This is the same as the order in the machine\n\
2362 description of the entry that matched. This number can be used as an\n\
2363 index into `insn_data' and other tables.\n");
2365 The third argument to recog is an optional pointer to an int. If\n\
2366 present, recog will accept a pattern if it matches except for missing\n\
2367 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2368 the optional pointer will be set to the number of CLOBBERs that need\n\
2369 to be added (it should be initialized to zero by the caller). If it");
2371 is set nonzero, the caller should allocate a PARALLEL of the\n\
2372 appropriate size, copy the initial entries, and call add_clobbers\n\
2373 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2377 The function split_insns returns 0 if the rtl could not\n\
2378 be split or the split rtl as an INSN list if it can be.\n\
2380 The function peephole2_insns returns 0 if the rtl could not\n\
2381 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2382 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2387 /* Construct and return a sequence of decisions
2388 that will recognize INSN.
2390 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2392 static struct decision_head
2393 make_insn_sequence (rtx insn, enum routine_type type)
2396 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2397 int truth = maybe_eval_c_test (c_test);
2398 struct decision *last;
2399 struct decision_test *test, **place;
2400 struct decision_head head;
2401 struct position *c_test_pos, **pos_ptr;
2403 /* We should never see an insn whose C test is false at compile time. */
2406 c_test_pos = &root_pos;
2407 if (type == PEEPHOLE2)
2411 /* peephole2 gets special treatment:
2412 - X always gets an outer parallel even if it's only one entry
2413 - we remove all traces of outer-level match_scratch and match_dup
2414 expressions here. */
2415 x = rtx_alloc (PARALLEL);
2416 PUT_MODE (x, VOIDmode);
2417 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2418 pos_ptr = &peep2_insn_pos_list;
2419 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2421 rtx tmp = XVECEXP (insn, 0, i);
2422 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2424 c_test_pos = next_position (pos_ptr, &root_pos,
2426 XVECEXP (x, 0, j) = tmp;
2428 pos_ptr = &c_test_pos->next;
2433 else if (XVECLEN (insn, type == RECOG) == 1)
2434 x = XVECEXP (insn, type == RECOG, 0);
2437 x = rtx_alloc (PARALLEL);
2438 XVEC (x, 0) = XVEC (insn, type == RECOG);
2439 PUT_MODE (x, VOIDmode);
2442 validate_pattern (x, insn, NULL_RTX, 0);
2444 memset(&head, 0, sizeof(head));
2445 last = add_to_sequence (x, &head, &root_pos, type, 1);
2447 /* Find the end of the test chain on the last node. */
2448 for (test = last->tests; test->next; test = test->next)
2450 place = &test->next;
2452 /* Skip the C test if it's known to be true at compile time. */
2455 /* Need a new node if we have another test to add. */
2456 if (test->type == DT_accept_op)
2458 last = new_decision (c_test_pos, &last->success);
2459 place = &last->tests;
2461 test = new_decision_test (DT_c_test, &place);
2462 test->u.c_test = c_test;
2465 test = new_decision_test (DT_accept_insn, &place);
2466 test->u.insn.code_number = next_insn_code;
2467 test->u.insn.lineno = pattern_lineno;
2468 test->u.insn.num_clobbers_to_add = 0;
2473 /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
2474 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2475 If so, set up to recognize the pattern without these CLOBBERs. */
2477 if (GET_CODE (x) == PARALLEL)
2481 /* Find the last non-clobber in the parallel. */
2482 for (i = XVECLEN (x, 0); i > 0; i--)
2484 rtx y = XVECEXP (x, 0, i - 1);
2485 if (GET_CODE (y) != CLOBBER
2486 || (!REG_P (XEXP (y, 0))
2487 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2491 if (i != XVECLEN (x, 0))
2494 struct decision_head clobber_head;
2496 /* Build a similar insn without the clobbers. */
2498 new_rtx = XVECEXP (x, 0, 0);
2503 new_rtx = rtx_alloc (PARALLEL);
2504 XVEC (new_rtx, 0) = rtvec_alloc (i);
2505 for (j = i - 1; j >= 0; j--)
2506 XVECEXP (new_rtx, 0, j) = XVECEXP (x, 0, j);
2510 memset (&clobber_head, 0, sizeof(clobber_head));
2511 last = add_to_sequence (new_rtx, &clobber_head, &root_pos,
2514 /* Find the end of the test chain on the last node. */
2515 for (test = last->tests; test->next; test = test->next)
2518 /* We definitely have a new test to add -- create a new
2520 place = &test->next;
2521 if (test->type == DT_accept_op)
2523 last = new_decision (&root_pos, &last->success);
2524 place = &last->tests;
2527 /* Skip the C test if it's known to be true at compile
2531 test = new_decision_test (DT_c_test, &place);
2532 test->u.c_test = c_test;
2535 test = new_decision_test (DT_accept_insn, &place);
2536 test->u.insn.code_number = next_insn_code;
2537 test->u.insn.lineno = pattern_lineno;
2538 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2540 merge_trees (&head, &clobber_head);
2546 /* Define the subroutine we will call below and emit in genemit. */
2547 printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code);
2551 /* Define the subroutine we will call below and emit in genemit. */
2552 printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
2561 process_tree (struct decision_head *head, enum routine_type subroutine_type)
2563 if (head->first == NULL)
2565 /* We can elide peephole2_insns, but not recog or split_insns. */
2566 if (subroutine_type == PEEPHOLE2)
2571 factor_tests (head);
2573 next_subroutine_number = 0;
2574 break_out_subroutines (head, 1);
2575 find_afterward (head, NULL);
2577 /* We run this after find_afterward, because find_afterward needs
2578 the redundant DT_mode tests on predicates to determine whether
2579 two tests can both be true or not. */
2580 simplify_tests(head);
2582 write_subroutines (head, subroutine_type);
2585 write_subroutine (head, subroutine_type);
2588 extern int main (int, char **);
2591 main (int argc, char **argv)
2594 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2596 progname = "genrecog";
2598 memset (&recog_tree, 0, sizeof recog_tree);
2599 memset (&split_tree, 0, sizeof split_tree);
2600 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2602 if (!init_rtx_reader_args (argc, argv))
2603 return (FATAL_EXIT_CODE);
2609 /* Read the machine description. */
2613 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2617 switch (GET_CODE (desc))
2620 h = make_insn_sequence (desc, RECOG);
2621 merge_trees (&recog_tree, &h);
2625 h = make_insn_sequence (desc, SPLIT);
2626 merge_trees (&split_tree, &h);
2629 case DEFINE_PEEPHOLE2:
2630 h = make_insn_sequence (desc, PEEPHOLE2);
2631 merge_trees (&peephole2_tree, &h);
2639 return FATAL_EXIT_CODE;
2643 process_tree (&recog_tree, RECOG);
2644 process_tree (&split_tree, SPLIT);
2645 process_tree (&peephole2_tree, PEEPHOLE2);
2648 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2652 debug_decision_2 (struct decision_test *test)
2657 fprintf (stderr, "num_insns=%d", test->u.num_insns);
2660 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2663 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2666 fprintf (stderr, "veclen=%d", test->u.veclen);
2668 case DT_elt_zero_int:
2669 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2671 case DT_elt_one_int:
2672 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2674 case DT_elt_zero_wide:
2675 fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2677 case DT_elt_zero_wide_safe:
2678 fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2681 fprintf (stderr, "veclen>=%d", test->u.veclen);
2684 fprintf (stderr, "dup=%d", test->u.dup);
2687 fprintf (stderr, "pred=(%s,%s)",
2688 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2693 strncpy (sub, test->u.c_test, sizeof(sub));
2694 memcpy (sub+16, "...", 4);
2695 fprintf (stderr, "c_test=\"%s\"", sub);
2699 fprintf (stderr, "A_op=%d", test->u.opno);
2701 case DT_accept_insn:
2702 fprintf (stderr, "A_insn=(%d,%d)",
2703 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2712 debug_decision_1 (struct decision *d, int indent)
2715 struct decision_test *test;
2719 for (i = 0; i < indent; ++i)
2721 fputs ("(nil)\n", stderr);
2725 for (i = 0; i < indent; ++i)
2732 debug_decision_2 (test);
2733 while ((test = test->next) != NULL)
2735 fputs (" + ", stderr);
2736 debug_decision_2 (test);
2739 fprintf (stderr, "} %d n %d a %d\n", d->number,
2740 (d->next ? d->next->number : -1),
2741 (d->afterward ? d->afterward->number : -1));
2745 debug_decision_0 (struct decision *d, int indent, int maxdepth)
2754 for (i = 0; i < indent; ++i)
2756 fputs ("(nil)\n", stderr);
2760 debug_decision_1 (d, indent);
2761 for (n = d->success.first; n ; n = n->next)
2762 debug_decision_0 (n, indent + 2, maxdepth - 1);
2766 debug_decision (struct decision *d)
2768 debug_decision_0 (d, 0, 1000000);
2772 debug_decision_list (struct decision *d)
2776 debug_decision_0 (d, 0, 0);