1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987-2015 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)
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
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
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
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. */
109 #include "coretypes.h"
114 #include "gensupport.h"
117 #undef GENERATOR_FILE
119 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM,
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
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
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
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
193 static const unsigned int MAX_PATTERN_PARAMS
= 5;
195 /* The maximum operand number plus one. */
198 /* Ways of obtaining an rtx to be tested. */
200 /* PATTERN (peep2_next_insn (ARG)). */
203 /* XEXP (BASE, ARG). */
206 /* XVECEXP (BASE, 0, ARG). */
210 /* The position of an rtx relative to X0. Each useful position is
211 represented by exactly one instance of this structure. */
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
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). */
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. */
245 /* A unique identifier for this position. */
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
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
;
278 pos
= XCNEW (struct position
);
281 if (type
== POS_PEEP2_INSN
)
285 pos
->depth
= base
->depth
;
290 pos
->insn_id
= base
->insn_id
;
291 pos
->depth
= base
->depth
+ 1;
293 pos
->id
= num_positions
++;
299 /* Compare positions POS1 and POS2 lexicographically. */
302 compare_positions (struct position
*pos1
, struct position
*pos2
)
306 diff
= pos1
->depth
- pos2
->depth
;
310 while (pos1
->depth
!= pos2
->depth
);
314 while (pos1
->depth
!= pos2
->depth
);
317 diff
= (int) pos1
->type
- (int) pos2
->type
;
319 diff
= pos1
->arg
- pos2
->arg
;
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
)
347 /* Search for and return operand N, stop when reaching node STOP. */
350 find_operand (rtx pattern
, int n
, rtx 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
)
368 fmt
= GET_RTX_FORMAT (code
);
369 len
= GET_RTX_LENGTH (code
);
370 for (i
= 0; i
< len
; i
++)
375 if ((r
= find_operand (XEXP (pattern
, i
), n
, stop
)) != NULL_RTX
)
380 if (! XVEC (pattern
, i
))
385 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
386 if ((r
= find_operand (XVECEXP (pattern
, i
, j
), n
, stop
))
391 case 'i': case 'r': case 'w': case '0': case 's':
402 /* Search for and return operand M, such that it has a matching
403 constraint for operand N. */
406 find_matching_operand (rtx pattern
, int n
)
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
)))
420 fmt
= GET_RTX_FORMAT (code
);
421 len
= GET_RTX_LENGTH (code
);
422 for (i
= 0; i
< len
; i
++)
427 if ((r
= find_matching_operand (XEXP (pattern
, i
), n
)))
432 if (! XVEC (pattern
, i
))
437 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
438 if ((r
= find_matching_operand (XVECEXP (pattern
, i
, j
), n
)))
442 case 'i': case 'r': case 'w': case '0': case 's':
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. */
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 /* Check for various errors in PATTERN, which is part of INFO.
467 SET is nonnull for a destination, and is the complete set pattern.
468 SET_CODE is '=' for normal sets, and '+' within a context that
469 requires in-out constraints. */
472 validate_pattern (rtx pattern
, md_rtx_info
*info
, rtx set
, int set_code
)
479 code
= GET_CODE (pattern
);
484 const char constraints0
= XSTR (pattern
, 1)[0];
486 if (!constraints_supported_in_insn_p (info
->def
))
490 error_at (info
->loc
, "constraints not supported in %s",
491 GET_RTX_NAME (GET_CODE (info
->def
)));
496 /* If a MATCH_SCRATCH is used in a context requiring an write-only
497 or read/write register, validate that. */
500 && constraints0
!= '='
501 && constraints0
!= '+')
503 error_at (info
->loc
, "operand %d missing output reload",
511 if (find_operand (info
->def
, XINT (pattern
, 0), pattern
) == pattern
)
512 error_at (info
->loc
, "operand %i duplicated before defined",
518 const char *pred_name
= XSTR (pattern
, 1);
519 const struct pred_data
*pred
;
522 if (GET_CODE (info
->def
) == DEFINE_INSN
)
523 c_test
= XSTR (info
->def
, 2);
525 c_test
= XSTR (info
->def
, 1);
527 if (pred_name
[0] != 0)
529 pred
= lookup_predicate (pred_name
);
531 error_at (info
->loc
, "unknown predicate '%s'", pred_name
);
536 if (code
== MATCH_OPERAND
)
538 const char *constraints
= XSTR (pattern
, 2);
539 const char constraints0
= constraints
[0];
541 if (!constraints_supported_in_insn_p (info
->def
))
545 error_at (info
->loc
, "constraints not supported in %s",
546 GET_RTX_NAME (GET_CODE (info
->def
)));
550 /* A MATCH_OPERAND that is a SET should have an output reload. */
551 else if (set
&& constraints0
)
555 if (constraints0
== '+')
557 /* If we've only got an output reload for this operand,
558 we'd better have a matching input operand. */
559 else if (constraints0
== '='
560 && find_matching_operand (info
->def
,
564 error_at (info
->loc
, "operand %d missing in-out reload",
567 else if (constraints0
!= '=' && constraints0
!= '+')
568 error_at (info
->loc
, "operand %d missing output reload",
572 /* For matching constraint in MATCH_OPERAND, the digit must be a
573 smaller number than the number of the operand that uses it in the
577 while (constraints
[0]
578 && (constraints
[0] == ' ' || constraints
[0] == ','))
583 if (constraints
[0] >= '0' && constraints
[0] <= '9')
587 sscanf (constraints
, "%d", &val
);
588 if (val
>= XINT (pattern
, 0))
589 error_at (info
->loc
, "constraint digit %d is not"
590 " smaller than operand %d",
591 val
, XINT (pattern
, 0));
594 while (constraints
[0] && constraints
[0] != ',')
599 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
600 while not likely to occur at runtime, results in less efficient
601 code from insn-recog.c. */
602 if (set
&& pred
&& pred
->allows_non_lvalue
)
603 error_at (info
->loc
, "destination operand %d allows non-lvalue",
606 /* A modeless MATCH_OPERAND can be handy when we can check for
607 multiple modes in the c_test. In most other cases, it is a
608 mistake. Only DEFINE_INSN is eligible, since SPLIT and
609 PEEP2 can FAIL within the output pattern. Exclude special
610 predicates, which check the mode themselves. Also exclude
611 predicates that allow only constants. Exclude the SET_DEST
612 of a call instruction, as that is a common idiom. */
614 if (GET_MODE (pattern
) == VOIDmode
615 && code
== MATCH_OPERAND
616 && GET_CODE (info
->def
) == DEFINE_INSN
619 && pred
->allows_non_const
620 && strstr (c_test
, "operands") == NULL
622 && GET_CODE (set
) == SET
623 && GET_CODE (SET_SRC (set
)) == CALL
))
624 message_at (info
->loc
, "warning: operand %d missing mode?",
631 machine_mode dmode
, smode
;
634 dest
= SET_DEST (pattern
);
635 src
= SET_SRC (pattern
);
637 /* STRICT_LOW_PART is a wrapper. Its argument is the real
638 destination, and it's mode should match the source. */
639 if (GET_CODE (dest
) == STRICT_LOW_PART
)
640 dest
= XEXP (dest
, 0);
642 /* Find the referent for a DUP. */
644 if (GET_CODE (dest
) == MATCH_DUP
645 || GET_CODE (dest
) == MATCH_OP_DUP
646 || GET_CODE (dest
) == MATCH_PAR_DUP
)
647 dest
= find_operand (info
->def
, XINT (dest
, 0), NULL
);
649 if (GET_CODE (src
) == MATCH_DUP
650 || GET_CODE (src
) == MATCH_OP_DUP
651 || GET_CODE (src
) == MATCH_PAR_DUP
)
652 src
= find_operand (info
->def
, XINT (src
, 0), NULL
);
654 dmode
= GET_MODE (dest
);
655 smode
= GET_MODE (src
);
657 /* The mode of an ADDRESS_OPERAND is the mode of the memory
658 reference, not the mode of the address. */
659 if (GET_CODE (src
) == MATCH_OPERAND
660 && ! strcmp (XSTR (src
, 1), "address_operand"))
663 /* The operands of a SET must have the same mode unless one
665 else if (dmode
!= VOIDmode
&& smode
!= VOIDmode
&& dmode
!= smode
)
666 error_at (info
->loc
, "mode mismatch in set: %smode vs %smode",
667 GET_MODE_NAME (dmode
), GET_MODE_NAME (smode
));
669 /* If only one of the operands is VOIDmode, and PC or CC0 is
670 not involved, it's probably a mistake. */
671 else if (dmode
!= smode
672 && GET_CODE (dest
) != PC
673 && GET_CODE (dest
) != CC0
674 && GET_CODE (src
) != PC
675 && GET_CODE (src
) != CC0
676 && !CONST_INT_P (src
)
677 && !CONST_WIDE_INT_P (src
)
678 && GET_CODE (src
) != CALL
)
681 which
= (dmode
== VOIDmode
? "destination" : "source");
682 message_at (info
->loc
, "warning: %s missing a mode?", which
);
685 if (dest
!= SET_DEST (pattern
))
686 validate_pattern (dest
, info
, pattern
, '=');
687 validate_pattern (SET_DEST (pattern
), info
, pattern
, '=');
688 validate_pattern (SET_SRC (pattern
), info
, NULL_RTX
, 0);
693 validate_pattern (SET_DEST (pattern
), info
, pattern
, '=');
697 validate_pattern (XEXP (pattern
, 0), info
, set
, set
? '+' : 0);
698 validate_pattern (XEXP (pattern
, 1), info
, NULL_RTX
, 0);
699 validate_pattern (XEXP (pattern
, 2), info
, NULL_RTX
, 0);
702 case STRICT_LOW_PART
:
703 validate_pattern (XEXP (pattern
, 0), info
, set
, set
? '+' : 0);
707 if (GET_MODE (LABEL_REF_LABEL (pattern
)) != VOIDmode
)
708 error_at (info
->loc
, "operand to label_ref %smode not VOIDmode",
709 GET_MODE_NAME (GET_MODE (LABEL_REF_LABEL (pattern
))));
716 fmt
= GET_RTX_FORMAT (code
);
717 len
= GET_RTX_LENGTH (code
);
718 for (i
= 0; i
< len
; i
++)
723 validate_pattern (XEXP (pattern
, i
), info
, NULL_RTX
, 0);
727 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
728 validate_pattern (XVECEXP (pattern
, i
, j
), info
, NULL_RTX
, 0);
731 case 'i': case 'r': case 'w': case '0': case 's':
740 /* Simple list structure for items of type T, for use when being part
741 of a list is an inherent property of T. T must have members equivalent
742 to "T *prev, *next;" and a function "void set_parent (list_head <T> *)"
743 to set the parent list. */
744 template <typename T
>
747 /* A range of linked items. */
754 void set_parent (list_head
*);
759 void push_back (range
);
760 range
remove (range
);
761 void replace (range
, range
);
762 T
*singleton () const;
767 /* Create a range [START_IN, START_IN]. */
769 template <typename T
>
770 list_head
<T
>::range::range (T
*start_in
) : start (start_in
), end (start_in
) {}
772 /* Create a range [START_IN, END_IN], linked by next and prev fields. */
774 template <typename T
>
775 list_head
<T
>::range::range (T
*start_in
, T
*end_in
)
776 : start (start_in
), end (end_in
) {}
778 template <typename T
>
780 list_head
<T
>::range::set_parent (list_head
<T
> *owner
)
782 for (T
*item
= start
; item
!= end
; item
= item
->next
)
783 item
->set_parent (owner
);
784 end
->set_parent (owner
);
787 template <typename T
>
788 list_head
<T
>::list_head () : first (0), last (0) {}
790 /* Add R to the end of the list. */
792 template <typename T
>
794 list_head
<T
>::push_back (range r
)
797 last
->next
= r
.start
;
800 r
.start
->prev
= last
;
805 /* Remove R from the list. R remains valid and can be inserted into
808 template <typename T
>
809 typename list_head
<T
>::range
810 list_head
<T
>::remove (range r
)
813 r
.start
->prev
->next
= r
.end
->next
;
817 r
.end
->next
->prev
= r
.start
->prev
;
819 last
= r
.start
->prev
;
826 /* Replace OLDR with NEWR. OLDR remains valid and can be inserted into
829 template <typename T
>
831 list_head
<T
>::replace (range oldr
, range newr
)
833 newr
.start
->prev
= oldr
.start
->prev
;
834 newr
.end
->next
= oldr
.end
->next
;
836 oldr
.start
->prev
= 0;
840 if (newr
.start
->prev
)
841 newr
.start
->prev
->next
= newr
.start
;
845 newr
.end
->next
->prev
= newr
.end
;
848 newr
.set_parent (this);
851 /* Empty the list and return the previous contents as a range that can
852 be inserted into other lists. */
854 template <typename T
>
855 typename list_head
<T
>::range
856 list_head
<T
>::release ()
858 range
r (first
, last
);
865 /* If the list contains a single item, return that item, otherwise return
868 template <typename T
>
870 list_head
<T
>::singleton () const
872 return first
== last
? first
: 0;
877 /* Describes a possible successful return from a routine. */
878 struct acceptance_type
880 /* The type of routine we're returning from. */
881 routine_type type
: 16;
883 /* True if this structure only really represents a partial match,
884 and if we must call a subroutine of type TYPE to complete the match.
885 In this case we'll call the subroutine and, if it succeeds, return
886 whatever the subroutine returned.
888 False if this structure presents a full match. */
889 unsigned int partial_p
: 1;
893 /* If PARTIAL_P, this is the number of the subroutine to call. */
896 /* Valid if !PARTIAL_P. */
899 /* The identifier of the matching pattern. For SUBPATTERNs this
900 value belongs to an ad-hoc routine-specific enum. For the
901 others it's the number of an .md file pattern. */
905 /* For RECOG, the number of clobbers that must be added to the
906 pattern in order for it to match CODE. */
909 /* For PEEPHOLE2, the number of additional instructions that were
910 included in the optimization. */
918 operator == (const acceptance_type
&a
, const acceptance_type
&b
)
920 if (a
.partial_p
!= b
.partial_p
)
923 return a
.u
.subroutine_id
== b
.u
.subroutine_id
;
925 return a
.u
.full
.code
== b
.u
.full
.code
;
929 operator != (const acceptance_type
&a
, const acceptance_type
&b
)
931 return !operator == (a
, b
);
934 /* Represents a parameter to a pattern routine. */
937 /* The C type of parameter. */
939 /* Represents an invalid parameter. */
942 /* A machine_mode parameter. */
945 /* An rtx_code parameter. */
948 /* An int parameter. */
951 /* An unsigned int parameter. */
954 /* A HOST_WIDE_INT parameter. */
959 parameter (type_enum
, bool, uint64_t);
961 /* The type of the parameter. */
964 /* True if the value passed is variable, false if it is constant. */
967 /* If IS_PARAM, this is the number of the variable passed, for an "i%d"
968 format string. If !IS_PARAM, this is the constant value passed. */
972 parameter::parameter ()
973 : type (UNSET
), is_param (false), value (0) {}
975 parameter::parameter (type_enum type_in
, bool is_param_in
, uint64_t value_in
)
976 : type (type_in
), is_param (is_param_in
), value (value_in
) {}
979 operator == (const parameter
¶m1
, const parameter
¶m2
)
981 return (param1
.type
== param2
.type
982 && param1
.is_param
== param2
.is_param
983 && param1
.value
== param2
.value
);
987 operator != (const parameter
¶m1
, const parameter
¶m2
)
989 return !operator == (param1
, param2
);
992 /* Represents a routine that matches a partial rtx pattern, returning
993 an ad-hoc enum value on success and -1 on failure. The routine can
994 be used by any subroutine type. The match can be parameterized by
995 things like mode, code and UNSPEC number. */
996 struct pattern_routine
998 /* The state that implements the pattern. */
1001 /* The deepest root position from which S can access all the rtxes it needs.
1002 This is NULL if the pattern doesn't need an rtx input, usually because
1003 all matching is done on operands[] instead. */
1006 /* A unique identifier for the routine. */
1007 unsigned int pattern_id
;
1009 /* True if the routine takes pnum_clobbers as argument. */
1010 bool pnum_clobbers_p
;
1012 /* True if the routine takes the enclosing instruction as argument. */
1015 /* The types of the other parameters to the routine, if any. */
1016 auto_vec
<parameter::type_enum
, MAX_PATTERN_PARAMS
> param_types
;
1019 /* All defined patterns. */
1020 static vec
<pattern_routine
*> patterns
;
1022 /* Represents one use of a pattern routine. */
1025 /* The pattern routine to use. */
1026 pattern_routine
*routine
;
1028 /* The values to pass as parameters. This vector has the same length
1029 as ROUTINE->PARAM_TYPES. */
1030 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
1033 /* Represents a test performed by a decision. */
1038 /* The types of test that can be performed. Most of them take as input
1039 an rtx X. Some also take as input a transition label LABEL; the others
1040 are booleans for which the transition label is always "true".
1042 The order of the enum isn't important. */
1044 /* Check GET_CODE (X) == LABEL. */
1047 /* Check GET_MODE (X) == LABEL. */
1050 /* Check REGNO (X) == LABEL. */
1053 /* Check XINT (X, u.opno) == LABEL. */
1056 /* Check XWINT (X, u.opno) == LABEL. */
1059 /* Check XVECLEN (X, 0) == LABEL. */
1062 /* Check peep2_current_count >= u.min_len. */
1065 /* Check XVECLEN (X, 0) >= u.min_len. */
1068 /* Check whether X is a cached const_int with value u.integer. */
1071 /* Check u.predicate.data (X, u.predicate.mode). */
1074 /* Check rtx_equal_p (X, operands[u.opno]). */
1077 /* Check whether X matches pattern u.pattern. */
1080 /* Check whether pnum_clobbers is nonnull (RECOG only). */
1083 /* Check whether general C test u.string holds. In general the condition
1084 needs access to "insn" and the full operand list. */
1087 /* Execute operands[u.opno] = X. (Always succeeds.) */
1090 /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT.
1091 May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */
1095 /* The position of rtx X in the above description, relative to the
1096 incoming instruction "insn". The position is null if the test
1097 doesn't take an X as input. */
1100 /* Which element of operands[] already contains POS, or -1 if no element
1101 is known to hold POS. */
1104 /* The type of test and its parameters, as described above. */
1117 const struct pred_data
*data
;
1118 /* True if the mode is taken from a machine_mode parameter
1119 to the routine rather than a constant machine_mode. If true,
1120 MODE is the number of the parameter (for an "i%d" format string),
1121 otherwise it is the mode itself. */
1125 pattern_use
*pattern
;
1127 acceptance_type acceptance
;
1130 static rtx_test
code (position
*);
1131 static rtx_test
mode (position
*);
1132 static rtx_test
regno_field (position
*);
1133 static rtx_test
int_field (position
*, int);
1134 static rtx_test
wide_int_field (position
*, int);
1135 static rtx_test
veclen (position
*);
1136 static rtx_test
peep2_count (int);
1137 static rtx_test
veclen_ge (position
*, int);
1138 static rtx_test
predicate (position
*, const pred_data
*, machine_mode
);
1139 static rtx_test
duplicate (position
*, int);
1140 static rtx_test
pattern (position
*, pattern_use
*);
1141 static rtx_test
have_num_clobbers ();
1142 static rtx_test
c_test (const char *);
1143 static rtx_test
set_op (position
*, int);
1144 static rtx_test
accept (const acceptance_type
&);
1146 bool terminal_p () const;
1147 bool single_outcome_p () const;
1150 rtx_test (position
*, kind_enum
);
1153 rtx_test::rtx_test () {}
1155 rtx_test::rtx_test (position
*pos_in
, kind_enum kind_in
)
1156 : pos (pos_in
), pos_operand (-1), kind (kind_in
) {}
1159 rtx_test::code (position
*pos
)
1161 return rtx_test (pos
, rtx_test::CODE
);
1165 rtx_test::mode (position
*pos
)
1167 return rtx_test (pos
, rtx_test::MODE
);
1171 rtx_test::regno_field (position
*pos
)
1173 rtx_test
res (pos
, rtx_test::REGNO_FIELD
);
1178 rtx_test::int_field (position
*pos
, int opno
)
1180 rtx_test
res (pos
, rtx_test::INT_FIELD
);
1186 rtx_test::wide_int_field (position
*pos
, int opno
)
1188 rtx_test
res (pos
, rtx_test::WIDE_INT_FIELD
);
1194 rtx_test::veclen (position
*pos
)
1196 return rtx_test (pos
, rtx_test::VECLEN
);
1200 rtx_test::peep2_count (int min_len
)
1202 rtx_test
res (0, rtx_test::PEEP2_COUNT
);
1203 res
.u
.min_len
= min_len
;
1208 rtx_test::veclen_ge (position
*pos
, int min_len
)
1210 rtx_test
res (pos
, rtx_test::VECLEN_GE
);
1211 res
.u
.min_len
= min_len
;
1216 rtx_test::predicate (position
*pos
, const struct pred_data
*data
,
1219 rtx_test
res (pos
, rtx_test::PREDICATE
);
1220 res
.u
.predicate
.data
= data
;
1221 res
.u
.predicate
.mode_is_param
= false;
1222 res
.u
.predicate
.mode
= mode
;
1227 rtx_test::duplicate (position
*pos
, int opno
)
1229 rtx_test
res (pos
, rtx_test::DUPLICATE
);
1235 rtx_test::pattern (position
*pos
, pattern_use
*pattern
)
1237 rtx_test
res (pos
, rtx_test::PATTERN
);
1238 res
.u
.pattern
= pattern
;
1243 rtx_test::have_num_clobbers ()
1245 return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS
);
1249 rtx_test::c_test (const char *string
)
1251 rtx_test
res (0, rtx_test::C_TEST
);
1252 res
.u
.string
= string
;
1257 rtx_test::set_op (position
*pos
, int opno
)
1259 rtx_test
res (pos
, rtx_test::SET_OP
);
1265 rtx_test::accept (const acceptance_type
&acceptance
)
1267 rtx_test
res (0, rtx_test::ACCEPT
);
1268 res
.u
.acceptance
= acceptance
;
1272 /* Return true if the test represents an unconditionally successful match. */
1275 rtx_test::terminal_p () const
1277 return kind
== rtx_test::ACCEPT
&& u
.acceptance
.type
!= PEEPHOLE2
;
1280 /* Return true if the test is a boolean that is always true. */
1283 rtx_test::single_outcome_p () const
1285 return terminal_p () || kind
== rtx_test::SET_OP
;
1289 operator == (const rtx_test
&a
, const rtx_test
&b
)
1291 if (a
.pos
!= b
.pos
|| a
.kind
!= b
.kind
)
1295 case rtx_test::CODE
:
1296 case rtx_test::MODE
:
1297 case rtx_test::REGNO_FIELD
:
1298 case rtx_test::VECLEN
:
1299 case rtx_test::HAVE_NUM_CLOBBERS
:
1302 case rtx_test::PEEP2_COUNT
:
1303 case rtx_test::VECLEN_GE
:
1304 return a
.u
.min_len
== b
.u
.min_len
;
1306 case rtx_test::INT_FIELD
:
1307 case rtx_test::WIDE_INT_FIELD
:
1308 case rtx_test::DUPLICATE
:
1309 case rtx_test::SET_OP
:
1310 return a
.u
.opno
== b
.u
.opno
;
1312 case rtx_test::SAVED_CONST_INT
:
1313 return (a
.u
.integer
.is_param
== b
.u
.integer
.is_param
1314 && a
.u
.integer
.value
== b
.u
.integer
.value
);
1316 case rtx_test::PREDICATE
:
1317 return (a
.u
.predicate
.data
== b
.u
.predicate
.data
1318 && a
.u
.predicate
.mode_is_param
== b
.u
.predicate
.mode_is_param
1319 && a
.u
.predicate
.mode
== b
.u
.predicate
.mode
);
1321 case rtx_test::PATTERN
:
1322 return (a
.u
.pattern
->routine
== b
.u
.pattern
->routine
1323 && a
.u
.pattern
->params
== b
.u
.pattern
->params
);
1325 case rtx_test::C_TEST
:
1326 return strcmp (a
.u
.string
, b
.u
.string
) == 0;
1328 case rtx_test::ACCEPT
:
1329 return a
.u
.acceptance
== b
.u
.acceptance
;
1335 operator != (const rtx_test
&a
, const rtx_test
&b
)
1337 return !operator == (a
, b
);
1340 /* A simple set of transition labels. Most transitions have a singleton
1341 label, so try to make that case as efficient as possible. */
1342 struct int_set
: public auto_vec
<uint64_t, 1>
1344 typedef uint64_t *iterator
;
1348 int_set (const int_set
&);
1350 int_set
&operator = (const int_set
&);
1356 int_set::int_set () {}
1358 int_set::int_set (uint64_t label
)
1363 int_set::int_set (const int_set
&other
)
1365 safe_splice (other
);
1369 int_set::operator = (const int_set
&other
)
1372 safe_splice (other
);
1385 return address () + length ();
1389 operator == (const int_set
&a
, const int_set
&b
)
1391 if (a
.length () != b
.length ())
1393 for (unsigned int i
= 0; i
< a
.length (); ++i
)
1400 operator != (const int_set
&a
, const int_set
&b
)
1402 return !operator == (a
, b
);
1407 /* Represents a transition between states, dependent on the result of
1411 transition (const int_set
&, state
*, bool);
1413 void set_parent (list_head
<transition
> *);
1415 /* Links to other transitions for T. Always null for boolean tests. */
1416 transition
*prev
, *next
;
1418 /* The transition should be taken when T has one of these values.
1419 E.g. for rtx_test::CODE this is a set of codes, while for booleans like
1420 rtx_test::PREDICATE it is always a singleton "true". The labels are
1421 sorted in ascending order. */
1424 /* The source decision. */
1427 /* The target state. */
1430 /* True if TO would function correctly even if TEST wasn't performed.
1431 E.g. it isn't necessary to check whether GET_MODE (x1) is SImode
1432 before calling register_operand (x1, SImode), since register_operand
1433 performs its own mode check. However, checking GET_MODE can be a cheap
1434 way of disambiguating SImode and DImode register operands. */
1437 /* True if LABELS contains parameter numbers rather than constants.
1438 E.g. if this is true for a rtx_test::CODE, the label is the number
1439 of an rtx_code parameter rather than an rtx_code itself.
1440 LABELS is always a singleton when this variable is true. */
1444 /* Represents a test and the action that should be taken on the result.
1445 If a transition exists for the test outcome, the machine switches
1446 to the transition's target state. If no suitable transition exists,
1447 the machine either falls through to the next decision or, if there are no
1448 more decisions to try, fails the match. */
1449 struct decision
: list_head
<transition
>
1451 decision (const rtx_test
&);
1453 void set_parent (list_head
<decision
> *s
);
1454 bool if_statement_p (uint64_t * = 0) const;
1456 /* The state to which this decision belongs. */
1459 /* Links to other decisions in the same state. */
1460 decision
*prev
, *next
;
1462 /* The test to perform. */
1466 /* Represents one machine state. For each state the machine tries a list
1467 of decisions, in order, and acts on the first match. It fails without
1468 further backtracking if no decisions match. */
1469 struct state
: list_head
<decision
>
1471 void set_parent (list_head
<state
> *) {}
1474 transition::transition (const int_set
&labels_in
, state
*to_in
,
1476 : prev (0), next (0), labels (labels_in
), from (0), to (to_in
),
1477 optional (optional_in
), is_param (false) {}
1479 /* Set the source decision of the transition. */
1482 transition::set_parent (list_head
<transition
> *from_in
)
1484 from
= static_cast <decision
*> (from_in
);
1487 decision::decision (const rtx_test
&test_in
)
1488 : prev (0), next (0), test (test_in
) {}
1490 /* Set the state to which this decision belongs. */
1493 decision::set_parent (list_head
<decision
> *s_in
)
1495 s
= static_cast <state
*> (s_in
);
1498 /* Return true if the decision has a single transition with a single label.
1499 If so, return the label in *LABEL if nonnull. */
1502 decision::if_statement_p (uint64_t *label
) const
1504 if (singleton () && first
->labels
.length () == 1)
1507 *label
= first
->labels
[0];
1513 /* Add to FROM a decision that performs TEST and has a single transition
1517 add_decision (state
*from
, const rtx_test
&test
, transition
*trans
)
1519 decision
*d
= new decision (test
);
1520 from
->push_back (d
);
1521 d
->push_back (trans
);
1524 /* Add a transition from FROM to a new, empty state that is taken
1525 when TEST == LABELS. OPTIONAL says whether the new transition
1526 should be optional. Return the new state. */
1529 add_decision (state
*from
, const rtx_test
&test
, int_set labels
, bool optional
)
1531 state
*to
= new state
;
1532 add_decision (from
, test
, new transition (labels
, to
, optional
));
1536 /* Insert a decision before decisions R to make them dependent on
1537 TEST == LABELS. OPTIONAL says whether the new transition should be
1541 insert_decision_before (state::range r
, const rtx_test
&test
,
1542 const int_set
&labels
, bool optional
)
1544 decision
*newd
= new decision (test
);
1545 state
*news
= new state
;
1546 newd
->push_back (new transition (labels
, news
, optional
));
1547 r
.start
->s
->replace (r
, newd
);
1548 news
->push_back (r
);
1552 /* Remove any optional transitions from S that turned out not to be useful. */
1555 collapse_optional_decisions (state
*s
)
1557 decision
*d
= s
->first
;
1560 decision
*next
= d
->next
;
1561 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1562 collapse_optional_decisions (trans
->to
);
1563 /* A decision with a single optional transition doesn't help
1564 partition the potential matches and so is unlikely to be
1565 worthwhile. In particular, if the decision that performs the
1566 test is the last in the state, the best it could do is reject
1567 an invalid pattern slightly earlier. If instead the decision
1568 is not the last in the state, the condition it tests could hold
1569 even for the later decisions in the state. The best it can do
1570 is save work in some cases where only the later decisions can
1573 In both cases the optional transition would add extra work to
1574 successful matches when the tested condition holds. */
1575 if (transition
*trans
= d
->singleton ())
1576 if (trans
->optional
)
1577 s
->replace (d
, trans
->to
->release ());
1582 /* Try to squash several separate tests into simpler ones. */
1585 simplify_tests (state
*s
)
1587 for (decision
*d
= s
->first
; d
; d
= d
->next
)
1590 /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N
1591 into checks for const_int_rtx[N'], if N is suitably small. */
1592 if (d
->test
.kind
== rtx_test::CODE
1593 && d
->if_statement_p (&label
)
1594 && label
== CONST_INT
)
1595 if (decision
*second
= d
->first
->to
->singleton ())
1596 if (d
->test
.pos
== second
->test
.pos
1597 && second
->test
.kind
== rtx_test::WIDE_INT_FIELD
1598 && second
->test
.u
.opno
== 0
1599 && second
->if_statement_p (&label
)
1600 && IN_RANGE (int64_t (label
),
1601 -MAX_SAVED_CONST_INT
, MAX_SAVED_CONST_INT
))
1603 d
->test
.kind
= rtx_test::SAVED_CONST_INT
;
1604 d
->test
.u
.integer
.is_param
= false;
1605 d
->test
.u
.integer
.value
= label
;
1606 d
->replace (d
->first
, second
->release ());
1607 d
->first
->labels
[0] = true;
1609 /* If we have a CODE test followed by a PREDICATE test, rely on
1610 the predicate to test the code.
1612 This case exists for match_operators. We initially treat the
1613 CODE test for a match_operator as non-optional so that we can
1614 safely move down to its operands. It may turn out that all
1615 paths that reach that code test require the same predicate
1616 to be true. cse_tests will then put the predicate test in
1617 series with the code test. */
1618 if (d
->test
.kind
== rtx_test::CODE
)
1619 if (transition
*trans
= d
->singleton ())
1621 state
*s
= trans
->to
;
1622 while (decision
*d2
= s
->singleton ())
1624 if (d
->test
.pos
!= d2
->test
.pos
)
1626 transition
*trans2
= d2
->singleton ();
1629 if (d2
->test
.kind
== rtx_test::PREDICATE
)
1632 trans
->labels
= int_set (true);
1633 s
->replace (d2
, trans2
->to
->release ());
1639 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1640 simplify_tests (trans
->to
);
1644 /* Return true if all successful returns passing through D require the
1645 condition tested by COMMON to be true.
1647 When returning true, add all transitions like COMMON in D to WHERE.
1648 WHERE may contain a partial result on failure. */
1651 common_test_p (decision
*d
, transition
*common
, vec
<transition
*> *where
)
1653 if (d
->test
.kind
== rtx_test::ACCEPT
)
1654 /* We found a successful return that didn't require COMMON. */
1656 if (d
->test
== common
->from
->test
)
1658 transition
*trans
= d
->singleton ();
1660 || trans
->optional
!= common
->optional
1661 || trans
->labels
!= common
->labels
)
1663 where
->safe_push (trans
);
1666 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1667 for (decision
*subd
= trans
->to
->first
; subd
; subd
= subd
->next
)
1668 if (!common_test_p (subd
, common
, where
))
1673 /* Indicates that we have tested GET_CODE (X) for a particular rtx X. */
1674 const unsigned char TESTED_CODE
= 1;
1676 /* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */
1677 const unsigned char TESTED_VECLEN
= 2;
1679 /* Represents a set of conditions that are known to hold. */
1680 struct known_conditions
1682 /* A mask of TESTED_ values for each position, indexed by the position's
1684 auto_vec
<unsigned char> position_tests
;
1686 /* Index N says whether operands[N] has been set. */
1687 auto_vec
<bool> set_operands
;
1689 /* A guranteed lower bound on the value of peep2_current_count. */
1693 /* Return true if TEST can safely be performed at D, where
1694 the conditions in KC hold. TEST is known to occur along the
1695 first path from D (i.e. always following the first transition
1696 of the first decision). Any intervening tests can be used as
1697 negative proof that hoisting isn't safe, but only KC can be used
1698 as positive proof. */
1701 safe_to_hoist_p (decision
*d
, const rtx_test
&test
, known_conditions
*kc
)
1705 case rtx_test::C_TEST
:
1706 /* In general, C tests require everything else to have been
1707 verified and all operands to have been set up. */
1710 case rtx_test::ACCEPT
:
1711 /* Don't accept something before all conditions have been tested. */
1714 case rtx_test::PREDICATE
:
1715 /* Don't move a predicate over a test for VECLEN_GE, since the
1716 predicate used in a match_parallel can legitimately expect the
1717 length to be checked first. */
1718 for (decision
*subd
= d
;
1720 subd
= subd
->first
->to
->first
)
1721 if (subd
->test
.pos
== test
.pos
1722 && subd
->test
.kind
== rtx_test::VECLEN_GE
)
1726 case rtx_test::DUPLICATE
:
1727 /* Don't test for a match_dup until the associated operand has
1729 if (!kc
->set_operands
[test
.u
.opno
])
1733 case rtx_test::CODE
:
1734 case rtx_test::MODE
:
1735 case rtx_test::SAVED_CONST_INT
:
1736 case rtx_test::SET_OP
:
1738 /* Check whether it is safe to access the rtx under test. */
1739 switch (test
.pos
->type
)
1741 case POS_PEEP2_INSN
:
1742 return test
.pos
->arg
< kc
->peep2_count
;
1745 return kc
->position_tests
[test
.pos
->base
->id
] & TESTED_CODE
;
1748 return kc
->position_tests
[test
.pos
->base
->id
] & TESTED_VECLEN
;
1752 case rtx_test::REGNO_FIELD
:
1753 case rtx_test::INT_FIELD
:
1754 case rtx_test::WIDE_INT_FIELD
:
1755 case rtx_test::VECLEN
:
1756 case rtx_test::VECLEN_GE
:
1757 /* These tests access a specific part of an rtx, so are only safe
1758 once we know what the rtx is. */
1759 return kc
->position_tests
[test
.pos
->id
] & TESTED_CODE
;
1761 case rtx_test::PEEP2_COUNT
:
1762 case rtx_test::HAVE_NUM_CLOBBERS
:
1763 /* These tests can be performed anywhere. */
1766 case rtx_test::PATTERN
:
1772 /* Look for a transition that is taken by all successful returns from a range
1773 of decisions starting at OUTER and that would be better performed by
1774 OUTER's state instead. On success, store all instances of that transition
1775 in WHERE and return the last decision in the range. The range could
1776 just be OUTER, or it could include later decisions as well.
1778 WITH_POSITION_P is true if only tests with position POS should be tried,
1779 false if any test should be tried. WORTHWHILE_SINGLE_P is true if the
1780 result is useful even when the range contains just a single decision
1781 with a single transition. KC are the conditions that are known to
1785 find_common_test (decision
*outer
, bool with_position_p
,
1786 position
*pos
, bool worthwhile_single_p
,
1787 known_conditions
*kc
, vec
<transition
*> *where
)
1789 /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains
1790 just a single decision is useful, regardless of the number of
1791 transitions it has. */
1792 if (!outer
->singleton ())
1793 worthwhile_single_p
= true;
1794 /* Quick exit if we don't have enough decisions to form a worthwhile
1796 if (!worthwhile_single_p
&& !outer
->next
)
1798 /* Follow the first chain down, as one example of a path that needs
1799 to contain the common test. */
1800 for (decision
*d
= outer
; d
; d
= d
->first
->to
->first
)
1802 transition
*trans
= d
->singleton ();
1804 && (!with_position_p
|| d
->test
.pos
== pos
)
1805 && safe_to_hoist_p (outer
, d
->test
, kc
))
1807 if (common_test_p (outer
, trans
, where
))
1810 /* We checked above whether the move is worthwhile. */
1812 /* See how many decisions in OUTER's chain could reuse
1814 decision
*outer_end
= outer
;
1817 unsigned int length
= where
->length ();
1818 if (!common_test_p (outer_end
->next
, trans
, where
))
1820 where
->truncate (length
);
1823 outer_end
= outer_end
->next
;
1825 while (outer_end
->next
);
1826 /* It is worth moving TRANS if it can be shared by more than
1828 if (outer_end
!= outer
|| worthwhile_single_p
)
1831 where
->truncate (0);
1837 /* Try to promote common subtests in S to a single, shared decision.
1838 Also try to bunch tests for the same position together. POS is the
1839 position of the rtx tested before reaching S. KC are the conditions
1840 that are known to hold on entry to S. */
1843 cse_tests (position
*pos
, state
*s
, known_conditions
*kc
)
1845 for (decision
*d
= s
->first
; d
; d
= d
->next
)
1847 auto_vec
<transition
*, 16> where
;
1850 /* Try to find conditions that don't depend on a particular rtx,
1851 such as pnum_clobbers != NULL or peep2_current_count >= X.
1852 It's usually better to check these conditions as soon as
1853 possible, so the change is worthwhile even if there is
1854 only one copy of the test. */
1855 decision
*endd
= find_common_test (d
, true, 0, true, kc
, &where
);
1856 if (!endd
&& d
->test
.pos
!= pos
)
1857 /* Try to find other conditions related to position POS
1858 before moving to the new position. Again, this is
1859 worthwhile even if there is only one copy of the test,
1860 since it means that fewer position variables are live
1862 endd
= find_common_test (d
, true, pos
, true, kc
, &where
);
1864 /* Try to find any condition that is used more than once. */
1865 endd
= find_common_test (d
, false, 0, false, kc
, &where
);
1868 transition
*common
= where
[0];
1869 /* Replace [D, ENDD] with a test like COMMON. We'll recurse
1870 on the common test and see the original D again next time. */
1871 d
= insert_decision_before (state::range (d
, endd
),
1875 /* Remove the old tests. */
1876 while (!where
.is_empty ())
1878 transition
*trans
= where
.pop ();
1879 trans
->from
->s
->replace (trans
->from
, trans
->to
->release ());
1884 /* Make sure that safe_to_hoist_p isn't being overly conservative.
1885 It should realize that D's test is safe in the current
1887 gcc_assert (d
->test
.kind
== rtx_test::C_TEST
1888 || d
->test
.kind
== rtx_test::ACCEPT
1889 || safe_to_hoist_p (d
, d
->test
, kc
));
1891 /* D won't be changed any further by the current optimization.
1892 Recurse with the state temporarily updated to include D. */
1894 switch (d
->test
.kind
)
1896 case rtx_test::CODE
:
1897 prev
= kc
->position_tests
[d
->test
.pos
->id
];
1898 kc
->position_tests
[d
->test
.pos
->id
] |= TESTED_CODE
;
1901 case rtx_test::VECLEN
:
1902 case rtx_test::VECLEN_GE
:
1903 prev
= kc
->position_tests
[d
->test
.pos
->id
];
1904 kc
->position_tests
[d
->test
.pos
->id
] |= TESTED_VECLEN
;
1907 case rtx_test::SET_OP
:
1908 prev
= kc
->set_operands
[d
->test
.u
.opno
];
1910 kc
->set_operands
[d
->test
.u
.opno
] = true;
1913 case rtx_test::PEEP2_COUNT
:
1914 prev
= kc
->peep2_count
;
1915 kc
->peep2_count
= MAX (prev
, d
->test
.u
.min_len
);
1921 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1922 cse_tests (d
->test
.pos
? d
->test
.pos
: pos
, trans
->to
, kc
);
1923 switch (d
->test
.kind
)
1925 case rtx_test::CODE
:
1926 case rtx_test::VECLEN
:
1927 case rtx_test::VECLEN_GE
:
1928 kc
->position_tests
[d
->test
.pos
->id
] = prev
;
1931 case rtx_test::SET_OP
:
1932 kc
->set_operands
[d
->test
.u
.opno
] = prev
;
1935 case rtx_test::PEEP2_COUNT
:
1936 kc
->peep2_count
= prev
;
1945 /* Return the type of value that can be used to parameterize test KIND,
1946 or parameter::UNSET if none. */
1948 parameter::type_enum
1949 transition_parameter_type (rtx_test::kind_enum kind
)
1953 case rtx_test::CODE
:
1954 return parameter::CODE
;
1956 case rtx_test::MODE
:
1957 return parameter::MODE
;
1959 case rtx_test::REGNO_FIELD
:
1960 return parameter::UINT
;
1962 case rtx_test::INT_FIELD
:
1963 case rtx_test::VECLEN
:
1964 case rtx_test::PATTERN
:
1965 return parameter::INT
;
1967 case rtx_test::WIDE_INT_FIELD
:
1968 return parameter::WIDE_INT
;
1970 case rtx_test::PEEP2_COUNT
:
1971 case rtx_test::VECLEN_GE
:
1972 case rtx_test::SAVED_CONST_INT
:
1973 case rtx_test::PREDICATE
:
1974 case rtx_test::DUPLICATE
:
1975 case rtx_test::HAVE_NUM_CLOBBERS
:
1976 case rtx_test::C_TEST
:
1977 case rtx_test::SET_OP
:
1978 case rtx_test::ACCEPT
:
1979 return parameter::UNSET
;
1984 /* Initialize the pos_operand fields of each state reachable from S.
1985 If OPERAND_POS[ID] >= 0, the position with id ID is stored in
1986 operands[OPERAND_POS[ID]] on entry to S. */
1989 find_operand_positions (state
*s
, vec
<int> &operand_pos
)
1991 for (decision
*d
= s
->first
; d
; d
= d
->next
)
1993 int this_operand
= (d
->test
.pos
? operand_pos
[d
->test
.pos
->id
] : -1);
1994 if (this_operand
>= 0)
1995 d
->test
.pos_operand
= this_operand
;
1996 if (d
->test
.kind
== rtx_test::SET_OP
)
1997 operand_pos
[d
->test
.pos
->id
] = d
->test
.u
.opno
;
1998 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1999 find_operand_positions (trans
->to
, operand_pos
);
2000 if (d
->test
.kind
== rtx_test::SET_OP
)
2001 operand_pos
[d
->test
.pos
->id
] = this_operand
;
2005 /* Statistics about a matching routine. */
2010 /* The total number of decisions in the routine, excluding trivial
2011 ones that never fail. */
2012 unsigned int num_decisions
;
2014 /* The number of non-trivial decisions on the longest path through
2015 the routine, and the return value that contributes most to that
2017 unsigned int longest_path
;
2018 int longest_path_code
;
2020 /* The maximum number of times that a single call to the routine
2021 can backtrack, and the value returned at the end of that path.
2022 "Backtracking" here means failing one decision in state and
2023 going onto to the next. */
2024 unsigned int longest_backtrack
;
2025 int longest_backtrack_code
;
2029 : num_decisions (0), longest_path (0), longest_path_code (-1),
2030 longest_backtrack (0), longest_backtrack_code (-1) {}
2032 /* Return statistics about S. */
2035 get_stats (state
*s
)
2038 unsigned int longest_path
= 0;
2039 for (decision
*d
= s
->first
; d
; d
= d
->next
)
2041 /* Work out the statistics for D. */
2043 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
2045 stats for_trans
= get_stats (trans
->to
);
2046 for_d
.num_decisions
+= for_trans
.num_decisions
;
2047 /* Each transition is mutually-exclusive, so just pick the
2048 longest of the individual paths. */
2049 if (for_d
.longest_path
<= for_trans
.longest_path
)
2051 for_d
.longest_path
= for_trans
.longest_path
;
2052 for_d
.longest_path_code
= for_trans
.longest_path_code
;
2054 /* Likewise for backtracking. */
2055 if (for_d
.longest_backtrack
<= for_trans
.longest_backtrack
)
2057 for_d
.longest_backtrack
= for_trans
.longest_backtrack
;
2058 for_d
.longest_backtrack_code
= for_trans
.longest_backtrack_code
;
2062 /* Account for D's test in its statistics. */
2063 if (!d
->test
.single_outcome_p ())
2065 for_d
.num_decisions
+= 1;
2066 for_d
.longest_path
+= 1;
2068 if (d
->test
.kind
== rtx_test::ACCEPT
)
2070 for_d
.longest_path_code
= d
->test
.u
.acceptance
.u
.full
.code
;
2071 for_d
.longest_backtrack_code
= d
->test
.u
.acceptance
.u
.full
.code
;
2074 /* Keep a running count of the number of backtracks. */
2076 for_s
.longest_backtrack
+= 1;
2078 /* Accumulate D's statistics into S's. */
2079 for_s
.num_decisions
+= for_d
.num_decisions
;
2080 for_s
.longest_path
+= for_d
.longest_path
;
2081 for_s
.longest_backtrack
+= for_d
.longest_backtrack
;
2083 /* Use the code from the decision with the longest individual path,
2084 since that's more likely to be useful if trying to make the
2085 path shorter. In the event of a tie, pick the later decision,
2086 since that's closer to the end of the path. */
2087 if (longest_path
<= for_d
.longest_path
)
2089 longest_path
= for_d
.longest_path
;
2090 for_s
.longest_path_code
= for_d
.longest_path_code
;
2093 /* Later decisions in a state are necessarily in a longer backtrack
2094 than earlier decisions. */
2095 for_s
.longest_backtrack_code
= for_d
.longest_backtrack_code
;
2100 /* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
2103 optimize_subroutine_group (const char *type
, state
*root
)
2105 /* Remove optional transitions that turned out not to be worthwhile. */
2106 if (collapse_optional_decisions_p
)
2107 collapse_optional_decisions (root
);
2109 /* Try to remove duplicated tests and to rearrange tests into a more
2113 known_conditions kc
;
2114 kc
.position_tests
.safe_grow_cleared (num_positions
);
2115 kc
.set_operands
.safe_grow_cleared (num_operands
);
2117 cse_tests (&root_pos
, root
, &kc
);
2120 /* Try to simplify two or more tests into one. */
2121 if (simplify_tests_p
)
2122 simplify_tests (root
);
2124 /* Try to use operands[] instead of xN variables. */
2125 if (use_operand_variables_p
)
2127 auto_vec
<int> operand_pos (num_positions
);
2128 for (unsigned int i
= 0; i
< num_positions
; ++i
)
2129 operand_pos
.quick_push (-1);
2130 find_operand_positions (root
, operand_pos
);
2133 /* Print a summary of the new state. */
2134 stats st
= get_stats (root
);
2135 fprintf (stderr
, "Statistics for %s:\n", type
);
2136 fprintf (stderr
, " Number of decisions: %6d\n", st
.num_decisions
);
2137 fprintf (stderr
, " longest path: %6d (code: %6d)\n",
2138 st
.longest_path
, st
.longest_path_code
);
2139 fprintf (stderr
, " longest backtrack: %6d (code: %6d)\n",
2140 st
.longest_backtrack
, st
.longest_backtrack_code
);
2143 struct merge_pattern_info
;
2145 /* Represents a transition from one pattern to another. */
2146 struct merge_pattern_transition
2148 merge_pattern_transition (merge_pattern_info
*);
2150 /* The target pattern. */
2151 merge_pattern_info
*to
;
2153 /* The parameters that the source pattern passes to the target pattern.
2154 "parameter (TYPE, true, I)" represents parameter I of the source
2156 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
2159 merge_pattern_transition::merge_pattern_transition (merge_pattern_info
*to_in
)
2164 /* Represents a pattern that can might match several states. The pattern
2165 may replace parts of the test with a parameter value. It may also
2166 replace transition labels with parameters. */
2167 struct merge_pattern_info
2169 merge_pattern_info (unsigned int);
2171 /* If PARAM_TEST_P, the state's singleton test should be generalized
2172 to use the runtime value of PARAMS[PARAM_TEST]. */
2173 unsigned int param_test
: 8;
2175 /* If PARAM_TRANSITION_P, the state's single transition label should
2176 be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */
2177 unsigned int param_transition
: 8;
2179 /* True if we have decided to generalize the root decision's test,
2180 as per PARAM_TEST. */
2181 unsigned int param_test_p
: 1;
2183 /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
2184 unsigned int param_transition_p
: 1;
2186 /* True if the contents of the structure are completely filled in. */
2187 unsigned int complete_p
: 1;
2189 /* The number of pseudo-statements in the pattern. Used to decide
2190 whether it's big enough to break out into a subroutine. */
2191 unsigned int num_statements
;
2193 /* The number of states that use this pattern. */
2194 unsigned int num_users
;
2196 /* The number of distinct success values that the pattern returns. */
2197 unsigned int num_results
;
2199 /* This array has one element for each runtime parameter to the pattern.
2200 PARAMS[I] gives the default value of parameter I, which is always
2203 These default parameters are used in cases where we match the
2204 pattern against some state S1, then add more parameters while
2205 matching against some state S2. S1 is then left passing fewer
2206 parameters than S2. The array gives us enough informatino to
2207 construct a full parameter list for S1 (see update_parameters).
2209 If we decide to create a subroutine for this pattern,
2210 PARAMS[I].type determines the C type of parameter I. */
2211 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
2213 /* All states that match this pattern must have the same number of
2214 transitions. TRANSITIONS[I] describes the subpattern for transition
2215 number I; it is null if transition I represents a successful return
2216 from the pattern. */
2217 auto_vec
<merge_pattern_transition
*, 1> transitions
;
2219 /* The routine associated with the pattern, or null if we haven't generated
2221 pattern_routine
*routine
;
2224 merge_pattern_info::merge_pattern_info (unsigned int num_transitions
)
2226 param_transition (0),
2227 param_test_p (false),
2228 param_transition_p (false),
2235 transitions
.safe_grow_cleared (num_transitions
);
2238 /* Describes one way of matching a particular state to a particular
2240 struct merge_state_result
2242 merge_state_result (merge_pattern_info
*, position
*, merge_state_result
*);
2244 /* A pattern that matches the state. */
2245 merge_pattern_info
*pattern
;
2247 /* If we decide to use this match and create a subroutine for PATTERN,
2248 the state should pass the rtx at position ROOT to the pattern's
2249 rtx parameter. A null root means that the pattern doesn't need
2250 an rtx parameter; all the rtxes it matches come from elsewhere. */
2253 /* The parameters that should be passed to PATTERN for this state.
2254 If the array is shorter than PATTERN->params, the missing entries
2255 should be taken from the corresponding element of PATTERN->params. */
2256 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
2258 /* An earlier match for the same state, or null if none. Patterns
2259 matched by earlier entries are smaller than PATTERN. */
2260 merge_state_result
*prev
;
2263 merge_state_result::merge_state_result (merge_pattern_info
*pattern_in
,
2265 merge_state_result
*prev_in
)
2266 : pattern (pattern_in
), root (root_in
), prev (prev_in
)
2269 /* Information about a state, used while trying to match it against
2271 struct merge_state_info
2273 merge_state_info (state
*);
2275 /* The state itself. */
2278 /* Index I gives information about the target of transition I. */
2279 merge_state_info
*to_states
;
2281 /* The number of transitions in S. */
2282 unsigned int num_transitions
;
2284 /* True if the state has been deleted in favor of a call to a
2288 /* The previous state that might be a merge candidate for S, or null
2289 if no previous states could be merged with S. */
2290 merge_state_info
*prev_same_test
;
2292 /* A list of pattern matches for this state. */
2293 merge_state_result
*res
;
2296 merge_state_info::merge_state_info (state
*s_in
)
2299 num_transitions (0),
2304 /* True if PAT would be useful as a subroutine. */
2307 useful_pattern_p (merge_pattern_info
*pat
)
2309 return pat
->num_statements
>= MIN_COMBINE_COST
;
2312 /* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
2313 into PAT1's C routine. */
2316 same_pattern_p (merge_pattern_info
*pat1
, merge_pattern_info
*pat2
)
2318 return pat1
->num_users
== pat2
->num_users
|| !useful_pattern_p (pat2
);
2321 /* PAT was previously matched against SINFO based on tentative matches
2322 for the target states of SINFO's state. Return true if the match
2323 still holds; that is, if the target states of SINFO's state still
2324 match the corresponding transitions of PAT. */
2327 valid_result_p (merge_pattern_info
*pat
, merge_state_info
*sinfo
)
2329 for (unsigned int j
= 0; j
< sinfo
->num_transitions
; ++j
)
2330 if (merge_pattern_transition
*ptrans
= pat
->transitions
[j
])
2332 merge_state_result
*to_res
= sinfo
->to_states
[j
].res
;
2333 if (!to_res
|| to_res
->pattern
!= ptrans
->to
)
2339 /* Remove any matches that are no longer valid from the head of SINFO's
2343 prune_invalid_results (merge_state_info
*sinfo
)
2345 while (sinfo
->res
&& !valid_result_p (sinfo
->res
->pattern
, sinfo
))
2347 sinfo
->res
= sinfo
->res
->prev
;
2348 gcc_assert (sinfo
->res
);
2352 /* Return true if PAT represents the biggest posssible match for SINFO;
2353 that is, if the next action of SINFO's state on return from PAT will
2354 be something that cannot be merged with any other state. */
2357 complete_result_p (merge_pattern_info
*pat
, merge_state_info
*sinfo
)
2359 for (unsigned int j
= 0; j
< sinfo
->num_transitions
; ++j
)
2360 if (sinfo
->to_states
[j
].res
&& !pat
->transitions
[j
])
2365 /* Update TO for any parameters that have been added to FROM since TO
2366 was last set. The extra parameters in FROM will be constants or
2367 instructions to duplicate earlier parameters. */
2370 update_parameters (vec
<parameter
> &to
, const vec
<parameter
> &from
)
2372 for (unsigned int i
= to
.length (); i
< from
.length (); ++i
)
2373 to
.quick_push (from
[i
]);
2376 /* Return true if A and B can be tested by a single test. If the test
2377 can be parameterised, store the parameter value for A in *PARAMA and
2378 the parameter value for B in *PARAMB, otherwise leave PARAMA and
2382 compatible_tests_p (const rtx_test
&a
, const rtx_test
&b
,
2383 parameter
*parama
, parameter
*paramb
)
2385 if (a
.kind
!= b
.kind
)
2389 case rtx_test::PREDICATE
:
2390 if (a
.u
.predicate
.data
!= b
.u
.predicate
.data
)
2392 *parama
= parameter (parameter::MODE
, false, a
.u
.predicate
.mode
);
2393 *paramb
= parameter (parameter::MODE
, false, b
.u
.predicate
.mode
);
2396 case rtx_test::SAVED_CONST_INT
:
2397 *parama
= parameter (parameter::INT
, false, a
.u
.integer
.value
);
2398 *paramb
= parameter (parameter::INT
, false, b
.u
.integer
.value
);
2406 /* PARAMS is an array of the parameters that a state is going to pass
2407 to a pattern routine. It is still incomplete; index I has a kind of
2408 parameter::UNSET if we don't yet know what the state will pass
2409 as parameter I. Try to make parameter ID equal VALUE, returning
2413 set_parameter (vec
<parameter
> ¶ms
, unsigned int id
,
2414 const parameter
&value
)
2416 if (params
[id
].type
== parameter::UNSET
)
2418 if (force_unique_params_p
)
2419 for (unsigned int i
= 0; i
< params
.length (); ++i
)
2420 if (params
[i
] == value
)
2425 return params
[id
] == value
;
2428 /* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
2429 set of parameters that a particular state is going to pass to
2432 Try to extend PARAMS1 and PARAMS2 so that there is a parameter
2433 that is equal to PARAM1 for the state and has a default value of
2434 PARAM2. Parameters beginning at START were added as part of the
2435 same match and so may be reused. */
2438 add_parameter (vec
<parameter
> ¶ms1
, vec
<parameter
> ¶ms2
,
2439 const parameter
¶m1
, const parameter
¶m2
,
2440 unsigned int start
, unsigned int *res
)
2442 gcc_assert (params1
.length () == params2
.length ());
2443 gcc_assert (!param1
.is_param
&& !param2
.is_param
);
2445 for (unsigned int i
= start
; i
< params2
.length (); ++i
)
2446 if (params1
[i
] == param1
&& params2
[i
] == param2
)
2452 if (force_unique_params_p
)
2453 for (unsigned int i
= 0; i
< params2
.length (); ++i
)
2454 if (params1
[i
] == param1
|| params2
[i
] == param2
)
2457 if (params2
.length () >= MAX_PATTERN_PARAMS
)
2460 *res
= params2
.length ();
2461 params1
.quick_push (param1
);
2462 params2
.quick_push (param2
);
2466 /* If *ROOTA is nonnull, return true if the same sequence of steps are
2467 required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA
2468 is null, update it if necessary in order to make the condition hold. */
2471 merge_relative_positions (position
**roota
, position
*a
,
2472 position
*rootb
, position
*b
)
2474 if (!relative_patterns_p
)
2483 return *roota
== rootb
;
2485 /* If B does not belong to the same instruction as ROOTB, we don't
2486 start with ROOTB but instead start with a call to peep2_next_insn.
2487 In that case the sequences for B and A are identical iff B and A
2488 are themselves identical. */
2489 if (rootb
->insn_id
!= b
->insn_id
)
2493 if (!a
|| b
->type
!= a
->type
|| b
->arg
!= a
->arg
)
2503 /* A hasher of states that treats two states as "equal" if they might be
2504 merged (but trying to be more discriminating than "return true"). */
2505 struct test_pattern_hasher
: nofree_ptr_hash
<merge_state_info
>
2507 static inline hashval_t
hash (const value_type
&);
2508 static inline bool equal (const value_type
&, const compare_type
&);
2512 test_pattern_hasher::hash (merge_state_info
*const &sinfo
)
2515 decision
*d
= sinfo
->s
->singleton ();
2516 h
.add_int (d
->test
.pos_operand
+ 1);
2517 if (!relative_patterns_p
)
2518 h
.add_int (d
->test
.pos
? d
->test
.pos
->id
+ 1 : 0);
2519 h
.add_int (d
->test
.kind
);
2520 h
.add_int (sinfo
->num_transitions
);
2525 test_pattern_hasher::equal (merge_state_info
*const &sinfo1
,
2526 merge_state_info
*const &sinfo2
)
2528 decision
*d1
= sinfo1
->s
->singleton ();
2529 decision
*d2
= sinfo2
->s
->singleton ();
2530 gcc_assert (d1
&& d2
);
2532 parameter new_param1
, new_param2
;
2533 return (d1
->test
.pos_operand
== d2
->test
.pos_operand
2534 && (relative_patterns_p
|| d1
->test
.pos
== d2
->test
.pos
)
2535 && compatible_tests_p (d1
->test
, d2
->test
, &new_param1
, &new_param2
)
2536 && sinfo1
->num_transitions
== sinfo2
->num_transitions
);
2539 /* Try to make the state described by SINFO1 use the same pattern as the
2540 state described by SINFO2. Return true on success.
2542 SINFO1 and SINFO2 are known to have the same hash value. */
2545 merge_patterns (merge_state_info
*sinfo1
, merge_state_info
*sinfo2
)
2547 merge_state_result
*res2
= sinfo2
->res
;
2548 merge_pattern_info
*pat
= res2
->pattern
;
2550 /* Write to temporary arrays while matching, in case we have to abort
2551 half way through. */
2552 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params1
;
2553 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params2
;
2554 params1
.quick_grow_cleared (pat
->params
.length ());
2555 params2
.splice (pat
->params
);
2556 unsigned int start_param
= params2
.length ();
2558 /* An array for recording changes to PAT->transitions[?].params.
2559 All changes involve replacing a constant parameter with some
2560 PAT->params[N], where N is the second element of the pending_param. */
2561 typedef std::pair
<parameter
*, unsigned int> pending_param
;
2562 auto_vec
<pending_param
, 32> pending_params
;
2564 decision
*d1
= sinfo1
->s
->singleton ();
2565 decision
*d2
= sinfo2
->s
->singleton ();
2566 gcc_assert (d1
&& d2
);
2568 /* If D2 tests a position, SINFO1's root relative to D1 is the same
2569 as SINFO2's root relative to D2. */
2570 position
*root1
= 0;
2571 position
*root2
= res2
->root
;
2572 if (d2
->test
.pos_operand
< 0
2574 && !merge_relative_positions (&root1
, d1
->test
.pos
,
2575 root2
, d2
->test
.pos
))
2578 /* Check whether the patterns have the same shape. */
2579 unsigned int num_transitions
= sinfo1
->num_transitions
;
2580 gcc_assert (num_transitions
== sinfo2
->num_transitions
);
2581 for (unsigned int i
= 0; i
< num_transitions
; ++i
)
2582 if (merge_pattern_transition
*ptrans
= pat
->transitions
[i
])
2584 merge_state_result
*to1_res
= sinfo1
->to_states
[i
].res
;
2585 merge_state_result
*to2_res
= sinfo2
->to_states
[i
].res
;
2586 merge_pattern_info
*to_pat
= ptrans
->to
;
2587 gcc_assert (to2_res
&& to2_res
->pattern
== to_pat
);
2588 if (!to1_res
|| to1_res
->pattern
!= to_pat
)
2591 && !merge_relative_positions (&root1
, to1_res
->root
,
2592 root2
, to2_res
->root
))
2594 /* Match the parameters that TO1_RES passes to TO_PAT with the
2595 parameters that PAT passes to TO_PAT. */
2596 update_parameters (to1_res
->params
, to_pat
->params
);
2597 for (unsigned int j
= 0; j
< to1_res
->params
.length (); ++j
)
2599 const parameter
¶m1
= to1_res
->params
[j
];
2600 const parameter
¶m2
= ptrans
->params
[j
];
2601 gcc_assert (!param1
.is_param
);
2602 if (param2
.is_param
)
2604 if (!set_parameter (params1
, param2
.value
, param1
))
2607 else if (param1
!= param2
)
2610 if (!add_parameter (params1
, params2
,
2611 param1
, param2
, start_param
, &id
))
2613 /* Record that PAT should now pass parameter ID to TO_PAT,
2614 instead of the current contents of *PARAM2. We only
2615 make the change if the rest of the match succeeds. */
2616 pending_params
.safe_push
2617 (pending_param (&ptrans
->params
[j
], id
));
2622 unsigned int param_test
= pat
->param_test
;
2623 unsigned int param_transition
= pat
->param_transition
;
2624 bool param_test_p
= pat
->param_test_p
;
2625 bool param_transition_p
= pat
->param_transition_p
;
2627 /* If the tests don't match exactly, try to parameterize them. */
2628 parameter new_param1
, new_param2
;
2629 if (!compatible_tests_p (d1
->test
, d2
->test
, &new_param1
, &new_param2
))
2631 if (new_param1
.type
!= parameter::UNSET
)
2633 /* If the test has not already been parameterized, all existing
2634 matches use constant NEW_PARAM2. */
2637 if (!set_parameter (params1
, param_test
, new_param1
))
2640 else if (new_param1
!= new_param2
)
2642 if (!add_parameter (params1
, params2
, new_param1
, new_param2
,
2643 start_param
, ¶m_test
))
2645 param_test_p
= true;
2649 /* Match the transitions. */
2650 transition
*trans1
= d1
->first
;
2651 transition
*trans2
= d2
->first
;
2652 for (unsigned int i
= 0; i
< num_transitions
; ++i
)
2654 if (param_transition_p
|| trans1
->labels
!= trans2
->labels
)
2656 /* We can only generalize a single transition with a single
2658 if (num_transitions
!= 1
2659 || trans1
->labels
.length () != 1
2660 || trans2
->labels
.length () != 1)
2663 /* Although we can match wide-int fields, in practice it leads
2664 to some odd results for const_vectors. We end up
2665 parameterizing the first N const_ints of the vector
2666 and then (once we reach the maximum number of parameters)
2667 we go on to match the other elements exactly. */
2668 if (d1
->test
.kind
== rtx_test::WIDE_INT_FIELD
)
2671 /* See whether the label has a generalizable type. */
2672 parameter::type_enum param_type
2673 = transition_parameter_type (d1
->test
.kind
);
2674 if (param_type
== parameter::UNSET
)
2677 /* Match the labels using parameters. */
2678 new_param1
= parameter (param_type
, false, trans1
->labels
[0]);
2679 if (param_transition_p
)
2681 if (!set_parameter (params1
, param_transition
, new_param1
))
2686 new_param2
= parameter (param_type
, false, trans2
->labels
[0]);
2687 if (!add_parameter (params1
, params2
, new_param1
, new_param2
,
2688 start_param
, ¶m_transition
))
2690 param_transition_p
= true;
2693 trans1
= trans1
->next
;
2694 trans2
= trans2
->next
;
2697 /* Set any unset parameters to their default values. This occurs if some
2698 other state needed something to be parameterized in order to match SINFO2,
2699 but SINFO1 on its own does not. */
2700 for (unsigned int i
= 0; i
< params1
.length (); ++i
)
2701 if (params1
[i
].type
== parameter::UNSET
)
2702 params1
[i
] = params2
[i
];
2704 /* The match was successful. Commit all pending changes to PAT. */
2705 update_parameters (pat
->params
, params2
);
2709 FOR_EACH_VEC_ELT (pending_params
, i
, pp
)
2710 *pp
->first
= parameter (pp
->first
->type
, true, pp
->second
);
2712 pat
->param_test
= param_test
;
2713 pat
->param_transition
= param_transition
;
2714 pat
->param_test_p
= param_test_p
;
2715 pat
->param_transition_p
= param_transition_p
;
2717 /* Record the match of SINFO1. */
2718 merge_state_result
*new_res1
= new merge_state_result (pat
, root1
,
2720 new_res1
->params
.splice (params1
);
2721 sinfo1
->res
= new_res1
;
2725 /* The number of states that were removed by calling pattern routines. */
2726 static unsigned int pattern_use_states
;
2728 /* The number of states used while defining pattern routines. */
2729 static unsigned int pattern_def_states
;
2731 /* Information used while constructing a use or definition of a pattern
2733 struct create_pattern_info
2735 /* The routine itself. */
2736 pattern_routine
*routine
;
2738 /* The first unclaimed return value for this particular use or definition.
2739 We walk the substates of uses and definitions in the same order
2740 so each return value always refers to the same position within
2742 unsigned int next_result
;
2745 static void populate_pattern_routine (create_pattern_info
*,
2746 merge_state_info
*, state
*,
2747 const vec
<parameter
> &);
2749 /* SINFO matches a pattern for which we've decided to create a C routine.
2750 Return a decision that performs a call to the pattern routine,
2751 but leave the caller to add the transitions to it. Initialize CPI
2752 for this purpose. Also create a definition for the pattern routine,
2753 if it doesn't already have one.
2755 PARAMS are the parameters that SINFO passes to its pattern. */
2758 init_pattern_use (create_pattern_info
*cpi
, merge_state_info
*sinfo
,
2759 const vec
<parameter
> ¶ms
)
2761 state
*s
= sinfo
->s
;
2762 merge_state_result
*res
= sinfo
->res
;
2763 merge_pattern_info
*pat
= res
->pattern
;
2764 cpi
->routine
= pat
->routine
;
2767 /* We haven't defined the pattern routine yet, so create
2768 a definition now. */
2769 pattern_routine
*routine
= new pattern_routine
;
2770 pat
->routine
= routine
;
2771 cpi
->routine
= routine
;
2772 routine
->s
= new state
;
2773 routine
->insn_p
= false;
2774 routine
->pnum_clobbers_p
= false;
2776 /* Create an "idempotent" mapping of parameter I to parameter I.
2777 Also record the C type of each parameter to the routine. */
2778 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> def_params
;
2779 for (unsigned int i
= 0; i
< pat
->params
.length (); ++i
)
2781 def_params
.quick_push (parameter (pat
->params
[i
].type
, true, i
));
2782 routine
->param_types
.quick_push (pat
->params
[i
].type
);
2785 /* Any of the states that match the pattern could be used to
2786 create the routine definition. We might as well use SINFO
2787 since it's already to hand. This means that all positions
2788 in the definition will be relative to RES->root. */
2789 routine
->pos
= res
->root
;
2790 cpi
->next_result
= 0;
2791 populate_pattern_routine (cpi
, sinfo
, routine
->s
, def_params
);
2792 gcc_assert (cpi
->next_result
== pat
->num_results
);
2794 /* Add the routine to the global list, after the subroutines
2796 routine
->pattern_id
= patterns
.length ();
2797 patterns
.safe_push (routine
);
2800 /* Create a decision to call the routine, passing PARAMS to it. */
2801 pattern_use
*use
= new pattern_use
;
2802 use
->routine
= pat
->routine
;
2803 use
->params
.splice (params
);
2804 decision
*d
= new decision (rtx_test::pattern (res
->root
, use
));
2806 /* If the original decision could use an element of operands[] instead
2807 of an rtx variable, try to transfer it to the new decision. */
2808 if (s
->first
->test
.pos
&& res
->root
== s
->first
->test
.pos
)
2809 d
->test
.pos_operand
= s
->first
->test
.pos_operand
;
2811 cpi
->next_result
= 0;
2815 /* Make S return the next unclaimed pattern routine result for CPI. */
2818 add_pattern_acceptance (create_pattern_info
*cpi
, state
*s
)
2820 acceptance_type acceptance
;
2821 acceptance
.type
= SUBPATTERN
;
2822 acceptance
.partial_p
= false;
2823 acceptance
.u
.full
.code
= cpi
->next_result
;
2824 add_decision (s
, rtx_test::accept (acceptance
), true, false);
2825 cpi
->next_result
+= 1;
2828 /* Initialize new empty state NEWS so that it implements SINFO's pattern
2829 (here referred to as "P"). P may be the top level of a pattern routine
2830 or a subpattern that should be inlined into its parent pattern's routine
2831 (as per same_pattern_p). The choice of SINFO for a top-level pattern is
2832 arbitrary; it could be any of the states that use P. The choice for
2833 subpatterns follows the choice for the parent pattern.
2835 PARAMS gives the value of each parameter to P in terms of the parameters
2836 to the top-level pattern. If P itself is the top level pattern, PARAMS[I]
2837 is always "parameter (TYPE, true, I)". */
2840 populate_pattern_routine (create_pattern_info
*cpi
, merge_state_info
*sinfo
,
2841 state
*news
, const vec
<parameter
> ¶ms
)
2843 pattern_def_states
+= 1;
2845 decision
*d
= sinfo
->s
->singleton ();
2846 merge_pattern_info
*pat
= sinfo
->res
->pattern
;
2847 pattern_routine
*routine
= cpi
->routine
;
2849 /* Create a copy of D's test for the pattern routine and generalize it
2851 decision
*newd
= new decision (d
->test
);
2852 gcc_assert (newd
->test
.pos_operand
>= 0
2854 || common_position (newd
->test
.pos
,
2855 routine
->pos
) == routine
->pos
);
2856 if (pat
->param_test_p
)
2858 const parameter
¶m
= params
[pat
->param_test
];
2859 switch (newd
->test
.kind
)
2861 case rtx_test::PREDICATE
:
2862 newd
->test
.u
.predicate
.mode_is_param
= param
.is_param
;
2863 newd
->test
.u
.predicate
.mode
= param
.value
;
2866 case rtx_test::SAVED_CONST_INT
:
2867 newd
->test
.u
.integer
.is_param
= param
.is_param
;
2868 newd
->test
.u
.integer
.value
= param
.value
;
2876 if (d
->test
.kind
== rtx_test::C_TEST
)
2877 routine
->insn_p
= true;
2878 else if (d
->test
.kind
== rtx_test::HAVE_NUM_CLOBBERS
)
2879 routine
->pnum_clobbers_p
= true;
2880 news
->push_back (newd
);
2882 /* Fill in the transitions of NEWD. */
2884 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
2886 /* Create a new state to act as the target of the new transition. */
2887 state
*to_news
= new state
;
2888 if (merge_pattern_transition
*ptrans
= pat
->transitions
[i
])
2890 /* The pattern hasn't finished matching yet. Get the target
2891 pattern and the corresponding target state of SINFO. */
2892 merge_pattern_info
*to_pat
= ptrans
->to
;
2893 merge_state_info
*to
= sinfo
->to_states
+ i
;
2894 gcc_assert (to
->res
->pattern
== to_pat
);
2895 gcc_assert (ptrans
->params
.length () == to_pat
->params
.length ());
2897 /* Express the parameters to TO_PAT in terms of the parameters
2898 to the top-level pattern. */
2899 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> to_params
;
2900 for (unsigned int j
= 0; j
< ptrans
->params
.length (); ++j
)
2902 const parameter
¶m
= ptrans
->params
[j
];
2903 to_params
.quick_push (param
.is_param
2904 ? params
[param
.value
]
2908 if (same_pattern_p (pat
, to_pat
))
2909 /* TO_PAT is part of the current routine, so just recurse. */
2910 populate_pattern_routine (cpi
, to
, to_news
, to_params
);
2913 /* TO_PAT should be matched by calling a separate routine. */
2914 create_pattern_info sub_cpi
;
2915 decision
*subd
= init_pattern_use (&sub_cpi
, to
, to_params
);
2916 routine
->insn_p
|= sub_cpi
.routine
->insn_p
;
2917 routine
->pnum_clobbers_p
|= sub_cpi
.routine
->pnum_clobbers_p
;
2919 /* Add the pattern routine call to the new target state. */
2920 to_news
->push_back (subd
);
2922 /* Add a transition for each successful call result. */
2923 for (unsigned int j
= 0; j
< to_pat
->num_results
; ++j
)
2925 state
*res
= new state
;
2926 add_pattern_acceptance (cpi
, res
);
2927 subd
->push_back (new transition (j
, res
, false));
2932 /* This transition corresponds to a successful match. */
2933 add_pattern_acceptance (cpi
, to_news
);
2935 /* Create the transition itself, generalizing as necessary. */
2936 transition
*new_trans
= new transition (trans
->labels
, to_news
,
2938 if (pat
->param_transition_p
)
2940 const parameter
¶m
= params
[pat
->param_transition
];
2941 new_trans
->is_param
= param
.is_param
;
2942 new_trans
->labels
[0] = param
.value
;
2944 newd
->push_back (new_trans
);
2949 /* USE is a decision that calls a pattern routine and SINFO is part of the
2950 original state tree that the call is supposed to replace. Add the
2951 transitions for SINFO and its substates to USE. */
2954 populate_pattern_use (create_pattern_info
*cpi
, decision
*use
,
2955 merge_state_info
*sinfo
)
2957 pattern_use_states
+= 1;
2958 gcc_assert (!sinfo
->merged_p
);
2959 sinfo
->merged_p
= true;
2960 merge_state_result
*res
= sinfo
->res
;
2961 merge_pattern_info
*pat
= res
->pattern
;
2962 decision
*d
= sinfo
->s
->singleton ();
2964 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
2966 if (pat
->transitions
[i
])
2967 /* The target state is also part of the pattern. */
2968 populate_pattern_use (cpi
, use
, sinfo
->to_states
+ i
);
2971 /* The transition corresponds to a successful return from the
2973 use
->push_back (new transition (cpi
->next_result
, trans
->to
, false));
2974 cpi
->next_result
+= 1;
2980 /* We have decided to replace SINFO's state with a call to a pattern
2981 routine. Make the change, creating a definition of the pattern routine
2982 if it doesn't have one already. */
2985 use_pattern (merge_state_info
*sinfo
)
2987 merge_state_result
*res
= sinfo
->res
;
2988 merge_pattern_info
*pat
= res
->pattern
;
2989 state
*s
= sinfo
->s
;
2991 /* The pattern may have acquired new parameters after it was matched
2992 against SINFO. Update the parameters that SINFO passes accordingly. */
2993 update_parameters (res
->params
, pat
->params
);
2995 create_pattern_info cpi
;
2996 decision
*d
= init_pattern_use (&cpi
, sinfo
, res
->params
);
2997 populate_pattern_use (&cpi
, d
, sinfo
);
3002 /* Look through the state trees in STATES for common patterns and
3003 split them into subroutines. */
3006 split_out_patterns (vec
<merge_state_info
> &states
)
3008 unsigned int first_transition
= states
.length ();
3009 hash_table
<test_pattern_hasher
> hashtab (128);
3010 /* Stage 1: Create an order in which parent states come before their child
3011 states and in which sibling states are at consecutive locations.
3012 Having consecutive sibling states allows merge_state_info to have
3013 a single to_states pointer. */
3014 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3015 for (decision
*d
= states
[i
].s
->first
; d
; d
= d
->next
)
3016 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
3018 states
.safe_push (trans
->to
);
3019 states
[i
].num_transitions
+= 1;
3021 /* Stage 2: Now that the addresses are stable, set up the to_states
3022 pointers. Look for states that might be merged and enter them
3023 into the hash table. */
3024 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3026 merge_state_info
*sinfo
= &states
[i
];
3027 if (sinfo
->num_transitions
)
3029 sinfo
->to_states
= &states
[first_transition
];
3030 first_transition
+= sinfo
->num_transitions
;
3032 /* For simplicity, we only try to merge states that have a single
3033 decision. This is in any case the best we can do for peephole2,
3034 since whether a peephole2 ACCEPT succeeds or not depends on the
3035 specific peephole2 pattern (which is unique to each ACCEPT
3036 and so couldn't be shared between states). */
3037 if (decision
*d
= sinfo
->s
->singleton ())
3038 /* ACCEPT states are unique, so don't even try to merge them. */
3039 if (d
->test
.kind
!= rtx_test::ACCEPT
3040 && (pattern_have_num_clobbers_p
3041 || d
->test
.kind
!= rtx_test::HAVE_NUM_CLOBBERS
)
3042 && (pattern_c_test_p
3043 || d
->test
.kind
!= rtx_test::C_TEST
))
3045 merge_state_info
**slot
= hashtab
.find_slot (sinfo
, INSERT
);
3046 sinfo
->prev_same_test
= *slot
;
3050 /* Stage 3: Walk backwards through the list of states and try to merge
3051 them. This is a greedy, bottom-up match; parent nodes can only start
3052 a new leaf pattern if they fail to match when combined with all child
3053 nodes that have matching patterns.
3055 For each state we keep a list of potential matches, with each
3056 potential match being larger (and deeper) than the next match in
3057 the list. The final element in the list is a leaf pattern that
3058 matches just a single state.
3060 Each candidate pattern created in this loop is unique -- it won't
3061 have been seen by an earlier iteration. We try to match each pattern
3062 with every state that appears earlier in STATES.
3064 Because the patterns created in the loop are unique, any state
3065 that already has a match must have a final potential match that
3066 is different from any new leaf pattern. Therefore, when matching
3067 leaf patterns, we need only consider states whose list of matches
3070 The non-leaf patterns that we try are as deep as possible
3071 and are an extension of the state's previous best candidate match (PB).
3072 We need only consider states whose current potential match is also PB;
3073 any states that don't match as much as PB cannnot match the new pattern,
3074 while any states that already match more than PB must be different from
3076 for (unsigned int i2
= states
.length (); i2
-- > 0; )
3078 merge_state_info
*sinfo2
= &states
[i2
];
3080 /* Enforce the bottom-upness of the match: remove matches with later
3081 states if SINFO2's child states ended up finding a better match. */
3082 prune_invalid_results (sinfo2
);
3084 /* Do nothing if the state doesn't match a later one and if there are
3085 no earlier states it could match. */
3086 if (!sinfo2
->res
&& !sinfo2
->prev_same_test
)
3089 merge_state_result
*res2
= sinfo2
->res
;
3090 decision
*d2
= sinfo2
->s
->singleton ();
3091 position
*root2
= (d2
->test
.pos_operand
< 0 ? d2
->test
.pos
: 0);
3092 unsigned int num_transitions
= sinfo2
->num_transitions
;
3094 /* If RES2 is null then SINFO2's test in isolation has not been seen
3095 before. First try matching that on its own. */
3098 merge_pattern_info
*new_pat
3099 = new merge_pattern_info (num_transitions
);
3100 merge_state_result
*new_res2
3101 = new merge_state_result (new_pat
, root2
, res2
);
3102 sinfo2
->res
= new_res2
;
3104 new_pat
->num_statements
= !d2
->test
.single_outcome_p ();
3105 new_pat
->num_results
= num_transitions
;
3106 bool matched_p
= false;
3107 /* Look for states that don't currently match anything but
3108 can be made to match SINFO2 on its own. */
3109 for (merge_state_info
*sinfo1
= sinfo2
->prev_same_test
; sinfo1
;
3110 sinfo1
= sinfo1
->prev_same_test
)
3111 if (!sinfo1
->res
&& merge_patterns (sinfo1
, sinfo2
))
3115 /* No other states match. */
3125 /* Keep the existing pattern if it's as good as anything we'd
3126 create for SINFO2. */
3127 if (complete_result_p (res2
->pattern
, sinfo2
))
3129 res2
->pattern
->num_users
+= 1;
3133 /* Create a new pattern for SINFO2. */
3134 merge_pattern_info
*new_pat
= new merge_pattern_info (num_transitions
);
3135 merge_state_result
*new_res2
3136 = new merge_state_result (new_pat
, root2
, res2
);
3137 sinfo2
->res
= new_res2
;
3139 /* Fill in details about the pattern. */
3140 new_pat
->num_statements
= !d2
->test
.single_outcome_p ();
3141 new_pat
->num_results
= 0;
3142 for (unsigned int j
= 0; j
< num_transitions
; ++j
)
3143 if (merge_state_result
*to_res
= sinfo2
->to_states
[j
].res
)
3145 /* Count the target state as part of this pattern.
3146 First update the root position so that it can reach
3147 the target state's root. */
3151 new_res2
->root
= common_position (new_res2
->root
,
3154 new_res2
->root
= to_res
->root
;
3156 merge_pattern_info
*to_pat
= to_res
->pattern
;
3157 merge_pattern_transition
*ptrans
3158 = new merge_pattern_transition (to_pat
);
3160 /* TO_PAT may have acquired more parameters when matching
3161 states earlier in STATES than TO_RES's, but the list is
3162 now final. Make sure that TO_RES is up to date. */
3163 update_parameters (to_res
->params
, to_pat
->params
);
3165 /* Start out by assuming that every user of NEW_PAT will
3166 want to pass the same (constant) parameters as TO_RES. */
3167 update_parameters (ptrans
->params
, to_res
->params
);
3169 new_pat
->transitions
[j
] = ptrans
;
3170 new_pat
->num_statements
+= to_pat
->num_statements
;
3171 new_pat
->num_results
+= to_pat
->num_results
;
3174 /* The target state doesn't match anything and so is not part
3176 new_pat
->num_results
+= 1;
3178 /* See if any earlier states that match RES2's pattern also match
3180 bool matched_p
= false;
3181 for (merge_state_info
*sinfo1
= sinfo2
->prev_same_test
; sinfo1
;
3182 sinfo1
= sinfo1
->prev_same_test
)
3184 prune_invalid_results (sinfo1
);
3186 && sinfo1
->res
->pattern
== res2
->pattern
3187 && merge_patterns (sinfo1
, sinfo2
))
3192 /* Nothing else matches NEW_PAT, so go back to the previous
3193 pattern (possibly just a single-state one). */
3198 /* Assume that SINFO2 will use RES. At this point we don't know
3199 whether earlier states that match the same pattern will use
3200 that match or a different one. */
3201 sinfo2
->res
->pattern
->num_users
+= 1;
3203 /* Step 4: Finalize the choice of pattern for each state, ignoring
3204 patterns that were only used once. Update each pattern's size
3205 so that it doesn't include subpatterns that are going to be split
3206 out into subroutines. */
3207 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3209 merge_state_info
*sinfo
= &states
[i
];
3210 merge_state_result
*res
= sinfo
->res
;
3211 /* Wind past patterns that are only used by SINFO. */
3212 while (res
&& res
->pattern
->num_users
== 1)
3217 res
->pattern
->num_users
+= 1;
3222 /* We have a shared pattern and are now committed to the match. */
3223 merge_pattern_info
*pat
= res
->pattern
;
3224 gcc_assert (valid_result_p (pat
, sinfo
));
3226 if (!pat
->complete_p
)
3228 /* Look for subpatterns that are going to be split out and remove
3229 them from the number of statements. */
3230 for (unsigned int j
= 0; j
< sinfo
->num_transitions
; ++j
)
3231 if (merge_pattern_transition
*ptrans
= pat
->transitions
[j
])
3233 merge_pattern_info
*to_pat
= ptrans
->to
;
3234 if (!same_pattern_p (pat
, to_pat
))
3235 pat
->num_statements
-= to_pat
->num_statements
;
3237 pat
->complete_p
= true;
3240 /* Step 5: Split out the patterns. */
3241 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3243 merge_state_info
*sinfo
= &states
[i
];
3244 merge_state_result
*res
= sinfo
->res
;
3245 if (!sinfo
->merged_p
&& res
&& useful_pattern_p (res
->pattern
))
3246 use_pattern (sinfo
);
3248 fprintf (stderr
, "Shared %d out of %d states by creating %d new states,"
3250 pattern_use_states
, states
.length (), pattern_def_states
,
3251 pattern_use_states
- pattern_def_states
);
3254 /* Information about a state tree that we're considering splitting into a
3258 /* The number of pseudo-statements in the state tree. */
3259 unsigned int num_statements
;
3261 /* The approximate number of nested "if" and "switch" statements that
3262 would be required if control could fall through to a later state. */
3266 /* Pairs a transition with information about its target state. */
3267 typedef std::pair
<transition
*, state_size
> subroutine_candidate
;
3269 /* Sort two subroutine_candidates so that the one with the largest
3270 number of statements comes last. */
3273 subroutine_candidate_cmp (const void *a
, const void *b
)
3275 return int (((const subroutine_candidate
*) a
)->second
.num_statements
3276 - ((const subroutine_candidate
*) b
)->second
.num_statements
);
3279 /* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new
3280 state that performs a subroutine call to S. */
3283 create_subroutine (routine_type type
, state
*s
, vec
<state
*> &procs
)
3285 procs
.safe_push (s
);
3286 acceptance_type acceptance
;
3287 acceptance
.type
= type
;
3288 acceptance
.partial_p
= true;
3289 acceptance
.u
.subroutine_id
= procs
.length ();
3290 state
*news
= new state
;
3291 add_decision (news
, rtx_test::accept (acceptance
), true, false);
3295 /* Walk state tree S, of type TYPE, and look for subtrees that would be
3296 better split into subroutines. Accumulate all such subroutines in PROCS.
3297 Return the size of the new state tree (excluding subroutines). */
3300 find_subroutines (routine_type type
, state
*s
, vec
<state
*> &procs
)
3302 auto_vec
<subroutine_candidate
, 16> candidates
;
3304 size
.num_statements
= 0;
3306 for (decision
*d
= s
->first
; d
; d
= d
->next
)
3308 if (!d
->test
.single_outcome_p ())
3309 size
.num_statements
+= 1;
3310 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
3312 /* Keep chains of simple decisions together if we know that no
3313 change of position is required. We'll output this chain as a
3314 single "if" statement, so it counts as a single nesting level. */
3315 if (d
->test
.pos
&& d
->if_statement_p ())
3318 decision
*newd
= trans
->to
->singleton ();
3321 && newd
->test
.pos_operand
< 0
3322 && newd
->test
.pos
!= d
->test
.pos
)
3323 || !newd
->if_statement_p ())
3325 if (!newd
->test
.single_outcome_p ())
3326 size
.num_statements
+= 1;
3327 trans
= newd
->singleton ();
3328 if (newd
->test
.kind
== rtx_test::SET_OP
3329 || newd
->test
.kind
== rtx_test::ACCEPT
)
3332 /* The target of TRANS is a subroutine candidate. First recurse
3333 on it to see how big it is after subroutines have been
3335 state_size to_size
= find_subroutines (type
, trans
->to
, procs
);
3336 if (d
->next
&& to_size
.depth
> MAX_DEPTH
)
3337 /* Keeping the target state in the same routine would lead
3338 to an excessive nesting of "if" and "switch" statements.
3339 Split it out into a subroutine so that it can use
3340 inverted tests that return early on failure. */
3341 trans
->to
= create_subroutine (type
, trans
->to
, procs
);
3344 size
.num_statements
+= to_size
.num_statements
;
3345 if (to_size
.num_statements
< MIN_NUM_STATEMENTS
)
3346 /* The target state is too small to be worth splitting.
3347 Keep it in the same routine as S. */
3348 size
.depth
= MAX (size
.depth
, to_size
.depth
);
3350 /* Assume for now that we'll keep the target state in the
3351 same routine as S, but record it as a subroutine candidate
3352 if S grows too big. */
3353 candidates
.safe_push (subroutine_candidate (trans
, to_size
));
3357 if (size
.num_statements
> MAX_NUM_STATEMENTS
)
3359 /* S is too big. Sort the subroutine candidates so that bigger ones
3360 are nearer the end. */
3361 candidates
.qsort (subroutine_candidate_cmp
);
3362 while (!candidates
.is_empty ()
3363 && size
.num_statements
> MAX_NUM_STATEMENTS
)
3365 /* Peel off a candidate and force it into a subroutine. */
3366 subroutine_candidate cand
= candidates
.pop ();
3367 size
.num_statements
-= cand
.second
.num_statements
;
3368 cand
.first
->to
= create_subroutine (type
, cand
.first
->to
, procs
);
3371 /* Update the depth for subroutine candidates that we decided not to
3373 for (unsigned int i
= 0; i
< candidates
.length (); ++i
)
3374 size
.depth
= MAX (size
.depth
, candidates
[i
].second
.depth
);
3379 /* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */
3382 safe_predicate_mode (const struct pred_data
*pred
, machine_mode mode
)
3384 /* Scalar integer constants have VOIDmode. */
3385 if (GET_MODE_CLASS (mode
) == MODE_INT
3386 && (pred
->codes
[CONST_INT
]
3387 || pred
->codes
[CONST_DOUBLE
]
3388 || pred
->codes
[CONST_WIDE_INT
]))
3391 return !pred
->special
&& mode
!= VOIDmode
;
3394 /* Fill CODES with the set of codes that could be matched by PRED. */
3397 get_predicate_codes (const struct pred_data
*pred
, int_set
*codes
)
3399 for (int i
= 0; i
< NUM_TRUE_RTX_CODE
; ++i
)
3400 if (!pred
|| pred
->codes
[i
])
3401 codes
->safe_push (i
);
3404 /* Return true if the first path through D1 tests the same thing as D2. */
3407 has_same_test_p (decision
*d1
, decision
*d2
)
3411 if (d1
->test
== d2
->test
)
3413 d1
= d1
->first
->to
->first
;
3419 /* Return true if D1 and D2 cannot match the same rtx. All states reachable
3420 from D2 have single decisions and all those decisions have single
3424 mutually_exclusive_p (decision
*d1
, decision
*d2
)
3426 /* If one path through D1 fails to test the same thing as D2, assume
3427 that D2's test could be true for D1 and look for a later, more useful,
3428 test. This isn't as expensive as it looks in practice. */
3429 while (!has_same_test_p (d1
, d2
))
3431 d2
= d2
->singleton ()->to
->singleton ();
3435 if (d1
->test
== d2
->test
)
3437 /* Look for any transitions from D1 that have the same labels as
3438 the transition from D2. */
3439 transition
*trans2
= d2
->singleton ();
3440 for (transition
*trans1
= d1
->first
; trans1
; trans1
= trans1
->next
)
3442 int_set::iterator i1
= trans1
->labels
.begin ();
3443 int_set::iterator end1
= trans1
->labels
.end ();
3444 int_set::iterator i2
= trans2
->labels
.begin ();
3445 int_set::iterator end2
= trans2
->labels
.end ();
3446 while (i1
!= end1
&& i2
!= end2
)
3453 /* TRANS1 has some labels in common with TRANS2. Assume
3454 that D1 and D2 could match the same rtx if the target
3455 of TRANS1 could match the same rtx as D2. */
3456 for (decision
*subd1
= trans1
->to
->first
;
3457 subd1
; subd1
= subd1
->next
)
3458 if (!mutually_exclusive_p (subd1
, d2
))
3465 for (transition
*trans1
= d1
->first
; trans1
; trans1
= trans1
->next
)
3466 for (decision
*subd1
= trans1
->to
->first
; subd1
; subd1
= subd1
->next
)
3467 if (!mutually_exclusive_p (subd1
, d2
))
3472 /* Try to merge S2's decision into D1, given that they have the same test.
3473 Fail only if EXCLUDE is nonnull and the new transition would have the
3474 same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2
3475 and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
3476 if the merge is complete. */
3479 merge_into_decision (decision
*d1
, state
*s2
, const int_set
*exclude
,
3480 state
**next_s1
, state
**next_s2
,
3481 const int_set
**next_exclude
)
3483 decision
*d2
= s2
->singleton ();
3484 transition
*trans2
= d2
->singleton ();
3486 /* Get a list of the transitions that intersect TRANS2. */
3487 auto_vec
<transition
*, 32> intersecting
;
3488 for (transition
*trans1
= d1
->first
; trans1
; trans1
= trans1
->next
)
3490 int_set::iterator i1
= trans1
->labels
.begin ();
3491 int_set::iterator end1
= trans1
->labels
.end ();
3492 int_set::iterator i2
= trans2
->labels
.begin ();
3493 int_set::iterator end2
= trans2
->labels
.end ();
3494 bool trans1_is_subset
= true;
3495 bool trans2_is_subset
= true;
3496 bool intersect_p
= false;
3497 while (i1
!= end1
&& i2
!= end2
)
3500 trans1_is_subset
= false;
3505 trans2_is_subset
= false;
3515 trans1_is_subset
= false;
3517 trans2_is_subset
= false;
3518 if (trans1_is_subset
&& trans2_is_subset
)
3520 /* There's already a transition that matches exactly.
3521 Merge the target states. */
3522 trans1
->optional
&= trans2
->optional
;
3523 *next_s1
= trans1
->to
;
3524 *next_s2
= trans2
->to
;
3528 if (trans2_is_subset
)
3530 /* TRANS1 has all the labels that TRANS2 needs. Merge S2 into
3531 the target of TRANS1, but (to avoid infinite recursion)
3532 make sure that we don't end up creating another transition
3534 *next_s1
= trans1
->to
;
3536 *next_exclude
= &trans1
->labels
;
3540 intersecting
.safe_push (trans1
);
3543 if (intersecting
.is_empty ())
3545 /* No existing labels intersect the new ones. We can just add
3547 d1
->push_back (d2
->release ());
3554 /* Take the union of the labels in INTERSECTING and TRANS2. Store the
3555 result in COMBINED and use NEXT as a temporary. */
3556 int_set tmp1
= trans2
->labels
, tmp2
;
3557 int_set
*combined
= &tmp1
, *next
= &tmp2
;
3558 for (unsigned int i
= 0; i
< intersecting
.length (); ++i
)
3560 transition
*trans1
= intersecting
[i
];
3562 next
->safe_grow (trans1
->labels
.length () + combined
->length ());
3563 int_set::iterator end
3564 = std::set_union (trans1
->labels
.begin (), trans1
->labels
.end (),
3565 combined
->begin (), combined
->end (),
3567 next
->truncate (end
- next
->begin ());
3568 std::swap (next
, combined
);
3571 /* Stop now if we've been told not to create a transition with these
3573 if (exclude
&& *combined
== *exclude
)
3576 /* Get the transition that should carry the new labels. */
3577 transition
*new_trans
= intersecting
[0];
3578 if (intersecting
.length () == 1)
3580 /* We're merging with one existing transition whose labels are a
3581 subset of those required. If both transitions are optional,
3582 we can just expand the set of labels so that it's suitable
3583 for both transitions. It isn't worth preserving the original
3584 transitions since we know that they can't be merged; we would
3585 need to backtrack to S2 if TRANS1->to fails. In contrast,
3586 we might be able to merge the targets of the transitions
3587 without any backtracking.
3589 If instead the existing transition is not optional, ensure that
3590 all target decisions are suitably protected. Some decisions
3591 might already have a more specific requirement than NEW_TRANS,
3592 in which case there's no point testing NEW_TRANS as well. E.g. this
3593 would have happened if a test for an (eq ...) rtx had been
3594 added to a decision that tested whether the code is suitable
3595 for comparison_operator. The original comparison_operator
3596 transition would have been non-optional and the (eq ...) test
3597 would be performed by a second decision in the target of that
3600 The remaining case -- keeping the original optional transition
3601 when adding a non-optional TRANS2 -- is a wash. Preserving
3602 the optional transition only helps if we later merge another
3603 state S3 that is mutually exclusive with S2 and whose labels
3604 belong to *COMBINED - TRANS1->labels. We can then test the
3605 original NEW_TRANS and S3 in the same decision. We keep the
3606 optional transition around for that case, but it occurs very
3608 gcc_assert (new_trans
->labels
!= *combined
);
3609 if (!new_trans
->optional
|| !trans2
->optional
)
3611 decision
*start
= 0;
3612 for (decision
*end
= new_trans
->to
->first
; end
; end
= end
->next
)
3614 if (!start
&& end
->test
!= d1
->test
)
3615 /* END belongs to a range of decisions that need to be
3616 protected by NEW_TRANS. */
3618 if (start
&& (!end
->next
|| end
->next
->test
== d1
->test
))
3620 /* Protect [START, END] with NEW_TRANS. The decisions
3621 move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */
3622 state
*new_s
= new state
;
3623 decision
*new_d
= new decision (d1
->test
);
3624 new_d
->push_back (new transition (new_trans
->labels
, new_s
,
3625 new_trans
->optional
));
3626 state::range
r (start
, end
);
3627 new_trans
->to
->replace (r
, new_d
);
3628 new_s
->push_back (r
);
3630 /* Continue with an empty range. */
3633 /* Continue from the decision after NEW_D. */
3638 new_trans
->optional
= true;
3639 new_trans
->labels
= *combined
;
3643 /* We're merging more than one existing transition together.
3644 Those transitions are successfully dividing the matching space
3645 and so we want to preserve them, even if they're optional.
3647 Create a new transition with the union set of labels and make
3648 it go to a state that has the original transitions. */
3649 decision
*new_d
= new decision (d1
->test
);
3650 for (unsigned int i
= 0; i
< intersecting
.length (); ++i
)
3651 new_d
->push_back (d1
->remove (intersecting
[i
]));
3653 state
*new_s
= new state
;
3654 new_s
->push_back (new_d
);
3656 new_trans
= new transition (*combined
, new_s
, true);
3657 d1
->push_back (new_trans
);
3660 /* We now have an optional transition with labels *COMBINED. Decide
3661 whether we can use it as TRANS2 or whether we need to merge S2
3662 into the target of NEW_TRANS. */
3663 gcc_assert (new_trans
->optional
);
3664 if (new_trans
->labels
== trans2
->labels
)
3666 /* NEW_TRANS matches TRANS2. Just merge the target states. */
3667 new_trans
->optional
= trans2
->optional
;
3668 *next_s1
= new_trans
->to
;
3669 *next_s2
= trans2
->to
;
3674 /* Try to merge TRANS2 into the target of the overlapping transition,
3675 but (to prevent infinite recursion or excessive redundancy) without
3676 creating another transition of the same type. */
3677 *next_s1
= new_trans
->to
;
3679 *next_exclude
= &new_trans
->labels
;
3684 /* Make progress in merging S2 into S1, given that each state in S2
3685 has a single decision. If EXCLUDE is nonnull, avoid creating a new
3686 transition with the same test as S2's decision and with the labels
3689 Return true if there is still work to do. When returning true,
3690 set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
3691 S1, S2 and EXCLUDE should have next time round.
3693 If S1 and S2 both match a particular rtx, give priority to S1. */
3696 merge_into_state_1 (state
*s1
, state
*s2
, const int_set
*exclude
,
3697 state
**next_s1
, state
**next_s2
,
3698 const int_set
**next_exclude
)
3700 decision
*d2
= s2
->singleton ();
3701 if (decision
*d1
= s1
->last
)
3703 if (d1
->test
.terminal_p ())
3704 /* D1 is an unconditional return, so S2 can never match. This can
3705 sometimes be a bug in the .md description, but might also happen
3706 if genconditions forces some conditions to true for certain
3710 /* Go backwards through the decisions in S1, stopping once we find one
3711 that could match the same thing as S2. */
3712 while (d1
->prev
&& mutually_exclusive_p (d1
, d2
))
3715 /* Search forwards from that point, merging D2 into the first
3717 for (; d1
; d1
= d1
->next
)
3719 /* If S2 performs some optional tests before testing the same thing
3720 as D1, those tests do not help to distinguish D1 and S2, so it's
3721 better to drop them. Search through such optional decisions
3722 until we find something that tests the same thing as D1. */
3726 decision
*sub_d2
= sub_s2
->singleton ();
3727 if (d1
->test
== sub_d2
->test
)
3729 /* Only apply EXCLUDE if we're testing the same thing
3731 const int_set
*sub_exclude
= (d2
== sub_d2
? exclude
: 0);
3733 /* Try to merge SUB_S2 into D1. This can only fail if
3734 it would involve creating a new transition with
3735 labels SUB_EXCLUDE. */
3736 if (merge_into_decision (d1
, sub_s2
, sub_exclude
,
3737 next_s1
, next_s2
, next_exclude
))
3738 return *next_s2
!= 0;
3740 /* Can't merge with D1; try a later decision. */
3743 transition
*sub_trans2
= sub_d2
->singleton ();
3744 if (!sub_trans2
->optional
)
3745 /* Can't merge with D1; try a later decision. */
3747 sub_s2
= sub_trans2
->to
;
3752 /* We can't merge D2 with any existing decision. Just add it to the end. */
3753 s1
->push_back (s2
->release ());
3757 /* Merge S2 into S1. If they both match a particular rtx, give
3758 priority to S1. Each state in S2 has a single decision. */
3761 merge_into_state (state
*s1
, state
*s2
)
3763 const int_set
*exclude
= 0;
3764 while (s2
&& merge_into_state_1 (s1
, s2
, exclude
, &s1
, &s2
, &exclude
))
3768 /* Pairs a pattern that needs to be matched with the rtx position at
3769 which the pattern should occur. */
3770 struct pattern_pos
{
3772 pattern_pos (rtx
, position
*);
3778 pattern_pos::pattern_pos (rtx pattern_in
, position
*pos_in
)
3779 : pattern (pattern_in
), pos (pos_in
)
3782 /* Compare entries according to their depth-first order. There shouldn't
3783 be two entries at the same position. */
3786 operator < (const pattern_pos
&e1
, const pattern_pos
&e2
)
3788 int diff
= compare_positions (e1
.pos
, e2
.pos
);
3789 gcc_assert (diff
!= 0 || e1
.pattern
== e2
.pattern
);
3793 /* Return the name of the predicate matched by MATCH_RTX. */
3796 predicate_name (rtx match_rtx
)
3798 if (GET_CODE (match_rtx
) == MATCH_SCRATCH
)
3799 return "scratch_operand";
3801 return XSTR (match_rtx
, 1);
3804 /* Add new decisions to S that check whether the rtx at position POS
3805 matches PATTERN. Return the state that is reached in that case.
3806 TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */
3809 match_pattern_2 (state
*s
, md_rtx_info
*info
, position
*pos
, rtx pattern
)
3811 auto_vec
<pattern_pos
, 32> worklist
;
3812 auto_vec
<pattern_pos
, 32> pred_and_mode_tests
;
3813 auto_vec
<pattern_pos
, 32> dup_tests
;
3815 worklist
.safe_push (pattern_pos (pattern
, pos
));
3816 while (!worklist
.is_empty ())
3818 pattern_pos next
= worklist
.pop ();
3819 pattern
= next
.pattern
;
3821 unsigned int reverse_s
= worklist
.length ();
3823 enum rtx_code code
= GET_CODE (pattern
);
3829 /* Add a test that the rtx matches the earlier one, but only
3830 after the structure and predicates have been checked. */
3831 dup_tests
.safe_push (pattern_pos (pattern
, pos
));
3833 /* Use the same code check as the original operand. */
3834 pattern
= find_operand (info
->def
, XINT (pattern
, 0), NULL_RTX
);
3837 case MATCH_PARALLEL
:
3840 case MATCH_OPERATOR
:
3842 const char *pred_name
= predicate_name (pattern
);
3843 const struct pred_data
*pred
= 0;
3844 if (pred_name
[0] != 0)
3846 pred
= lookup_predicate (pred_name
);
3847 /* Only report errors once per rtx. */
3848 if (code
== GET_CODE (pattern
))
3851 error_at (info
->loc
, "unknown predicate '%s' used in %s",
3852 pred_name
, GET_RTX_NAME (code
));
3853 else if (code
== MATCH_PARALLEL
3854 && pred
->singleton
!= PARALLEL
)
3855 error_at (info
->loc
, "predicate '%s' used in"
3856 " match_parallel does not allow only PARALLEL",
3861 if (code
== MATCH_PARALLEL
|| code
== MATCH_PAR_DUP
)
3863 /* Check that we have a parallel with enough elements. */
3864 s
= add_decision (s
, rtx_test::code (pos
), PARALLEL
, false);
3865 int min_len
= XVECLEN (pattern
, 2);
3866 s
= add_decision (s
, rtx_test::veclen_ge (pos
, min_len
),
3871 /* Check that the rtx has one of codes accepted by the
3872 predicate. This is necessary when matching suboperands
3873 of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
3874 call XEXP (X, N) without checking that X has at least
3877 get_predicate_codes (pred
, &codes
);
3878 bool need_codes
= (pred
3879 && (code
== MATCH_OPERATOR
3880 || code
== MATCH_OP_DUP
));
3881 s
= add_decision (s
, rtx_test::code (pos
), codes
, !need_codes
);
3884 /* Postpone the predicate check until we've checked the rest
3885 of the rtx structure. */
3886 if (code
== GET_CODE (pattern
))
3887 pred_and_mode_tests
.safe_push (pattern_pos (pattern
, pos
));
3889 /* If we need to match suboperands, add them to the worklist. */
3890 if (code
== MATCH_OPERATOR
|| code
== MATCH_PARALLEL
)
3892 position
**subpos_ptr
;
3893 enum position_type pos_type
;
3895 if (code
== MATCH_OPERATOR
|| code
== MATCH_OP_DUP
)
3897 pos_type
= POS_XEXP
;
3898 subpos_ptr
= &pos
->xexps
;
3899 i
= (code
== MATCH_OPERATOR
? 2 : 1);
3903 pos_type
= POS_XVECEXP0
;
3904 subpos_ptr
= &pos
->xvecexp0s
;
3907 for (int j
= 0; j
< XVECLEN (pattern
, i
); ++j
)
3909 position
*subpos
= next_position (subpos_ptr
, pos
,
3911 worklist
.safe_push (pattern_pos (XVECEXP (pattern
, i
, j
),
3913 subpos_ptr
= &subpos
->next
;
3921 /* Check that the rtx has the right code. */
3922 s
= add_decision (s
, rtx_test::code (pos
), code
, false);
3924 /* Queue a test for the mode if one is specified. */
3925 if (GET_MODE (pattern
) != VOIDmode
)
3926 pred_and_mode_tests
.safe_push (pattern_pos (pattern
, pos
));
3928 /* Push subrtxes onto the worklist. Match nonrtx operands now. */
3929 const char *fmt
= GET_RTX_FORMAT (code
);
3930 position
**subpos_ptr
= &pos
->xexps
;
3931 for (size_t i
= 0; fmt
[i
]; ++i
)
3933 position
*subpos
= next_position (subpos_ptr
, pos
,
3938 worklist
.safe_push (pattern_pos (XEXP (pattern
, i
),
3944 /* Make sure the vector has the right number of
3946 int length
= XVECLEN (pattern
, i
);
3947 s
= add_decision (s
, rtx_test::veclen (pos
),
3950 position
**subpos2_ptr
= &pos
->xvecexp0s
;
3951 for (int j
= 0; j
< length
; j
++)
3953 position
*subpos2
= next_position (subpos2_ptr
, pos
,
3955 rtx x
= XVECEXP (pattern
, i
, j
);
3956 worklist
.safe_push (pattern_pos (x
, subpos2
));
3957 subpos2_ptr
= &subpos2
->next
;
3963 /* Make sure that XINT (X, I) has the right value. */
3964 s
= add_decision (s
, rtx_test::int_field (pos
, i
),
3965 XINT (pattern
, i
), false);
3969 /* Make sure that REGNO (X) has the right value. */
3970 gcc_assert (i
== 0);
3971 s
= add_decision (s
, rtx_test::regno_field (pos
),
3972 REGNO (pattern
), false);
3976 /* Make sure that XWINT (X, I) has the right value. */
3977 s
= add_decision (s
, rtx_test::wide_int_field (pos
, i
),
3978 XWINT (pattern
, 0), false);
3987 subpos_ptr
= &subpos
->next
;
3992 /* Operands are pushed onto the worklist so that later indices are
3993 nearer the top. That's what we want for SETs, since a SET_SRC
3994 is a better discriminator than a SET_DEST. In other cases it's
3995 usually better to match earlier indices first. This is especially
3996 true of PARALLELs, where the first element tends to be the most
3997 individual. It's also true for commutative operators, where the
3998 canonicalization rules say that the more complex operand should
4000 if (code
!= SET
&& worklist
.length () > reverse_s
)
4001 std::reverse (&worklist
[0] + reverse_s
,
4002 &worklist
[0] + worklist
.length ());
4005 /* Sort the predicate and mode tests so that they're in depth-first order.
4006 The main goal of this is to put SET_SRC match_operands after SET_DEST
4007 match_operands and after mode checks for the enclosing SET_SRC operators
4008 (such as the mode of a PLUS in an addition instruction). The latter
4009 two types of test can determine the mode exactly, whereas a SET_SRC
4010 match_operand often has to cope with the possibility of the operand
4011 being a modeless constant integer. E.g. something that matches
4012 register_operand (x, SImode) never matches register_operand (x, DImode),
4013 but a const_int that matches immediate_operand (x, SImode) also matches
4014 immediate_operand (x, DImode). The register_operand cases can therefore
4015 be distinguished by a switch on the mode, but the immediate_operand
4017 if (pred_and_mode_tests
.length () > 1)
4018 std::sort (&pred_and_mode_tests
[0],
4019 &pred_and_mode_tests
[0] + pred_and_mode_tests
.length ());
4021 /* Add the mode and predicate tests. */
4024 FOR_EACH_VEC_ELT (pred_and_mode_tests
, i
, e
)
4026 switch (GET_CODE (e
->pattern
))
4028 case MATCH_PARALLEL
:
4031 case MATCH_OPERATOR
:
4033 int opno
= XINT (e
->pattern
, 0);
4034 num_operands
= MAX (num_operands
, opno
+ 1);
4035 const char *pred_name
= predicate_name (e
->pattern
);
4038 const struct pred_data
*pred
= lookup_predicate (pred_name
);
4039 /* Check the mode first, to distinguish things like SImode
4040 and DImode register_operands, as described above. */
4041 machine_mode mode
= GET_MODE (e
->pattern
);
4042 if (safe_predicate_mode (pred
, mode
))
4043 s
= add_decision (s
, rtx_test::mode (e
->pos
), mode
, true);
4045 /* Assign to operands[] first, so that the rtx usually doesn't
4046 need to be live across the call to the predicate.
4048 This shouldn't cause a problem with dirtying the page,
4049 since we fully expect to assign to operands[] at some point,
4050 and since the caller usually writes to other parts of
4051 recog_data anyway. */
4052 s
= add_decision (s
, rtx_test::set_op (e
->pos
, opno
),
4054 s
= add_decision (s
, rtx_test::predicate (e
->pos
, pred
, mode
),
4058 /* Historically we've ignored the mode when there's no
4059 predicate. Just set up operands[] unconditionally. */
4060 s
= add_decision (s
, rtx_test::set_op (e
->pos
, opno
),
4066 s
= add_decision (s
, rtx_test::mode (e
->pos
),
4067 GET_MODE (e
->pattern
), false);
4072 /* Finally add rtx_equal_p checks for duplicated operands. */
4073 FOR_EACH_VEC_ELT (dup_tests
, i
, e
)
4074 s
= add_decision (s
, rtx_test::duplicate (e
->pos
, XINT (e
->pattern
, 0)),
4079 /* Add new decisions to S that make it return ACCEPTANCE if:
4081 (1) the rtx doesn't match anything already matched by S
4082 (2) the rtx matches TOP_PATTERN and
4085 For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns
4086 to match, otherwise it is a single instruction pattern. */
4089 match_pattern_1 (state
*s
, md_rtx_info
*info
, rtx pattern
, const char *c_test
,
4090 acceptance_type acceptance
)
4092 if (acceptance
.type
== PEEPHOLE2
)
4094 /* Match each individual instruction. */
4095 position
**subpos_ptr
= &peep2_insn_pos_list
;
4097 for (int i
= 0; i
< XVECLEN (pattern
, 0); ++i
)
4099 rtx x
= XVECEXP (pattern
, 0, i
);
4100 position
*subpos
= next_position (subpos_ptr
, &root_pos
,
4101 POS_PEEP2_INSN
, count
);
4103 s
= add_decision (s
, rtx_test::peep2_count (count
+ 1),
4105 s
= match_pattern_2 (s
, info
, subpos
, x
);
4106 subpos_ptr
= &subpos
->next
;
4109 acceptance
.u
.full
.u
.match_len
= count
- 1;
4113 /* Make the rtx itself. */
4114 s
= match_pattern_2 (s
, info
, &root_pos
, pattern
);
4116 /* If the match is only valid when extra clobbers are added,
4117 make sure we're able to pass that information to the caller. */
4118 if (acceptance
.type
== RECOG
&& acceptance
.u
.full
.u
.num_clobbers
)
4119 s
= add_decision (s
, rtx_test::have_num_clobbers (), true, false);
4122 /* Make sure that the C test is true. */
4123 if (maybe_eval_c_test (c_test
) != 1)
4124 s
= add_decision (s
, rtx_test::c_test (c_test
), true, false);
4126 /* Accept the pattern. */
4127 add_decision (s
, rtx_test::accept (acceptance
), true, false);
4130 /* Like match_pattern_1, but (if merge_states_p) try to merge the
4131 decisions with what's already in S, to reduce the amount of
4135 match_pattern (state
*s
, md_rtx_info
*info
, rtx pattern
, const char *c_test
,
4136 acceptance_type acceptance
)
4141 /* Add the decisions to a fresh state and then merge the full tree
4142 into the existing one. */
4143 match_pattern_1 (&root
, info
, pattern
, c_test
, acceptance
);
4144 merge_into_state (s
, &root
);
4147 match_pattern_1 (s
, info
, pattern
, c_test
, acceptance
);
4150 /* Begin the output file. */
4156 /* Generated automatically by the program `genrecog' from the target\n\
4157 machine description file. */\n\
4159 #include \"config.h\"\n\
4160 #include \"system.h\"\n\
4161 #include \"coretypes.h\"\n\
4162 #include \"backend.h\"\n\
4163 #include \"predict.h\"\n\
4164 #include \"rtl.h\"\n\
4165 #include \"tm_p.h\"\n\
4166 #include \"emit-rtl.h\"\n\
4167 #include \"insn-config.h\"\n\
4168 #include \"recog.h\"\n\
4169 #include \"output.h\"\n\
4170 #include \"flags.h\"\n\
4171 #include \"df.h\"\n\
4172 #include \"resource.h\"\n\
4173 #include \"diagnostic-core.h\"\n\
4174 #include \"reload.h\"\n\
4175 #include \"regs.h\"\n\
4176 #include \"tm-constrs.h\"\n\
4180 /* `recog' contains a decision tree that recognizes whether the rtx\n\
4181 X0 is a valid instruction.\n\
4183 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
4184 returns a nonnegative number which is the insn code number for the\n\
4185 pattern that matched. This is the same as the order in the machine\n\
4186 description of the entry that matched. This number can be used as an\n\
4187 index into `insn_data' and other tables.\n");
4189 The third parameter to recog is an optional pointer to an int. If\n\
4190 present, recog will accept a pattern if it matches except for missing\n\
4191 CLOBBER expressions at the end. In that case, the value pointed to by\n\
4192 the optional pointer will be set to the number of CLOBBERs that need\n\
4193 to be added (it should be initialized to zero by the caller). If it");
4195 is set nonzero, the caller should allocate a PARALLEL of the\n\
4196 appropriate size, copy the initial entries, and call add_clobbers\n\
4197 (found in insn-emit.c) to fill in the CLOBBERs.\n\
4201 The function split_insns returns 0 if the rtl could not\n\
4202 be split or the split rtl as an INSN list if it can be.\n\
4204 The function peephole2_insns returns 0 if the rtl could not\n\
4205 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4206 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4210 /* Return the C type of a parameter with type TYPE. */
4213 parameter_type_string (parameter::type_enum type
)
4217 case parameter::UNSET
:
4220 case parameter::CODE
:
4223 case parameter::MODE
:
4224 return "machine_mode";
4226 case parameter::INT
:
4229 case parameter::UINT
:
4230 return "unsigned int";
4232 case parameter::WIDE_INT
:
4233 return "HOST_WIDE_INT";
4238 /* Return true if ACCEPTANCE requires only a single C statement even in
4239 a backtracking context. */
4242 single_statement_p (const acceptance_type
&acceptance
)
4244 if (acceptance
.partial_p
)
4245 /* We need to handle failures of the subroutine. */
4247 switch (acceptance
.type
)
4254 /* False if we need to assign to pnum_clobbers. */
4255 return acceptance
.u
.full
.u
.num_clobbers
== 0;
4258 /* We need to assign to pmatch_len_ and handle null returns from the
4259 peephole2 routine. */
4265 /* Return the C failure value for a routine of type TYPE. */
4268 get_failure_return (routine_type type
)
4283 /* Indicates whether a block of code always returns or whether it can fall
4291 /* Information used while writing out code. */
4295 /* The type of routine that we're generating. */
4298 /* Maps position ids to xN variable numbers. The entry is only valid if
4299 it is less than the length of VAR_TO_ID, but this holds for every position
4300 tested by a state when writing out that state. */
4301 auto_vec
<unsigned int> id_to_var
;
4303 /* Maps xN variable numbers to position ids. */
4304 auto_vec
<unsigned int> var_to_id
;
4306 /* Index N is true if variable xN has already been set. */
4307 auto_vec
<bool> seen_vars
;
4310 /* Return true if D is a call to a pattern routine and if there is some X
4311 such that the transition for pattern result N goes to a successful return
4312 with code X+N. When returning true, set *BASE_OUT to this X and *COUNT_OUT
4313 to the number of return values. (We know that every PATTERN decision has
4314 a transition for every successful return.) */
4317 terminal_pattern_p (decision
*d
, unsigned int *base_out
,
4318 unsigned int *count_out
)
4320 if (d
->test
.kind
!= rtx_test::PATTERN
)
4322 unsigned int base
= 0;
4323 unsigned int count
= 0;
4324 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
4326 if (trans
->is_param
|| trans
->labels
.length () != 1)
4328 decision
*subd
= trans
->to
->singleton ();
4329 if (!subd
|| subd
->test
.kind
!= rtx_test::ACCEPT
)
4331 unsigned int this_base
= (subd
->test
.u
.acceptance
.u
.full
.code
4332 - trans
->labels
[0]);
4333 if (trans
== d
->first
)
4335 else if (base
!= this_base
)
4344 /* Return true if TEST doesn't test an rtx or if the rtx it tests is
4345 already available in state OS. */
4348 test_position_available_p (output_state
*os
, const rtx_test
&test
)
4351 || test
.pos_operand
>= 0
4352 || os
->seen_vars
[os
->id_to_var
[test
.pos
->id
]]);
4355 /* Like printf, but print INDENT spaces at the beginning. */
4357 static void ATTRIBUTE_PRINTF_2
4358 printf_indent (unsigned int indent
, const char *format
, ...)
4361 va_start (ap
, format
);
4362 printf ("%*s", indent
, "");
4363 vprintf (format
, ap
);
4367 /* Emit code to initialize the variable associated with POS, if it isn't
4368 already valid in state OS. Indent each line by INDENT spaces. Update
4369 OS with the new state. */
4372 change_state (output_state
*os
, position
*pos
, unsigned int indent
)
4374 unsigned int var
= os
->id_to_var
[pos
->id
];
4375 gcc_assert (var
< os
->var_to_id
.length () && os
->var_to_id
[var
] == pos
->id
);
4376 if (os
->seen_vars
[var
])
4380 case POS_PEEP2_INSN
:
4381 printf_indent (indent
, "x%d = PATTERN (peep2_next_insn (%d));\n",
4386 change_state (os
, pos
->base
, indent
);
4387 printf_indent (indent
, "x%d = XEXP (x%d, %d);\n",
4388 var
, os
->id_to_var
[pos
->base
->id
], pos
->arg
);
4392 change_state (os
, pos
->base
, indent
);
4393 printf_indent (indent
, "x%d = XVECEXP (x%d, 0, %d);\n",
4394 var
, os
->id_to_var
[pos
->base
->id
], pos
->arg
);
4397 os
->seen_vars
[var
] = true;
4400 /* Print the enumerator constant for CODE -- the upcase version of
4404 print_code (enum rtx_code code
)
4407 for (p
= GET_RTX_NAME (code
); *p
; p
++)
4408 putchar (TOUPPER (*p
));
4411 /* Emit a uint64_t as an integer constant expression. We need to take
4412 special care to avoid "decimal constant is so large that it is unsigned"
4413 warnings in the resulting code. */
4416 print_host_wide_int (uint64_t val
)
4418 uint64_t min
= uint64_t (1) << (HOST_BITS_PER_WIDE_INT
- 1);
4420 printf ("(" HOST_WIDE_INT_PRINT_DEC_C
" - 1)", val
+ 1);
4422 printf (HOST_WIDE_INT_PRINT_DEC_C
, val
);
4425 /* Print the C expression for actual parameter PARAM. */
4428 print_parameter_value (const parameter
¶m
)
4431 printf ("i%d", (int) param
.value
+ 1);
4435 case parameter::UNSET
:
4439 case parameter::CODE
:
4440 print_code ((enum rtx_code
) param
.value
);
4443 case parameter::MODE
:
4444 printf ("%smode", GET_MODE_NAME ((machine_mode
) param
.value
));
4447 case parameter::INT
:
4448 printf ("%d", (int) param
.value
);
4451 case parameter::UINT
:
4452 printf ("%u", (unsigned int) param
.value
);
4455 case parameter::WIDE_INT
:
4456 print_host_wide_int (param
.value
);
4461 /* Print the C expression for the rtx tested by TEST. */
4464 print_test_rtx (output_state
*os
, const rtx_test
&test
)
4466 if (test
.pos_operand
>= 0)
4467 printf ("operands[%d]", test
.pos_operand
);
4469 printf ("x%d", os
->id_to_var
[test
.pos
->id
]);
4472 /* Print the C expression for non-boolean test TEST. */
4475 print_nonbool_test (output_state
*os
, const rtx_test
&test
)
4479 case rtx_test::CODE
:
4480 printf ("GET_CODE (");
4481 print_test_rtx (os
, test
);
4485 case rtx_test::MODE
:
4486 printf ("GET_MODE (");
4487 print_test_rtx (os
, test
);
4491 case rtx_test::VECLEN
:
4492 printf ("XVECLEN (");
4493 print_test_rtx (os
, test
);
4497 case rtx_test::INT_FIELD
:
4499 print_test_rtx (os
, test
);
4500 printf (", %d)", test
.u
.opno
);
4503 case rtx_test::REGNO_FIELD
:
4505 print_test_rtx (os
, test
);
4509 case rtx_test::WIDE_INT_FIELD
:
4511 print_test_rtx (os
, test
);
4512 printf (", %d)", test
.u
.opno
);
4515 case rtx_test::PATTERN
:
4517 pattern_routine
*routine
= test
.u
.pattern
->routine
;
4518 printf ("pattern%d (", routine
->pattern_id
);
4519 const char *sep
= "";
4522 print_test_rtx (os
, test
);
4525 if (routine
->insn_p
)
4527 printf ("%sinsn", sep
);
4530 if (routine
->pnum_clobbers_p
)
4532 printf ("%spnum_clobbers", sep
);
4535 for (unsigned int i
= 0; i
< test
.u
.pattern
->params
.length (); ++i
)
4537 fputs (sep
, stdout
);
4538 print_parameter_value (test
.u
.pattern
->params
[i
]);
4545 case rtx_test::PEEP2_COUNT
:
4546 case rtx_test::VECLEN_GE
:
4547 case rtx_test::SAVED_CONST_INT
:
4548 case rtx_test::DUPLICATE
:
4549 case rtx_test::PREDICATE
:
4550 case rtx_test::SET_OP
:
4551 case rtx_test::HAVE_NUM_CLOBBERS
:
4552 case rtx_test::C_TEST
:
4553 case rtx_test::ACCEPT
:
4558 /* IS_PARAM and LABEL are taken from a transition whose source
4559 decision performs TEST. Print the C code for the label. */
4562 print_label_value (const rtx_test
&test
, bool is_param
, uint64_t value
)
4564 print_parameter_value (parameter (transition_parameter_type (test
.kind
),
4568 /* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
4569 If !IS_PARAM, print code to compare TEST with the C constant VALUE.
4570 Test for inequality if INVERT_P, otherwise test for equality. */
4573 print_test (output_state
*os
, const rtx_test
&test
, bool is_param
,
4574 uint64_t value
, bool invert_p
)
4578 /* Handle the non-boolean TESTs. */
4579 case rtx_test::CODE
:
4580 case rtx_test::MODE
:
4581 case rtx_test::VECLEN
:
4582 case rtx_test::REGNO_FIELD
:
4583 case rtx_test::INT_FIELD
:
4584 case rtx_test::WIDE_INT_FIELD
:
4585 case rtx_test::PATTERN
:
4586 print_nonbool_test (os
, test
);
4587 printf (" %s ", invert_p
? "!=" : "==");
4588 print_label_value (test
, is_param
, value
);
4591 case rtx_test::SAVED_CONST_INT
:
4592 gcc_assert (!is_param
&& value
== 1);
4593 print_test_rtx (os
, test
);
4594 printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ",
4595 invert_p
? "!=" : "==");
4596 print_parameter_value (parameter (parameter::INT
,
4597 test
.u
.integer
.is_param
,
4598 test
.u
.integer
.value
));
4602 case rtx_test::PEEP2_COUNT
:
4603 gcc_assert (!is_param
&& value
== 1);
4604 printf ("peep2_current_count %s %d", invert_p
? "<" : ">=",
4608 case rtx_test::VECLEN_GE
:
4609 gcc_assert (!is_param
&& value
== 1);
4610 printf ("XVECLEN (");
4611 print_test_rtx (os
, test
);
4612 printf (", 0) %s %d", invert_p
? "<" : ">=", test
.u
.min_len
);
4615 case rtx_test::PREDICATE
:
4616 gcc_assert (!is_param
&& value
== 1);
4617 printf ("%s%s (", invert_p
? "!" : "", test
.u
.predicate
.data
->name
);
4618 print_test_rtx (os
, test
);
4620 print_parameter_value (parameter (parameter::MODE
,
4621 test
.u
.predicate
.mode_is_param
,
4622 test
.u
.predicate
.mode
));
4626 case rtx_test::DUPLICATE
:
4627 gcc_assert (!is_param
&& value
== 1);
4628 printf ("%srtx_equal_p (", invert_p
? "!" : "");
4629 print_test_rtx (os
, test
);
4630 printf (", operands[%d])", test
.u
.opno
);
4633 case rtx_test::HAVE_NUM_CLOBBERS
:
4634 gcc_assert (!is_param
&& value
== 1);
4635 printf ("pnum_clobbers %s NULL", invert_p
? "==" : "!=");
4638 case rtx_test::C_TEST
:
4639 gcc_assert (!is_param
&& value
== 1);
4642 print_c_condition (test
.u
.string
);
4645 case rtx_test::ACCEPT
:
4646 case rtx_test::SET_OP
:
4651 static exit_state
print_decision (output_state
*, decision
*,
4652 unsigned int, bool);
4654 /* Print code to perform S, indent each line by INDENT spaces.
4655 IS_FINAL is true if there are no fallback decisions to test on failure;
4656 if the state fails then the entire routine fails. */
4659 print_state (output_state
*os
, state
*s
, unsigned int indent
, bool is_final
)
4661 exit_state es
= ES_FALLTHROUGH
;
4662 for (decision
*d
= s
->first
; d
; d
= d
->next
)
4663 es
= print_decision (os
, d
, indent
, is_final
&& !d
->next
);
4664 if (es
!= ES_RETURNED
&& is_final
)
4666 printf_indent (indent
, "return %s;\n", get_failure_return (os
->type
));
4672 /* Print the code for subroutine call ACCEPTANCE (for which partial_p
4673 is known to be true). Return the C condition that indicates a successful
4677 print_subroutine_call (const acceptance_type
&acceptance
)
4679 switch (acceptance
.type
)
4685 printf ("recog_%d (x1, insn, pnum_clobbers)",
4686 acceptance
.u
.subroutine_id
);
4690 printf ("split_%d (x1, insn)", acceptance
.u
.subroutine_id
);
4691 return "!= NULL_RTX";
4694 printf ("peephole2_%d (x1, insn, pmatch_len_)",
4695 acceptance
.u
.subroutine_id
);
4696 return "!= NULL_RTX";
4701 /* Print code for the successful match described by ACCEPTANCE.
4702 INDENT and IS_FINAL are as for print_state. */
4705 print_acceptance (const acceptance_type
&acceptance
, unsigned int indent
,
4708 if (acceptance
.partial_p
)
4710 /* Defer the rest of the match to a subroutine. */
4713 printf_indent (indent
, "return ");
4714 print_subroutine_call (acceptance
);
4720 printf_indent (indent
, "res = ");
4721 const char *res_test
= print_subroutine_call (acceptance
);
4723 printf_indent (indent
, "if (res %s)\n", res_test
);
4724 printf_indent (indent
+ 2, "return res;\n");
4725 return ES_FALLTHROUGH
;
4728 switch (acceptance
.type
)
4731 printf_indent (indent
, "return %d;\n", acceptance
.u
.full
.code
);
4735 if (acceptance
.u
.full
.u
.num_clobbers
!= 0)
4736 printf_indent (indent
, "*pnum_clobbers = %d;\n",
4737 acceptance
.u
.full
.u
.num_clobbers
);
4738 printf_indent (indent
, "return %d; /* %s */\n", acceptance
.u
.full
.code
,
4739 get_insn_name (acceptance
.u
.full
.code
));
4743 printf_indent (indent
, "return gen_split_%d (insn, operands);\n",
4744 acceptance
.u
.full
.code
);
4748 printf_indent (indent
, "*pmatch_len_ = %d;\n",
4749 acceptance
.u
.full
.u
.match_len
);
4752 printf_indent (indent
, "return gen_peephole2_%d (insn, operands);\n",
4753 acceptance
.u
.full
.code
);
4758 printf_indent (indent
, "res = gen_peephole2_%d (insn, operands);\n",
4759 acceptance
.u
.full
.code
);
4760 printf_indent (indent
, "if (res != NULL_RTX)\n");
4761 printf_indent (indent
+ 2, "return res;\n");
4762 return ES_FALLTHROUGH
;
4768 /* Print code to perform D. INDENT and IS_FINAL are as for print_state. */
4771 print_decision (output_state
*os
, decision
*d
, unsigned int indent
,
4775 unsigned int base
, count
;
4777 /* Make sure the rtx under test is available either in operands[] or
4778 in an xN variable. */
4779 if (d
->test
.pos
&& d
->test
.pos_operand
< 0)
4780 change_state (os
, d
->test
.pos
, indent
);
4782 /* Look for cases where a pattern routine P1 calls another pattern routine
4783 P2 and where P1 returns X + BASE whenever P2 returns X. If IS_FINAL
4784 is true and BASE is zero we can simply use:
4786 return patternN (...);
4788 Otherwise we can use:
4790 res = patternN (...);
4794 However, if BASE is nonzero and patternN only returns 0 or -1,
4795 the usual "return BASE;" is better than "return res + BASE;".
4796 If BASE is zero, "return res;" should be better than "return 0;",
4797 since no assignment to the return register is required. */
4798 if (os
->type
== SUBPATTERN
4799 && terminal_pattern_p (d
, &base
, &count
)
4800 && (base
== 0 || count
> 1))
4802 if (is_final
&& base
== 0)
4804 printf_indent (indent
, "return ");
4805 print_nonbool_test (os
, d
->test
);
4806 printf ("; /* [-1, %d] */\n", count
- 1);
4811 printf_indent (indent
, "res = ");
4812 print_nonbool_test (os
, d
->test
);
4814 printf_indent (indent
, "if (res >= 0)\n");
4815 printf_indent (indent
+ 2, "return res");
4817 printf (" + %d", base
);
4818 printf ("; /* [%d, %d] */\n", base
, base
+ count
- 1);
4819 return ES_FALLTHROUGH
;
4822 else if (d
->test
.kind
== rtx_test::ACCEPT
)
4823 return print_acceptance (d
->test
.u
.acceptance
, indent
, is_final
);
4824 else if (d
->test
.kind
== rtx_test::SET_OP
)
4826 printf_indent (indent
, "operands[%d] = ", d
->test
.u
.opno
);
4827 print_test_rtx (os
, d
->test
);
4829 return print_state (os
, d
->singleton ()->to
, indent
, is_final
);
4831 /* Handle decisions with a single transition and a single transition
4833 else if (d
->if_statement_p (&label
))
4835 transition
*trans
= d
->singleton ();
4836 if (mark_optional_transitions_p
&& trans
->optional
)
4837 printf_indent (indent
, "/* OPTIONAL IF */\n");
4839 /* Print the condition associated with TRANS. Invert it if IS_FINAL,
4840 so that we return immediately on failure and fall through on
4842 printf_indent (indent
, "if (");
4843 print_test (os
, d
->test
, trans
->is_param
, label
, is_final
);
4845 /* Look for following states that would be handled by this code
4846 on recursion. If they don't need any preparatory statements,
4847 include them in the current "if" statement rather than creating
4851 d
= trans
->to
->singleton ();
4853 || d
->test
.kind
== rtx_test::ACCEPT
4854 || d
->test
.kind
== rtx_test::SET_OP
4855 || !d
->if_statement_p (&label
)
4856 || !test_position_available_p (os
, d
->test
))
4860 if (mark_optional_transitions_p
&& trans
->optional
)
4861 printf_indent (indent
+ 4, "/* OPTIONAL IF */\n");
4862 printf_indent (indent
+ 4, "%s ", is_final
? "||" : "&&");
4863 print_test (os
, d
->test
, trans
->is_param
, label
, is_final
);
4867 /* Print the conditional code with INDENT + 2 and the fallthrough
4868 code with indent INDENT. */
4869 state
*to
= trans
->to
;
4872 /* We inverted the condition above, so return failure in the
4873 "if" body and fall through to the target of the transition. */
4874 printf_indent (indent
+ 2, "return %s;\n",
4875 get_failure_return (os
->type
));
4876 return print_state (os
, to
, indent
, is_final
);
4878 else if (to
->singleton ()
4879 && to
->first
->test
.kind
== rtx_test::ACCEPT
4880 && single_statement_p (to
->first
->test
.u
.acceptance
))
4882 /* The target of the transition is a simple "return" statement.
4883 It doesn't need any braces and doesn't fall through. */
4884 if (print_acceptance (to
->first
->test
.u
.acceptance
,
4885 indent
+ 2, true) != ES_RETURNED
)
4887 return ES_FALLTHROUGH
;
4891 /* The general case. Output code for the target of the transition
4892 in braces. This will not invalidate any of the xN variables
4893 that are already valid, but we mustn't rely on any that are
4894 set by the "if" body. */
4895 auto_vec
<bool, 32> old_seen
;
4896 old_seen
.safe_splice (os
->seen_vars
);
4898 printf_indent (indent
+ 2, "{\n");
4899 print_state (os
, trans
->to
, indent
+ 4, is_final
);
4900 printf_indent (indent
+ 2, "}\n");
4902 os
->seen_vars
.truncate (0);
4903 os
->seen_vars
.splice (old_seen
);
4904 return ES_FALLTHROUGH
;
4909 /* Output the decision as a switch statement. */
4910 printf_indent (indent
, "switch (");
4911 print_nonbool_test (os
, d
->test
);
4914 /* Each case statement starts with the same set of valid variables.
4915 These are also the only variables will be valid on fallthrough. */
4916 auto_vec
<bool, 32> old_seen
;
4917 old_seen
.safe_splice (os
->seen_vars
);
4919 printf_indent (indent
+ 2, "{\n");
4920 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
4922 gcc_assert (!trans
->is_param
);
4923 if (mark_optional_transitions_p
&& trans
->optional
)
4924 printf_indent (indent
+ 2, "/* OPTIONAL CASE */\n");
4925 for (int_set::iterator j
= trans
->labels
.begin ();
4926 j
!= trans
->labels
.end (); ++j
)
4928 printf_indent (indent
+ 2, "case ");
4929 print_label_value (d
->test
, trans
->is_param
, *j
);
4932 if (print_state (os
, trans
->to
, indent
+ 4, is_final
))
4934 /* The state can fall through. Add an explicit break. */
4935 gcc_assert (!is_final
);
4936 printf_indent (indent
+ 4, "break;\n");
4940 /* Restore the original set of valid variables. */
4941 os
->seen_vars
.truncate (0);
4942 os
->seen_vars
.splice (old_seen
);
4944 /* Add a default case. */
4945 printf_indent (indent
+ 2, "default:\n");
4947 printf_indent (indent
+ 4, "return %s;\n",
4948 get_failure_return (os
->type
));
4950 printf_indent (indent
+ 4, "break;\n");
4951 printf_indent (indent
+ 2, "}\n");
4952 return is_final
? ES_RETURNED
: ES_FALLTHROUGH
;
4956 /* Make sure that OS has a position variable for POS. ROOT_P is true if
4957 POS is the root position for the routine. */
4960 assign_position_var (output_state
*os
, position
*pos
, bool root_p
)
4962 unsigned int idx
= os
->id_to_var
[pos
->id
];
4963 if (idx
< os
->var_to_id
.length () && os
->var_to_id
[idx
] == pos
->id
)
4965 if (!root_p
&& pos
->type
!= POS_PEEP2_INSN
)
4966 assign_position_var (os
, pos
->base
, false);
4967 os
->id_to_var
[pos
->id
] = os
->var_to_id
.length ();
4968 os
->var_to_id
.safe_push (pos
->id
);
4971 /* Make sure that OS has the position variables required by S. */
4974 assign_position_vars (output_state
*os
, state
*s
)
4976 for (decision
*d
= s
->first
; d
; d
= d
->next
)
4978 /* Positions associated with operands can be read from the
4979 operands[] array. */
4980 if (d
->test
.pos
&& d
->test
.pos_operand
< 0)
4981 assign_position_var (os
, d
->test
.pos
, false);
4982 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
4983 assign_position_vars (os
, trans
->to
);
4987 /* Print the open brace and variable definitions for a routine that
4988 implements S. ROOT is the deepest rtx from which S can access all
4989 relevant parts of the first instruction it matches. Initialize OS
4990 so that every relevant position has an rtx variable xN and so that
4991 only ROOT's variable has a valid value. */
4994 print_subroutine_start (output_state
*os
, state
*s
, position
*root
)
4996 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED"
4997 " = &recog_data.operand[0];\n");
4998 os
->var_to_id
.truncate (0);
4999 os
->seen_vars
.truncate (0);
5002 /* Create a fake entry for position 0 so that an id_to_var of 0
5003 is always invalid. This also makes the xN variables naturally
5004 1-based rather than 0-based. */
5005 os
->var_to_id
.safe_push (num_positions
);
5007 /* Associate ROOT with x1. */
5008 assign_position_var (os
, root
, true);
5010 /* Assign xN variables to all other relevant positions. */
5011 assign_position_vars (os
, s
);
5013 /* Output the variable declarations (except for ROOT's, which is
5014 passed in as a parameter). */
5015 unsigned int num_vars
= os
->var_to_id
.length ();
5018 for (unsigned int i
= 2; i
< num_vars
; ++i
)
5019 /* Print 8 rtx variables to a line. */
5021 i
== 2 ? " rtx" : (i
- 2) % 8 == 0 ? ";\n rtx" : ",", i
);
5025 /* Say that x1 is valid and the rest aren't. */
5026 os
->seen_vars
.safe_grow_cleared (num_vars
);
5027 os
->seen_vars
[1] = true;
5029 if (os
->type
== SUBPATTERN
|| os
->type
== RECOG
)
5030 printf (" int res ATTRIBUTE_UNUSED;\n");
5032 printf (" rtx_insn *res ATTRIBUTE_UNUSED;\n");
5035 /* Output the definition of pattern routine ROUTINE. */
5038 print_pattern (output_state
*os
, pattern_routine
*routine
)
5040 printf ("\nstatic int\npattern%d (", routine
->pattern_id
);
5041 const char *sep
= "";
5042 /* Add the top-level rtx parameter, if any. */
5045 printf ("%srtx x1", sep
);
5048 /* Add the optional parameters. */
5049 if (routine
->insn_p
)
5051 /* We can't easily tell whether a C condition actually reads INSN,
5052 so add an ATTRIBUTE_UNUSED just in case. */
5053 printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep
);
5056 if (routine
->pnum_clobbers_p
)
5058 printf ("%sint *pnum_clobbers", sep
);
5061 /* Add the "i" parameters. */
5062 for (unsigned int i
= 0; i
< routine
->param_types
.length (); ++i
)
5064 printf ("%s%s i%d", sep
,
5065 parameter_type_string (routine
->param_types
[i
]), i
+ 1);
5069 os
->type
= SUBPATTERN
;
5070 print_subroutine_start (os
, routine
->s
, routine
->pos
);
5071 print_state (os
, routine
->s
, 2, true);
5075 /* Output a routine of type TYPE that implements S. PROC_ID is the
5076 number of the subroutine associated with S, or 0 if S is the main
5080 print_subroutine (output_state
*os
, state
*s
, int proc_id
)
5082 /* For now, the top-level "recog" takes a plain "rtx", and performs a
5083 checked cast to "rtx_insn *" for use throughout the rest of the
5084 function and the code it calls. */
5085 const char *insn_param
5086 = proc_id
> 0 ? "rtx_insn *insn" : "rtx uncast_insn";
5095 printf ("static int\nrecog_%d", proc_id
);
5097 printf ("int\nrecog");
5098 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5099 "\t%s ATTRIBUTE_UNUSED,\n"
5100 "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", insn_param
);
5105 printf ("static rtx_insn *\nsplit_%d", proc_id
);
5107 printf ("rtx_insn *\nsplit_insns");
5108 printf (" (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED)\n");
5113 printf ("static rtx_insn *\npeephole2_%d", proc_id
);
5115 printf ("rtx_insn *\npeephole2_insns");
5116 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5117 "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5118 "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n");
5121 print_subroutine_start (os
, s
, &root_pos
);
5124 printf (" recog_data.insn = NULL;\n");
5125 if (os
->type
== RECOG
)
5127 printf (" rtx_insn *insn ATTRIBUTE_UNUSED;\n");
5128 printf (" insn = safe_as_a <rtx_insn *> (uncast_insn);\n");
5131 print_state (os
, s
, 2, true);
5135 /* Print out a routine of type TYPE that performs ROOT. */
5138 print_subroutine_group (output_state
*os
, routine_type type
, state
*root
)
5141 if (use_subroutines_p
)
5143 /* Split ROOT up into smaller pieces, both for readability and to
5144 help the compiler. */
5145 auto_vec
<state
*> subroutines
;
5146 find_subroutines (type
, root
, subroutines
);
5148 /* Output the subroutines (but not ROOT itself). */
5151 FOR_EACH_VEC_ELT (subroutines
, i
, s
)
5152 print_subroutine (os
, s
, i
+ 1);
5154 /* Output the main routine. */
5155 print_subroutine (os
, root
, 0);
5158 /* Return the rtx pattern for the list of rtxes in a define_peephole2. */
5161 get_peephole2_pattern (md_rtx_info
*info
)
5164 rtvec vec
= XVEC (info
->def
, 0);
5165 rtx pattern
= rtx_alloc (SEQUENCE
);
5166 XVEC (pattern
, 0) = rtvec_alloc (GET_NUM_ELEM (vec
));
5167 for (i
= j
= 0; i
< GET_NUM_ELEM (vec
); i
++)
5169 rtx x
= RTVEC_ELT (vec
, i
);
5170 /* Ignore scratch register requirements. */
5171 if (GET_CODE (x
) != MATCH_SCRATCH
&& GET_CODE (x
) != MATCH_DUP
)
5173 XVECEXP (pattern
, 0, j
) = x
;
5177 XVECLEN (pattern
, 0) = j
;
5179 error_at (info
->loc
, "empty define_peephole2");
5183 /* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
5184 rtx can be added automatically by add_clobbers. If so, update
5185 *ACCEPTANCE_PTR so that its num_clobbers field contains the number
5186 of such trailing rtxes and update *PATTERN_PTR so that it contains
5187 the pattern without those rtxes. */
5190 remove_clobbers (acceptance_type
*acceptance_ptr
, rtx
*pattern_ptr
)
5195 /* Find the last non-clobber in the parallel. */
5196 rtx pattern
= *pattern_ptr
;
5197 for (i
= XVECLEN (pattern
, 0); i
> 0; i
--)
5199 rtx x
= XVECEXP (pattern
, 0, i
- 1);
5200 if (GET_CODE (x
) != CLOBBER
5201 || (!REG_P (XEXP (x
, 0))
5202 && GET_CODE (XEXP (x
, 0)) != MATCH_SCRATCH
))
5206 if (i
== XVECLEN (pattern
, 0))
5209 /* Build a similar insn without the clobbers. */
5211 new_pattern
= XVECEXP (pattern
, 0, 0);
5214 new_pattern
= rtx_alloc (PARALLEL
);
5215 XVEC (new_pattern
, 0) = rtvec_alloc (i
);
5216 for (int j
= 0; j
< i
; ++j
)
5217 XVECEXP (new_pattern
, 0, j
) = XVECEXP (pattern
, 0, j
);
5221 acceptance_ptr
->u
.full
.u
.num_clobbers
= XVECLEN (pattern
, 0) - i
;
5222 *pattern_ptr
= new_pattern
;
5227 main (int argc
, char **argv
)
5229 state insn_root
, split_root
, peephole2_root
;
5231 progname
= "genrecog";
5233 if (!init_rtx_reader_args (argc
, argv
))
5234 return (FATAL_EXIT_CODE
);
5238 /* Read the machine description. */
5241 while (read_md_rtx (&info
))
5245 acceptance_type acceptance
;
5246 acceptance
.partial_p
= false;
5247 acceptance
.u
.full
.code
= info
.index
;
5250 switch (GET_CODE (def
))
5254 /* Match the instruction in the original .md form. */
5255 acceptance
.type
= RECOG
;
5256 acceptance
.u
.full
.u
.num_clobbers
= 0;
5257 pattern
= add_implicit_parallel (XVEC (def
, 1));
5258 validate_pattern (pattern
, &info
, NULL_RTX
, 0);
5259 match_pattern (&insn_root
, &info
, pattern
,
5260 XSTR (def
, 2), acceptance
);
5262 /* If the pattern is a PARALLEL with trailing CLOBBERs,
5263 allow recog_for_combine to match without the clobbers. */
5264 if (GET_CODE (pattern
) == PARALLEL
5265 && remove_clobbers (&acceptance
, &pattern
))
5266 match_pattern (&insn_root
, &info
, pattern
,
5267 XSTR (def
, 2), acceptance
);
5272 acceptance
.type
= SPLIT
;
5273 pattern
= add_implicit_parallel (XVEC (def
, 0));
5274 validate_pattern (pattern
, &info
, NULL_RTX
, 0);
5275 match_pattern (&split_root
, &info
, pattern
,
5276 XSTR (def
, 1), acceptance
);
5278 /* Declare the gen_split routine that we'll call if the
5279 pattern matches. The definition comes from insn-emit.c. */
5280 printf ("extern rtx_insn *gen_split_%d (rtx_insn *, rtx *);\n",
5284 case DEFINE_PEEPHOLE2
:
5285 acceptance
.type
= PEEPHOLE2
;
5286 pattern
= get_peephole2_pattern (&info
);
5287 validate_pattern (pattern
, &info
, NULL_RTX
, 0);
5288 match_pattern (&peephole2_root
, &info
, pattern
,
5289 XSTR (def
, 1), acceptance
);
5291 /* Declare the gen_peephole2 routine that we'll call if the
5292 pattern matches. The definition comes from insn-emit.c. */
5293 printf ("extern rtx_insn *gen_peephole2_%d (rtx_insn *, rtx *);\n",
5303 return FATAL_EXIT_CODE
;
5307 /* Optimize each routine in turn. */
5308 optimize_subroutine_group ("recog", &insn_root
);
5309 optimize_subroutine_group ("split_insns", &split_root
);
5310 optimize_subroutine_group ("peephole2_insns", &peephole2_root
);
5313 os
.id_to_var
.safe_grow_cleared (num_positions
);
5315 if (use_pattern_routines_p
)
5317 /* Look for common patterns and split them out into subroutines. */
5318 auto_vec
<merge_state_info
> states
;
5319 states
.safe_push (&insn_root
);
5320 states
.safe_push (&split_root
);
5321 states
.safe_push (&peephole2_root
);
5322 split_out_patterns (states
);
5324 /* Print out the routines that we just created. */
5326 pattern_routine
*routine
;
5327 FOR_EACH_VEC_ELT (patterns
, i
, routine
)
5328 print_pattern (&os
, routine
);
5331 /* Print out the matching routines. */
5332 print_subroutine_group (&os
, RECOG
, &insn_root
);
5333 print_subroutine_group (&os
, SPLIT
, &split_root
);
5334 print_subroutine_group (&os
, PEEPHOLE2
, &peephole2_root
);
5337 return (ferror (stdout
) != 0 ? FATAL_EXIT_CODE
: SUCCESS_EXIT_CODE
);