</
1/* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
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.
15
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/>. */
19
20
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.
25
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).
32
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.
41
42 This program also generates the function `split_insns', which
43 returns 0 if the rtl could not be split, or it returns the split
44 rtl as an INSN list.
45
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.
50
51
52 At a high level, the algorithm used in this file is as follows:
53
54 1. Build up a decision tree for each routine, using the following
55 approach to matching an rtx:
56
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.
62
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.
67
68 - Next check match_dups.
69
70 - Finally check the C condition and (where appropriate) pnum_clobbers.
71
72 2. Try to optimize the tree by removing redundant tests, CSEing tests,
73 folding tests together, etc.
74
75 3. Look for common subtrees and split them out into "pattern" routines.
76 These common subtrees can be identical or they can differ in mode,
77 code, or integer (usually an UNSPEC or UNSPEC_VOLATILE code).
78 In the latter case the users of the pattern routine pass the
79 appropriate mode, etc., as argument. For example, if two patterns
80 contain:
81
82 (plus:SI (match_operand:SI 1 "register_operand")
83 (match_operand:SI 2 "register_operand"))
84
85 we can split the associated matching code out into a subroutine.
86 If a pattern contains:
87
88 (minus:DI (match_operand:DI 1 "register_operand")
89 (match_operand:DI 2 "register_operand"))
90
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.
94
95 The main aim of this phase is to reduce the compile time of the
96 insn-recog.c code and to reduce the amount of object code in
97 insn-recog.o.
98
99 4. Split the matching trees into functions, trying to limit the
100 size of each function to a sensible amount.
101
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.)
104
105 5. Write out C++ code for each function. */
106
107#include "bconfig.h"
108#define INCLUDE_ALGORITHM
109#include "system.h"
110#include "coretypes.h"
111#include "tm.h"
112#include "rtl.h"
113#include "errors.h"
114#include "read-md.h"
115#include "gensupport.h"
116
117#undef GENERATOR_FILE
118enum true_rtx_doe {
119#define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM,
120#include "rtl.def"
121#undef DEF_RTL_EXPR
122 FIRST_GENERATOR_RTX_CODE
123};
124#define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE)
125#define GENERATOR_FILE 1
126
127/* Debugging variables to control which optimizations are performed.
128 Note that disabling merge_states_p leads to very large output. */
129static const bool merge_states_p = true;
130static const bool collapse_optional_decisions_p = true;
131static const bool cse_tests_p = true;
132static const bool simplify_tests_p = true;
133static const bool use_operand_variables_p = true;
134static const bool use_subroutines_p = true;
135static const bool use_pattern_routines_p = true;
136
137/* Whether to add comments for optional tests that we decided to keep.
138 Can be useful when debugging the generator itself but is noise when
139 debugging the generated code. */
140static const bool mark_optional_transitions_p = false;
141
142/* Whether pattern routines should calculate positions relative to their
143 rtx parameter rather than use absolute positions. This e.g. allows
144 a pattern routine to be shared between a plain SET and a PARALLEL
145 that includes a SET.
146
147 In principle it sounds like this should be useful, especially for
148 recog_for_combine, where the plain SET form is generated automatically
149 from a PARALLEL of a single SET and some CLOBBERs. In practice it doesn't
150 seem to help much and leads to slightly bigger object files. */
151static const bool relative_patterns_p = false;
152
153/* Whether pattern routines should be allowed to test whether pnum_clobbers
154 is null. This requires passing pnum_clobbers around as a parameter. */
155static const bool pattern_have_num_clobbers_p = true;
156
157/* Whether pattern routines should be allowed to test .md file C conditions.
158 This requires passing insn around as a parameter, in case the C
159 condition refers to it. In practice this tends to lead to bigger
160 object files. */
161static const bool pattern_c_test_p = false;
162
163/* Whether to require each parameter passed to a pattern routine to be
164 unique. Disabling this check for example allows unary operators with
165 matching modes (like NEG) and unary operators with mismatched modes
166 (like ZERO_EXTEND) to be matched by a single pattern. However, we then
167 often have cases where the same value is passed too many times. */
168static const bool force_unique_params_p = true;
169
170/* The maximum (approximate) depth of block nesting that an individual
171 routine or subroutine should have. This limit is about keeping the
172 output readable rather than reducing compile time. */
173static const unsigned int MAX_DEPTH = 6;
174
175/* The minimum number of pseudo-statements that a state must have before
176 we split it out into a subroutine. */
177static const unsigned int MIN_NUM_STATEMENTS = 5;
178
179/* The number of pseudo-statements a state can have before we consider
180 splitting out substates into subroutines. This limit is about avoiding
181 compile-time problems with very big functions (and also about keeping
182 functions within --param optimization limits, etc.). */
183static const unsigned int MAX_NUM_STATEMENTS = 200;
184
185/* The minimum number of pseudo-statements that can be used in a pattern
186 routine. */
187static const unsigned int MIN_COMBINE_COST = 4;
188
189/* The maximum number of arguments that a pattern routine can have.
190 The idea is to prevent one pattern getting a ridiculous number of
191 arguments when it would be more beneficial to have a separate pattern
192 routine instead. */
193static const unsigned int MAX_PATTERN_PARAMS = 5;
194
195/* The maximum operand number plus one. */
196int num_operands;
197
198/* Ways of obtaining an rtx to be tested. */
199enum position_type {
200 /* PATTERN (peep2_next_insn (ARG)). */
201 POS_PEEP2_INSN,
202
203 /* XEXP (BASE, ARG). */
204 POS_XEXP,
205
206 /* XVECEXP (BASE, 0, ARG). */
207 POS_XVECEXP0
208};
209
210/* The position of an rtx relative to X0. Each useful position is
211 represented by exactly one instance of this structure. */
212struct position
213{
214 /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
215 struct position *base;
216
217 /* A position with the same BASE and TYPE, but with the next value
218 of ARG. */
219 struct position *next;
220
221 /* A list of all POS_XEXP positions that use this one as their base,
222 chained by NEXT fields. The first entry represents XEXP (this, 0),
223 the second represents XEXP (this, 1), and so on. */
224 struct position *xexps;
225
226 /* A list of POS_XVECEXP0 positions that use this one as their base,
227 chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0),
228 the second represents XVECEXP (this, 0, 1), and so on. */
229 struct position *xvecexp0s;
230
231 /* The type of position. */
232 enum position_type type;
233
234 /* The argument to TYPE (shown as ARG in the position_type comments). */
235 int arg;
236
237 /* The instruction to which the position belongs. */
238 unsigned int insn_id;
239
240 /* The depth of this position relative to the instruction pattern.
241 E.g. if the instruction pattern is a SET, the SET itself has a
242 depth of 0 while the SET_DEST and SET_SRC have depths of 1. */
243 unsigned int depth;
244
245 /* A unique identifier for this position. */
246 unsigned int id;
247};
248
249enum routine_type {
250 SUBPATTERN, RECOG, SPLIT, PEEPHOLE2
251};
252
253/* The root position (x0). */
254static struct position root_pos;
255
256/* The number of positions created. Also one higher than the maximum
257 position id. */
258static unsigned int num_positions = 1;
259
260/* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
261 since we are given that instruction's pattern as x0. */
262static struct position *peep2_insn_pos_list = &root_pos;
263
264/* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
265 points to where the unique object that represents the position
266 should be stored. Create the object if it doesn't already exist,
267 otherwise reuse the object that is already there. */
268
269static struct position *
270next_position (struct position **next_ptr, struct position *base,
271 enum position_type type, int arg)
272{
273 struct position *pos;
274
275 pos = *next_ptr;
276 if (!pos)
277 {
278 pos = XCNEW (struct position);
279 pos->type = type;
280 pos->arg = arg;
281 if (type == POS_PEEP2_INSN)
282 {
283 pos->base = 0;
284 pos->insn_id = arg;
285 pos->depth = base->depth;
286 }
287 else
288 {
289 pos->base = base;
290 pos->insn_id = base->insn_id;
291 pos->depth = base->depth + 1;
292 }
293 pos->id = num_positions++;
294 *next_ptr = pos;
295 }
296 return pos;
297}
298
299/* Compare positions POS1 and POS2 lexicographically. */
300
301static int
302compare_positions (struct position *pos1, struct position *pos2)
303{
304 int diff;
305
306 diff = pos1->depth - pos2->depth;
307 if (diff < 0)
308 do
309 pos2 = pos2->base;
310 while (pos1->depth != pos2->depth);
311 else if (diff > 0)
312 do
313 pos1 = pos1->base;
314 while (pos1->depth != pos2->depth);
315 while (pos1 != pos2)
316 {
317 diff = (int) pos1->type - (int) pos2->type;
318 if (diff == 0)
319 diff = pos1->arg - pos2->arg;
320 pos1 = pos1->base;
321 pos2 = pos2->base;
322 }
323 return diff;
324}
325
326/* Return the most deeply-nested position that is common to both
327 POS1 and POS2. If the positions are from different instructions,
328 return the one with the lowest insn_id. */
329
330static struct position *
331common_position (struct position *pos1, struct position *pos2)
332{
333 if (pos1->insn_id != pos2->insn_id)
334 return pos1->insn_id < pos2->insn_id ? pos1 : pos2;
335 if (pos1->depth > pos2->depth)
336 std::swap (pos1, pos2);
337 while (pos1->depth != pos2->depth)
338 pos2 = pos2->base;
339 while (pos1 != pos2)
340 {
341 pos1 = pos1->base;
342 pos2 = pos2->base;
343 }
344 return pos1;
345}
346
347/* Search for and return operand N, stop when reaching node STOP. */
348
349static rtx
350find_operand (rtx pattern, int n, rtx stop)
351{
352 const char *fmt;
353 RTX_CODE code;
354 int i, j, len;
355 rtx r;
356
357 if (pattern == stop)
358 return stop;
359
360 code = GET_CODE (pattern);
361 if ((code == MATCH_SCRATCH
362 || code == MATCH_OPERAND
363 || code == MATCH_OPERATOR
364 || code == MATCH_PARALLEL)
365 && XINT (pattern, 0) == n)
366 return pattern;
367
368 fmt = GET_RTX_FORMAT (code);
369 len = GET_RTX_LENGTH (code);
370 for (i = 0; i < len; i++)
371 {
372 switch (fmt[i])
373 {
374 case 'e': case 'u':
375 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
376 return r;
377 break;
378
379 case 'V':
380 if (! XVEC (pattern, i))
381 break;
382 /* Fall through. */
383
384 case 'E':
385 for (j = 0; j < XVECLEN (pattern, i); j++)
386 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
387 != NULL_RTX)
388 return r;
389 break;
390
391 case 'i': case 'r': case 'w': case '0': case 's':
392 break;
393
394 default:
395 gcc_unreachable ();
396 }
397 }
398
399 return NULL;
400}
401
402/* Search for and return operand M, such that it has a matching
403 constraint for operand N. */
404
405static rtx
406find_matching_operand (rtx pattern, int n)
407{
408 const char *fmt;
409 RTX_CODE code;
410 int i, j, len;
411 rtx r;
412
413 code = GET_CODE (pattern);
414 if (code == MATCH_OPERAND
415 && (XSTR (pattern, 2)[0] == '0' + n
416 || (XSTR (pattern, 2)[0] == '%'
417 && XSTR (pattern, 2)[1] == '0' + n)))
418 return pattern;
419
420 fmt = GET_RTX_FORMAT (code);
421 len = GET_RTX_LENGTH (code);
422 for (i = 0; i < len; i++)
423 {
424 switch (fmt[i])
425 {
426 case 'e': case 'u':
427 if ((r = find_matching_operand (XEXP (pattern, i), n)))
428 return r;
429 break;
430
431 case 'V':
432 if (! XVEC (pattern, i))
433 break;
434 /* Fall through. */
435
436 case 'E':
437 for (j = 0; j < XVECLEN (pattern, i); j++)
438 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
439 return r;
440 break;
441
442 case 'i': case 'r': case 'w': case '0': case 's':
443 break;
444
445 default:
446 gcc_unreachable ();
447 }
448 }
449
450 return NULL;
451}
452
453/* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
454 don't use the MATCH_OPERAND constraint, only the predicate.
455 This is confusing to folks doing new ports, so help them
456 not make the mistake. */
457
458static bool
459constraints_supported_in_insn_p (rtx insn)
460{
461 return !(GET_CODE (insn) == DEFINE_EXPAND
462 || GET_CODE (insn) == DEFINE_SPLIT
463 || GET_CODE (insn) == DEFINE_PEEPHOLE2);
464}
465
466/* Return the name of the predicate matched by MATCH_RTX. */
467
468static const char *
469predicate_name (rtx match_rtx)
470{
471 if (GET_CODE (match_rtx) == MATCH_SCRATCH)
472 return "scratch_operand";
473 else
474 return XSTR (match_rtx, 1);
475}
476
477/* Return true if OPERAND is a MATCH_OPERAND using a special predicate
478 function. */
479
480static bool
481special_predicate_operand_p (rtx operand)
482{
483 if (GET_CODE (operand) == MATCH_OPERAND)
484 {
485 const char *pred_name = predicate_name (operand);
486 if (pred_name[0] != 0)
487 {
488 const struct pred_data *pred;
489
490 pred = lookup_predicate (pred_name);
491 return pred != NULL && pred->special;
492 }
493 }
494
495 return false;
496}
497
498/* Check for various errors in PATTERN, which is part of INFO.
499 SET is nonnull for a destination, and is the complete set pattern.
500 SET_CODE is '=' for normal sets, and '+' within a context that
501 requires in-out constraints. */
502
503static void
504validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code)
505{
506 const char *fmt;
507 RTX_CODE code;
508 size_t i, len;
509 int j;
510
511 code = GET_CODE (pattern);
512 switch (code)
513 {
514 case MATCH_SCRATCH:
515 {
516 const char constraints0 = XSTR (pattern, 1)[0];
517
518 if (!constraints_supported_in_insn_p (info->def))
519 {
520 if (constraints0)
521 {
522 error_at (info->loc, "constraints not supported in %s",
523 GET_RTX_NAME (GET_CODE (info->def)));
524 }
525 return;
526 }
527
528 /* If a MATCH_SCRATCH is used in a context requiring an write-only
529 or read/write register, validate that. */
530 if (set_code == '='
531 && constraints0
532 && constraints0 != '='
533 && constraints0 != '+')
534 {
535 error_at (info->loc, "operand %d missing output reload",
536 XINT (pattern, 0));
537 }
538 return;
539 }
540 case MATCH_DUP:
541 case MATCH_OP_DUP:
542 case MATCH_PAR_DUP:
543 if (find_operand (info->def, XINT (pattern, 0), pattern) == pattern)
544 error_at (info->loc, "operand %i duplicated before defined",
545 XINT (pattern, 0));
546 break;
547 case MATCH_OPERAND:
548 case MATCH_OPERATOR:
549 {
550 const char *pred_name = XSTR (pattern, 1);
551 const struct pred_data *pred;
552 const char *c_test;
553
554 c_test = get_c_test (info->def);
555
556 if (pred_name[0] != 0)
557 {
558 pred = lookup_predicate (pred_name);
559 if (!pred)
560 error_at (info->loc, "unknown predicate '%s'", pred_name);
561 }
562 else
563 pred = 0;
564
565 if (code == MATCH_OPERAND)
566 {
567 const char *constraints = XSTR (pattern, 2);
568 const char constraints0 = constraints[0];
569
570 if (!constraints_supported_in_insn_p (info->def))
571 {
572 if (constraints0)
573 {
574 error_at (info->loc, "constraints not supported in %s",
575 GET_RTX_NAME (GET_CODE (info->def)));
576 }
577 }
578
579 /* A MATCH_OPERAND that is a SET should have an output reload. */
580 else if (set && constraints0)
581 {
582 if (set_code == '+')
583 {
584 if (constraints0 == '+')
585 ;
586 /* If we've only got an output reload for this operand,
587 we'd better have a matching input operand. */
588 else if (constraints0 == '='
589 && find_matching_operand (info->def,
590 XINT (pattern, 0)))
591 ;
592 else
593 error_at (info->loc, "operand %d missing in-out reload",
594 XINT (pattern, 0));
595 }
596 else if (constraints0 != '=' && constraints0 != '+')
597 error_at (info->loc, "operand %d missing output reload",
598 XINT (pattern, 0));
599 }
600
601 /* For matching constraint in MATCH_OPERAND, the digit must be a
602 smaller number than the number of the operand that uses it in the
603 constraint. */
604 while (1)
605 {
606 while (constraints[0]
607 && (constraints[0] == ' ' || constraints[0] == ','))
608 constraints++;
609 if (!constraints[0])
610 break;
611
612 if (constraints[0] >= '0' && constraints[0] <= '9')
613 {
614 int val;
615
616 sscanf (constraints, "%d", &val);
617 if (val >= XINT (pattern, 0))
618 error_at (info->loc, "constraint digit %d is not"
619 " smaller than operand %d",
620 val, XINT (pattern, 0));
621 }
622
623 while (constraints[0] && constraints[0] != ',')
624 constraints++;
625 }
626 }
627
628 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
629 while not likely to occur at runtime, results in less efficient
630 code from insn-recog.c. */
631 if (set && pred && pred->allows_non_lvalue)
632 error_at (info->loc, "destination operand %d allows non-lvalue",
633 XINT (pattern, 0));
634
635 /* A modeless MATCH_OPERAND can be handy when we can check for
636 multiple modes in the c_test. In most other cases, it is a
637 mistake. Only DEFINE_INSN is eligible, since SPLIT and
638 PEEP2 can FAIL within the output pattern. Exclude special
639 predicates, which check the mode themselves. Also exclude
640 predicates that allow only constants. Exclude the SET_DEST
641 of a call instruction, as that is a common idiom. */
642
643 if (GET_MODE (pattern) == VOIDmode
644 && code == MATCH_OPERAND
645 && GET_CODE (info->def) == DEFINE_INSN
646 && pred
647 && !pred->special
648 && pred->allows_non_const
649 && strstr (c_test, "operands") == NULL
650 && ! (set
651 && GET_CODE (set) == SET
652 && GET_CODE (SET_SRC (set)) == CALL))
653 message_at (info->loc, "warning: operand %d missing mode?",
654 XINT (pattern, 0));
655 return;
656 }
657
658 case SET:
659 {
660 machine_mode dmode, smode;
661 rtx dest, src;
662
663 dest = SET_DEST (pattern);
664 src = SET_SRC (pattern);
665
666 /* STRICT_LOW_PART is a wrapper. Its argument is the real
667 destination, and it's mode should match the source. */
668 if (GET_CODE (dest) == STRICT_LOW_PART)
669 dest = XEXP (dest, 0);
670
671 /* Find the referent for a DUP. */
672
673 if (GET_CODE (dest) == MATCH_DUP
674 || GET_CODE (dest) == MATCH_OP_DUP
675 || GET_CODE (dest) == MATCH_PAR_DUP)
676 dest = find_operand (info->def, XINT (dest, 0), NULL);
677
678 if (GET_CODE (src) == MATCH_DUP
679 || GET_CODE (src) == MATCH_OP_DUP
680 || GET_CODE (src) == MATCH_PAR_DUP)
681 src = find_operand (info->def, XINT (src, 0), NULL);
682
683 dmode = GET_MODE (dest);
684 smode = GET_MODE (src);
685
686 /* Mode checking is not performed for special predicates. */
687 if (special_predicate_operand_p (src)
688 || special_predicate_operand_p (dest))
689 ;
690
691 /* The operands of a SET must have the same mode unless one
692 is VOIDmode. */
693 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
694 error_at (info->loc, "mode mismatch in set: %smode vs %smode",
695 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
696
697 /* If only one of the operands is VOIDmode, and PC or CC0 is
698 not involved, it's probably a mistake. */
699 else if (dmode != smode
700 && GET_CODE (dest) != PC
701 && GET_CODE (dest) != CC0
702 && GET_CODE (src) != PC
703 && GET_CODE (src) != CC0
704 && !CONST_INT_P (src)
705 && !CONST_WIDE_INT_P (src)
706 && GET_CODE (src) != CALL)
707 {
708 const char *which;
709 which = (dmode == VOIDmode ? "destination" : "source");
710 message_at (info->loc, "warning: %s missing a mode?", which);
711 }
712
713 if (dest != SET_DEST (pattern))
714 validate_pattern (dest, info, pattern, '=');
715 validate_pattern (SET_DEST (pattern), info, pattern, '=');
716 validate_pattern (SET_SRC (pattern), info, NULL_RTX, 0);
717 return;
718 }
719
720 case CLOBBER:
721 validate_pattern (SET_DEST (pattern), info, pattern, '=');
722 return;
723
724 case ZERO_EXTRACT:
725 validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0);
726 validate_pattern (XEXP (pattern, 1), info, NULL_RTX, 0);
727 validate_pattern (XEXP (pattern, 2), info, NULL_RTX, 0);
728 return;
729
730 case STRICT_LOW_PART:
731 validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0);
732 return;
733
734 case LABEL_REF:
735 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
736 error_at (info->loc, "operand to label_ref %smode not VOIDmode",
737 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
738 break;
739
740 case VEC_SELECT:
741 if (GET_MODE (pattern) != VOIDmode)
742 {
743 machine_mode mode = GET_MODE (pattern);
744 machine_mode imode = GET_MODE (XEXP (pattern, 0));
745 machine_mode emode
746 = VECTOR_MODE_P (mode) ? GET_MODE_INNER (mode) : mode;
747 if (GET_CODE (XEXP (pattern, 1)) == PARALLEL)
748 {
749 int expected = VECTOR_MODE_P (mode) ? GET_MODE_NUNITS (mode) : 1;
750 if (XVECLEN (XEXP (pattern, 1), 0) != expected)
751 error_at (info->loc,
752 "vec_select parallel with %d elements, expected %d",
753 XVECLEN (XEXP (pattern, 1), 0), expected);
754 else if (VECTOR_MODE_P (imode))
755 {
756 unsigned int nelems = GET_MODE_NUNITS (imode);
757 int i;
758 for (i = 0; i < expected; ++i)
759 if (CONST_INT_P (XVECEXP (XEXP (pattern, 1), 0, i))
760 && (UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i))
761 >= nelems))
762 error_at (info->loc,
763 "out of bounds selector %u in vec_select, "
764 "expected at most %u",
765 (unsigned)
766 UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)),
767 nelems - 1);
768 }
769 }
770 if (imode != VOIDmode && !VECTOR_MODE_P (imode))
771 error_at (info->loc, "%smode of first vec_select operand is not a "
772 "vector mode", GET_MODE_NAME (imode));
773 else if (imode != VOIDmode && GET_MODE_INNER (imode) != emode)
774 error_at (info->loc, "element mode mismatch between vec_select "
775 "%smode and its operand %smode",
776 GET_MODE_NAME (emode),
777 GET_MODE_NAME (GET_MODE_INNER (imode)));
778 }
779 break;
780
781 default:
782 break;
783 }
784
785 fmt = GET_RTX_FORMAT (code);
786 len = GET_RTX_LENGTH (code);
787 for (i = 0; i < len; i++)
788 {
789 switch (fmt[i])
790 {
791 case 'e': case 'u':
792 validate_pattern (XEXP (pattern, i), info, NULL_RTX, 0);
793 break;
794
795 case 'E':
796 for (j = 0; j < XVECLEN (pattern, i); j++)
797 validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, 0);
798 break;
799
800 case 'i': case 'r': case 'w': case '0': case 's':
801 break;
802
803 default:
804 gcc_unreachable ();
805 }
806 }
807}
808
809/* Simple list structure for items of type T, for use when being part
810 of a list is an inherent property of T. T must have members equivalent
811 to "T *prev, *next;" and a function "void set_parent (list_head <T> *)"
812 to set the parent list. */
813template <typename T>
814struct list_head
815{
816 /* A range of linked items. */
817 struct range
818 {
819 range (T *);
820 range (T *, T *);
821
822 T *start, *end;
823 void set_parent (list_head *);
824 };
825
826 list_head ();
827 range release ();
828 void push_back (range);
829 range remove (range);
830 void replace (range, range);
831 T *singleton () const;
832
833 T *first, *last;
834};
835
836/* Create a range [START_IN, START_IN]. */
837
838template <typename T>
839list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {}
840
841/* Create a range [START_IN, END_IN], linked by next and prev fields. */
842
843template <typename T>
844list_head <T>::range::range (T *start_in, T *end_in)
845 : start (start_in), end (end_in) {}
846
847template <typename T>
848void
849list_head <T>::range::set_parent (list_head <T> *owner)
850{
851 for (T *item = start; item != end; item = item->next)
852 item->set_parent (owner);
853 end->set_parent (owner);
854}
855
856template <typename T>
857list_head <T>::list_head () : first (0), last (0) {}
858
859/* Add R to the end of the list. */
860
861template <typename T>
862void
863list_head <T>::push_back (range r)
864{
865 if (last)
866 last->next = r.start;
867 else
868 first = r.start;
869 r.start->prev = last;
870 last = r.end;
871 r.set_parent (this);
872}
873
874/* Remove R from the list. R remains valid and can be inserted into
875 other lists. */
876
877template <typename T>
878typename list_head <T>::range
879list_head <T>::remove (range r)
880{
881 if (r.start->prev)
882 r.start->prev->next = r.end->next;
883 else
884 first = r.end->next;
885 if (r.end->next)
886 r.end->next->prev = r.start->prev;
887 else
888 last = r.start->prev;
889 r.start->prev = 0;
890 r.end->next = 0;
891 r.set_parent (0);
892 return r;
893}
894
895/* Replace OLDR with NEWR. OLDR remains valid and can be inserted into
896 other lists. */
897
898template <typename T>
899void
900list_head <T>::replace (range oldr, range newr)
901{
902 newr.start->prev = oldr.start->prev;
903 newr.end->next = oldr.end->next;
904
905 oldr.start->prev = 0;
906 oldr.end->next = 0;
907 oldr.set_parent (0);
908
909 if (newr.start->prev)
910 newr.start->prev->next = newr.start;
911 else
912 first = newr.start;
913 if (newr.end->next)
914 newr.end->next->prev = newr.end;
915 else
916 last = newr.end;
917 newr.set_parent (this);
918}
919
920/* Empty the list and return the previous contents as a range that can
921 be inserted into other lists. */
922
923template <typename T>
924typename list_head <T>::range
925list_head <T>::release ()
926{
927 range r (first, last);
928 first = 0;
929 last = 0;
930 r.set_parent (0);
931 return r;
932}
933
934/* If the list contains a single item, return that item, otherwise return
935 null. */
936
937template <typename T>
938T *
939list_head <T>::singleton () const
940{
941 return first == last ? first : 0;
942}
943
944struct state;
945
946/* Describes a possible successful return from a routine. */
947struct acceptance_type
948{
949 /* The type of routine we're returning from. */
950 routine_type type : 16;
951
952 /* True if this structure only really represents a partial match,
953 and if we must call a subroutine of type TYPE to complete the match.
954 In this case we'll call the subroutine and, if it succeeds, return
955 whatever the subroutine returned.
956
957 False if this structure presents a full match. */
958 unsigned int partial_p : 1;
959
960 union
961 {
962 /* If PARTIAL_P, this is the number of the subroutine to call. */
963 int subroutine_id;
964
965 /* Valid if !PARTIAL_P. */
966 struct
967 {
968 /* The identifier of the matching pattern. For SUBPATTERNs this
969 value belongs to an ad-hoc routine-specific enum. For the
970 others it's the number of an .md file pattern. */
971 int code;
972 union
973 {
974 /* For RECOG, the number of clobbers that must be added to the
975 pattern in order for it to match CODE. */
976 int num_clobbers;
977
978 /* For PEEPHOLE2, the number of additional instructions that were
979 included in the optimization. */
980 int match_len;
981 } u;
982 } full;
983 } u;
984};
985
986bool
987operator == (const acceptance_type &a, const acceptance_type &b)
988{
989 if (a.partial_p != b.partial_p)
990 return false;
991 if (a.partial_p)
992 return a.u.subroutine_id == b.u.subroutine_id;
993 else
994 return a.u.full.code == b.u.full.code;
995}
996
997bool
998operator != (const acceptance_type &a, const acceptance_type &b)
999{
1000 return !operator == (a, b);
1001}
1002
1003/* Represents a parameter to a pattern routine. */
1004struct parameter
1005{
1006 /* The C type of parameter. */
1007 enum type_enum {
1008 /* Represents an invalid parameter. */
1009 UNSET,
1010
1011 /* A machine_mode parameter. */
1012 MODE,
1013
1014 /* An rtx_code parameter. */
1015 CODE,
1016
1017 /* An int parameter. */
1018 INT,
1019
1020 /* An unsigned int parameter. */
1021 UINT,
1022
1023 /* A HOST_WIDE_INT parameter. */
1024 WIDE_INT
1025 };
1026
1027 parameter ();
1028 parameter (type_enum, bool, uint64_t);
1029
1030 /* The type of the parameter. */
1031 type_enum type;
1032
1033 /* True if the value passed is variable, false if it is constant. */
1034 bool is_param;
1035
1036 /* If IS_PARAM, this is the number of the variable passed, for an "i%d"
1037 format string. If !IS_PARAM, this is the constant value passed. */
1038 uint64_t value;
1039};
1040
1041parameter::parameter ()
1042 : type (UNSET), is_param (false), value (0) {}
1043
1044parameter::parameter (type_enum type_in, bool is_param_in, uint64_t value_in)
1045 : type (type_in), is_param (is_param_in), value (value_in) {}
1046
1047bool
1048operator == (const parameter &param1, const parameter &param2)
1049{
1050 return (param1.type == param2.type
1051 && param1.is_param == param2.is_param
1052 && param1.value == param2.value);
1053}
1054
1055bool
1056operator != (const parameter &param1, const parameter &param2)
1057{
1058 return !operator == (param1, param2);
1059}
1060
1061/* Represents a routine that matches a partial rtx pattern, returning
1062 an ad-hoc enum value on success and -1 on failure. The routine can
1063 be used by any subroutine type. The match can be parameterized by
1064 things like mode, code and UNSPEC number. */
1065struct pattern_routine
1066{
1067 /* The state that implements the pattern. */
1068 state *s;
1069
1070 /* The deepest root position from which S can access all the rtxes it needs.
1071 This is NULL if the pattern doesn't need an rtx input, usually because
1072 all matching is done on operands[] instead. */
1073 position *pos;
1074
1075 /* A unique identifier for the routine. */
1076 unsigned int pattern_id;
1077
1078 /* True if the routine takes pnum_clobbers as argument. */
1079 bool pnum_clobbers_p;
1080
1081 /* True if the routine takes the enclosing instruction as argument. */
1082 bool insn_p;
1083
1084 /* The types of the other parameters to the routine, if any. */
1085 auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types;
1086};
1087
1088/* All defined patterns. */
1089static vec <pattern_routine *> patterns;
1090
1091/* Represents one use of a pattern routine. */
1092struct pattern_use
1093{
1094 /* The pattern routine to use. */
1095 pattern_routine *routine;
1096
1097 /* The values to pass as parameters. This vector has the same length
1098 as ROUTINE->PARAM_TYPES. */
1099 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
1100};
1101
1102/* Represents a test performed by a decision. */
1103struct rtx_test
1104{
1105 rtx_test ();
1106
1107 /* The types of test that can be performed. Most of them take as input
1108 an rtx X. Some also take as input a transition label LABEL; the others
1109 are booleans for which the transition label is always "true".
1110
1111 The order of the enum isn't important. */
1112 enum kind_enum {
1113 /* Check GET_CODE (X) == LABEL. */
1114 CODE,
1115
1116 /* Check GET_MODE (X) == LABEL. */
1117 MODE,
1118
1119 /* Check REGNO (X) == LABEL. */
1120 REGNO_FIELD,
1121
1122 /* Check XINT (X, u.opno) == LABEL. */
1123 INT_FIELD,
1124
1125 /* Check XWINT (X, u.opno) == LABEL. */
1126 WIDE_INT_FIELD,
1127
1128 /* Check XVECLEN (X, 0) == LABEL. */
1129 VECLEN,
1130
1131 /* Check peep2_current_count >= u.min_len. */
1132 PEEP2_COUNT,
1133
1134 /* Check XVECLEN (X, 0) >= u.min_len. */
1135 VECLEN_GE,
1136
1137 /* Check whether X is a cached const_int with value u.integer. */
1138 SAVED_CONST_INT,
1139
1140 /* Check u.predicate.data (X, u.predicate.mode). */
1141 PREDICATE,
1142
1143 /* Check rtx_equal_p (X, operands[u.opno]). */
1144 DUPLICATE,
1145
1146 /* Check whether X matches pattern u.pattern. */
1147 PATTERN,
1148
1149 /* Check whether pnum_clobbers is nonnull (RECOG only). */
1150 HAVE_NUM_CLOBBERS,
1151
1152 /* Check whether general C test u.string holds. In general the condition
1153 needs access to "insn" and the full operand list. */
1154 C_TEST,
1155
1156 /* Execute operands[u.opno] = X. (Always succeeds.) */
1157 SET_OP,
1158
1159 /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT.
1160 May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */
1161 ACCEPT
1162 };
1163
1164 /* The position of rtx X in the above description, relative to the
1165 incoming instruction "insn". The position is null if the test
1166 doesn't take an X as input. */
1167 position *pos;
1168
1169 /* Which element of operands[] already contains POS, or -1 if no element
1170 is known to hold POS. */
1171 int pos_operand;
1172
1173 /* The type of test and its parameters, as described above. */
1174 kind_enum kind;
1175 union
1176 {
1177 int opno;
1178 int min_len;
1179 struct
1180 {
1181 bool is_param;
1182 int value;
1183 } integer;
1184 struct
1185 {
1186 const struct pred_data *data;
1187 /* True if the mode is taken from a machine_mode parameter
1188 to the routine rather than a constant machine_mode. If true,
1189 MODE is the number of the parameter (for an "i%d" format string),
1190 otherwise it is the mode itself. */
1191 bool mode_is_param;
1192 unsigned int mode;
1193 } predicate;
1194 pattern_use *pattern;
1195 const char *string;
1196 acceptance_type acceptance;
1197 } u;
1198
1199 static rtx_test code (position *);
1200 static rtx_test mode (position *);
1201 static rtx_test regno_field (position *);
1202 static rtx_test int_field (position *, int);
1203 static rtx_test wide_int_field (position *, int);
1204 static rtx_test veclen (position *);
1205 static rtx_test peep2_count (int);
1206 static rtx_test veclen_ge (position *, int);
1207 static rtx_test predicate (position *, const pred_data *, machine_mode);
1208 static rtx_test duplicate (position *, int);
1209 static rtx_test pattern (position *, pattern_use *);
1210 static rtx_test have_num_clobbers ();
1211 static rtx_test c_test (const char *);
1212 static rtx_test set_op (position *, int);
1213 static rtx_test accept (const acceptance_type &);
1214
1215 bool terminal_p () const;
1216 bool single_outcome_p () const;
1217
1218private:
1219 rtx_test (position *, kind_enum);
1220};
1221
1222rtx_test::rtx_test () {}
1223
1224rtx_test::rtx_test (position *pos_in, kind_enum kind_in)
1225 : pos (pos_in), pos_operand (-1), kind (kind_in) {}
1226
1227rtx_test
1228rtx_test::code (position *pos)
1229{
1230 return rtx_test (pos, rtx_test::CODE);
1231}
1232
1233rtx_test
1234rtx_test::mode (position *pos)
1235{
1236 return rtx_test (pos, rtx_test::MODE);
1237}
1238
1239rtx_test
1240rtx_test::regno_field (position *pos)
1241{
1242 rtx_test res (pos, rtx_test::REGNO_FIELD);
1243 return res;
1244}
1245
1246rtx_test
1247rtx_test::int_field (position *pos, int opno)
1248{
1249 rtx_test res (pos, rtx_test::INT_FIELD);
1250 res.u.opno = opno;
1251 return res;
1252}
1253
1254rtx_test
1255rtx_test::wide_int_field (position *pos, int opno)
1256{
1257 rtx_test res (pos, rtx_test::WIDE_INT_FIELD);
1258 res.u.opno = opno;
1259 return res;
1260}
1261
1262rtx_test
1263rtx_test::veclen (position *pos)
1264{
1265 return rtx_test (pos, rtx_test::VECLEN);
1266}
1267
1268rtx_test
1269rtx_test::peep2_count (int min_len)
1270{
1271 rtx_test res (0, rtx_test::PEEP2_COUNT);
1272 res.u.min_len = min_len;
1273 return res;
1274}
1275
1276rtx_test
1277rtx_test::veclen_ge (position *pos, int min_len)
1278{
1279 rtx_test res (pos, rtx_test::VECLEN_GE);
1280 res.u.min_len = min_len;
1281 return res;
1282}
1283
1284rtx_test
1285rtx_test::predicate (position *pos, const struct pred_data *data,
1286 machine_mode mode)
1287{
1288 rtx_test res (pos, rtx_test::PREDICATE);
1289 res.u.predicate.data = data;
1290 res.u.predicate.mode_is_param = false;
1291 res.u.predicate.mode = mode;
1292 return res;
1293}
1294
1295rtx_test
1296rtx_test::duplicate (position *pos, int opno)
1297{
1298 rtx_test res (pos, rtx_test::DUPLICATE);
1299 res.u.opno = opno;
1300 return res;
1301}
1302
1303rtx_test
1304rtx_test::pattern (position *pos, pattern_use *pattern)
1305{
1306 rtx_test res (pos, rtx_test::PATTERN);
1307 res.u.pattern = pattern;
1308 return res;
1309}
1310
1311rtx_test
1312rtx_test::have_num_clobbers ()
1313{
1314 return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS);
1315}
1316
1317rtx_test
1318rtx_test::c_test (const char *string)
1319{
1320 rtx_test res (0, rtx_test::C_TEST);
1321 res.u.string = string;
1322 return res;
1323}
1324
1325rtx_test
1326rtx_test::set_op (position *pos, int opno)
1327{
1328 rtx_test res (pos, rtx_test::SET_OP);
1329 res.u.opno = opno;
1330 return res;
1331}
1332
1333rtx_test
1334rtx_test::accept (const acceptance_type &acceptance)
1335{
1336 rtx_test res (0, rtx_test::ACCEPT);
1337 res.u.acceptance = acceptance;
1338 return res;
1339}
1340
1341/* Return true if the test represents an unconditionally successful match. */
1342
1343bool
1344rtx_test::terminal_p () const
1345{
1346 return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2;
1347}
1348
1349/* Return true if the test is a boolean that is always true. */
1350
1351bool
1352rtx_test::single_outcome_p () const
1353{
1354 return terminal_p () || kind == rtx_test::SET_OP;
1355}
1356
1357bool
1358operator == (const rtx_test &a, const rtx_test &b)
1359{
1360 if (a.pos != b.pos || a.kind != b.kind)
1361 return false;
1362 switch (a.kind)
1363 {
1364 case rtx_test::CODE:
1365 case rtx_test::MODE:
1366 case rtx_test::REGNO_FIELD:
1367 case rtx_test::VECLEN:
1368 case rtx_test::HAVE_NUM_CLOBBERS:
1369 return true;
1370
1371 case rtx_test::PEEP2_COUNT:
1372 case rtx_test::VECLEN_GE:
1373 return a.u.min_len == b.u.min_len;
1374
1375 case rtx_test::INT_FIELD:
1376 case rtx_test::WIDE_INT_FIELD:
1377 case rtx_test::DUPLICATE:
1378 case rtx_test::SET_OP:
1379 return a.u.opno == b.u.opno;
1380
1381 case rtx_test::SAVED_CONST_INT:
1382 return (a.u.integer.is_param == b.u.integer.is_param
1383 && a.u.integer.value == b.u.integer.value);
1384
1385 case rtx_test::PREDICATE:
1386 return (a.u.predicate.data == b.u.predicate.data
1387 && a.u.predicate.mode_is_param == b.u.predicate.mode_is_param
1388 && a.u.predicate.mode == b.u.predicate.mode);
1389
1390 case rtx_test::PATTERN:
1391 return (a.u.pattern->routine == b.u.pattern->routine
1392 && a.u.pattern->params == b.u.pattern->params);
1393
1394 case rtx_test::C_TEST:
1395 return strcmp (a.u.string, b.u.string) == 0;
1396
1397 case rtx_test::ACCEPT:
1398 return a.u.acceptance == b.u.acceptance;
1399 }
1400 gcc_unreachable ();
1401}
1402
1403bool
1404operator != (const rtx_test &a, const rtx_test &b)
1405{
1406 return !operator == (a, b);
1407}
1408
1409/* A simple set of transition labels. Most transitions have a singleton
1410 label, so try to make that case as efficient as possible. */
1411struct int_set : public auto_vec <uint64_t, 1>
1412{
1413 typedef uint64_t *iterator;
1414
1415 int_set ();
1416 int_set (uint64_t);
1417 int_set (const int_set &);
1418
1419 int_set &operator = (const int_set &);
1420
1421 iterator begin ();
1422 iterator end ();
1423};
1424
1425int_set::int_set () : auto_vec<uint64_t, 1> () {}
1426
1427int_set::int_set (uint64_t label) :
1428 auto_vec<uint64_t, 1> ()
1429{
1430 safe_push (label);
1431}
1432
1433int_set::int_set (const int_set &other) :
1434 auto_vec<uint64_t, 1> ()
1435{
1436 safe_splice (other);
1437}
1438
1439int_set &
1440int_set::operator = (const int_set &other)
1441{
1442 truncate (0);
1443 safe_splice (other);
1444 return *this;
1445}
1446
1447int_set::iterator
1448int_set::begin ()
1449{
1450 return address ();
1451}
1452
1453int_set::iterator
1454int_set::end ()
1455{
1456 return address () + length ();
1457}
1458
1459bool
1460operator == (const int_set &a, const int_set &b)
1461{
1462 if (a.length () != b.length ())
1463 return false;
1464 for (unsigned int i = 0; i < a.length (); ++i)
1465 if (a[i] != b[i])
1466 return false;
1467 return true;
1468}
1469
1470bool
1471operator != (const int_set &a, const int_set &b)
1472{
1473 return !operator == (a, b);
1474}
1475
1476struct decision;
1477
1478/* Represents a transition between states, dependent on the result of
1479 a test T. */
1480struct transition
1481{
1482 transition (const int_set &, state *, bool);
1483
1484 void set_parent (list_head <transition> *);
1485
1486 /* Links to other transitions for T. Always null for boolean tests. */
1487 transition *prev, *next;
1488
1489 /* The transition should be taken when T has one of these values.
1490 E.g. for rtx_test::CODE this is a set of codes, while for booleans like
1491 rtx_test::PREDICATE it is always a singleton "true". The labels are
1492 sorted in ascending order. */
1493 int_set labels;
1494
1495 /* The source decision. */
1496 decision *from;
1497
1498 /* The target state. */
1499 state *to;
1500
1501 /* True if TO would function correctly even if TEST wasn't performed.
1502 E.g. it isn't necessary to check whether GET_MODE (x1) is SImode
1503 before calling register_operand (x1, SImode), since register_operand
1504 performs its own mode check. However, checking GET_MODE can be a cheap
1505 way of disambiguating SImode and DImode register operands. */
1506 bool optional;
1507
1508 /* True if LABELS contains parameter numbers rather than constants.
1509 E.g. if this is true for a rtx_test::CODE, the label is the number
1510 of an rtx_code parameter rather than an rtx_code itself.
1511 LABELS is always a singleton when this variable is true. */
1512 bool is_param;
1513};
1514
1515/* Represents a test and the action that should be taken on the result.
1516 If a transition exists for the test outcome, the machine switches
1517 to the transition's target state. If no suitable transition exists,
1518 the machine either falls through to the next decision or, if there are no
1519 more decisions to try, fails the match. */
1520struct decision : list_head <transition>
1521{
1522 decision (const rtx_test &);
1523
1524 void set_parent (list_head <decision> *s);
1525 bool if_statement_p (uint64_t * = 0) const;
1526
1527 /* The state to which this decision belongs. */
1528 state *s;
1529
1530 /* Links to other decisions in the same state. */
1531 decision *prev, *next;
1532
1533 /* The test to perform. */
1534 rtx_test test;
1535};
1536
1537/* Represents one machine state. For each state the machine tries a list
1538 of decisions, in order, and acts on the first match. It fails without
1539 further backtracking if no decisions match. */
1540struct state : list_head <decision>
1541{
1542 void set_parent (list_head <state> *) {}
1543};
1544
1545transition::transition (const int_set &labels_in, state *to_in,
1546 bool optional_in)
1547 : prev (0), next (0), labels (labels_in), from (0), to (to_in),
1548 optional (optional_in), is_param (false) {}
1549
1550/* Set the source decision of the transition. */
1551
1552void
1553transition::set_parent (list_head <transition> *from_in)
1554{
1555 from = static_cast <decision *> (from_in);
1556}
1557
1558decision::decision (const rtx_test &test_in)
1559 : prev (0), next (0), test (test_in) {}
1560
1561/* Set the state to which this decision belongs. */
1562
1563void
1564decision::set_parent (list_head <decision> *s_in)
1565{
1566 s = static_cast <state *> (s_in);
1567}
1568
1569/* Return true if the decision has a single transition with a single label.
1570 If so, return the label in *LABEL if nonnull. */
1571
1572inline bool
1573decision::if_statement_p (uint64_t *label) const
1574{
1575 if (singleton () && first->labels.length () == 1)
1576 {
1577 if (label)
1578 *label = first->labels[0];
1579 return true;
1580 }
1581 return false;
1582}
1583
1584/* Add to FROM a decision that performs TEST and has a single transition
1585 TRANS. */
1586
1587static void
1588add_decision (state *from, const rtx_test &test, transition *trans)
1589{
1590 decision *d = new decision (test);
1591 from->push_back (d);
1592 d->push_back (trans);
1593}
1594
1595/* Add a transition from FROM to a new, empty state that is taken
1596 when TEST == LABELS. OPTIONAL says whether the new transition
1597 should be optional. Return the new state. */
1598
1599static state *
1600add_decision (state *from, const rtx_test &test, int_set labels, bool optional)
1601{
1602 state *to = new state;
1603 add_decision (from, test, new transition (labels, to, optional));
1604 return to;
1605}
1606
1607/* Insert a decision before decisions R to make them dependent on
1608 TEST == LABELS. OPTIONAL says whether the new transition should be
1609 optional. */
1610
1611static decision *
1612insert_decision_before (state::range r, const rtx_test &test,
1613 const int_set &labels, bool optional)
1614{
1615 decision *newd = new decision (test);
1616 state *news = new state;
1617 newd->push_back (new transition (labels, news, optional));
1618 r.start->s->replace (r, newd);
1619 news->push_back (r);
1620 return newd;
1621}
1622
1623/* Remove any optional transitions from S that turned out not to be useful. */
1624
1625static void
1626collapse_optional_decisions (state *s)
1627{
1628 decision *d = s->first;
1629 while (d)
1630 {
1631 decision *next = d->next;
1632 for (transition *trans = d->first; trans; trans = trans->next)
1633 collapse_optional_decisions (trans->to);
1634 /* A decision with a single optional transition doesn't help
1635 partition the potential matches and so is unlikely to be
1636 worthwhile. In particular, if the decision that performs the
1637 test is the last in the state, the best it could do is reject
1638 an invalid pattern slightly earlier. If instead the decision
1639 is not the last in the state, the condition it tests could hold
1640 even for the later decisions in the state. The best it can do
1641 is save work in some cases where only the later decisions can
1642 succeed.
1643
1644 In both cases the optional transition would add extra work to
1645 successful matches when the tested condition holds. */
1646 if (transition *trans = d->singleton ())
1647 if (trans->optional)
1648 s->replace (d, trans->to->release ());
1649 d = next;
1650 }
1651}
1652
1653/* Try to squash several separate tests into simpler ones. */
1654
1655static void
1656simplify_tests (state *s)
1657{
1658 for (decision *d = s->first; d; d = d->next)
1659 {
1660 uint64_t label;
1661 /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N
1662 into checks for const_int_rtx[N'], if N is suitably small. */
1663 if (d->test.kind == rtx_test::CODE
1664 && d->if_statement_p (&label)
1665 && label == CONST_INT)
1666 if (decision *second = d->first->to->singleton ())
1667 if (d->test.pos == second->test.pos
1668 && second->test.kind == rtx_test::WIDE_INT_FIELD
1669 && second->test.u.opno == 0
1670 && second->if_statement_p (&label)
1671 && IN_RANGE (int64_t (label),
1672 -MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT))
1673 {
1674 d->test.kind = rtx_test::SAVED_CONST_INT;
1675 d->test.u.integer.is_param = false;
1676 d->test.u.integer.value = label;
1677 d->replace (d->first, second->release ());
1678 d->first->labels[0] = true;
1679 }
1680 /* If we have a CODE test followed by a PREDICATE test, rely on
1681 the predicate to test the code.
1682
1683 This case exists for match_operators. We initially treat the
1684 CODE test for a match_operator as non-optional so that we can
1685 safely move down to its operands. It may turn out that all
1686 paths that reach that code test require the same predicate
1687 to be true. cse_tests will then put the predicate test in
1688 series with the code test. */
1689 if (d->test.kind == rtx_test::CODE)
1690 if (transition *trans = d->singleton ())
1691 {
1692 state *s = trans->to;
1693 while (decision *d2 = s->singleton ())
1694 {
1695 if (d->test.pos != d2->test.pos)
1696 break;
1697 transition *trans2 = d2->singleton ();
1698 if (!trans2)
1699 break;
1700 if (d2->test.kind == rtx_test::PREDICATE)
1701 {
1702 d->test = d2->test;
1703 trans->labels = int_set (true);
1704 s->replace (d2, trans2->to->release ());
1705 break;
1706 }
1707 s = trans2->to;
1708 }
1709 }
1710 for (transition *trans = d->first; trans; trans = trans->next)
1711 simplify_tests (trans->to);
1712 }
1713}
1714
1715/* Return true if all successful returns passing through D require the
1716 condition tested by COMMON to be true.
1717
1718 When returning true, add all transitions like COMMON in D to WHERE.
1719 WHERE may contain a partial result on failure. */
1720
1721static bool
1722common_test_p (decision *d, transition *common, vec <transition *> *where)
1723{
1724 if (d->test.kind == rtx_test::ACCEPT)
1725 /* We found a successful return that didn't require COMMON. */
1726 return false;
1727 if (d->test == common->from->test)
1728 {
1729 transition *trans = d->singleton ();
1730 if (!trans
1731 || trans->optional != common->optional
1732 || trans->labels != common->labels)
1733 return false;
1734 where->safe_push (trans);
1735 return true;
1736 }
1737 for (transition *trans = d->first; trans; trans = trans->next)
1738 for (decision *subd = trans->to->first; subd; subd = subd->next)
1739 if (!common_test_p (subd, common, where))
1740 return false;
1741 return true;
1742}
1743
1744/* Indicates that we have tested GET_CODE (X) for a particular rtx X. */
1745const unsigned char TESTED_CODE = 1;
1746
1747/* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */
1748const unsigned char TESTED_VECLEN = 2;
1749
1750/* Represents a set of conditions that are known to hold. */
1751struct known_conditions
1752{
1753 /* A mask of TESTED_ values for each position, indexed by the position's
1754 id field. */
1755 auto_vec <unsigned char> position_tests;
1756
1757 /* Index N says whether operands[N] has been set. */
1758 auto_vec <bool> set_operands;
1759
1760 /* A guranteed lower bound on the value of peep2_current_count. */
1761 int peep2_count;
1762};
1763
1764/* Return true if TEST can safely be performed at D, where
1765 the conditions in KC hold. TEST is known to occur along the
1766 first path from D (i.e. always following the first transition
1767 of the first decision). Any intervening tests can be used as
1768 negative proof that hoisting isn't safe, but only KC can be used
1769 as positive proof. */
1770
1771static bool
1772safe_to_hoist_p (decision *d, const rtx_test &test, known_conditions *kc)
1773{
1774 switch (test.kind)
1775 {
1776 case rtx_test::C_TEST:
1777 /* In general, C tests require everything else to have been
1778 verified and all operands to have been set up. */
1779 return false;
1780
1781 case rtx_test::ACCEPT:
1782 /* Don't accept something before all conditions have been tested. */
1783 return false;
1784
1785 case rtx_test::PREDICATE:
1786 /* Don't move a predicate over a test for VECLEN_GE, since the
1787 predicate used in a match_parallel can legitimately expect the
1788 length to be checked first. */
1789 for (decision *subd = d;
1790 subd->test != test;
1791 subd = subd->first->to->first)
1792 if (subd->test.pos == test.pos
1793 && subd->test.kind == rtx_test::VECLEN_GE)
1794 return false;
1795 goto any_rtx;
1796
1797 case rtx_test::DUPLICATE:
1798 /* Don't test for a match_dup until the associated operand has
1799 been set. */
1800 if (!kc->set_operands[test.u.opno])
1801 return false;
1802 goto any_rtx;
1803
1804 case rtx_test::CODE:
1805 case rtx_test::MODE:
1806 case rtx_test::SAVED_CONST_INT:
1807 case rtx_test::SET_OP:
1808 any_rtx:
1809 /* Check whether it is safe to access the rtx under test. */
1810 switch (test.pos->type)
1811 {
1812 case POS_PEEP2_INSN:
1813 return test.pos->arg < kc->peep2_count;
1814
1815 case POS_XEXP:
1816 return kc->position_tests[test.pos->base->id] & TESTED_CODE;
1817
1818 case POS_XVECEXP0:
1819 return kc->position_tests[test.pos->base->id] & TESTED_VECLEN;
1820 }
1821 gcc_unreachable ();
1822
1823 case rtx_test::REGNO_FIELD:
1824 case rtx_test::INT_FIELD:
1825 case rtx_test::WIDE_INT_FIELD:
1826 case rtx_test::VECLEN:
1827 case rtx_test::VECLEN_GE:
1828 /* These tests access a specific part of an rtx, so are only safe
1829 once we know what the rtx is. */
1830 return kc->position_tests[test.pos->id] & TESTED_CODE;
1831
1832 case rtx_test::PEEP2_COUNT:
1833 case rtx_test::HAVE_NUM_CLOBBERS:
1834 /* These tests can be performed anywhere. */
1835 return true;
1836
1837 case rtx_test::PATTERN:
1838 gcc_unreachable ();
1839 }
1840 gcc_unreachable ();
1841}
1842
1843/* Look for a transition that is taken by all successful returns from a range
1844 of decisions starting at OUTER and that would be better performed by
1845 OUTER's state instead. On success, store all instances of that transition
1846 in WHERE and return the last decision in the range. The range could
1847 just be OUTER, or it could include later decisions as well.
1848
1849 WITH_POSITION_P is true if only tests with position POS should be tried,
1850 false if any test should be tried. WORTHWHILE_SINGLE_P is true if the
1851 result is useful even when the range contains just a single decision
1852 with a single transition. KC are the conditions that are known to
1853 hold at OUTER. */
1854
1855static decision *
1856find_common_test (decision *outer, bool with_position_p,
1857 position *pos, bool worthwhile_single_p,
1858 known_conditions *kc, vec <transition *> *where)
1859{
1860 /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains
1861 just a single decision is useful, regardless of the number of
1862 transitions it has. */
1863 if (!outer->singleton ())
1864 worthwhile_single_p = true;
1865 /* Quick exit if we don't have enough decisions to form a worthwhile
1866 range. */
1867 if (!worthwhile_single_p && !outer->next)
1868 return 0;
1869 /* Follow the first chain down, as one example of a path that needs
1870 to contain the common test. */
1871 for (decision *d = outer; d; d = d->first->to->first)
1872 {
1873 transition *trans = d->singleton ();
1874 if (trans
1875 && (!with_position_p || d->test.pos == pos)
1876 && safe_to_hoist_p (outer, d->test, kc))
1877 {
1878 if (common_test_p (outer, trans, where))
1879 {
1880 if (!outer->next)
1881 /* We checked above whether the move is worthwhile. */
1882 return outer;
1883 /* See how many decisions in OUTER's chain could reuse
1884 the same test. */
1885 decision *outer_end = outer;
1886 do
1887 {
1888 unsigned int length = where->length ();
1889 if (!common_test_p (outer_end->next, trans, where))
1890 {
1891 where->truncate (length);
1892 break;
1893 }
1894 outer_end = outer_end->next;
1895 }
1896 while (outer_end->next);
1897 /* It is worth moving TRANS if it can be shared by more than
1898 one decision. */
1899 if (outer_end != outer || worthwhile_single_p)
1900 return outer_end;
1901 }
1902 where->truncate (0);
1903 }
1904 }
1905 return 0;
1906}
1907
1908/* Try to promote common subtests in S to a single, shared decision.
1909 Also try to bunch tests for the same position together. POS is the
1910 position of the rtx tested before reaching S. KC are the conditions
1911 that are known to hold on entry to S. */
1912
1913static void
1914cse_tests (position *pos, state *s, known_conditions *kc)
1915{
1916 for (decision *d = s->first; d; d = d->next)
1917 {
1918 auto_vec <transition *, 16> where;
1919 if (d->test.pos)
1920 {
1921 /* Try to find conditions that don't depend on a particular rtx,
1922 such as pnum_clobbers != NULL or peep2_current_count >= X.
1923 It's usually better to check these conditions as soon as
1924 possible, so the change is worthwhile even if there is
1925 only one copy of the test. */
1926 decision *endd = find_common_test (d, true, 0, true, kc, &where);
1927 if (!endd && d->test.pos != pos)
1928 /* Try to find other conditions related to position POS
1929 before moving to the new position. Again, this is
1930 worthwhile even if there is only one copy of the test,
1931 since it means that fewer position variables are live
1932 at a given time. */
1933 endd = find_common_test (d, true, pos, true, kc, &where);
1934 if (!endd)
1935 /* Try to find any condition that is used more than once. */
1936 endd = find_common_test (d, false, 0, false, kc, &where);
1937 if (endd)
1938 {
1939 transition *common = where[0];
1940 /* Replace [D, ENDD] with a test like COMMON. We'll recurse
1941 on the common test and see the original D again next time. */
1942 d = insert_decision_before (state::range (d, endd),
1943 common->from->test,
1944 common->labels,
1945 common->optional);
1946 /* Remove the old tests. */
1947 while (!where.is_empty ())
1948 {
1949 transition *trans = where.pop ();
1950 trans->from->s->replace (trans->from, trans->to->release ());
1951 }
1952 }
1953 }
1954
1955 /* Make sure that safe_to_hoist_p isn't being overly conservative.
1956 It should realize that D's test is safe in the current
1957 environment. */
1958 gcc_assert (d->test.kind == rtx_test::C_TEST
1959 || d->test.kind == rtx_test::ACCEPT
1960 || safe_to_hoist_p (d, d->test, kc));
1961
1962 /* D won't be changed any further by the current optimization.
1963 Recurse with the state temporarily updated to include D. */
1964 int prev = 0;
1965 switch (d->test.kind)
1966 {
1967 case rtx_test::CODE:
1968 prev = kc->position_tests[d->test.pos->id];
1969 kc->position_tests[d->test.pos->id] |= TESTED_CODE;
1970 break;
1971
1972 case rtx_test::VECLEN:
1973 case rtx_test::VECLEN_GE:
1974 prev = kc->position_tests[d->test.pos->id];
1975 kc->position_tests[d->test.pos->id] |= TESTED_VECLEN;
1976 break;
1977
1978 case rtx_test::SET_OP:
1979 prev = kc->set_operands[d->test.u.opno];
1980 gcc_assert (!prev);
1981 kc->set_operands[d->test.u.opno] = true;
1982 break;
1983
1984 case rtx_test::PEEP2_COUNT:
1985 prev = kc->peep2_count;
1986 kc->peep2_count = MAX (prev, d->test.u.min_len);
1987 break;
1988
1989 default:
1990 break;
1991 }
1992 for (transition *trans = d->first; trans; trans = trans->next)
1993 cse_tests (d->test.pos ? d->test.pos : pos, trans->to, kc);
1994 switch (d->test.kind)
1995 {
1996 case rtx_test::CODE:
1997 case rtx_test::VECLEN:
1998 case rtx_test::VECLEN_GE:
1999 kc->position_tests[d->test.pos->id] = prev;
2000 break;
2001
2002 case rtx_test::SET_OP:
2003 kc->set_operands[d->test.u.opno] = prev;
2004 break;
2005
2006 case rtx_test::PEEP2_COUNT:
2007 kc->peep2_count = prev;
2008 break;
2009
2010 default:
2011 break;
2012 }
2013 }
2014}
2015
2016/* Return the type of value that can be used to parameterize test KIND,
2017 or parameter::UNSET if none. */
2018
2019parameter::type_enum
2020transition_parameter_type (rtx_test::kind_enum kind)
2021{
2022 switch (kind)
2023 {
2024 case rtx_test::CODE:
2025 return parameter::CODE;
2026
2027 case rtx_test::MODE:
2028 return parameter::MODE;
2029
2030 case rtx_test::REGNO_FIELD:
2031 return parameter::UINT;
2032
2033 case rtx_test::INT_FIELD:
2034 case rtx_test::VECLEN:
2035 case rtx_test::PATTERN:
2036 return parameter::INT;
2037
2038 case rtx_test::WIDE_INT_FIELD:
2039 return parameter::WIDE_INT;
2040
2041 case rtx_test::PEEP2_COUNT:
2042 case rtx_test::VECLEN_GE:
2043 case rtx_test::SAVED_CONST_INT:
2044 case rtx_test::PREDICATE:
2045 case rtx_test::DUPLICATE:
2046 case rtx_test::HAVE_NUM_CLOBBERS:
2047 case rtx_test::C_TEST:
2048 case rtx_test::SET_OP:
2049 case rtx_test::ACCEPT:
2050 return parameter::UNSET;
2051 }
2052 gcc_unreachable ();
2053}
2054
2055/* Initialize the pos_operand fields of each state reachable from S.
2056 If OPERAND_POS[ID] >= 0, the position with id ID is stored in
2057 operands[OPERAND_POS[ID]] on entry to S. */
2058
2059static void
2060find_operand_positions (state *s, vec <int> &operand_pos)
2061{
2062 for (decision *d = s->first; d; d = d->next)
2063 {
2064 int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1);
2065 if (this_operand >= 0)
2066 d->test.pos_operand = this_operand;
2067 if (d->test.kind == rtx_test::SET_OP)
2068 operand_pos[d->test.pos->id] = d->test.u.opno;
2069 for (transition *trans = d->first; trans; trans = trans->next)
2070 find_operand_positions (trans->to, operand_pos);
2071 if (d->test.kind == rtx_test::SET_OP)
2072 operand_pos[d->test.pos->id] = this_operand;
2073 }
2074}
2075
2076/* Statistics about a matching routine. */
2077struct stats
2078{
2079 stats ();
2080
2081 /* The total number of decisions in the routine, excluding trivial
2082 ones that never fail. */
2083 unsigned int num_decisions;
2084
2085 /* The number of non-trivial decisions on the longest path through
2086 the routine, and the return value that contributes most to that
2087 long path. */
2088 unsigned int longest_path;
2089 int longest_path_code;
2090
2091 /* The maximum number of times that a single call to the routine
2092 can backtrack, and the value returned at the end of that path.
2093 "Backtracking" here means failing one decision in state and
2094 going onto to the next. */
2095 unsigned int longest_backtrack;
2096 int longest_backtrack_code;
2097};
2098
2099stats::stats ()
2100 : num_decisions (0), longest_path (0), longest_path_code (-1),
2101 longest_backtrack (0), longest_backtrack_code (-1) {}
2102
2103/* Return statistics about S. */
2104
2105static stats
2106get_stats (state *s)
2107{
2108 stats for_s;
2109 unsigned int longest_path = 0;
2110 for (decision *d = s->first; d; d = d->next)
2111 {
2112 /* Work out the statistics for D. */
2113 stats for_d;
2114 for (transition *trans = d->first; trans; trans = trans->next)
2115 {
2116 stats for_trans = get_stats (trans->to);
2117 for_d.num_decisions += for_trans.num_decisions;
2118 /* Each transition is mutually-exclusive, so just pick the
2119 longest of the individual paths. */
2120 if (for_d.longest_path <= for_trans.longest_path)
2121 {
2122 for_d.longest_path = for_trans.longest_path;
2123 for_d.longest_path_code = for_trans.longest_path_code;
2124 }
2125 /* Likewise for backtracking. */
2126 if (for_d.longest_backtrack <= for_trans.longest_backtrack)
2127 {
2128 for_d.longest_backtrack = for_trans.longest_backtrack;
2129 for_d.longest_backtrack_code = for_trans.longest_backtrack_code;
2130 }
2131 }
2132
2133 /* Account for D's test in its statistics. */
2134 if (!d->test.single_outcome_p ())
2135 {
2136 for_d.num_decisions += 1;
2137 for_d.longest_path += 1;
2138 }
2139 if (d->test.kind == rtx_test::ACCEPT)
2140 {
2141 for_d.longest_path_code = d->test.u.acceptance.u.full.code;
2142 for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code;
2143 }
2144
2145 /* Keep a running count of the number of backtracks. */
2146 if (d->prev)
2147 for_s.longest_backtrack += 1;
2148
2149 /* Accumulate D's statistics into S's. */
2150 for_s.num_decisions += for_d.num_decisions;
2151 for_s.longest_path += for_d.longest_path;
2152 for_s.longest_backtrack += for_d.longest_backtrack;
2153
2154 /* Use the code from the decision with the longest individual path,
2155 since that's more likely to be useful if trying to make the
2156 path shorter. In the event of a tie, pick the later decision,
2157 since that's closer to the end of the path. */
2158 if (longest_path <= for_d.longest_path)
2159 {
2160 longest_path = for_d.longest_path;
2161 for_s.longest_path_code = for_d.longest_path_code;
2162 }
2163
2164 /* Later decisions in a state are necessarily in a longer backtrack
2165 than earlier decisions. */
2166 for_s.longest_backtrack_code = for_d.longest_backtrack_code;
2167 }
2168 return for_s;
2169}
2170
2171/* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
2172
2173static void
2174optimize_subroutine_group (const char *type, state *root)
2175{
2176 /* Remove optional transitions that turned out not to be worthwhile. */
2177 if (collapse_optional_decisions_p)
2178 collapse_optional_decisions (root);
2179
2180 /* Try to remove duplicated tests and to rearrange tests into a more
2181 logical order. */
2182 if (cse_tests_p)
2183 {
2184 known_conditions kc;
2185 kc.position_tests.safe_grow_cleared (num_positions);
2186 kc.set_operands.safe_grow_cleared (num_operands);
2187 kc.peep2_count = 1;
2188 cse_tests (&root_pos, root, &kc);
2189 }
2190
2191 /* Try to simplify two or more tests into one. */
2192 if (simplify_tests_p)
2193 simplify_tests (root);
2194
2195 /* Try to use operands[] instead of xN variables. */
2196 if (use_operand_variables_p)
2197 {
2198 auto_vec <int> operand_pos (num_positions);
2199 for (unsigned int i = 0; i < num_positions; ++i)
2200 operand_pos.quick_push (-1);
2201 find_operand_positions (root, operand_pos);
2202 }
2203
2204 /* Print a summary of the new state. */
2205 stats st = get_stats (root);
2206 fprintf (stderr, "Statistics for %s:\n", type);
2207 fprintf (stderr, " Number of decisions: %6d\n", st.num_decisions);
2208 fprintf (stderr, " longest path: %6d (code: %6d)\n",
2209 st.longest_path, st.longest_path_code);
2210 fprintf (stderr, " longest backtrack: %6d (code: %6d)\n",
2211 st.longest_backtrack, st.longest_backtrack_code);
2212}
2213
2214struct merge_pattern_info;
2215
2216/* Represents a transition from one pattern to another. */
2217struct merge_pattern_transition
2218{
2219 merge_pattern_transition (merge_pattern_info *);
2220
2221 /* The target pattern. */
2222 merge_pattern_info *to;
2223
2224 /* The parameters that the source pattern passes to the target pattern.
2225 "parameter (TYPE, true, I)" represents parameter I of the source
2226 pattern. */
2227 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2228};
2229
2230merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in)
2231 : to (to_in)
2232{
2233}
2234
2235/* Represents a pattern that can might match several states. The pattern
2236 may replace parts of the test with a parameter value. It may also
2237 replace transition labels with parameters. */
2238struct merge_pattern_info
2239{
2240 merge_pattern_info (unsigned int);
2241
2242 /* If PARAM_TEST_P, the state's singleton test should be generalized
2243 to use the runtime value of PARAMS[PARAM_TEST]. */
2244 unsigned int param_test : 8;
2245
2246 /* If PARAM_TRANSITION_P, the state's single transition label should
2247 be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */
2248 unsigned int param_transition : 8;
2249
2250 /* True if we have decided to generalize the root decision's test,
2251 as per PARAM_TEST. */
2252 unsigned int param_test_p : 1;
2253
2254 /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
2255 unsigned int param_transition_p : 1;
2256
2257 /* True if the contents of the structure are completely filled in. */
2258 unsigned int complete_p : 1;
2259
2260 /* The number of pseudo-statements in the pattern. Used to decide
2261 whether it's big enough to break out into a subroutine. */
2262 unsigned int num_statements;
2263
2264 /* The number of states that use this pattern. */
2265 unsigned int num_users;
2266
2267 /* The number of distinct success values that the pattern returns. */
2268 unsigned int num_results;
2269
2270 /* This array has one element for each runtime parameter to the pattern.
2271 PARAMS[I] gives the default value of parameter I, which is always
2272 constant.
2273
2274 These default parameters are used in cases where we match the
2275 pattern against some state S1, then add more parameters while
2276 matching against some state S2. S1 is then left passing fewer
2277 parameters than S2. The array gives us enough informatino to
2278 construct a full parameter list for S1 (see update_parameters).
2279
2280 If we decide to create a subroutine for this pattern,
2281 PARAMS[I].type determines the C type of parameter I. */
2282 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2283
2284 /* All states that match this pattern must have the same number of
2285 transitions. TRANSITIONS[I] describes the subpattern for transition
2286 number I; it is null if transition I represents a successful return
2287 from the pattern. */
2288 auto_vec <merge_pattern_transition *, 1> transitions;
2289
2290 /* The routine associated with the pattern, or null if we haven't generated
2291 one yet. */
2292 pattern_routine *routine;
2293};
2294
2295merge_pattern_info::merge_pattern_info (unsigned int num_transitions)
2296 : param_test (0),
2297 param_transition (0),
2298 param_test_p (false),
2299 param_transition_p (false),
2300 complete_p (false),
2301 num_statements (0),
2302 num_users (0),
2303 num_results (0),
2304 routine (0)
2305{
2306 transitions.safe_grow_cleared (num_transitions);
2307}
2308
2309/* Describes one way of matching a particular state to a particular
2310 pattern. */
2311struct merge_state_result
2312{
2313 merge_state_result (merge_pattern_info *, position *, merge_state_result *);
2314
2315 /* A pattern that matches the state. */
2316 merge_pattern_info *pattern;
2317
2318 /* If we decide to use this match and create a subroutine for PATTERN,
2319 the state should pass the rtx at position ROOT to the pattern's
2320 rtx parameter. A null root means that the pattern doesn't need
2321 an rtx parameter; all the rtxes it matches come from elsewhere. */
2322 position *root;
2323
2324 /* The parameters that should be passed to PATTERN for this state.
2325 If the array is shorter than PATTERN->params, the missing entries
2326 should be taken from the corresponding element of PATTERN->params. */
2327 auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2328
2329 /* An earlier match for the same state, or null if none. Patterns
2330 matched by earlier entries are smaller than PATTERN. */
2331 merge_state_result *prev;
2332};
2333
2334merge_state_result::merge_state_result (merge_pattern_info *pattern_in,
2335 position *root_in,
2336 merge_state_result *prev_in)
2337 : pattern (pattern_in), root (root_in), prev (prev_in)
2338{}
2339
2340/* Information about a state, used while trying to match it against
2341 a pattern. */
2342struct merge_state_info
2343{
2344 merge_state_info (state *);
2345
2346 /* The state itself. */
2347 state *s;
2348
2349 /* Index I gives information about the target of transition I. */
2350 merge_state_info *to_states;
2351
2352 /* The number of transitions in S. */
2353 unsigned int num_transitions;
2354
2355 /* True if the state has been deleted in favor of a call to a
2356 pattern routine. */
2357 bool merged_p;
2358
2359 /* The previous state that might be a merge candidate for S, or null
2360 if no previous states could be merged with S. */
2361 merge_state_info *prev_same_test;
2362
2363 /* A list of pattern matches for this state. */
2364 merge_state_result *res;
2365};
2366
2367merge_state_info::merge_state_info (state *s_in)
2368 : s (s_in),
2369 to_states (0),
2370 num_transitions (0),
2371 merged_p (false),
2372 prev_same_test (0),
2373 res (0) {}
2374
2375/* True if PAT would be useful as a subroutine. */
2376
2377static bool
2378useful_pattern_p (merge_pattern_info *pat)
2379{
2380 return pat->num_statements >= MIN_COMBINE_COST;
2381}
2382
2383/* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
2384 into PAT1's C routine. */
2385
2386static bool
2387same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2)
2388{
2389 return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2);
2390}
2391
2392/* PAT was previously matched against SINFO based on tentative matches
2393 for the target states of SINFO's state. Return true if the match
2394 still holds; that is, if the target states of SINFO's state still
2395 match the corresponding transitions of PAT. */
2396
2397static bool
2398valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2399{
2400 for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2401 if (merge_pattern_transition *ptrans = pat->transitions[j])
2402 {
2403 merge_state_result *to_res = sinfo->to_states[j].res;
2404 if (!to_res || to_res->pattern != ptrans->to)
2405 return false;
2406 }
2407 return true;
2408}
2409
2410/* Remove any matches that are no longer valid from the head of SINFO's
2411 list of matches. */
2412
2413static void
2414prune_invalid_results (merge_state_info *sinfo)
2415{
2416 while (sinfo->res && !valid_result_p (sinfo->res->pattern, sinfo))
2417 {
2418 sinfo->res = sinfo->res->prev;
2419 gcc_assert (sinfo->res);
2420 }
2421}
2422
2423/* Return true if PAT represents the biggest posssible match for SINFO;
2424 that is, if the next action of SINFO's state on return from PAT will
2425 be something that cannot be merged with any other state. */
2426
2427static bool
2428complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2429{
2430 for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2431 if (sinfo->to_states[j].res && !pat->transitions[j])
2432 return false;
2433 return true;
2434}
2435
2436/* Update TO for any parameters that have been added to FROM since TO
2437 was last set. The extra parameters in FROM will be constants or
2438 instructions to duplicate earlier parameters. */
2439
2440static void
2441update_parameters (vec <parameter> &to, const vec <parameter> &from)
2442{
2443 for (unsigned int i = to.length (); i < from.length (); ++i)
2444 to.quick_push (from[i]);
2445}
2446
2447/* Return true if A and B can be tested by a single test. If the test
2448 can be parameterised, store the parameter value for A in *PARAMA and
2449 the parameter value for B in *PARAMB, otherwise leave PARAMA and
2450 PARAMB alone. */
2451
2452static bool
2453compatible_tests_p (const rtx_test &a, const rtx_test &b,
2454 parameter *parama, parameter *paramb)
2455{
2456 if (a.kind != b.kind)
2457 return false;
2458 switch (a.kind)
2459 {
2460 case rtx_test::PREDICATE:
2461 if (a.u.predicate.data != b.u.predicate.data)
2462 return false;
2463 *parama = parameter (parameter::MODE, false, a.u.predicate.mode);
2464 *paramb = parameter (parameter::MODE, false, b.u.predicate.mode);
2465 return true;
2466
2467 case rtx_test::SAVED_CONST_INT:
2468 *parama = parameter (parameter::INT, false, a.u.integer.value);
2469 *paramb = parameter (parameter::INT, false, b.u.integer.value);
2470 return true;
2471
2472 default:
2473 return a == b;
2474 }
2475}
2476
2477/* PARAMS is an array of the parameters that a state is going to pass
2478 to a pattern routine. It is still incomplete; index I has a kind of
2479 parameter::UNSET if we don't yet know what the state will pass
2480 as parameter I. Try to make parameter ID equal VALUE, returning
2481 true on success. */
2482
2483static bool
2484set_parameter (vec <parameter> &params, unsigned int id,
2485 const parameter &value)
2486{
2487 if (params[id].type == parameter::UNSET)
2488 {
2489 if (force_unique_params_p)
2490 for (unsigned int i = 0; i < params.length (); ++i)
2491 if (params[i] == value)
2492 return false;
2493 params[id] = value;
2494 return true;
2495 }
2496 return params[id] == value;
2497}
2498
2499/* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
2500 set of parameters that a particular state is going to pass to
2501 that pattern.
2502
2503 Try to extend PARAMS1 and PARAMS2 so that there is a parameter
2504 that is equal to PARAM1 for the state and has a default value of
2505 PARAM2. Parameters beginning at START were added as part of the
2506 same match and so may be reused. */
2507
2508static bool
2509add_parameter (vec <parameter> &params1, vec <parameter> &params2,
2510 const parameter &param1, const parameter &param2,
2511 unsigned int start, unsigned int *res)
2512{
2513 gcc_assert (params1.length () == params2.length ());
2514 gcc_assert (!param1.is_param && !param2.is_param);
2515
2516 for (unsigned int i = start; i < params2.length (); ++i)
2517 if (params1[i] == param1 && params2[i] == param2)
2518 {
2519 *res = i;
2520 return true;
2521 }
2522
2523 if (force_unique_params_p)
2524 for (unsigned int i = 0; i < params2.length (); ++i)
2525 if (params1[i] == param1 || params2[i] == param2)
2526 return false;
2527
2528 if (params2.length () >= MAX_PATTERN_PARAMS)
2529 return false;
2530
2531 *res = params2.length ();
2532 params1.quick_push (param1);
2533 params2.quick_push (param2);
2534 return true;
2535}
2536
2537/* If *ROOTA is nonnull, return true if the same sequence of steps are
2538 required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA
2539 is null, update it if necessary in order to make the condition hold. */
2540
2541static bool
2542merge_relative_positions (position **roota, position *a,
2543 position *rootb, position *b)
2544{
2545 if (!relative_patterns_p)
2546 {
2547 if (a != b)
2548 return false;
2549 if (!*roota)
2550 {
2551 *roota = rootb;
2552 return true;
2553 }
2554 return *roota == rootb;
2555 }
2556 /* If B does not belong to the same instruction as ROOTB, we don't
2557 start with ROOTB but instead start with a call to peep2_next_insn.
2558 In that case the sequences for B and A are identical iff B and A
2559 are themselves identical. */
2560 if (rootb->insn_id != b->insn_id)
2561 return a == b;
2562 while (rootb != b)
2563 {
2564 if (!a || b->type != a->type || b->arg != a->arg)
2565 return false;
2566 b = b->base;
2567 a = a->base;
2568 }
2569 if (!*roota)
2570 *roota = a;
2571 return *roota == a;
2572}
2573
2574/* A hasher of states that treats two states as "equal" if they might be
2575 merged (but trying to be more discriminating than "return true"). */
2576struct test_pattern_hasher : nofree_ptr_hash <merge_state_info>
2577{
2578 static inline hashval_t hash (const value_type &);
2579 static inline bool equal (const value_type &, const compare_type &);
2580};
2581
2582hashval_t
2583test_pattern_hasher::hash (merge_state_info *const &sinfo)
2584{
2585 inchash::hash h;
2586 decision *d = sinfo->s->singleton ();
2587 h.add_int (d->test.pos_operand + 1);
2588 if (!relative_patterns_p)
2589 h.add_int (d->test.pos ? d->test.pos->id + 1 : 0);
2590 h.add_int (d->test.kind);
2591 h.add_int (sinfo->num_transitions);
2592 return h.end ();
2593}
2594
2595bool
2596test_pattern_hasher::equal (merge_state_info *const &sinfo1,
2597 merge_state_info *const &sinfo2)
2598{
2599 decision *d1 = sinfo1->s->singleton ();
2600 decision *d2 = sinfo2->s->singleton ();
2601 gcc_assert (d1 && d2);
2602
2603 parameter new_param1, new_param2;
2604 return (d1->test.pos_operand == d2->test.pos_operand
2605 && (relative_patterns_p || d1->test.pos == d2->test.pos)
2606 && compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2)
2607 && sinfo1->num_transitions == sinfo2->num_transitions);
2608}
2609
2610/* Try to make the state described by SINFO1 use the same pattern as the
2611 state described by SINFO2. Return true on success.
2612
2613 SINFO1 and SINFO2 are known to have the same hash value. */
2614
2615static bool
2616merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2)
2617{
2618 merge_state_result *res2 = sinfo2->res;
2619 merge_pattern_info *pat = res2->pattern;
2620
2621 /* Write to temporary arrays while matching, in case we have to abort
2622 half way through. */
2623 auto_vec <parameter, MAX_PATTERN_PARAMS> params1;
2624 auto_vec <parameter, MAX_PATTERN_PARAMS> params2;
2625 params1.quick_grow_cleared (pat->params.length ());
2626 params2.splice (pat->params);
2627 unsigned int start_param = params2.length ();
2628
2629 /* An array for recording changes to PAT->transitions[?].params.
2630 All changes involve replacing a constant parameter with some
2631 PAT->params[N], where N is the second element of the pending_param. */
2632 typedef std::pair <parameter *, unsigned int> pending_param;
2633 auto_vec <pending_param, 32> pending_params;
2634
2635 decision *d1 = sinfo1->s->singleton ();
2636 decision *d2 = sinfo2->s->singleton ();
2637 gcc_assert (d1 && d2);
2638
2639 /* If D2 tests a position, SINFO1's root relative to D1 is the same
2640 as SINFO2's root relative to D2. */
2641 position *root1 = 0;
2642 position *root2 = res2->root;
2643 if (d2->test.pos_operand < 0
2644 && d1->test.pos
2645 && !merge_relative_positions (&root1, d1->test.pos,
2646 root2, d2->test.pos))
2647 return false;
2648
2649 /* Check whether the patterns have the same shape. */
2650 unsigned int num_transitions = sinfo1->num_transitions;
2651 gcc_assert (num_transitions == sinfo2->num_transitions);
2652 for (unsigned int i = 0; i < num_transitions; ++i)
2653 if (merge_pattern_transition *ptrans = pat->transitions[i])
2654 {
2655 merge_state_result *to1_res = sinfo1->to_states[i].res;
2656 merge_state_result *to2_res = sinfo2->to_states[i].res;
2657 merge_pattern_info *to_pat = ptrans->to;
2658 gcc_assert (to2_res && to2_res->pattern == to_pat);
2659 if (!to1_res || to1_res->pattern != to_pat)
2660 return false;
2661 if (to2_res->root
2662 && !merge_relative_positions (&root1, to1_res->root,
2663 root2, to2_res->root))
2664 return false;
2665 /* Match the parameters that TO1_RES passes to TO_PAT with the
2666 parameters that PAT passes to TO_PAT. */
2667 update_parameters (to1_res->params, to_pat->params);
2668 for (unsigned int j = 0; j < to1_res->params.length (); ++j)
2669 {
2670 const parameter &param1 = to1_res->params[j];
2671 const parameter &param2 = ptrans->params[j];
2672 gcc_assert (!param1.is_param);
2673 if (param2.is_param)
2674 {
2675 if (!set_parameter (params1, param2.value, param1))
2676 return false;
2677 }
2678 else if (param1 != param2)
2679 {
2680 unsigned int id;
2681 if (!add_parameter (params1, params2,
2682 param1, param2, start_param, &id))
2683 return false;
2684 /* Record that PAT should now pass parameter ID to TO_PAT,
2685 instead of the current contents of *PARAM2. We only
2686 make the change if the rest of the match succeeds. */
2687 pending_params.safe_push
2688 (pending_param (&ptrans->params[j], id));
2689 }
2690 }
2691 }
2692
2693 unsigned int param_test = pat->param_test;
2694 unsigned int param_transition = pat->param_transition;
2695 bool param_test_p = pat->param_test_p;
2696 bool param_transition_p = pat->param_transition_p;
2697
2698 /* If the tests don't match exactly, try to parameterize them. */
2699 parameter new_param1, new_param2;
2700 if (!compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2))
2701 gcc_unreachable ();
2702 if (new_param1.type != parameter::UNSET)
2703 {
2704 /* If the test has not already been parameterized, all existing
2705 matches use constant NEW_PARAM2. */
2706 if (param_test_p)
2707 {
2708 if (!set_parameter (params1, param_test, new_param1))
2709 return false;
2710 }
2711 else if (new_param1 != new_param2)
2712 {
2713 if (!add_parameter (params1, params2, new_param1, new_param2,
2714 start_param, &param_test))
2715 return false;
2716 param_test_p = true;
2717 }
2718 }
2719
2720 /* Match the transitions. */
2721 transition *trans1 = d1->first;
2722 transition *trans2 = d2->first;
2723 for (unsigned int i = 0; i < num_transitions; ++i)
2724 {
2725 if (param_transition_p || trans1->labels != trans2->labels)
2726 {
2727 /* We can only generalize a single transition with a single
2728 label. */
2729 if (num_transitions != 1
2730 || trans1->labels.length () != 1
2731 || trans2->labels.length () != 1)
2732 return false;
2733
2734 /* Although we can match wide-int fields, in practice it leads
2735 to some odd results for const_vectors. We end up
2736 parameterizing the first N const_ints of the vector
2737 and then (once we reach the maximum number of parameters)
2738 we go on to match the other elements exactly. */
2739 if (d1->test.kind == rtx_test::WIDE_INT_FIELD)
2740 return false;
2741
2742 /* See whether the label has a generalizable type. */
2743 parameter::type_enum param_type
2744 = transition_parameter_type (d1->test.kind);
2745 if (param_type == parameter::UNSET)
2746 return false;
2747
2748 /* Match the labels using parameters. */
2749 new_param1 = parameter (param_type, false, trans1->labels[0]);
2750 if (param_transition_p)
2751 {
2752 if (!set_parameter (params1, param_transition, new_param1))
2753 return false;
2754 }
2755 else
2756 {
2757 new_param2 = parameter (param_type, false, trans2->labels[0]);
2758 if (!add_parameter (params1, params2, new_param1, new_param2,
2759 start_param, &param_transition))
2760 return false;
2761 param_transition_p = true;
2762 }
2763 }
2764 trans1 = trans1->next;
2765 trans2 = trans2->next;
2766 }
2767
2768 /* Set any unset parameters to their default values. This occurs if some
2769 other state needed something to be parameterized in order to match SINFO2,
2770 but SINFO1 on its own does not. */
2771 for (unsigned int i = 0; i < params1.length (); ++i)
2772 if (params1[i].type == parameter::UNSET)
2773 params1[i] = params2[i];
2774
2775 /* The match was successful. Commit all pending changes to PAT. */
2776 update_parameters (pat->params, params2);
2777 {
2778 pending_param *pp;
2779 unsigned int i;
2780 FOR_EACH_VEC_ELT (pending_params, i, pp)
2781 *pp->first = parameter (pp->first->type, true, pp->second);
2782 }
2783 pat->param_test = param_test;
2784 pat->param_transition = param_transition;
2785 pat->param_test_p = param_test_p;
2786 pat->param_transition_p = param_transition_p;
2787
2788 /* Record the match of SINFO1. */
2789 merge_state_result *new_res1 = new merge_state_result (pat, root1,
2790 sinfo1->res);
2791 new_res1->params.splice (params1);
2792 sinfo1->res = new_res1;
2793 return true;
2794}
2795
2796/* The number of states that were removed by calling pattern routines. */
2797static unsigned int pattern_use_states;
2798
2799/* The number of states used while defining pattern routines. */
2800static unsigned int pattern_def_states;
2801
2802/* Information used while constructing a use or definition of a pattern
2803 routine. */
2804struct create_pattern_info
2805{
2806 /* The routine itself. */
2807 pattern_routine *routine;
2808
2809 /* The first unclaimed return value for this particular use or definition.
2810 We walk the substates of uses and definitions in the same order
2811 so each return value always refers to the same position within
2812 the pattern. */
2813 unsigned int next_result;
2814};
2815
2816static void populate_pattern_routine (create_pattern_info *,
2817 merge_state_info *, state *,
2818 const vec <parameter> &);
2819
2820/* SINFO matches a pattern for which we've decided to create a C routine.
2821 Return a decision that performs a call to the pattern routine,
2822 but leave the caller to add the transitions to it. Initialize CPI
2823 for this purpose. Also create a definition for the pattern routine,
2824 if it doesn't already have one.
2825
2826 PARAMS are the parameters that SINFO passes to its pattern. */
2827
2828static decision *
2829init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo,
2830 const vec <parameter> &params)
2831{
2832 state *s = sinfo->s;
2833 merge_state_result *res = sinfo->res;
2834 merge_pattern_info *pat = res->pattern;
2835 cpi->routine = pat->routine;
2836 if (!cpi->routine)
2837 {
2838 /* We haven't defined the pattern routine yet, so create
2839 a definition now. */
2840 pattern_routine *routine = new pattern_routine;
2841 pat->routine = routine;
2842 cpi->routine = routine;
2843 routine->s = new state;
2844 routine->insn_p = false;
2845 routine->pnum_clobbers_p = false;
2846
2847 /* Create an "idempotent" mapping of parameter I to parameter I.
2848 Also record the C type of each parameter to the routine. */
2849 auto_vec <parameter, MAX_PATTERN_PARAMS> def_params;
2850 for (unsigned int i = 0; i < pat->params.length (); ++i)
2851 {
2852 def_params.quick_push (parameter (pat->params[i].type, true, i));
2853 routine->param_types.quick_push (pat->params[i].type);
2854 }
2855
2856 /* Any of the states that match the pattern could be used to
2857 create the routine definition. We might as well use SINFO
2858 since it's already to hand. This means that all positions
2859 in the definition will be relative to RES->root. */
2860 routine->pos = res->root;
2861 cpi->next_result = 0;
2862 populate_pattern_routine (cpi, sinfo, routine->s, def_params);
2863 gcc_assert (cpi->next_result == pat->num_results);
2864
2865 /* Add the routine to the global list, after the subroutines
2866 that it calls. */
2867 routine->pattern_id = patterns.length ();
2868 patterns.safe_push (routine);
2869 }
2870
2871 /* Create a decision to call the routine, passing PARAMS to it. */
2872 pattern_use *use = new pattern_use;
2873 use->routine = pat->routine;
2874 use->params.splice (params);
2875 decision *d = new decision (rtx_test::pattern (res->root, use));
2876
2877 /* If the original decision could use an element of operands[] instead
2878 of an rtx variable, try to transfer it to the new decision. */
2879 if (s->first->test.pos && res->root == s->first->test.pos)
2880 d->test.pos_operand = s->first->test.pos_operand;
2881
2882 cpi->next_result = 0;
2883 return d;
2884}
2885
2886/* Make S return the next unclaimed pattern routine result for CPI. */
2887
2888static void
2889add_pattern_acceptance (create_pattern_info *cpi, state *s)
2890{
2891 acceptance_type acceptance;
2892 acceptance.type = SUBPATTERN;
2893 acceptance.partial_p = false;
2894 acceptance.u.full.code = cpi->next_result;
2895 add_decision (s, rtx_test::accept (acceptance), true, false);
2896 cpi->next_result += 1;
2897}
2898
2899/* Initialize new empty state NEWS so that it implements SINFO's pattern
2900 (here referred to as "P"). P may be the top level of a pattern routine
2901 or a subpattern that should be inlined into its parent pattern's routine
2902 (as per same_pattern_p). The choice of SINFO for a top-level pattern is
2903 arbitrary; it could be any of the states that use P. The choice for
2904 subpatterns follows the choice for the parent pattern.
2905
2906 PARAMS gives the value of each parameter to P in terms of the parameters
2907 to the top-level pattern. If P itself is the top level pattern, PARAMS[I]
2908 is always "parameter (TYPE, true, I)". */
2909
2910static void
2911populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo,
2912 state *news, const vec <parameter> &params)
2913{
2914 pattern_def_states += 1;
2915
2916 decision *d = sinfo->s->singleton ();
2917 merge_pattern_info *pat = sinfo->res->pattern;
2918 pattern_routine *routine = cpi->routine;
2919
2920 /* Create a copy of D's test for the pattern routine and generalize it
2921 as appropriate. */
2922 decision *newd = new decision (d->test);
2923 gcc_assert (newd->test.pos_operand >= 0
2924 || !newd->test.pos
2925 || common_position (newd->test.pos,
2926 routine->pos) == routine->pos);
2927 if (pat->param_test_p)
2928 {
2929 const parameter &param = params[pat->param_test];
2930 switch (newd->test.kind)
2931 {
2932 case rtx_test::PREDICATE:
2933 newd->test.u.predicate.mode_is_param = param.is_param;
2934 newd->test.u.predicate.mode = param.value;
2935 break;
2936
2937 case rtx_test::SAVED_CONST_INT:
2938 newd->test.u.integer.is_param = param.is_param;
2939 newd->test.u.integer.value = param.value;
2940 break;
2941
2942 default:
2943 gcc_unreachable ();
2944 break;
2945 }
2946 }
2947 if (d->test.kind == rtx_test::C_TEST)
2948 routine->insn_p = true;
2949 else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS)
2950 routine->pnum_clobbers_p = true;
2951 news->push_back (newd);
2952
2953 /* Fill in the transitions of NEWD. */
2954 unsigned int i = 0;
2955 for (transition *trans = d->first; trans; trans = trans->next)
2956 {
2957 /* Create a new state to act as the target of the new transition. */
2958 state *to_news = new state;
2959 if (merge_pattern_transition *ptrans = pat->transitions[i])
2960 {
2961 /* The pattern hasn't finished matching yet. Get the target
2962 pattern and the corresponding target state of SINFO. */
2963 merge_pattern_info *to_pat = ptrans->to;
2964 merge_state_info *to = sinfo->to_states + i;
2965 gcc_assert (to->res->pattern == to_pat);
2966 gcc_assert (ptrans->params.length () == to_pat->params.length ());
2967
2968 /* Express the parameters to TO_PAT in terms of the parameters
2969 to the top-level pattern. */
2970 auto_vec <parameter, MAX_PATTERN_PARAMS> to_params;
2971 for (unsigned int j = 0; j < ptrans->params.length (); ++j)
2972 {
2973 const parameter &param = ptrans->params[j];
2974 to_params.quick_push (param.is_param
2975 ? params[param.value]
2976 : param);
2977 }
2978
2979 if (same_pattern_p (pat, to_pat))
2980 /* TO_PAT is part of the current routine, so just recurse. */
2981 populate_pattern_routine (cpi, to, to_news, to_params);
2982 else
2983 {
2984 /* TO_PAT should be matched by calling a separate routine. */
2985 create_pattern_info sub_cpi;
2986 decision *subd = init_pattern_use (&sub_cpi, to, to_params);
2987 routine->insn_p |= sub_cpi.routine->insn_p;
2988 routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p;
2989
2990 /* Add the pattern routine call to the new target state. */
2991 to_news->push_back (subd);
2992
2993 /* Add a transition for each successful call result. */
2994 for (unsigned int j = 0; j < to_pat->num_results; ++j)
2995 {
2996 state *res = new state;
2997 add_pattern_acceptance (cpi, res);
2998 subd->push_back (new transition (j, res, false));
2999 }
3000 }
3001 }
3002 else
3003 /* This transition corresponds to a successful match. */
3004 add_pattern_acceptance (cpi, to_news);
3005
3006 /* Create the transition itself, generalizing as necessary. */
3007 transition *new_trans = new transition (trans->labels, to_news,
3008 trans->optional);
3009 if (pat->param_transition_p)
3010 {
3011 const parameter &param = params[pat->param_transition];
3012 new_trans->is_param = param.is_param;
3013 new_trans->labels[0] = param.value;
3014 }
3015 newd->push_back (new_trans);
3016 i += 1;
3017 }
3018}
3019
3020/* USE is a decision that calls a pattern routine and SINFO is part of the
3021 original state tree that the call is supposed to replace. Add the
3022 transitions for SINFO and its substates to USE. */
3023
3024static void
3025populate_pattern_use (create_pattern_info *cpi, decision *use,
3026 merge_state_info *sinfo)
3027{
3028 pattern_use_states += 1;
3029 gcc_assert (!sinfo->merged_p);
3030 sinfo->merged_p = true;
3031 merge_state_result *res = sinfo->res;
3032 merge_pattern_info *pat = res->pattern;
3033 decision *d = sinfo->s->singleton ();
3034 unsigned int i = 0;
3035 for (transition *trans = d->first; trans; trans = trans->next)
3036 {
3037 if (pat->transitions[i])
3038 /* The target state is also part of the pattern. */
3039 populate_pattern_use (cpi, use, sinfo->to_states + i);
3040 else
3041 {
3042 /* The transition corresponds to a successful return from the
3043 pattern routine. */
3044 use->push_back (new transition (cpi->next_result, trans->to, false));
3045 cpi->next_result += 1;
3046 }
3047 i += 1;
3048 }
3049}
3050
3051/* We have decided to replace SINFO's state with a call to a pattern
3052 routine. Make the change, creating a definition of the pattern routine
3053 if it doesn't have one already. */
3054
3055static void
3056use_pattern (merge_state_info *sinfo)
3057{
3058 merge_state_result *res = sinfo->res;
3059 merge_pattern_info *pat = res->pattern;
3060 state *s = sinfo->s;
3061
3062 /* The pattern may have acquired new parameters after it was matched
3063 against SINFO. Update the parameters that SINFO passes accordingly. */
3064 update_parameters (res->params, pat->params);
3065
3066 create_pattern_info cpi;
3067 decision *d = init_pattern_use (&cpi, sinfo, res->params);
3068 populate_pattern_use (&cpi, d, sinfo);
3069 s->release ();
3070 s->push_back (d);
3071}
3072
3073/* Look through the state trees in STATES for common patterns and
3074 split them into subroutines. */
3075
3076static void
3077split_out_patterns (vec <merge_state_info> &states)
3078{
3079 unsigned int first_transition = states.length ();
3080 hash_table <test_pattern_hasher> hashtab (128);
3081 /* Stage 1: Create an order in which parent states come before their child
3082 states and in which sibling states are at consecutive locations.
3083 Having consecutive sibling states allows merge_state_info to have
3084 a single to_states pointer. */
3085 for (unsigned int i = 0; i < states.length (); ++i)
3086 for (decision *d = states[i].s->first; d; d = d->next)
3087 for (transition *trans = d->first; trans; trans = trans->next)
3088 {
3089 states.safe_push (trans->to);
3090 states[i].num_transitions += 1;
3091 }
3092 /* Stage 2: Now that the addresses are stable, set up the to_states
3093 pointers. Look for states that might be merged and enter them
3094 into the hash table. */
3095 for (unsigned int i = 0; i < states.length (); ++i)
3096 {
3097 merge_state_info *sinfo = &states[i];
3098 if (sinfo->num_transitions)
3099 {
3100 sinfo->to_states = &states[first_transition];
3101 first_transition += sinfo->num_transitions;
3102 }
3103 /* For simplicity, we only try to merge states that have a single
3104 decision. This is in any case the best we can do for peephole2,
3105 since whether a peephole2 ACCEPT succeeds or not depends on the
3106 specific peephole2 pattern (which is unique to each ACCEPT
3107 and so couldn't be shared between states). */
3108 if (decision *d = sinfo->s->singleton ())
3109 /* ACCEPT states are unique, so don't even try to merge them. */
3110 if (d->test.kind != rtx_test::ACCEPT
3111 && (pattern_have_num_clobbers_p
3112 || d->test.kind != rtx_test::HAVE_NUM_CLOBBERS)
3113 && (pattern_c_test_p
3114 || d->test.kind != rtx_test::C_TEST))
3115 {
3116 merge_state_info **slot = hashtab.find_slot (sinfo, INSERT);
3117 sinfo->prev_same_test = *slot;
3118 *slot = sinfo;
3119 }
3120 }
3121 /* Stage 3: Walk backwards through the list of states and try to merge
3122 them. This is a greedy, bottom-up match; parent nodes can only start
3123 a new leaf pattern if they fail to match when combined with all child
3124 nodes that have matching patterns.
3125
3126 For each state we keep a list of potential matches, with each
3127 potential match being larger (and deeper) than the next match in
3128 the list. The final element in the list is a leaf pattern that
3129 matches just a single state.
3130
3131 Each candidate pattern created in this loop is unique -- it won't
3132 have been seen by an earlier iteration. We try to match each pattern
3133 with every state that appears earlier in STATES.
3134
3135 Because the patterns created in the loop are unique, any state
3136 that already has a match must have a final potential match that
3137 is different from any new leaf pattern. Therefore, when matching
3138 leaf patterns, we need only consider states whose list of matches
3139 is empty.
3140
3141 The non-leaf patterns that we try are as deep as possible
3142 and are an extension of the state's previous best candidate match (PB).
3143 We need only consider states whose current potential match is also PB;
3144 any states that don't match as much as PB cannnot match the new pattern,
3145 while any states that already match more than PB must be different from
3146 the new pattern. */
3147 for (unsigned int i2 = states.length (); i2-- > 0; )
3148 {
3149 merge_state_info *sinfo2 = &states[i2];
3150
3151 /* Enforce the bottom-upness of the match: remove matches with later
3152 states if SINFO2's child states ended up finding a better match. */
3153 prune_invalid_results (sinfo2);
3154
3155 /* Do nothing if the state doesn't match a later one and if there are
3156 no earlier states it could match. */
3157 if (!sinfo2->res && !sinfo2->prev_same_test)
3158 continue;
3159
3160 merge_state_result *res2 = sinfo2->res;
3161 decision *d2 = sinfo2->s->singleton ();
3162 position *root2 = (d2->test.pos_operand < 0 ? d2->test.pos : 0);
3163 unsigned int num_transitions = sinfo2->num_transitions;
3164
3165 /* If RES2 is null then SINFO2's test in isolation has not been seen
3166 before. First try matching that on its own. */
3167 if (!res2)
3168 {
3169 merge_pattern_info *new_pat
3170 = new merge_pattern_info (num_transitions);
3171 merge_state_result *new_res2
3172 = new merge_state_result (new_pat, root2, res2);
3173 sinfo2->res = new_res2;
3174
3175 new_pat->num_statements = !d2->test.single_outcome_p ();
3176 new_pat->num_results = num_transitions;
3177 bool matched_p = false;
3178 /* Look for states that don't currently match anything but
3179 can be made to match SINFO2 on its own. */
3180 for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3181 sinfo1 = sinfo1->prev_same_test)
3182 if (!sinfo1->res && merge_patterns (sinfo1, sinfo2))
3183 matched_p = true;
3184 if (!matched_p)
3185 {
3186 /* No other states match. */
3187 sinfo2->res = res2;
3188 delete new_pat;
3189 delete new_res2;
3190 continue;
3191 }
3192 else
3193 res2 = new_res2;
3194 }
3195
3196 /* Keep the existing pattern if it's as good as anything we'd
3197 create for SINFO2. */
3198 if (complete_result_p (res2->pattern, sinfo2))
3199 {
3200 res2->pattern->num_users += 1;
3201 continue;
3202 }
3203
3204 /* Create a new pattern for SINFO2. */
3205 merge_pattern_info *new_pat = new merge_pattern_info (num_transitions);
3206 merge_state_result *new_res2
3207 = new merge_state_result (new_pat, root2, res2);
3208 sinfo2->res = new_res2;
3209
3210 /* Fill in details about the pattern. */
3211 new_pat->num_statements = !d2->test.single_outcome_p ();
3212 new_pat->num_results = 0;
3213 for (unsigned int j = 0; j < num_transitions; ++j)
3214 if (merge_state_result *to_res = sinfo2->to_states[j].res)
3215 {
3216 /* Count the target state as part of this pattern.
3217 First update the root position so that it can reach
3218 the target state's root. */
3219 if (to_res->root)
3220 {
3221 if (new_res2->root)
3222 new_res2->root = common_position (new_res2->root,
3223 to_res->root);
3224 else
3225 new_res2->root = to_res->root;
3226 }
3227 merge_pattern_info *to_pat = to_res->pattern;
3228 merge_pattern_transition *ptrans
3229 = new merge_pattern_transition (to_pat);
3230
3231 /* TO_PAT may have acquired more parameters when matching
3232 states earlier in STATES than TO_RES's, but the list is
3233 now final. Make sure that TO_RES is up to date. */
3234 update_parameters (to_res->params, to_pat->params);
3235
3236 /* Start out by assuming that every user of NEW_PAT will
3237 want to pass the same (constant) parameters as TO_RES. */
3238 update_parameters (ptrans->params, to_res->params);
3239
3240 new_pat->transitions[j] = ptrans;
3241 new_pat->num_statements += to_pat->num_statements;
3242 new_pat->num_results += to_pat->num_results;
3243 }
3244 else
3245 /* The target state doesn't match anything and so is not part
3246 of the pattern. */
3247 new_pat->num_results += 1;
3248
3249 /* See if any earlier states that match RES2's pattern also match
3250 NEW_PAT. */
3251 bool matched_p = false;
3252 for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3253 sinfo1 = sinfo1->prev_same_test)
3254 {
3255 prune_invalid_results (sinfo1);
3256 if (sinfo1->res
3257 && sinfo1->res->pattern == res2->pattern
3258 && merge_patterns (sinfo1, sinfo2))
3259 matched_p = true;
3260 }
3261 if (!matched_p)
3262 {
3263 /* Nothing else matches NEW_PAT, so go back to the previous
3264 pattern (possibly just a single-state one). */
3265 sinfo2->res = res2;
3266 delete new_pat;
3267 delete new_res2;
3268 }
3269 /* Assume that SINFO2 will use RES. At this point we don't know
3270 whether earlier states that match the same pattern will use
3271 that match or a different one. */
3272 sinfo2->res->pattern->num_users += 1;
3273 }
3274 /* Step 4: Finalize the choice of pattern for each state, ignoring
3275 patterns that were only used once. Update each pattern's size
3276 so that it doesn't include subpatterns that are going to be split
3277 out into subroutines. */
3278 for (unsigned int i = 0; i < states.length (); ++i)
3279 {
3280 merge_state_info *sinfo = &states[i];
3281 merge_state_result *res = sinfo->res;
3282 /* Wind past patterns that are only used by SINFO. */
3283 while (res && res->pattern->num_users == 1)
3284 {
3285 res = res->prev;
3286 sinfo->res = res;
3287 if (res)
3288 res->pattern->num_users += 1;
3289 }
3290 if (!res)
3291 continue;
3292
3293 /* We have a shared pattern and are now committed to the match. */
3294 merge_pattern_info *pat = res->pattern;
3295 gcc_assert (valid_result_p (pat, sinfo));
3296
3297 if (!pat->complete_p)
3298 {
3299 /* Look for subpatterns that are going to be split out and remove
3300 them from the number of statements. */
3301 for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
3302 if (merge_pattern_transition *ptrans = pat->transitions[j])
3303 {
3304 merge_pattern_info *to_pat = ptrans->to;
3305 if (!same_pattern_p (pat, to_pat))
3306 pat->num_statements -= to_pat->num_statements;
3307 }
3308 pat->complete_p = true;
3309 }
3310 }
3311 /* Step 5: Split out the patterns. */
3312 for (unsigned int i = 0; i < states.length (); ++i)
3313 {
3314 merge_state_info *sinfo = &states[i];
3315 merge_state_result *res = sinfo->res;
3316 if (!sinfo->merged_p && res && useful_pattern_p (res->pattern))
3317 use_pattern (sinfo);
3318 }
3319 fprintf (stderr, "Shared %d out of %d states by creating %d new states,"
3320 " saving %d\n",
3321 pattern_use_states, states.length (), pattern_def_states,
3322 pattern_use_states - pattern_def_states);
3323}
3324
3325/* Information about a state tree that we're considering splitting into a
3326 subroutine. */
3327struct state_size
3328{
3329 /* The number of pseudo-statements in the state tree. */
3330 unsigned int num_statements;
3331
3332 /* The approximate number of nested "if" and "switch" statements that
3333 would be required if control could fall through to a later state. */
3334 unsigned int depth;
3335};
3336
3337/* Pairs a transition with information about its target state. */
3338typedef std::pair <transition *, state_size> subroutine_candidate;
3339
3340/* Sort two subroutine_candidates so that the one with the largest
3341 number of statements comes last. */
3342
3343static int
3344subroutine_candidate_cmp (const void *a, const void *b)
3345{
3346 return int (((const subroutine_candidate *) a)->second.num_statements
3347 - ((const subroutine_candidate *) b)->second.num_statements);
3348}
3349
3350/* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new
3351 state that performs a subroutine call to S. */
3352
3353static state *
3354create_subroutine (routine_type type, state *s, vec <state *> &procs)
3355{
3356 procs.safe_push (s);
3357 acceptance_type acceptance;
3358 acceptance.type = type;
3359 acceptance.partial_p = true;
3360 acceptance.u.subroutine_id = procs.length ();
3361 state *news = new state;
3362 add_decision (news, rtx_test::accept (acceptance), true, false);
3363 return news;
3364}
3365
3366/* Walk state tree S, of type TYPE, and look for subtrees that would be
3367 better split into subroutines. Accumulate all such subroutines in PROCS.
3368 Return the size of the new state tree (excluding subroutines). */
3369
3370static state_size
3371find_subroutines (routine_type type, state *s, vec <state *> &procs)
3372{
3373 auto_vec <subroutine_candidate, 16> candidates;
3374 state_size size;
3375 size.num_statements = 0;
3376 size.depth = 0;
3377 for (decision *d = s->first; d; d = d->next)
3378 {
3379 if (!d->test.single_outcome_p ())
3380 size.num_statements += 1;
3381 for (transition *trans = d->first; trans; trans = trans->next)
3382 {
3383 /* Keep chains of simple decisions together if we know that no
3384 change of position is required. We'll output this chain as a
3385 single "if" statement, so it counts as a single nesting level. */
3386 if (d->test.pos && d->if_statement_p ())
3387 for (;;)
3388 {
3389 decision *newd = trans->to->singleton ();
3390 if (!newd
3391 || (newd->test.pos
3392 && newd->test.pos_operand < 0
3393 && newd->test.pos != d->test.pos)
3394 || !newd->if_statement_p ())
3395 break;
3396 if (!newd->test.single_outcome_p ())
3397 size.num_statements += 1;
3398 trans = newd->singleton ();
3399 if (newd->test.kind == rtx_test::SET_OP
3400 || newd->test.kind == rtx_test::ACCEPT)
3401 break;
3402 }
3403 /* The target of TRANS is a subroutine candidate. First recurse
3404 on it to see how big it is after subroutines have been
3405 split out. */
3406 state_size to_size = find_subroutines (type, trans->to, procs);
3407 if (d->next && to_size.depth > MAX_DEPTH)
3408 /* Keeping the target state in the same routine would lead
3409 to an excessive nesting of "if" and "switch" statements.
3410 Split it out into a subroutine so that it can use
3411 inverted tests that return early on failure. */
3412 trans->to = create_subroutine (type, trans->to, procs);
3413 else
3414 {
3415 size.num_statements += to_size.num_statements;
3416 if (to_size.num_statements < MIN_NUM_STATEMENTS)
3417 /* The target state is too small to be worth splitting.
3418 Keep it in the same routine as S. */
3419 size.depth = MAX (size.depth, to_size.depth);
3420 else
3421 /* Assume for now that we'll keep the target state in the
3422 same routine as S, but record it as a subroutine candidate
3423 if S grows too big. */
3424 candidates.safe_push (subroutine_candidate (trans, to_size));
3425 }
3426 }
3427 }
3428 if (size.num_statements > MAX_NUM_STATEMENTS)
3429 {
3430 /* S is too big. Sort the subroutine candidates so that bigger ones
3431 are nearer the end. */
3432 candidates.qsort (subroutine_candidate_cmp);
3433 while (!candidates.is_empty ()
3434 && size.num_statements > MAX_NUM_STATEMENTS)
3435 {
3436 /* Peel off a candidate and force it into a subroutine. */
3437 subroutine_candidate cand = candidates.pop ();
3438 size.num_statements -= cand.second.num_statements;
3439 cand.first->to = create_subroutine (type, cand.first->to, procs);
3440 }
3441 }
3442 /* Update the depth for subroutine candidates that we decided not to
3443 split out. */
3444 for (unsigned int i = 0; i < candidates.length (); ++i)
3445 size.depth = MAX (size.depth, candidates[i].second.depth);
3446 size.depth += 1;
3447 return size;
3448}
3449
3450/* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */
3451
3452static bool
3453safe_predicate_mode (const struct pred_data *pred, machine_mode mode)
3454{
3455 /* Scalar integer constants have VOIDmode. */
3456 if (GET_MODE_CLASS (mode) == MODE_INT
3457 && (pred->codes[CONST_INT]
3458 || pred->codes[CONST_DOUBLE]
3459 || pred->codes[CONST_WIDE_INT]
3460 || pred->codes[LABEL_REF]))
3461 return false;
3462
3463 return !pred->special && mode != VOIDmode;
3464}
3465
3466/* Fill CODES with the set of codes that could be matched by PRED. */
3467
3468static void
3469get_predicate_codes (const struct pred_data *pred, int_set *codes)
3470{
3471 for (int i = 0; i < NUM_TRUE_RTX_CODE; ++i)
3472 if (!pred || pred->codes[i])
3473 codes->safe_push (i);
3474}
3475
3476/* Return true if the first path through D1 tests the same thing as D2. */
3477
3478static bool
3479has_same_test_p (decision *d1, decision *d2)
3480{
3481 do
3482 {
3483 if (d1->test == d2->test)
3484 return true;
3485 d1 = d1->first->to->first;
3486 }
3487 while (d1);
3488 return false;
3489}
3490
3491/* Return true if D1 and D2 cannot match the same rtx. All states reachable
3492 from D2 have single decisions and all those decisions have single
3493 transitions. */
3494
3495static bool
3496mutually_exclusive_p (decision *d1, decision *d2)
3497{
3498 /* If one path through D1 fails to test the same thing as D2, assume
3499 that D2's test could be true for D1 and look for a later, more useful,
3500 test. This isn't as expensive as it looks in practice. */
3501 while (!has_same_test_p (d1, d2))
3502 {
3503 d2 = d2->singleton ()->to->singleton ();
3504 if (!d2)
3505 return false;
3506 }
3507 if (d1->test == d2->test)
3508 {
3509 /* Look for any transitions from D1 that have the same labels as
3510 the transition from D2. */
3511 transition *trans2 = d2->singleton ();
3512 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3513 {
3514 int_set::iterator i1 = trans1->labels.begin ();
3515 int_set::iterator end1 = trans1->labels.end ();
3516 int_set::iterator i2 = trans2->labels.begin ();
3517 int_set::iterator end2 = trans2->labels.end ();
3518 while (i1 != end1 && i2 != end2)
3519 if (*i1 < *i2)
3520 ++i1;
3521 else if (*i2 < *i1)
3522 ++i2;
3523 else
3524 {
3525 /* TRANS1 has some labels in common with TRANS2. Assume
3526 that D1 and D2 could match the same rtx if the target
3527 of TRANS1 could match the same rtx as D2. */
3528 for (decision *subd1 = trans1->to->first;
3529 subd1; subd1 = subd1->next)
3530 if (!mutually_exclusive_p (subd1, d2))
3531 return false;
3532 break;
3533 }
3534 }
3535 return true;
3536 }
3537 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3538 for (decision *subd1 = trans1->to->first; subd1; subd1 = subd1->next)
3539 if (!mutually_exclusive_p (subd1, d2))
3540 return false;
3541 return true;
3542}
3543
3544/* Try to merge S2's decision into D1, given that they have the same test.
3545 Fail only if EXCLUDE is nonnull and the new transition would have the
3546 same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2
3547 and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
3548 if the merge is complete. */
3549
3550static bool
3551merge_into_decision (decision *d1, state *s2, const int_set *exclude,
3552 state **next_s1, state **next_s2,
3553 const int_set **next_exclude)
3554{
3555 decision *d2 = s2->singleton ();
3556 transition *trans2 = d2->singleton ();
3557
3558 /* Get a list of the transitions that intersect TRANS2. */
3559 auto_vec <transition *, 32> intersecting;
3560 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3561 {
3562 int_set::iterator i1 = trans1->labels.begin ();
3563 int_set::iterator end1 = trans1->labels.end ();
3564 int_set::iterator i2 = trans2->labels.begin ();
3565 int_set::iterator end2 = trans2->labels.end ();
3566 bool trans1_is_subset = true;
3567 bool trans2_is_subset = true;
3568 bool intersect_p = false;
3569 while (i1 != end1 && i2 != end2)
3570 if (*i1 < *i2)
3571 {
3572 trans1_is_subset = false;
3573 ++i1;
3574 }
3575 else if (*i2 < *i1)
3576 {
3577 trans2_is_subset = false;
3578 ++i2;
3579 }
3580 else
3581 {
3582 intersect_p = true;
3583 ++i1;
3584 ++i2;
3585 }
3586 if (i1 != end1)
3587 trans1_is_subset = false;
3588 if (i2 != end2)
3589 trans2_is_subset = false;
3590 if (trans1_is_subset && trans2_is_subset)
3591 {
3592 /* There's already a transition that matches exactly.
3593 Merge the target states. */
3594 trans1->optional &= trans2->optional;
3595 *next_s1 = trans1->to;
3596 *next_s2 = trans2->to;
3597 *next_exclude = 0;
3598 return true;
3599 }
3600 if (trans2_is_subset)
3601 {
3602 /* TRANS1 has all the labels that TRANS2 needs. Merge S2 into
3603 the target of TRANS1, but (to avoid infinite recursion)
3604 make sure that we don't end up creating another transition
3605 like TRANS1. */
3606 *next_s1 = trans1->to;
3607 *next_s2 = s2;
3608 *next_exclude = &trans1->labels;
3609 return true;
3610 }
3611 if (intersect_p)
3612 intersecting.safe_push (trans1);
3613 }
3614
3615 if (intersecting.is_empty ())
3616 {
3617 /* No existing labels intersect the new ones. We can just add
3618 TRANS2 itself. */
3619 d1->push_back (d2->release ());
3620 *next_s1 = 0;
3621 *next_s2 = 0;
3622 *next_exclude = 0;
3623 return true;
3624 }
3625
3626 /* Take the union of the labels in INTERSECTING and TRANS2. Store the
3627 result in COMBINED and use NEXT as a temporary. */
3628 int_set tmp1 = trans2->labels, tmp2;
3629 int_set *combined = &tmp1, *next = &tmp2;
3630 for (unsigned int i = 0; i < intersecting.length (); ++i)
3631 {
3632 transition *trans1 = intersecting[i];
3633 next->truncate (0);
3634 next->safe_grow (trans1->labels.length () + combined->length ());
3635 int_set::iterator end
3636 = std::set_union (trans1->labels.begin (), trans1->labels.end (),
3637 combined->begin (), combined->end (),
3638 next->begin ());
3639 next->truncate (end - next->begin ());
3640 std::swap (next, combined);
3641 }
3642
3643 /* Stop now if we've been told not to create a transition with these
3644 labels. */
3645 if (exclude && *combined == *exclude)
3646 return false;
3647
3648 /* Get the transition that should carry the new labels. */
3649 transition *new_trans = intersecting[0];
3650 if (intersecting.length () == 1)
3651 {
3652 /* We're merging with one existing transition whose labels are a
3653 subset of those required. If both transitions are optional,
3654 we can just expand the set of labels so that it's suitable
3655 for both transitions. It isn't worth preserving the original
3656 transitions since we know that they can't be merged; we would
3657 need to backtrack to S2 if TRANS1->to fails. In contrast,
3658 we might be able to merge the targets of the transitions
3659 without any backtracking.
3660
3661 If instead the existing transition is not optional, ensure that
3662 all target decisions are suitably protected. Some decisions
3663 might already have a more specific requirement than NEW_TRANS,
3664 in which case there's no point testing NEW_TRANS as well. E.g. this
3665 would have happened if a test for an (eq ...) rtx had been
3666 added to a decision that tested whether the code is suitable
3667 for comparison_operator. The original comparison_operator
3668 transition would have been non-optional and the (eq ...) test
3669 would be performed by a second decision in the target of that
3670 transition.
3671
3672 The remaining case -- keeping the original optional transition
3673 when adding a non-optional TRANS2 -- is a wash. Preserving
3674 the optional transition only helps if we later merge another
3675 state S3 that is mutually exclusive with S2 and whose labels
3676 belong to *COMBINED - TRANS1->labels. We can then test the
3677 original NEW_TRANS and S3 in the same decision. We keep the
3678 optional transition around for that case, but it occurs very
3679 rarely. */
3680 gcc_assert (new_trans->labels != *combined);
3681 if (!new_trans->optional || !trans2->optional)
3682 {
3683 decision *start = 0;
3684 for (decision *end = new_trans->to->first; end; end = end->next)
3685 {
3686 if (!start && end->test != d1->test)
3687 /* END belongs to a range of decisions that need to be
3688 protected by NEW_TRANS. */
3689 start = end;
3690 if (start && (!end->next || end->next->test == d1->test))
3691 {
3692 /* Protect [START, END] with NEW_TRANS. The decisions
3693 move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */
3694 state *new_s = new state;
3695 decision *new_d = new decision (d1->test);
3696 new_d->push_back (new transition (new_trans->labels, new_s,
3697 new_trans->optional));
3698 state::range r (start, end);
3699 new_trans->to->replace (r, new_d);
3700 new_s->push_back (r);
3701
3702 /* Continue with an empty range. */
3703 start = 0;
3704
3705 /* Continue from the decision after NEW_D. */
3706 end = new_d;
3707 }
3708 }
3709 }
3710 new_trans->optional = true;
3711 new_trans->labels = *combined;
3712 }
3713 else
3714 {
3715 /* We're merging more than one existing transition together.
3716 Those transitions are successfully dividing the matching space
3717 and so we want to preserve them, even if they're optional.
3718
3719 Create a new transition with the union set of labels and make
3720 it go to a state that has the original transitions. */
3721 decision *new_d = new decision (d1->test);
3722 for (unsigned int i = 0; i < intersecting.length (); ++i)
3723 new_d->push_back (d1->remove (intersecting[i]));
3724
3725 state *new_s = new state;
3726 new_s->push_back (new_d);
3727
3728 new_trans = new transition (*combined, new_s, true);
3729 d1->push_back (new_trans);
3730 }
3731
3732 /* We now have an optional transition with labels *COMBINED. Decide
3733 whether we can use it as TRANS2 or whether we need to merge S2
3734 into the target of NEW_TRANS. */
3735 gcc_assert (new_trans->optional);
3736 if (new_trans->labels == trans2->labels)
3737 {
3738 /* NEW_TRANS matches TRANS2. Just merge the target states. */
3739 new_trans->optional = trans2->optional;
3740 *next_s1 = new_trans->to;
3741 *next_s2 = trans2->to;
3742 *next_exclude = 0;
3743 }
3744 else
3745 {
3746 /* Try to merge TRANS2 into the target of the overlapping transition,
3747 but (to prevent infinite recursion or excessive redundancy) without
3748 creating another transition of the same type. */
3749 *next_s1 = new_trans->to;
3750 *next_s2 = s2;
3751 *next_exclude = &new_trans->labels;
3752 }
3753 return true;
3754}
3755
3756/* Make progress in merging S2 into S1, given that each state in S2
3757 has a single decision. If EXCLUDE is nonnull, avoid creating a new
3758 transition with the same test as S2's decision and with the labels
3759 in *EXCLUDE.
3760
3761 Return true if there is still work to do. When returning true,
3762 set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
3763 S1, S2 and EXCLUDE should have next time round.
3764
3765 If S1 and S2 both match a particular rtx, give priority to S1. */
3766
3767static bool
3768merge_into_state_1 (state *s1, state *s2, const int_set *exclude,
3769 state **next_s1, state **next_s2,
3770 const int_set **next_exclude)
3771{
3772 decision *d2 = s2->singleton ();
3773 if (decision *d1 = s1->last)
3774 {
3775 if (d1->test.terminal_p ())
3776 /* D1 is an unconditional return, so S2 can never match. This can
3777 sometimes be a bug in the .md description, but might also happen
3778 if genconditions forces some conditions to true for certain
3779 configurations. */
3780 return false;
3781
3782 /* Go backwards through the decisions in S1, stopping once we find one
3783 that could match the same thing as S2. */
3784 while (d1->prev && mutually_exclusive_p (d1, d2))
3785 d1 = d1->prev;
3786
3787 /* Search forwards from that point, merging D2 into the first
3788 decision we can. */
3789 for (; d1; d1 = d1->next)
3790 {
3791 /* If S2 performs some optional tests before testing the same thing
3792 as D1, those tests do not help to distinguish D1 and S2, so it's
3793 better to drop them. Search through such optional decisions
3794 until we find something that tests the same thing as D1. */
3795 state *sub_s2 = s2;
3796 for (;;)
3797 {
3798 decision *sub_d2 = sub_s2->singleton ();
3799 if (d1->test == sub_d2->test)
3800 {
3801 /* Only apply EXCLUDE if we're testing the same thing
3802 as D2. */
3803 const int_set *sub_exclude = (d2 == sub_d2 ? exclude : 0);
3804
3805 /* Try to merge SUB_S2 into D1. This can only fail if
3806 it would involve creating a new transition with
3807 labels SUB_EXCLUDE. */
3808 if (merge_into_decision (d1, sub_s2, sub_exclude,
3809 next_s1, next_s2, next_exclude))
3810 return *next_s2 != 0;
3811
3812 /* Can't merge with D1; try a later decision. */
3813 break;
3814 }
3815 transition *sub_trans2 = sub_d2->singleton ();
3816 if (!sub_trans2->optional)
3817 /* Can't merge with D1; try a later decision. */
3818 break;
3819 sub_s2 = sub_trans2->to;
3820 }
3821 }
3822 }
3823
3824 /* We can't merge D2 with any existing decision. Just add it to the end. */
3825 s1->push_back (s2->release ());
3826 return false;
3827}
3828
3829/* Merge S2 into S1. If they both match a particular rtx, give
3830 priority to S1. Each state in S2 has a single decision. */
3831
3832static void
3833merge_into_state (state *s1, state *s2)
3834{
3835 const int_set *exclude = 0;
3836 while (s2 && merge_into_state_1 (s1, s2, exclude, &s1, &s2, &exclude))
3837 continue;
3838}
3839
3840/* Pairs a pattern that needs to be matched with the rtx position at
3841 which the pattern should occur. */
3842struct pattern_pos {
3843 pattern_pos () {}
3844 pattern_pos (rtx, position *);
3845
3846 rtx pattern;
3847 position *pos;
3848};
3849
3850pattern_pos::pattern_pos (rtx pattern_in, position *pos_in)
3851 : pattern (pattern_in), pos (pos_in)
3852{}
3853
3854/* Compare entries according to their depth-first order. There shouldn't
3855 be two entries at the same position. */
3856
3857bool
3858operator < (const pattern_pos &e1, const pattern_pos &e2)
3859{
3860 int diff = compare_positions (e1.pos, e2.pos);
3861 gcc_assert (diff != 0 || e1.pattern == e2.pattern);
3862 return diff < 0;
3863}
3864
3865/* Add new decisions to S that check whether the rtx at position POS
3866 matches PATTERN. Return the state that is reached in that case.
3867 TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */
3868
3869static state *
3870match_pattern_2 (state *s, md_rtx_info *info, position *pos, rtx pattern)
3871{
3872 auto_vec <pattern_pos, 32> worklist;
3873 auto_vec <pattern_pos, 32> pred_and_mode_tests;
3874 auto_vec <pattern_pos, 32> dup_tests;
3875
3876 worklist.safe_push (pattern_pos (pattern, pos));
3877 while (!worklist.is_empty ())
3878 {
3879 pattern_pos next = worklist.pop ();
3880 pattern = next.pattern;
3881 pos = next.pos;
3882 unsigned int reverse_s = worklist.length ();
3883
3884 enum rtx_code code = GET_CODE (pattern);
3885 switch (code)
3886 {
3887 case MATCH_OP_DUP:
3888 case MATCH_DUP:
3889 case MATCH_PAR_DUP:
3890 /* Add a test that the rtx matches the earlier one, but only
3891 after the structure and predicates have been checked. */
3892 dup_tests.safe_push (pattern_pos (pattern, pos));
3893
3894 /* Use the same code check as the original operand. */
3895 pattern = find_operand (info->def, XINT (pattern, 0), NULL_RTX);
3896 /* Fall through. */
3897
3898 case MATCH_PARALLEL:
3899 case MATCH_OPERAND:
3900 case MATCH_SCRATCH:
3901 case MATCH_OPERATOR:
3902 {
3903 const char *pred_name = predicate_name (pattern);
3904 const struct pred_data *pred = 0;
3905 if (pred_name[0] != 0)
3906 {
3907 pred = lookup_predicate (pred_name);
3908 /* Only report errors once per rtx. */
3909 if (code == GET_CODE (pattern))
3910 {
3911 if (!pred)
3912 error_at (info->loc, "unknown predicate '%s' used in %s",
3913 pred_name, GET_RTX_NAME (code));
3914 else if (code == MATCH_PARALLEL
3915 && pred->singleton != PARALLEL)
3916 error_at (info->loc, "predicate '%s' used in"
3917 " match_parallel does not allow only PARALLEL",
3918 pred->name);
3919 }
3920 }
3921
3922 if (code == MATCH_PARALLEL || code == MATCH_PAR_DUP)
3923 {
3924 /* Check that we have a parallel with enough elements. */
3925 s = add_decision (s, rtx_test::code (pos), PARALLEL, false);
3926 int min_len = XVECLEN (pattern, 2);
3927 s = add_decision (s, rtx_test::veclen_ge (pos, min_len),
3928 true, false);
3929 }
3930 else
3931 {
3932 /* Check that the rtx has one of codes accepted by the
3933 predicate. This is necessary when matching suboperands
3934 of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
3935 call XEXP (X, N) without checking that X has at least
3936 N+1 operands. */
3937 int_set codes;
3938 get_predicate_codes (pred, &codes);
3939 bool need_codes = (pred
3940 && (code == MATCH_OPERATOR
3941 || code == MATCH_OP_DUP));
3942 s = add_decision (s, rtx_test::code (pos), codes, !need_codes);
3943 }
3944
3945 /* Postpone the predicate check until we've checked the rest
3946 of the rtx structure. */
3947 if (code == GET_CODE (pattern))
3948 pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
3949
3950 /* If we need to match suboperands, add them to the worklist. */
3951 if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
3952 {
3953 position **subpos_ptr;
3954 enum position_type pos_type;
3955 int i;
3956 if (code == MATCH_OPERATOR || code == MATCH_OP_DUP)
3957 {
3958 pos_type = POS_XEXP;
3959 subpos_ptr = &pos->xexps;
3960 i = (code == MATCH_OPERATOR ? 2 : 1);
3961 }
3962 else
3963 {
3964 pos_type = POS_XVECEXP0;
3965 subpos_ptr = &pos->xvecexp0s;
3966 i = 2;
3967 }
3968 for (int j = 0; j < XVECLEN (pattern, i); ++j)
3969 {
3970 position *subpos = next_position (subpos_ptr, pos,
3971 pos_type, j);
3972 worklist.safe_push (pattern_pos (XVECEXP (pattern, i, j),
3973 subpos));
3974 subpos_ptr = &subpos->next;
3975 }
3976 }
3977 break;
3978 }
3979
3980 default:
3981 {
3982 /* Check that the rtx has the right code. */
3983 s = add_decision (s, rtx_test::code (pos), code, false);
3984
3985 /* Queue a test for the mode if one is specified. */
3986 if (GET_MODE (pattern) != VOIDmode)
3987 pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
3988
3989 /* Push subrtxes onto the worklist. Match nonrtx operands now. */
3990 const char *fmt = GET_RTX_FORMAT (code);
3991 position **subpos_ptr = &pos->xexps;
3992 for (size_t i = 0; fmt[i]; ++i)
3993 {
3994 position *subpos = next_position (subpos_ptr, pos,
3995 POS_XEXP, i);
3996 switch (fmt[i])
3997 {
3998 case 'e': case 'u':
3999 worklist.safe_push (pattern_pos (XEXP (pattern, i),
4000 subpos));
4001 break;
4002
4003 case 'E':
4004 {
4005 /* Make sure the vector has the right number of
4006 elements. */
4007 int length = XVECLEN (pattern, i);
4008 s = add_decision (s, rtx_test::veclen (pos),
4009 length, false);
4010
4011 position **subpos2_ptr = &pos->xvecexp0s;
4012 for (int j = 0; j < length; j++)
4013 {
4014 position *subpos2 = next_position (subpos2_ptr, pos,
4015 POS_XVECEXP0, j);
4016 rtx x = XVECEXP (pattern, i, j);
4017 worklist.safe_push (pattern_pos (x, subpos2));
4018 subpos2_ptr = &subpos2->next;
4019 }
4020 break;
4021 }
4022
4023 case 'i':
4024 /* Make sure that XINT (X, I) has the right value. */
4025 s = add_decision (s, rtx_test::int_field (pos, i),
4026 XINT (pattern, i), false);
4027 break;
4028
4029 case 'r':
4030 /* Make sure that REGNO (X) has the right value. */
4031 gcc_assert (i == 0);
4032 s = add_decision (s, rtx_test::regno_field (pos),
4033 REGNO (pattern), false);
4034 break;
4035
4036 case 'w':
4037 /* Make sure that XWINT (X, I) has the right value. */
4038 s = add_decision (s, rtx_test::wide_int_field (pos, i),
4039 XWINT (pattern, 0), false);
4040 break;
4041
4042 case '0':
4043 break;
4044
4045 default:
4046 gcc_unreachable ();
4047 }
4048 subpos_ptr = &subpos->next;
4049 }
4050 }
4051 break;
4052 }
4053 /* Operands are pushed onto the worklist so that later indices are
4054 nearer the top. That's what we want for SETs, since a SET_SRC
4055 is a better discriminator than a SET_DEST. In other cases it's
4056 usually better to match earlier indices first. This is especially
4057 true of PARALLELs, where the first element tends to be the most
4058 individual. It's also true for commutative operators, where the
4059 canonicalization rules say that the more complex operand should
4060 come first. */
4061 if (code != SET && worklist.length () > reverse_s)
4062 std::reverse (&worklist[0] + reverse_s,
4063 &worklist[0] + worklist.length ());
4064 }
4065
4066 /* Sort the predicate and mode tests so that they're in depth-first order.
4067 The main goal of this is to put SET_SRC match_operands after SET_DEST
4068 match_operands and after mode checks for the enclosing SET_SRC operators
4069 (such as the mode of a PLUS in an addition instruction). The latter
4070 two types of test can determine the mode exactly, whereas a SET_SRC
4071 match_operand often has to cope with the possibility of the operand
4072 being a modeless constant integer. E.g. something that matches
4073 register_operand (x, SImode) never matches register_operand (x, DImode),
4074 but a const_int that matches immediate_operand (x, SImode) also matches
4075 immediate_operand (x, DImode). The register_operand cases can therefore
4076 be distinguished by a switch on the mode, but the immediate_operand
4077 cases can't. */
4078 if (pred_and_mode_tests.length () > 1)
4079 std::sort (&pred_and_mode_tests[0],
4080 &pred_and_mode_tests[0] + pred_and_mode_tests.length ());
4081
4082 /* Add the mode and predicate tests. */
4083 pattern_pos *e;
4084 unsigned int i;
4085 FOR_EACH_VEC_ELT (pred_and_mode_tests, i, e)
4086 {
4087 switch (GET_CODE (e->pattern))
4088 {
4089 case MATCH_PARALLEL:
4090 case MATCH_OPERAND:
4091 case MATCH_SCRATCH:
4092 case MATCH_OPERATOR:
4093 {
4094 int opno = XINT (e->pattern, 0);
4095 num_operands = MAX (num_operands, opno + 1);
4096 const char *pred_name = predicate_name (e->pattern);
4097 if (pred_name[0])
4098 {
4099 const struct pred_data *pred = lookup_predicate (pred_name);
4100 /* Check the mode first, to distinguish things like SImode
4101 and DImode register_operands, as described above. */
4102 machine_mode mode = GET_MODE (e->pattern);
4103 if (pred && safe_predicate_mode (pred, mode))
4104 s = add_decision (s, rtx_test::mode (e->pos), mode, true);
4105
4106 /* Assign to operands[] first, so that the rtx usually doesn't
4107 need to be live across the call to the predicate.
4108
4109 This shouldn't cause a problem with dirtying the page,
4110 since we fully expect to assign to operands[] at some point,
4111 and since the caller usually writes to other parts of
4112 recog_data anyway. */
4113 s = add_decision (s, rtx_test::set_op (e->pos, opno),
4114 true, false);
4115 s = add_decision (s, rtx_test::predicate (e->pos, pred, mode),
4116 true, false);
4117 }
4118 else
4119 /* Historically we've ignored the mode when there's no
4120 predicate. Just set up operands[] unconditionally. */
4121 s = add_decision (s, rtx_test::set_op (e->pos, opno),
4122 true, false);
4123 break;
4124 }
4125
4126 default:
4127 s = add_decision (s, rtx_test::mode (e->pos),
4128 GET_MODE (e->pattern), false);
4129 break;
4130 }
4131 }
4132
4133 /* Finally add rtx_equal_p checks for duplicated operands. */
4134 FOR_EACH_VEC_ELT (dup_tests, i, e)
4135 s = add_decision (s, rtx_test::duplicate (e->pos, XINT (e->pattern, 0)),
4136 true, false);
4137 return s;
4138}
4139
4140/* Add new decisions to S that make it return ACCEPTANCE if:
4141
4142 (1) the rtx doesn't match anything already matched by S
4143 (2) the rtx matches TOP_PATTERN and
4144 (3) the C test required by INFO->def is true
4145
4146 For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns
4147 to match, otherwise it is a single instruction pattern. */
4148
4149static void
4150match_pattern_1 (state *s, md_rtx_info *info, rtx pattern,
4151 acceptance_type acceptance)
4152{
4153 if (acceptance.type == PEEPHOLE2)
4154 {
4155 /* Match each individual instruction. */
4156 position **subpos_ptr = &peep2_insn_pos_list;
4157 int count = 0;
4158 for (int i = 0; i < XVECLEN (pattern, 0); ++i)
4159 {
4160 rtx x = XVECEXP (pattern, 0, i);
4161 position *subpos = next_position (subpos_ptr, &root_pos,
4162 POS_PEEP2_INSN, count);
4163 if (count > 0)
4164 s = add_decision (s, rtx_test::peep2_count (count + 1),
4165 true, false);
4166 s = match_pattern_2 (s, info, subpos, x);
4167 subpos_ptr = &subpos->next;
4168 count += 1;
4169 }
4170 acceptance.u.full.u.match_len = count - 1;
4171 }
4172 else
4173 {
4174 /* Make the rtx itself. */
4175 s = match_pattern_2 (s, info, &root_pos, pattern);
4176
4177 /* If the match is only valid when extra clobbers are added,
4178 make sure we're able to pass that information to the caller. */
4179 if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers)
4180 s = add_decision (s, rtx_test::have_num_clobbers (), true, false);
4181 }
4182
4183 /* Make sure that the C test is true. */
4184 const char *c_test = get_c_test (info->def);
4185 if (maybe_eval_c_test (c_test) != 1)
4186 s = add_decision (s, rtx_test::c_test (c_test), true, false);
4187
4188 /* Accept the pattern. */
4189 add_decision (s, rtx_test::accept (acceptance), true, false);
4190}
4191
4192/* Like match_pattern_1, but (if merge_states_p) try to merge the
4193 decisions with what's already in S, to reduce the amount of
4194 backtracking. */
4195
4196static void
4197match_pattern (state *s, md_rtx_info *info, rtx pattern,
4198 acceptance_type acceptance)
4199{
4200 if (merge_states_p)
4201 {
4202 state root;
4203 /* Add the decisions to a fresh state and then merge the full tree
4204 into the existing one. */
4205 match_pattern_1 (&root, info, pattern, acceptance);
4206 merge_into_state (s, &root);
4207 }
4208 else
4209 match_pattern_1 (s, info, pattern, acceptance);
4210}
4211
4212/* Begin the output file. */
4213
4214static void
4215write_header (void)
4216{
4217 puts ("\
4218/* Generated automatically by the program `genrecog' from the target\n\
4219 machine description file. */\n\
4220\n\
4221#include \"config.h\"\n\
4222#include \"system.h\"\n\
4223#include \"coretypes.h\"\n\
4224#include \"backend.h\"\n\
4225#include \"predict.h\"\n\
4226#include \"rtl.h\"\n\
4227#include \"memmodel.h\"\n\
4228#include \"tm_p.h\"\n\
4229#include \"emit-rtl.h\"\n\
4230#include \"insn-config.h\"\n\
4231#include \"recog.h\"\n\
4232#include \"output.h\"\n\
4233#include \"flags.h\"\n\
4234#include \"df.h\"\n\
4235#include \"resource.h\"\n\
4236#include \"diagnostic-core.h\"\n\
4237#include \"reload.h\"\n\
4238#include \"regs.h\"\n\
4239#include \"tm-constrs.h\"\n\
4240\n");
4241
4242 puts ("\n\
4243/* `recog' contains a decision tree that recognizes whether the rtx\n\
4244 X0 is a valid instruction.\n\
4245\n\
4246 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
4247 returns a nonnegative number which is the insn code number for the\n\
4248 pattern that matched. This is the same as the order in the machine\n\
4249 description of the entry that matched. This number can be used as an\n\
4250 index into `insn_data' and other tables.\n");
4251 puts ("\
4252 The third parameter to recog is an optional pointer to an int. If\n\
4253 present, recog will accept a pattern if it matches except for missing\n\
4254 CLOBBER expressions at the end. In that case, the value pointed to by\n\
4255 the optional pointer will be set to the number of CLOBBERs that need\n\
4256 to be added (it should be initialized to zero by the caller). If it");
4257 puts ("\
4258 is set nonzero, the caller should allocate a PARALLEL of the\n\
4259 appropriate size, copy the initial entries, and call add_clobbers\n\
4260 (found in insn-emit.c) to fill in the CLOBBERs.\n\
4261");
4262
4263 puts ("\n\
4264 The function split_insns returns 0 if the rtl could not\n\
4265 be split or the split rtl as an INSN list if it can be.\n\
4266\n\
4267 The function peephole2_insns returns 0 if the rtl could not\n\
4268 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4269 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4270*/\n\n");
4271}
4272
4273/* Return the C type of a parameter with type TYPE. */
4274
4275static const char *
4276parameter_type_string (parameter::type_enum type)
4277{
4278 switch (type)
4279 {
4280 case parameter::UNSET:
4281 break;
4282
4283 case parameter::CODE:
4284 return "rtx_code";
4285
4286 case parameter::MODE:
4287 return "machine_mode";
4288
4289 case parameter::INT:
4290 return "int";
4291
4292 case parameter::UINT:
4293 return "unsigned int";
4294
4295 case parameter::WIDE_INT:
4296 return "HOST_WIDE_INT";
4297 }
4298 gcc_unreachable ();
4299}
4300
4301/* Return true if ACCEPTANCE requires only a single C statement even in
4302 a backtracking context. */
4303
4304static bool
4305single_statement_p (const acceptance_type &acceptance)
4306{
4307 if (acceptance.partial_p)
4308 /* We need to handle failures of the subroutine. */
4309 return false;
4310 switch (acceptance.type)
4311 {
4312 case SUBPATTERN:
4313 case SPLIT:
4314 return true;
4315
4316 case RECOG:
4317 /* False if we need to assign to pnum_clobbers. */
4318 return acceptance.u.full.u.num_clobbers == 0;
4319
4320 case PEEPHOLE2:
4321 /* We need to assign to pmatch_len_ and handle null returns from the
4322 peephole2 routine. */
4323 return false;
4324 }
4325 gcc_unreachable ();
4326}
4327
4328/* Return the C failure value for a routine of type TYPE. */
4329
4330static const char *
4331get_failure_return (routine_type type)
4332{
4333 switch (type)
4334 {
4335 case SUBPATTERN:
4336 case RECOG:
4337 return "-1";
4338
4339 case SPLIT:
4340 case PEEPHOLE2:
4341 return "NULL";
4342 }
4343 gcc_unreachable ();
4344}
4345