gcc/ChangeLog:
[official-gcc.git] / gcc / genrecog.c
blobf414d5f4f2735ce2286508d7436228aa10d127ee
1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
21 /* This program is used to produce insn-recog.c, which contains a
22 function called `recog' plus its subroutines. These functions
23 contain a decision tree that recognizes whether an rtx, the
24 argument given to recog, is a valid instruction.
26 recog returns -1 if the rtx is not valid. If the rtx is valid,
27 recog returns a nonnegative number which is the insn code number
28 for the pattern that matched. This is the same as the order in the
29 machine description of the entry that matched. This number can be
30 used as an index into various insn_* tables, such as insn_template,
31 insn_outfun, and insn_n_operands (found in insn-output.c).
33 The third argument to recog is an optional pointer to an int. If
34 present, recog will accept a pattern if it matches except for
35 missing CLOBBER expressions at the end. In that case, the value
36 pointed to by the optional pointer will be set to the number of
37 CLOBBERs that need to be added (it should be initialized to zero by
38 the caller). If it is set nonzero, the caller should allocate a
39 PARALLEL of the appropriate size, copy the initial entries, and
40 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
42 This program also generates the function `split_insns', which
43 returns 0 if the rtl could not be split, or it returns the split
44 rtl as an INSN list.
46 This program also generates the function `peephole2_insns', which
47 returns 0 if the rtl could not be matched. If there was a match,
48 the new rtl is returned in an INSN list, and LAST_INSN will point
49 to the last recognized insn in the old sequence.
52 At a high level, the algorithm used in this file is as follows:
54 1. Build up a decision tree for each routine, using the following
55 approach to matching an rtx:
57 - First determine the "shape" of the rtx, based on GET_CODE,
58 XVECLEN and XINT. This phase examines SET_SRCs before SET_DESTs
59 since SET_SRCs tend to be more distinctive. It examines other
60 operands in numerical order, since the canonicalization rules
61 prefer putting complex operands of commutative operators first.
63 - Next check modes and predicates. This phase examines all
64 operands in numerical order, even for SETs, since the mode of a
65 SET_DEST is exact while the mode of a SET_SRC can be VOIDmode
66 for constant integers.
68 - Next check match_dups.
70 - Finally check the C condition and (where appropriate) pnum_clobbers.
72 2. Try to optimize the tree by removing redundant tests, CSEing tests,
73 folding tests together, etc.
75 3. Look for common subtrees and split them out into "pattern" routines.
76 These common subtrees can be identical or they can differ in mode,
77 code, or integer (usually an UNSPEC or UNSPEC_VOLATILE code).
78 In the latter case the users of the pattern routine pass the
79 appropriate mode, etc., as argument. For example, if two patterns
80 contain:
82 (plus:SI (match_operand:SI 1 "register_operand")
83 (match_operand:SI 2 "register_operand"))
85 we can split the associated matching code out into a subroutine.
86 If a pattern contains:
88 (minus:DI (match_operand:DI 1 "register_operand")
89 (match_operand:DI 2 "register_operand"))
91 then we can consider using the same matching routine for both
92 the plus and minus expressions, passing PLUS and SImode in the
93 former case and MINUS and DImode in the latter case.
95 The main aim of this phase is to reduce the compile time of the
96 insn-recog.c code and to reduce the amount of object code in
97 insn-recog.o.
99 4. Split the matching trees into functions, trying to limit the
100 size of each function to a sensible amount.
102 Again, the main aim of this phase is to reduce the compile time
103 of insn-recog.c. (It doesn't help with the size of insn-recog.o.)
105 5. Write out C++ code for each function. */
107 #include "bconfig.h"
108 #define INCLUDE_ALGORITHM
109 #include "system.h"
110 #include "coretypes.h"
111 #include "tm.h"
112 #include "rtl.h"
113 #include "errors.h"
114 #include "read-md.h"
115 #include "gensupport.h"
117 #undef GENERATOR_FILE
118 enum true_rtx_doe {
119 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM,
120 #include "rtl.def"
121 #undef DEF_RTL_EXPR
122 FIRST_GENERATOR_RTX_CODE
124 #define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE)
125 #define GENERATOR_FILE 1
127 /* Debugging variables to control which optimizations are performed.
128 Note that disabling merge_states_p leads to very large output. */
129 static const bool merge_states_p = true;
130 static const bool collapse_optional_decisions_p = true;
131 static const bool cse_tests_p = true;
132 static const bool simplify_tests_p = true;
133 static const bool use_operand_variables_p = true;
134 static const bool use_subroutines_p = true;
135 static const bool use_pattern_routines_p = true;
137 /* Whether to add comments for optional tests that we decided to keep.
138 Can be useful when debugging the generator itself but is noise when
139 debugging the generated code. */
140 static const bool mark_optional_transitions_p = false;
142 /* Whether pattern routines should calculate positions relative to their
143 rtx parameter rather than use absolute positions. This e.g. allows
144 a pattern routine to be shared between a plain SET and a PARALLEL
145 that includes a SET.
147 In principle it sounds like this should be useful, especially for
148 recog_for_combine, where the plain SET form is generated automatically
149 from a PARALLEL of a single SET and some CLOBBERs. In practice it doesn't
150 seem to help much and leads to slightly bigger object files. */
151 static const bool relative_patterns_p = false;
153 /* Whether pattern routines should be allowed to test whether pnum_clobbers
154 is null. This requires passing pnum_clobbers around as a parameter. */
155 static const bool pattern_have_num_clobbers_p = true;
157 /* Whether pattern routines should be allowed to test .md file C conditions.
158 This requires passing insn around as a parameter, in case the C
159 condition refers to it. In practice this tends to lead to bigger
160 object files. */
161 static const bool pattern_c_test_p = false;
163 /* Whether to require each parameter passed to a pattern routine to be
164 unique. Disabling this check for example allows unary operators with
165 matching modes (like NEG) and unary operators with mismatched modes
166 (like ZERO_EXTEND) to be matched by a single pattern. However, we then
167 often have cases where the same value is passed too many times. */
168 static const bool force_unique_params_p = true;
170 /* The maximum (approximate) depth of block nesting that an individual
171 routine or subroutine should have. This limit is about keeping the
172 output readable rather than reducing compile time. */
173 static const unsigned int MAX_DEPTH = 6;
175 /* The minimum number of pseudo-statements that a state must have before
176 we split it out into a subroutine. */
177 static const unsigned int MIN_NUM_STATEMENTS = 5;
179 /* The number of pseudo-statements a state can have before we consider
180 splitting out substates into subroutines. This limit is about avoiding
181 compile-time problems with very big functions (and also about keeping
182 functions within --param optimization limits, etc.). */
183 static const unsigned int MAX_NUM_STATEMENTS = 200;
185 /* The minimum number of pseudo-statements that can be used in a pattern
186 routine. */
187 static const unsigned int MIN_COMBINE_COST = 4;
189 /* The maximum number of arguments that a pattern routine can have.
190 The idea is to prevent one pattern getting a ridiculous number of
191 arguments when it would be more beneficial to have a separate pattern
192 routine instead. */
193 static const unsigned int MAX_PATTERN_PARAMS = 5;
195 /* The maximum operand number plus one. */
196 int num_operands;
198 /* Ways of obtaining an rtx to be tested. */
199 enum position_type {
200 /* PATTERN (peep2_next_insn (ARG)). */
201 POS_PEEP2_INSN,
203 /* XEXP (BASE, ARG). */
204 POS_XEXP,
206 /* XVECEXP (BASE, 0, ARG). */
207 POS_XVECEXP0
210 /* The position of an rtx relative to X0. Each useful position is
211 represented by exactly one instance of this structure. */
212 struct position
214 /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
215 struct position *base;
217 /* A position with the same BASE and TYPE, but with the next value
218 of ARG. */
219 struct position *next;
221 /* A list of all POS_XEXP positions that use this one as their base,
222 chained by NEXT fields. The first entry represents XEXP (this, 0),
223 the second represents XEXP (this, 1), and so on. */
224 struct position *xexps;
226 /* A list of POS_XVECEXP0 positions that use this one as their base,
227 chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0),
228 the second represents XVECEXP (this, 0, 1), and so on. */
229 struct position *xvecexp0s;
231 /* The type of position. */
232 enum position_type type;
234 /* The argument to TYPE (shown as ARG in the position_type comments). */
235 int arg;
237 /* The instruction to which the position belongs. */
238 unsigned int insn_id;
240 /* The depth of this position relative to the instruction pattern.
241 E.g. if the instruction pattern is a SET, the SET itself has a
242 depth of 0 while the SET_DEST and SET_SRC have depths of 1. */
243 unsigned int depth;
245 /* A unique identifier for this position. */
246 unsigned int id;
249 enum routine_type {
250 SUBPATTERN, RECOG, SPLIT, PEEPHOLE2
253 /* The root position (x0). */
254 static struct position root_pos;
256 /* The number of positions created. Also one higher than the maximum
257 position id. */
258 static unsigned int num_positions = 1;
260 /* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
261 since we are given that instruction's pattern as x0. */
262 static struct position *peep2_insn_pos_list = &root_pos;
264 /* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
265 points to where the unique object that represents the position
266 should be stored. Create the object if it doesn't already exist,
267 otherwise reuse the object that is already there. */
269 static struct position *
270 next_position (struct position **next_ptr, struct position *base,
271 enum position_type type, int arg)
273 struct position *pos;
275 pos = *next_ptr;
276 if (!pos)
278 pos = XCNEW (struct position);
279 pos->type = type;
280 pos->arg = arg;
281 if (type == POS_PEEP2_INSN)
283 pos->base = 0;
284 pos->insn_id = arg;
285 pos->depth = base->depth;
287 else
289 pos->base = base;
290 pos->insn_id = base->insn_id;
291 pos->depth = base->depth + 1;
293 pos->id = num_positions++;
294 *next_ptr = pos;
296 return pos;
299 /* Compare positions POS1 and POS2 lexicographically. */
301 static int
302 compare_positions (struct position *pos1, struct position *pos2)
304 int diff;
306 diff = pos1->depth - pos2->depth;
307 if (diff < 0)
309 pos2 = pos2->base;
310 while (pos1->depth != pos2->depth);
311 else if (diff > 0)
313 pos1 = pos1->base;
314 while (pos1->depth != pos2->depth);
315 while (pos1 != pos2)
317 diff = (int) pos1->type - (int) pos2->type;
318 if (diff == 0)
319 diff = pos1->arg - pos2->arg;
320 pos1 = pos1->base;
321 pos2 = pos2->base;
323 return diff;
326 /* Return the most deeply-nested position that is common to both
327 POS1 and POS2. If the positions are from different instructions,
328 return the one with the lowest insn_id. */
330 static struct position *
331 common_position (struct position *pos1, struct position *pos2)
333 if (pos1->insn_id != pos2->insn_id)
334 return pos1->insn_id < pos2->insn_id ? pos1 : pos2;
335 if (pos1->depth > pos2->depth)
336 std::swap (pos1, pos2);
337 while (pos1->depth != pos2->depth)
338 pos2 = pos2->base;
339 while (pos1 != pos2)
341 pos1 = pos1->base;
342 pos2 = pos2->base;
344 return pos1;
347 /* Search for and return operand N, stop when reaching node STOP. */
349 static rtx
350 find_operand (rtx pattern, int n, rtx stop)
352 const char *fmt;
353 RTX_CODE code;
354 int i, j, len;
355 rtx r;
357 if (pattern == stop)
358 return stop;
360 code = GET_CODE (pattern);
361 if ((code == MATCH_SCRATCH
362 || code == MATCH_OPERAND
363 || code == MATCH_OPERATOR
364 || code == MATCH_PARALLEL)
365 && XINT (pattern, 0) == n)
366 return pattern;
368 fmt = GET_RTX_FORMAT (code);
369 len = GET_RTX_LENGTH (code);
370 for (i = 0; i < len; i++)
372 switch (fmt[i])
374 case 'e': case 'u':
375 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
376 return r;
377 break;
379 case 'V':
380 if (! XVEC (pattern, i))
381 break;
382 /* Fall through. */
384 case 'E':
385 for (j = 0; j < XVECLEN (pattern, i); j++)
386 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
387 != NULL_RTX)
388 return r;
389 break;
391 case 'i': case 'r': case 'w': case '0': case 's':
392 break;
394 default:
395 gcc_unreachable ();
399 return NULL;
402 /* Search for and return operand M, such that it has a matching
403 constraint for operand N. */
405 static rtx
406 find_matching_operand (rtx pattern, int n)
408 const char *fmt;
409 RTX_CODE code;
410 int i, j, len;
411 rtx r;
413 code = GET_CODE (pattern);
414 if (code == MATCH_OPERAND
415 && (XSTR (pattern, 2)[0] == '0' + n
416 || (XSTR (pattern, 2)[0] == '%'
417 && XSTR (pattern, 2)[1] == '0' + n)))
418 return pattern;
420 fmt = GET_RTX_FORMAT (code);
421 len = GET_RTX_LENGTH (code);
422 for (i = 0; i < len; i++)
424 switch (fmt[i])
426 case 'e': case 'u':
427 if ((r = find_matching_operand (XEXP (pattern, i), n)))
428 return r;
429 break;
431 case 'V':
432 if (! XVEC (pattern, i))
433 break;
434 /* Fall through. */
436 case 'E':
437 for (j = 0; j < XVECLEN (pattern, i); j++)
438 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
439 return r;
440 break;
442 case 'i': case 'r': case 'w': case '0': case 's':
443 break;
445 default:
446 gcc_unreachable ();
450 return NULL;
453 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
454 don't use the MATCH_OPERAND constraint, only the predicate.
455 This is confusing to folks doing new ports, so help them
456 not make the mistake. */
458 static bool
459 constraints_supported_in_insn_p (rtx insn)
461 return !(GET_CODE (insn) == DEFINE_EXPAND
462 || GET_CODE (insn) == DEFINE_SPLIT
463 || GET_CODE (insn) == DEFINE_PEEPHOLE2);
466 /* Return the name of the predicate matched by MATCH_RTX. */
468 static const char *
469 predicate_name (rtx match_rtx)
471 if (GET_CODE (match_rtx) == MATCH_SCRATCH)
472 return "scratch_operand";
473 else
474 return XSTR (match_rtx, 1);
477 /* Return true if OPERAND is a MATCH_OPERAND using a special predicate
478 function. */
480 static bool
481 special_predicate_operand_p (rtx operand)
483 if (GET_CODE (operand) == MATCH_OPERAND)
485 const char *pred_name = predicate_name (operand);
486 if (pred_name[0] != 0)
488 const struct pred_data *pred;
490 pred = lookup_predicate (pred_name);
491 return pred != NULL && pred->special;
495 return false;
498 /* Check for various errors in PATTERN, which is part of INFO.
499 SET is nonnull for a destination, and is the complete set pattern.
500 SET_CODE is '=' for normal sets, and '+' within a context that
501 requires in-out constraints. */
503 static void
504 validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code)
506 const char *fmt;
507 RTX_CODE code;
508 size_t i, len;
509 int j;
511 code = GET_CODE (pattern);
512 switch (code)
514 case MATCH_SCRATCH:
516 const char constraints0 = XSTR (pattern, 1)[0];
518 if (!constraints_supported_in_insn_p (info->def))
520 if (constraints0)
522 error_at (info->loc, "constraints not supported in %s",
523 GET_RTX_NAME (GET_CODE (info->def)));
525 return;
528 /* If a MATCH_SCRATCH is used in a context requiring an write-only
529 or read/write register, validate that. */
530 if (set_code == '='
531 && constraints0
532 && constraints0 != '='
533 && constraints0 != '+')
535 error_at (info->loc, "operand %d missing output reload",
536 XINT (pattern, 0));
538 return;
540 case MATCH_DUP:
541 case MATCH_OP_DUP:
542 case MATCH_PAR_DUP:
543 if (find_operand (info->def, XINT (pattern, 0), pattern) == pattern)
544 error_at (info->loc, "operand %i duplicated before defined",
545 XINT (pattern, 0));
546 break;
547 case MATCH_OPERAND:
548 case MATCH_OPERATOR:
550 const char *pred_name = XSTR (pattern, 1);
551 const struct pred_data *pred;
552 const char *c_test;
554 c_test = get_c_test (info->def);
556 if (pred_name[0] != 0)
558 pred = lookup_predicate (pred_name);
559 if (!pred)
560 error_at (info->loc, "unknown predicate '%s'", pred_name);
562 else
563 pred = 0;
565 if (code == MATCH_OPERAND)
567 const char *constraints = XSTR (pattern, 2);
568 const char constraints0 = constraints[0];
570 if (!constraints_supported_in_insn_p (info->def))
572 if (constraints0)
574 error_at (info->loc, "constraints not supported in %s",
575 GET_RTX_NAME (GET_CODE (info->def)));
579 /* A MATCH_OPERAND that is a SET should have an output reload. */
580 else if (set && constraints0)
582 if (set_code == '+')
584 if (constraints0 == '+')
586 /* If we've only got an output reload for this operand,
587 we'd better have a matching input operand. */
588 else if (constraints0 == '='
589 && find_matching_operand (info->def,
590 XINT (pattern, 0)))
592 else
593 error_at (info->loc, "operand %d missing in-out reload",
594 XINT (pattern, 0));
596 else if (constraints0 != '=' && constraints0 != '+')
597 error_at (info->loc, "operand %d missing output reload",
598 XINT (pattern, 0));
601 /* For matching constraint in MATCH_OPERAND, the digit must be a
602 smaller number than the number of the operand that uses it in the
603 constraint. */
604 while (1)
606 while (constraints[0]
607 && (constraints[0] == ' ' || constraints[0] == ','))
608 constraints++;
609 if (!constraints[0])
610 break;
612 if (constraints[0] >= '0' && constraints[0] <= '9')
614 int val;
616 sscanf (constraints, "%d", &val);
617 if (val >= XINT (pattern, 0))
618 error_at (info->loc, "constraint digit %d is not"
619 " smaller than operand %d",
620 val, XINT (pattern, 0));
623 while (constraints[0] && constraints[0] != ',')
624 constraints++;
628 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
629 while not likely to occur at runtime, results in less efficient
630 code from insn-recog.c. */
631 if (set && pred && pred->allows_non_lvalue)
632 error_at (info->loc, "destination operand %d allows non-lvalue",
633 XINT (pattern, 0));
635 /* A modeless MATCH_OPERAND can be handy when we can check for
636 multiple modes in the c_test. In most other cases, it is a
637 mistake. Only DEFINE_INSN is eligible, since SPLIT and
638 PEEP2 can FAIL within the output pattern. Exclude special
639 predicates, which check the mode themselves. Also exclude
640 predicates that allow only constants. Exclude the SET_DEST
641 of a call instruction, as that is a common idiom. */
643 if (GET_MODE (pattern) == VOIDmode
644 && code == MATCH_OPERAND
645 && GET_CODE (info->def) == DEFINE_INSN
646 && pred
647 && !pred->special
648 && pred->allows_non_const
649 && strstr (c_test, "operands") == NULL
650 && ! (set
651 && GET_CODE (set) == SET
652 && GET_CODE (SET_SRC (set)) == CALL))
653 message_at (info->loc, "warning: operand %d missing mode?",
654 XINT (pattern, 0));
655 return;
658 case SET:
660 machine_mode dmode, smode;
661 rtx dest, src;
663 dest = SET_DEST (pattern);
664 src = SET_SRC (pattern);
666 /* STRICT_LOW_PART is a wrapper. Its argument is the real
667 destination, and it's mode should match the source. */
668 if (GET_CODE (dest) == STRICT_LOW_PART)
669 dest = XEXP (dest, 0);
671 /* Find the referent for a DUP. */
673 if (GET_CODE (dest) == MATCH_DUP
674 || GET_CODE (dest) == MATCH_OP_DUP
675 || GET_CODE (dest) == MATCH_PAR_DUP)
676 dest = find_operand (info->def, XINT (dest, 0), NULL);
678 if (GET_CODE (src) == MATCH_DUP
679 || GET_CODE (src) == MATCH_OP_DUP
680 || GET_CODE (src) == MATCH_PAR_DUP)
681 src = find_operand (info->def, XINT (src, 0), NULL);
683 dmode = GET_MODE (dest);
684 smode = GET_MODE (src);
686 /* Mode checking is not performed for special predicates. */
687 if (special_predicate_operand_p (src)
688 || special_predicate_operand_p (dest))
691 /* The operands of a SET must have the same mode unless one
692 is VOIDmode. */
693 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
694 error_at (info->loc, "mode mismatch in set: %smode vs %smode",
695 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
697 /* If only one of the operands is VOIDmode, and PC or CC0 is
698 not involved, it's probably a mistake. */
699 else if (dmode != smode
700 && GET_CODE (dest) != PC
701 && GET_CODE (dest) != CC0
702 && GET_CODE (src) != PC
703 && GET_CODE (src) != CC0
704 && !CONST_INT_P (src)
705 && !CONST_WIDE_INT_P (src)
706 && GET_CODE (src) != CALL)
708 const char *which;
709 which = (dmode == VOIDmode ? "destination" : "source");
710 message_at (info->loc, "warning: %s missing a mode?", which);
713 if (dest != SET_DEST (pattern))
714 validate_pattern (dest, info, pattern, '=');
715 validate_pattern (SET_DEST (pattern), info, pattern, '=');
716 validate_pattern (SET_SRC (pattern), info, NULL_RTX, 0);
717 return;
720 case CLOBBER:
721 validate_pattern (SET_DEST (pattern), info, pattern, '=');
722 return;
724 case ZERO_EXTRACT:
725 validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0);
726 validate_pattern (XEXP (pattern, 1), info, NULL_RTX, 0);
727 validate_pattern (XEXP (pattern, 2), info, NULL_RTX, 0);
728 return;
730 case STRICT_LOW_PART:
731 validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0);
732 return;
734 case LABEL_REF:
735 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
736 error_at (info->loc, "operand to label_ref %smode not VOIDmode",
737 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
738 break;
740 default:
741 break;
744 fmt = GET_RTX_FORMAT (code);
745 len = GET_RTX_LENGTH (code);
746 for (i = 0; i < len; i++)
748 switch (fmt[i])
750 case 'e': case 'u':
751 validate_pattern (XEXP (pattern, i), info, NULL_RTX, 0);
752 break;
754 case 'E':
755 for (j = 0; j < XVECLEN (pattern, i); j++)
756 validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, 0);
757 break;
759 case 'i': case 'r': case 'w': case '0': case 's':
760 break;
762 default:
763 gcc_unreachable ();
768 /* Simple list structure for items of type T, for use when being part
769 of a list is an inherent property of T. T must have members equivalent
770 to "T *prev, *next;" and a function "void set_parent (list_head <T> *)"
771 to set the parent list. */
772 template <typename T>
773 struct list_head
775 /* A range of linked items. */
776 struct range
778 range (T *);
779 range (T *, T *);
781 T *start, *end;
782 void set_parent (list_head *);
785 list_head ();
786 range release ();
787 void push_back (range);
788 range remove (range);
789 void replace (range, range);
790 T *singleton () const;
792 T *first, *last;
795 /* Create a range [START_IN, START_IN]. */
797 template <typename T>
798 list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {}
800 /* Create a range [START_IN, END_IN], linked by next and prev fields. */
802 template <typename T>
803 list_head <T>::range::range (T *start_in, T *end_in)
804 : start (start_in), end (end_in) {}
806 template <typename T>
807 void
808 list_head <T>::range::set_parent (list_head <T> *owner)
810 for (T *item = start; item != end; item = item->next)
811 item->set_parent (owner);
812 end->set_parent (owner);
815 template <typename T>
816 list_head <T>::list_head () : first (0), last (0) {}
818 /* Add R to the end of the list. */
820 template <typename T>
821 void
822 list_head <T>::push_back (range r)
824 if (last)
825 last->next = r.start;
826 else
827 first = r.start;
828 r.start->prev = last;
829 last = r.end;
830 r.set_parent (this);
833 /* Remove R from the list. R remains valid and can be inserted into
834 other lists. */
836 template <typename T>
837 typename list_head <T>::range
838 list_head <T>::remove (range r)
840 if (r.start->prev)
841 r.start->prev->next = r.end->next;
842 else
843 first = r.end->next;
844 if (r.end->next)
845 r.end->next->prev = r.start->prev;
846 else
847 last = r.start->prev;
848 r.start->prev = 0;
849 r.end->next = 0;
850 r.set_parent (0);
851 return r;
854 /* Replace OLDR with NEWR. OLDR remains valid and can be inserted into
855 other lists. */
857 template <typename T>
858 void
859 list_head <T>::replace (range oldr, range newr)
861 newr.start->prev = oldr.start->prev;
862 newr.end->next = oldr.end->next;
864 oldr.start->prev = 0;
865 oldr.end->next = 0;
866 oldr.set_parent (0);
868 if (newr.start->prev)
869 newr.start->prev->next = newr.start;
870 else
871 first = newr.start;
872 if (newr.end->next)
873 newr.end->next->prev = newr.end;
874 else
875 last = newr.end;
876 newr.set_parent (this);
879 /* Empty the list and return the previous contents as a range that can
880 be inserted into other lists. */
882 template <typename T>
883 typename list_head <T>::range
884 list_head <T>::release ()
886 range r (first, last);
887 first = 0;
888 last = 0;
889 r.set_parent (0);
890 return r;
893 /* If the list contains a single item, return that item, otherwise return
894 null. */
896 template <typename T>
898 list_head <T>::singleton () const
900 return first == last ? first : 0;
903 struct state;
905 /* Describes a possible successful return from a routine. */
906 struct acceptance_type
908 /* The type of routine we're returning from. */
909 routine_type type : 16;
911 /* True if this structure only really represents a partial match,
912 and if we must call a subroutine of type TYPE to complete the match.
913 In this case we'll call the subroutine and, if it succeeds, return
914 whatever the subroutine returned.
916 False if this structure presents a full match. */
917 unsigned int partial_p : 1;
919 union
921 /* If PARTIAL_P, this is the number of the subroutine to call. */
922 int subroutine_id;
924 /* Valid if !PARTIAL_P. */
925 struct
927 /* The identifier of the matching pattern. For SUBPATTERNs this
928 value belongs to an ad-hoc routine-specific enum. For the
929 others it's the number of an .md file pattern. */
930 int code;
931 union
933 /* For RECOG, the number of clobbers that must be added to the
934 pattern in order for it to match CODE. */
935 int num_clobbers;
937 /* For PEEPHOLE2, the number of additional instructions that were
938 included in the optimization. */
939 int match_len;
940 } u;
941 } full;
942 } u;
945 bool
946 operator == (const acceptance_type &a, const acceptance_type &b)
948 if (a.partial_p != b.partial_p)
949 return false;
950 if (a.partial_p)
951 return a.u.subroutine_id == b.u.subroutine_id;
952 else
953 return a.u.full.code == b.u.full.code;
956 bool
957 operator != (const acceptance_type &a, const acceptance_type &b)
959 return !operator == (a, b);
962 /* Represents a parameter to a pattern routine. */
963 struct parameter
965 /* The C type of parameter. */
966 enum type_enum {
967 /* Represents an invalid parameter. */
968 UNSET,
970 /* A machine_mode parameter. */
971 MODE,
973 /* An rtx_code parameter. */
974 CODE,
976 /* An int parameter. */
977 INT,
979 /* An unsigned int parameter. */
980 UINT,
982 /* A HOST_WIDE_INT parameter. */
983 WIDE_INT
986 parameter ();
987 parameter (type_enum, bool, uint64_t);
989 /* The type of the parameter. */
990 type_enum type;
992 /* True if the value passed is variable, false if it is constant. */
993 bool is_param;
995 /* If IS_PARAM, this is the number of the variable passed, for an "i%d"
996 format string. If !IS_PARAM, this is the constant value passed. */
997 uint64_t value;
1000 parameter::parameter ()
1001 : type (UNSET), is_param (false), value (0) {}
1003 parameter::parameter (type_enum type_in, bool is_param_in, uint64_t value_in)
1004 : type (type_in), is_param (is_param_in), value (value_in) {}
1006 bool
1007 operator == (const parameter &param1, const parameter &param2)
1009 return (param1.type == param2.type
1010 && param1.is_param == param2.is_param
1011 && param1.value == param2.value);
1014 bool
1015 operator != (const parameter &param1, const parameter &param2)
1017 return !operator == (param1, param2);
1020 /* Represents a routine that matches a partial rtx pattern, returning
1021 an ad-hoc enum value on success and -1 on failure. The routine can
1022 be used by any subroutine type. The match can be parameterized by
1023 things like mode, code and UNSPEC number. */
1024 struct pattern_routine
1026 /* The state that implements the pattern. */
1027 state *s;
1029 /* The deepest root position from which S can access all the rtxes it needs.
1030 This is NULL if the pattern doesn't need an rtx input, usually because
1031 all matching is done on operands[] instead. */
1032 position *pos;
1034 /* A unique identifier for the routine. */
1035 unsigned int pattern_id;
1037 /* True if the routine takes pnum_clobbers as argument. */
1038 bool pnum_clobbers_p;
1040 /* True if the routine takes the enclosing instruction as argument. */
1041 bool insn_p;
1043 /* The types of the other parameters to the routine, if any. */
1044 auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types;
1047 /* All defined patterns. */
1048 static vec <pattern_routine *> patterns;
1050 /* Represents one use of a pattern routine. */
1051 struct pattern_use
1053 /* The pattern routine to use. */
1054 pattern_routine *routine;
1056 /* The values to pass as parameters. This vector has the same length
1057 as ROUTINE->PARAM_TYPES. */
1058 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
1061 /* Represents a test performed by a decision. */
1062 struct rtx_test
1064 rtx_test ();
1066 /* The types of test that can be performed. Most of them take as input
1067 an rtx X. Some also take as input a transition label LABEL; the others
1068 are booleans for which the transition label is always "true".
1070 The order of the enum isn't important. */
1071 enum kind_enum {
1072 /* Check GET_CODE (X) == LABEL. */
1073 CODE,
1075 /* Check GET_MODE (X) == LABEL. */
1076 MODE,
1078 /* Check REGNO (X) == LABEL. */
1079 REGNO_FIELD,
1081 /* Check XINT (X, u.opno) == LABEL. */
1082 INT_FIELD,
1084 /* Check XWINT (X, u.opno) == LABEL. */
1085 WIDE_INT_FIELD,
1087 /* Check XVECLEN (X, 0) == LABEL. */
1088 VECLEN,
1090 /* Check peep2_current_count >= u.min_len. */
1091 PEEP2_COUNT,
1093 /* Check XVECLEN (X, 0) >= u.min_len. */
1094 VECLEN_GE,
1096 /* Check whether X is a cached const_int with value u.integer. */
1097 SAVED_CONST_INT,
1099 /* Check u.predicate.data (X, u.predicate.mode). */
1100 PREDICATE,
1102 /* Check rtx_equal_p (X, operands[u.opno]). */
1103 DUPLICATE,
1105 /* Check whether X matches pattern u.pattern. */
1106 PATTERN,
1108 /* Check whether pnum_clobbers is nonnull (RECOG only). */
1109 HAVE_NUM_CLOBBERS,
1111 /* Check whether general C test u.string holds. In general the condition
1112 needs access to "insn" and the full operand list. */
1113 C_TEST,
1115 /* Execute operands[u.opno] = X. (Always succeeds.) */
1116 SET_OP,
1118 /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT.
1119 May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */
1120 ACCEPT
1123 /* The position of rtx X in the above description, relative to the
1124 incoming instruction "insn". The position is null if the test
1125 doesn't take an X as input. */
1126 position *pos;
1128 /* Which element of operands[] already contains POS, or -1 if no element
1129 is known to hold POS. */
1130 int pos_operand;
1132 /* The type of test and its parameters, as described above. */
1133 kind_enum kind;
1134 union
1136 int opno;
1137 int min_len;
1138 struct
1140 bool is_param;
1141 int value;
1142 } integer;
1143 struct
1145 const struct pred_data *data;
1146 /* True if the mode is taken from a machine_mode parameter
1147 to the routine rather than a constant machine_mode. If true,
1148 MODE is the number of the parameter (for an "i%d" format string),
1149 otherwise it is the mode itself. */
1150 bool mode_is_param;
1151 unsigned int mode;
1152 } predicate;
1153 pattern_use *pattern;
1154 const char *string;
1155 acceptance_type acceptance;
1156 } u;
1158 static rtx_test code (position *);
1159 static rtx_test mode (position *);
1160 static rtx_test regno_field (position *);
1161 static rtx_test int_field (position *, int);
1162 static rtx_test wide_int_field (position *, int);
1163 static rtx_test veclen (position *);
1164 static rtx_test peep2_count (int);
1165 static rtx_test veclen_ge (position *, int);
1166 static rtx_test predicate (position *, const pred_data *, machine_mode);
1167 static rtx_test duplicate (position *, int);
1168 static rtx_test pattern (position *, pattern_use *);
1169 static rtx_test have_num_clobbers ();
1170 static rtx_test c_test (const char *);
1171 static rtx_test set_op (position *, int);
1172 static rtx_test accept (const acceptance_type &);
1174 bool terminal_p () const;
1175 bool single_outcome_p () const;
1177 private:
1178 rtx_test (position *, kind_enum);
1181 rtx_test::rtx_test () {}
1183 rtx_test::rtx_test (position *pos_in, kind_enum kind_in)
1184 : pos (pos_in), pos_operand (-1), kind (kind_in) {}
1186 rtx_test
1187 rtx_test::code (position *pos)
1189 return rtx_test (pos, rtx_test::CODE);
1192 rtx_test
1193 rtx_test::mode (position *pos)
1195 return rtx_test (pos, rtx_test::MODE);
1198 rtx_test
1199 rtx_test::regno_field (position *pos)
1201 rtx_test res (pos, rtx_test::REGNO_FIELD);
1202 return res;
1205 rtx_test
1206 rtx_test::int_field (position *pos, int opno)
1208 rtx_test res (pos, rtx_test::INT_FIELD);
1209 res.u.opno = opno;
1210 return res;
1213 rtx_test
1214 rtx_test::wide_int_field (position *pos, int opno)
1216 rtx_test res (pos, rtx_test::WIDE_INT_FIELD);
1217 res.u.opno = opno;
1218 return res;
1221 rtx_test
1222 rtx_test::veclen (position *pos)
1224 return rtx_test (pos, rtx_test::VECLEN);
1227 rtx_test
1228 rtx_test::peep2_count (int min_len)
1230 rtx_test res (0, rtx_test::PEEP2_COUNT);
1231 res.u.min_len = min_len;
1232 return res;
1235 rtx_test
1236 rtx_test::veclen_ge (position *pos, int min_len)
1238 rtx_test res (pos, rtx_test::VECLEN_GE);
1239 res.u.min_len = min_len;
1240 return res;
1243 rtx_test
1244 rtx_test::predicate (position *pos, const struct pred_data *data,
1245 machine_mode mode)
1247 rtx_test res (pos, rtx_test::PREDICATE);
1248 res.u.predicate.data = data;
1249 res.u.predicate.mode_is_param = false;
1250 res.u.predicate.mode = mode;
1251 return res;
1254 rtx_test
1255 rtx_test::duplicate (position *pos, int opno)
1257 rtx_test res (pos, rtx_test::DUPLICATE);
1258 res.u.opno = opno;
1259 return res;
1262 rtx_test
1263 rtx_test::pattern (position *pos, pattern_use *pattern)
1265 rtx_test res (pos, rtx_test::PATTERN);
1266 res.u.pattern = pattern;
1267 return res;
1270 rtx_test
1271 rtx_test::have_num_clobbers ()
1273 return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS);
1276 rtx_test
1277 rtx_test::c_test (const char *string)
1279 rtx_test res (0, rtx_test::C_TEST);
1280 res.u.string = string;
1281 return res;
1284 rtx_test
1285 rtx_test::set_op (position *pos, int opno)
1287 rtx_test res (pos, rtx_test::SET_OP);
1288 res.u.opno = opno;
1289 return res;
1292 rtx_test
1293 rtx_test::accept (const acceptance_type &acceptance)
1295 rtx_test res (0, rtx_test::ACCEPT);
1296 res.u.acceptance = acceptance;
1297 return res;
1300 /* Return true if the test represents an unconditionally successful match. */
1302 bool
1303 rtx_test::terminal_p () const
1305 return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2;
1308 /* Return true if the test is a boolean that is always true. */
1310 bool
1311 rtx_test::single_outcome_p () const
1313 return terminal_p () || kind == rtx_test::SET_OP;
1316 bool
1317 operator == (const rtx_test &a, const rtx_test &b)
1319 if (a.pos != b.pos || a.kind != b.kind)
1320 return false;
1321 switch (a.kind)
1323 case rtx_test::CODE:
1324 case rtx_test::MODE:
1325 case rtx_test::REGNO_FIELD:
1326 case rtx_test::VECLEN:
1327 case rtx_test::HAVE_NUM_CLOBBERS:
1328 return true;
1330 case rtx_test::PEEP2_COUNT:
1331 case rtx_test::VECLEN_GE:
1332 return a.u.min_len == b.u.min_len;
1334 case rtx_test::INT_FIELD:
1335 case rtx_test::WIDE_INT_FIELD:
1336 case rtx_test::DUPLICATE:
1337 case rtx_test::SET_OP:
1338 return a.u.opno == b.u.opno;
1340 case rtx_test::SAVED_CONST_INT:
1341 return (a.u.integer.is_param == b.u.integer.is_param
1342 && a.u.integer.value == b.u.integer.value);
1344 case rtx_test::PREDICATE:
1345 return (a.u.predicate.data == b.u.predicate.data
1346 && a.u.predicate.mode_is_param == b.u.predicate.mode_is_param
1347 && a.u.predicate.mode == b.u.predicate.mode);
1349 case rtx_test::PATTERN:
1350 return (a.u.pattern->routine == b.u.pattern->routine
1351 && a.u.pattern->params == b.u.pattern->params);
1353 case rtx_test::C_TEST:
1354 return strcmp (a.u.string, b.u.string) == 0;
1356 case rtx_test::ACCEPT:
1357 return a.u.acceptance == b.u.acceptance;
1359 gcc_unreachable ();
1362 bool
1363 operator != (const rtx_test &a, const rtx_test &b)
1365 return !operator == (a, b);
1368 /* A simple set of transition labels. Most transitions have a singleton
1369 label, so try to make that case as efficient as possible. */
1370 struct int_set : public auto_vec <uint64_t, 1>
1372 typedef uint64_t *iterator;
1374 int_set ();
1375 int_set (uint64_t);
1376 int_set (const int_set &);
1378 int_set &operator = (const int_set &);
1380 iterator begin ();
1381 iterator end ();
1384 int_set::int_set () {}
1386 int_set::int_set (uint64_t label)
1388 safe_push (label);
1391 int_set::int_set (const int_set &other)
1393 safe_splice (other);
1396 int_set &
1397 int_set::operator = (const int_set &other)
1399 truncate (0);
1400 safe_splice (other);
1401 return *this;
1404 int_set::iterator
1405 int_set::begin ()
1407 return address ();
1410 int_set::iterator
1411 int_set::end ()
1413 return address () + length ();
1416 bool
1417 operator == (const int_set &a, const int_set &b)
1419 if (a.length () != b.length ())
1420 return false;
1421 for (unsigned int i = 0; i < a.length (); ++i)
1422 if (a[i] != b[i])
1423 return false;
1424 return true;
1427 bool
1428 operator != (const int_set &a, const int_set &b)
1430 return !operator == (a, b);
1433 struct decision;
1435 /* Represents a transition between states, dependent on the result of
1436 a test T. */
1437 struct transition
1439 transition (const int_set &, state *, bool);
1441 void set_parent (list_head <transition> *);
1443 /* Links to other transitions for T. Always null for boolean tests. */
1444 transition *prev, *next;
1446 /* The transition should be taken when T has one of these values.
1447 E.g. for rtx_test::CODE this is a set of codes, while for booleans like
1448 rtx_test::PREDICATE it is always a singleton "true". The labels are
1449 sorted in ascending order. */
1450 int_set labels;
1452 /* The source decision. */
1453 decision *from;
1455 /* The target state. */
1456 state *to;
1458 /* True if TO would function correctly even if TEST wasn't performed.
1459 E.g. it isn't necessary to check whether GET_MODE (x1) is SImode
1460 before calling register_operand (x1, SImode), since register_operand
1461 performs its own mode check. However, checking GET_MODE can be a cheap
1462 way of disambiguating SImode and DImode register operands. */
1463 bool optional;
1465 /* True if LABELS contains parameter numbers rather than constants.
1466 E.g. if this is true for a rtx_test::CODE, the label is the number
1467 of an rtx_code parameter rather than an rtx_code itself.
1468 LABELS is always a singleton when this variable is true. */
1469 bool is_param;
1472 /* Represents a test and the action that should be taken on the result.
1473 If a transition exists for the test outcome, the machine switches
1474 to the transition's target state. If no suitable transition exists,
1475 the machine either falls through to the next decision or, if there are no
1476 more decisions to try, fails the match. */
1477 struct decision : list_head <transition>
1479 decision (const rtx_test &);
1481 void set_parent (list_head <decision> *s);
1482 bool if_statement_p (uint64_t * = 0) const;
1484 /* The state to which this decision belongs. */
1485 state *s;
1487 /* Links to other decisions in the same state. */
1488 decision *prev, *next;
1490 /* The test to perform. */
1491 rtx_test test;
1494 /* Represents one machine state. For each state the machine tries a list
1495 of decisions, in order, and acts on the first match. It fails without
1496 further backtracking if no decisions match. */
1497 struct state : list_head <decision>
1499 void set_parent (list_head <state> *) {}
1502 transition::transition (const int_set &labels_in, state *to_in,
1503 bool optional_in)
1504 : prev (0), next (0), labels (labels_in), from (0), to (to_in),
1505 optional (optional_in), is_param (false) {}
1507 /* Set the source decision of the transition. */
1509 void
1510 transition::set_parent (list_head <transition> *from_in)
1512 from = static_cast <decision *> (from_in);
1515 decision::decision (const rtx_test &test_in)
1516 : prev (0), next (0), test (test_in) {}
1518 /* Set the state to which this decision belongs. */
1520 void
1521 decision::set_parent (list_head <decision> *s_in)
1523 s = static_cast <state *> (s_in);
1526 /* Return true if the decision has a single transition with a single label.
1527 If so, return the label in *LABEL if nonnull. */
1529 inline bool
1530 decision::if_statement_p (uint64_t *label) const
1532 if (singleton () && first->labels.length () == 1)
1534 if (label)
1535 *label = first->labels[0];
1536 return true;
1538 return false;
1541 /* Add to FROM a decision that performs TEST and has a single transition
1542 TRANS. */
1544 static void
1545 add_decision (state *from, const rtx_test &test, transition *trans)
1547 decision *d = new decision (test);
1548 from->push_back (d);
1549 d->push_back (trans);
1552 /* Add a transition from FROM to a new, empty state that is taken
1553 when TEST == LABELS. OPTIONAL says whether the new transition
1554 should be optional. Return the new state. */
1556 static state *
1557 add_decision (state *from, const rtx_test &test, int_set labels, bool optional)
1559 state *to = new state;
1560 add_decision (from, test, new transition (labels, to, optional));
1561 return to;
1564 /* Insert a decision before decisions R to make them dependent on
1565 TEST == LABELS. OPTIONAL says whether the new transition should be
1566 optional. */
1568 static decision *
1569 insert_decision_before (state::range r, const rtx_test &test,
1570 const int_set &labels, bool optional)
1572 decision *newd = new decision (test);
1573 state *news = new state;
1574 newd->push_back (new transition (labels, news, optional));
1575 r.start->s->replace (r, newd);
1576 news->push_back (r);
1577 return newd;
1580 /* Remove any optional transitions from S that turned out not to be useful. */
1582 static void
1583 collapse_optional_decisions (state *s)
1585 decision *d = s->first;
1586 while (d)
1588 decision *next = d->next;
1589 for (transition *trans = d->first; trans; trans = trans->next)
1590 collapse_optional_decisions (trans->to);
1591 /* A decision with a single optional transition doesn't help
1592 partition the potential matches and so is unlikely to be
1593 worthwhile. In particular, if the decision that performs the
1594 test is the last in the state, the best it could do is reject
1595 an invalid pattern slightly earlier. If instead the decision
1596 is not the last in the state, the condition it tests could hold
1597 even for the later decisions in the state. The best it can do
1598 is save work in some cases where only the later decisions can
1599 succeed.
1601 In both cases the optional transition would add extra work to
1602 successful matches when the tested condition holds. */
1603 if (transition *trans = d->singleton ())
1604 if (trans->optional)
1605 s->replace (d, trans->to->release ());
1606 d = next;
1610 /* Try to squash several separate tests into simpler ones. */
1612 static void
1613 simplify_tests (state *s)
1615 for (decision *d = s->first; d; d = d->next)
1617 uint64_t label;
1618 /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N
1619 into checks for const_int_rtx[N'], if N is suitably small. */
1620 if (d->test.kind == rtx_test::CODE
1621 && d->if_statement_p (&label)
1622 && label == CONST_INT)
1623 if (decision *second = d->first->to->singleton ())
1624 if (d->test.pos == second->test.pos
1625 && second->test.kind == rtx_test::WIDE_INT_FIELD
1626 && second->test.u.opno == 0
1627 && second->if_statement_p (&label)
1628 && IN_RANGE (int64_t (label),
1629 -MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT))
1631 d->test.kind = rtx_test::SAVED_CONST_INT;
1632 d->test.u.integer.is_param = false;
1633 d->test.u.integer.value = label;
1634 d->replace (d->first, second->release ());
1635 d->first->labels[0] = true;
1637 /* If we have a CODE test followed by a PREDICATE test, rely on
1638 the predicate to test the code.
1640 This case exists for match_operators. We initially treat the
1641 CODE test for a match_operator as non-optional so that we can
1642 safely move down to its operands. It may turn out that all
1643 paths that reach that code test require the same predicate
1644 to be true. cse_tests will then put the predicate test in
1645 series with the code test. */
1646 if (d->test.kind == rtx_test::CODE)
1647 if (transition *trans = d->singleton ())
1649 state *s = trans->to;
1650 while (decision *d2 = s->singleton ())
1652 if (d->test.pos != d2->test.pos)
1653 break;
1654 transition *trans2 = d2->singleton ();
1655 if (!trans2)
1656 break;
1657 if (d2->test.kind == rtx_test::PREDICATE)
1659 d->test = d2->test;
1660 trans->labels = int_set (true);
1661 s->replace (d2, trans2->to->release ());
1662 break;
1664 s = trans2->to;
1667 for (transition *trans = d->first; trans; trans = trans->next)
1668 simplify_tests (trans->to);
1672 /* Return true if all successful returns passing through D require the
1673 condition tested by COMMON to be true.
1675 When returning true, add all transitions like COMMON in D to WHERE.
1676 WHERE may contain a partial result on failure. */
1678 static bool
1679 common_test_p (decision *d, transition *common, vec <transition *> *where)
1681 if (d->test.kind == rtx_test::ACCEPT)
1682 /* We found a successful return that didn't require COMMON. */
1683 return false;
1684 if (d->test == common->from->test)
1686 transition *trans = d->singleton ();
1687 if (!trans
1688 || trans->optional != common->optional
1689 || trans->labels != common->labels)
1690 return false;
1691 where->safe_push (trans);
1692 return true;
1694 for (transition *trans = d->first; trans; trans = trans->next)
1695 for (decision *subd = trans->to->first; subd; subd = subd->next)
1696 if (!common_test_p (subd, common, where))
1697 return false;
1698 return true;
1701 /* Indicates that we have tested GET_CODE (X) for a particular rtx X. */
1702 const unsigned char TESTED_CODE = 1;
1704 /* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */
1705 const unsigned char TESTED_VECLEN = 2;
1707 /* Represents a set of conditions that are known to hold. */
1708 struct known_conditions
1710 /* A mask of TESTED_ values for each position, indexed by the position's
1711 id field. */
1712 auto_vec <unsigned char> position_tests;
1714 /* Index N says whether operands[N] has been set. */
1715 auto_vec <bool> set_operands;
1717 /* A guranteed lower bound on the value of peep2_current_count. */
1718 int peep2_count;
1721 /* Return true if TEST can safely be performed at D, where
1722 the conditions in KC hold. TEST is known to occur along the
1723 first path from D (i.e. always following the first transition
1724 of the first decision). Any intervening tests can be used as
1725 negative proof that hoisting isn't safe, but only KC can be used
1726 as positive proof. */
1728 static bool
1729 safe_to_hoist_p (decision *d, const rtx_test &test, known_conditions *kc)
1731 switch (test.kind)
1733 case rtx_test::C_TEST:
1734 /* In general, C tests require everything else to have been
1735 verified and all operands to have been set up. */
1736 return false;
1738 case rtx_test::ACCEPT:
1739 /* Don't accept something before all conditions have been tested. */
1740 return false;
1742 case rtx_test::PREDICATE:
1743 /* Don't move a predicate over a test for VECLEN_GE, since the
1744 predicate used in a match_parallel can legitimately expect the
1745 length to be checked first. */
1746 for (decision *subd = d;
1747 subd->test != test;
1748 subd = subd->first->to->first)
1749 if (subd->test.pos == test.pos
1750 && subd->test.kind == rtx_test::VECLEN_GE)
1751 return false;
1752 goto any_rtx;
1754 case rtx_test::DUPLICATE:
1755 /* Don't test for a match_dup until the associated operand has
1756 been set. */
1757 if (!kc->set_operands[test.u.opno])
1758 return false;
1759 goto any_rtx;
1761 case rtx_test::CODE:
1762 case rtx_test::MODE:
1763 case rtx_test::SAVED_CONST_INT:
1764 case rtx_test::SET_OP:
1765 any_rtx:
1766 /* Check whether it is safe to access the rtx under test. */
1767 switch (test.pos->type)
1769 case POS_PEEP2_INSN:
1770 return test.pos->arg < kc->peep2_count;
1772 case POS_XEXP:
1773 return kc->position_tests[test.pos->base->id] & TESTED_CODE;
1775 case POS_XVECEXP0:
1776 return kc->position_tests[test.pos->base->id] & TESTED_VECLEN;
1778 gcc_unreachable ();
1780 case rtx_test::REGNO_FIELD:
1781 case rtx_test::INT_FIELD:
1782 case rtx_test::WIDE_INT_FIELD:
1783 case rtx_test::VECLEN:
1784 case rtx_test::VECLEN_GE:
1785 /* These tests access a specific part of an rtx, so are only safe
1786 once we know what the rtx is. */
1787 return kc->position_tests[test.pos->id] & TESTED_CODE;
1789 case rtx_test::PEEP2_COUNT:
1790 case rtx_test::HAVE_NUM_CLOBBERS:
1791 /* These tests can be performed anywhere. */
1792 return true;
1794 case rtx_test::PATTERN:
1795 gcc_unreachable ();
1797 gcc_unreachable ();
1800 /* Look for a transition that is taken by all successful returns from a range
1801 of decisions starting at OUTER and that would be better performed by
1802 OUTER's state instead. On success, store all instances of that transition
1803 in WHERE and return the last decision in the range. The range could
1804 just be OUTER, or it could include later decisions as well.
1806 WITH_POSITION_P is true if only tests with position POS should be tried,
1807 false if any test should be tried. WORTHWHILE_SINGLE_P is true if the
1808 result is useful even when the range contains just a single decision
1809 with a single transition. KC are the conditions that are known to
1810 hold at OUTER. */
1812 static decision *
1813 find_common_test (decision *outer, bool with_position_p,
1814 position *pos, bool worthwhile_single_p,
1815 known_conditions *kc, vec <transition *> *where)
1817 /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains
1818 just a single decision is useful, regardless of the number of
1819 transitions it has. */
1820 if (!outer->singleton ())
1821 worthwhile_single_p = true;
1822 /* Quick exit if we don't have enough decisions to form a worthwhile
1823 range. */
1824 if (!worthwhile_single_p && !outer->next)
1825 return 0;
1826 /* Follow the first chain down, as one example of a path that needs
1827 to contain the common test. */
1828 for (decision *d = outer; d; d = d->first->to->first)
1830 transition *trans = d->singleton ();
1831 if (trans
1832 && (!with_position_p || d->test.pos == pos)
1833 && safe_to_hoist_p (outer, d->test, kc))
1835 if (common_test_p (outer, trans, where))
1837 if (!outer->next)
1838 /* We checked above whether the move is worthwhile. */
1839 return outer;
1840 /* See how many decisions in OUTER's chain could reuse
1841 the same test. */
1842 decision *outer_end = outer;
1845 unsigned int length = where->length ();
1846 if (!common_test_p (outer_end->next, trans, where))
1848 where->truncate (length);
1849 break;
1851 outer_end = outer_end->next;
1853 while (outer_end->next);
1854 /* It is worth moving TRANS if it can be shared by more than
1855 one decision. */
1856 if (outer_end != outer || worthwhile_single_p)
1857 return outer_end;
1859 where->truncate (0);
1862 return 0;
1865 /* Try to promote common subtests in S to a single, shared decision.
1866 Also try to bunch tests for the same position together. POS is the
1867 position of the rtx tested before reaching S. KC are the conditions
1868 that are known to hold on entry to S. */
1870 static void
1871 cse_tests (position *pos, state *s, known_conditions *kc)
1873 for (decision *d = s->first; d; d = d->next)
1875 auto_vec <transition *, 16> where;
1876 if (d->test.pos)
1878 /* Try to find conditions that don't depend on a particular rtx,
1879 such as pnum_clobbers != NULL or peep2_current_count >= X.
1880 It's usually better to check these conditions as soon as
1881 possible, so the change is worthwhile even if there is
1882 only one copy of the test. */
1883 decision *endd = find_common_test (d, true, 0, true, kc, &where);
1884 if (!endd && d->test.pos != pos)
1885 /* Try to find other conditions related to position POS
1886 before moving to the new position. Again, this is
1887 worthwhile even if there is only one copy of the test,
1888 since it means that fewer position variables are live
1889 at a given time. */
1890 endd = find_common_test (d, true, pos, true, kc, &where);
1891 if (!endd)
1892 /* Try to find any condition that is used more than once. */
1893 endd = find_common_test (d, false, 0, false, kc, &where);
1894 if (endd)
1896 transition *common = where[0];
1897 /* Replace [D, ENDD] with a test like COMMON. We'll recurse
1898 on the common test and see the original D again next time. */
1899 d = insert_decision_before (state::range (d, endd),
1900 common->from->test,
1901 common->labels,
1902 common->optional);
1903 /* Remove the old tests. */
1904 while (!where.is_empty ())
1906 transition *trans = where.pop ();
1907 trans->from->s->replace (trans->from, trans->to->release ());
1912 /* Make sure that safe_to_hoist_p isn't being overly conservative.
1913 It should realize that D's test is safe in the current
1914 environment. */
1915 gcc_assert (d->test.kind == rtx_test::C_TEST
1916 || d->test.kind == rtx_test::ACCEPT
1917 || safe_to_hoist_p (d, d->test, kc));
1919 /* D won't be changed any further by the current optimization.
1920 Recurse with the state temporarily updated to include D. */
1921 int prev = 0;
1922 switch (d->test.kind)
1924 case rtx_test::CODE:
1925 prev = kc->position_tests[d->test.pos->id];
1926 kc->position_tests[d->test.pos->id] |= TESTED_CODE;
1927 break;
1929 case rtx_test::VECLEN:
1930 case rtx_test::VECLEN_GE:
1931 prev = kc->position_tests[d->test.pos->id];
1932 kc->position_tests[d->test.pos->id] |= TESTED_VECLEN;
1933 break;
1935 case rtx_test::SET_OP:
1936 prev = kc->set_operands[d->test.u.opno];
1937 gcc_assert (!prev);
1938 kc->set_operands[d->test.u.opno] = true;
1939 break;
1941 case rtx_test::PEEP2_COUNT:
1942 prev = kc->peep2_count;
1943 kc->peep2_count = MAX (prev, d->test.u.min_len);
1944 break;
1946 default:
1947 break;
1949 for (transition *trans = d->first; trans; trans = trans->next)
1950 cse_tests (d->test.pos ? d->test.pos : pos, trans->to, kc);
1951 switch (d->test.kind)
1953 case rtx_test::CODE:
1954 case rtx_test::VECLEN:
1955 case rtx_test::VECLEN_GE:
1956 kc->position_tests[d->test.pos->id] = prev;
1957 break;
1959 case rtx_test::SET_OP:
1960 kc->set_operands[d->test.u.opno] = prev;
1961 break;
1963 case rtx_test::PEEP2_COUNT:
1964 kc->peep2_count = prev;
1965 break;
1967 default:
1968 break;
1973 /* Return the type of value that can be used to parameterize test KIND,
1974 or parameter::UNSET if none. */
1976 parameter::type_enum
1977 transition_parameter_type (rtx_test::kind_enum kind)
1979 switch (kind)
1981 case rtx_test::CODE:
1982 return parameter::CODE;
1984 case rtx_test::MODE:
1985 return parameter::MODE;
1987 case rtx_test::REGNO_FIELD:
1988 return parameter::UINT;
1990 case rtx_test::INT_FIELD:
1991 case rtx_test::VECLEN:
1992 case rtx_test::PATTERN:
1993 return parameter::INT;
1995 case rtx_test::WIDE_INT_FIELD:
1996 return parameter::WIDE_INT;
1998 case rtx_test::PEEP2_COUNT:
1999 case rtx_test::VECLEN_GE:
2000 case rtx_test::SAVED_CONST_INT:
2001 case rtx_test::PREDICATE:
2002 case rtx_test::DUPLICATE:
2003 case rtx_test::HAVE_NUM_CLOBBERS:
2004 case rtx_test::C_TEST:
2005 case rtx_test::SET_OP:
2006 case rtx_test::ACCEPT:
2007 return parameter::UNSET;
2009 gcc_unreachable ();
2012 /* Initialize the pos_operand fields of each state reachable from S.
2013 If OPERAND_POS[ID] >= 0, the position with id ID is stored in
2014 operands[OPERAND_POS[ID]] on entry to S. */
2016 static void
2017 find_operand_positions (state *s, vec <int> &operand_pos)
2019 for (decision *d = s->first; d; d = d->next)
2021 int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1);
2022 if (this_operand >= 0)
2023 d->test.pos_operand = this_operand;
2024 if (d->test.kind == rtx_test::SET_OP)
2025 operand_pos[d->test.pos->id] = d->test.u.opno;
2026 for (transition *trans = d->first; trans; trans = trans->next)
2027 find_operand_positions (trans->to, operand_pos);
2028 if (d->test.kind == rtx_test::SET_OP)
2029 operand_pos[d->test.pos->id] = this_operand;
2033 /* Statistics about a matching routine. */
2034 struct stats
2036 stats ();
2038 /* The total number of decisions in the routine, excluding trivial
2039 ones that never fail. */
2040 unsigned int num_decisions;
2042 /* The number of non-trivial decisions on the longest path through
2043 the routine, and the return value that contributes most to that
2044 long path. */
2045 unsigned int longest_path;
2046 int longest_path_code;
2048 /* The maximum number of times that a single call to the routine
2049 can backtrack, and the value returned at the end of that path.
2050 "Backtracking" here means failing one decision in state and
2051 going onto to the next. */
2052 unsigned int longest_backtrack;
2053 int longest_backtrack_code;
2056 stats::stats ()
2057 : num_decisions (0), longest_path (0), longest_path_code (-1),
2058 longest_backtrack (0), longest_backtrack_code (-1) {}
2060 /* Return statistics about S. */
2062 static stats
2063 get_stats (state *s)
2065 stats for_s;
2066 unsigned int longest_path = 0;
2067 for (decision *d = s->first; d; d = d->next)
2069 /* Work out the statistics for D. */
2070 stats for_d;
2071 for (transition *trans = d->first; trans; trans = trans->next)
2073 stats for_trans = get_stats (trans->to);
2074 for_d.num_decisions += for_trans.num_decisions;
2075 /* Each transition is mutually-exclusive, so just pick the
2076 longest of the individual paths. */
2077 if (for_d.longest_path <= for_trans.longest_path)
2079 for_d.longest_path = for_trans.longest_path;
2080 for_d.longest_path_code = for_trans.longest_path_code;
2082 /* Likewise for backtracking. */
2083 if (for_d.longest_backtrack <= for_trans.longest_backtrack)
2085 for_d.longest_backtrack = for_trans.longest_backtrack;
2086 for_d.longest_backtrack_code = for_trans.longest_backtrack_code;
2090 /* Account for D's test in its statistics. */
2091 if (!d->test.single_outcome_p ())
2093 for_d.num_decisions += 1;
2094 for_d.longest_path += 1;
2096 if (d->test.kind == rtx_test::ACCEPT)
2098 for_d.longest_path_code = d->test.u.acceptance.u.full.code;
2099 for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code;
2102 /* Keep a running count of the number of backtracks. */
2103 if (d->prev)
2104 for_s.longest_backtrack += 1;
2106 /* Accumulate D's statistics into S's. */
2107 for_s.num_decisions += for_d.num_decisions;
2108 for_s.longest_path += for_d.longest_path;
2109 for_s.longest_backtrack += for_d.longest_backtrack;
2111 /* Use the code from the decision with the longest individual path,
2112 since that's more likely to be useful if trying to make the
2113 path shorter. In the event of a tie, pick the later decision,
2114 since that's closer to the end of the path. */
2115 if (longest_path <= for_d.longest_path)
2117 longest_path = for_d.longest_path;
2118 for_s.longest_path_code = for_d.longest_path_code;
2121 /* Later decisions in a state are necessarily in a longer backtrack
2122 than earlier decisions. */
2123 for_s.longest_backtrack_code = for_d.longest_backtrack_code;
2125 return for_s;
2128 /* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
2130 static void
2131 optimize_subroutine_group (const char *type, state *root)
2133 /* Remove optional transitions that turned out not to be worthwhile. */
2134 if (collapse_optional_decisions_p)
2135 collapse_optional_decisions (root);
2137 /* Try to remove duplicated tests and to rearrange tests into a more
2138 logical order. */
2139 if (cse_tests_p)
2141 known_conditions kc;
2142 kc.position_tests.safe_grow_cleared (num_positions);
2143 kc.set_operands.safe_grow_cleared (num_operands);
2144 kc.peep2_count = 1;
2145 cse_tests (&root_pos, root, &kc);
2148 /* Try to simplify two or more tests into one. */
2149 if (simplify_tests_p)
2150 simplify_tests (root);
2152 /* Try to use operands[] instead of xN variables. */
2153 if (use_operand_variables_p)
2155 auto_vec <int> operand_pos (num_positions);
2156 for (unsigned int i = 0; i < num_positions; ++i)
2157 operand_pos.quick_push (-1);
2158 find_operand_positions (root, operand_pos);
2161 /* Print a summary of the new state. */
2162 stats st = get_stats (root);
2163 fprintf (stderr, "Statistics for %s:\n", type);
2164 fprintf (stderr, " Number of decisions: %6d\n", st.num_decisions);
2165 fprintf (stderr, " longest path: %6d (code: %6d)\n",
2166 st.longest_path, st.longest_path_code);
2167 fprintf (stderr, " longest backtrack: %6d (code: %6d)\n",
2168 st.longest_backtrack, st.longest_backtrack_code);
2171 struct merge_pattern_info;
2173 /* Represents a transition from one pattern to another. */
2174 struct merge_pattern_transition
2176 merge_pattern_transition (merge_pattern_info *);
2178 /* The target pattern. */
2179 merge_pattern_info *to;
2181 /* The parameters that the source pattern passes to the target pattern.
2182 "parameter (TYPE, true, I)" represents parameter I of the source
2183 pattern. */
2184 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2187 merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in)
2188 : to (to_in)
2192 /* Represents a pattern that can might match several states. The pattern
2193 may replace parts of the test with a parameter value. It may also
2194 replace transition labels with parameters. */
2195 struct merge_pattern_info
2197 merge_pattern_info (unsigned int);
2199 /* If PARAM_TEST_P, the state's singleton test should be generalized
2200 to use the runtime value of PARAMS[PARAM_TEST]. */
2201 unsigned int param_test : 8;
2203 /* If PARAM_TRANSITION_P, the state's single transition label should
2204 be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */
2205 unsigned int param_transition : 8;
2207 /* True if we have decided to generalize the root decision's test,
2208 as per PARAM_TEST. */
2209 unsigned int param_test_p : 1;
2211 /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
2212 unsigned int param_transition_p : 1;
2214 /* True if the contents of the structure are completely filled in. */
2215 unsigned int complete_p : 1;
2217 /* The number of pseudo-statements in the pattern. Used to decide
2218 whether it's big enough to break out into a subroutine. */
2219 unsigned int num_statements;
2221 /* The number of states that use this pattern. */
2222 unsigned int num_users;
2224 /* The number of distinct success values that the pattern returns. */
2225 unsigned int num_results;
2227 /* This array has one element for each runtime parameter to the pattern.
2228 PARAMS[I] gives the default value of parameter I, which is always
2229 constant.
2231 These default parameters are used in cases where we match the
2232 pattern against some state S1, then add more parameters while
2233 matching against some state S2. S1 is then left passing fewer
2234 parameters than S2. The array gives us enough informatino to
2235 construct a full parameter list for S1 (see update_parameters).
2237 If we decide to create a subroutine for this pattern,
2238 PARAMS[I].type determines the C type of parameter I. */
2239 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2241 /* All states that match this pattern must have the same number of
2242 transitions. TRANSITIONS[I] describes the subpattern for transition
2243 number I; it is null if transition I represents a successful return
2244 from the pattern. */
2245 auto_vec <merge_pattern_transition *, 1> transitions;
2247 /* The routine associated with the pattern, or null if we haven't generated
2248 one yet. */
2249 pattern_routine *routine;
2252 merge_pattern_info::merge_pattern_info (unsigned int num_transitions)
2253 : param_test (0),
2254 param_transition (0),
2255 param_test_p (false),
2256 param_transition_p (false),
2257 complete_p (false),
2258 num_statements (0),
2259 num_users (0),
2260 num_results (0),
2261 routine (0)
2263 transitions.safe_grow_cleared (num_transitions);
2266 /* Describes one way of matching a particular state to a particular
2267 pattern. */
2268 struct merge_state_result
2270 merge_state_result (merge_pattern_info *, position *, merge_state_result *);
2272 /* A pattern that matches the state. */
2273 merge_pattern_info *pattern;
2275 /* If we decide to use this match and create a subroutine for PATTERN,
2276 the state should pass the rtx at position ROOT to the pattern's
2277 rtx parameter. A null root means that the pattern doesn't need
2278 an rtx parameter; all the rtxes it matches come from elsewhere. */
2279 position *root;
2281 /* The parameters that should be passed to PATTERN for this state.
2282 If the array is shorter than PATTERN->params, the missing entries
2283 should be taken from the corresponding element of PATTERN->params. */
2284 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2286 /* An earlier match for the same state, or null if none. Patterns
2287 matched by earlier entries are smaller than PATTERN. */
2288 merge_state_result *prev;
2291 merge_state_result::merge_state_result (merge_pattern_info *pattern_in,
2292 position *root_in,
2293 merge_state_result *prev_in)
2294 : pattern (pattern_in), root (root_in), prev (prev_in)
2297 /* Information about a state, used while trying to match it against
2298 a pattern. */
2299 struct merge_state_info
2301 merge_state_info (state *);
2303 /* The state itself. */
2304 state *s;
2306 /* Index I gives information about the target of transition I. */
2307 merge_state_info *to_states;
2309 /* The number of transitions in S. */
2310 unsigned int num_transitions;
2312 /* True if the state has been deleted in favor of a call to a
2313 pattern routine. */
2314 bool merged_p;
2316 /* The previous state that might be a merge candidate for S, or null
2317 if no previous states could be merged with S. */
2318 merge_state_info *prev_same_test;
2320 /* A list of pattern matches for this state. */
2321 merge_state_result *res;
2324 merge_state_info::merge_state_info (state *s_in)
2325 : s (s_in),
2326 to_states (0),
2327 num_transitions (0),
2328 merged_p (false),
2329 prev_same_test (0),
2330 res (0) {}
2332 /* True if PAT would be useful as a subroutine. */
2334 static bool
2335 useful_pattern_p (merge_pattern_info *pat)
2337 return pat->num_statements >= MIN_COMBINE_COST;
2340 /* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
2341 into PAT1's C routine. */
2343 static bool
2344 same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2)
2346 return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2);
2349 /* PAT was previously matched against SINFO based on tentative matches
2350 for the target states of SINFO's state. Return true if the match
2351 still holds; that is, if the target states of SINFO's state still
2352 match the corresponding transitions of PAT. */
2354 static bool
2355 valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2357 for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2358 if (merge_pattern_transition *ptrans = pat->transitions[j])
2360 merge_state_result *to_res = sinfo->to_states[j].res;
2361 if (!to_res || to_res->pattern != ptrans->to)
2362 return false;
2364 return true;
2367 /* Remove any matches that are no longer valid from the head of SINFO's
2368 list of matches. */
2370 static void
2371 prune_invalid_results (merge_state_info *sinfo)
2373 while (sinfo->res && !valid_result_p (sinfo->res->pattern, sinfo))
2375 sinfo->res = sinfo->res->prev;
2376 gcc_assert (sinfo->res);
2380 /* Return true if PAT represents the biggest posssible match for SINFO;
2381 that is, if the next action of SINFO's state on return from PAT will
2382 be something that cannot be merged with any other state. */
2384 static bool
2385 complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2387 for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2388 if (sinfo->to_states[j].res && !pat->transitions[j])
2389 return false;
2390 return true;
2393 /* Update TO for any parameters that have been added to FROM since TO
2394 was last set. The extra parameters in FROM will be constants or
2395 instructions to duplicate earlier parameters. */
2397 static void
2398 update_parameters (vec <parameter> &to, const vec <parameter> &from)
2400 for (unsigned int i = to.length (); i < from.length (); ++i)
2401 to.quick_push (from[i]);
2404 /* Return true if A and B can be tested by a single test. If the test
2405 can be parameterised, store the parameter value for A in *PARAMA and
2406 the parameter value for B in *PARAMB, otherwise leave PARAMA and
2407 PARAMB alone. */
2409 static bool
2410 compatible_tests_p (const rtx_test &a, const rtx_test &b,
2411 parameter *parama, parameter *paramb)
2413 if (a.kind != b.kind)
2414 return false;
2415 switch (a.kind)
2417 case rtx_test::PREDICATE:
2418 if (a.u.predicate.data != b.u.predicate.data)
2419 return false;
2420 *parama = parameter (parameter::MODE, false, a.u.predicate.mode);
2421 *paramb = parameter (parameter::MODE, false, b.u.predicate.mode);
2422 return true;
2424 case rtx_test::SAVED_CONST_INT:
2425 *parama = parameter (parameter::INT, false, a.u.integer.value);
2426 *paramb = parameter (parameter::INT, false, b.u.integer.value);
2427 return true;
2429 default:
2430 return a == b;
2434 /* PARAMS is an array of the parameters that a state is going to pass
2435 to a pattern routine. It is still incomplete; index I has a kind of
2436 parameter::UNSET if we don't yet know what the state will pass
2437 as parameter I. Try to make parameter ID equal VALUE, returning
2438 true on success. */
2440 static bool
2441 set_parameter (vec <parameter> &params, unsigned int id,
2442 const parameter &value)
2444 if (params[id].type == parameter::UNSET)
2446 if (force_unique_params_p)
2447 for (unsigned int i = 0; i < params.length (); ++i)
2448 if (params[i] == value)
2449 return false;
2450 params[id] = value;
2451 return true;
2453 return params[id] == value;
2456 /* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
2457 set of parameters that a particular state is going to pass to
2458 that pattern.
2460 Try to extend PARAMS1 and PARAMS2 so that there is a parameter
2461 that is equal to PARAM1 for the state and has a default value of
2462 PARAM2. Parameters beginning at START were added as part of the
2463 same match and so may be reused. */
2465 static bool
2466 add_parameter (vec <parameter> &params1, vec <parameter> &params2,
2467 const parameter &param1, const parameter &param2,
2468 unsigned int start, unsigned int *res)
2470 gcc_assert (params1.length () == params2.length ());
2471 gcc_assert (!param1.is_param && !param2.is_param);
2473 for (unsigned int i = start; i < params2.length (); ++i)
2474 if (params1[i] == param1 && params2[i] == param2)
2476 *res = i;
2477 return true;
2480 if (force_unique_params_p)
2481 for (unsigned int i = 0; i < params2.length (); ++i)
2482 if (params1[i] == param1 || params2[i] == param2)
2483 return false;
2485 if (params2.length () >= MAX_PATTERN_PARAMS)
2486 return false;
2488 *res = params2.length ();
2489 params1.quick_push (param1);
2490 params2.quick_push (param2);
2491 return true;
2494 /* If *ROOTA is nonnull, return true if the same sequence of steps are
2495 required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA
2496 is null, update it if necessary in order to make the condition hold. */
2498 static bool
2499 merge_relative_positions (position **roota, position *a,
2500 position *rootb, position *b)
2502 if (!relative_patterns_p)
2504 if (a != b)
2505 return false;
2506 if (!*roota)
2508 *roota = rootb;
2509 return true;
2511 return *roota == rootb;
2513 /* If B does not belong to the same instruction as ROOTB, we don't
2514 start with ROOTB but instead start with a call to peep2_next_insn.
2515 In that case the sequences for B and A are identical iff B and A
2516 are themselves identical. */
2517 if (rootb->insn_id != b->insn_id)
2518 return a == b;
2519 while (rootb != b)
2521 if (!a || b->type != a->type || b->arg != a->arg)
2522 return false;
2523 b = b->base;
2524 a = a->base;
2526 if (!*roota)
2527 *roota = a;
2528 return *roota == a;
2531 /* A hasher of states that treats two states as "equal" if they might be
2532 merged (but trying to be more discriminating than "return true"). */
2533 struct test_pattern_hasher : nofree_ptr_hash <merge_state_info>
2535 static inline hashval_t hash (const value_type &);
2536 static inline bool equal (const value_type &, const compare_type &);
2539 hashval_t
2540 test_pattern_hasher::hash (merge_state_info *const &sinfo)
2542 inchash::hash h;
2543 decision *d = sinfo->s->singleton ();
2544 h.add_int (d->test.pos_operand + 1);
2545 if (!relative_patterns_p)
2546 h.add_int (d->test.pos ? d->test.pos->id + 1 : 0);
2547 h.add_int (d->test.kind);
2548 h.add_int (sinfo->num_transitions);
2549 return h.end ();
2552 bool
2553 test_pattern_hasher::equal (merge_state_info *const &sinfo1,
2554 merge_state_info *const &sinfo2)
2556 decision *d1 = sinfo1->s->singleton ();
2557 decision *d2 = sinfo2->s->singleton ();
2558 gcc_assert (d1 && d2);
2560 parameter new_param1, new_param2;
2561 return (d1->test.pos_operand == d2->test.pos_operand
2562 && (relative_patterns_p || d1->test.pos == d2->test.pos)
2563 && compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2)
2564 && sinfo1->num_transitions == sinfo2->num_transitions);
2567 /* Try to make the state described by SINFO1 use the same pattern as the
2568 state described by SINFO2. Return true on success.
2570 SINFO1 and SINFO2 are known to have the same hash value. */
2572 static bool
2573 merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2)
2575 merge_state_result *res2 = sinfo2->res;
2576 merge_pattern_info *pat = res2->pattern;
2578 /* Write to temporary arrays while matching, in case we have to abort
2579 half way through. */
2580 auto_vec <parameter, MAX_PATTERN_PARAMS> params1;
2581 auto_vec <parameter, MAX_PATTERN_PARAMS> params2;
2582 params1.quick_grow_cleared (pat->params.length ());
2583 params2.splice (pat->params);
2584 unsigned int start_param = params2.length ();
2586 /* An array for recording changes to PAT->transitions[?].params.
2587 All changes involve replacing a constant parameter with some
2588 PAT->params[N], where N is the second element of the pending_param. */
2589 typedef std::pair <parameter *, unsigned int> pending_param;
2590 auto_vec <pending_param, 32> pending_params;
2592 decision *d1 = sinfo1->s->singleton ();
2593 decision *d2 = sinfo2->s->singleton ();
2594 gcc_assert (d1 && d2);
2596 /* If D2 tests a position, SINFO1's root relative to D1 is the same
2597 as SINFO2's root relative to D2. */
2598 position *root1 = 0;
2599 position *root2 = res2->root;
2600 if (d2->test.pos_operand < 0
2601 && d1->test.pos
2602 && !merge_relative_positions (&root1, d1->test.pos,
2603 root2, d2->test.pos))
2604 return false;
2606 /* Check whether the patterns have the same shape. */
2607 unsigned int num_transitions = sinfo1->num_transitions;
2608 gcc_assert (num_transitions == sinfo2->num_transitions);
2609 for (unsigned int i = 0; i < num_transitions; ++i)
2610 if (merge_pattern_transition *ptrans = pat->transitions[i])
2612 merge_state_result *to1_res = sinfo1->to_states[i].res;
2613 merge_state_result *to2_res = sinfo2->to_states[i].res;
2614 merge_pattern_info *to_pat = ptrans->to;
2615 gcc_assert (to2_res && to2_res->pattern == to_pat);
2616 if (!to1_res || to1_res->pattern != to_pat)
2617 return false;
2618 if (to2_res->root
2619 && !merge_relative_positions (&root1, to1_res->root,
2620 root2, to2_res->root))
2621 return false;
2622 /* Match the parameters that TO1_RES passes to TO_PAT with the
2623 parameters that PAT passes to TO_PAT. */
2624 update_parameters (to1_res->params, to_pat->params);
2625 for (unsigned int j = 0; j < to1_res->params.length (); ++j)
2627 const parameter &param1 = to1_res->params[j];
2628 const parameter &param2 = ptrans->params[j];
2629 gcc_assert (!param1.is_param);
2630 if (param2.is_param)
2632 if (!set_parameter (params1, param2.value, param1))
2633 return false;
2635 else if (param1 != param2)
2637 unsigned int id;
2638 if (!add_parameter (params1, params2,
2639 param1, param2, start_param, &id))
2640 return false;
2641 /* Record that PAT should now pass parameter ID to TO_PAT,
2642 instead of the current contents of *PARAM2. We only
2643 make the change if the rest of the match succeeds. */
2644 pending_params.safe_push
2645 (pending_param (&ptrans->params[j], id));
2650 unsigned int param_test = pat->param_test;
2651 unsigned int param_transition = pat->param_transition;
2652 bool param_test_p = pat->param_test_p;
2653 bool param_transition_p = pat->param_transition_p;
2655 /* If the tests don't match exactly, try to parameterize them. */
2656 parameter new_param1, new_param2;
2657 if (!compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2))
2658 gcc_unreachable ();
2659 if (new_param1.type != parameter::UNSET)
2661 /* If the test has not already been parameterized, all existing
2662 matches use constant NEW_PARAM2. */
2663 if (param_test_p)
2665 if (!set_parameter (params1, param_test, new_param1))
2666 return false;
2668 else if (new_param1 != new_param2)
2670 if (!add_parameter (params1, params2, new_param1, new_param2,
2671 start_param, &param_test))
2672 return false;
2673 param_test_p = true;
2677 /* Match the transitions. */
2678 transition *trans1 = d1->first;
2679 transition *trans2 = d2->first;
2680 for (unsigned int i = 0; i < num_transitions; ++i)
2682 if (param_transition_p || trans1->labels != trans2->labels)
2684 /* We can only generalize a single transition with a single
2685 label. */
2686 if (num_transitions != 1
2687 || trans1->labels.length () != 1
2688 || trans2->labels.length () != 1)
2689 return false;
2691 /* Although we can match wide-int fields, in practice it leads
2692 to some odd results for const_vectors. We end up
2693 parameterizing the first N const_ints of the vector
2694 and then (once we reach the maximum number of parameters)
2695 we go on to match the other elements exactly. */
2696 if (d1->test.kind == rtx_test::WIDE_INT_FIELD)
2697 return false;
2699 /* See whether the label has a generalizable type. */
2700 parameter::type_enum param_type
2701 = transition_parameter_type (d1->test.kind);
2702 if (param_type == parameter::UNSET)
2703 return false;
2705 /* Match the labels using parameters. */
2706 new_param1 = parameter (param_type, false, trans1->labels[0]);
2707 if (param_transition_p)
2709 if (!set_parameter (params1, param_transition, new_param1))
2710 return false;
2712 else
2714 new_param2 = parameter (param_type, false, trans2->labels[0]);
2715 if (!add_parameter (params1, params2, new_param1, new_param2,
2716 start_param, &param_transition))
2717 return false;
2718 param_transition_p = true;
2721 trans1 = trans1->next;
2722 trans2 = trans2->next;
2725 /* Set any unset parameters to their default values. This occurs if some
2726 other state needed something to be parameterized in order to match SINFO2,
2727 but SINFO1 on its own does not. */
2728 for (unsigned int i = 0; i < params1.length (); ++i)
2729 if (params1[i].type == parameter::UNSET)
2730 params1[i] = params2[i];
2732 /* The match was successful. Commit all pending changes to PAT. */
2733 update_parameters (pat->params, params2);
2735 pending_param *pp;
2736 unsigned int i;
2737 FOR_EACH_VEC_ELT (pending_params, i, pp)
2738 *pp->first = parameter (pp->first->type, true, pp->second);
2740 pat->param_test = param_test;
2741 pat->param_transition = param_transition;
2742 pat->param_test_p = param_test_p;
2743 pat->param_transition_p = param_transition_p;
2745 /* Record the match of SINFO1. */
2746 merge_state_result *new_res1 = new merge_state_result (pat, root1,
2747 sinfo1->res);
2748 new_res1->params.splice (params1);
2749 sinfo1->res = new_res1;
2750 return true;
2753 /* The number of states that were removed by calling pattern routines. */
2754 static unsigned int pattern_use_states;
2756 /* The number of states used while defining pattern routines. */
2757 static unsigned int pattern_def_states;
2759 /* Information used while constructing a use or definition of a pattern
2760 routine. */
2761 struct create_pattern_info
2763 /* The routine itself. */
2764 pattern_routine *routine;
2766 /* The first unclaimed return value for this particular use or definition.
2767 We walk the substates of uses and definitions in the same order
2768 so each return value always refers to the same position within
2769 the pattern. */
2770 unsigned int next_result;
2773 static void populate_pattern_routine (create_pattern_info *,
2774 merge_state_info *, state *,
2775 const vec <parameter> &);
2777 /* SINFO matches a pattern for which we've decided to create a C routine.
2778 Return a decision that performs a call to the pattern routine,
2779 but leave the caller to add the transitions to it. Initialize CPI
2780 for this purpose. Also create a definition for the pattern routine,
2781 if it doesn't already have one.
2783 PARAMS are the parameters that SINFO passes to its pattern. */
2785 static decision *
2786 init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo,
2787 const vec <parameter> &params)
2789 state *s = sinfo->s;
2790 merge_state_result *res = sinfo->res;
2791 merge_pattern_info *pat = res->pattern;
2792 cpi->routine = pat->routine;
2793 if (!cpi->routine)
2795 /* We haven't defined the pattern routine yet, so create
2796 a definition now. */
2797 pattern_routine *routine = new pattern_routine;
2798 pat->routine = routine;
2799 cpi->routine = routine;
2800 routine->s = new state;
2801 routine->insn_p = false;
2802 routine->pnum_clobbers_p = false;
2804 /* Create an "idempotent" mapping of parameter I to parameter I.
2805 Also record the C type of each parameter to the routine. */
2806 auto_vec <parameter, MAX_PATTERN_PARAMS> def_params;
2807 for (unsigned int i = 0; i < pat->params.length (); ++i)
2809 def_params.quick_push (parameter (pat->params[i].type, true, i));
2810 routine->param_types.quick_push (pat->params[i].type);
2813 /* Any of the states that match the pattern could be used to
2814 create the routine definition. We might as well use SINFO
2815 since it's already to hand. This means that all positions
2816 in the definition will be relative to RES->root. */
2817 routine->pos = res->root;
2818 cpi->next_result = 0;
2819 populate_pattern_routine (cpi, sinfo, routine->s, def_params);
2820 gcc_assert (cpi->next_result == pat->num_results);
2822 /* Add the routine to the global list, after the subroutines
2823 that it calls. */
2824 routine->pattern_id = patterns.length ();
2825 patterns.safe_push (routine);
2828 /* Create a decision to call the routine, passing PARAMS to it. */
2829 pattern_use *use = new pattern_use;
2830 use->routine = pat->routine;
2831 use->params.splice (params);
2832 decision *d = new decision (rtx_test::pattern (res->root, use));
2834 /* If the original decision could use an element of operands[] instead
2835 of an rtx variable, try to transfer it to the new decision. */
2836 if (s->first->test.pos && res->root == s->first->test.pos)
2837 d->test.pos_operand = s->first->test.pos_operand;
2839 cpi->next_result = 0;
2840 return d;
2843 /* Make S return the next unclaimed pattern routine result for CPI. */
2845 static void
2846 add_pattern_acceptance (create_pattern_info *cpi, state *s)
2848 acceptance_type acceptance;
2849 acceptance.type = SUBPATTERN;
2850 acceptance.partial_p = false;
2851 acceptance.u.full.code = cpi->next_result;
2852 add_decision (s, rtx_test::accept (acceptance), true, false);
2853 cpi->next_result += 1;
2856 /* Initialize new empty state NEWS so that it implements SINFO's pattern
2857 (here referred to as "P"). P may be the top level of a pattern routine
2858 or a subpattern that should be inlined into its parent pattern's routine
2859 (as per same_pattern_p). The choice of SINFO for a top-level pattern is
2860 arbitrary; it could be any of the states that use P. The choice for
2861 subpatterns follows the choice for the parent pattern.
2863 PARAMS gives the value of each parameter to P in terms of the parameters
2864 to the top-level pattern. If P itself is the top level pattern, PARAMS[I]
2865 is always "parameter (TYPE, true, I)". */
2867 static void
2868 populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo,
2869 state *news, const vec <parameter> &params)
2871 pattern_def_states += 1;
2873 decision *d = sinfo->s->singleton ();
2874 merge_pattern_info *pat = sinfo->res->pattern;
2875 pattern_routine *routine = cpi->routine;
2877 /* Create a copy of D's test for the pattern routine and generalize it
2878 as appropriate. */
2879 decision *newd = new decision (d->test);
2880 gcc_assert (newd->test.pos_operand >= 0
2881 || !newd->test.pos
2882 || common_position (newd->test.pos,
2883 routine->pos) == routine->pos);
2884 if (pat->param_test_p)
2886 const parameter &param = params[pat->param_test];
2887 switch (newd->test.kind)
2889 case rtx_test::PREDICATE:
2890 newd->test.u.predicate.mode_is_param = param.is_param;
2891 newd->test.u.predicate.mode = param.value;
2892 break;
2894 case rtx_test::SAVED_CONST_INT:
2895 newd->test.u.integer.is_param = param.is_param;
2896 newd->test.u.integer.value = param.value;
2897 break;
2899 default:
2900 gcc_unreachable ();
2901 break;
2904 if (d->test.kind == rtx_test::C_TEST)
2905 routine->insn_p = true;
2906 else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS)
2907 routine->pnum_clobbers_p = true;
2908 news->push_back (newd);
2910 /* Fill in the transitions of NEWD. */
2911 unsigned int i = 0;
2912 for (transition *trans = d->first; trans; trans = trans->next)
2914 /* Create a new state to act as the target of the new transition. */
2915 state *to_news = new state;
2916 if (merge_pattern_transition *ptrans = pat->transitions[i])
2918 /* The pattern hasn't finished matching yet. Get the target
2919 pattern and the corresponding target state of SINFO. */
2920 merge_pattern_info *to_pat = ptrans->to;
2921 merge_state_info *to = sinfo->to_states + i;
2922 gcc_assert (to->res->pattern == to_pat);
2923 gcc_assert (ptrans->params.length () == to_pat->params.length ());
2925 /* Express the parameters to TO_PAT in terms of the parameters
2926 to the top-level pattern. */
2927 auto_vec <parameter, MAX_PATTERN_PARAMS> to_params;
2928 for (unsigned int j = 0; j < ptrans->params.length (); ++j)
2930 const parameter &param = ptrans->params[j];
2931 to_params.quick_push (param.is_param
2932 ? params[param.value]
2933 : param);
2936 if (same_pattern_p (pat, to_pat))
2937 /* TO_PAT is part of the current routine, so just recurse. */
2938 populate_pattern_routine (cpi, to, to_news, to_params);
2939 else
2941 /* TO_PAT should be matched by calling a separate routine. */
2942 create_pattern_info sub_cpi;
2943 decision *subd = init_pattern_use (&sub_cpi, to, to_params);
2944 routine->insn_p |= sub_cpi.routine->insn_p;
2945 routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p;
2947 /* Add the pattern routine call to the new target state. */
2948 to_news->push_back (subd);
2950 /* Add a transition for each successful call result. */
2951 for (unsigned int j = 0; j < to_pat->num_results; ++j)
2953 state *res = new state;
2954 add_pattern_acceptance (cpi, res);
2955 subd->push_back (new transition (j, res, false));
2959 else
2960 /* This transition corresponds to a successful match. */
2961 add_pattern_acceptance (cpi, to_news);
2963 /* Create the transition itself, generalizing as necessary. */
2964 transition *new_trans = new transition (trans->labels, to_news,
2965 trans->optional);
2966 if (pat->param_transition_p)
2968 const parameter &param = params[pat->param_transition];
2969 new_trans->is_param = param.is_param;
2970 new_trans->labels[0] = param.value;
2972 newd->push_back (new_trans);
2973 i += 1;
2977 /* USE is a decision that calls a pattern routine and SINFO is part of the
2978 original state tree that the call is supposed to replace. Add the
2979 transitions for SINFO and its substates to USE. */
2981 static void
2982 populate_pattern_use (create_pattern_info *cpi, decision *use,
2983 merge_state_info *sinfo)
2985 pattern_use_states += 1;
2986 gcc_assert (!sinfo->merged_p);
2987 sinfo->merged_p = true;
2988 merge_state_result *res = sinfo->res;
2989 merge_pattern_info *pat = res->pattern;
2990 decision *d = sinfo->s->singleton ();
2991 unsigned int i = 0;
2992 for (transition *trans = d->first; trans; trans = trans->next)
2994 if (pat->transitions[i])
2995 /* The target state is also part of the pattern. */
2996 populate_pattern_use (cpi, use, sinfo->to_states + i);
2997 else
2999 /* The transition corresponds to a successful return from the
3000 pattern routine. */
3001 use->push_back (new transition (cpi->next_result, trans->to, false));
3002 cpi->next_result += 1;
3004 i += 1;
3008 /* We have decided to replace SINFO's state with a call to a pattern
3009 routine. Make the change, creating a definition of the pattern routine
3010 if it doesn't have one already. */
3012 static void
3013 use_pattern (merge_state_info *sinfo)
3015 merge_state_result *res = sinfo->res;
3016 merge_pattern_info *pat = res->pattern;
3017 state *s = sinfo->s;
3019 /* The pattern may have acquired new parameters after it was matched
3020 against SINFO. Update the parameters that SINFO passes accordingly. */
3021 update_parameters (res->params, pat->params);
3023 create_pattern_info cpi;
3024 decision *d = init_pattern_use (&cpi, sinfo, res->params);
3025 populate_pattern_use (&cpi, d, sinfo);
3026 s->release ();
3027 s->push_back (d);
3030 /* Look through the state trees in STATES for common patterns and
3031 split them into subroutines. */
3033 static void
3034 split_out_patterns (vec <merge_state_info> &states)
3036 unsigned int first_transition = states.length ();
3037 hash_table <test_pattern_hasher> hashtab (128);
3038 /* Stage 1: Create an order in which parent states come before their child
3039 states and in which sibling states are at consecutive locations.
3040 Having consecutive sibling states allows merge_state_info to have
3041 a single to_states pointer. */
3042 for (unsigned int i = 0; i < states.length (); ++i)
3043 for (decision *d = states[i].s->first; d; d = d->next)
3044 for (transition *trans = d->first; trans; trans = trans->next)
3046 states.safe_push (trans->to);
3047 states[i].num_transitions += 1;
3049 /* Stage 2: Now that the addresses are stable, set up the to_states
3050 pointers. Look for states that might be merged and enter them
3051 into the hash table. */
3052 for (unsigned int i = 0; i < states.length (); ++i)
3054 merge_state_info *sinfo = &states[i];
3055 if (sinfo->num_transitions)
3057 sinfo->to_states = &states[first_transition];
3058 first_transition += sinfo->num_transitions;
3060 /* For simplicity, we only try to merge states that have a single
3061 decision. This is in any case the best we can do for peephole2,
3062 since whether a peephole2 ACCEPT succeeds or not depends on the
3063 specific peephole2 pattern (which is unique to each ACCEPT
3064 and so couldn't be shared between states). */
3065 if (decision *d = sinfo->s->singleton ())
3066 /* ACCEPT states are unique, so don't even try to merge them. */
3067 if (d->test.kind != rtx_test::ACCEPT
3068 && (pattern_have_num_clobbers_p
3069 || d->test.kind != rtx_test::HAVE_NUM_CLOBBERS)
3070 && (pattern_c_test_p
3071 || d->test.kind != rtx_test::C_TEST))
3073 merge_state_info **slot = hashtab.find_slot (sinfo, INSERT);
3074 sinfo->prev_same_test = *slot;
3075 *slot = sinfo;
3078 /* Stage 3: Walk backwards through the list of states and try to merge
3079 them. This is a greedy, bottom-up match; parent nodes can only start
3080 a new leaf pattern if they fail to match when combined with all child
3081 nodes that have matching patterns.
3083 For each state we keep a list of potential matches, with each
3084 potential match being larger (and deeper) than the next match in
3085 the list. The final element in the list is a leaf pattern that
3086 matches just a single state.
3088 Each candidate pattern created in this loop is unique -- it won't
3089 have been seen by an earlier iteration. We try to match each pattern
3090 with every state that appears earlier in STATES.
3092 Because the patterns created in the loop are unique, any state
3093 that already has a match must have a final potential match that
3094 is different from any new leaf pattern. Therefore, when matching
3095 leaf patterns, we need only consider states whose list of matches
3096 is empty.
3098 The non-leaf patterns that we try are as deep as possible
3099 and are an extension of the state's previous best candidate match (PB).
3100 We need only consider states whose current potential match is also PB;
3101 any states that don't match as much as PB cannnot match the new pattern,
3102 while any states that already match more than PB must be different from
3103 the new pattern. */
3104 for (unsigned int i2 = states.length (); i2-- > 0; )
3106 merge_state_info *sinfo2 = &states[i2];
3108 /* Enforce the bottom-upness of the match: remove matches with later
3109 states if SINFO2's child states ended up finding a better match. */
3110 prune_invalid_results (sinfo2);
3112 /* Do nothing if the state doesn't match a later one and if there are
3113 no earlier states it could match. */
3114 if (!sinfo2->res && !sinfo2->prev_same_test)
3115 continue;
3117 merge_state_result *res2 = sinfo2->res;
3118 decision *d2 = sinfo2->s->singleton ();
3119 position *root2 = (d2->test.pos_operand < 0 ? d2->test.pos : 0);
3120 unsigned int num_transitions = sinfo2->num_transitions;
3122 /* If RES2 is null then SINFO2's test in isolation has not been seen
3123 before. First try matching that on its own. */
3124 if (!res2)
3126 merge_pattern_info *new_pat
3127 = new merge_pattern_info (num_transitions);
3128 merge_state_result *new_res2
3129 = new merge_state_result (new_pat, root2, res2);
3130 sinfo2->res = new_res2;
3132 new_pat->num_statements = !d2->test.single_outcome_p ();
3133 new_pat->num_results = num_transitions;
3134 bool matched_p = false;
3135 /* Look for states that don't currently match anything but
3136 can be made to match SINFO2 on its own. */
3137 for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3138 sinfo1 = sinfo1->prev_same_test)
3139 if (!sinfo1->res && merge_patterns (sinfo1, sinfo2))
3140 matched_p = true;
3141 if (!matched_p)
3143 /* No other states match. */
3144 sinfo2->res = res2;
3145 delete new_pat;
3146 delete new_res2;
3147 continue;
3149 else
3150 res2 = new_res2;
3153 /* Keep the existing pattern if it's as good as anything we'd
3154 create for SINFO2. */
3155 if (complete_result_p (res2->pattern, sinfo2))
3157 res2->pattern->num_users += 1;
3158 continue;
3161 /* Create a new pattern for SINFO2. */
3162 merge_pattern_info *new_pat = new merge_pattern_info (num_transitions);
3163 merge_state_result *new_res2
3164 = new merge_state_result (new_pat, root2, res2);
3165 sinfo2->res = new_res2;
3167 /* Fill in details about the pattern. */
3168 new_pat->num_statements = !d2->test.single_outcome_p ();
3169 new_pat->num_results = 0;
3170 for (unsigned int j = 0; j < num_transitions; ++j)
3171 if (merge_state_result *to_res = sinfo2->to_states[j].res)
3173 /* Count the target state as part of this pattern.
3174 First update the root position so that it can reach
3175 the target state's root. */
3176 if (to_res->root)
3178 if (new_res2->root)
3179 new_res2->root = common_position (new_res2->root,
3180 to_res->root);
3181 else
3182 new_res2->root = to_res->root;
3184 merge_pattern_info *to_pat = to_res->pattern;
3185 merge_pattern_transition *ptrans
3186 = new merge_pattern_transition (to_pat);
3188 /* TO_PAT may have acquired more parameters when matching
3189 states earlier in STATES than TO_RES's, but the list is
3190 now final. Make sure that TO_RES is up to date. */
3191 update_parameters (to_res->params, to_pat->params);
3193 /* Start out by assuming that every user of NEW_PAT will
3194 want to pass the same (constant) parameters as TO_RES. */
3195 update_parameters (ptrans->params, to_res->params);
3197 new_pat->transitions[j] = ptrans;
3198 new_pat->num_statements += to_pat->num_statements;
3199 new_pat->num_results += to_pat->num_results;
3201 else
3202 /* The target state doesn't match anything and so is not part
3203 of the pattern. */
3204 new_pat->num_results += 1;
3206 /* See if any earlier states that match RES2's pattern also match
3207 NEW_PAT. */
3208 bool matched_p = false;
3209 for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3210 sinfo1 = sinfo1->prev_same_test)
3212 prune_invalid_results (sinfo1);
3213 if (sinfo1->res
3214 && sinfo1->res->pattern == res2->pattern
3215 && merge_patterns (sinfo1, sinfo2))
3216 matched_p = true;
3218 if (!matched_p)
3220 /* Nothing else matches NEW_PAT, so go back to the previous
3221 pattern (possibly just a single-state one). */
3222 sinfo2->res = res2;
3223 delete new_pat;
3224 delete new_res2;
3226 /* Assume that SINFO2 will use RES. At this point we don't know
3227 whether earlier states that match the same pattern will use
3228 that match or a different one. */
3229 sinfo2->res->pattern->num_users += 1;
3231 /* Step 4: Finalize the choice of pattern for each state, ignoring
3232 patterns that were only used once. Update each pattern's size
3233 so that it doesn't include subpatterns that are going to be split
3234 out into subroutines. */
3235 for (unsigned int i = 0; i < states.length (); ++i)
3237 merge_state_info *sinfo = &states[i];
3238 merge_state_result *res = sinfo->res;
3239 /* Wind past patterns that are only used by SINFO. */
3240 while (res && res->pattern->num_users == 1)
3242 res = res->prev;
3243 sinfo->res = res;
3244 if (res)
3245 res->pattern->num_users += 1;
3247 if (!res)
3248 continue;
3250 /* We have a shared pattern and are now committed to the match. */
3251 merge_pattern_info *pat = res->pattern;
3252 gcc_assert (valid_result_p (pat, sinfo));
3254 if (!pat->complete_p)
3256 /* Look for subpatterns that are going to be split out and remove
3257 them from the number of statements. */
3258 for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
3259 if (merge_pattern_transition *ptrans = pat->transitions[j])
3261 merge_pattern_info *to_pat = ptrans->to;
3262 if (!same_pattern_p (pat, to_pat))
3263 pat->num_statements -= to_pat->num_statements;
3265 pat->complete_p = true;
3268 /* Step 5: Split out the patterns. */
3269 for (unsigned int i = 0; i < states.length (); ++i)
3271 merge_state_info *sinfo = &states[i];
3272 merge_state_result *res = sinfo->res;
3273 if (!sinfo->merged_p && res && useful_pattern_p (res->pattern))
3274 use_pattern (sinfo);
3276 fprintf (stderr, "Shared %d out of %d states by creating %d new states,"
3277 " saving %d\n",
3278 pattern_use_states, states.length (), pattern_def_states,
3279 pattern_use_states - pattern_def_states);
3282 /* Information about a state tree that we're considering splitting into a
3283 subroutine. */
3284 struct state_size
3286 /* The number of pseudo-statements in the state tree. */
3287 unsigned int num_statements;
3289 /* The approximate number of nested "if" and "switch" statements that
3290 would be required if control could fall through to a later state. */
3291 unsigned int depth;
3294 /* Pairs a transition with information about its target state. */
3295 typedef std::pair <transition *, state_size> subroutine_candidate;
3297 /* Sort two subroutine_candidates so that the one with the largest
3298 number of statements comes last. */
3300 static int
3301 subroutine_candidate_cmp (const void *a, const void *b)
3303 return int (((const subroutine_candidate *) a)->second.num_statements
3304 - ((const subroutine_candidate *) b)->second.num_statements);
3307 /* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new
3308 state that performs a subroutine call to S. */
3310 static state *
3311 create_subroutine (routine_type type, state *s, vec <state *> &procs)
3313 procs.safe_push (s);
3314 acceptance_type acceptance;
3315 acceptance.type = type;
3316 acceptance.partial_p = true;
3317 acceptance.u.subroutine_id = procs.length ();
3318 state *news = new state;
3319 add_decision (news, rtx_test::accept (acceptance), true, false);
3320 return news;
3323 /* Walk state tree S, of type TYPE, and look for subtrees that would be
3324 better split into subroutines. Accumulate all such subroutines in PROCS.
3325 Return the size of the new state tree (excluding subroutines). */
3327 static state_size
3328 find_subroutines (routine_type type, state *s, vec <state *> &procs)
3330 auto_vec <subroutine_candidate, 16> candidates;
3331 state_size size;
3332 size.num_statements = 0;
3333 size.depth = 0;
3334 for (decision *d = s->first; d; d = d->next)
3336 if (!d->test.single_outcome_p ())
3337 size.num_statements += 1;
3338 for (transition *trans = d->first; trans; trans = trans->next)
3340 /* Keep chains of simple decisions together if we know that no
3341 change of position is required. We'll output this chain as a
3342 single "if" statement, so it counts as a single nesting level. */
3343 if (d->test.pos && d->if_statement_p ())
3344 for (;;)
3346 decision *newd = trans->to->singleton ();
3347 if (!newd
3348 || (newd->test.pos
3349 && newd->test.pos_operand < 0
3350 && newd->test.pos != d->test.pos)
3351 || !newd->if_statement_p ())
3352 break;
3353 if (!newd->test.single_outcome_p ())
3354 size.num_statements += 1;
3355 trans = newd->singleton ();
3356 if (newd->test.kind == rtx_test::SET_OP
3357 || newd->test.kind == rtx_test::ACCEPT)
3358 break;
3360 /* The target of TRANS is a subroutine candidate. First recurse
3361 on it to see how big it is after subroutines have been
3362 split out. */
3363 state_size to_size = find_subroutines (type, trans->to, procs);
3364 if (d->next && to_size.depth > MAX_DEPTH)
3365 /* Keeping the target state in the same routine would lead
3366 to an excessive nesting of "if" and "switch" statements.
3367 Split it out into a subroutine so that it can use
3368 inverted tests that return early on failure. */
3369 trans->to = create_subroutine (type, trans->to, procs);
3370 else
3372 size.num_statements += to_size.num_statements;
3373 if (to_size.num_statements < MIN_NUM_STATEMENTS)
3374 /* The target state is too small to be worth splitting.
3375 Keep it in the same routine as S. */
3376 size.depth = MAX (size.depth, to_size.depth);
3377 else
3378 /* Assume for now that we'll keep the target state in the
3379 same routine as S, but record it as a subroutine candidate
3380 if S grows too big. */
3381 candidates.safe_push (subroutine_candidate (trans, to_size));
3385 if (size.num_statements > MAX_NUM_STATEMENTS)
3387 /* S is too big. Sort the subroutine candidates so that bigger ones
3388 are nearer the end. */
3389 candidates.qsort (subroutine_candidate_cmp);
3390 while (!candidates.is_empty ()
3391 && size.num_statements > MAX_NUM_STATEMENTS)
3393 /* Peel off a candidate and force it into a subroutine. */
3394 subroutine_candidate cand = candidates.pop ();
3395 size.num_statements -= cand.second.num_statements;
3396 cand.first->to = create_subroutine (type, cand.first->to, procs);
3399 /* Update the depth for subroutine candidates that we decided not to
3400 split out. */
3401 for (unsigned int i = 0; i < candidates.length (); ++i)
3402 size.depth = MAX (size.depth, candidates[i].second.depth);
3403 size.depth += 1;
3404 return size;
3407 /* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */
3409 static bool
3410 safe_predicate_mode (const struct pred_data *pred, machine_mode mode)
3412 /* Scalar integer constants have VOIDmode. */
3413 if (GET_MODE_CLASS (mode) == MODE_INT
3414 && (pred->codes[CONST_INT]
3415 || pred->codes[CONST_DOUBLE]
3416 || pred->codes[CONST_WIDE_INT]
3417 || pred->codes[LABEL_REF]))
3418 return false;
3420 return !pred->special && mode != VOIDmode;
3423 /* Fill CODES with the set of codes that could be matched by PRED. */
3425 static void
3426 get_predicate_codes (const struct pred_data *pred, int_set *codes)
3428 for (int i = 0; i < NUM_TRUE_RTX_CODE; ++i)
3429 if (!pred || pred->codes[i])
3430 codes->safe_push (i);
3433 /* Return true if the first path through D1 tests the same thing as D2. */
3435 static bool
3436 has_same_test_p (decision *d1, decision *d2)
3440 if (d1->test == d2->test)
3441 return true;
3442 d1 = d1->first->to->first;
3444 while (d1);
3445 return false;
3448 /* Return true if D1 and D2 cannot match the same rtx. All states reachable
3449 from D2 have single decisions and all those decisions have single
3450 transitions. */
3452 static bool
3453 mutually_exclusive_p (decision *d1, decision *d2)
3455 /* If one path through D1 fails to test the same thing as D2, assume
3456 that D2's test could be true for D1 and look for a later, more useful,
3457 test. This isn't as expensive as it looks in practice. */
3458 while (!has_same_test_p (d1, d2))
3460 d2 = d2->singleton ()->to->singleton ();
3461 if (!d2)
3462 return false;
3464 if (d1->test == d2->test)
3466 /* Look for any transitions from D1 that have the same labels as
3467 the transition from D2. */
3468 transition *trans2 = d2->singleton ();
3469 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3471 int_set::iterator i1 = trans1->labels.begin ();
3472 int_set::iterator end1 = trans1->labels.end ();
3473 int_set::iterator i2 = trans2->labels.begin ();
3474 int_set::iterator end2 = trans2->labels.end ();
3475 while (i1 != end1 && i2 != end2)
3476 if (*i1 < *i2)
3477 ++i1;
3478 else if (*i2 < *i1)
3479 ++i2;
3480 else
3482 /* TRANS1 has some labels in common with TRANS2. Assume
3483 that D1 and D2 could match the same rtx if the target
3484 of TRANS1 could match the same rtx as D2. */
3485 for (decision *subd1 = trans1->to->first;
3486 subd1; subd1 = subd1->next)
3487 if (!mutually_exclusive_p (subd1, d2))
3488 return false;
3489 break;
3492 return true;
3494 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3495 for (decision *subd1 = trans1->to->first; subd1; subd1 = subd1->next)
3496 if (!mutually_exclusive_p (subd1, d2))
3497 return false;
3498 return true;
3501 /* Try to merge S2's decision into D1, given that they have the same test.
3502 Fail only if EXCLUDE is nonnull and the new transition would have the
3503 same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2
3504 and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
3505 if the merge is complete. */
3507 static bool
3508 merge_into_decision (decision *d1, state *s2, const int_set *exclude,
3509 state **next_s1, state **next_s2,
3510 const int_set **next_exclude)
3512 decision *d2 = s2->singleton ();
3513 transition *trans2 = d2->singleton ();
3515 /* Get a list of the transitions that intersect TRANS2. */
3516 auto_vec <transition *, 32> intersecting;
3517 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3519 int_set::iterator i1 = trans1->labels.begin ();
3520 int_set::iterator end1 = trans1->labels.end ();
3521 int_set::iterator i2 = trans2->labels.begin ();
3522 int_set::iterator end2 = trans2->labels.end ();
3523 bool trans1_is_subset = true;
3524 bool trans2_is_subset = true;
3525 bool intersect_p = false;
3526 while (i1 != end1 && i2 != end2)
3527 if (*i1 < *i2)
3529 trans1_is_subset = false;
3530 ++i1;
3532 else if (*i2 < *i1)
3534 trans2_is_subset = false;
3535 ++i2;
3537 else
3539 intersect_p = true;
3540 ++i1;
3541 ++i2;
3543 if (i1 != end1)
3544 trans1_is_subset = false;
3545 if (i2 != end2)
3546 trans2_is_subset = false;
3547 if (trans1_is_subset && trans2_is_subset)
3549 /* There's already a transition that matches exactly.
3550 Merge the target states. */
3551 trans1->optional &= trans2->optional;
3552 *next_s1 = trans1->to;
3553 *next_s2 = trans2->to;
3554 *next_exclude = 0;
3555 return true;
3557 if (trans2_is_subset)
3559 /* TRANS1 has all the labels that TRANS2 needs. Merge S2 into
3560 the target of TRANS1, but (to avoid infinite recursion)
3561 make sure that we don't end up creating another transition
3562 like TRANS1. */
3563 *next_s1 = trans1->to;
3564 *next_s2 = s2;
3565 *next_exclude = &trans1->labels;
3566 return true;
3568 if (intersect_p)
3569 intersecting.safe_push (trans1);
3572 if (intersecting.is_empty ())
3574 /* No existing labels intersect the new ones. We can just add
3575 TRANS2 itself. */
3576 d1->push_back (d2->release ());
3577 *next_s1 = 0;
3578 *next_s2 = 0;
3579 *next_exclude = 0;
3580 return true;
3583 /* Take the union of the labels in INTERSECTING and TRANS2. Store the
3584 result in COMBINED and use NEXT as a temporary. */
3585 int_set tmp1 = trans2->labels, tmp2;
3586 int_set *combined = &tmp1, *next = &tmp2;
3587 for (unsigned int i = 0; i < intersecting.length (); ++i)
3589 transition *trans1 = intersecting[i];
3590 next->truncate (0);
3591 next->safe_grow (trans1->labels.length () + combined->length ());
3592 int_set::iterator end
3593 = std::set_union (trans1->labels.begin (), trans1->labels.end (),
3594 combined->begin (), combined->end (),
3595 next->begin ());
3596 next->truncate (end - next->begin ());
3597 std::swap (next, combined);
3600 /* Stop now if we've been told not to create a transition with these
3601 labels. */
3602 if (exclude && *combined == *exclude)
3603 return false;
3605 /* Get the transition that should carry the new labels. */
3606 transition *new_trans = intersecting[0];
3607 if (intersecting.length () == 1)
3609 /* We're merging with one existing transition whose labels are a
3610 subset of those required. If both transitions are optional,
3611 we can just expand the set of labels so that it's suitable
3612 for both transitions. It isn't worth preserving the original
3613 transitions since we know that they can't be merged; we would
3614 need to backtrack to S2 if TRANS1->to fails. In contrast,
3615 we might be able to merge the targets of the transitions
3616 without any backtracking.
3618 If instead the existing transition is not optional, ensure that
3619 all target decisions are suitably protected. Some decisions
3620 might already have a more specific requirement than NEW_TRANS,
3621 in which case there's no point testing NEW_TRANS as well. E.g. this
3622 would have happened if a test for an (eq ...) rtx had been
3623 added to a decision that tested whether the code is suitable
3624 for comparison_operator. The original comparison_operator
3625 transition would have been non-optional and the (eq ...) test
3626 would be performed by a second decision in the target of that
3627 transition.
3629 The remaining case -- keeping the original optional transition
3630 when adding a non-optional TRANS2 -- is a wash. Preserving
3631 the optional transition only helps if we later merge another
3632 state S3 that is mutually exclusive with S2 and whose labels
3633 belong to *COMBINED - TRANS1->labels. We can then test the
3634 original NEW_TRANS and S3 in the same decision. We keep the
3635 optional transition around for that case, but it occurs very
3636 rarely. */
3637 gcc_assert (new_trans->labels != *combined);
3638 if (!new_trans->optional || !trans2->optional)
3640 decision *start = 0;
3641 for (decision *end = new_trans->to->first; end; end = end->next)
3643 if (!start && end->test != d1->test)
3644 /* END belongs to a range of decisions that need to be
3645 protected by NEW_TRANS. */
3646 start = end;
3647 if (start && (!end->next || end->next->test == d1->test))
3649 /* Protect [START, END] with NEW_TRANS. The decisions
3650 move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */
3651 state *new_s = new state;
3652 decision *new_d = new decision (d1->test);
3653 new_d->push_back (new transition (new_trans->labels, new_s,
3654 new_trans->optional));
3655 state::range r (start, end);
3656 new_trans->to->replace (r, new_d);
3657 new_s->push_back (r);
3659 /* Continue with an empty range. */
3660 start = 0;
3662 /* Continue from the decision after NEW_D. */
3663 end = new_d;
3667 new_trans->optional = true;
3668 new_trans->labels = *combined;
3670 else
3672 /* We're merging more than one existing transition together.
3673 Those transitions are successfully dividing the matching space
3674 and so we want to preserve them, even if they're optional.
3676 Create a new transition with the union set of labels and make
3677 it go to a state that has the original transitions. */
3678 decision *new_d = new decision (d1->test);
3679 for (unsigned int i = 0; i < intersecting.length (); ++i)
3680 new_d->push_back (d1->remove (intersecting[i]));
3682 state *new_s = new state;
3683 new_s->push_back (new_d);
3685 new_trans = new transition (*combined, new_s, true);
3686 d1->push_back (new_trans);
3689 /* We now have an optional transition with labels *COMBINED. Decide
3690 whether we can use it as TRANS2 or whether we need to merge S2
3691 into the target of NEW_TRANS. */
3692 gcc_assert (new_trans->optional);
3693 if (new_trans->labels == trans2->labels)
3695 /* NEW_TRANS matches TRANS2. Just merge the target states. */
3696 new_trans->optional = trans2->optional;
3697 *next_s1 = new_trans->to;
3698 *next_s2 = trans2->to;
3699 *next_exclude = 0;
3701 else
3703 /* Try to merge TRANS2 into the target of the overlapping transition,
3704 but (to prevent infinite recursion or excessive redundancy) without
3705 creating another transition of the same type. */
3706 *next_s1 = new_trans->to;
3707 *next_s2 = s2;
3708 *next_exclude = &new_trans->labels;
3710 return true;
3713 /* Make progress in merging S2 into S1, given that each state in S2
3714 has a single decision. If EXCLUDE is nonnull, avoid creating a new
3715 transition with the same test as S2's decision and with the labels
3716 in *EXCLUDE.
3718 Return true if there is still work to do. When returning true,
3719 set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
3720 S1, S2 and EXCLUDE should have next time round.
3722 If S1 and S2 both match a particular rtx, give priority to S1. */
3724 static bool
3725 merge_into_state_1 (state *s1, state *s2, const int_set *exclude,
3726 state **next_s1, state **next_s2,
3727 const int_set **next_exclude)
3729 decision *d2 = s2->singleton ();
3730 if (decision *d1 = s1->last)
3732 if (d1->test.terminal_p ())
3733 /* D1 is an unconditional return, so S2 can never match. This can
3734 sometimes be a bug in the .md description, but might also happen
3735 if genconditions forces some conditions to true for certain
3736 configurations. */
3737 return false;
3739 /* Go backwards through the decisions in S1, stopping once we find one
3740 that could match the same thing as S2. */
3741 while (d1->prev && mutually_exclusive_p (d1, d2))
3742 d1 = d1->prev;
3744 /* Search forwards from that point, merging D2 into the first
3745 decision we can. */
3746 for (; d1; d1 = d1->next)
3748 /* If S2 performs some optional tests before testing the same thing
3749 as D1, those tests do not help to distinguish D1 and S2, so it's
3750 better to drop them. Search through such optional decisions
3751 until we find something that tests the same thing as D1. */
3752 state *sub_s2 = s2;
3753 for (;;)
3755 decision *sub_d2 = sub_s2->singleton ();
3756 if (d1->test == sub_d2->test)
3758 /* Only apply EXCLUDE if we're testing the same thing
3759 as D2. */
3760 const int_set *sub_exclude = (d2 == sub_d2 ? exclude : 0);
3762 /* Try to merge SUB_S2 into D1. This can only fail if
3763 it would involve creating a new transition with
3764 labels SUB_EXCLUDE. */
3765 if (merge_into_decision (d1, sub_s2, sub_exclude,
3766 next_s1, next_s2, next_exclude))
3767 return *next_s2 != 0;
3769 /* Can't merge with D1; try a later decision. */
3770 break;
3772 transition *sub_trans2 = sub_d2->singleton ();
3773 if (!sub_trans2->optional)
3774 /* Can't merge with D1; try a later decision. */
3775 break;
3776 sub_s2 = sub_trans2->to;
3781 /* We can't merge D2 with any existing decision. Just add it to the end. */
3782 s1->push_back (s2->release ());
3783 return false;
3786 /* Merge S2 into S1. If they both match a particular rtx, give
3787 priority to S1. Each state in S2 has a single decision. */
3789 static void
3790 merge_into_state (state *s1, state *s2)
3792 const int_set *exclude = 0;
3793 while (s2 && merge_into_state_1 (s1, s2, exclude, &s1, &s2, &exclude))
3794 continue;
3797 /* Pairs a pattern that needs to be matched with the rtx position at
3798 which the pattern should occur. */
3799 struct pattern_pos {
3800 pattern_pos () {}
3801 pattern_pos (rtx, position *);
3803 rtx pattern;
3804 position *pos;
3807 pattern_pos::pattern_pos (rtx pattern_in, position *pos_in)
3808 : pattern (pattern_in), pos (pos_in)
3811 /* Compare entries according to their depth-first order. There shouldn't
3812 be two entries at the same position. */
3814 bool
3815 operator < (const pattern_pos &e1, const pattern_pos &e2)
3817 int diff = compare_positions (e1.pos, e2.pos);
3818 gcc_assert (diff != 0 || e1.pattern == e2.pattern);
3819 return diff < 0;
3822 /* Add new decisions to S that check whether the rtx at position POS
3823 matches PATTERN. Return the state that is reached in that case.
3824 TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */
3826 static state *
3827 match_pattern_2 (state *s, md_rtx_info *info, position *pos, rtx pattern)
3829 auto_vec <pattern_pos, 32> worklist;
3830 auto_vec <pattern_pos, 32> pred_and_mode_tests;
3831 auto_vec <pattern_pos, 32> dup_tests;
3833 worklist.safe_push (pattern_pos (pattern, pos));
3834 while (!worklist.is_empty ())
3836 pattern_pos next = worklist.pop ();
3837 pattern = next.pattern;
3838 pos = next.pos;
3839 unsigned int reverse_s = worklist.length ();
3841 enum rtx_code code = GET_CODE (pattern);
3842 switch (code)
3844 case MATCH_OP_DUP:
3845 case MATCH_DUP:
3846 case MATCH_PAR_DUP:
3847 /* Add a test that the rtx matches the earlier one, but only
3848 after the structure and predicates have been checked. */
3849 dup_tests.safe_push (pattern_pos (pattern, pos));
3851 /* Use the same code check as the original operand. */
3852 pattern = find_operand (info->def, XINT (pattern, 0), NULL_RTX);
3853 /* Fall through. */
3855 case MATCH_PARALLEL:
3856 case MATCH_OPERAND:
3857 case MATCH_SCRATCH:
3858 case MATCH_OPERATOR:
3860 const char *pred_name = predicate_name (pattern);
3861 const struct pred_data *pred = 0;
3862 if (pred_name[0] != 0)
3864 pred = lookup_predicate (pred_name);
3865 /* Only report errors once per rtx. */
3866 if (code == GET_CODE (pattern))
3868 if (!pred)
3869 error_at (info->loc, "unknown predicate '%s' used in %s",
3870 pred_name, GET_RTX_NAME (code));
3871 else if (code == MATCH_PARALLEL
3872 && pred->singleton != PARALLEL)
3873 error_at (info->loc, "predicate '%s' used in"
3874 " match_parallel does not allow only PARALLEL",
3875 pred->name);
3879 if (code == MATCH_PARALLEL || code == MATCH_PAR_DUP)
3881 /* Check that we have a parallel with enough elements. */
3882 s = add_decision (s, rtx_test::code (pos), PARALLEL, false);
3883 int min_len = XVECLEN (pattern, 2);
3884 s = add_decision (s, rtx_test::veclen_ge (pos, min_len),
3885 true, false);
3887 else
3889 /* Check that the rtx has one of codes accepted by the
3890 predicate. This is necessary when matching suboperands
3891 of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
3892 call XEXP (X, N) without checking that X has at least
3893 N+1 operands. */
3894 int_set codes;
3895 get_predicate_codes (pred, &codes);
3896 bool need_codes = (pred
3897 && (code == MATCH_OPERATOR
3898 || code == MATCH_OP_DUP));
3899 s = add_decision (s, rtx_test::code (pos), codes, !need_codes);
3902 /* Postpone the predicate check until we've checked the rest
3903 of the rtx structure. */
3904 if (code == GET_CODE (pattern))
3905 pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
3907 /* If we need to match suboperands, add them to the worklist. */
3908 if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
3910 position **subpos_ptr;
3911 enum position_type pos_type;
3912 int i;
3913 if (code == MATCH_OPERATOR || code == MATCH_OP_DUP)
3915 pos_type = POS_XEXP;
3916 subpos_ptr = &pos->xexps;
3917 i = (code == MATCH_OPERATOR ? 2 : 1);
3919 else
3921 pos_type = POS_XVECEXP0;
3922 subpos_ptr = &pos->xvecexp0s;
3923 i = 2;
3925 for (int j = 0; j < XVECLEN (pattern, i); ++j)
3927 position *subpos = next_position (subpos_ptr, pos,
3928 pos_type, j);
3929 worklist.safe_push (pattern_pos (XVECEXP (pattern, i, j),
3930 subpos));
3931 subpos_ptr = &subpos->next;
3934 break;
3937 default:
3939 /* Check that the rtx has the right code. */
3940 s = add_decision (s, rtx_test::code (pos), code, false);
3942 /* Queue a test for the mode if one is specified. */
3943 if (GET_MODE (pattern) != VOIDmode)
3944 pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
3946 /* Push subrtxes onto the worklist. Match nonrtx operands now. */
3947 const char *fmt = GET_RTX_FORMAT (code);
3948 position **subpos_ptr = &pos->xexps;
3949 for (size_t i = 0; fmt[i]; ++i)
3951 position *subpos = next_position (subpos_ptr, pos,
3952 POS_XEXP, i);
3953 switch (fmt[i])
3955 case 'e': case 'u':
3956 worklist.safe_push (pattern_pos (XEXP (pattern, i),
3957 subpos));
3958 break;
3960 case 'E':
3962 /* Make sure the vector has the right number of
3963 elements. */
3964 int length = XVECLEN (pattern, i);
3965 s = add_decision (s, rtx_test::veclen (pos),
3966 length, false);
3968 position **subpos2_ptr = &pos->xvecexp0s;
3969 for (int j = 0; j < length; j++)
3971 position *subpos2 = next_position (subpos2_ptr, pos,
3972 POS_XVECEXP0, j);
3973 rtx x = XVECEXP (pattern, i, j);
3974 worklist.safe_push (pattern_pos (x, subpos2));
3975 subpos2_ptr = &subpos2->next;
3977 break;
3980 case 'i':
3981 /* Make sure that XINT (X, I) has the right value. */
3982 s = add_decision (s, rtx_test::int_field (pos, i),
3983 XINT (pattern, i), false);
3984 break;
3986 case 'r':
3987 /* Make sure that REGNO (X) has the right value. */
3988 gcc_assert (i == 0);
3989 s = add_decision (s, rtx_test::regno_field (pos),
3990 REGNO (pattern), false);
3991 break;
3993 case 'w':
3994 /* Make sure that XWINT (X, I) has the right value. */
3995 s = add_decision (s, rtx_test::wide_int_field (pos, i),
3996 XWINT (pattern, 0), false);
3997 break;
3999 case '0':
4000 break;
4002 default:
4003 gcc_unreachable ();
4005 subpos_ptr = &subpos->next;
4008 break;
4010 /* Operands are pushed onto the worklist so that later indices are
4011 nearer the top. That's what we want for SETs, since a SET_SRC
4012 is a better discriminator than a SET_DEST. In other cases it's
4013 usually better to match earlier indices first. This is especially
4014 true of PARALLELs, where the first element tends to be the most
4015 individual. It's also true for commutative operators, where the
4016 canonicalization rules say that the more complex operand should
4017 come first. */
4018 if (code != SET && worklist.length () > reverse_s)
4019 std::reverse (&worklist[0] + reverse_s,
4020 &worklist[0] + worklist.length ());
4023 /* Sort the predicate and mode tests so that they're in depth-first order.
4024 The main goal of this is to put SET_SRC match_operands after SET_DEST
4025 match_operands and after mode checks for the enclosing SET_SRC operators
4026 (such as the mode of a PLUS in an addition instruction). The latter
4027 two types of test can determine the mode exactly, whereas a SET_SRC
4028 match_operand often has to cope with the possibility of the operand
4029 being a modeless constant integer. E.g. something that matches
4030 register_operand (x, SImode) never matches register_operand (x, DImode),
4031 but a const_int that matches immediate_operand (x, SImode) also matches
4032 immediate_operand (x, DImode). The register_operand cases can therefore
4033 be distinguished by a switch on the mode, but the immediate_operand
4034 cases can't. */
4035 if (pred_and_mode_tests.length () > 1)
4036 std::sort (&pred_and_mode_tests[0],
4037 &pred_and_mode_tests[0] + pred_and_mode_tests.length ());
4039 /* Add the mode and predicate tests. */
4040 pattern_pos *e;
4041 unsigned int i;
4042 FOR_EACH_VEC_ELT (pred_and_mode_tests, i, e)
4044 switch (GET_CODE (e->pattern))
4046 case MATCH_PARALLEL:
4047 case MATCH_OPERAND:
4048 case MATCH_SCRATCH:
4049 case MATCH_OPERATOR:
4051 int opno = XINT (e->pattern, 0);
4052 num_operands = MAX (num_operands, opno + 1);
4053 const char *pred_name = predicate_name (e->pattern);
4054 if (pred_name[0])
4056 const struct pred_data *pred = lookup_predicate (pred_name);
4057 /* Check the mode first, to distinguish things like SImode
4058 and DImode register_operands, as described above. */
4059 machine_mode mode = GET_MODE (e->pattern);
4060 if (pred && safe_predicate_mode (pred, mode))
4061 s = add_decision (s, rtx_test::mode (e->pos), mode, true);
4063 /* Assign to operands[] first, so that the rtx usually doesn't
4064 need to be live across the call to the predicate.
4066 This shouldn't cause a problem with dirtying the page,
4067 since we fully expect to assign to operands[] at some point,
4068 and since the caller usually writes to other parts of
4069 recog_data anyway. */
4070 s = add_decision (s, rtx_test::set_op (e->pos, opno),
4071 true, false);
4072 s = add_decision (s, rtx_test::predicate (e->pos, pred, mode),
4073 true, false);
4075 else
4076 /* Historically we've ignored the mode when there's no
4077 predicate. Just set up operands[] unconditionally. */
4078 s = add_decision (s, rtx_test::set_op (e->pos, opno),
4079 true, false);
4080 break;
4083 default:
4084 s = add_decision (s, rtx_test::mode (e->pos),
4085 GET_MODE (e->pattern), false);
4086 break;
4090 /* Finally add rtx_equal_p checks for duplicated operands. */
4091 FOR_EACH_VEC_ELT (dup_tests, i, e)
4092 s = add_decision (s, rtx_test::duplicate (e->pos, XINT (e->pattern, 0)),
4093 true, false);
4094 return s;
4097 /* Add new decisions to S that make it return ACCEPTANCE if:
4099 (1) the rtx doesn't match anything already matched by S
4100 (2) the rtx matches TOP_PATTERN and
4101 (3) the C test required by INFO->def is true
4103 For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns
4104 to match, otherwise it is a single instruction pattern. */
4106 static void
4107 match_pattern_1 (state *s, md_rtx_info *info, rtx pattern,
4108 acceptance_type acceptance)
4110 if (acceptance.type == PEEPHOLE2)
4112 /* Match each individual instruction. */
4113 position **subpos_ptr = &peep2_insn_pos_list;
4114 int count = 0;
4115 for (int i = 0; i < XVECLEN (pattern, 0); ++i)
4117 rtx x = XVECEXP (pattern, 0, i);
4118 position *subpos = next_position (subpos_ptr, &root_pos,
4119 POS_PEEP2_INSN, count);
4120 if (count > 0)
4121 s = add_decision (s, rtx_test::peep2_count (count + 1),
4122 true, false);
4123 s = match_pattern_2 (s, info, subpos, x);
4124 subpos_ptr = &subpos->next;
4125 count += 1;
4127 acceptance.u.full.u.match_len = count - 1;
4129 else
4131 /* Make the rtx itself. */
4132 s = match_pattern_2 (s, info, &root_pos, pattern);
4134 /* If the match is only valid when extra clobbers are added,
4135 make sure we're able to pass that information to the caller. */
4136 if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers)
4137 s = add_decision (s, rtx_test::have_num_clobbers (), true, false);
4140 /* Make sure that the C test is true. */
4141 const char *c_test = get_c_test (info->def);
4142 if (maybe_eval_c_test (c_test) != 1)
4143 s = add_decision (s, rtx_test::c_test (c_test), true, false);
4145 /* Accept the pattern. */
4146 add_decision (s, rtx_test::accept (acceptance), true, false);
4149 /* Like match_pattern_1, but (if merge_states_p) try to merge the
4150 decisions with what's already in S, to reduce the amount of
4151 backtracking. */
4153 static void
4154 match_pattern (state *s, md_rtx_info *info, rtx pattern,
4155 acceptance_type acceptance)
4157 if (merge_states_p)
4159 state root;
4160 /* Add the decisions to a fresh state and then merge the full tree
4161 into the existing one. */
4162 match_pattern_1 (&root, info, pattern, acceptance);
4163 merge_into_state (s, &root);
4165 else
4166 match_pattern_1 (s, info, pattern, acceptance);
4169 /* Begin the output file. */
4171 static void
4172 write_header (void)
4174 puts ("\
4175 /* Generated automatically by the program `genrecog' from the target\n\
4176 machine description file. */\n\
4178 #include \"config.h\"\n\
4179 #include \"system.h\"\n\
4180 #include \"coretypes.h\"\n\
4181 #include \"backend.h\"\n\
4182 #include \"predict.h\"\n\
4183 #include \"rtl.h\"\n\
4184 #include \"memmodel.h\"\n\
4185 #include \"tm_p.h\"\n\
4186 #include \"emit-rtl.h\"\n\
4187 #include \"insn-config.h\"\n\
4188 #include \"recog.h\"\n\
4189 #include \"output.h\"\n\
4190 #include \"flags.h\"\n\
4191 #include \"df.h\"\n\
4192 #include \"resource.h\"\n\
4193 #include \"diagnostic-core.h\"\n\
4194 #include \"reload.h\"\n\
4195 #include \"regs.h\"\n\
4196 #include \"tm-constrs.h\"\n\
4197 \n");
4199 puts ("\n\
4200 /* `recog' contains a decision tree that recognizes whether the rtx\n\
4201 X0 is a valid instruction.\n\
4203 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
4204 returns a nonnegative number which is the insn code number for the\n\
4205 pattern that matched. This is the same as the order in the machine\n\
4206 description of the entry that matched. This number can be used as an\n\
4207 index into `insn_data' and other tables.\n");
4208 puts ("\
4209 The third parameter to recog is an optional pointer to an int. If\n\
4210 present, recog will accept a pattern if it matches except for missing\n\
4211 CLOBBER expressions at the end. In that case, the value pointed to by\n\
4212 the optional pointer will be set to the number of CLOBBERs that need\n\
4213 to be added (it should be initialized to zero by the caller). If it");
4214 puts ("\
4215 is set nonzero, the caller should allocate a PARALLEL of the\n\
4216 appropriate size, copy the initial entries, and call add_clobbers\n\
4217 (found in insn-emit.c) to fill in the CLOBBERs.\n\
4220 puts ("\n\
4221 The function split_insns returns 0 if the rtl could not\n\
4222 be split or the split rtl as an INSN list if it can be.\n\
4224 The function peephole2_insns returns 0 if the rtl could not\n\
4225 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4226 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4227 */\n\n");
4230 /* Return the C type of a parameter with type TYPE. */
4232 static const char *
4233 parameter_type_string (parameter::type_enum type)
4235 switch (type)
4237 case parameter::UNSET:
4238 break;
4240 case parameter::CODE:
4241 return "rtx_code";
4243 case parameter::MODE:
4244 return "machine_mode";
4246 case parameter::INT:
4247 return "int";
4249 case parameter::UINT:
4250 return "unsigned int";
4252 case parameter::WIDE_INT:
4253 return "HOST_WIDE_INT";
4255 gcc_unreachable ();
4258 /* Return true if ACCEPTANCE requires only a single C statement even in
4259 a backtracking context. */
4261 static bool
4262 single_statement_p (const acceptance_type &acceptance)
4264 if (acceptance.partial_p)
4265 /* We need to handle failures of the subroutine. */
4266 return false;
4267 switch (acceptance.type)
4269 case SUBPATTERN:
4270 case SPLIT:
4271 return true;
4273 case RECOG:
4274 /* False if we need to assign to pnum_clobbers. */
4275 return acceptance.u.full.u.num_clobbers == 0;
4277 case PEEPHOLE2:
4278 /* We need to assign to pmatch_len_ and handle null returns from the
4279 peephole2 routine. */
4280 return false;
4282 gcc_unreachable ();
4285 /* Return the C failure value for a routine of type TYPE. */
4287 static const char *
4288 get_failure_return (routine_type type)
4290 switch (type)
4292 case SUBPATTERN:
4293 case RECOG:
4294 return "-1";
4296 case SPLIT:
4297 case PEEPHOLE2:
4298 return "NULL";
4300 gcc_unreachable ();
4303 /* Indicates whether a block of code always returns or whether it can fall
4304 through. */
4306 enum exit_state {
4307 ES_RETURNED,
4308 ES_FALLTHROUGH
4311 /* Information used while writing out code. */
4313 struct output_state
4315 /* The type of routine that we're generating. */
4316 routine_type type;
4318 /* Maps position ids to xN variable numbers. The entry is only valid if
4319 it is less than the length of VAR_TO_ID, but this holds for every position
4320 tested by a state when writing out that state. */
4321 auto_vec <unsigned int> id_to_var;
4323 /* Maps xN variable numbers to position ids. */
4324 auto_vec <unsigned int> var_to_id;
4326 /* Index N is true if variable xN has already been set. */
4327 auto_vec <bool> seen_vars;
4330 /* Return true if D is a call to a pattern routine and if there is some X
4331 such that the transition for pattern result N goes to a successful return
4332 with code X+N. When returning true, set *BASE_OUT to this X and *COUNT_OUT
4333 to the number of return values. (We know that every PATTERN decision has
4334 a transition for every successful return.) */
4336 static bool
4337 terminal_pattern_p (decision *d, unsigned int *base_out,
4338 unsigned int *count_out)
4340 if (d->test.kind != rtx_test::PATTERN)
4341 return false;
4342 unsigned int base = 0;
4343 unsigned int count = 0;
4344 for (transition *trans = d->first; trans; trans = trans->next)
4346 if (trans->is_param || trans->labels.length () != 1)
4347 return false;
4348 decision *subd = trans->to->singleton ();
4349 if (!subd || subd->test.kind != rtx_test::ACCEPT)
4350 return false;
4351 unsigned int this_base = (subd->test.u.acceptance.u.full.code
4352 - trans->labels[0]);
4353 if (trans == d->first)
4354 base = this_base;
4355 else if (base != this_base)
4356 return false;
4357 count += 1;
4359 *base_out = base;
4360 *count_out = count;
4361 return true;
4364 /* Return true if TEST doesn't test an rtx or if the rtx it tests is
4365 already available in state OS. */
4367 static bool
4368 test_position_available_p (output_state *os, const rtx_test &test)
4370 return (!test.pos
4371 || test.pos_operand >= 0
4372 || os->seen_vars[os->id_to_var[test.pos->id]]);
4375 /* Like printf, but print INDENT spaces at the beginning. */
4377 static void ATTRIBUTE_PRINTF_2
4378 printf_indent (unsigned int indent, const char *format, ...)
4380 va_list ap;
4381 va_start (ap, format);
4382 printf ("%*s", indent, "");
4383 vprintf (format, ap);
4384 va_end (ap);
4387 /* Emit code to initialize the variable associated with POS, if it isn't
4388 already valid in state OS. Indent each line by INDENT spaces. Update
4389 OS with the new state. */
4391 static void
4392 change_state (output_state *os, position *pos, unsigned int indent)
4394 unsigned int var = os->id_to_var[pos->id];
4395 gcc_assert (var < os->var_to_id.length () && os->var_to_id[var] == pos->id);
4396 if (os->seen_vars[var])
4397 return;
4398 switch (pos->type)
4400 case POS_PEEP2_INSN:
4401 printf_indent (indent, "x%d = PATTERN (peep2_next_insn (%d));\n",
4402 var, pos->arg);
4403 break;
4405 case POS_XEXP:
4406 change_state (os, pos->base, indent);
4407 printf_indent (indent, "x%d = XEXP (x%d, %d);\n",
4408 var, os->id_to_var[pos->base->id], pos->arg);
4409 break;
4411 case POS_XVECEXP0:
4412 change_state (os, pos->base, indent);
4413 printf_indent (indent, "x%d = XVECEXP (x%d, 0, %d);\n",
4414 var, os->id_to_var[pos->base->id], pos->arg);
4415 break;
4417 os->seen_vars[var] = true;
4420 /* Print the enumerator constant for CODE -- the upcase version of
4421 the name. */
4423 static void
4424 print_code (enum rtx_code code)
4426 const char *p;
4427 for (p = GET_RTX_NAME (code); *p; p++)
4428 putchar (TOUPPER (*p));
4431 /* Emit a uint64_t as an integer constant expression. We need to take
4432 special care to avoid "decimal constant is so large that it is unsigned"
4433 warnings in the resulting code. */
4435 static void
4436 print_host_wide_int (uint64_t val)
4438 uint64_t min = uint64_t (1) << (HOST_BITS_PER_WIDE_INT - 1);
4439 if (val == min)
4440 printf ("(" HOST_WIDE_INT_PRINT_DEC_C " - 1)", val + 1);
4441 else
4442 printf (HOST_WIDE_INT_PRINT_DEC_C, val);
4445 /* Print the C expression for actual parameter PARAM. */
4447 static void
4448 print_parameter_value (const parameter &param)
4450 if (param.is_param)
4451 printf ("i%d", (int) param.value + 1);
4452 else
4453 switch (param.type)
4455 case parameter::UNSET:
4456 gcc_unreachable ();
4457 break;
4459 case parameter::CODE:
4460 print_code ((enum rtx_code) param.value);
4461 break;
4463 case parameter::MODE:
4464 printf ("%smode", GET_MODE_NAME ((machine_mode) param.value));
4465 break;
4467 case parameter::INT:
4468 printf ("%d", (int) param.value);
4469 break;
4471 case parameter::UINT:
4472 printf ("%u", (unsigned int) param.value);
4473 break;
4475 case parameter::WIDE_INT:
4476 print_host_wide_int (param.value);
4477 break;
4481 /* Print the C expression for the rtx tested by TEST. */
4483 static void
4484 print_test_rtx (output_state *os, const rtx_test &test)
4486 if (test.pos_operand >= 0)
4487 printf ("operands[%d]", test.pos_operand);
4488 else
4489 printf ("x%d", os->id_to_var[test.pos->id]);
4492 /* Print the C expression for non-boolean test TEST. */
4494 static void
4495 print_nonbool_test (output_state *os, const rtx_test &test)
4497 switch (test.kind)
4499 case rtx_test::CODE:
4500 printf ("GET_CODE (");
4501 print_test_rtx (os, test);
4502 printf (")");
4503 break;
4505 case rtx_test::MODE:
4506 printf ("GET_MODE (");
4507 print_test_rtx (os, test);
4508 printf (")");
4509 break;
4511 case rtx_test::VECLEN:
4512 printf ("XVECLEN (");
4513 print_test_rtx (os, test);
4514 printf (", 0)");
4515 break;
4517 case rtx_test::INT_FIELD:
4518 printf ("XINT (");
4519 print_test_rtx (os, test);
4520 printf (", %d)", test.u.opno);
4521 break;
4523 case rtx_test::REGNO_FIELD:
4524 printf ("REGNO (");
4525 print_test_rtx (os, test);
4526 printf (")");
4527 break;
4529 case rtx_test::WIDE_INT_FIELD:
4530 printf ("XWINT (");
4531 print_test_rtx (os, test);
4532 printf (", %d)", test.u.opno);
4533 break;
4535 case rtx_test::PATTERN:
4537 pattern_routine *routine = test.u.pattern->routine;
4538 printf ("pattern%d (", routine->pattern_id);
4539 const char *sep = "";
4540 if (test.pos)
4542 print_test_rtx (os, test);
4543 sep = ", ";
4545 if (routine->insn_p)
4547 printf ("%sinsn", sep);
4548 sep = ", ";
4550 if (routine->pnum_clobbers_p)
4552 printf ("%spnum_clobbers", sep);
4553 sep = ", ";
4555 for (unsigned int i = 0; i < test.u.pattern->params.length (); ++i)
4557 fputs (sep, stdout);
4558 print_parameter_value (test.u.pattern->params[i]);
4559 sep = ", ";
4561 printf (")");
4562 break;
4565 case rtx_test::PEEP2_COUNT:
4566 case rtx_test::VECLEN_GE:
4567 case rtx_test::SAVED_CONST_INT:
4568 case rtx_test::DUPLICATE:
4569 case rtx_test::PREDICATE:
4570 case rtx_test::SET_OP:
4571 case rtx_test::HAVE_NUM_CLOBBERS:
4572 case rtx_test::C_TEST:
4573 case rtx_test::ACCEPT:
4574 gcc_unreachable ();
4578 /* IS_PARAM and LABEL are taken from a transition whose source
4579 decision performs TEST. Print the C code for the label. */
4581 static void
4582 print_label_value (const rtx_test &test, bool is_param, uint64_t value)
4584 print_parameter_value (parameter (transition_parameter_type (test.kind),
4585 is_param, value));
4588 /* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
4589 If !IS_PARAM, print code to compare TEST with the C constant VALUE.
4590 Test for inequality if INVERT_P, otherwise test for equality. */
4592 static void
4593 print_test (output_state *os, const rtx_test &test, bool is_param,
4594 uint64_t value, bool invert_p)
4596 switch (test.kind)
4598 /* Handle the non-boolean TESTs. */
4599 case rtx_test::CODE:
4600 case rtx_test::MODE:
4601 case rtx_test::VECLEN:
4602 case rtx_test::REGNO_FIELD:
4603 case rtx_test::INT_FIELD:
4604 case rtx_test::WIDE_INT_FIELD:
4605 case rtx_test::PATTERN:
4606 print_nonbool_test (os, test);
4607 printf (" %s ", invert_p ? "!=" : "==");
4608 print_label_value (test, is_param, value);
4609 break;
4611 case rtx_test::SAVED_CONST_INT:
4612 gcc_assert (!is_param && value == 1);
4613 print_test_rtx (os, test);
4614 printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ",
4615 invert_p ? "!=" : "==");
4616 print_parameter_value (parameter (parameter::INT,
4617 test.u.integer.is_param,
4618 test.u.integer.value));
4619 printf ("]");
4620 break;
4622 case rtx_test::PEEP2_COUNT:
4623 gcc_assert (!is_param && value == 1);
4624 printf ("peep2_current_count %s %d", invert_p ? "<" : ">=",
4625 test.u.min_len);
4626 break;
4628 case rtx_test::VECLEN_GE:
4629 gcc_assert (!is_param && value == 1);
4630 printf ("XVECLEN (");
4631 print_test_rtx (os, test);
4632 printf (", 0) %s %d", invert_p ? "<" : ">=", test.u.min_len);
4633 break;
4635 case rtx_test::PREDICATE:
4636 gcc_assert (!is_param && value == 1);
4637 printf ("%s%s (", invert_p ? "!" : "", test.u.predicate.data->name);
4638 print_test_rtx (os, test);
4639 printf (", ");
4640 print_parameter_value (parameter (parameter::MODE,
4641 test.u.predicate.mode_is_param,
4642 test.u.predicate.mode));
4643 printf (")");
4644 break;
4646 case rtx_test::DUPLICATE:
4647 gcc_assert (!is_param && value == 1);
4648 printf ("%srtx_equal_p (", invert_p ? "!" : "");
4649 print_test_rtx (os, test);
4650 printf (", operands[%d])", test.u.opno);
4651 break;
4653 case rtx_test::HAVE_NUM_CLOBBERS:
4654 gcc_assert (!is_param && value == 1);
4655 printf ("pnum_clobbers %s NULL", invert_p ? "==" : "!=");
4656 break;
4658 case rtx_test::C_TEST:
4659 gcc_assert (!is_param && value == 1);
4660 if (invert_p)
4661 printf ("!");
4662 rtx_reader_ptr->print_c_condition (test.u.string);
4663 break;
4665 case rtx_test::ACCEPT:
4666 case rtx_test::SET_OP:
4667 gcc_unreachable ();
4671 static exit_state print_decision (output_state *, decision *,
4672 unsigned int, bool);
4674 /* Print code to perform S, indent each line by INDENT spaces.
4675 IS_FINAL is true if there are no fallback decisions to test on failure;
4676 if the state fails then the entire routine fails. */
4678 static exit_state
4679 print_state (output_state *os, state *s, unsigned int indent, bool is_final)
4681 exit_state es = ES_FALLTHROUGH;
4682 for (decision *d = s->first; d; d = d->next)
4683 es = print_decision (os, d, indent, is_final && !d->next);
4684 if (es != ES_RETURNED && is_final)
4686 printf_indent (indent, "return %s;\n", get_failure_return (os->type));
4687 es = ES_RETURNED;
4689 return es;
4692 /* Print the code for subroutine call ACCEPTANCE (for which partial_p
4693 is known to be true). Return the C condition that indicates a successful
4694 match. */
4696 static const char *
4697 print_subroutine_call (const acceptance_type &acceptance)
4699 switch (acceptance.type)
4701 case SUBPATTERN:
4702 gcc_unreachable ();
4704 case RECOG:
4705 printf ("recog_%d (x1, insn, pnum_clobbers)",
4706 acceptance.u.subroutine_id);
4707 return ">= 0";
4709 case SPLIT:
4710 printf ("split_%d (x1, insn)", acceptance.u.subroutine_id);
4711 return "!= NULL_RTX";
4713 case PEEPHOLE2:
4714 printf ("peephole2_%d (x1, insn, pmatch_len_)",
4715 acceptance.u.subroutine_id);
4716 return "!= NULL_RTX";
4718 gcc_unreachable ();
4721 /* Print code for the successful match described by ACCEPTANCE.
4722 INDENT and IS_FINAL are as for print_state. */
4724 static exit_state
4725 print_acceptance (const acceptance_type &acceptance, unsigned int indent,
4726 bool is_final)
4728 if (acceptance.partial_p)
4730 /* Defer the rest of the match to a subroutine. */
4731 if (is_final)
4733 printf_indent (indent, "return ");
4734 print_subroutine_call (acceptance);
4735 printf (";\n");
4736 return ES_RETURNED;
4738 else
4740 printf_indent (indent, "res = ");
4741 const char *res_test = print_subroutine_call (acceptance);
4742 printf (";\n");
4743 printf_indent (indent, "if (res %s)\n", res_test);
4744 printf_indent (indent + 2, "return res;\n");
4745 return ES_FALLTHROUGH;
4748 switch (acceptance.type)
4750 case SUBPATTERN:
4751 printf_indent (indent, "return %d;\n", acceptance.u.full.code);
4752 return ES_RETURNED;
4754 case RECOG:
4755 if (acceptance.u.full.u.num_clobbers != 0)
4756 printf_indent (indent, "*pnum_clobbers = %d;\n",
4757 acceptance.u.full.u.num_clobbers);
4758 printf_indent (indent, "return %d; /* %s */\n", acceptance.u.full.code,
4759 get_insn_name (acceptance.u.full.code));
4760 return ES_RETURNED;
4762 case SPLIT:
4763 printf_indent (indent, "return gen_split_%d (insn, operands);\n",
4764 acceptance.u.full.code);
4765 return ES_RETURNED;
4767 case PEEPHOLE2:
4768 printf_indent (indent, "*pmatch_len_ = %d;\n",
4769 acceptance.u.full.u.match_len);
4770 if (is_final)
4772 printf_indent (indent, "return gen_peephole2_%d (insn, operands);\n",
4773 acceptance.u.full.code);
4774 return ES_RETURNED;
4776 else
4778 printf_indent (indent, "res = gen_peephole2_%d (insn, operands);\n",
4779 acceptance.u.full.code);
4780 printf_indent (indent, "if (res != NULL_RTX)\n");
4781 printf_indent (indent + 2, "return res;\n");
4782 return ES_FALLTHROUGH;
4785 gcc_unreachable ();
4788 /* Print code to perform D. INDENT and IS_FINAL are as for print_state. */
4790 static exit_state
4791 print_decision (output_state *os, decision *d, unsigned int indent,
4792 bool is_final)
4794 uint64_t label;
4795 unsigned int base, count;
4797 /* Make sure the rtx under test is available either in operands[] or
4798 in an xN variable. */
4799 if (d->test.pos && d->test.pos_operand < 0)
4800 change_state (os, d->test.pos, indent);
4802 /* Look for cases where a pattern routine P1 calls another pattern routine
4803 P2 and where P1 returns X + BASE whenever P2 returns X. If IS_FINAL
4804 is true and BASE is zero we can simply use:
4806 return patternN (...);
4808 Otherwise we can use:
4810 res = patternN (...);
4811 if (res >= 0)
4812 return res + BASE;
4814 However, if BASE is nonzero and patternN only returns 0 or -1,
4815 the usual "return BASE;" is better than "return res + BASE;".
4816 If BASE is zero, "return res;" should be better than "return 0;",
4817 since no assignment to the return register is required. */
4818 if (os->type == SUBPATTERN
4819 && terminal_pattern_p (d, &base, &count)
4820 && (base == 0 || count > 1))
4822 if (is_final && base == 0)
4824 printf_indent (indent, "return ");
4825 print_nonbool_test (os, d->test);
4826 printf ("; /* [-1, %d] */\n", count - 1);
4827 return ES_RETURNED;
4829 else
4831 printf_indent (indent, "res = ");
4832 print_nonbool_test (os, d->test);
4833 printf (";\n");
4834 printf_indent (indent, "if (res >= 0)\n");
4835 printf_indent (indent + 2, "return res");
4836 if (base != 0)
4837 printf (" + %d", base);
4838 printf ("; /* [%d, %d] */\n", base, base + count - 1);
4839 return ES_FALLTHROUGH;
4842 else if (d->test.kind == rtx_test::ACCEPT)
4843 return print_acceptance (d->test.u.acceptance, indent, is_final);
4844 else if (d->test.kind == rtx_test::SET_OP)
4846 printf_indent (indent, "operands[%d] = ", d->test.u.opno);
4847 print_test_rtx (os, d->test);
4848 printf (";\n");
4849 return print_state (os, d->singleton ()->to, indent, is_final);
4851 /* Handle decisions with a single transition and a single transition
4852 label. */
4853 else if (d->if_statement_p (&label))
4855 transition *trans = d->singleton ();
4856 if (mark_optional_transitions_p && trans->optional)
4857 printf_indent (indent, "/* OPTIONAL IF */\n");
4859 /* Print the condition associated with TRANS. Invert it if IS_FINAL,
4860 so that we return immediately on failure and fall through on
4861 success. */
4862 printf_indent (indent, "if (");
4863 print_test (os, d->test, trans->is_param, label, is_final);
4865 /* Look for following states that would be handled by this code
4866 on recursion. If they don't need any preparatory statements,
4867 include them in the current "if" statement rather than creating
4868 a new one. */
4869 for (;;)
4871 d = trans->to->singleton ();
4872 if (!d
4873 || d->test.kind == rtx_test::ACCEPT
4874 || d->test.kind == rtx_test::SET_OP
4875 || !d->if_statement_p (&label)
4876 || !test_position_available_p (os, d->test))
4877 break;
4878 trans = d->first;
4879 printf ("\n");
4880 if (mark_optional_transitions_p && trans->optional)
4881 printf_indent (indent + 4, "/* OPTIONAL IF */\n");
4882 printf_indent (indent + 4, "%s ", is_final ? "||" : "&&");
4883 print_test (os, d->test, trans->is_param, label, is_final);
4885 printf (")\n");
4887 /* Print the conditional code with INDENT + 2 and the fallthrough
4888 code with indent INDENT. */
4889 state *to = trans->to;
4890 if (is_final)
4892 /* We inverted the condition above, so return failure in the
4893 "if" body and fall through to the target of the transition. */
4894 printf_indent (indent + 2, "return %s;\n",
4895 get_failure_return (os->type));
4896 return print_state (os, to, indent, is_final);
4898 else if (to->singleton ()
4899 && to->first->test.kind == rtx_test::ACCEPT
4900 && single_statement_p (to->first->test.u.acceptance))
4902 /* The target of the transition is a simple "return" statement.
4903 It doesn't need any braces and doesn't fall through. */
4904 if (print_acceptance (to->first->test.u.acceptance,
4905 indent + 2, true) != ES_RETURNED)
4906 gcc_unreachable ();
4907 return ES_FALLTHROUGH;
4909 else
4911 /* The general case. Output code for the target of the transition
4912 in braces. This will not invalidate any of the xN variables
4913 that are already valid, but we mustn't rely on any that are
4914 set by the "if" body. */
4915 auto_vec <bool, 32> old_seen;
4916 old_seen.safe_splice (os->seen_vars);
4918 printf_indent (indent + 2, "{\n");
4919 print_state (os, trans->to, indent + 4, is_final);
4920 printf_indent (indent + 2, "}\n");
4922 os->seen_vars.truncate (0);
4923 os->seen_vars.splice (old_seen);
4924 return ES_FALLTHROUGH;
4927 else
4929 /* Output the decision as a switch statement. */
4930 printf_indent (indent, "switch (");
4931 print_nonbool_test (os, d->test);
4932 printf (")\n");
4934 /* Each case statement starts with the same set of valid variables.
4935 These are also the only variables will be valid on fallthrough. */
4936 auto_vec <bool, 32> old_seen;
4937 old_seen.safe_splice (os->seen_vars);
4939 printf_indent (indent + 2, "{\n");
4940 for (transition *trans = d->first; trans; trans = trans->next)
4942 gcc_assert (!trans->is_param);
4943 if (mark_optional_transitions_p && trans->optional)
4944 printf_indent (indent + 2, "/* OPTIONAL CASE */\n");
4945 for (int_set::iterator j = trans->labels.begin ();
4946 j != trans->labels.end (); ++j)
4948 printf_indent (indent + 2, "case ");
4949 print_label_value (d->test, trans->is_param, *j);
4950 printf (":\n");
4952 if (print_state (os, trans->to, indent + 4, is_final))
4954 /* The state can fall through. Add an explicit break. */
4955 gcc_assert (!is_final);
4956 printf_indent (indent + 4, "break;\n");
4958 printf ("\n");
4960 /* Restore the original set of valid variables. */
4961 os->seen_vars.truncate (0);
4962 os->seen_vars.splice (old_seen);
4964 /* Add a default case. */
4965 printf_indent (indent + 2, "default:\n");
4966 if (is_final)
4967 printf_indent (indent + 4, "return %s;\n",
4968 get_failure_return (os->type));
4969 else
4970 printf_indent (indent + 4, "break;\n");
4971 printf_indent (indent + 2, "}\n");
4972 return is_final ? ES_RETURNED : ES_FALLTHROUGH;
4976 /* Make sure that OS has a position variable for POS. ROOT_P is true if
4977 POS is the root position for the routine. */
4979 static void
4980 assign_position_var (output_state *os, position *pos, bool root_p)
4982 unsigned int idx = os->id_to_var[pos->id];
4983 if (idx < os->var_to_id.length () && os->var_to_id[idx] == pos->id)
4984 return;
4985 if (!root_p && pos->type != POS_PEEP2_INSN)
4986 assign_position_var (os, pos->base, false);
4987 os->id_to_var[pos->id] = os->var_to_id.length ();
4988 os->var_to_id.safe_push (pos->id);
4991 /* Make sure that OS has the position variables required by S. */
4993 static void
4994 assign_position_vars (output_state *os, state *s)
4996 for (decision *d = s->first; d; d = d->next)
4998 /* Positions associated with operands can be read from the
4999 operands[] array. */
5000 if (d->test.pos && d->test.pos_operand < 0)
5001 assign_position_var (os, d->test.pos, false);
5002 for (transition *trans = d->first; trans; trans = trans->next)
5003 assign_position_vars (os, trans->to);
5007 /* Print the open brace and variable definitions for a routine that
5008 implements S. ROOT is the deepest rtx from which S can access all
5009 relevant parts of the first instruction it matches. Initialize OS
5010 so that every relevant position has an rtx variable xN and so that
5011 only ROOT's variable has a valid value. */
5013 static void
5014 print_subroutine_start (output_state *os, state *s, position *root)
5016 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED"
5017 " = &recog_data.operand[0];\n");
5018 os->var_to_id.truncate (0);
5019 os->seen_vars.truncate (0);
5020 if (root)
5022 /* Create a fake entry for position 0 so that an id_to_var of 0
5023 is always invalid. This also makes the xN variables naturally
5024 1-based rather than 0-based. */
5025 os->var_to_id.safe_push (num_positions);
5027 /* Associate ROOT with x1. */
5028 assign_position_var (os, root, true);
5030 /* Assign xN variables to all other relevant positions. */
5031 assign_position_vars (os, s);
5033 /* Output the variable declarations (except for ROOT's, which is
5034 passed in as a parameter). */
5035 unsigned int num_vars = os->var_to_id.length ();
5036 if (num_vars > 2)
5038 for (unsigned int i = 2; i < num_vars; ++i)
5039 /* Print 8 rtx variables to a line. */
5040 printf ("%s x%d",
5041 i == 2 ? " rtx" : (i - 2) % 8 == 0 ? ";\n rtx" : ",", i);
5042 printf (";\n");
5045 /* Say that x1 is valid and the rest aren't. */
5046 os->seen_vars.safe_grow_cleared (num_vars);
5047 os->seen_vars[1] = true;
5049 if (os->type == SUBPATTERN || os->type == RECOG)
5050 printf (" int res ATTRIBUTE_UNUSED;\n");
5051 else
5052 printf (" rtx_insn *res ATTRIBUTE_UNUSED;\n");
5055 /* Output the definition of pattern routine ROUTINE. */
5057 static void
5058 print_pattern (output_state *os, pattern_routine *routine)
5060 printf ("\nstatic int\npattern%d (", routine->pattern_id);
5061 const char *sep = "";
5062 /* Add the top-level rtx parameter, if any. */
5063 if (routine->pos)
5065 printf ("%srtx x1", sep);
5066 sep = ", ";
5068 /* Add the optional parameters. */
5069 if (routine->insn_p)
5071 /* We can't easily tell whether a C condition actually reads INSN,
5072 so add an ATTRIBUTE_UNUSED just in case. */
5073 printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep);
5074 sep = ", ";
5076 if (routine->pnum_clobbers_p)
5078 printf ("%sint *pnum_clobbers", sep);
5079 sep = ", ";
5081 /* Add the "i" parameters. */
5082 for (unsigned int i = 0; i < routine->param_types.length (); ++i)
5084 printf ("%s%s i%d", sep,
5085 parameter_type_string (routine->param_types[i]), i + 1);
5086 sep = ", ";
5088 printf (")\n");
5089 os->type = SUBPATTERN;
5090 print_subroutine_start (os, routine->s, routine->pos);
5091 print_state (os, routine->s, 2, true);
5092 printf ("}\n");
5095 /* Output a routine of type TYPE that implements S. PROC_ID is the
5096 number of the subroutine associated with S, or 0 if S is the main
5097 routine. */
5099 static void
5100 print_subroutine (output_state *os, state *s, int proc_id)
5102 printf ("\n");
5103 switch (os->type)
5105 case SUBPATTERN:
5106 gcc_unreachable ();
5108 case RECOG:
5109 if (proc_id)
5110 printf ("static int\nrecog_%d", proc_id);
5111 else
5112 printf ("int\nrecog");
5113 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5114 "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5115 "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n");
5116 break;
5118 case SPLIT:
5119 if (proc_id)
5120 printf ("static rtx_insn *\nsplit_%d", proc_id);
5121 else
5122 printf ("rtx_insn *\nsplit_insns");
5123 printf (" (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED)\n");
5124 break;
5126 case PEEPHOLE2:
5127 if (proc_id)
5128 printf ("static rtx_insn *\npeephole2_%d", proc_id);
5129 else
5130 printf ("rtx_insn *\npeephole2_insns");
5131 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5132 "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5133 "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n");
5134 break;
5136 print_subroutine_start (os, s, &root_pos);
5137 if (proc_id == 0)
5139 printf (" recog_data.insn = NULL;\n");
5141 print_state (os, s, 2, true);
5142 printf ("}\n");
5145 /* Print out a routine of type TYPE that performs ROOT. */
5147 static void
5148 print_subroutine_group (output_state *os, routine_type type, state *root)
5150 os->type = type;
5151 if (use_subroutines_p)
5153 /* Split ROOT up into smaller pieces, both for readability and to
5154 help the compiler. */
5155 auto_vec <state *> subroutines;
5156 find_subroutines (type, root, subroutines);
5158 /* Output the subroutines (but not ROOT itself). */
5159 unsigned int i;
5160 state *s;
5161 FOR_EACH_VEC_ELT (subroutines, i, s)
5162 print_subroutine (os, s, i + 1);
5164 /* Output the main routine. */
5165 print_subroutine (os, root, 0);
5168 /* Return the rtx pattern for the list of rtxes in a define_peephole2. */
5170 static rtx
5171 get_peephole2_pattern (md_rtx_info *info)
5173 int i, j;
5174 rtvec vec = XVEC (info->def, 0);
5175 rtx pattern = rtx_alloc (SEQUENCE);
5176 XVEC (pattern, 0) = rtvec_alloc (GET_NUM_ELEM (vec));
5177 for (i = j = 0; i < GET_NUM_ELEM (vec); i++)
5179 rtx x = RTVEC_ELT (vec, i);
5180 /* Ignore scratch register requirements. */
5181 if (GET_CODE (x) != MATCH_SCRATCH && GET_CODE (x) != MATCH_DUP)
5183 XVECEXP (pattern, 0, j) = x;
5184 j++;
5187 XVECLEN (pattern, 0) = j;
5188 if (j == 0)
5189 error_at (info->loc, "empty define_peephole2");
5190 return pattern;
5193 /* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
5194 rtx can be added automatically by add_clobbers. If so, update
5195 *ACCEPTANCE_PTR so that its num_clobbers field contains the number
5196 of such trailing rtxes and update *PATTERN_PTR so that it contains
5197 the pattern without those rtxes. */
5199 static bool
5200 remove_clobbers (acceptance_type *acceptance_ptr, rtx *pattern_ptr)
5202 int i;
5203 rtx new_pattern;
5205 /* Find the last non-clobber in the parallel. */
5206 rtx pattern = *pattern_ptr;
5207 for (i = XVECLEN (pattern, 0); i > 0; i--)
5209 rtx x = XVECEXP (pattern, 0, i - 1);
5210 if (GET_CODE (x) != CLOBBER
5211 || (!REG_P (XEXP (x, 0))
5212 && GET_CODE (XEXP (x, 0)) != MATCH_SCRATCH))
5213 break;
5216 if (i == XVECLEN (pattern, 0))
5217 return false;
5219 /* Build a similar insn without the clobbers. */
5220 if (i == 1)
5221 new_pattern = XVECEXP (pattern, 0, 0);
5222 else
5224 new_pattern = rtx_alloc (PARALLEL);
5225 XVEC (new_pattern, 0) = rtvec_alloc (i);
5226 for (int j = 0; j < i; ++j)
5227 XVECEXP (new_pattern, 0, j) = XVECEXP (pattern, 0, j);
5230 /* Recognize it. */
5231 acceptance_ptr->u.full.u.num_clobbers = XVECLEN (pattern, 0) - i;
5232 *pattern_ptr = new_pattern;
5233 return true;
5237 main (int argc, const char **argv)
5239 state insn_root, split_root, peephole2_root;
5241 progname = "genrecog";
5243 if (!init_rtx_reader_args (argc, argv))
5244 return (FATAL_EXIT_CODE);
5246 write_header ();
5248 /* Read the machine description. */
5250 md_rtx_info info;
5251 while (read_md_rtx (&info))
5253 rtx def = info.def;
5255 acceptance_type acceptance;
5256 acceptance.partial_p = false;
5257 acceptance.u.full.code = info.index;
5259 rtx pattern;
5260 switch (GET_CODE (def))
5262 case DEFINE_INSN:
5264 /* Match the instruction in the original .md form. */
5265 acceptance.type = RECOG;
5266 acceptance.u.full.u.num_clobbers = 0;
5267 pattern = add_implicit_parallel (XVEC (def, 1));
5268 validate_pattern (pattern, &info, NULL_RTX, 0);
5269 match_pattern (&insn_root, &info, pattern, acceptance);
5271 /* If the pattern is a PARALLEL with trailing CLOBBERs,
5272 allow recog_for_combine to match without the clobbers. */
5273 if (GET_CODE (pattern) == PARALLEL
5274 && remove_clobbers (&acceptance, &pattern))
5275 match_pattern (&insn_root, &info, pattern, acceptance);
5276 break;
5279 case DEFINE_SPLIT:
5280 acceptance.type = SPLIT;
5281 pattern = add_implicit_parallel (XVEC (def, 0));
5282 validate_pattern (pattern, &info, NULL_RTX, 0);
5283 match_pattern (&split_root, &info, pattern, acceptance);
5285 /* Declare the gen_split routine that we'll call if the
5286 pattern matches. The definition comes from insn-emit.c. */
5287 printf ("extern rtx_insn *gen_split_%d (rtx_insn *, rtx *);\n",
5288 info.index);
5289 break;
5291 case DEFINE_PEEPHOLE2:
5292 acceptance.type = PEEPHOLE2;
5293 pattern = get_peephole2_pattern (&info);
5294 validate_pattern (pattern, &info, NULL_RTX, 0);
5295 match_pattern (&peephole2_root, &info, pattern, acceptance);
5297 /* Declare the gen_peephole2 routine that we'll call if the
5298 pattern matches. The definition comes from insn-emit.c. */
5299 printf ("extern rtx_insn *gen_peephole2_%d (rtx_insn *, rtx *);\n",
5300 info.index);
5301 break;
5303 default:
5304 /* do nothing */;
5308 if (have_error)
5309 return FATAL_EXIT_CODE;
5311 puts ("\n\n");
5313 /* Optimize each routine in turn. */
5314 optimize_subroutine_group ("recog", &insn_root);
5315 optimize_subroutine_group ("split_insns", &split_root);
5316 optimize_subroutine_group ("peephole2_insns", &peephole2_root);
5318 output_state os;
5319 os.id_to_var.safe_grow_cleared (num_positions);
5321 if (use_pattern_routines_p)
5323 /* Look for common patterns and split them out into subroutines. */
5324 auto_vec <merge_state_info> states;
5325 states.safe_push (&insn_root);
5326 states.safe_push (&split_root);
5327 states.safe_push (&peephole2_root);
5328 split_out_patterns (states);
5330 /* Print out the routines that we just created. */
5331 unsigned int i;
5332 pattern_routine *routine;
5333 FOR_EACH_VEC_ELT (patterns, i, routine)
5334 print_pattern (&os, routine);
5337 /* Print out the matching routines. */
5338 print_subroutine_group (&os, RECOG, &insn_root);
5339 print_subroutine_group (&os, SPLIT, &split_root);
5340 print_subroutine_group (&os, PEEPHOLE2, &peephole2_root);
5342 fflush (stdout);
5343 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);