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"
115 #include "hash-table.h"
119 #undef GENERATOR_FILE
121 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM,
124 FIRST_GENERATOR_RTX_CODE
126 #define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE)
127 #define GENERATOR_FILE 1
129 /* Debugging variables to control which optimizations are performed.
130 Note that disabling merge_states_p leads to very large output. */
131 static const bool merge_states_p
= true;
132 static const bool collapse_optional_decisions_p
= true;
133 static const bool cse_tests_p
= true;
134 static const bool simplify_tests_p
= true;
135 static const bool use_operand_variables_p
= true;
136 static const bool use_subroutines_p
= true;
137 static const bool use_pattern_routines_p
= true;
139 /* Whether to add comments for optional tests that we decided to keep.
140 Can be useful when debugging the generator itself but is noise when
141 debugging the generated code. */
142 static const bool mark_optional_transitions_p
= false;
144 /* Whether pattern routines should calculate positions relative to their
145 rtx parameter rather than use absolute positions. This e.g. allows
146 a pattern routine to be shared between a plain SET and a PARALLEL
149 In principle it sounds like this should be useful, especially for
150 recog_for_combine, where the plain SET form is generated automatically
151 from a PARALLEL of a single SET and some CLOBBERs. In practice it doesn't
152 seem to help much and leads to slightly bigger object files. */
153 static const bool relative_patterns_p
= false;
155 /* Whether pattern routines should be allowed to test whether pnum_clobbers
156 is null. This requires passing pnum_clobbers around as a parameter. */
157 static const bool pattern_have_num_clobbers_p
= true;
159 /* Whether pattern routines should be allowed to test .md file C conditions.
160 This requires passing insn around as a parameter, in case the C
161 condition refers to it. In practice this tends to lead to bigger
163 static const bool pattern_c_test_p
= false;
165 /* Whether to require each parameter passed to a pattern routine to be
166 unique. Disabling this check for example allows unary operators with
167 matching modes (like NEG) and unary operators with mismatched modes
168 (like ZERO_EXTEND) to be matched by a single pattern. However, we then
169 often have cases where the same value is passed too many times. */
170 static const bool force_unique_params_p
= true;
172 /* The maximum (approximate) depth of block nesting that an individual
173 routine or subroutine should have. This limit is about keeping the
174 output readable rather than reducing compile time. */
175 static const int MAX_DEPTH
= 6;
177 /* The minimum number of pseudo-statements that a state must have before
178 we split it out into a subroutine. */
179 static const int MIN_NUM_STATEMENTS
= 5;
181 /* The number of pseudo-statements a state can have before we consider
182 splitting out substates into subroutines. This limit is about avoiding
183 compile-time problems with very big functions (and also about keeping
184 functions within --param optimization limits, etc.). */
185 static const int MAX_NUM_STATEMENTS
= 200;
187 /* The minimum number of pseudo-statements that can be used in a pattern
189 static const unsigned int MIN_COMBINE_COST
= 4;
191 /* The maximum number of arguments that a pattern routine can have.
192 The idea is to prevent one pattern getting a ridiculous number of
193 arguments when it would be more beneficial to have a separate pattern
195 static const unsigned int MAX_PATTERN_PARAMS
= 5;
197 /* The maximum operand number plus one. */
200 /* Ways of obtaining an rtx to be tested. */
202 /* PATTERN (peep2_next_insn (ARG)). */
205 /* XEXP (BASE, ARG). */
208 /* XVECEXP (BASE, 0, ARG). */
212 /* The position of an rtx relative to X0. Each useful position is
213 represented by exactly one instance of this structure. */
216 /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
217 struct position
*base
;
219 /* A position with the same BASE and TYPE, but with the next value
221 struct position
*next
;
223 /* A list of all POS_XEXP positions that use this one as their base,
224 chained by NEXT fields. The first entry represents XEXP (this, 0),
225 the second represents XEXP (this, 1), and so on. */
226 struct position
*xexps
;
228 /* A list of POS_XVECEXP0 positions that use this one as their base,
229 chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0),
230 the second represents XVECEXP (this, 0, 1), and so on. */
231 struct position
*xvecexp0s
;
233 /* The type of position. */
234 enum position_type type
;
236 /* The argument to TYPE (shown as ARG in the position_type comments). */
239 /* The instruction to which the position belongs. */
240 unsigned int insn_id
;
242 /* The depth of this position relative to the instruction pattern.
243 E.g. if the instruction pattern is a SET, the SET itself has a
244 depth of 0 while the SET_DEST and SET_SRC have depths of 1. */
247 /* A unique identifier for this position. */
252 SUBPATTERN
, RECOG
, SPLIT
, PEEPHOLE2
255 /* Next number to use as an insn_code. */
256 static int next_insn_code
;
258 /* The line number of the start of the pattern currently being processed. */
259 static int pattern_lineno
;
261 /* The root position (x0). */
262 static struct position root_pos
;
264 /* The number of positions created. Also one higher than the maximum
266 static unsigned int num_positions
= 1;
268 /* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
269 since we are given that instruction's pattern as x0. */
270 static struct position
*peep2_insn_pos_list
= &root_pos
;
272 /* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
273 points to where the unique object that represents the position
274 should be stored. Create the object if it doesn't already exist,
275 otherwise reuse the object that is already there. */
277 static struct position
*
278 next_position (struct position
**next_ptr
, struct position
*base
,
279 enum position_type type
, int arg
)
281 struct position
*pos
;
286 pos
= XCNEW (struct position
);
289 if (type
== POS_PEEP2_INSN
)
293 pos
->depth
= base
->depth
;
298 pos
->insn_id
= base
->insn_id
;
299 pos
->depth
= base
->depth
+ 1;
301 pos
->id
= num_positions
++;
307 /* Compare positions POS1 and POS2 lexicographically. */
310 compare_positions (struct position
*pos1
, struct position
*pos2
)
314 diff
= pos1
->depth
- pos2
->depth
;
318 while (pos1
->depth
!= pos2
->depth
);
322 while (pos1
->depth
!= pos2
->depth
);
325 diff
= (int) pos1
->type
- (int) pos2
->type
;
327 diff
= pos1
->arg
- pos2
->arg
;
334 /* Return the most deeply-nested position that is common to both
335 POS1 and POS2. If the positions are from different instructions,
336 return the one with the lowest insn_id. */
338 static struct position
*
339 common_position (struct position
*pos1
, struct position
*pos2
)
341 if (pos1
->insn_id
!= pos2
->insn_id
)
342 return pos1
->insn_id
< pos2
->insn_id
? pos1
: pos2
;
343 if (pos1
->depth
> pos2
->depth
)
344 std::swap (pos1
, pos2
);
345 while (pos1
->depth
!= pos2
->depth
)
355 /* Search for and return operand N, stop when reaching node STOP. */
358 find_operand (rtx pattern
, int n
, rtx stop
)
368 code
= GET_CODE (pattern
);
369 if ((code
== MATCH_SCRATCH
370 || code
== MATCH_OPERAND
371 || code
== MATCH_OPERATOR
372 || code
== MATCH_PARALLEL
)
373 && XINT (pattern
, 0) == n
)
376 fmt
= GET_RTX_FORMAT (code
);
377 len
= GET_RTX_LENGTH (code
);
378 for (i
= 0; i
< len
; i
++)
383 if ((r
= find_operand (XEXP (pattern
, i
), n
, stop
)) != NULL_RTX
)
388 if (! XVEC (pattern
, i
))
393 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
394 if ((r
= find_operand (XVECEXP (pattern
, i
, j
), n
, stop
))
399 case 'i': case 'w': case '0': case 's':
410 /* Search for and return operand M, such that it has a matching
411 constraint for operand N. */
414 find_matching_operand (rtx pattern
, int n
)
421 code
= GET_CODE (pattern
);
422 if (code
== MATCH_OPERAND
423 && (XSTR (pattern
, 2)[0] == '0' + n
424 || (XSTR (pattern
, 2)[0] == '%'
425 && XSTR (pattern
, 2)[1] == '0' + n
)))
428 fmt
= GET_RTX_FORMAT (code
);
429 len
= GET_RTX_LENGTH (code
);
430 for (i
= 0; i
< len
; i
++)
435 if ((r
= find_matching_operand (XEXP (pattern
, i
), n
)))
440 if (! XVEC (pattern
, i
))
445 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
446 if ((r
= find_matching_operand (XVECEXP (pattern
, i
, j
), n
)))
450 case 'i': case 'w': case '0': case 's':
461 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
462 don't use the MATCH_OPERAND constraint, only the predicate.
463 This is confusing to folks doing new ports, so help them
464 not make the mistake. */
467 constraints_supported_in_insn_p (rtx insn
)
469 return !(GET_CODE (insn
) == DEFINE_EXPAND
470 || GET_CODE (insn
) == DEFINE_SPLIT
471 || GET_CODE (insn
) == DEFINE_PEEPHOLE2
);
474 /* Check for various errors in patterns. SET is nonnull for a destination,
475 and is the complete set pattern. SET_CODE is '=' for normal sets, and
476 '+' within a context that requires in-out constraints. */
479 validate_pattern (rtx pattern
, rtx insn
, rtx set
, int set_code
)
486 code
= GET_CODE (pattern
);
491 const char constraints0
= XSTR (pattern
, 1)[0];
493 if (!constraints_supported_in_insn_p (insn
))
497 error_with_line (pattern_lineno
,
498 "constraints not supported in %s",
499 rtx_name
[GET_CODE (insn
)]);
504 /* If a MATCH_SCRATCH is used in a context requiring an write-only
505 or read/write register, validate that. */
508 && constraints0
!= '='
509 && constraints0
!= '+')
511 error_with_line (pattern_lineno
,
512 "operand %d missing output reload",
520 if (find_operand (insn
, XINT (pattern
, 0), pattern
) == pattern
)
521 error_with_line (pattern_lineno
,
522 "operand %i duplicated before defined",
528 const char *pred_name
= XSTR (pattern
, 1);
529 const struct pred_data
*pred
;
532 if (GET_CODE (insn
) == DEFINE_INSN
)
533 c_test
= XSTR (insn
, 2);
535 c_test
= XSTR (insn
, 1);
537 if (pred_name
[0] != 0)
539 pred
= lookup_predicate (pred_name
);
541 error_with_line (pattern_lineno
, "unknown predicate '%s'",
547 if (code
== MATCH_OPERAND
)
549 const char *constraints
= XSTR (pattern
, 2);
550 const char constraints0
= constraints
[0];
552 if (!constraints_supported_in_insn_p (insn
))
556 error_with_line (pattern_lineno
,
557 "constraints not supported in %s",
558 rtx_name
[GET_CODE (insn
)]);
562 /* A MATCH_OPERAND that is a SET should have an output reload. */
563 else if (set
&& constraints0
)
567 if (constraints0
== '+')
569 /* If we've only got an output reload for this operand,
570 we'd better have a matching input operand. */
571 else if (constraints0
== '='
572 && find_matching_operand (insn
, XINT (pattern
, 0)))
575 error_with_line (pattern_lineno
,
576 "operand %d missing in-out reload",
579 else if (constraints0
!= '=' && constraints0
!= '+')
580 error_with_line (pattern_lineno
,
581 "operand %d missing output reload",
585 /* For matching constraint in MATCH_OPERAND, the digit must be a
586 smaller number than the number of the operand that uses it in the
590 while (constraints
[0]
591 && (constraints
[0] == ' ' || constraints
[0] == ','))
596 if (constraints
[0] >= '0' && constraints
[0] <= '9')
600 sscanf (constraints
, "%d", &val
);
601 if (val
>= XINT (pattern
, 0))
602 error_with_line (pattern_lineno
,
603 "constraint digit %d is not smaller than"
605 val
, XINT (pattern
, 0));
608 while (constraints
[0] && constraints
[0] != ',')
613 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
614 while not likely to occur at runtime, results in less efficient
615 code from insn-recog.c. */
616 if (set
&& pred
&& pred
->allows_non_lvalue
)
617 error_with_line (pattern_lineno
,
618 "destination operand %d allows non-lvalue",
621 /* A modeless MATCH_OPERAND can be handy when we can check for
622 multiple modes in the c_test. In most other cases, it is a
623 mistake. Only DEFINE_INSN is eligible, since SPLIT and
624 PEEP2 can FAIL within the output pattern. Exclude special
625 predicates, which check the mode themselves. Also exclude
626 predicates that allow only constants. Exclude the SET_DEST
627 of a call instruction, as that is a common idiom. */
629 if (GET_MODE (pattern
) == VOIDmode
630 && code
== MATCH_OPERAND
631 && GET_CODE (insn
) == DEFINE_INSN
634 && pred
->allows_non_const
635 && strstr (c_test
, "operands") == NULL
637 && GET_CODE (set
) == SET
638 && GET_CODE (SET_SRC (set
)) == CALL
))
639 message_with_line (pattern_lineno
,
640 "warning: operand %d missing mode?",
647 machine_mode dmode
, smode
;
650 dest
= SET_DEST (pattern
);
651 src
= SET_SRC (pattern
);
653 /* STRICT_LOW_PART is a wrapper. Its argument is the real
654 destination, and it's mode should match the source. */
655 if (GET_CODE (dest
) == STRICT_LOW_PART
)
656 dest
= XEXP (dest
, 0);
658 /* Find the referent for a DUP. */
660 if (GET_CODE (dest
) == MATCH_DUP
661 || GET_CODE (dest
) == MATCH_OP_DUP
662 || GET_CODE (dest
) == MATCH_PAR_DUP
)
663 dest
= find_operand (insn
, XINT (dest
, 0), NULL
);
665 if (GET_CODE (src
) == MATCH_DUP
666 || GET_CODE (src
) == MATCH_OP_DUP
667 || GET_CODE (src
) == MATCH_PAR_DUP
)
668 src
= find_operand (insn
, XINT (src
, 0), NULL
);
670 dmode
= GET_MODE (dest
);
671 smode
= GET_MODE (src
);
673 /* The mode of an ADDRESS_OPERAND is the mode of the memory
674 reference, not the mode of the address. */
675 if (GET_CODE (src
) == MATCH_OPERAND
676 && ! strcmp (XSTR (src
, 1), "address_operand"))
679 /* The operands of a SET must have the same mode unless one
681 else if (dmode
!= VOIDmode
&& smode
!= VOIDmode
&& dmode
!= smode
)
682 error_with_line (pattern_lineno
,
683 "mode mismatch in set: %smode vs %smode",
684 GET_MODE_NAME (dmode
), GET_MODE_NAME (smode
));
686 /* If only one of the operands is VOIDmode, and PC or CC0 is
687 not involved, it's probably a mistake. */
688 else if (dmode
!= smode
689 && GET_CODE (dest
) != PC
690 && GET_CODE (dest
) != CC0
691 && GET_CODE (src
) != PC
692 && GET_CODE (src
) != CC0
693 && !CONST_INT_P (src
)
694 && !CONST_WIDE_INT_P (src
)
695 && GET_CODE (src
) != CALL
)
698 which
= (dmode
== VOIDmode
? "destination" : "source");
699 message_with_line (pattern_lineno
,
700 "warning: %s missing a mode?", which
);
703 if (dest
!= SET_DEST (pattern
))
704 validate_pattern (dest
, insn
, pattern
, '=');
705 validate_pattern (SET_DEST (pattern
), insn
, pattern
, '=');
706 validate_pattern (SET_SRC (pattern
), insn
, NULL_RTX
, 0);
711 validate_pattern (SET_DEST (pattern
), insn
, pattern
, '=');
715 validate_pattern (XEXP (pattern
, 0), insn
, set
, set
? '+' : 0);
716 validate_pattern (XEXP (pattern
, 1), insn
, NULL_RTX
, 0);
717 validate_pattern (XEXP (pattern
, 2), insn
, NULL_RTX
, 0);
720 case STRICT_LOW_PART
:
721 validate_pattern (XEXP (pattern
, 0), insn
, set
, set
? '+' : 0);
725 if (GET_MODE (LABEL_REF_LABEL (pattern
)) != VOIDmode
)
726 error_with_line (pattern_lineno
,
727 "operand to label_ref %smode not VOIDmode",
728 GET_MODE_NAME (GET_MODE (LABEL_REF_LABEL (pattern
))));
735 fmt
= GET_RTX_FORMAT (code
);
736 len
= GET_RTX_LENGTH (code
);
737 for (i
= 0; i
< len
; i
++)
742 validate_pattern (XEXP (pattern
, i
), insn
, NULL_RTX
, 0);
746 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
747 validate_pattern (XVECEXP (pattern
, i
, j
), insn
, NULL_RTX
, 0);
750 case 'i': case 'w': case '0': case 's':
759 /* Simple list structure for items of type T, for use when being part
760 of a list is an inherent property of T. T must have members equivalent
761 to "T *prev, *next;" and a function "void set_parent (list_head <T> *)"
762 to set the parent list. */
763 template <typename T
>
766 /* A range of linked items. */
773 void set_parent (list_head
*);
778 void push_back (range
);
779 range
remove (range
);
780 void replace (range
, range
);
781 T
*singleton () const;
786 /* Create a range [START_IN, START_IN]. */
788 template <typename T
>
789 list_head
<T
>::range::range (T
*start_in
) : start (start_in
), end (start_in
) {}
791 /* Create a range [START_IN, END_IN], linked by next and prev fields. */
793 template <typename T
>
794 list_head
<T
>::range::range (T
*start_in
, T
*end_in
)
795 : start (start_in
), end (end_in
) {}
797 template <typename T
>
799 list_head
<T
>::range::set_parent (list_head
<T
> *owner
)
801 for (T
*item
= start
; item
!= end
; item
= item
->next
)
802 item
->set_parent (owner
);
803 end
->set_parent (owner
);
806 template <typename T
>
807 list_head
<T
>::list_head () : first (0), last (0) {}
809 /* Add R to the end of the list. */
811 template <typename T
>
813 list_head
<T
>::push_back (range r
)
816 last
->next
= r
.start
;
819 r
.start
->prev
= last
;
824 /* Remove R from the list. R remains valid and can be inserted into
827 template <typename T
>
828 typename list_head
<T
>::range
829 list_head
<T
>::remove (range r
)
832 r
.start
->prev
->next
= r
.end
->next
;
836 r
.end
->next
->prev
= r
.start
->prev
;
838 last
= r
.start
->prev
;
845 /* Replace OLDR with NEWR. OLDR remains valid and can be inserted into
848 template <typename T
>
850 list_head
<T
>::replace (range oldr
, range newr
)
852 newr
.start
->prev
= oldr
.start
->prev
;
853 newr
.end
->next
= oldr
.end
->next
;
855 oldr
.start
->prev
= 0;
859 if (newr
.start
->prev
)
860 newr
.start
->prev
->next
= newr
.start
;
864 newr
.end
->next
->prev
= newr
.end
;
867 newr
.set_parent (this);
870 /* Empty the list and return the previous contents as a range that can
871 be inserted into other lists. */
873 template <typename T
>
874 typename list_head
<T
>::range
875 list_head
<T
>::release ()
877 range
r (first
, last
);
884 /* If the list contains a single item, return that item, otherwise return
887 template <typename T
>
889 list_head
<T
>::singleton () const
891 return first
== last
? first
: 0;
896 /* Describes a possible successful return from a routine. */
897 struct acceptance_type
899 /* The type of routine we're returning from. */
900 routine_type type
: 16;
902 /* True if this structure only really represents a partial match,
903 and if we must call a subroutine of type TYPE to complete the match.
904 In this case we'll call the subroutine and, if it succeeds, return
905 whatever the subroutine returned.
907 False if this structure presents a full match. */
908 unsigned int partial_p
: 1;
912 /* If PARTIAL_P, this is the number of the subroutine to call. */
915 /* Valid if !PARTIAL_P. */
918 /* The identifier of the matching pattern. For SUBPATTERNs this
919 value belongs to an ad-hoc routine-specific enum. For the
920 others it's the number of an .md file pattern. */
924 /* For RECOG, the number of clobbers that must be added to the
925 pattern in order for it to match CODE. */
928 /* For PEEPHOLE2, the number of additional instructions that were
929 included in the optimization. */
937 operator == (const acceptance_type
&a
, const acceptance_type
&b
)
939 if (a
.partial_p
!= b
.partial_p
)
942 return a
.u
.subroutine_id
== b
.u
.subroutine_id
;
944 return a
.u
.full
.code
== b
.u
.full
.code
;
948 operator != (const acceptance_type
&a
, const acceptance_type
&b
)
950 return !operator == (a
, b
);
953 /* Represents a parameter to a pattern routine. */
956 /* The C type of parameter. */
958 /* Represents an invalid parameter. */
961 /* A machine_mode parameter. */
964 /* An rtx_code parameter. */
967 /* An int parameter. */
970 /* A HOST_WIDE_INT parameter. */
975 parameter (type_enum
, bool, uint64_t);
977 /* The type of the parameter. */
980 /* True if the value passed is variable, false if it is constant. */
983 /* If IS_PARAM, this is the number of the variable passed, for an "i%d"
984 format string. If !IS_PARAM, this is the constant value passed. */
988 parameter::parameter ()
989 : type (UNSET
), is_param (false), value (0) {}
991 parameter::parameter (type_enum type_in
, bool is_param_in
, uint64_t value_in
)
992 : type (type_in
), is_param (is_param_in
), value (value_in
) {}
995 operator == (const parameter
¶m1
, const parameter
¶m2
)
997 return (param1
.type
== param2
.type
998 && param1
.is_param
== param2
.is_param
999 && param1
.value
== param2
.value
);
1003 operator != (const parameter
¶m1
, const parameter
¶m2
)
1005 return !operator == (param1
, param2
);
1008 /* Represents a routine that matches a partial rtx pattern, returning
1009 an ad-hoc enum value on success and -1 on failure. The routine can
1010 be used by any subroutine type. The match can be parameterized by
1011 things like mode, code and UNSPEC number. */
1012 struct pattern_routine
1014 /* The state that implements the pattern. */
1017 /* The deepest root position from which S can access all the rtxes it needs.
1018 This is NULL if the pattern doesn't need an rtx input, usually because
1019 all matching is done on operands[] instead. */
1022 /* A unique identifier for the routine. */
1023 unsigned int pattern_id
;
1025 /* True if the routine takes pnum_clobbers as argument. */
1026 bool pnum_clobbers_p
;
1028 /* True if the routine takes the enclosing instruction as argument. */
1031 /* The types of the other parameters to the routine, if any. */
1032 auto_vec
<parameter::type_enum
, MAX_PATTERN_PARAMS
> param_types
;
1035 /* All defined patterns. */
1036 static vec
<pattern_routine
*> patterns
;
1038 /* Represents one use of a pattern routine. */
1041 /* The pattern routine to use. */
1042 pattern_routine
*routine
;
1044 /* The values to pass as parameters. This vector has the same length
1045 as ROUTINE->PARAM_TYPES. */
1046 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
1049 /* Represents a test performed by a decision. */
1054 /* The types of test that can be performed. Most of them take as input
1055 an rtx X. Some also take as input a transition label LABEL; the others
1056 are booleans for which the transition label is always "true".
1058 The order of the enum isn't important. */
1060 /* Check GET_CODE (X) == LABEL. */
1063 /* Check GET_MODE (X) == LABEL. */
1066 /* Check XINT (X, u.opno) == LABEL. */
1069 /* Check XWINT (X, u.opno) == LABEL. */
1072 /* Check XVECLEN (X, 0) == LABEL. */
1075 /* Check peep2_current_count >= u.min_len. */
1078 /* Check XVECLEN (X, 0) >= u.min_len. */
1081 /* Check whether X is a cached const_int with value u.integer. */
1084 /* Check u.predicate.data (X, u.predicate.mode). */
1087 /* Check rtx_equal_p (X, operands[u.opno]). */
1090 /* Check whether X matches pattern u.pattern. */
1093 /* Check whether pnum_clobbers is nonnull (RECOG only). */
1096 /* Check whether general C test u.string holds. In general the condition
1097 needs access to "insn" and the full operand list. */
1100 /* Execute operands[u.opno] = X. (Always succeeds.) */
1103 /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT.
1104 May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */
1108 /* The position of rtx X in the above description, relative to the
1109 incoming instruction "insn". The position is null if the test
1110 doesn't take an X as input. */
1113 /* Which element of operands[] already contains POS, or -1 if no element
1114 is known to hold POS. */
1117 /* The type of test and its parameters, as described above. */
1130 const struct pred_data
*data
;
1131 /* True if the mode is taken from a machine_mode parameter
1132 to the routine rather than a constant machine_mode. If true,
1133 MODE is the number of the parameter (for an "i%d" format string),
1134 otherwise it is the mode itself. */
1138 pattern_use
*pattern
;
1140 acceptance_type acceptance
;
1143 static test
code (position
*);
1144 static test
mode (position
*);
1145 static test
int_field (position
*, int);
1146 static test
wide_int_field (position
*, int);
1147 static test
veclen (position
*);
1148 static test
peep2_count (int);
1149 static test
veclen_ge (position
*, int);
1150 static test
predicate (position
*, const pred_data
*, machine_mode
);
1151 static test
duplicate (position
*, int);
1152 static test
pattern (position
*, pattern_use
*);
1153 static test
have_num_clobbers ();
1154 static test
c_test (const char *);
1155 static test
set_op (position
*, int);
1156 static test
accept (const acceptance_type
&);
1158 bool terminal_p () const;
1159 bool single_outcome_p () const;
1162 test (position
*, kind_enum
);
1167 test::test (position
*pos_in
, kind_enum kind_in
)
1168 : pos (pos_in
), pos_operand (-1), kind (kind_in
) {}
1171 test::code (position
*pos
)
1173 return test (pos
, test::CODE
);
1177 test::mode (position
*pos
)
1179 return test (pos
, test::MODE
);
1183 test::int_field (position
*pos
, int opno
)
1185 test
res (pos
, test::INT_FIELD
);
1191 test::wide_int_field (position
*pos
, int opno
)
1193 test
res (pos
, test::WIDE_INT_FIELD
);
1199 test::veclen (position
*pos
)
1201 return test (pos
, test::VECLEN
);
1205 test::peep2_count (int min_len
)
1207 test
res (0, test::PEEP2_COUNT
);
1208 res
.u
.min_len
= min_len
;
1213 test::veclen_ge (position
*pos
, int min_len
)
1215 test
res (pos
, test::VECLEN_GE
);
1216 res
.u
.min_len
= min_len
;
1221 test::predicate (position
*pos
, const struct pred_data
*data
,
1224 test
res (pos
, test::PREDICATE
);
1225 res
.u
.predicate
.data
= data
;
1226 res
.u
.predicate
.mode_is_param
= false;
1227 res
.u
.predicate
.mode
= mode
;
1232 test::duplicate (position
*pos
, int opno
)
1234 test
res (pos
, test::DUPLICATE
);
1240 test::pattern (position
*pos
, pattern_use
*pattern
)
1242 test
res (pos
, test::PATTERN
);
1243 res
.u
.pattern
= pattern
;
1248 test::have_num_clobbers ()
1250 return test (0, test::HAVE_NUM_CLOBBERS
);
1254 test::c_test (const char *string
)
1256 test
res (0, test::C_TEST
);
1257 res
.u
.string
= string
;
1262 test::set_op (position
*pos
, int opno
)
1264 test
res (pos
, test::SET_OP
);
1270 test::accept (const acceptance_type
&acceptance
)
1272 test
res (0, test::ACCEPT
);
1273 res
.u
.acceptance
= acceptance
;
1277 /* Return true if the test represents an unconditionally successful match. */
1280 test::terminal_p () const
1282 return kind
== test::ACCEPT
&& u
.acceptance
.type
!= PEEPHOLE2
;
1285 /* Return true if the test is a boolean that is always true. */
1288 test::single_outcome_p () const
1290 return terminal_p () || kind
== test::SET_OP
;
1294 operator == (const test
&a
, const test
&b
)
1296 if (a
.pos
!= b
.pos
|| a
.kind
!= b
.kind
)
1303 case test::HAVE_NUM_CLOBBERS
:
1306 case test::PEEP2_COUNT
:
1307 case test::VECLEN_GE
:
1308 return a
.u
.min_len
== b
.u
.min_len
;
1310 case test::INT_FIELD
:
1311 case test::WIDE_INT_FIELD
:
1312 case test::DUPLICATE
:
1314 return a
.u
.opno
== b
.u
.opno
;
1316 case test::SAVED_CONST_INT
:
1317 return (a
.u
.integer
.is_param
== b
.u
.integer
.is_param
1318 && a
.u
.integer
.value
== b
.u
.integer
.value
);
1320 case test::PREDICATE
:
1321 return (a
.u
.predicate
.data
== b
.u
.predicate
.data
1322 && a
.u
.predicate
.mode_is_param
== b
.u
.predicate
.mode_is_param
1323 && a
.u
.predicate
.mode
== b
.u
.predicate
.mode
);
1326 return (a
.u
.pattern
->routine
== b
.u
.pattern
->routine
1327 && a
.u
.pattern
->params
== b
.u
.pattern
->params
);
1330 return strcmp (a
.u
.string
, b
.u
.string
) == 0;
1333 return a
.u
.acceptance
== b
.u
.acceptance
;
1339 operator != (const test
&a
, const test
&b
)
1341 return !operator == (a
, b
);
1344 /* A simple set of transition labels. Most transitions have a singleton
1345 label, so try to make that case as efficient as possible. */
1346 struct int_set
: public auto_vec
<uint64_t, 1>
1348 typedef uint64_t *iterator
;
1352 int_set (const int_set
&);
1354 int_set
&operator = (const int_set
&);
1360 int_set::int_set () {}
1362 int_set::int_set (uint64_t label
)
1367 int_set::int_set (const int_set
&other
)
1369 safe_splice (other
);
1373 int_set::operator = (const int_set
&other
)
1376 safe_splice (other
);
1389 return address () + length ();
1393 operator == (const int_set
&a
, const int_set
&b
)
1395 if (a
.length () != b
.length ())
1397 for (unsigned int i
= 0; i
< a
.length (); ++i
)
1404 operator != (const int_set
&a
, const int_set
&b
)
1406 return !operator == (a
, b
);
1411 /* Represents a transition between states, dependent on the result of
1415 transition (const int_set
&, state
*, bool);
1417 void set_parent (list_head
<transition
> *);
1419 /* Links to other transitions for T. Always null for boolean tests. */
1420 transition
*prev
, *next
;
1422 /* The transition should be taken when T has one of these values.
1423 E.g. for test::CODE this is a set of codes, while for booleans like
1424 test::PREDICATE it is always a singleton "true". The labels are
1425 sorted in ascending order. */
1428 /* The source decision. */
1431 /* The target state. */
1434 /* True if TO would function correctly even if TEST wasn't performed.
1435 E.g. it isn't necessary to check whether GET_MODE (x1) is SImode
1436 before calling register_operand (x1, SImode), since register_operand
1437 performs its own mode check. However, checking GET_MODE can be a cheap
1438 way of disambiguating SImode and DImode register operands. */
1441 /* True if LABELS contains parameter numbers rather than constants.
1442 E.g. if this is true for a test::CODE, the label is the number
1443 of an rtx_code parameter rather than an rtx_code itself.
1444 LABELS is always a singleton when this variable is true. */
1448 /* Represents a test and the action that should be taken on the result.
1449 If a transition exists for the test outcome, the machine switches
1450 to the transition's target state. If no suitable transition exists,
1451 the machine either falls through to the next decision or, if there are no
1452 more decisions to try, fails the match. */
1453 struct decision
: list_head
<transition
>
1455 decision (const test
&);
1457 void set_parent (list_head
<decision
> *s
);
1458 bool if_statement_p (uint64_t * = 0) const;
1460 /* The state to which this decision belongs. */
1463 /* Links to other decisions in the same state. */
1464 decision
*prev
, *next
;
1466 /* The test to perform. */
1470 /* Represents one machine state. For each state the machine tries a list
1471 of decisions, in order, and acts on the first match. It fails without
1472 further backtracking if no decisions match. */
1473 struct state
: list_head
<decision
>
1475 void set_parent (list_head
<state
> *) {}
1478 transition::transition (const int_set
&labels_in
, state
*to_in
,
1480 : prev (0), next (0), labels (labels_in
), from (0), to (to_in
),
1481 optional (optional_in
), is_param (false) {}
1483 /* Set the source decision of the transition. */
1486 transition::set_parent (list_head
<transition
> *from_in
)
1488 from
= static_cast <decision
*> (from_in
);
1491 decision::decision (const struct test
&test_in
)
1492 : prev (0), next (0), test (test_in
) {}
1494 /* Set the state to which this decision belongs. */
1497 decision::set_parent (list_head
<decision
> *s_in
)
1499 s
= static_cast <state
*> (s_in
);
1502 /* Return true if the decision has a single transition with a single label.
1503 If so, return the label in *LABEL if nonnull. */
1506 decision::if_statement_p (uint64_t *label
) const
1508 if (singleton () && first
->labels
.length () == 1)
1511 *label
= first
->labels
[0];
1517 /* Add to FROM a decision that performs TEST and has a single transition
1521 add_decision (state
*from
, const test
&test
, transition
*trans
)
1523 decision
*d
= new decision (test
);
1524 from
->push_back (d
);
1525 d
->push_back (trans
);
1528 /* Add a transition from FROM to a new, empty state that is taken
1529 when TEST == LABELS. OPTIONAL says whether the new transition
1530 should be optional. Return the new state. */
1533 add_decision (state
*from
, const test
&test
, int_set labels
, bool optional
)
1535 state
*to
= new state
;
1536 add_decision (from
, test
, new transition (labels
, to
, optional
));
1540 /* Insert a decision before decisions R to make them dependent on
1541 TEST == LABELS. OPTIONAL says whether the new transition should be
1545 insert_decision_before (state::range r
, const test
&test
,
1546 const int_set
&labels
, bool optional
)
1548 decision
*newd
= new decision (test
);
1549 state
*news
= new state
;
1550 newd
->push_back (new transition (labels
, news
, optional
));
1551 r
.start
->s
->replace (r
, newd
);
1552 news
->push_back (r
);
1556 /* Remove any optional transitions from S that turned out not to be useful. */
1559 collapse_optional_decisions (state
*s
)
1561 decision
*d
= s
->first
;
1564 decision
*next
= d
->next
;
1565 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1566 collapse_optional_decisions (trans
->to
);
1567 /* A decision with a single optional transition doesn't help
1568 partition the potential matches and so is unlikely to be
1569 worthwhile. In particular, if the decision that performs the
1570 test is the last in the state, the best it could do is reject
1571 an invalid pattern slightly earlier. If instead the decision
1572 is not the last in the state, the condition it tests could hold
1573 even for the later decisions in the state. The best it can do
1574 is save work in some cases where only the later decisions can
1577 In both cases the optional transition would add extra work to
1578 successful matches when the tested condition holds. */
1579 if (transition
*trans
= d
->singleton ())
1580 if (trans
->optional
)
1581 s
->replace (d
, trans
->to
->release ());
1586 /* Try to squash several separate tests into simpler ones. */
1589 simplify_tests (state
*s
)
1591 for (decision
*d
= s
->first
; d
; d
= d
->next
)
1594 /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N
1595 into checks for const_int_rtx[N'], if N is suitably small. */
1596 if (d
->test
.kind
== test::CODE
1597 && d
->if_statement_p (&label
)
1598 && label
== CONST_INT
)
1599 if (decision
*second
= d
->first
->to
->singleton ())
1600 if (second
->test
.kind
== test::WIDE_INT_FIELD
1601 && second
->test
.u
.opno
== 0
1602 && second
->if_statement_p (&label
)
1603 && IN_RANGE (int64_t (label
),
1604 -MAX_SAVED_CONST_INT
, MAX_SAVED_CONST_INT
))
1606 d
->test
.kind
= test::SAVED_CONST_INT
;
1607 d
->test
.u
.integer
.is_param
= false;
1608 d
->test
.u
.integer
.value
= label
;
1609 d
->replace (d
->first
, second
->release ());
1610 d
->first
->labels
[0] = true;
1612 /* If we have a CODE test followed by a PREDICATE test, rely on
1613 the predicate to test the code.
1615 This case exists for match_operators. We initially treat the
1616 CODE test for a match_operator as non-optional so that we can
1617 safely move down to its operands. It may turn out that all
1618 paths that reach that code test require the same predicate
1619 to be true. cse_tests will then put the predicate test in
1620 series with the code test. */
1621 if (d
->test
.kind
== test::CODE
)
1622 if (transition
*trans
= d
->singleton ())
1624 state
*s
= trans
->to
;
1625 while (decision
*d2
= s
->singleton ())
1627 if (d
->test
.pos
!= d2
->test
.pos
)
1629 transition
*trans2
= d2
->singleton ();
1632 if (d2
->test
.kind
== test::PREDICATE
)
1635 trans
->labels
= int_set (true);
1636 s
->replace (d2
, trans2
->to
->release ());
1642 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1643 simplify_tests (trans
->to
);
1647 /* Return true if all successful returns passing through D require the
1648 condition tested by COMMON to be true.
1650 When returning true, add all transitions like COMMON in D to WHERE.
1651 WHERE may contain a partial result on failure. */
1654 common_test_p (decision
*d
, transition
*common
, vec
<transition
*> *where
)
1656 if (d
->test
.kind
== test::ACCEPT
)
1657 /* We found a successful return that didn't require COMMON. */
1659 if (d
->test
== common
->from
->test
)
1661 transition
*trans
= d
->singleton ();
1663 || trans
->optional
!= common
->optional
1664 || trans
->labels
!= common
->labels
)
1666 where
->safe_push (trans
);
1669 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1670 for (decision
*subd
= trans
->to
->first
; subd
; subd
= subd
->next
)
1671 if (!common_test_p (subd
, common
, where
))
1676 /* Indicates that we have tested GET_CODE (X) for a particular rtx X. */
1677 const unsigned char TESTED_CODE
= 1;
1679 /* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */
1680 const unsigned char TESTED_VECLEN
= 2;
1682 /* Represents a set of conditions that are known to hold. */
1683 struct known_conditions
1685 /* A mask of TESTED_ values for each position, indexed by the position's
1687 auto_vec
<unsigned char> position_tests
;
1689 /* Index N says whether operands[N] has been set. */
1690 auto_vec
<bool> set_operands
;
1692 /* A guranteed lower bound on the value of peep2_current_count. */
1696 /* Return true if TEST can safely be performed at D, where
1697 the conditions in KC hold. TEST is known to occur along the
1698 first path from D (i.e. always following the first transition
1699 of the first decision). Any intervening tests can be used as
1700 negative proof that hoisting isn't safe, but only KC can be used
1701 as positive proof. */
1704 safe_to_hoist_p (decision
*d
, const test
&test
, known_conditions
*kc
)
1709 /* In general, C tests require everything else to have been
1710 verified and all operands to have been set up. */
1714 /* Don't accept something before all conditions have been tested. */
1717 case test::PREDICATE
:
1718 /* Don't move a predicate over a test for VECLEN_GE, since the
1719 predicate used in a match_parallel can legitimately expect the
1720 length to be checked first. */
1721 for (decision
*subd
= d
;
1723 subd
= subd
->first
->to
->first
)
1724 if (subd
->test
.pos
== test
.pos
1725 && subd
->test
.kind
== test::VECLEN_GE
)
1729 case test::DUPLICATE
:
1730 /* Don't test for a match_dup until the associated operand has
1732 if (!kc
->set_operands
[test
.u
.opno
])
1738 case test::SAVED_CONST_INT
:
1741 /* Check whether it is safe to access the rtx under test. */
1742 switch (test
.pos
->type
)
1744 case POS_PEEP2_INSN
:
1745 return test
.pos
->arg
< kc
->peep2_count
;
1748 return kc
->position_tests
[test
.pos
->base
->id
] & TESTED_CODE
;
1751 return kc
->position_tests
[test
.pos
->base
->id
] & TESTED_VECLEN
;
1755 case test::INT_FIELD
:
1756 case test::WIDE_INT_FIELD
:
1758 case test::VECLEN_GE
:
1759 /* These tests access a specific part of an rtx, so are only safe
1760 once we know what the rtx is. */
1761 return kc
->position_tests
[test
.pos
->id
] & TESTED_CODE
;
1763 case test::PEEP2_COUNT
:
1764 case test::HAVE_NUM_CLOBBERS
:
1765 /* These tests can be performed anywhere. */
1774 /* Look for a transition that is taken by all successful returns from a range
1775 of decisions starting at OUTER and that would be better performed by
1776 OUTER's state instead. On success, store all instances of that transition
1777 in WHERE and return the last decision in the range. The range could
1778 just be OUTER, or it could include later decisions as well.
1780 WITH_POSITION_P is true if only tests with position POS should be tried,
1781 false if any test should be tried. WORTHWHILE_SINGLE_P is true if the
1782 result is useful even when the range contains just a single decision
1783 with a single transition. KC are the conditions that are known to
1787 find_common_test (decision
*outer
, bool with_position_p
,
1788 position
*pos
, bool worthwhile_single_p
,
1789 known_conditions
*kc
, vec
<transition
*> *where
)
1791 /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains
1792 just a single decision is useful, regardless of the number of
1793 transitions it has. */
1794 if (!outer
->singleton ())
1795 worthwhile_single_p
= true;
1796 /* Quick exit if we don't have enough decisions to form a worthwhile
1798 if (!worthwhile_single_p
&& !outer
->next
)
1800 /* Follow the first chain down, as one example of a path that needs
1801 to contain the common test. */
1802 for (decision
*d
= outer
; d
; d
= d
->first
->to
->first
)
1804 transition
*trans
= d
->singleton ();
1806 && (!with_position_p
|| d
->test
.pos
== pos
)
1807 && safe_to_hoist_p (outer
, d
->test
, kc
))
1809 if (common_test_p (outer
, trans
, where
))
1812 /* We checked above whether the move is worthwhile. */
1814 /* See how many decisions in OUTER's chain could reuse
1816 decision
*outer_end
= outer
;
1819 unsigned int length
= where
->length ();
1820 if (!common_test_p (outer_end
->next
, trans
, where
))
1822 where
->truncate (length
);
1825 outer_end
= outer_end
->next
;
1827 while (outer_end
->next
);
1828 /* It is worth moving TRANS if it can be shared by more than
1830 if (outer_end
!= outer
|| worthwhile_single_p
)
1833 where
->truncate (0);
1839 /* Try to promote common subtests in S to a single, shared decision.
1840 Also try to bunch tests for the same position together. POS is the
1841 position of the rtx tested before reaching S. KC are the conditions
1842 that are known to hold on entry to S. */
1845 cse_tests (position
*pos
, state
*s
, known_conditions
*kc
)
1847 for (decision
*d
= s
->first
; d
; d
= d
->next
)
1849 auto_vec
<transition
*, 16> where
;
1852 /* Try to find conditions that don't depend on a particular rtx,
1853 such as pnum_clobbers != NULL or peep2_current_count >= X.
1854 It's usually better to check these conditions as soon as
1855 possible, so the change is worthwhile even if there is
1856 only one copy of the test. */
1857 decision
*endd
= find_common_test (d
, true, 0, true, kc
, &where
);
1858 if (!endd
&& d
->test
.pos
!= pos
)
1859 /* Try to find other conditions related to position POS
1860 before moving to the new position. Again, this is
1861 worthwhile even if there is only one copy of the test,
1862 since it means that fewer position variables are live
1864 endd
= find_common_test (d
, true, pos
, true, kc
, &where
);
1866 /* Try to find any condition that is used more than once. */
1867 endd
= find_common_test (d
, false, 0, false, kc
, &where
);
1870 transition
*common
= where
[0];
1871 /* Replace [D, ENDD] with a test like COMMON. We'll recurse
1872 on the common test and see the original D again next time. */
1873 d
= insert_decision_before (state::range (d
, endd
),
1877 /* Remove the old tests. */
1878 while (!where
.is_empty ())
1880 transition
*trans
= where
.pop ();
1881 trans
->from
->s
->replace (trans
->from
, trans
->to
->release ());
1886 /* Make sure that safe_to_hoist_p isn't being overly conservative.
1887 It should realize that D's test is safe in the current
1889 gcc_assert (d
->test
.kind
== test::C_TEST
1890 || d
->test
.kind
== test::ACCEPT
1891 || safe_to_hoist_p (d
, d
->test
, kc
));
1893 /* D won't be changed any further by the current optimization.
1894 Recurse with the state temporarily updated to include D. */
1896 switch (d
->test
.kind
)
1899 prev
= kc
->position_tests
[d
->test
.pos
->id
];
1900 kc
->position_tests
[d
->test
.pos
->id
] |= TESTED_CODE
;
1904 case test::VECLEN_GE
:
1905 prev
= kc
->position_tests
[d
->test
.pos
->id
];
1906 kc
->position_tests
[d
->test
.pos
->id
] |= TESTED_VECLEN
;
1910 prev
= kc
->set_operands
[d
->test
.u
.opno
];
1912 kc
->set_operands
[d
->test
.u
.opno
] = true;
1915 case test::PEEP2_COUNT
:
1916 prev
= kc
->peep2_count
;
1917 kc
->peep2_count
= MAX (prev
, d
->test
.u
.min_len
);
1923 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1924 cse_tests (d
->test
.pos
? d
->test
.pos
: pos
, trans
->to
, kc
);
1925 switch (d
->test
.kind
)
1929 case test::VECLEN_GE
:
1930 kc
->position_tests
[d
->test
.pos
->id
] = prev
;
1934 kc
->set_operands
[d
->test
.u
.opno
] = prev
;
1937 case test::PEEP2_COUNT
:
1938 kc
->peep2_count
= prev
;
1947 /* Return the type of value that can be used to parameterize test KIND,
1948 or parameter::UNSET if none. */
1950 parameter::type_enum
1951 transition_parameter_type (test::kind_enum kind
)
1956 return parameter::CODE
;
1959 return parameter::MODE
;
1961 case test::INT_FIELD
:
1964 return parameter::INT
;
1966 case test::WIDE_INT_FIELD
:
1967 return parameter::WIDE_INT
;
1969 case test::PEEP2_COUNT
:
1970 case test::VECLEN_GE
:
1971 case test::SAVED_CONST_INT
:
1972 case test::PREDICATE
:
1973 case test::DUPLICATE
:
1974 case test::HAVE_NUM_CLOBBERS
:
1978 return parameter::UNSET
;
1983 /* Initialize the pos_operand fields of each state reachable from S.
1984 If OPERAND_POS[ID] >= 0, the position with id ID is stored in
1985 operands[OPERAND_POS[ID]] on entry to S. */
1988 find_operand_positions (state
*s
, vec
<int> &operand_pos
)
1990 for (decision
*d
= s
->first
; d
; d
= d
->next
)
1992 int this_operand
= (d
->test
.pos
? operand_pos
[d
->test
.pos
->id
] : -1);
1993 if (this_operand
>= 0)
1994 d
->test
.pos_operand
= this_operand
;
1995 if (d
->test
.kind
== test::SET_OP
)
1996 operand_pos
[d
->test
.pos
->id
] = d
->test
.u
.opno
;
1997 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
1998 find_operand_positions (trans
->to
, operand_pos
);
1999 if (d
->test
.kind
== test::SET_OP
)
2000 operand_pos
[d
->test
.pos
->id
] = this_operand
;
2004 /* Statistics about a matching routine. */
2009 /* The total number of decisions in the routine, excluding trivial
2010 ones that never fail. */
2011 unsigned int num_decisions
;
2013 /* The number of non-trivial decisions on the longest path through
2014 the routine, and the return value that contributes most to that
2016 unsigned int longest_path
;
2017 int longest_path_code
;
2019 /* The maximum number of times that a single call to the routine
2020 can backtrack, and the value returned at the end of that path.
2021 "Backtracking" here means failing one decision in state and
2022 going onto to the next. */
2023 unsigned int longest_backtrack
;
2024 int longest_backtrack_code
;
2028 : num_decisions (0), longest_path (0), longest_path_code (-1),
2029 longest_backtrack (0), longest_backtrack_code (-1) {}
2031 /* Return statistics about S. */
2034 get_stats (state
*s
)
2037 unsigned int longest_path
= 0;
2038 for (decision
*d
= s
->first
; d
; d
= d
->next
)
2040 /* Work out the statistics for D. */
2042 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
2044 stats for_trans
= get_stats (trans
->to
);
2045 for_d
.num_decisions
+= for_trans
.num_decisions
;
2046 /* Each transition is mutually-exclusive, so just pick the
2047 longest of the individual paths. */
2048 if (for_d
.longest_path
<= for_trans
.longest_path
)
2050 for_d
.longest_path
= for_trans
.longest_path
;
2051 for_d
.longest_path_code
= for_trans
.longest_path_code
;
2053 /* Likewise for backtracking. */
2054 if (for_d
.longest_backtrack
<= for_trans
.longest_backtrack
)
2056 for_d
.longest_backtrack
= for_trans
.longest_backtrack
;
2057 for_d
.longest_backtrack_code
= for_trans
.longest_backtrack_code
;
2061 /* Account for D's test in its statistics. */
2062 if (!d
->test
.single_outcome_p ())
2064 for_d
.num_decisions
+= 1;
2065 for_d
.longest_path
+= 1;
2067 if (d
->test
.kind
== test::ACCEPT
)
2069 for_d
.longest_path_code
= d
->test
.u
.acceptance
.u
.full
.code
;
2070 for_d
.longest_backtrack_code
= d
->test
.u
.acceptance
.u
.full
.code
;
2073 /* Keep a running count of the number of backtracks. */
2075 for_s
.longest_backtrack
+= 1;
2077 /* Accumulate D's statistics into S's. */
2078 for_s
.num_decisions
+= for_d
.num_decisions
;
2079 for_s
.longest_path
+= for_d
.longest_path
;
2080 for_s
.longest_backtrack
+= for_d
.longest_backtrack
;
2082 /* Use the code from the decision with the longest individual path,
2083 since that's more likely to be useful if trying to make the
2084 path shorter. In the event of a tie, pick the later decision,
2085 since that's closer to the end of the path. */
2086 if (longest_path
<= for_d
.longest_path
)
2088 longest_path
= for_d
.longest_path
;
2089 for_s
.longest_path_code
= for_d
.longest_path_code
;
2092 /* Later decisions in a state are necessarily in a longer backtrack
2093 than earlier decisions. */
2094 for_s
.longest_backtrack_code
= for_d
.longest_backtrack_code
;
2099 /* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
2102 optimize_subroutine_group (const char *type
, state
*root
)
2104 /* Remove optional transitions that turned out not to be worthwhile. */
2105 if (collapse_optional_decisions_p
)
2106 collapse_optional_decisions (root
);
2108 /* Try to remove duplicated tests and to rearrange tests into a more
2112 known_conditions kc
;
2113 kc
.position_tests
.safe_grow_cleared (num_positions
);
2114 kc
.set_operands
.safe_grow_cleared (num_operands
);
2116 cse_tests (&root_pos
, root
, &kc
);
2119 /* Try to simplify two or more tests into one. */
2120 if (simplify_tests_p
)
2121 simplify_tests (root
);
2123 /* Try to use operands[] instead of xN variables. */
2124 if (use_operand_variables_p
)
2126 auto_vec
<int> operand_pos (num_positions
);
2127 for (unsigned int i
= 0; i
< num_positions
; ++i
)
2128 operand_pos
.quick_push (-1);
2129 find_operand_positions (root
, operand_pos
);
2132 /* Print a summary of the new state. */
2133 stats st
= get_stats (root
);
2134 fprintf (stderr
, "Statistics for %s:\n", type
);
2135 fprintf (stderr
, " Number of decisions: %6d\n", st
.num_decisions
);
2136 fprintf (stderr
, " longest path: %6d (code: %6d)\n",
2137 st
.longest_path
, st
.longest_path_code
);
2138 fprintf (stderr
, " longest backtrack: %6d (code: %6d)\n",
2139 st
.longest_backtrack
, st
.longest_backtrack_code
);
2142 struct merge_pattern_info
;
2144 /* Represents a transition from one pattern to another. */
2145 struct merge_pattern_transition
2147 merge_pattern_transition (merge_pattern_info
*);
2149 /* The target pattern. */
2150 merge_pattern_info
*to
;
2152 /* The parameters that the source pattern passes to the target pattern.
2153 "parameter (TYPE, true, I)" represents parameter I of the source
2155 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
2158 merge_pattern_transition::merge_pattern_transition (merge_pattern_info
*to_in
)
2163 /* Represents a pattern that can might match several states. The pattern
2164 may replace parts of the test with a parameter value. It may also
2165 replace transition labels with parameters. */
2166 struct merge_pattern_info
2168 merge_pattern_info (unsigned int);
2170 /* If PARAM_TEST_P, the state's singleton test should be generalized
2171 to use the runtime value of PARAMS[PARAM_TEST]. */
2172 unsigned int param_test
: 8;
2174 /* If PARAM_TRANSITION_P, the state's single transition label should
2175 be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */
2176 unsigned int param_transition
: 8;
2178 /* True if we have decided to generalize the root decision's test,
2179 as per PARAM_TEST. */
2180 unsigned int param_test_p
: 1;
2182 /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
2183 unsigned int param_transition_p
: 1;
2185 /* True if the contents of the structure are completely filled in. */
2186 unsigned int complete_p
: 1;
2188 /* The number of pseudo-statements in the pattern. Used to decide
2189 whether it's big enough to break out into a subroutine. */
2190 unsigned int num_statements
;
2192 /* The number of states that use this pattern. */
2193 unsigned int num_users
;
2195 /* The number of distinct success values that the pattern returns. */
2196 unsigned int num_results
;
2198 /* This array has one element for each runtime parameter to the pattern.
2199 PARAMS[I] gives the default value of parameter I, which is always
2202 These default parameters are used in cases where we match the
2203 pattern against some state S1, then add more parameters while
2204 matching against some state S2. S1 is then left passing fewer
2205 parameters than S2. The array gives us enough informatino to
2206 construct a full parameter list for S1 (see update_parameters).
2208 If we decide to create a subroutine for this pattern,
2209 PARAMS[I].type determines the C type of parameter I. */
2210 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
2212 /* All states that match this pattern must have the same number of
2213 transitions. TRANSITIONS[I] describes the subpattern for transition
2214 number I; it is null if transition I represents a successful return
2215 from the pattern. */
2216 auto_vec
<merge_pattern_transition
*, 1> transitions
;
2218 /* The routine associated with the pattern, or null if we haven't generated
2220 pattern_routine
*routine
;
2223 merge_pattern_info::merge_pattern_info (unsigned int num_transitions
)
2225 param_transition (0),
2226 param_test_p (false),
2227 param_transition_p (false),
2234 transitions
.safe_grow_cleared (num_transitions
);
2237 /* Describes one way of matching a particular state to a particular
2239 struct merge_state_result
2241 merge_state_result (merge_pattern_info
*, position
*, merge_state_result
*);
2243 /* A pattern that matches the state. */
2244 merge_pattern_info
*pattern
;
2246 /* If we decide to use this match and create a subroutine for PATTERN,
2247 the state should pass the rtx at position ROOT to the pattern's
2248 rtx parameter. A null root means that the pattern doesn't need
2249 an rtx parameter; all the rtxes it matches come from elsewhere. */
2252 /* The parameters that should be passed to PATTERN for this state.
2253 If the array is shorter than PATTERN->params, the missing entries
2254 should be taken from the corresponding element of PATTERN->params. */
2255 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params
;
2257 /* An earlier match for the same state, or null if none. Patterns
2258 matched by earlier entries are smaller than PATTERN. */
2259 merge_state_result
*prev
;
2262 merge_state_result::merge_state_result (merge_pattern_info
*pattern_in
,
2264 merge_state_result
*prev_in
)
2265 : pattern (pattern_in
), root (root_in
), prev (prev_in
)
2268 /* Information about a state, used while trying to match it against
2270 struct merge_state_info
2272 merge_state_info (state
*);
2274 /* The state itself. */
2277 /* Index I gives information about the target of transition I. */
2278 merge_state_info
*to_states
;
2280 /* The number of transitions in S. */
2281 unsigned int num_transitions
;
2283 /* True if the state has been deleted in favor of a call to a
2287 /* The previous state that might be a merge candidate for S, or null
2288 if no previous states could be merged with S. */
2289 merge_state_info
*prev_same_test
;
2291 /* A list of pattern matches for this state. */
2292 merge_state_result
*res
;
2295 merge_state_info::merge_state_info (state
*s_in
)
2298 num_transitions (0),
2303 /* True if PAT would be useful as a subroutine. */
2306 useful_pattern_p (merge_pattern_info
*pat
)
2308 return pat
->num_statements
>= MIN_COMBINE_COST
;
2311 /* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
2312 into PAT1's C routine. */
2315 same_pattern_p (merge_pattern_info
*pat1
, merge_pattern_info
*pat2
)
2317 return pat1
->num_users
== pat2
->num_users
|| !useful_pattern_p (pat2
);
2320 /* PAT was previously matched against SINFO based on tentative matches
2321 for the target states of SINFO's state. Return true if the match
2322 still holds; that is, if the target states of SINFO's state still
2323 match the corresponding transitions of PAT. */
2326 valid_result_p (merge_pattern_info
*pat
, merge_state_info
*sinfo
)
2328 for (unsigned int j
= 0; j
< sinfo
->num_transitions
; ++j
)
2329 if (merge_pattern_transition
*ptrans
= pat
->transitions
[j
])
2331 merge_state_result
*to_res
= sinfo
->to_states
[j
].res
;
2332 if (!to_res
|| to_res
->pattern
!= ptrans
->to
)
2338 /* Remove any matches that are no longer valid from the head of SINFO's
2342 prune_invalid_results (merge_state_info
*sinfo
)
2344 while (sinfo
->res
&& !valid_result_p (sinfo
->res
->pattern
, sinfo
))
2346 sinfo
->res
= sinfo
->res
->prev
;
2347 gcc_assert (sinfo
->res
);
2351 /* Return true if PAT represents the biggest posssible match for SINFO;
2352 that is, if the next action of SINFO's state on return from PAT will
2353 be something that cannot be merged with any other state. */
2356 complete_result_p (merge_pattern_info
*pat
, merge_state_info
*sinfo
)
2358 for (unsigned int j
= 0; j
< sinfo
->num_transitions
; ++j
)
2359 if (sinfo
->to_states
[j
].res
&& !pat
->transitions
[j
])
2364 /* Update TO for any parameters that have been added to FROM since TO
2365 was last set. The extra parameters in FROM will be constants or
2366 instructions to duplicate earlier parameters. */
2369 update_parameters (vec
<parameter
> &to
, const vec
<parameter
> &from
)
2371 for (unsigned int i
= to
.length (); i
< from
.length (); ++i
)
2372 to
.quick_push (from
[i
]);
2375 /* Return true if A and B can be tested by a single test. If the test
2376 can be parameterised, store the parameter value for A in *PARAMA and
2377 the parameter value for B in *PARAMB, otherwise leave PARAMA and
2381 compatible_tests_p (const test
&a
, const test
&b
,
2382 parameter
*parama
, parameter
*paramb
)
2384 if (a
.kind
!= b
.kind
)
2388 case test::PREDICATE
:
2389 if (a
.u
.predicate
.data
!= b
.u
.predicate
.data
)
2391 *parama
= parameter (parameter::MODE
, false, a
.u
.predicate
.mode
);
2392 *paramb
= parameter (parameter::MODE
, false, b
.u
.predicate
.mode
);
2395 case test::SAVED_CONST_INT
:
2396 *parama
= parameter (parameter::INT
, false, a
.u
.integer
.value
);
2397 *paramb
= parameter (parameter::INT
, false, b
.u
.integer
.value
);
2405 /* PARAMS is an array of the parameters that a state is going to pass
2406 to a pattern routine. It is still incomplete; index I has a kind of
2407 parameter::UNSET if we don't yet know what the state will pass
2408 as parameter I. Try to make parameter ID equal VALUE, returning
2412 set_parameter (vec
<parameter
> ¶ms
, unsigned int id
,
2413 const parameter
&value
)
2415 if (params
[id
].type
== parameter::UNSET
)
2417 if (force_unique_params_p
)
2418 for (unsigned int i
= 0; i
< params
.length (); ++i
)
2419 if (params
[i
] == value
)
2424 return params
[id
] == value
;
2427 /* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
2428 set of parameters that a particular state is going to pass to
2431 Try to extend PARAMS1 and PARAMS2 so that there is a parameter
2432 that is equal to PARAM1 for the state and has a default value of
2433 PARAM2. Parameters beginning at START were added as part of the
2434 same match and so may be reused. */
2437 add_parameter (vec
<parameter
> ¶ms1
, vec
<parameter
> ¶ms2
,
2438 const parameter
¶m1
, const parameter
¶m2
,
2439 unsigned int start
, unsigned int *res
)
2441 gcc_assert (params1
.length () == params2
.length ());
2442 gcc_assert (!param1
.is_param
&& !param2
.is_param
);
2444 for (unsigned int i
= start
; i
< params2
.length (); ++i
)
2445 if (params1
[i
] == param1
&& params2
[i
] == param2
)
2451 if (force_unique_params_p
)
2452 for (unsigned int i
= 0; i
< params2
.length (); ++i
)
2453 if (params1
[i
] == param1
|| params2
[i
] == param2
)
2456 if (params2
.length () >= MAX_PATTERN_PARAMS
)
2459 *res
= params2
.length ();
2460 params1
.quick_push (param1
);
2461 params2
.quick_push (param2
);
2465 /* If *ROOTA is nonnull, return true if the same sequence of steps are
2466 required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA
2467 is null, update it if necessary in order to make the condition hold. */
2470 merge_relative_positions (position
**roota
, position
*a
,
2471 position
*rootb
, position
*b
)
2473 if (!relative_patterns_p
)
2482 return *roota
== rootb
;
2484 /* If B does not belong to the same instruction as ROOTB, we don't
2485 start with ROOTB but instead start with a call to peep2_next_insn.
2486 In that case the sequences for B and A are identical iff B and A
2487 are themselves identical. */
2488 if (rootb
->insn_id
!= b
->insn_id
)
2492 if (!a
|| b
->type
!= a
->type
|| b
->arg
!= a
->arg
)
2502 /* A hasher of states that treats two states as "equal" if they might be
2503 merged (but trying to be more discriminating than "return true"). */
2504 struct test_pattern_hasher
: typed_noop_remove
<merge_state_info
>
2506 typedef merge_state_info
*value_type
;
2507 typedef merge_state_info
*compare_type
;
2508 static inline hashval_t
hash (const value_type
&);
2509 static inline bool equal (const value_type
&, const compare_type
&);
2513 test_pattern_hasher::hash (merge_state_info
*const &sinfo
)
2516 decision
*d
= sinfo
->s
->singleton ();
2517 h
.add_int (d
->test
.pos_operand
+ 1);
2518 if (!relative_patterns_p
)
2519 h
.add_int (d
->test
.pos
? d
->test
.pos
->id
+ 1 : 0);
2520 h
.add_int (d
->test
.kind
);
2521 h
.add_int (sinfo
->num_transitions
);
2526 test_pattern_hasher::equal (merge_state_info
*const &sinfo1
,
2527 merge_state_info
*const &sinfo2
)
2529 decision
*d1
= sinfo1
->s
->singleton ();
2530 decision
*d2
= sinfo2
->s
->singleton ();
2531 gcc_assert (d1
&& d2
);
2533 parameter new_param1
, new_param2
;
2534 return (d1
->test
.pos_operand
== d2
->test
.pos_operand
2535 && (relative_patterns_p
|| d1
->test
.pos
== d2
->test
.pos
)
2536 && compatible_tests_p (d1
->test
, d2
->test
, &new_param1
, &new_param2
)
2537 && sinfo1
->num_transitions
== sinfo2
->num_transitions
);
2540 /* Try to make the state described by SINFO1 use the same pattern as the
2541 state described by SINFO2. Return true on success.
2543 SINFO1 and SINFO2 are known to have the same hash value. */
2546 merge_patterns (merge_state_info
*sinfo1
, merge_state_info
*sinfo2
)
2548 merge_state_result
*res2
= sinfo2
->res
;
2549 merge_pattern_info
*pat
= res2
->pattern
;
2551 /* Write to temporary arrays while matching, in case we have to abort
2552 half way through. */
2553 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params1
;
2554 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> params2
;
2555 params1
.quick_grow_cleared (pat
->params
.length ());
2556 params2
.splice (pat
->params
);
2557 unsigned int start_param
= params2
.length ();
2559 /* An array for recording changes to PAT->transitions[?].params.
2560 All changes involve replacing a constant parameter with some
2561 PAT->params[N], where N is the second element of the pending_param. */
2562 typedef std::pair
<parameter
*, unsigned int> pending_param
;
2563 auto_vec
<pending_param
, 32> pending_params
;
2565 decision
*d1
= sinfo1
->s
->singleton ();
2566 decision
*d2
= sinfo2
->s
->singleton ();
2567 gcc_assert (d1
&& d2
);
2569 /* If D2 tests a position, SINFO1's root relative to D1 is the same
2570 as SINFO2's root relative to D2. */
2571 position
*root1
= 0;
2572 position
*root2
= res2
->root
;
2573 if (d2
->test
.pos_operand
< 0
2575 && !merge_relative_positions (&root1
, d1
->test
.pos
,
2576 root2
, d2
->test
.pos
))
2579 /* Check whether the patterns have the same shape. */
2580 unsigned int num_transitions
= sinfo1
->num_transitions
;
2581 gcc_assert (num_transitions
== sinfo2
->num_transitions
);
2582 for (unsigned int i
= 0; i
< num_transitions
; ++i
)
2583 if (merge_pattern_transition
*ptrans
= pat
->transitions
[i
])
2585 merge_state_result
*to1_res
= sinfo1
->to_states
[i
].res
;
2586 merge_state_result
*to2_res
= sinfo2
->to_states
[i
].res
;
2587 merge_pattern_info
*to_pat
= ptrans
->to
;
2588 gcc_assert (to2_res
&& to2_res
->pattern
== to_pat
);
2589 if (!to1_res
|| to1_res
->pattern
!= to_pat
)
2592 && !merge_relative_positions (&root1
, to1_res
->root
,
2593 root2
, to2_res
->root
))
2595 /* Match the parameters that TO1_RES passes to TO_PAT with the
2596 parameters that PAT passes to TO_PAT. */
2597 update_parameters (to1_res
->params
, to_pat
->params
);
2598 for (unsigned int j
= 0; j
< to1_res
->params
.length (); ++j
)
2600 const parameter
¶m1
= to1_res
->params
[j
];
2601 const parameter
¶m2
= ptrans
->params
[j
];
2602 gcc_assert (!param1
.is_param
);
2603 if (param2
.is_param
)
2605 if (!set_parameter (params1
, param2
.value
, param1
))
2608 else if (param1
!= param2
)
2611 if (!add_parameter (params1
, params2
,
2612 param1
, param2
, start_param
, &id
))
2614 /* Record that PAT should now pass parameter ID to TO_PAT,
2615 instead of the current contents of *PARAM2. We only
2616 make the change if the rest of the match succeeds. */
2617 pending_params
.safe_push
2618 (pending_param (&ptrans
->params
[j
], id
));
2623 unsigned int param_test
= pat
->param_test
;
2624 unsigned int param_transition
= pat
->param_transition
;
2625 bool param_test_p
= pat
->param_test_p
;
2626 bool param_transition_p
= pat
->param_transition_p
;
2628 /* If the tests don't match exactly, try to parameterize them. */
2629 parameter new_param1
, new_param2
;
2630 if (!compatible_tests_p (d1
->test
, d2
->test
, &new_param1
, &new_param2
))
2632 if (new_param1
.type
!= parameter::UNSET
)
2634 /* If the test has not already been parameterized, all existing
2635 matches use constant NEW_PARAM2. */
2638 if (!set_parameter (params1
, param_test
, new_param1
))
2641 else if (new_param1
!= new_param2
)
2643 if (!add_parameter (params1
, params2
, new_param1
, new_param2
,
2644 start_param
, ¶m_test
))
2646 param_test_p
= true;
2650 /* Match the transitions. */
2651 transition
*trans1
= d1
->first
;
2652 transition
*trans2
= d2
->first
;
2653 for (unsigned int i
= 0; i
< num_transitions
; ++i
)
2655 if (param_transition_p
|| trans1
->labels
!= trans2
->labels
)
2657 /* We can only generalize a single transition with a single
2659 if (num_transitions
!= 1
2660 || trans1
->labels
.length () != 1
2661 || trans2
->labels
.length () != 1)
2664 /* Although we can match wide-int fields, in practice it leads
2665 to some odd results for const_vectors. We end up
2666 parameterizing the first N const_ints of the vector
2667 and then (once we reach the maximum number of parameters)
2668 we go on to match the other elements exactly. */
2669 if (d1
->test
.kind
== test::WIDE_INT_FIELD
)
2672 /* See whether the label has a generalizable type. */
2673 parameter::type_enum param_type
2674 = transition_parameter_type (d1
->test
.kind
);
2675 if (param_type
== parameter::UNSET
)
2678 /* Match the labels using parameters. */
2679 new_param1
= parameter (param_type
, false, trans1
->labels
[0]);
2680 if (param_transition_p
)
2682 if (!set_parameter (params1
, param_transition
, new_param1
))
2687 new_param2
= parameter (param_type
, false, trans2
->labels
[0]);
2688 if (!add_parameter (params1
, params2
, new_param1
, new_param2
,
2689 start_param
, ¶m_transition
))
2691 param_transition_p
= true;
2694 trans1
= trans1
->next
;
2695 trans2
= trans2
->next
;
2698 /* Set any unset parameters to their default values. This occurs if some
2699 other state needed something to be parameterized in order to match SINFO2,
2700 but SINFO1 on its own does not. */
2701 for (unsigned int i
= 0; i
< params1
.length (); ++i
)
2702 if (params1
[i
].type
== parameter::UNSET
)
2703 params1
[i
] = params2
[i
];
2705 /* The match was successful. Commit all pending changes to PAT. */
2706 update_parameters (pat
->params
, params2
);
2710 FOR_EACH_VEC_ELT (pending_params
, i
, pp
)
2711 *pp
->first
= parameter (pp
->first
->type
, true, pp
->second
);
2713 pat
->param_test
= param_test
;
2714 pat
->param_transition
= param_transition
;
2715 pat
->param_test_p
= param_test_p
;
2716 pat
->param_transition_p
= param_transition_p
;
2718 /* Record the match of SINFO1. */
2719 merge_state_result
*new_res1
= new merge_state_result (pat
, root1
,
2721 new_res1
->params
.splice (params1
);
2722 sinfo1
->res
= new_res1
;
2726 /* The number of states that were removed by calling pattern routines. */
2727 static unsigned int pattern_use_states
;
2729 /* The number of states used while defining pattern routines. */
2730 static unsigned int pattern_def_states
;
2732 /* Information used while constructing a use or definition of a pattern
2734 struct create_pattern_info
2736 /* The routine itself. */
2737 pattern_routine
*routine
;
2739 /* The first unclaimed return value for this particular use or definition.
2740 We walk the substates of uses and definitions in the same order
2741 so each return value always refers to the same position within
2743 unsigned int next_result
;
2746 static void populate_pattern_routine (create_pattern_info
*,
2747 merge_state_info
*, state
*,
2748 const vec
<parameter
> &);
2750 /* SINFO matches a pattern for which we've decided to create a C routine.
2751 Return a decision that performs a call to the pattern routine,
2752 but leave the caller to add the transitions to it. Initialize CPI
2753 for this purpose. Also create a definition for the pattern routine,
2754 if it doesn't already have one.
2756 PARAMS are the parameters that SINFO passes to its pattern. */
2759 init_pattern_use (create_pattern_info
*cpi
, merge_state_info
*sinfo
,
2760 const vec
<parameter
> ¶ms
)
2762 state
*s
= sinfo
->s
;
2763 merge_state_result
*res
= sinfo
->res
;
2764 merge_pattern_info
*pat
= res
->pattern
;
2765 cpi
->routine
= pat
->routine
;
2768 /* We haven't defined the pattern routine yet, so create
2769 a definition now. */
2770 pattern_routine
*routine
= new pattern_routine
;
2771 pat
->routine
= routine
;
2772 cpi
->routine
= routine
;
2773 routine
->s
= new state
;
2774 routine
->insn_p
= false;
2775 routine
->pnum_clobbers_p
= false;
2777 /* Create an "idempotent" mapping of parameter I to parameter I.
2778 Also record the C type of each parameter to the routine. */
2779 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> def_params
;
2780 for (unsigned int i
= 0; i
< pat
->params
.length (); ++i
)
2782 def_params
.quick_push (parameter (pat
->params
[i
].type
, true, i
));
2783 routine
->param_types
.quick_push (pat
->params
[i
].type
);
2786 /* Any of the states that match the pattern could be used to
2787 create the routine definition. We might as well use SINFO
2788 since it's already to hand. This means that all positions
2789 in the definition will be relative to RES->root. */
2790 routine
->pos
= res
->root
;
2791 cpi
->next_result
= 0;
2792 populate_pattern_routine (cpi
, sinfo
, routine
->s
, def_params
);
2793 gcc_assert (cpi
->next_result
== pat
->num_results
);
2795 /* Add the routine to the global list, after the subroutines
2797 routine
->pattern_id
= patterns
.length ();
2798 patterns
.safe_push (routine
);
2801 /* Create a decision to call the routine, passing PARAMS to it. */
2802 pattern_use
*use
= new pattern_use
;
2803 use
->routine
= pat
->routine
;
2804 use
->params
.splice (params
);
2805 decision
*d
= new decision (test::pattern (res
->root
, use
));
2807 /* If the original decision could use an element of operands[] instead
2808 of an rtx variable, try to transfer it to the new decision. */
2809 if (s
->first
->test
.pos
&& res
->root
== s
->first
->test
.pos
)
2810 d
->test
.pos_operand
= s
->first
->test
.pos_operand
;
2812 cpi
->next_result
= 0;
2816 /* Make S return the next unclaimed pattern routine result for CPI. */
2819 add_pattern_acceptance (create_pattern_info
*cpi
, state
*s
)
2821 acceptance_type acceptance
;
2822 acceptance
.type
= SUBPATTERN
;
2823 acceptance
.partial_p
= false;
2824 acceptance
.u
.full
.code
= cpi
->next_result
;
2825 add_decision (s
, test::accept (acceptance
), true, false);
2826 cpi
->next_result
+= 1;
2829 /* Initialize new empty state NEWS so that it implements SINFO's pattern
2830 (here referred to as "P"). P may be the top level of a pattern routine
2831 or a subpattern that should be inlined into its parent pattern's routine
2832 (as per same_pattern_p). The choice of SINFO for a top-level pattern is
2833 arbitrary; it could be any of the states that use P. The choice for
2834 subpatterns follows the choice for the parent pattern.
2836 PARAMS gives the value of each parameter to P in terms of the parameters
2837 to the top-level pattern. If P itself is the top level pattern, PARAMS[I]
2838 is always "parameter (TYPE, true, I)". */
2841 populate_pattern_routine (create_pattern_info
*cpi
, merge_state_info
*sinfo
,
2842 state
*news
, const vec
<parameter
> ¶ms
)
2844 pattern_def_states
+= 1;
2846 decision
*d
= sinfo
->s
->singleton ();
2847 merge_pattern_info
*pat
= sinfo
->res
->pattern
;
2848 pattern_routine
*routine
= cpi
->routine
;
2850 /* Create a copy of D's test for the pattern routine and generalize it
2852 decision
*newd
= new decision (d
->test
);
2853 gcc_assert (newd
->test
.pos_operand
>= 0
2855 || common_position (newd
->test
.pos
,
2856 routine
->pos
) == routine
->pos
);
2857 if (pat
->param_test_p
)
2859 const parameter
¶m
= params
[pat
->param_test
];
2860 switch (newd
->test
.kind
)
2862 case test::PREDICATE
:
2863 newd
->test
.u
.predicate
.mode_is_param
= param
.is_param
;
2864 newd
->test
.u
.predicate
.mode
= param
.value
;
2867 case test::SAVED_CONST_INT
:
2868 newd
->test
.u
.integer
.is_param
= param
.is_param
;
2869 newd
->test
.u
.integer
.value
= param
.value
;
2877 if (d
->test
.kind
== test::C_TEST
)
2878 routine
->insn_p
= true;
2879 else if (d
->test
.kind
== test::HAVE_NUM_CLOBBERS
)
2880 routine
->pnum_clobbers_p
= true;
2881 news
->push_back (newd
);
2883 /* Fill in the transitions of NEWD. */
2885 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
2887 /* Create a new state to act as the target of the new transition. */
2888 state
*to_news
= new state
;
2889 if (merge_pattern_transition
*ptrans
= pat
->transitions
[i
])
2891 /* The pattern hasn't finished matching yet. Get the target
2892 pattern and the corresponding target state of SINFO. */
2893 merge_pattern_info
*to_pat
= ptrans
->to
;
2894 merge_state_info
*to
= sinfo
->to_states
+ i
;
2895 gcc_assert (to
->res
->pattern
== to_pat
);
2896 gcc_assert (ptrans
->params
.length () == to_pat
->params
.length ());
2898 /* Express the parameters to TO_PAT in terms of the parameters
2899 to the top-level pattern. */
2900 auto_vec
<parameter
, MAX_PATTERN_PARAMS
> to_params
;
2901 for (unsigned int j
= 0; j
< ptrans
->params
.length (); ++j
)
2903 const parameter
¶m
= ptrans
->params
[j
];
2904 to_params
.quick_push (param
.is_param
2905 ? params
[param
.value
]
2909 if (same_pattern_p (pat
, to_pat
))
2910 /* TO_PAT is part of the current routine, so just recurse. */
2911 populate_pattern_routine (cpi
, to
, to_news
, to_params
);
2914 /* TO_PAT should be matched by calling a separate routine. */
2915 create_pattern_info sub_cpi
;
2916 decision
*subd
= init_pattern_use (&sub_cpi
, to
, to_params
);
2917 routine
->insn_p
|= sub_cpi
.routine
->insn_p
;
2918 routine
->pnum_clobbers_p
|= sub_cpi
.routine
->pnum_clobbers_p
;
2920 /* Add the pattern routine call to the new target state. */
2921 to_news
->push_back (subd
);
2923 /* Add a transition for each successful call result. */
2924 for (unsigned int j
= 0; j
< to_pat
->num_results
; ++j
)
2926 state
*res
= new state
;
2927 add_pattern_acceptance (cpi
, res
);
2928 subd
->push_back (new transition (j
, res
, false));
2933 /* This transition corresponds to a successful match. */
2934 add_pattern_acceptance (cpi
, to_news
);
2936 /* Create the transition itself, generalizing as necessary. */
2937 transition
*new_trans
= new transition (trans
->labels
, to_news
,
2939 if (pat
->param_transition_p
)
2941 const parameter
¶m
= params
[pat
->param_transition
];
2942 new_trans
->is_param
= param
.is_param
;
2943 new_trans
->labels
[0] = param
.value
;
2945 newd
->push_back (new_trans
);
2950 /* USE is a decision that calls a pattern routine and SINFO is part of the
2951 original state tree that the call is supposed to replace. Add the
2952 transitions for SINFO and its substates to USE. */
2955 populate_pattern_use (create_pattern_info
*cpi
, decision
*use
,
2956 merge_state_info
*sinfo
)
2958 pattern_use_states
+= 1;
2959 gcc_assert (!sinfo
->merged_p
);
2960 sinfo
->merged_p
= true;
2961 merge_state_result
*res
= sinfo
->res
;
2962 merge_pattern_info
*pat
= res
->pattern
;
2963 decision
*d
= sinfo
->s
->singleton ();
2965 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
2967 if (pat
->transitions
[i
])
2968 /* The target state is also part of the pattern. */
2969 populate_pattern_use (cpi
, use
, sinfo
->to_states
+ i
);
2972 /* The transition corresponds to a successful return from the
2974 use
->push_back (new transition (cpi
->next_result
, trans
->to
, false));
2975 cpi
->next_result
+= 1;
2981 /* We have decided to replace SINFO's state with a call to a pattern
2982 routine. Make the change, creating a definition of the pattern routine
2983 if it doesn't have one already. */
2986 use_pattern (merge_state_info
*sinfo
)
2988 merge_state_result
*res
= sinfo
->res
;
2989 merge_pattern_info
*pat
= res
->pattern
;
2990 state
*s
= sinfo
->s
;
2992 /* The pattern may have acquired new parameters after it was matched
2993 against SINFO. Update the parameters that SINFO passes accordingly. */
2994 update_parameters (res
->params
, pat
->params
);
2996 create_pattern_info cpi
;
2997 decision
*d
= init_pattern_use (&cpi
, sinfo
, res
->params
);
2998 populate_pattern_use (&cpi
, d
, sinfo
);
3003 /* Look through the state trees in STATES for common patterns and
3004 split them into subroutines. */
3007 split_out_patterns (vec
<merge_state_info
> &states
)
3009 unsigned int first_transition
= states
.length ();
3010 hash_table
<test_pattern_hasher
> hashtab (128);
3011 /* Stage 1: Create an order in which parent states come before their child
3012 states and in which sibling states are at consecutive locations.
3013 Having consecutive sibling states allows merge_state_info to have
3014 a single to_states pointer. */
3015 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3016 for (decision
*d
= states
[i
].s
->first
; d
; d
= d
->next
)
3017 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
3019 states
.safe_push (trans
->to
);
3020 states
[i
].num_transitions
+= 1;
3022 /* Stage 2: Now that the addresses are stable, set up the to_states
3023 pointers. Look for states that might be merged and enter them
3024 into the hash table. */
3025 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3027 merge_state_info
*sinfo
= &states
[i
];
3028 if (sinfo
->num_transitions
)
3030 sinfo
->to_states
= &states
[first_transition
];
3031 first_transition
+= sinfo
->num_transitions
;
3033 /* For simplicity, we only try to merge states that have a single
3034 decision. This is in any case the best we can do for peephole2,
3035 since whether a peephole2 ACCEPT succeeds or not depends on the
3036 specific peephole2 pattern (which is unique to each ACCEPT
3037 and so couldn't be shared between states). */
3038 if (decision
*d
= sinfo
->s
->singleton ())
3039 /* ACCEPT states are unique, so don't even try to merge them. */
3040 if (d
->test
.kind
!= test::ACCEPT
3041 && (pattern_have_num_clobbers_p
3042 || d
->test
.kind
!= test::HAVE_NUM_CLOBBERS
)
3043 && (pattern_c_test_p
3044 || d
->test
.kind
!= test::C_TEST
))
3046 merge_state_info
**slot
= hashtab
.find_slot (sinfo
, INSERT
);
3047 sinfo
->prev_same_test
= *slot
;
3051 /* Stage 3: Walk backwards through the list of states and try to merge
3052 them. This is a greedy, bottom-up match; parent nodes can only start
3053 a new leaf pattern if they fail to match when combined with all child
3054 nodes that have matching patterns.
3056 For each state we keep a list of potential matches, with each
3057 potential match being larger (and deeper) than the next match in
3058 the list. The final element in the list is a leaf pattern that
3059 matches just a single state.
3061 Each candidate pattern created in this loop is unique -- it won't
3062 have been seen by an earlier iteration. We try to match each pattern
3063 with every state that appears earlier in STATES.
3065 Because the patterns created in the loop are unique, any state
3066 that already has a match must have a final potential match that
3067 is different from any new leaf pattern. Therefore, when matching
3068 leaf patterns, we need only consider states whose list of matches
3071 The non-leaf patterns that we try are as deep as possible
3072 and are an extension of the state's previous best candidate match (PB).
3073 We need only consider states whose current potential match is also PB;
3074 any states that don't match as much as PB cannnot match the new pattern,
3075 while any states that already match more than PB must be different from
3077 for (unsigned int i2
= states
.length (); i2
-- > 0; )
3079 merge_state_info
*sinfo2
= &states
[i2
];
3081 /* Enforce the bottom-upness of the match: remove matches with later
3082 states if SINFO2's child states ended up finding a better match. */
3083 prune_invalid_results (sinfo2
);
3085 /* Do nothing if the state doesn't match a later one and if there are
3086 no earlier states it could match. */
3087 if (!sinfo2
->res
&& !sinfo2
->prev_same_test
)
3090 merge_state_result
*res2
= sinfo2
->res
;
3091 decision
*d2
= sinfo2
->s
->singleton ();
3092 position
*root2
= (d2
->test
.pos_operand
< 0 ? d2
->test
.pos
: 0);
3093 unsigned int num_transitions
= sinfo2
->num_transitions
;
3095 /* If RES2 is null then SINFO2's test in isolation has not been seen
3096 before. First try matching that on its own. */
3099 merge_pattern_info
*new_pat
3100 = new merge_pattern_info (num_transitions
);
3101 merge_state_result
*new_res2
3102 = new merge_state_result (new_pat
, root2
, res2
);
3103 sinfo2
->res
= new_res2
;
3105 new_pat
->num_statements
= !d2
->test
.single_outcome_p ();
3106 new_pat
->num_results
= num_transitions
;
3107 bool matched_p
= false;
3108 /* Look for states that don't currently match anything but
3109 can be made to match SINFO2 on its own. */
3110 for (merge_state_info
*sinfo1
= sinfo2
->prev_same_test
; sinfo1
;
3111 sinfo1
= sinfo1
->prev_same_test
)
3112 if (!sinfo1
->res
&& merge_patterns (sinfo1
, sinfo2
))
3116 /* No other states match. */
3126 /* Keep the existing pattern if it's as good as anything we'd
3127 create for SINFO2. */
3128 if (complete_result_p (res2
->pattern
, sinfo2
))
3130 res2
->pattern
->num_users
+= 1;
3134 /* Create a new pattern for SINFO2. */
3135 merge_pattern_info
*new_pat
= new merge_pattern_info (num_transitions
);
3136 merge_state_result
*new_res2
3137 = new merge_state_result (new_pat
, root2
, res2
);
3138 sinfo2
->res
= new_res2
;
3140 /* Fill in details about the pattern. */
3141 new_pat
->num_statements
= !d2
->test
.single_outcome_p ();
3142 new_pat
->num_results
= 0;
3143 for (unsigned int j
= 0; j
< num_transitions
; ++j
)
3144 if (merge_state_result
*to_res
= sinfo2
->to_states
[j
].res
)
3146 /* Count the target state as part of this pattern.
3147 First update the root position so that it can reach
3148 the target state's root. */
3152 new_res2
->root
= common_position (new_res2
->root
,
3155 new_res2
->root
= to_res
->root
;
3157 merge_pattern_info
*to_pat
= to_res
->pattern
;
3158 merge_pattern_transition
*ptrans
3159 = new merge_pattern_transition (to_pat
);
3161 /* TO_PAT may have acquired more parameters when matching
3162 states earlier in STATES than TO_RES's, but the list is
3163 now final. Make sure that TO_RES is up to date. */
3164 update_parameters (to_res
->params
, to_pat
->params
);
3166 /* Start out by assuming that every user of NEW_PAT will
3167 want to pass the same (constant) parameters as TO_RES. */
3168 update_parameters (ptrans
->params
, to_res
->params
);
3170 new_pat
->transitions
[j
] = ptrans
;
3171 new_pat
->num_statements
+= to_pat
->num_statements
;
3172 new_pat
->num_results
+= to_pat
->num_results
;
3175 /* The target state doesn't match anything and so is not part
3177 new_pat
->num_results
+= 1;
3179 /* See if any earlier states that match RES2's pattern also match
3181 bool matched_p
= false;
3182 for (merge_state_info
*sinfo1
= sinfo2
->prev_same_test
; sinfo1
;
3183 sinfo1
= sinfo1
->prev_same_test
)
3185 prune_invalid_results (sinfo1
);
3187 && sinfo1
->res
->pattern
== res2
->pattern
3188 && merge_patterns (sinfo1
, sinfo2
))
3193 /* Nothing else matches NEW_PAT, so go back to the previous
3194 pattern (possibly just a single-state one). */
3199 /* Assume that SINFO2 will use RES. At this point we don't know
3200 whether earlier states that match the same pattern will use
3201 that match or a different one. */
3202 sinfo2
->res
->pattern
->num_users
+= 1;
3204 /* Step 4: Finalize the choice of pattern for each state, ignoring
3205 patterns that were only used once. Update each pattern's size
3206 so that it doesn't include subpatterns that are going to be split
3207 out into subroutines. */
3208 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3210 merge_state_info
*sinfo
= &states
[i
];
3211 merge_state_result
*res
= sinfo
->res
;
3212 /* Wind past patterns that are only used by SINFO. */
3213 while (res
&& res
->pattern
->num_users
== 1)
3218 res
->pattern
->num_users
+= 1;
3223 /* We have a shared pattern and are now committed to the match. */
3224 merge_pattern_info
*pat
= res
->pattern
;
3225 gcc_assert (valid_result_p (pat
, sinfo
));
3227 if (!pat
->complete_p
)
3229 /* Look for subpatterns that are going to be split out and remove
3230 them from the number of statements. */
3231 for (unsigned int j
= 0; j
< sinfo
->num_transitions
; ++j
)
3232 if (merge_pattern_transition
*ptrans
= pat
->transitions
[j
])
3234 merge_pattern_info
*to_pat
= ptrans
->to
;
3235 if (!same_pattern_p (pat
, to_pat
))
3236 pat
->num_statements
-= to_pat
->num_statements
;
3238 pat
->complete_p
= true;
3241 /* Step 5: Split out the patterns. */
3242 for (unsigned int i
= 0; i
< states
.length (); ++i
)
3244 merge_state_info
*sinfo
= &states
[i
];
3245 merge_state_result
*res
= sinfo
->res
;
3246 if (!sinfo
->merged_p
&& res
&& useful_pattern_p (res
->pattern
))
3247 use_pattern (sinfo
);
3249 fprintf (stderr
, "Shared %d out of %d states by creating %d new states,"
3251 pattern_use_states
, states
.length (), pattern_def_states
,
3252 pattern_use_states
- pattern_def_states
);
3255 /* Information about a state tree that we're considering splitting into a
3259 /* The number of pseudo-statements in the state tree. */
3260 unsigned int num_statements
;
3262 /* The approximate number of nested "if" and "switch" statements that
3263 would be required if control could fall through to a later state. */
3267 /* Pairs a transition with information about its target state. */
3268 typedef std::pair
<transition
*, state_size
> subroutine_candidate
;
3270 /* Sort two subroutine_candidates so that the one with the largest
3271 number of statements comes last. */
3274 subroutine_candidate_cmp (const void *a
, const void *b
)
3276 return int (((const subroutine_candidate
*) a
)->second
.num_statements
3277 - ((const subroutine_candidate
*) b
)->second
.num_statements
);
3280 /* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new
3281 state that performs a subroutine call to S. */
3284 create_subroutine (routine_type type
, state
*s
, vec
<state
*> &procs
)
3286 procs
.safe_push (s
);
3287 acceptance_type acceptance
;
3288 acceptance
.type
= type
;
3289 acceptance
.partial_p
= true;
3290 acceptance
.u
.subroutine_id
= procs
.length ();
3291 state
*news
= new state
;
3292 add_decision (news
, test::accept (acceptance
), true, false);
3296 /* Walk state tree S, of type TYPE, and look for subtrees that would be
3297 better split into subroutines. Accumulate all such subroutines in PROCS.
3298 Return the size of the new state tree (excluding subroutines). */
3301 find_subroutines (routine_type type
, state
*s
, vec
<state
*> &procs
)
3303 auto_vec
<subroutine_candidate
, 16> candidates
;
3305 size
.num_statements
= 0;
3307 for (decision
*d
= s
->first
; d
; d
= d
->next
)
3309 if (!d
->test
.single_outcome_p ())
3310 size
.num_statements
+= 1;
3311 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
3313 /* Keep chains of simple decisions together if we know that no
3314 change of position is required. We'll output this chain as a
3315 single "if" statement, so it counts as a single nesting level. */
3316 if (d
->test
.pos
&& d
->if_statement_p ())
3319 decision
*newd
= trans
->to
->singleton ();
3322 && newd
->test
.pos_operand
< 0
3323 && newd
->test
.pos
!= d
->test
.pos
)
3324 || !newd
->if_statement_p ())
3326 if (!newd
->test
.single_outcome_p ())
3327 size
.num_statements
+= 1;
3328 trans
= newd
->singleton ();
3329 if (newd
->test
.kind
== test::SET_OP
3330 || newd
->test
.kind
== test::ACCEPT
)
3333 /* The target of TRANS is a subroutine candidate. First recurse
3334 on it to see how big it is after subroutines have been
3336 state_size to_size
= find_subroutines (type
, trans
->to
, procs
);
3337 if (d
->next
&& to_size
.depth
> MAX_DEPTH
)
3338 /* Keeping the target state in the same routine would lead
3339 to an excessive nesting of "if" and "switch" statements.
3340 Split it out into a subroutine so that it can use
3341 inverted tests that return early on failure. */
3342 trans
->to
= create_subroutine (type
, trans
->to
, procs
);
3345 size
.num_statements
+= to_size
.num_statements
;
3346 if (to_size
.num_statements
< MIN_NUM_STATEMENTS
)
3347 /* The target state is too small to be worth splitting.
3348 Keep it in the same routine as S. */
3349 size
.depth
= MAX (size
.depth
, to_size
.depth
);
3351 /* Assume for now that we'll keep the target state in the
3352 same routine as S, but record it as a subroutine candidate
3353 if S grows too big. */
3354 candidates
.safe_push (subroutine_candidate (trans
, to_size
));
3358 if (size
.num_statements
> MAX_NUM_STATEMENTS
)
3360 /* S is too big. Sort the subroutine candidates so that bigger ones
3361 are nearer the end. */
3362 candidates
.qsort (subroutine_candidate_cmp
);
3363 while (!candidates
.is_empty ()
3364 && size
.num_statements
> MAX_NUM_STATEMENTS
)
3366 /* Peel off a candidate and force it into a subroutine. */
3367 subroutine_candidate cand
= candidates
.pop ();
3368 size
.num_statements
-= cand
.second
.num_statements
;
3369 cand
.first
->to
= create_subroutine (type
, cand
.first
->to
, procs
);
3372 /* Update the depth for subroutine candidates that we decided not to
3374 for (unsigned int i
= 0; i
< candidates
.length (); ++i
)
3375 size
.depth
= MAX (size
.depth
, candidates
[i
].second
.depth
);
3380 /* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */
3383 safe_predicate_mode (const struct pred_data
*pred
, machine_mode mode
)
3385 /* Scalar integer constants have VOIDmode. */
3386 if (GET_MODE_CLASS (mode
) == MODE_INT
3387 && (pred
->codes
[CONST_INT
]
3388 || pred
->codes
[CONST_DOUBLE
]
3389 || pred
->codes
[CONST_WIDE_INT
]))
3392 return !pred
->special
&& mode
!= VOIDmode
;
3395 /* Fill CODES with the set of codes that could be matched by PRED. */
3398 get_predicate_codes (const struct pred_data
*pred
, int_set
*codes
)
3400 for (int i
= 0; i
< NUM_TRUE_RTX_CODE
; ++i
)
3401 if (!pred
|| pred
->codes
[i
])
3402 codes
->safe_push (i
);
3405 /* Return true if the first path through D1 tests the same thing as D2. */
3408 has_same_test_p (decision
*d1
, decision
*d2
)
3412 if (d1
->test
== d2
->test
)
3414 d1
= d1
->first
->to
->first
;
3420 /* Return true if D1 and D2 cannot match the same rtx. All states reachable
3421 from D2 have single decisions and all those decisions have single
3425 mutually_exclusive_p (decision
*d1
, decision
*d2
)
3427 /* If one path through D1 fails to test the same thing as D2, assume
3428 that D2's test could be true for D1 and look for a later, more useful,
3429 test. This isn't as expensive as it looks in practice. */
3430 while (!has_same_test_p (d1
, d2
))
3432 d2
= d2
->singleton ()->to
->singleton ();
3436 if (d1
->test
== d2
->test
)
3438 /* Look for any transitions from D1 that have the same labels as
3439 the transition from D2. */
3440 transition
*trans2
= d2
->singleton ();
3441 for (transition
*trans1
= d1
->first
; trans1
; trans1
= trans1
->next
)
3443 int_set::iterator i1
= trans1
->labels
.begin ();
3444 int_set::iterator end1
= trans1
->labels
.end ();
3445 int_set::iterator i2
= trans2
->labels
.begin ();
3446 int_set::iterator end2
= trans2
->labels
.end ();
3447 while (i1
!= end1
&& i2
!= end2
)
3454 /* TRANS1 has some labels in common with TRANS2. Assume
3455 that D1 and D2 could match the same rtx if the target
3456 of TRANS1 could match the same rtx as D2. */
3457 for (decision
*subd1
= trans1
->to
->first
;
3458 subd1
; subd1
= subd1
->next
)
3459 if (!mutually_exclusive_p (subd1
, d2
))
3466 for (transition
*trans1
= d1
->first
; trans1
; trans1
= trans1
->next
)
3467 for (decision
*subd1
= trans1
->to
->first
; subd1
; subd1
= subd1
->next
)
3468 if (!mutually_exclusive_p (subd1
, d2
))
3473 /* Try to merge S2's decision into D1, given that they have the same test.
3474 Fail only if EXCLUDE is nonnull and the new transition would have the
3475 same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2
3476 and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
3477 if the merge is complete. */
3480 merge_into_decision (decision
*d1
, state
*s2
, const int_set
*exclude
,
3481 state
**next_s1
, state
**next_s2
,
3482 const int_set
**next_exclude
)
3484 decision
*d2
= s2
->singleton ();
3485 transition
*trans2
= d2
->singleton ();
3487 /* Get a list of the transitions that intersect TRANS2. */
3488 auto_vec
<transition
*, 32> intersecting
;
3489 for (transition
*trans1
= d1
->first
; trans1
; trans1
= trans1
->next
)
3491 int_set::iterator i1
= trans1
->labels
.begin ();
3492 int_set::iterator end1
= trans1
->labels
.end ();
3493 int_set::iterator i2
= trans2
->labels
.begin ();
3494 int_set::iterator end2
= trans2
->labels
.end ();
3495 bool trans1_is_subset
= true;
3496 bool trans2_is_subset
= true;
3497 bool intersect_p
= false;
3498 while (i1
!= end1
&& i2
!= end2
)
3501 trans1_is_subset
= false;
3506 trans2_is_subset
= false;
3516 trans1_is_subset
= false;
3518 trans2_is_subset
= false;
3519 if (trans1_is_subset
&& trans2_is_subset
)
3521 /* There's already a transition that matches exactly.
3522 Merge the target states. */
3523 trans1
->optional
&= trans2
->optional
;
3524 *next_s1
= trans1
->to
;
3525 *next_s2
= trans2
->to
;
3529 if (trans2_is_subset
)
3531 /* TRANS1 has all the labels that TRANS2 needs. Merge S2 into
3532 the target of TRANS1, but (to avoid infinite recursion)
3533 make sure that we don't end up creating another transition
3535 *next_s1
= trans1
->to
;
3537 *next_exclude
= &trans1
->labels
;
3541 intersecting
.safe_push (trans1
);
3544 if (intersecting
.is_empty ())
3546 /* No existing labels intersect the new ones. We can just add
3548 d1
->push_back (d2
->release ());
3555 /* Take the union of the labels in INTERSECTING and TRANS2. Store the
3556 result in COMBINED and use NEXT as a temporary. */
3557 int_set tmp1
= trans2
->labels
, tmp2
;
3558 int_set
*combined
= &tmp1
, *next
= &tmp2
;
3559 for (unsigned int i
= 0; i
< intersecting
.length (); ++i
)
3561 transition
*trans1
= intersecting
[i
];
3563 next
->safe_grow (trans1
->labels
.length () + combined
->length ());
3564 int_set::iterator end
3565 = std::set_union (trans1
->labels
.begin (), trans1
->labels
.end (),
3566 combined
->begin (), combined
->end (),
3568 next
->truncate (end
- next
->begin ());
3569 std::swap (next
, combined
);
3572 /* Stop now if we've been told not to create a transition with these
3574 if (exclude
&& *combined
== *exclude
)
3577 /* Get the transition that should carry the new labels. */
3578 transition
*new_trans
= intersecting
[0];
3579 if (intersecting
.length () == 1)
3581 /* We're merging with one existing transition whose labels are a
3582 subset of those required. If both transitions are optional,
3583 we can just expand the set of labels so that it's suitable
3584 for both transitions. It isn't worth preserving the original
3585 transitions since we know that they can't be merged; we would
3586 need to backtrack to S2 if TRANS1->to fails. In contrast,
3587 we might be able to merge the targets of the transitions
3588 without any backtracking.
3590 If instead the existing transition is not optional, ensure that
3591 all target decisions are suitably protected. Some decisions
3592 might already have a more specific requirement than NEW_TRANS,
3593 in which case there's no point testing NEW_TRANS as well. E.g. this
3594 would have happened if a test for an (eq ...) rtx had been
3595 added to a decision that tested whether the code is suitable
3596 for comparison_operator. The original comparison_operator
3597 transition would have been non-optional and the (eq ...) test
3598 would be performed by a second decision in the target of that
3601 The remaining case -- keeping the original optional transition
3602 when adding a non-optional TRANS2 -- is a wash. Preserving
3603 the optional transition only helps if we later merge another
3604 state S3 that is mutually exclusive with S2 and whose labels
3605 belong to *COMBINED - TRANS1->labels. We can then test the
3606 original NEW_TRANS and S3 in the same decision. We keep the
3607 optional transition around for that case, but it occurs very
3609 gcc_assert (new_trans
->labels
!= *combined
);
3610 if (!new_trans
->optional
|| !trans2
->optional
)
3612 decision
*start
= 0;
3613 for (decision
*end
= new_trans
->to
->first
; end
; end
= end
->next
)
3615 if (!start
&& end
->test
!= d1
->test
)
3616 /* END belongs to a range of decisions that need to be
3617 protected by NEW_TRANS. */
3619 if (start
&& (!end
->next
|| end
->next
->test
== d1
->test
))
3621 /* Protect [START, END] with NEW_TRANS. The decisions
3622 move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */
3623 state
*new_s
= new state
;
3624 decision
*new_d
= new decision (d1
->test
);
3625 new_d
->push_back (new transition (new_trans
->labels
, new_s
,
3626 new_trans
->optional
));
3627 state::range
r (start
, end
);
3628 new_trans
->to
->replace (r
, new_d
);
3629 new_s
->push_back (r
);
3631 /* Continue with an empty range. */
3634 /* Continue from the decision after NEW_D. */
3639 new_trans
->optional
= true;
3640 new_trans
->labels
= *combined
;
3644 /* We're merging more than one existing transition together.
3645 Those transitions are successfully dividing the matching space
3646 and so we want to preserve them, even if they're optional.
3648 Create a new transition with the union set of labels and make
3649 it go to a state that has the original transitions. */
3650 decision
*new_d
= new decision (d1
->test
);
3651 for (unsigned int i
= 0; i
< intersecting
.length (); ++i
)
3652 new_d
->push_back (d1
->remove (intersecting
[i
]));
3654 state
*new_s
= new state
;
3655 new_s
->push_back (new_d
);
3657 new_trans
= new transition (*combined
, new_s
, true);
3658 d1
->push_back (new_trans
);
3661 /* We now have an optional transition with labels *COMBINED. Decide
3662 whether we can use it as TRANS2 or whether we need to merge S2
3663 into the target of NEW_TRANS. */
3664 gcc_assert (new_trans
->optional
);
3665 if (new_trans
->labels
== trans2
->labels
)
3667 /* NEW_TRANS matches TRANS2. Just merge the target states. */
3668 new_trans
->optional
= trans2
->optional
;
3669 *next_s1
= new_trans
->to
;
3670 *next_s2
= trans2
->to
;
3675 /* Try to merge TRANS2 into the target of the overlapping transition,
3676 but (to prevent infinite recursion or excessive redundancy) without
3677 creating another transition of the same type. */
3678 *next_s1
= new_trans
->to
;
3680 *next_exclude
= &new_trans
->labels
;
3685 /* Make progress in merging S2 into S1, given that each state in S2
3686 has a single decision. If EXCLUDE is nonnull, avoid creating a new
3687 transition with the same test as S2's decision and with the labels
3690 Return true if there is still work to do. When returning true,
3691 set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
3692 S1, S2 and EXCLUDE should have next time round.
3694 If S1 and S2 both match a particular rtx, give priority to S1. */
3697 merge_into_state_1 (state
*s1
, state
*s2
, const int_set
*exclude
,
3698 state
**next_s1
, state
**next_s2
,
3699 const int_set
**next_exclude
)
3701 decision
*d2
= s2
->singleton ();
3702 if (decision
*d1
= s1
->last
)
3704 if (d1
->test
.terminal_p ())
3705 /* D1 is an unconditional return, so S2 can never match. This can
3706 sometimes be a bug in the .md description, but might also happen
3707 if genconditions forces some conditions to true for certain
3711 /* Go backwards through the decisions in S1, stopping once we find one
3712 that could match the same thing as S2. */
3713 while (d1
->prev
&& mutually_exclusive_p (d1
, d2
))
3716 /* Search forwards from that point, merging D2 into the first
3718 for (; d1
; d1
= d1
->next
)
3720 /* If S2 performs some optional tests before testing the same thing
3721 as D1, those tests do not help to distinguish D1 and S2, so it's
3722 better to drop them. Search through such optional decisions
3723 until we find something that tests the same thing as D1. */
3727 decision
*sub_d2
= sub_s2
->singleton ();
3728 if (d1
->test
== sub_d2
->test
)
3730 /* Only apply EXCLUDE if we're testing the same thing
3732 const int_set
*sub_exclude
= (d2
== sub_d2
? exclude
: 0);
3734 /* Try to merge SUB_S2 into D1. This can only fail if
3735 it would involve creating a new transition with
3736 labels SUB_EXCLUDE. */
3737 if (merge_into_decision (d1
, sub_s2
, sub_exclude
,
3738 next_s1
, next_s2
, next_exclude
))
3739 return *next_s2
!= 0;
3741 /* Can't merge with D1; try a later decision. */
3744 transition
*sub_trans2
= sub_d2
->singleton ();
3745 if (!sub_trans2
->optional
)
3746 /* Can't merge with D1; try a later decision. */
3748 sub_s2
= sub_trans2
->to
;
3753 /* We can't merge D2 with any existing decision. Just add it to the end. */
3754 s1
->push_back (s2
->release ());
3758 /* Merge S2 into S1. If they both match a particular rtx, give
3759 priority to S1. Each state in S2 has a single decision. */
3762 merge_into_state (state
*s1
, state
*s2
)
3764 const int_set
*exclude
= 0;
3765 while (s2
&& merge_into_state_1 (s1
, s2
, exclude
, &s1
, &s2
, &exclude
))
3769 /* Pairs a pattern that needs to be matched with the rtx position at
3770 which the pattern should occur. */
3771 struct pattern_pos
{
3773 pattern_pos (rtx
, position
*);
3779 pattern_pos::pattern_pos (rtx pattern_in
, position
*pos_in
)
3780 : pattern (pattern_in
), pos (pos_in
)
3783 /* Compare entries according to their depth-first order. There shouldn't
3784 be two entries at the same position. */
3787 operator < (const pattern_pos
&e1
, const pattern_pos
&e2
)
3789 int diff
= compare_positions (e1
.pos
, e2
.pos
);
3790 gcc_assert (diff
!= 0 || e1
.pattern
== e2
.pattern
);
3794 /* Return the name of the predicate matched by MATCH_RTX. */
3797 predicate_name (rtx match_rtx
)
3799 if (GET_CODE (match_rtx
) == MATCH_SCRATCH
)
3800 return "scratch_operand";
3802 return XSTR (match_rtx
, 1);
3805 /* Add new decisions to S that check whether the rtx at position POS
3806 matches PATTERN. Return the state that is reached in that case.
3807 TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */
3810 match_pattern_2 (state
*s
, rtx top_pattern
, position
*pos
, rtx pattern
)
3812 auto_vec
<pattern_pos
, 32> worklist
;
3813 auto_vec
<pattern_pos
, 32> pred_and_mode_tests
;
3814 auto_vec
<pattern_pos
, 32> dup_tests
;
3816 worklist
.safe_push (pattern_pos (pattern
, pos
));
3817 while (!worklist
.is_empty ())
3819 pattern_pos next
= worklist
.pop ();
3820 pattern
= next
.pattern
;
3822 unsigned int reverse_s
= worklist
.length ();
3824 enum rtx_code code
= GET_CODE (pattern
);
3830 /* Add a test that the rtx matches the earlier one, but only
3831 after the structure and predicates have been checked. */
3832 dup_tests
.safe_push (pattern_pos (pattern
, pos
));
3834 /* Use the same code check as the original operand. */
3835 pattern
= find_operand (top_pattern
, XINT (pattern
, 0), NULL_RTX
);
3838 case MATCH_PARALLEL
:
3841 case MATCH_OPERATOR
:
3843 const char *pred_name
= predicate_name (pattern
);
3844 const struct pred_data
*pred
= 0;
3845 if (pred_name
[0] != 0)
3847 pred
= lookup_predicate (pred_name
);
3848 /* Only report errors once per rtx. */
3849 if (code
== GET_CODE (pattern
))
3852 error_with_line (pattern_lineno
,
3853 "unknown predicate '%s'"
3854 " in '%s' expression",
3855 pred_name
, GET_RTX_NAME (code
));
3856 else if (code
== MATCH_PARALLEL
3857 && pred
->singleton
!= PARALLEL
)
3858 error_with_line (pattern_lineno
,
3859 "predicate '%s' used in match_parallel"
3860 " does not allow only PARALLEL",
3865 if (code
== MATCH_PARALLEL
|| code
== MATCH_PAR_DUP
)
3867 /* Check that we have a parallel with enough elements. */
3868 s
= add_decision (s
, test::code (pos
), PARALLEL
, false);
3869 int min_len
= XVECLEN (pattern
, 2);
3870 s
= add_decision (s
, test::veclen_ge (pos
, min_len
),
3875 /* Check that the rtx has one of codes accepted by the
3876 predicate. This is necessary when matching suboperands
3877 of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
3878 call XEXP (X, N) without checking that X has at least
3881 get_predicate_codes (pred
, &codes
);
3882 bool need_codes
= (pred
3883 && (code
== MATCH_OPERATOR
3884 || code
== MATCH_OP_DUP
));
3885 s
= add_decision (s
, test::code (pos
), codes
, !need_codes
);
3888 /* Postpone the predicate check until we've checked the rest
3889 of the rtx structure. */
3890 if (code
== GET_CODE (pattern
))
3891 pred_and_mode_tests
.safe_push (pattern_pos (pattern
, pos
));
3893 /* If we need to match suboperands, add them to the worklist. */
3894 if (code
== MATCH_OPERATOR
|| code
== MATCH_PARALLEL
)
3896 position
**subpos_ptr
;
3897 enum position_type pos_type
;
3899 if (code
== MATCH_OPERATOR
|| code
== MATCH_OP_DUP
)
3901 pos_type
= POS_XEXP
;
3902 subpos_ptr
= &pos
->xexps
;
3903 i
= (code
== MATCH_OPERATOR
? 2 : 1);
3907 pos_type
= POS_XVECEXP0
;
3908 subpos_ptr
= &pos
->xvecexp0s
;
3911 for (int j
= 0; j
< XVECLEN (pattern
, i
); ++j
)
3913 position
*subpos
= next_position (subpos_ptr
, pos
,
3915 worklist
.safe_push (pattern_pos (XVECEXP (pattern
, i
, j
),
3917 subpos_ptr
= &subpos
->next
;
3925 /* Check that the rtx has the right code. */
3926 s
= add_decision (s
, test::code (pos
), code
, false);
3928 /* Queue a test for the mode if one is specified. */
3929 if (GET_MODE (pattern
) != VOIDmode
)
3930 pred_and_mode_tests
.safe_push (pattern_pos (pattern
, pos
));
3932 /* Push subrtxes onto the worklist. Match nonrtx operands now. */
3933 const char *fmt
= GET_RTX_FORMAT (code
);
3934 position
**subpos_ptr
= &pos
->xexps
;
3935 for (size_t i
= 0; fmt
[i
]; ++i
)
3937 position
*subpos
= next_position (subpos_ptr
, pos
,
3942 worklist
.safe_push (pattern_pos (XEXP (pattern
, i
),
3948 /* Make sure the vector has the right number of
3950 int length
= XVECLEN (pattern
, i
);
3951 s
= add_decision (s
, test::veclen (pos
), length
, false);
3953 position
**subpos2_ptr
= &pos
->xvecexp0s
;
3954 for (int j
= 0; j
< length
; j
++)
3956 position
*subpos2
= next_position (subpos2_ptr
, pos
,
3958 rtx x
= XVECEXP (pattern
, i
, j
);
3959 worklist
.safe_push (pattern_pos (x
, subpos2
));
3960 subpos2_ptr
= &subpos2
->next
;
3966 /* Make sure that XINT (X, I) has the right value. */
3967 s
= add_decision (s
, test::int_field (pos
, i
),
3968 XINT (pattern
, i
), false);
3972 /* Make sure that XWINT (X, I) has the right value. */
3973 s
= add_decision (s
, test::wide_int_field (pos
, i
),
3974 XWINT (pattern
, 0), false);
3983 subpos_ptr
= &subpos
->next
;
3988 /* Operands are pushed onto the worklist so that later indices are
3989 nearer the top. That's what we want for SETs, since a SET_SRC
3990 is a better discriminator than a SET_DEST. In other cases it's
3991 usually better to match earlier indices first. This is especially
3992 true of PARALLELs, where the first element tends to be the most
3993 individual. It's also true for commutative operators, where the
3994 canonicalization rules say that the more complex operand should
3996 if (code
!= SET
&& worklist
.length () > reverse_s
)
3997 std::reverse (&worklist
[0] + reverse_s
,
3998 &worklist
[0] + worklist
.length ());
4001 /* Sort the predicate and mode tests so that they're in depth-first order.
4002 The main goal of this is to put SET_SRC match_operands after SET_DEST
4003 match_operands and after mode checks for the enclosing SET_SRC operators
4004 (such as the mode of a PLUS in an addition instruction). The latter
4005 two types of test can determine the mode exactly, whereas a SET_SRC
4006 match_operand often has to cope with the possibility of the operand
4007 being a modeless constant integer. E.g. something that matches
4008 register_operand (x, SImode) never matches register_operand (x, DImode),
4009 but a const_int that matches immediate_operand (x, SImode) also matches
4010 immediate_operand (x, DImode). The register_operand cases can therefore
4011 be distinguished by a switch on the mode, but the immediate_operand
4013 if (pred_and_mode_tests
.length () > 1)
4014 std::sort (&pred_and_mode_tests
[0],
4015 &pred_and_mode_tests
[0] + pred_and_mode_tests
.length ());
4017 /* Add the mode and predicate tests. */
4020 FOR_EACH_VEC_ELT (pred_and_mode_tests
, i
, e
)
4022 switch (GET_CODE (e
->pattern
))
4024 case MATCH_PARALLEL
:
4027 case MATCH_OPERATOR
:
4029 int opno
= XINT (e
->pattern
, 0);
4030 num_operands
= MAX (num_operands
, opno
+ 1);
4031 const char *pred_name
= predicate_name (e
->pattern
);
4034 const struct pred_data
*pred
= lookup_predicate (pred_name
);
4035 /* Check the mode first, to distinguish things like SImode
4036 and DImode register_operands, as described above. */
4037 machine_mode mode
= GET_MODE (e
->pattern
);
4038 if (safe_predicate_mode (pred
, mode
))
4039 s
= add_decision (s
, test::mode (e
->pos
), mode
, true);
4041 /* Assign to operands[] first, so that the rtx usually doesn't
4042 need to be live across the call to the predicate.
4044 This shouldn't cause a problem with dirtying the page,
4045 since we fully expect to assign to operands[] at some point,
4046 and since the caller usually writes to other parts of
4047 recog_data anyway. */
4048 s
= add_decision (s
, test::set_op (e
->pos
, opno
), true, false);
4049 s
= add_decision (s
, test::predicate (e
->pos
, pred
, mode
),
4053 /* Historically we've ignored the mode when there's no
4054 predicate. Just set up operands[] unconditionally. */
4055 s
= add_decision (s
, test::set_op (e
->pos
, opno
), true, false);
4060 s
= add_decision (s
, test::mode (e
->pos
),
4061 GET_MODE (e
->pattern
), false);
4066 /* Finally add rtx_equal_p checks for duplicated operands. */
4067 FOR_EACH_VEC_ELT (dup_tests
, i
, e
)
4068 s
= add_decision (s
, test::duplicate (e
->pos
, XINT (e
->pattern
, 0)),
4073 /* Add new decisions to S that make it return ACCEPTANCE if:
4075 (1) the rtx doesn't match anything already matched by S
4076 (2) the rtx matches TOP_PATTERN and
4079 For peephole2, TOP_PATTERN is the DEFINE_PEEPHOLE2 itself, otherwise
4080 it is the rtx pattern to match (PARALLEL, SET, etc.). */
4083 match_pattern_1 (state
*s
, rtx top_pattern
, const char *c_test
,
4084 acceptance_type acceptance
)
4086 if (GET_CODE (top_pattern
) == DEFINE_PEEPHOLE2
)
4088 /* Match each individual instruction. */
4089 position
**subpos_ptr
= &peep2_insn_pos_list
;
4091 for (int i
= 0; i
< XVECLEN (top_pattern
, 0); ++i
)
4093 rtx x
= XVECEXP (top_pattern
, 0, i
);
4094 /* Ignore scratch register requirements. */
4095 if (GET_CODE (x
) != MATCH_SCRATCH
&& GET_CODE (x
) != MATCH_DUP
)
4097 position
*subpos
= next_position (subpos_ptr
, &root_pos
,
4098 POS_PEEP2_INSN
, count
);
4100 s
= add_decision (s
, test::peep2_count (count
+ 1),
4102 s
= match_pattern_2 (s
, top_pattern
, subpos
, x
);
4103 subpos_ptr
= &subpos
->next
;
4107 acceptance
.u
.full
.u
.match_len
= count
- 1;
4111 /* Make the rtx itself. */
4112 s
= match_pattern_2 (s
, top_pattern
, &root_pos
, top_pattern
);
4114 /* If the match is only valid when extra clobbers are added,
4115 make sure we're able to pass that information to the caller. */
4116 if (acceptance
.type
== RECOG
&& acceptance
.u
.full
.u
.num_clobbers
)
4117 s
= add_decision (s
, test::have_num_clobbers (), true, false);
4120 /* Make sure that the C test is true. */
4121 if (maybe_eval_c_test (c_test
) != 1)
4122 s
= add_decision (s
, test::c_test (c_test
), true, false);
4124 /* Accept the pattern. */
4125 add_decision (s
, test::accept (acceptance
), true, false);
4128 /* Like match_pattern_1, but (if merge_states_p) try to merge the
4129 decisions with what's already in S, to reduce the amount of
4133 match_pattern (state
*s
, rtx top_pattern
, const char *c_test
,
4134 acceptance_type acceptance
)
4139 /* Add the decisions to a fresh state and then merge the full tree
4140 into the existing one. */
4141 match_pattern_1 (&root
, top_pattern
, c_test
, acceptance
);
4142 merge_into_state (s
, &root
);
4145 match_pattern_1 (s
, top_pattern
, c_test
, acceptance
);
4148 /* Begin the output file. */
4154 /* Generated automatically by the program `genrecog' from the target\n\
4155 machine description file. */\n\
4157 #include \"config.h\"\n\
4158 #include \"system.h\"\n\
4159 #include \"coretypes.h\"\n\
4160 #include \"tm.h\"\n\
4161 #include \"rtl.h\"\n\
4162 #include \"tm_p.h\"\n\
4163 #include \"hashtab.h\"\n\
4164 #include \"hash-set.h\"\n\
4165 #include \"vec.h\"\n\
4166 #include \"machmode.h\"\n\
4167 #include \"hard-reg-set.h\"\n\
4168 #include \"input.h\"\n\
4169 #include \"function.h\"\n\
4170 #include \"insn-config.h\"\n\
4171 #include \"recog.h\"\n\
4172 #include \"output.h\"\n\
4173 #include \"flags.h\"\n\
4174 #include \"hard-reg-set.h\"\n\
4175 #include \"predict.h\"\n\
4176 #include \"basic-block.h\"\n\
4177 #include \"resource.h\"\n\
4178 #include \"diagnostic-core.h\"\n\
4179 #include \"reload.h\"\n\
4180 #include \"regs.h\"\n\
4181 #include \"tm-constrs.h\"\n\
4182 #include \"predict.h\"\n\
4186 /* `recog' contains a decision tree that recognizes whether the rtx\n\
4187 X0 is a valid instruction.\n\
4189 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
4190 returns a nonnegative number which is the insn code number for the\n\
4191 pattern that matched. This is the same as the order in the machine\n\
4192 description of the entry that matched. This number can be used as an\n\
4193 index into `insn_data' and other tables.\n");
4195 The third parameter to recog is an optional pointer to an int. If\n\
4196 present, recog will accept a pattern if it matches except for missing\n\
4197 CLOBBER expressions at the end. In that case, the value pointed to by\n\
4198 the optional pointer will be set to the number of CLOBBERs that need\n\
4199 to be added (it should be initialized to zero by the caller). If it");
4201 is set nonzero, the caller should allocate a PARALLEL of the\n\
4202 appropriate size, copy the initial entries, and call add_clobbers\n\
4203 (found in insn-emit.c) to fill in the CLOBBERs.\n\
4207 The function split_insns returns 0 if the rtl could not\n\
4208 be split or the split rtl as an INSN list if it can be.\n\
4210 The function peephole2_insns returns 0 if the rtl could not\n\
4211 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4212 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4216 /* Return the C type of a parameter with type TYPE. */
4219 parameter_type_string (parameter::type_enum type
)
4223 case parameter::UNSET
:
4226 case parameter::CODE
:
4229 case parameter::MODE
:
4230 return "machine_mode";
4232 case parameter::INT
:
4235 case parameter::WIDE_INT
:
4236 return "HOST_WIDE_INT";
4241 /* Return true if ACCEPTANCE requires only a single C statement even in
4242 a backtracking context. */
4245 single_statement_p (const acceptance_type
&acceptance
)
4247 if (acceptance
.partial_p
)
4248 /* We need to handle failures of the subroutine. */
4250 switch (acceptance
.type
)
4257 /* False if we need to assign to pnum_clobbers. */
4258 return acceptance
.u
.full
.u
.num_clobbers
== 0;
4261 /* We need to assign to pmatch_len_ and handle null returns from the
4262 peephole2 routine. */
4268 /* Return the C failure value for a routine of type TYPE. */
4271 get_failure_return (routine_type type
)
4286 /* Indicates whether a block of code always returns or whether it can fall
4294 /* Information used while writing out code. */
4298 /* The type of routine that we're generating. */
4301 /* Maps position ids to xN variable numbers. The entry is only valid if
4302 it is less than the length of VAR_TO_ID, but this holds for every position
4303 tested by a state when writing out that state. */
4304 auto_vec
<unsigned int> id_to_var
;
4306 /* Maps xN variable numbers to position ids. */
4307 auto_vec
<unsigned int> var_to_id
;
4309 /* Index N is true if variable xN has already been set. */
4310 auto_vec
<bool> seen_vars
;
4313 /* Return true if D is a call to a pattern routine and if there is some X
4314 such that the transition for pattern result N goes to a successful return
4315 with code X+N. When returning true, set *BASE_OUT to this X and *COUNT_OUT
4316 to the number of return values. (We know that every PATTERN decision has
4317 a transition for every successful return.) */
4320 terminal_pattern_p (decision
*d
, unsigned int *base_out
,
4321 unsigned int *count_out
)
4323 if (d
->test
.kind
!= test::PATTERN
)
4325 unsigned int base
= 0;
4326 unsigned int count
= 0;
4327 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
4329 if (trans
->is_param
|| trans
->labels
.length () != 1)
4331 decision
*subd
= trans
->to
->singleton ();
4332 if (!subd
|| subd
->test
.kind
!= test::ACCEPT
)
4334 unsigned int this_base
= (subd
->test
.u
.acceptance
.u
.full
.code
4335 - trans
->labels
[0]);
4336 if (trans
== d
->first
)
4338 else if (base
!= this_base
)
4347 /* Return true if TEST doesn't test an rtx or if the rtx it tests is
4348 already available in state OS. */
4351 test_position_available_p (output_state
*os
, const test
&test
)
4354 || test
.pos_operand
>= 0
4355 || os
->seen_vars
[os
->id_to_var
[test
.pos
->id
]]);
4358 /* Like printf, but print INDENT spaces at the beginning. */
4360 static void ATTRIBUTE_PRINTF_2
4361 printf_indent (unsigned int indent
, const char *format
, ...)
4364 va_start (ap
, format
);
4365 printf ("%*s", indent
, "");
4366 vprintf (format
, ap
);
4370 /* Emit code to initialize the variable associated with POS, if it isn't
4371 already valid in state OS. Indent each line by INDENT spaces. Update
4372 OS with the new state. */
4375 change_state (output_state
*os
, position
*pos
, unsigned int indent
)
4377 unsigned int var
= os
->id_to_var
[pos
->id
];
4378 gcc_assert (var
< os
->var_to_id
.length () && os
->var_to_id
[var
] == pos
->id
);
4379 if (os
->seen_vars
[var
])
4383 case POS_PEEP2_INSN
:
4384 printf_indent (indent
, "x%d = PATTERN (peep2_next_insn (%d));\n",
4389 change_state (os
, pos
->base
, indent
);
4390 printf_indent (indent
, "x%d = XEXP (x%d, %d);\n",
4391 var
, os
->id_to_var
[pos
->base
->id
], pos
->arg
);
4395 change_state (os
, pos
->base
, indent
);
4396 printf_indent (indent
, "x%d = XVECEXP (x%d, 0, %d);\n",
4397 var
, os
->id_to_var
[pos
->base
->id
], pos
->arg
);
4400 os
->seen_vars
[var
] = true;
4403 /* Print the enumerator constant for CODE -- the upcase version of
4407 print_code (enum rtx_code code
)
4410 for (p
= GET_RTX_NAME (code
); *p
; p
++)
4411 putchar (TOUPPER (*p
));
4414 /* Emit a uint64_t as an integer constant expression. We need to take
4415 special care to avoid "decimal constant is so large that it is unsigned"
4416 warnings in the resulting code. */
4419 print_host_wide_int (uint64_t val
)
4421 uint64_t min
= uint64_t (1) << (HOST_BITS_PER_WIDE_INT
- 1);
4423 printf ("(" HOST_WIDE_INT_PRINT_DEC_C
" - 1)", val
+ 1);
4425 printf (HOST_WIDE_INT_PRINT_DEC_C
, val
);
4428 /* Print the C expression for actual parameter PARAM. */
4431 print_parameter_value (const parameter
¶m
)
4434 printf ("i%d", (int) param
.value
+ 1);
4438 case parameter::UNSET
:
4442 case parameter::CODE
:
4443 print_code ((enum rtx_code
) param
.value
);
4446 case parameter::MODE
:
4447 printf ("%smode", GET_MODE_NAME ((machine_mode
) param
.value
));
4450 case parameter::INT
:
4451 printf ("%d", (int) param
.value
);
4454 case parameter::WIDE_INT
:
4455 print_host_wide_int (param
.value
);
4460 /* Print the C expression for the rtx tested by TEST. */
4463 print_test_rtx (output_state
*os
, const test
&test
)
4465 if (test
.pos_operand
>= 0)
4466 printf ("operands[%d]", test
.pos_operand
);
4468 printf ("x%d", os
->id_to_var
[test
.pos
->id
]);
4471 /* Print the C expression for non-boolean test TEST. */
4474 print_nonbool_test (output_state
*os
, const test
&test
)
4479 printf ("GET_CODE (");
4480 print_test_rtx (os
, test
);
4485 printf ("GET_MODE (");
4486 print_test_rtx (os
, test
);
4491 printf ("XVECLEN (");
4492 print_test_rtx (os
, test
);
4496 case test::INT_FIELD
:
4498 print_test_rtx (os
, test
);
4499 printf (", %d)", test
.u
.opno
);
4502 case test::WIDE_INT_FIELD
:
4504 print_test_rtx (os
, test
);
4505 printf (", %d)", test
.u
.opno
);
4510 pattern_routine
*routine
= test
.u
.pattern
->routine
;
4511 printf ("pattern%d (", routine
->pattern_id
);
4512 const char *sep
= "";
4515 print_test_rtx (os
, test
);
4518 if (routine
->insn_p
)
4520 printf ("%sinsn", sep
);
4523 if (routine
->pnum_clobbers_p
)
4525 printf ("%spnum_clobbers", sep
);
4528 for (unsigned int i
= 0; i
< test
.u
.pattern
->params
.length (); ++i
)
4530 fputs (sep
, stdout
);
4531 print_parameter_value (test
.u
.pattern
->params
[i
]);
4538 case test::PEEP2_COUNT
:
4539 case test::VECLEN_GE
:
4540 case test::SAVED_CONST_INT
:
4541 case test::DUPLICATE
:
4542 case test::PREDICATE
:
4544 case test::HAVE_NUM_CLOBBERS
:
4551 /* IS_PARAM and LABEL are taken from a transition whose source
4552 decision performs TEST. Print the C code for the label. */
4555 print_label_value (const test
&test
, bool is_param
, uint64_t value
)
4557 print_parameter_value (parameter (transition_parameter_type (test
.kind
),
4561 /* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
4562 If !IS_PARAM, print code to compare TEST with the C constant VALUE.
4563 Test for inequality if INVERT_P, otherwise test for equality. */
4566 print_test (output_state
*os
, const test
&test
, bool is_param
, uint64_t value
,
4571 /* Handle the non-boolean TESTs. */
4575 case test::INT_FIELD
:
4576 case test::WIDE_INT_FIELD
:
4578 print_nonbool_test (os
, test
);
4579 printf (" %s ", invert_p
? "!=" : "==");
4580 print_label_value (test
, is_param
, value
);
4583 case test::SAVED_CONST_INT
:
4584 gcc_assert (!is_param
&& value
== 1);
4585 print_test_rtx (os
, test
);
4586 printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ",
4587 invert_p
? "!=" : "==");
4588 print_parameter_value (parameter (parameter::INT
,
4589 test
.u
.integer
.is_param
,
4590 test
.u
.integer
.value
));
4594 case test::PEEP2_COUNT
:
4595 gcc_assert (!is_param
&& value
== 1);
4596 printf ("peep2_current_count %s %d", invert_p
? "<" : ">=",
4600 case test::VECLEN_GE
:
4601 gcc_assert (!is_param
&& value
== 1);
4602 printf ("XVECLEN (");
4603 print_test_rtx (os
, test
);
4604 printf (", 0) %s %d", invert_p
? "<" : ">=", test
.u
.min_len
);
4607 case test::PREDICATE
:
4608 gcc_assert (!is_param
&& value
== 1);
4609 printf ("%s%s (", invert_p
? "!" : "", test
.u
.predicate
.data
->name
);
4610 print_test_rtx (os
, test
);
4612 print_parameter_value (parameter (parameter::MODE
,
4613 test
.u
.predicate
.mode_is_param
,
4614 test
.u
.predicate
.mode
));
4618 case test::DUPLICATE
:
4619 gcc_assert (!is_param
&& value
== 1);
4620 printf ("%srtx_equal_p (", invert_p
? "!" : "");
4621 print_test_rtx (os
, test
);
4622 printf (", operands[%d])", test
.u
.opno
);
4625 case test::HAVE_NUM_CLOBBERS
:
4626 gcc_assert (!is_param
&& value
== 1);
4627 printf ("pnum_clobbers %s NULL", invert_p
? "==" : "!=");
4631 gcc_assert (!is_param
&& value
== 1);
4634 print_c_condition (test
.u
.string
);
4643 static exit_state
print_decision (output_state
*, decision
*,
4644 unsigned int, bool);
4646 /* Print code to perform S, indent each line by INDENT spaces.
4647 IS_FINAL is true if there are no fallback decisions to test on failure;
4648 if the state fails then the entire routine fails. */
4651 print_state (output_state
*os
, state
*s
, unsigned int indent
, bool is_final
)
4653 exit_state es
= ES_FALLTHROUGH
;
4654 for (decision
*d
= s
->first
; d
; d
= d
->next
)
4655 es
= print_decision (os
, d
, indent
, is_final
&& !d
->next
);
4656 if (es
!= ES_RETURNED
&& is_final
)
4658 printf_indent (indent
, "return %s;\n", get_failure_return (os
->type
));
4664 /* Print the code for subroutine call ACCEPTANCE (for which partial_p
4665 is known to be true). Return the C condition that indicates a successful
4669 print_subroutine_call (const acceptance_type
&acceptance
)
4671 switch (acceptance
.type
)
4677 printf ("recog_%d (x1, insn, pnum_clobbers)",
4678 acceptance
.u
.subroutine_id
);
4682 printf ("split_%d (x1, insn)", acceptance
.u
.subroutine_id
);
4683 return "!= NULL_RTX";
4686 printf ("peephole2_%d (x1, insn, pmatch_len_)",
4687 acceptance
.u
.subroutine_id
);
4688 return "!= NULL_RTX";
4693 /* Print code for the successful match described by ACCEPTANCE.
4694 INDENT and IS_FINAL are as for print_state. */
4697 print_acceptance (const acceptance_type
&acceptance
, unsigned int indent
,
4700 if (acceptance
.partial_p
)
4702 /* Defer the rest of the match to a subroutine. */
4705 printf_indent (indent
, "return ");
4706 print_subroutine_call (acceptance
);
4712 printf_indent (indent
, "res = ");
4713 const char *res_test
= print_subroutine_call (acceptance
);
4715 printf_indent (indent
, "if (res %s)\n", res_test
);
4716 printf_indent (indent
+ 2, "return res;\n");
4717 return ES_FALLTHROUGH
;
4720 switch (acceptance
.type
)
4723 printf_indent (indent
, "return %d;\n", acceptance
.u
.full
.code
);
4727 if (acceptance
.u
.full
.u
.num_clobbers
!= 0)
4728 printf_indent (indent
, "*pnum_clobbers = %d;\n",
4729 acceptance
.u
.full
.u
.num_clobbers
);
4730 printf_indent (indent
, "return %d; /* %s */\n", acceptance
.u
.full
.code
,
4731 get_insn_name (acceptance
.u
.full
.code
));
4735 printf_indent (indent
, "return gen_split_%d (insn, operands);\n",
4736 acceptance
.u
.full
.code
);
4740 printf_indent (indent
, "*pmatch_len_ = %d;\n",
4741 acceptance
.u
.full
.u
.match_len
);
4744 printf_indent (indent
, "return gen_peephole2_%d (insn, operands);\n",
4745 acceptance
.u
.full
.code
);
4750 printf_indent (indent
, "res = gen_peephole2_%d (insn, operands);\n",
4751 acceptance
.u
.full
.code
);
4752 printf_indent (indent
, "if (res != NULL_RTX)\n");
4753 printf_indent (indent
+ 2, "return res;\n");
4754 return ES_FALLTHROUGH
;
4760 /* Print code to perform D. INDENT and IS_FINAL are as for print_state. */
4763 print_decision (output_state
*os
, decision
*d
, unsigned int indent
,
4767 unsigned int base
, count
;
4769 /* Make sure the rtx under test is available either in operands[] or
4770 in an xN variable. */
4771 if (d
->test
.pos
&& d
->test
.pos_operand
< 0)
4772 change_state (os
, d
->test
.pos
, indent
);
4774 /* Look for cases where a pattern routine P1 calls another pattern routine
4775 P2 and where P1 returns X + BASE whenever P2 returns X. If IS_FINAL
4776 is true and BASE is zero we can simply use:
4778 return patternN (...);
4780 Otherwise we can use:
4782 res = patternN (...);
4786 However, if BASE is nonzero and patternN only returns 0 or -1,
4787 the usual "return BASE;" is better than "return res + BASE;".
4788 If BASE is zero, "return res;" should be better than "return 0;",
4789 since no assignment to the return register is required. */
4790 if (os
->type
== SUBPATTERN
4791 && terminal_pattern_p (d
, &base
, &count
)
4792 && (base
== 0 || count
> 1))
4794 if (is_final
&& base
== 0)
4796 printf_indent (indent
, "return ");
4797 print_nonbool_test (os
, d
->test
);
4798 printf ("; /* [-1, %d] */\n", count
- 1);
4803 printf_indent (indent
, "res = ");
4804 print_nonbool_test (os
, d
->test
);
4806 printf_indent (indent
, "if (res >= 0)\n");
4807 printf_indent (indent
+ 2, "return res");
4809 printf (" + %d", base
);
4810 printf ("; /* [%d, %d] */\n", base
, base
+ count
- 1);
4811 return ES_FALLTHROUGH
;
4814 else if (d
->test
.kind
== test::ACCEPT
)
4815 return print_acceptance (d
->test
.u
.acceptance
, indent
, is_final
);
4816 else if (d
->test
.kind
== test::SET_OP
)
4818 printf_indent (indent
, "operands[%d] = ", d
->test
.u
.opno
);
4819 print_test_rtx (os
, d
->test
);
4821 return print_state (os
, d
->singleton ()->to
, indent
, is_final
);
4823 /* Handle decisions with a single transition and a single transition
4825 else if (d
->if_statement_p (&label
))
4827 transition
*trans
= d
->singleton ();
4828 if (mark_optional_transitions_p
&& trans
->optional
)
4829 printf_indent (indent
, "/* OPTIONAL IF */\n");
4831 /* Print the condition associated with TRANS. Invert it if IS_FINAL,
4832 so that we return immediately on failure and fall through on
4834 printf_indent (indent
, "if (");
4835 print_test (os
, d
->test
, trans
->is_param
, label
, is_final
);
4837 /* Look for following states that would be handled by this code
4838 on recursion. If they don't need any preparatory statements,
4839 include them in the current "if" statement rather than creating
4843 d
= trans
->to
->singleton ();
4845 || d
->test
.kind
== test::ACCEPT
4846 || d
->test
.kind
== test::SET_OP
4847 || !d
->if_statement_p (&label
)
4848 || !test_position_available_p (os
, d
->test
))
4852 if (mark_optional_transitions_p
&& trans
->optional
)
4853 printf_indent (indent
+ 4, "/* OPTIONAL IF */\n");
4854 printf_indent (indent
+ 4, "%s ", is_final
? "||" : "&&");
4855 print_test (os
, d
->test
, trans
->is_param
, label
, is_final
);
4859 /* Print the conditional code with INDENT + 2 and the fallthrough
4860 code with indent INDENT. */
4861 state
*to
= trans
->to
;
4864 /* We inverted the condition above, so return failure in the
4865 "if" body and fall through to the target of the transition. */
4866 printf_indent (indent
+ 2, "return %s;\n",
4867 get_failure_return (os
->type
));
4868 return print_state (os
, to
, indent
, is_final
);
4870 else if (to
->singleton ()
4871 && to
->first
->test
.kind
== test::ACCEPT
4872 && single_statement_p (to
->first
->test
.u
.acceptance
))
4874 /* The target of the transition is a simple "return" statement.
4875 It doesn't need any braces and doesn't fall through. */
4876 if (print_acceptance (to
->first
->test
.u
.acceptance
,
4877 indent
+ 2, true) != ES_RETURNED
)
4879 return ES_FALLTHROUGH
;
4883 /* The general case. Output code for the target of the transition
4884 in braces. This will not invalidate any of the xN variables
4885 that are already valid, but we mustn't rely on any that are
4886 set by the "if" body. */
4887 auto_vec
<bool, 32> old_seen
;
4888 old_seen
.safe_splice (os
->seen_vars
);
4890 printf_indent (indent
+ 2, "{\n");
4891 print_state (os
, trans
->to
, indent
+ 4, is_final
);
4892 printf_indent (indent
+ 2, "}\n");
4894 os
->seen_vars
.truncate (0);
4895 os
->seen_vars
.splice (old_seen
);
4896 return ES_FALLTHROUGH
;
4901 /* Output the decision as a switch statement. */
4902 printf_indent (indent
, "switch (");
4903 print_nonbool_test (os
, d
->test
);
4906 /* Each case statement starts with the same set of valid variables.
4907 These are also the only variables will be valid on fallthrough. */
4908 auto_vec
<bool, 32> old_seen
;
4909 old_seen
.safe_splice (os
->seen_vars
);
4911 printf_indent (indent
+ 2, "{\n");
4912 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
4914 gcc_assert (!trans
->is_param
);
4915 if (mark_optional_transitions_p
&& trans
->optional
)
4916 printf_indent (indent
+ 2, "/* OPTIONAL CASE */\n");
4917 for (int_set::iterator j
= trans
->labels
.begin ();
4918 j
!= trans
->labels
.end (); ++j
)
4920 printf_indent (indent
+ 2, "case ");
4921 print_label_value (d
->test
, trans
->is_param
, *j
);
4924 if (print_state (os
, trans
->to
, indent
+ 4, is_final
))
4926 /* The state can fall through. Add an explicit break. */
4927 gcc_assert (!is_final
);
4928 printf_indent (indent
+ 4, "break;\n");
4932 /* Restore the original set of valid variables. */
4933 os
->seen_vars
.truncate (0);
4934 os
->seen_vars
.splice (old_seen
);
4936 /* Add a default case. */
4937 printf_indent (indent
+ 2, "default:\n");
4939 printf_indent (indent
+ 4, "return %s;\n",
4940 get_failure_return (os
->type
));
4942 printf_indent (indent
+ 4, "break;\n");
4943 printf_indent (indent
+ 2, "}\n");
4944 return is_final
? ES_RETURNED
: ES_FALLTHROUGH
;
4948 /* Make sure that OS has a position variable for POS. ROOT_P is true if
4949 POS is the root position for the routine. */
4952 assign_position_var (output_state
*os
, position
*pos
, bool root_p
)
4954 unsigned int idx
= os
->id_to_var
[pos
->id
];
4955 if (idx
< os
->var_to_id
.length () && os
->var_to_id
[idx
] == pos
->id
)
4957 if (!root_p
&& pos
->type
!= POS_PEEP2_INSN
)
4958 assign_position_var (os
, pos
->base
, false);
4959 os
->id_to_var
[pos
->id
] = os
->var_to_id
.length ();
4960 os
->var_to_id
.safe_push (pos
->id
);
4963 /* Make sure that OS has the position variables required by S. */
4966 assign_position_vars (output_state
*os
, state
*s
)
4968 for (decision
*d
= s
->first
; d
; d
= d
->next
)
4970 /* Positions associated with operands can be read from the
4971 operands[] array. */
4972 if (d
->test
.pos
&& d
->test
.pos_operand
< 0)
4973 assign_position_var (os
, d
->test
.pos
, false);
4974 for (transition
*trans
= d
->first
; trans
; trans
= trans
->next
)
4975 assign_position_vars (os
, trans
->to
);
4979 /* Print the open brace and variable definitions for a routine that
4980 implements S. ROOT is the deepest rtx from which S can access all
4981 relevant parts of the first instruction it matches. Initialize OS
4982 so that every relevant position has an rtx variable xN and so that
4983 only ROOT's variable has a valid value. */
4986 print_subroutine_start (output_state
*os
, state
*s
, position
*root
)
4988 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED"
4989 " = &recog_data.operand[0];\n");
4990 os
->var_to_id
.truncate (0);
4991 os
->seen_vars
.truncate (0);
4994 /* Create a fake entry for position 0 so that an id_to_var of 0
4995 is always invalid. This also makes the xN variables naturally
4996 1-based rather than 0-based. */
4997 os
->var_to_id
.safe_push (num_positions
);
4999 /* Associate ROOT with x1. */
5000 assign_position_var (os
, root
, true);
5002 /* Assign xN variables to all other relevant positions. */
5003 assign_position_vars (os
, s
);
5005 /* Output the variable declarations (except for ROOT's, which is
5006 passed in as a parameter). */
5007 unsigned int num_vars
= os
->var_to_id
.length ();
5010 for (unsigned int i
= 2; i
< num_vars
; ++i
)
5011 /* Print 8 rtx variables to a line. */
5013 i
== 2 ? " rtx" : (i
- 2) % 8 == 0 ? ";\n rtx" : ",", i
);
5017 /* Say that x1 is valid and the rest aren't. */
5018 os
->seen_vars
.safe_grow_cleared (num_vars
);
5019 os
->seen_vars
[1] = true;
5021 if (os
->type
== SUBPATTERN
|| os
->type
== RECOG
)
5022 printf (" int res ATTRIBUTE_UNUSED;\n");
5024 printf (" rtx res ATTRIBUTE_UNUSED;\n");
5027 /* Output the definition of pattern routine ROUTINE. */
5030 print_pattern (output_state
*os
, pattern_routine
*routine
)
5032 printf ("\nstatic int\npattern%d (", routine
->pattern_id
);
5033 const char *sep
= "";
5034 /* Add the top-level rtx parameter, if any. */
5037 printf ("%srtx x1", sep
);
5040 /* Add the optional parameters. */
5041 if (routine
->insn_p
)
5043 /* We can't easily tell whether a C condition actually reads INSN,
5044 so add an ATTRIBUTE_UNUSED just in case. */
5045 printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep
);
5048 if (routine
->pnum_clobbers_p
)
5050 printf ("%sint *pnum_clobbers", sep
);
5053 /* Add the "i" parameters. */
5054 for (unsigned int i
= 0; i
< routine
->param_types
.length (); ++i
)
5056 printf ("%s%s i%d", sep
,
5057 parameter_type_string (routine
->param_types
[i
]), i
+ 1);
5061 os
->type
= SUBPATTERN
;
5062 print_subroutine_start (os
, routine
->s
, routine
->pos
);
5063 print_state (os
, routine
->s
, 2, true);
5067 /* Output a routine of type TYPE that implements S. PROC_ID is the
5068 number of the subroutine associated with S, or 0 if S is the main
5072 print_subroutine (output_state
*os
, state
*s
, int proc_id
)
5074 /* For now, the top-level functions take a plain "rtx", and perform a
5075 checked cast to "rtx_insn *" for use throughout the rest of the
5076 function and the code it calls. */
5077 const char *insn_param
5078 = proc_id
> 0 ? "rtx_insn *insn" : "rtx uncast_insn";
5087 printf ("static int\nrecog_%d", proc_id
);
5089 printf ("int\nrecog");
5090 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5091 "\t%s ATTRIBUTE_UNUSED,\n"
5092 "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", insn_param
);
5097 printf ("static rtx\nsplit_%d", proc_id
);
5099 printf ("rtx\nsplit_insns");
5100 printf (" (rtx x1 ATTRIBUTE_UNUSED, %s ATTRIBUTE_UNUSED)\n",
5106 printf ("static rtx\npeephole2_%d", proc_id
);
5108 printf ("rtx\npeephole2_insns");
5109 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5110 "\t%s ATTRIBUTE_UNUSED,\n"
5111 "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n", insn_param
);
5114 print_subroutine_start (os
, s
, &root_pos
);
5117 printf (" recog_data.insn = NULL_RTX;\n");
5118 printf (" rtx_insn *insn ATTRIBUTE_UNUSED;\n");
5119 printf (" insn = safe_as_a <rtx_insn *> (uncast_insn);\n");
5121 print_state (os
, s
, 2, true);
5125 /* Print out a routine of type TYPE that performs ROOT. */
5128 print_subroutine_group (output_state
*os
, routine_type type
, state
*root
)
5131 if (use_subroutines_p
)
5133 /* Split ROOT up into smaller pieces, both for readability and to
5134 help the compiler. */
5135 auto_vec
<state
*> subroutines
;
5136 find_subroutines (type
, root
, subroutines
);
5138 /* Output the subroutines (but not ROOT itself). */
5141 FOR_EACH_VEC_ELT (subroutines
, i
, s
)
5142 print_subroutine (os
, s
, i
+ 1);
5144 /* Output the main routine. */
5145 print_subroutine (os
, root
, 0);
5148 /* Return the rtx pattern specified by the list of rtxes in a
5149 define_insn or define_split. */
5152 add_implicit_parallel (rtvec vec
)
5154 if (GET_NUM_ELEM (vec
) == 1)
5155 return RTVEC_ELT (vec
, 0);
5158 rtx pattern
= rtx_alloc (PARALLEL
);
5159 XVEC (pattern
, 0) = vec
;
5164 /* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
5165 rtx can be added automatically by add_clobbers. If so, update
5166 *ACCEPTANCE_PTR so that its num_clobbers field contains the number
5167 of such trailing rtxes and update *PATTERN_PTR so that it contains
5168 the pattern without those rtxes. */
5171 remove_clobbers (acceptance_type
*acceptance_ptr
, rtx
*pattern_ptr
)
5176 /* Find the last non-clobber in the parallel. */
5177 rtx pattern
= *pattern_ptr
;
5178 for (i
= XVECLEN (pattern
, 0); i
> 0; i
--)
5180 rtx x
= XVECEXP (pattern
, 0, i
- 1);
5181 if (GET_CODE (x
) != CLOBBER
5182 || (!REG_P (XEXP (x
, 0))
5183 && GET_CODE (XEXP (x
, 0)) != MATCH_SCRATCH
))
5187 if (i
== XVECLEN (pattern
, 0))
5190 /* Build a similar insn without the clobbers. */
5192 new_pattern
= XVECEXP (pattern
, 0, 0);
5195 new_pattern
= rtx_alloc (PARALLEL
);
5196 XVEC (new_pattern
, 0) = rtvec_alloc (i
);
5197 for (int j
= 0; j
< i
; ++j
)
5198 XVECEXP (new_pattern
, 0, j
) = XVECEXP (pattern
, 0, j
);
5202 acceptance_ptr
->u
.full
.u
.num_clobbers
= XVECLEN (pattern
, 0) - i
;
5203 *pattern_ptr
= new_pattern
;
5208 main (int argc
, char **argv
)
5211 state insn_root
, split_root
, peephole2_root
;
5213 progname
= "genrecog";
5215 if (!init_rtx_reader_args (argc
, argv
))
5216 return (FATAL_EXIT_CODE
);
5222 /* Read the machine description. */
5226 desc
= read_md_rtx (&pattern_lineno
, &next_insn_code
);
5232 acceptance_type acceptance
;
5233 acceptance
.partial_p
= false;
5234 acceptance
.u
.full
.code
= next_insn_code
;
5236 switch (GET_CODE (desc
))
5240 /* Match the instruction in the original .md form. */
5241 pattern
= add_implicit_parallel (XVEC (desc
, 1));
5242 acceptance
.type
= RECOG
;
5243 acceptance
.u
.full
.u
.num_clobbers
= 0;
5244 match_pattern (&insn_root
, pattern
, XSTR (desc
, 2), acceptance
);
5246 /* If the pattern is a PARALLEL with trailing CLOBBERs,
5247 allow recog_for_combine to match without the clobbers. */
5248 if (GET_CODE (pattern
) == PARALLEL
5249 && remove_clobbers (&acceptance
, &pattern
))
5250 match_pattern (&insn_root
, pattern
, XSTR (desc
, 2), acceptance
);
5255 acceptance
.type
= SPLIT
;
5256 pattern
= add_implicit_parallel (XVEC (desc
, 0));
5257 match_pattern (&split_root
, pattern
, XSTR (desc
, 1), acceptance
);
5259 /* Declare the gen_split routine that we'll call if the
5260 pattern matches. The definition comes from insn-emit.c. */
5261 printf ("extern rtx gen_split_%d (rtx_insn *, rtx *);\n",
5265 case DEFINE_PEEPHOLE2
:
5266 acceptance
.type
= PEEPHOLE2
;
5267 match_pattern (&peephole2_root
, desc
, XSTR (desc
, 1), acceptance
);
5269 /* Declare the gen_peephole2 routine that we'll call if the
5270 pattern matches. The definition comes from insn-emit.c. */
5271 printf ("extern rtx gen_peephole2_%d (rtx_insn *, rtx *);\n",
5281 return FATAL_EXIT_CODE
;
5285 /* Optimize each routine in turn. */
5286 optimize_subroutine_group ("recog", &insn_root
);
5287 optimize_subroutine_group ("split_insns", &split_root
);
5288 optimize_subroutine_group ("peephole2_insns", &peephole2_root
);
5291 os
.id_to_var
.safe_grow_cleared (num_positions
);
5293 if (use_pattern_routines_p
)
5295 /* Look for common patterns and split them out into subroutines. */
5296 auto_vec
<merge_state_info
> states
;
5297 states
.safe_push (&insn_root
);
5298 states
.safe_push (&split_root
);
5299 states
.safe_push (&peephole2_root
);
5300 split_out_patterns (states
);
5302 /* Print out the routines that we just created. */
5304 pattern_routine
*routine
;
5305 FOR_EACH_VEC_ELT (patterns
, i
, routine
)
5306 print_pattern (&os
, routine
);
5309 /* Print out the matching routines. */
5310 print_subroutine_group (&os
, RECOG
, &insn_root
);
5311 print_subroutine_group (&os
, SPLIT
, &split_root
);
5312 print_subroutine_group (&os
, PEEPHOLE2
, &peephole2_root
);
5315 return (ferror (stdout
) != 0 ? FATAL_EXIT_CODE
: SUCCESS_EXIT_CODE
);