2014-08-15 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / genrecog.c
blob457b59c901d95d30d90af0dcc1d31380a86730f8
1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
21 /* This program is used to produce insn-recog.c, which contains a
22 function called `recog' plus its subroutines. These functions
23 contain a decision tree that recognizes whether an rtx, the
24 argument given to recog, is a valid instruction.
26 recog returns -1 if the rtx is not valid. If the rtx is valid,
27 recog returns a nonnegative number which is the insn code number
28 for the pattern that matched. This is the same as the order in the
29 machine description of the entry that matched. This number can be
30 used as an index into various insn_* tables, such as insn_template,
31 insn_outfun, and insn_n_operands (found in insn-output.c).
33 The third argument to recog is an optional pointer to an int. If
34 present, recog will accept a pattern if it matches except for
35 missing CLOBBER expressions at the end. In that case, the value
36 pointed to by the optional pointer will be set to the number of
37 CLOBBERs that need to be added (it should be initialized to zero by
38 the caller). If it is set nonzero, the caller should allocate a
39 PARALLEL of the appropriate size, copy the initial entries, and
40 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
42 This program also generates the function `split_insns', which
43 returns 0 if the rtl could not be split, or it returns the split
44 rtl as an INSN list.
46 This program also generates the function `peephole2_insns', which
47 returns 0 if the rtl could not be matched. If there was a match,
48 the new rtl is returned in an INSN list, and LAST_INSN will point
49 to the last recognized insn in the old sequence. */
51 #include "bconfig.h"
52 #include "system.h"
53 #include "coretypes.h"
54 #include "tm.h"
55 #include "rtl.h"
56 #include "errors.h"
57 #include "read-md.h"
58 #include "gensupport.h"
60 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
61 printf ("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
63 /* Ways of obtaining an rtx to be tested. */
64 enum position_type {
65 /* PATTERN (peep2_next_insn (ARG)). */
66 POS_PEEP2_INSN,
68 /* XEXP (BASE, ARG). */
69 POS_XEXP,
71 /* XVECEXP (BASE, 0, ARG). */
72 POS_XVECEXP0
75 /* The position of an rtx relative to X0. Each useful position is
76 represented by exactly one instance of this structure. */
77 struct position
79 /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
80 struct position *base;
82 /* A position with the same BASE and TYPE, but with the next value
83 of ARG. */
84 struct position *next;
86 /* A list of all POS_XEXP positions that use this one as their base,
87 chained by NEXT fields. The first entry represents XEXP (this, 0),
88 the second represents XEXP (this, 1), and so on. */
89 struct position *xexps;
91 /* A list of POS_XVECEXP0 positions that use this one as their base,
92 chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0),
93 the second represents XVECEXP (this, 0, 1), and so on. */
94 struct position *xvecexp0s;
96 /* The type of position. */
97 enum position_type type;
99 /* The argument to TYPE (shown as ARG in the position_type comments). */
100 int arg;
102 /* The depth of this position, with 0 as the root. */
103 int depth;
106 /* A listhead of decision trees. The alternatives to a node are kept
107 in a doubly-linked list so we can easily add nodes to the proper
108 place when merging. */
110 struct decision_head
112 struct decision *first;
113 struct decision *last;
116 /* These types are roughly in the order in which we'd like to test them. */
117 enum decision_type
119 DT_num_insns,
120 DT_mode, DT_code, DT_veclen,
121 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
122 DT_const_int,
123 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
124 DT_accept_op, DT_accept_insn
127 /* A single test. The two accept types aren't tests per-se, but
128 their equality (or lack thereof) does affect tree merging so
129 it is convenient to keep them here. */
131 struct decision_test
133 /* A linked list through the tests attached to a node. */
134 struct decision_test *next;
136 enum decision_type type;
138 union
140 int num_insns; /* Number if insn in a define_peephole2. */
141 enum machine_mode mode; /* Machine mode of node. */
142 RTX_CODE code; /* Code to test. */
144 struct
146 const char *name; /* Predicate to call. */
147 const struct pred_data *data;
148 /* Optimization hints for this predicate. */
149 enum machine_mode mode; /* Machine mode for node. */
150 } pred;
152 const char *c_test; /* Additional test to perform. */
153 int veclen; /* Length of vector. */
154 int dup; /* Number of operand to compare against. */
155 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
156 int opno; /* Operand number matched. */
158 struct {
159 int code_number; /* Insn number matched. */
160 int lineno; /* Line number of the insn. */
161 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
162 } insn;
163 } u;
166 /* Data structure for decision tree for recognizing legitimate insns. */
168 struct decision
170 struct decision_head success; /* Nodes to test on success. */
171 struct decision *next; /* Node to test on failure. */
172 struct decision *prev; /* Node whose failure tests us. */
173 struct decision *afterward; /* Node to test on success,
174 but failure of successor nodes. */
176 struct position *position; /* Position in pattern. */
178 struct decision_test *tests; /* The tests for this node. */
180 int number; /* Node number, used for labels */
181 int subroutine_number; /* Number of subroutine this node starts */
182 int need_label; /* Label needs to be output. */
185 #define SUBROUTINE_THRESHOLD 100
187 static int next_subroutine_number;
189 /* We can write three types of subroutines: One for insn recognition,
190 one to split insns, and one for peephole-type optimizations. This
191 defines which type is being written. */
193 enum routine_type {
194 RECOG, SPLIT, PEEPHOLE2
197 #define IS_SPLIT(X) ((X) != RECOG)
199 /* Next available node number for tree nodes. */
201 static int next_number;
203 /* Next number to use as an insn_code. */
205 static int next_insn_code;
207 /* Record the highest depth we ever have so we know how many variables to
208 allocate in each subroutine we make. */
210 static int max_depth;
212 /* The line number of the start of the pattern currently being processed. */
213 static int pattern_lineno;
215 /* The root position (x0). */
216 static struct position root_pos;
218 /* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
219 since we are given that instruction's pattern as x0. */
220 static struct position *peep2_insn_pos_list = &root_pos;
222 extern void debug_decision
223 (struct decision *);
224 extern void debug_decision_list
225 (struct decision *);
227 /* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
228 points to where the unique object that represents the position
229 should be stored. Create the object if it doesn't already exist,
230 otherwise reuse the object that is already there. */
232 static struct position *
233 next_position (struct position **next_ptr, struct position *base,
234 enum position_type type, int arg)
236 struct position *pos;
238 pos = *next_ptr;
239 if (!pos)
241 pos = XCNEW (struct position);
242 pos->base = base;
243 pos->type = type;
244 pos->arg = arg;
245 pos->depth = base->depth + 1;
246 *next_ptr = pos;
248 return pos;
251 /* Compare positions POS1 and POS2 lexicographically. */
253 static int
254 compare_positions (struct position *pos1, struct position *pos2)
256 int diff;
258 diff = pos1->depth - pos2->depth;
259 if (diff < 0)
261 pos2 = pos2->base;
262 while (pos1->depth != pos2->depth);
263 else if (diff > 0)
265 pos1 = pos1->base;
266 while (pos1->depth != pos2->depth);
267 while (pos1 != pos2)
269 diff = (int) pos1->type - (int) pos2->type;
270 if (diff == 0)
271 diff = pos1->arg - pos2->arg;
272 pos1 = pos1->base;
273 pos2 = pos2->base;
275 return diff;
278 /* Create a new node in sequence after LAST. */
280 static struct decision *
281 new_decision (struct position *pos, struct decision_head *last)
283 struct decision *new_decision = XCNEW (struct decision);
285 new_decision->success = *last;
286 new_decision->position = pos;
287 new_decision->number = next_number++;
289 last->first = last->last = new_decision;
290 return new_decision;
293 /* Create a new test and link it in at PLACE. */
295 static struct decision_test *
296 new_decision_test (enum decision_type type, struct decision_test ***pplace)
298 struct decision_test **place = *pplace;
299 struct decision_test *test;
301 test = XNEW (struct decision_test);
302 test->next = *place;
303 test->type = type;
304 *place = test;
306 place = &test->next;
307 *pplace = place;
309 return test;
312 /* Search for and return operand N, stop when reaching node STOP. */
314 static rtx
315 find_operand (rtx pattern, int n, rtx stop)
317 const char *fmt;
318 RTX_CODE code;
319 int i, j, len;
320 rtx r;
322 if (pattern == stop)
323 return stop;
325 code = GET_CODE (pattern);
326 if ((code == MATCH_SCRATCH
327 || code == MATCH_OPERAND
328 || code == MATCH_OPERATOR
329 || code == MATCH_PARALLEL)
330 && XINT (pattern, 0) == n)
331 return pattern;
333 fmt = GET_RTX_FORMAT (code);
334 len = GET_RTX_LENGTH (code);
335 for (i = 0; i < len; i++)
337 switch (fmt[i])
339 case 'e': case 'u':
340 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
341 return r;
342 break;
344 case 'V':
345 if (! XVEC (pattern, i))
346 break;
347 /* Fall through. */
349 case 'E':
350 for (j = 0; j < XVECLEN (pattern, i); j++)
351 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
352 != NULL_RTX)
353 return r;
354 break;
356 case 'i': case 'w': case '0': case 's':
357 break;
359 default:
360 gcc_unreachable ();
364 return NULL;
367 /* Search for and return operand M, such that it has a matching
368 constraint for operand N. */
370 static rtx
371 find_matching_operand (rtx pattern, int n)
373 const char *fmt;
374 RTX_CODE code;
375 int i, j, len;
376 rtx r;
378 code = GET_CODE (pattern);
379 if (code == MATCH_OPERAND
380 && (XSTR (pattern, 2)[0] == '0' + n
381 || (XSTR (pattern, 2)[0] == '%'
382 && XSTR (pattern, 2)[1] == '0' + n)))
383 return pattern;
385 fmt = GET_RTX_FORMAT (code);
386 len = GET_RTX_LENGTH (code);
387 for (i = 0; i < len; i++)
389 switch (fmt[i])
391 case 'e': case 'u':
392 if ((r = find_matching_operand (XEXP (pattern, i), n)))
393 return r;
394 break;
396 case 'V':
397 if (! XVEC (pattern, i))
398 break;
399 /* Fall through. */
401 case 'E':
402 for (j = 0; j < XVECLEN (pattern, i); j++)
403 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
404 return r;
405 break;
407 case 'i': case 'w': case '0': case 's':
408 break;
410 default:
411 gcc_unreachable ();
415 return NULL;
419 /* Check for various errors in patterns. SET is nonnull for a destination,
420 and is the complete set pattern. SET_CODE is '=' for normal sets, and
421 '+' within a context that requires in-out constraints. */
423 static void
424 validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
426 const char *fmt;
427 RTX_CODE code;
428 size_t i, len;
429 int j;
431 code = GET_CODE (pattern);
432 switch (code)
434 case MATCH_SCRATCH:
435 return;
436 case MATCH_DUP:
437 case MATCH_OP_DUP:
438 case MATCH_PAR_DUP:
439 if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
440 error_with_line (pattern_lineno,
441 "operand %i duplicated before defined",
442 XINT (pattern, 0));
443 break;
444 case MATCH_OPERAND:
445 case MATCH_OPERATOR:
447 const char *pred_name = XSTR (pattern, 1);
448 const struct pred_data *pred;
449 const char *c_test;
451 if (GET_CODE (insn) == DEFINE_INSN)
452 c_test = XSTR (insn, 2);
453 else
454 c_test = XSTR (insn, 1);
456 if (pred_name[0] != 0)
458 pred = lookup_predicate (pred_name);
459 if (!pred)
460 error_with_line (pattern_lineno, "unknown predicate '%s'",
461 pred_name);
463 else
464 pred = 0;
466 if (code == MATCH_OPERAND)
468 const char constraints0 = XSTR (pattern, 2)[0];
470 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
471 don't use the MATCH_OPERAND constraint, only the predicate.
472 This is confusing to folks doing new ports, so help them
473 not make the mistake. */
474 if (GET_CODE (insn) == DEFINE_EXPAND
475 || GET_CODE (insn) == DEFINE_SPLIT
476 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
478 if (constraints0)
479 error_with_line (pattern_lineno,
480 "constraints not supported in %s",
481 rtx_name[GET_CODE (insn)]);
484 /* A MATCH_OPERAND that is a SET should have an output reload. */
485 else if (set && constraints0)
487 if (set_code == '+')
489 if (constraints0 == '+')
491 /* If we've only got an output reload for this operand,
492 we'd better have a matching input operand. */
493 else if (constraints0 == '='
494 && find_matching_operand (insn, XINT (pattern, 0)))
496 else
497 error_with_line (pattern_lineno,
498 "operand %d missing in-out reload",
499 XINT (pattern, 0));
501 else if (constraints0 != '=' && constraints0 != '+')
502 error_with_line (pattern_lineno,
503 "operand %d missing output reload",
504 XINT (pattern, 0));
508 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
509 while not likely to occur at runtime, results in less efficient
510 code from insn-recog.c. */
511 if (set && pred && pred->allows_non_lvalue)
512 error_with_line (pattern_lineno,
513 "destination operand %d allows non-lvalue",
514 XINT (pattern, 0));
516 /* A modeless MATCH_OPERAND can be handy when we can check for
517 multiple modes in the c_test. In most other cases, it is a
518 mistake. Only DEFINE_INSN is eligible, since SPLIT and
519 PEEP2 can FAIL within the output pattern. Exclude special
520 predicates, which check the mode themselves. Also exclude
521 predicates that allow only constants. Exclude the SET_DEST
522 of a call instruction, as that is a common idiom. */
524 if (GET_MODE (pattern) == VOIDmode
525 && code == MATCH_OPERAND
526 && GET_CODE (insn) == DEFINE_INSN
527 && pred
528 && !pred->special
529 && pred->allows_non_const
530 && strstr (c_test, "operands") == NULL
531 && ! (set
532 && GET_CODE (set) == SET
533 && GET_CODE (SET_SRC (set)) == CALL))
534 message_with_line (pattern_lineno,
535 "warning: operand %d missing mode?",
536 XINT (pattern, 0));
537 return;
540 case SET:
542 enum machine_mode dmode, smode;
543 rtx dest, src;
545 dest = SET_DEST (pattern);
546 src = SET_SRC (pattern);
548 /* STRICT_LOW_PART is a wrapper. Its argument is the real
549 destination, and it's mode should match the source. */
550 if (GET_CODE (dest) == STRICT_LOW_PART)
551 dest = XEXP (dest, 0);
553 /* Find the referent for a DUP. */
555 if (GET_CODE (dest) == MATCH_DUP
556 || GET_CODE (dest) == MATCH_OP_DUP
557 || GET_CODE (dest) == MATCH_PAR_DUP)
558 dest = find_operand (insn, XINT (dest, 0), NULL);
560 if (GET_CODE (src) == MATCH_DUP
561 || GET_CODE (src) == MATCH_OP_DUP
562 || GET_CODE (src) == MATCH_PAR_DUP)
563 src = find_operand (insn, XINT (src, 0), NULL);
565 dmode = GET_MODE (dest);
566 smode = GET_MODE (src);
568 /* The mode of an ADDRESS_OPERAND is the mode of the memory
569 reference, not the mode of the address. */
570 if (GET_CODE (src) == MATCH_OPERAND
571 && ! strcmp (XSTR (src, 1), "address_operand"))
574 /* The operands of a SET must have the same mode unless one
575 is VOIDmode. */
576 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
577 error_with_line (pattern_lineno,
578 "mode mismatch in set: %smode vs %smode",
579 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
581 /* If only one of the operands is VOIDmode, and PC or CC0 is
582 not involved, it's probably a mistake. */
583 else if (dmode != smode
584 && GET_CODE (dest) != PC
585 && GET_CODE (dest) != CC0
586 && GET_CODE (src) != PC
587 && GET_CODE (src) != CC0
588 && !CONST_INT_P (src)
589 && !CONST_WIDE_INT_P (src)
590 && GET_CODE (src) != CALL)
592 const char *which;
593 which = (dmode == VOIDmode ? "destination" : "source");
594 message_with_line (pattern_lineno,
595 "warning: %s missing a mode?", which);
598 if (dest != SET_DEST (pattern))
599 validate_pattern (dest, insn, pattern, '=');
600 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
601 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
602 return;
605 case CLOBBER:
606 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
607 return;
609 case ZERO_EXTRACT:
610 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
611 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
612 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
613 return;
615 case STRICT_LOW_PART:
616 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
617 return;
619 case LABEL_REF:
620 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
621 error_with_line (pattern_lineno,
622 "operand to label_ref %smode not VOIDmode",
623 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
624 break;
626 default:
627 break;
630 fmt = GET_RTX_FORMAT (code);
631 len = GET_RTX_LENGTH (code);
632 for (i = 0; i < len; i++)
634 switch (fmt[i])
636 case 'e': case 'u':
637 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
638 break;
640 case 'E':
641 for (j = 0; j < XVECLEN (pattern, i); j++)
642 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
643 break;
645 case 'i': case 'w': case '0': case 's':
646 break;
648 default:
649 gcc_unreachable ();
654 /* Create a chain of nodes to verify that an rtl expression matches
655 PATTERN.
657 LAST is a pointer to the listhead in the previous node in the chain (or
658 in the calling function, for the first node).
660 POSITION is the current position in the insn.
662 INSN_TYPE is the type of insn for which we are emitting code.
664 A pointer to the final node in the chain is returned. */
666 static struct decision *
667 add_to_sequence (rtx pattern, struct decision_head *last,
668 struct position *pos, enum routine_type insn_type, int top)
670 RTX_CODE code;
671 struct decision *this_decision, *sub;
672 struct decision_test *test;
673 struct decision_test **place;
674 struct position *subpos, **subpos_ptr;
675 size_t i;
676 const char *fmt;
677 int len;
678 enum machine_mode mode;
679 enum position_type pos_type;
681 if (pos->depth > max_depth)
682 max_depth = pos->depth;
684 sub = this_decision = new_decision (pos, last);
685 place = &this_decision->tests;
687 mode = GET_MODE (pattern);
688 code = GET_CODE (pattern);
690 switch (code)
692 case PARALLEL:
693 /* Toplevel peephole pattern. */
694 if (insn_type == PEEPHOLE2 && top)
696 int num_insns;
698 /* Check we have sufficient insns. This avoids complications
699 because we then know peep2_next_insn never fails. */
700 num_insns = XVECLEN (pattern, 0);
701 if (num_insns > 1)
703 test = new_decision_test (DT_num_insns, &place);
704 test->u.num_insns = num_insns;
705 last = &sub->success;
707 else
709 /* We don't need the node we just created -- unlink it. */
710 last->first = last->last = NULL;
713 subpos_ptr = &peep2_insn_pos_list;
714 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
716 subpos = next_position (subpos_ptr, &root_pos,
717 POS_PEEP2_INSN, i);
718 sub = add_to_sequence (XVECEXP (pattern, 0, i),
719 last, subpos, insn_type, 0);
720 last = &sub->success;
721 subpos_ptr = &subpos->next;
723 goto ret;
726 /* Else nothing special. */
727 break;
729 case MATCH_PARALLEL:
730 /* The explicit patterns within a match_parallel enforce a minimum
731 length on the vector. The match_parallel predicate may allow
732 for more elements. We do need to check for this minimum here
733 or the code generated to match the internals may reference data
734 beyond the end of the vector. */
735 test = new_decision_test (DT_veclen_ge, &place);
736 test->u.veclen = XVECLEN (pattern, 2);
737 /* Fall through. */
739 case MATCH_OPERAND:
740 case MATCH_SCRATCH:
741 case MATCH_OPERATOR:
743 RTX_CODE was_code = code;
744 const char *pred_name;
745 bool allows_const_int = true;
747 if (code == MATCH_SCRATCH)
749 pred_name = "scratch_operand";
750 code = UNKNOWN;
752 else
754 pred_name = XSTR (pattern, 1);
755 if (code == MATCH_PARALLEL)
756 code = PARALLEL;
757 else
758 code = UNKNOWN;
761 if (pred_name[0] != 0)
763 const struct pred_data *pred;
765 test = new_decision_test (DT_pred, &place);
766 test->u.pred.name = pred_name;
767 test->u.pred.mode = mode;
769 /* See if we know about this predicate.
770 If we do, remember it for use below.
772 We can optimize the generated code a little if either
773 (a) the predicate only accepts one code, or (b) the
774 predicate does not allow CONST_INT or CONST_WIDE_INT,
775 in which case it can match only if the modes match. */
776 pred = lookup_predicate (pred_name);
777 if (pred)
779 test->u.pred.data = pred;
780 allows_const_int = (pred->codes[CONST_INT]
781 || pred->codes[CONST_WIDE_INT]);
782 if (was_code == MATCH_PARALLEL
783 && pred->singleton != PARALLEL)
784 error_with_line (pattern_lineno,
785 "predicate '%s' used in match_parallel "
786 "does not allow only PARALLEL", pred->name);
787 else
788 code = pred->singleton;
790 else
791 error_with_line (pattern_lineno,
792 "unknown predicate '%s' in '%s' expression",
793 pred_name, GET_RTX_NAME (was_code));
796 /* Can't enforce a mode if we allow const_int. */
797 if (allows_const_int)
798 mode = VOIDmode;
800 /* Accept the operand, i.e. record it in `operands'. */
801 test = new_decision_test (DT_accept_op, &place);
802 test->u.opno = XINT (pattern, 0);
804 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
806 if (was_code == MATCH_OPERATOR)
808 pos_type = POS_XEXP;
809 subpos_ptr = &pos->xexps;
811 else
813 pos_type = POS_XVECEXP0;
814 subpos_ptr = &pos->xvecexp0s;
816 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
818 subpos = next_position (subpos_ptr, pos, pos_type, i);
819 sub = add_to_sequence (XVECEXP (pattern, 2, i),
820 &sub->success, subpos, insn_type, 0);
821 subpos_ptr = &subpos->next;
824 goto fini;
827 case MATCH_OP_DUP:
828 code = UNKNOWN;
830 test = new_decision_test (DT_dup, &place);
831 test->u.dup = XINT (pattern, 0);
833 test = new_decision_test (DT_accept_op, &place);
834 test->u.opno = XINT (pattern, 0);
836 subpos_ptr = &pos->xexps;
837 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
839 subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
840 sub = add_to_sequence (XVECEXP (pattern, 1, i),
841 &sub->success, subpos, insn_type, 0);
842 subpos_ptr = &subpos->next;
844 goto fini;
846 case MATCH_DUP:
847 case MATCH_PAR_DUP:
848 code = UNKNOWN;
850 test = new_decision_test (DT_dup, &place);
851 test->u.dup = XINT (pattern, 0);
852 goto fini;
854 default:
855 break;
858 fmt = GET_RTX_FORMAT (code);
859 len = GET_RTX_LENGTH (code);
861 /* Do tests against the current node first. */
862 for (i = 0; i < (size_t) len; i++)
864 if (fmt[i] == 'i')
866 gcc_assert (i < 2);
868 if (!i)
870 test = new_decision_test (DT_elt_zero_int, &place);
871 test->u.intval = XINT (pattern, i);
873 else
875 test = new_decision_test (DT_elt_one_int, &place);
876 test->u.intval = XINT (pattern, i);
879 else if (fmt[i] == 'w')
881 /* If this value actually fits in an int, we can use a switch
882 statement here, so indicate that. */
883 enum decision_type type
884 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
885 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
887 gcc_assert (!i);
889 test = new_decision_test (type, &place);
890 test->u.intval = XWINT (pattern, i);
892 else if (fmt[i] == 'E')
894 gcc_assert (!i);
896 test = new_decision_test (DT_veclen, &place);
897 test->u.veclen = XVECLEN (pattern, i);
901 /* Now test our sub-patterns. */
902 subpos_ptr = &pos->xexps;
903 for (i = 0; i < (size_t) len; i++)
905 subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
906 switch (fmt[i])
908 case 'e': case 'u':
909 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
910 subpos, insn_type, 0);
911 break;
913 case 'E':
915 struct position *subpos2, **subpos2_ptr;
916 int j;
918 subpos2_ptr = &pos->xvecexp0s;
919 for (j = 0; j < XVECLEN (pattern, i); j++)
921 subpos2 = next_position (subpos2_ptr, pos, POS_XVECEXP0, j);
922 sub = add_to_sequence (XVECEXP (pattern, i, j),
923 &sub->success, subpos2, insn_type, 0);
924 subpos2_ptr = &subpos2->next;
926 break;
929 case 'i': case 'w':
930 /* Handled above. */
931 break;
932 case '0':
933 break;
935 default:
936 gcc_unreachable ();
938 subpos_ptr = &subpos->next;
941 fini:
942 /* Insert nodes testing mode and code, if they're still relevant,
943 before any of the nodes we may have added above. */
944 if (code != UNKNOWN)
946 place = &this_decision->tests;
947 test = new_decision_test (DT_code, &place);
948 test->u.code = code;
951 if (mode != VOIDmode)
953 place = &this_decision->tests;
954 test = new_decision_test (DT_mode, &place);
955 test->u.mode = mode;
958 /* If we didn't insert any tests or accept nodes, hork. */
959 gcc_assert (this_decision->tests);
961 ret:
962 return sub;
965 /* A subroutine of maybe_both_true; examines only one test.
966 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
968 static int
969 maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
971 if (d1->type == d2->type)
973 switch (d1->type)
975 case DT_num_insns:
976 if (d1->u.num_insns == d2->u.num_insns)
977 return 1;
978 else
979 return -1;
981 case DT_mode:
982 return d1->u.mode == d2->u.mode;
984 case DT_code:
985 return d1->u.code == d2->u.code;
987 case DT_veclen:
988 return d1->u.veclen == d2->u.veclen;
990 case DT_elt_zero_int:
991 case DT_elt_one_int:
992 case DT_elt_zero_wide:
993 case DT_elt_zero_wide_safe:
994 return d1->u.intval == d2->u.intval;
996 default:
997 break;
1001 /* If either has a predicate that we know something about, set
1002 things up so that D1 is the one that always has a known
1003 predicate. Then see if they have any codes in common. */
1005 if (d1->type == DT_pred || d2->type == DT_pred)
1007 if (d2->type == DT_pred)
1009 struct decision_test *tmp;
1010 tmp = d1, d1 = d2, d2 = tmp;
1013 /* If D2 tests a mode, see if it matches D1. */
1014 if (d1->u.pred.mode != VOIDmode)
1016 if (d2->type == DT_mode)
1018 if (d1->u.pred.mode != d2->u.mode
1019 /* The mode of an address_operand predicate is the
1020 mode of the memory, not the operand. It can only
1021 be used for testing the predicate, so we must
1022 ignore it here. */
1023 && strcmp (d1->u.pred.name, "address_operand") != 0)
1024 return 0;
1026 /* Don't check two predicate modes here, because if both predicates
1027 accept CONST_INT, then both can still be true even if the modes
1028 are different. If they don't accept CONST_INT, there will be a
1029 separate DT_mode that will make maybe_both_true_1 return 0. */
1032 if (d1->u.pred.data)
1034 /* If D2 tests a code, see if it is in the list of valid
1035 codes for D1's predicate. */
1036 if (d2->type == DT_code)
1038 if (!d1->u.pred.data->codes[d2->u.code])
1039 return 0;
1042 /* Otherwise see if the predicates have any codes in common. */
1043 else if (d2->type == DT_pred && d2->u.pred.data)
1045 bool common = false;
1046 int c;
1048 for (c = 0; c < NUM_RTX_CODE; c++)
1049 if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c])
1051 common = true;
1052 break;
1055 if (!common)
1056 return 0;
1061 /* Tests vs veclen may be known when strict equality is involved. */
1062 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1063 return d1->u.veclen >= d2->u.veclen;
1064 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1065 return d2->u.veclen >= d1->u.veclen;
1067 return -1;
1070 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1071 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1073 static int
1074 maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
1076 struct decision_test *t1, *t2;
1078 /* A match_operand with no predicate can match anything. Recognize
1079 this by the existence of a lone DT_accept_op test. */
1080 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1081 return 1;
1083 /* Eliminate pairs of tests while they can exactly match. */
1084 while (d1 && d2 && d1->type == d2->type)
1086 if (maybe_both_true_2 (d1, d2) == 0)
1087 return 0;
1088 d1 = d1->next, d2 = d2->next;
1091 /* After that, consider all pairs. */
1092 for (t1 = d1; t1 ; t1 = t1->next)
1093 for (t2 = d2; t2 ; t2 = t2->next)
1094 if (maybe_both_true_2 (t1, t2) == 0)
1095 return 0;
1097 return -1;
1100 /* Return 0 if we can prove that there is no RTL that can match both
1101 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1102 can match both or just that we couldn't prove there wasn't such an RTL).
1104 TOPLEVEL is nonzero if we are to only look at the top level and not
1105 recursively descend. */
1107 static int
1108 maybe_both_true (struct decision *d1, struct decision *d2,
1109 int toplevel)
1111 struct decision *p1, *p2;
1112 int cmp;
1114 /* Don't compare strings on the different positions in insn. Doing so
1115 is incorrect and results in false matches from constructs like
1117 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1118 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1120 [(set (match_operand:HI "register_operand" "r")
1121 (match_operand:HI "register_operand" "r"))]
1123 If we are presented with such, we are recursing through the remainder
1124 of a node's success nodes (from the loop at the end of this function).
1125 Skip forward until we come to a position that matches.
1127 Due to the way positions are constructed, we know that iterating
1128 forward from the lexically lower position will run into the lexically
1129 higher position and not the other way around. This saves a bit
1130 of effort. */
1132 cmp = compare_positions (d1->position, d2->position);
1133 if (cmp != 0)
1135 gcc_assert (!toplevel);
1137 /* If the d2->position was lexically lower, swap. */
1138 if (cmp > 0)
1139 p1 = d1, d1 = d2, d2 = p1;
1141 if (d1->success.first == 0)
1142 return 1;
1143 for (p1 = d1->success.first; p1; p1 = p1->next)
1144 if (maybe_both_true (p1, d2, 0))
1145 return 1;
1147 return 0;
1150 /* Test the current level. */
1151 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1152 if (cmp >= 0)
1153 return cmp;
1155 /* We can't prove that D1 and D2 cannot both be true. If we are only
1156 to check the top level, return 1. Otherwise, see if we can prove
1157 that all choices in both successors are mutually exclusive. If
1158 either does not have any successors, we can't prove they can't both
1159 be true. */
1161 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1162 return 1;
1164 for (p1 = d1->success.first; p1; p1 = p1->next)
1165 for (p2 = d2->success.first; p2; p2 = p2->next)
1166 if (maybe_both_true (p1, p2, 0))
1167 return 1;
1169 return 0;
1172 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1174 static int
1175 nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
1177 switch (d1->type)
1179 case DT_num_insns:
1180 return d1->u.num_insns == d2->u.num_insns;
1182 case DT_mode:
1183 return d1->u.mode == d2->u.mode;
1185 case DT_code:
1186 return d1->u.code == d2->u.code;
1188 case DT_pred:
1189 return (d1->u.pred.mode == d2->u.pred.mode
1190 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1192 case DT_c_test:
1193 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1195 case DT_veclen:
1196 case DT_veclen_ge:
1197 return d1->u.veclen == d2->u.veclen;
1199 case DT_dup:
1200 return d1->u.dup == d2->u.dup;
1202 case DT_elt_zero_int:
1203 case DT_elt_one_int:
1204 case DT_elt_zero_wide:
1205 case DT_elt_zero_wide_safe:
1206 return d1->u.intval == d2->u.intval;
1208 case DT_accept_op:
1209 return d1->u.opno == d2->u.opno;
1211 case DT_accept_insn:
1212 /* Differences will be handled in merge_accept_insn. */
1213 return 1;
1215 default:
1216 gcc_unreachable ();
1220 /* True iff the two nodes are identical (on one level only). Due
1221 to the way these lists are constructed, we shouldn't have to
1222 consider different orderings on the tests. */
1224 static int
1225 nodes_identical (struct decision *d1, struct decision *d2)
1227 struct decision_test *t1, *t2;
1229 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1231 if (t1->type != t2->type)
1232 return 0;
1233 if (! nodes_identical_1 (t1, t2))
1234 return 0;
1237 /* For success, they should now both be null. */
1238 if (t1 != t2)
1239 return 0;
1241 /* Check that their subnodes are at the same position, as any one set
1242 of sibling decisions must be at the same position. Allowing this
1243 requires complications to find_afterward and when change_state is
1244 invoked. */
1245 if (d1->success.first
1246 && d2->success.first
1247 && d1->success.first->position != d2->success.first->position)
1248 return 0;
1250 return 1;
1253 /* A subroutine of merge_trees; given two nodes that have been declared
1254 identical, cope with two insn accept states. If they differ in the
1255 number of clobbers, then the conflict was created by make_insn_sequence
1256 and we can drop the with-clobbers version on the floor. If both
1257 nodes have no additional clobbers, we have found an ambiguity in the
1258 source machine description. */
1260 static void
1261 merge_accept_insn (struct decision *oldd, struct decision *addd)
1263 struct decision_test *old, *add;
1265 for (old = oldd->tests; old; old = old->next)
1266 if (old->type == DT_accept_insn)
1267 break;
1268 if (old == NULL)
1269 return;
1271 for (add = addd->tests; add; add = add->next)
1272 if (add->type == DT_accept_insn)
1273 break;
1274 if (add == NULL)
1275 return;
1277 /* If one node is for a normal insn and the second is for the base
1278 insn with clobbers stripped off, the second node should be ignored. */
1280 if (old->u.insn.num_clobbers_to_add == 0
1281 && add->u.insn.num_clobbers_to_add > 0)
1283 /* Nothing to do here. */
1285 else if (old->u.insn.num_clobbers_to_add > 0
1286 && add->u.insn.num_clobbers_to_add == 0)
1288 /* In this case, replace OLD with ADD. */
1289 old->u.insn = add->u.insn;
1291 else
1293 error_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1294 get_insn_name (add->u.insn.code_number),
1295 get_insn_name (old->u.insn.code_number));
1296 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1297 get_insn_name (old->u.insn.code_number));
1301 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1303 static void
1304 merge_trees (struct decision_head *oldh, struct decision_head *addh)
1306 struct decision *next, *add;
1308 if (addh->first == 0)
1309 return;
1310 if (oldh->first == 0)
1312 *oldh = *addh;
1313 return;
1316 /* Trying to merge bits at different positions isn't possible. */
1317 gcc_assert (oldh->first->position == addh->first->position);
1319 for (add = addh->first; add ; add = next)
1321 struct decision *old, *insert_before = NULL;
1323 next = add->next;
1325 /* The semantics of pattern matching state that the tests are
1326 done in the order given in the MD file so that if an insn
1327 matches two patterns, the first one will be used. However,
1328 in practice, most, if not all, patterns are unambiguous so
1329 that their order is independent. In that case, we can merge
1330 identical tests and group all similar modes and codes together.
1332 Scan starting from the end of OLDH until we reach a point
1333 where we reach the head of the list or where we pass a
1334 pattern that could also be true if NEW is true. If we find
1335 an identical pattern, we can merge them. Also, record the
1336 last node that tests the same code and mode and the last one
1337 that tests just the same mode.
1339 If we have no match, place NEW after the closest match we found. */
1341 for (old = oldh->last; old; old = old->prev)
1343 if (nodes_identical (old, add))
1345 merge_accept_insn (old, add);
1346 merge_trees (&old->success, &add->success);
1347 goto merged_nodes;
1350 if (maybe_both_true (old, add, 0))
1351 break;
1353 /* Insert the nodes in DT test type order, which is roughly
1354 how expensive/important the test is. Given that the tests
1355 are also ordered within the list, examining the first is
1356 sufficient. */
1357 if ((int) add->tests->type < (int) old->tests->type)
1358 insert_before = old;
1361 if (insert_before == NULL)
1363 add->next = NULL;
1364 add->prev = oldh->last;
1365 oldh->last->next = add;
1366 oldh->last = add;
1368 else
1370 if ((add->prev = insert_before->prev) != NULL)
1371 add->prev->next = add;
1372 else
1373 oldh->first = add;
1374 add->next = insert_before;
1375 insert_before->prev = add;
1378 merged_nodes:;
1382 /* Walk the tree looking for sub-nodes that perform common tests.
1383 Factor out the common test into a new node. This enables us
1384 (depending on the test type) to emit switch statements later. */
1386 static void
1387 factor_tests (struct decision_head *head)
1389 struct decision *first, *next;
1391 for (first = head->first; first && first->next; first = next)
1393 enum decision_type type;
1394 struct decision *new_dec, *old_last;
1396 type = first->tests->type;
1397 next = first->next;
1399 /* Want at least two compatible sequential nodes. */
1400 if (next->tests->type != type)
1401 continue;
1403 /* Don't want all node types, just those we can turn into
1404 switch statements. */
1405 if (type != DT_mode
1406 && type != DT_code
1407 && type != DT_veclen
1408 && type != DT_elt_zero_int
1409 && type != DT_elt_one_int
1410 && type != DT_elt_zero_wide_safe)
1411 continue;
1413 /* If we'd been performing more than one test, create a new node
1414 below our first test. */
1415 if (first->tests->next != NULL)
1417 new_dec = new_decision (first->position, &first->success);
1418 new_dec->tests = first->tests->next;
1419 first->tests->next = NULL;
1422 /* Crop the node tree off after our first test. */
1423 first->next = NULL;
1424 old_last = head->last;
1425 head->last = first;
1427 /* For each compatible test, adjust to perform only one test in
1428 the top level node, then merge the node back into the tree. */
1431 struct decision_head h;
1433 if (next->tests->next != NULL)
1435 new_dec = new_decision (next->position, &next->success);
1436 new_dec->tests = next->tests->next;
1437 next->tests->next = NULL;
1439 new_dec = next;
1440 next = next->next;
1441 new_dec->next = NULL;
1442 h.first = h.last = new_dec;
1444 merge_trees (head, &h);
1446 while (next && next->tests->type == type);
1448 /* After we run out of compatible tests, graft the remaining nodes
1449 back onto the tree. */
1450 if (next)
1452 next->prev = head->last;
1453 head->last->next = next;
1454 head->last = old_last;
1458 /* Recurse. */
1459 for (first = head->first; first; first = first->next)
1460 factor_tests (&first->success);
1463 /* After factoring, try to simplify the tests on any one node.
1464 Tests that are useful for switch statements are recognizable
1465 by having only a single test on a node -- we'll be manipulating
1466 nodes with multiple tests:
1468 If we have mode tests or code tests that are redundant with
1469 predicates, remove them. */
1471 static void
1472 simplify_tests (struct decision_head *head)
1474 struct decision *tree;
1476 for (tree = head->first; tree; tree = tree->next)
1478 struct decision_test *a, *b;
1480 a = tree->tests;
1481 b = a->next;
1482 if (b == NULL)
1483 continue;
1485 /* Find a predicate node. */
1486 while (b && b->type != DT_pred)
1487 b = b->next;
1488 if (b)
1490 /* Due to how these tests are constructed, we don't even need
1491 to check that the mode and code are compatible -- they were
1492 generated from the predicate in the first place. */
1493 while (a->type == DT_mode || a->type == DT_code)
1494 a = a->next;
1495 tree->tests = a;
1499 /* Recurse. */
1500 for (tree = head->first; tree; tree = tree->next)
1501 simplify_tests (&tree->success);
1504 /* Count the number of subnodes of HEAD. If the number is high enough,
1505 make the first node in HEAD start a separate subroutine in the C code
1506 that is generated. */
1508 static int
1509 break_out_subroutines (struct decision_head *head, int initial)
1511 int size = 0;
1512 struct decision *sub;
1514 for (sub = head->first; sub; sub = sub->next)
1515 size += 1 + break_out_subroutines (&sub->success, 0);
1517 if (size > SUBROUTINE_THRESHOLD && ! initial)
1519 head->first->subroutine_number = ++next_subroutine_number;
1520 size = 1;
1522 return size;
1525 /* For each node p, find the next alternative that might be true
1526 when p is true. */
1528 static void
1529 find_afterward (struct decision_head *head, struct decision *real_afterward)
1531 struct decision *p, *q, *afterward;
1533 /* We can't propagate alternatives across subroutine boundaries.
1534 This is not incorrect, merely a minor optimization loss. */
1536 p = head->first;
1537 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1539 for ( ; p ; p = p->next)
1541 /* Find the next node that might be true if this one fails. */
1542 for (q = p->next; q ; q = q->next)
1543 if (maybe_both_true (p, q, 1))
1544 break;
1546 /* If we reached the end of the list without finding one,
1547 use the incoming afterward position. */
1548 if (!q)
1549 q = afterward;
1550 p->afterward = q;
1551 if (q)
1552 q->need_label = 1;
1555 /* Recurse. */
1556 for (p = head->first; p ; p = p->next)
1557 if (p->success.first)
1558 find_afterward (&p->success, p->afterward);
1560 /* When we are generating a subroutine, record the real afterward
1561 position in the first node where write_tree can find it, and we
1562 can do the right thing at the subroutine call site. */
1563 p = head->first;
1564 if (p->subroutine_number > 0)
1565 p->afterward = real_afterward;
1568 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1569 actions are necessary to move to NEWPOS. If we fail to move to the
1570 new state, branch to node AFTERWARD if nonzero, otherwise return.
1572 Failure to move to the new state can only occur if we are trying to
1573 match multiple insns and we try to step past the end of the stream. */
1575 static void
1576 change_state (struct position *oldpos, struct position *newpos,
1577 const char *indent)
1579 while (oldpos->depth > newpos->depth)
1580 oldpos = oldpos->base;
1582 if (oldpos != newpos)
1583 switch (newpos->type)
1585 case POS_PEEP2_INSN:
1586 printf ("%stem = peep2_next_insn (%d);\n", indent, newpos->arg);
1587 printf ("%sx%d = PATTERN (tem);\n", indent, newpos->depth);
1588 break;
1590 case POS_XEXP:
1591 change_state (oldpos, newpos->base, indent);
1592 printf ("%sx%d = XEXP (x%d, %d);\n",
1593 indent, newpos->depth, newpos->depth - 1, newpos->arg);
1594 break;
1596 case POS_XVECEXP0:
1597 change_state (oldpos, newpos->base, indent);
1598 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1599 indent, newpos->depth, newpos->depth - 1, newpos->arg);
1600 break;
1604 /* Print the enumerator constant for CODE -- the upcase version of
1605 the name. */
1607 static void
1608 print_code (enum rtx_code code)
1610 const char *p;
1611 for (p = GET_RTX_NAME (code); *p; p++)
1612 putchar (TOUPPER (*p));
1615 /* Emit code to cross an afterward link -- change state and branch. */
1617 static void
1618 write_afterward (struct decision *start, struct decision *afterward,
1619 const char *indent)
1621 if (!afterward || start->subroutine_number > 0)
1622 printf ("%sgoto ret0;\n", indent);
1623 else
1625 change_state (start->position, afterward->position, indent);
1626 printf ("%sgoto L%d;\n", indent, afterward->number);
1630 /* Emit a HOST_WIDE_INT as an integer constant expression. We need to take
1631 special care to avoid "decimal constant is so large that it is unsigned"
1632 warnings in the resulting code. */
1634 static void
1635 print_host_wide_int (HOST_WIDE_INT val)
1637 HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
1638 if (val == min)
1639 printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
1640 else
1641 printf (HOST_WIDE_INT_PRINT_DEC_C, val);
1644 /* Emit a switch statement, if possible, for an initial sequence of
1645 nodes at START. Return the first node yet untested. */
1647 static struct decision *
1648 write_switch (struct decision *start, int depth)
1650 struct decision *p = start;
1651 enum decision_type type = p->tests->type;
1652 struct decision *needs_label = NULL;
1654 /* If we have two or more nodes in sequence that test the same one
1655 thing, we may be able to use a switch statement. */
1657 if (!p->next
1658 || p->tests->next
1659 || p->next->tests->type != type
1660 || p->next->tests->next
1661 || nodes_identical_1 (p->tests, p->next->tests))
1662 return p;
1664 /* DT_code is special in that we can do interesting things with
1665 known predicates at the same time. */
1666 if (type == DT_code)
1668 char codemap[NUM_RTX_CODE];
1669 struct decision *ret;
1670 RTX_CODE code;
1672 memset (codemap, 0, sizeof (codemap));
1674 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1675 code = p->tests->u.code;
1678 if (p != start && p->need_label && needs_label == NULL)
1679 needs_label = p;
1681 printf (" case ");
1682 print_code (code);
1683 printf (":\n goto L%d;\n", p->success.first->number);
1684 p->success.first->need_label = 1;
1686 codemap[code] = 1;
1687 p = p->next;
1689 while (p
1690 && ! p->tests->next
1691 && p->tests->type == DT_code
1692 && ! codemap[code = p->tests->u.code]);
1694 /* If P is testing a predicate that we know about and we haven't
1695 seen any of the codes that are valid for the predicate, we can
1696 write a series of "case" statement, one for each possible code.
1697 Since we are already in a switch, these redundant tests are very
1698 cheap and will reduce the number of predicates called. */
1700 /* Note that while we write out cases for these predicates here,
1701 we don't actually write the test here, as it gets kinda messy.
1702 It is trivial to leave this to later by telling our caller that
1703 we only processed the CODE tests. */
1704 if (needs_label != NULL)
1705 ret = needs_label;
1706 else
1707 ret = p;
1709 while (p && p->tests->type == DT_pred && p->tests->u.pred.data)
1711 const struct pred_data *data = p->tests->u.pred.data;
1712 int c;
1714 for (c = 0; c < NUM_RTX_CODE; c++)
1715 if (codemap[c] && data->codes[c])
1716 goto pred_done;
1718 for (c = 0; c < NUM_RTX_CODE; c++)
1719 if (data->codes[c])
1721 fputs (" case ", stdout);
1722 print_code ((enum rtx_code) c);
1723 fputs (":\n", stdout);
1724 codemap[c] = 1;
1727 printf (" goto L%d;\n", p->number);
1728 p->need_label = 1;
1729 p = p->next;
1732 pred_done:
1733 /* Make the default case skip the predicates we managed to match. */
1735 printf (" default:\n");
1736 if (p != ret)
1738 if (p)
1740 printf (" goto L%d;\n", p->number);
1741 p->need_label = 1;
1743 else
1744 write_afterward (start, start->afterward, " ");
1746 else
1747 printf (" break;\n");
1748 printf (" }\n");
1750 return ret;
1752 else if (type == DT_mode
1753 || type == DT_veclen
1754 || type == DT_elt_zero_int
1755 || type == DT_elt_one_int
1756 || type == DT_elt_zero_wide_safe)
1758 const char *indent = "";
1760 /* We cast switch parameter to integer, so we must ensure that the value
1761 fits. */
1762 if (type == DT_elt_zero_wide_safe)
1764 indent = " ";
1765 printf (" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n",
1766 depth, depth);
1768 printf ("%s switch (", indent);
1769 switch (type)
1771 case DT_mode:
1772 printf ("GET_MODE (x%d)", depth);
1773 break;
1774 case DT_veclen:
1775 printf ("XVECLEN (x%d, 0)", depth);
1776 break;
1777 case DT_elt_zero_int:
1778 printf ("XINT (x%d, 0)", depth);
1779 break;
1780 case DT_elt_one_int:
1781 printf ("XINT (x%d, 1)", depth);
1782 break;
1783 case DT_elt_zero_wide_safe:
1784 /* Convert result of XWINT to int for portability since some C
1785 compilers won't do it and some will. */
1786 printf ("(int) XWINT (x%d, 0)", depth);
1787 break;
1788 default:
1789 gcc_unreachable ();
1791 printf (")\n%s {\n", indent);
1795 /* Merge trees will not unify identical nodes if their
1796 sub-nodes are at different levels. Thus we must check
1797 for duplicate cases. */
1798 struct decision *q;
1799 for (q = start; q != p; q = q->next)
1800 if (nodes_identical_1 (p->tests, q->tests))
1801 goto case_done;
1803 if (p != start && p->need_label && needs_label == NULL)
1804 needs_label = p;
1806 printf ("%s case ", indent);
1807 switch (type)
1809 case DT_mode:
1810 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1811 break;
1812 case DT_veclen:
1813 printf ("%d", p->tests->u.veclen);
1814 break;
1815 case DT_elt_zero_int:
1816 case DT_elt_one_int:
1817 case DT_elt_zero_wide:
1818 case DT_elt_zero_wide_safe:
1819 print_host_wide_int (p->tests->u.intval);
1820 break;
1821 default:
1822 gcc_unreachable ();
1824 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1825 p->success.first->need_label = 1;
1827 p = p->next;
1829 while (p && p->tests->type == type && !p->tests->next);
1831 case_done:
1832 printf ("%s default:\n%s break;\n%s }\n",
1833 indent, indent, indent);
1835 return needs_label != NULL ? needs_label : p;
1837 else
1839 /* None of the other tests are amenable. */
1840 return p;
1844 /* Emit code for one test. */
1846 static void
1847 write_cond (struct decision_test *p, int depth,
1848 enum routine_type subroutine_type)
1850 switch (p->type)
1852 case DT_num_insns:
1853 printf ("peep2_current_count >= %d", p->u.num_insns);
1854 break;
1856 case DT_mode:
1857 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1858 break;
1860 case DT_code:
1861 printf ("GET_CODE (x%d) == ", depth);
1862 print_code (p->u.code);
1863 break;
1865 case DT_veclen:
1866 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1867 break;
1869 case DT_elt_zero_int:
1870 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1871 break;
1873 case DT_elt_one_int:
1874 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1875 break;
1877 case DT_elt_zero_wide:
1878 case DT_elt_zero_wide_safe:
1879 printf ("XWINT (x%d, 0) == ", depth);
1880 print_host_wide_int (p->u.intval);
1881 break;
1883 case DT_const_int:
1884 printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
1885 depth, (int) p->u.intval);
1886 break;
1888 case DT_veclen_ge:
1889 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
1890 break;
1892 case DT_dup:
1893 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1894 break;
1896 case DT_pred:
1897 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1898 GET_MODE_NAME (p->u.pred.mode));
1899 break;
1901 case DT_c_test:
1902 print_c_condition (p->u.c_test);
1903 break;
1905 case DT_accept_insn:
1906 gcc_assert (subroutine_type == RECOG);
1907 gcc_assert (p->u.insn.num_clobbers_to_add);
1908 printf ("pnum_clobbers != NULL");
1909 break;
1911 default:
1912 gcc_unreachable ();
1916 /* Emit code for one action. The previous tests have succeeded;
1917 TEST is the last of the chain. In the normal case we simply
1918 perform a state change. For the `accept' tests we must do more work. */
1920 static void
1921 write_action (struct decision *p, struct decision_test *test,
1922 int depth, int uncond, struct decision *success,
1923 enum routine_type subroutine_type)
1925 const char *indent;
1926 int want_close = 0;
1928 if (uncond)
1929 indent = " ";
1930 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1932 fputs (" {\n", stdout);
1933 indent = " ";
1934 want_close = 1;
1936 else
1937 indent = " ";
1939 if (test->type == DT_accept_op)
1941 printf ("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1943 /* Only allow DT_accept_insn to follow. */
1944 if (test->next)
1946 test = test->next;
1947 gcc_assert (test->type == DT_accept_insn);
1951 /* Sanity check that we're now at the end of the list of tests. */
1952 gcc_assert (!test->next);
1954 if (test->type == DT_accept_insn)
1956 switch (subroutine_type)
1958 case RECOG:
1959 if (test->u.insn.num_clobbers_to_add != 0)
1960 printf ("%s*pnum_clobbers = %d;\n",
1961 indent, test->u.insn.num_clobbers_to_add);
1962 printf ("%sreturn %d; /* %s */\n", indent,
1963 test->u.insn.code_number,
1964 get_insn_name (test->u.insn.code_number));
1965 break;
1967 case SPLIT:
1968 printf ("%sreturn gen_split_%d (insn, operands);\n",
1969 indent, test->u.insn.code_number);
1970 break;
1972 case PEEPHOLE2:
1974 int match_len = 0;
1975 struct position *pos;
1977 for (pos = p->position; pos; pos = pos->base)
1978 if (pos->type == POS_PEEP2_INSN)
1980 match_len = pos->arg;
1981 break;
1983 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
1984 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1985 indent, test->u.insn.code_number);
1986 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
1988 break;
1990 default:
1991 gcc_unreachable ();
1994 else
1996 printf ("%sgoto L%d;\n", indent, success->number);
1997 success->need_label = 1;
2000 if (want_close)
2001 fputs (" }\n", stdout);
2004 /* Return 1 if the test is always true and has no fallthru path. Return -1
2005 if the test does have a fallthru path, but requires that the condition be
2006 terminated. Otherwise return 0 for a normal test. */
2007 /* ??? is_unconditional is a stupid name for a tri-state function. */
2009 static int
2010 is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
2012 if (t->type == DT_accept_op)
2013 return 1;
2015 if (t->type == DT_accept_insn)
2017 switch (subroutine_type)
2019 case RECOG:
2020 return (t->u.insn.num_clobbers_to_add == 0);
2021 case SPLIT:
2022 return 1;
2023 case PEEPHOLE2:
2024 return -1;
2025 default:
2026 gcc_unreachable ();
2030 return 0;
2033 /* Emit code for one node -- the conditional and the accompanying action.
2034 Return true if there is no fallthru path. */
2036 static int
2037 write_node (struct decision *p, int depth,
2038 enum routine_type subroutine_type)
2040 struct decision_test *test, *last_test;
2041 int uncond;
2043 /* Scan the tests and simplify comparisons against small
2044 constants. */
2045 for (test = p->tests; test; test = test->next)
2047 if (test->type == DT_code
2048 && test->u.code == CONST_INT
2049 && test->next
2050 && test->next->type == DT_elt_zero_wide_safe
2051 && -MAX_SAVED_CONST_INT <= test->next->u.intval
2052 && test->next->u.intval <= MAX_SAVED_CONST_INT)
2054 test->type = DT_const_int;
2055 test->u.intval = test->next->u.intval;
2056 test->next = test->next->next;
2060 last_test = test = p->tests;
2061 uncond = is_unconditional (test, subroutine_type);
2062 if (uncond == 0)
2064 printf (" if (");
2065 write_cond (test, depth, subroutine_type);
2067 while ((test = test->next) != NULL)
2069 last_test = test;
2070 if (is_unconditional (test, subroutine_type))
2071 break;
2073 printf ("\n && ");
2074 write_cond (test, depth, subroutine_type);
2077 printf (")\n");
2080 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2082 return uncond > 0;
2085 /* Emit code for all of the sibling nodes of HEAD. */
2087 static void
2088 write_tree_1 (struct decision_head *head, int depth,
2089 enum routine_type subroutine_type)
2091 struct decision *p, *next;
2092 int uncond = 0;
2094 for (p = head->first; p ; p = next)
2096 /* The label for the first element was printed in write_tree. */
2097 if (p != head->first && p->need_label)
2098 OUTPUT_LABEL (" ", p->number);
2100 /* Attempt to write a switch statement for a whole sequence. */
2101 next = write_switch (p, depth);
2102 if (p != next)
2103 uncond = 0;
2104 else
2106 /* Failed -- fall back and write one node. */
2107 uncond = write_node (p, depth, subroutine_type);
2108 next = p->next;
2112 /* Finished with this chain. Close a fallthru path by branching
2113 to the afterward node. */
2114 if (! uncond)
2115 write_afterward (head->last, head->last->afterward, " ");
2118 /* Write out the decision tree starting at HEAD. PREVPOS is the
2119 position at the node that branched to this node. */
2121 static void
2122 write_tree (struct decision_head *head, struct position *prevpos,
2123 enum routine_type type, int initial)
2125 struct decision *p = head->first;
2127 putchar ('\n');
2128 if (p->need_label)
2129 OUTPUT_LABEL (" ", p->number);
2131 if (! initial && p->subroutine_number > 0)
2133 static const char * const name_prefix[] = {
2134 "recog", "split", "peephole2"
2137 static const char * const call_suffix[] = {
2138 ", pnum_clobbers", "", ", _pmatch_len"
2141 /* This node has been broken out into a separate subroutine.
2142 Call it, test the result, and branch accordingly. */
2144 if (p->afterward)
2146 printf (" tem = %s_%d (x0, insn%s);\n",
2147 name_prefix[type], p->subroutine_number, call_suffix[type]);
2148 if (IS_SPLIT (type))
2149 printf (" if (tem != 0)\n return tem;\n");
2150 else
2151 printf (" if (tem >= 0)\n return tem;\n");
2153 change_state (p->position, p->afterward->position, " ");
2154 printf (" goto L%d;\n", p->afterward->number);
2156 else
2158 printf (" return %s_%d (x0, insn%s);\n",
2159 name_prefix[type], p->subroutine_number, call_suffix[type]);
2162 else
2164 change_state (prevpos, p->position, " ");
2165 write_tree_1 (head, p->position->depth, type);
2167 for (p = head->first; p; p = p->next)
2168 if (p->success.first)
2169 write_tree (&p->success, p->position, type, 0);
2173 /* Write out a subroutine of type TYPE to do comparisons starting at
2174 node TREE. */
2176 static void
2177 write_subroutine (struct decision_head *head, enum routine_type type)
2179 int subfunction = head->first ? head->first->subroutine_number : 0;
2180 const char *s_or_e;
2181 char extension[32];
2182 int i;
2184 s_or_e = subfunction ? "static " : "";
2186 if (subfunction)
2187 sprintf (extension, "_%d", subfunction);
2188 else if (type == RECOG)
2189 extension[0] = '\0';
2190 else
2191 strcpy (extension, "_insns");
2193 switch (type)
2195 case RECOG:
2196 printf ("%sint\n\
2197 recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
2198 break;
2199 case SPLIT:
2200 printf ("%srtx\n\
2201 split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
2202 s_or_e, extension);
2203 break;
2204 case PEEPHOLE2:
2205 printf ("%srtx\n\
2206 peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
2207 s_or_e, extension);
2208 break;
2211 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2212 for (i = 1; i <= max_depth; i++)
2213 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2215 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2217 if (!subfunction)
2218 printf (" recog_data.insn = NULL_RTX;\n");
2220 if (head->first)
2221 write_tree (head, &root_pos, type, 1);
2222 else
2223 printf (" goto ret0;\n");
2225 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2228 /* In break_out_subroutines, we discovered the boundaries for the
2229 subroutines, but did not write them out. Do so now. */
2231 static void
2232 write_subroutines (struct decision_head *head, enum routine_type type)
2234 struct decision *p;
2236 for (p = head->first; p ; p = p->next)
2237 if (p->success.first)
2238 write_subroutines (&p->success, type);
2240 if (head->first->subroutine_number > 0)
2241 write_subroutine (head, type);
2244 /* Begin the output file. */
2246 static void
2247 write_header (void)
2249 puts ("\
2250 /* Generated automatically by the program `genrecog' from the target\n\
2251 machine description file. */\n\
2253 #include \"config.h\"\n\
2254 #include \"system.h\"\n\
2255 #include \"coretypes.h\"\n\
2256 #include \"tm.h\"\n\
2257 #include \"rtl.h\"\n\
2258 #include \"tm_p.h\"\n\
2259 #include \"function.h\"\n\
2260 #include \"insn-config.h\"\n\
2261 #include \"recog.h\"\n\
2262 #include \"output.h\"\n\
2263 #include \"flags.h\"\n\
2264 #include \"hard-reg-set.h\"\n\
2265 #include \"resource.h\"\n\
2266 #include \"diagnostic-core.h\"\n\
2267 #include \"reload.h\"\n\
2268 #include \"regs.h\"\n\
2269 #include \"tm-constrs.h\"\n\
2270 \n");
2272 puts ("\n\
2273 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2274 X0 is a valid instruction.\n\
2276 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2277 returns a nonnegative number which is the insn code number for the\n\
2278 pattern that matched. This is the same as the order in the machine\n\
2279 description of the entry that matched. This number can be used as an\n\
2280 index into `insn_data' and other tables.\n");
2281 puts ("\
2282 The third argument to recog is an optional pointer to an int. If\n\
2283 present, recog will accept a pattern if it matches except for missing\n\
2284 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2285 the optional pointer will be set to the number of CLOBBERs that need\n\
2286 to be added (it should be initialized to zero by the caller). If it");
2287 puts ("\
2288 is set nonzero, the caller should allocate a PARALLEL of the\n\
2289 appropriate size, copy the initial entries, and call add_clobbers\n\
2290 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2293 puts ("\n\
2294 The function split_insns returns 0 if the rtl could not\n\
2295 be split or the split rtl as an INSN list if it can be.\n\
2297 The function peephole2_insns returns 0 if the rtl could not\n\
2298 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2299 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2300 */\n\n");
2304 /* Construct and return a sequence of decisions
2305 that will recognize INSN.
2307 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2309 static struct decision_head
2310 make_insn_sequence (rtx insn, enum routine_type type)
2312 rtx x;
2313 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2314 int truth = maybe_eval_c_test (c_test);
2315 struct decision *last;
2316 struct decision_test *test, **place;
2317 struct decision_head head;
2318 struct position *c_test_pos, **pos_ptr;
2320 /* We should never see an insn whose C test is false at compile time. */
2321 gcc_assert (truth);
2323 c_test_pos = &root_pos;
2324 if (type == PEEPHOLE2)
2326 int i, j;
2328 /* peephole2 gets special treatment:
2329 - X always gets an outer parallel even if it's only one entry
2330 - we remove all traces of outer-level match_scratch and match_dup
2331 expressions here. */
2332 x = rtx_alloc (PARALLEL);
2333 PUT_MODE (x, VOIDmode);
2334 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2335 pos_ptr = &peep2_insn_pos_list;
2336 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2338 rtx tmp = XVECEXP (insn, 0, i);
2339 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2341 c_test_pos = next_position (pos_ptr, &root_pos,
2342 POS_PEEP2_INSN, j);
2343 XVECEXP (x, 0, j) = tmp;
2344 j++;
2345 pos_ptr = &c_test_pos->next;
2348 XVECLEN (x, 0) = j;
2350 else if (XVECLEN (insn, type == RECOG) == 1)
2351 x = XVECEXP (insn, type == RECOG, 0);
2352 else
2354 x = rtx_alloc (PARALLEL);
2355 XVEC (x, 0) = XVEC (insn, type == RECOG);
2356 PUT_MODE (x, VOIDmode);
2359 validate_pattern (x, insn, NULL_RTX, 0);
2361 memset (&head, 0, sizeof (head));
2362 last = add_to_sequence (x, &head, &root_pos, type, 1);
2364 /* Find the end of the test chain on the last node. */
2365 for (test = last->tests; test->next; test = test->next)
2366 continue;
2367 place = &test->next;
2369 /* Skip the C test if it's known to be true at compile time. */
2370 if (truth == -1)
2372 /* Need a new node if we have another test to add. */
2373 if (test->type == DT_accept_op)
2375 last = new_decision (c_test_pos, &last->success);
2376 place = &last->tests;
2378 test = new_decision_test (DT_c_test, &place);
2379 test->u.c_test = c_test;
2382 test = new_decision_test (DT_accept_insn, &place);
2383 test->u.insn.code_number = next_insn_code;
2384 test->u.insn.lineno = pattern_lineno;
2385 test->u.insn.num_clobbers_to_add = 0;
2387 switch (type)
2389 case RECOG:
2390 /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
2391 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2392 If so, set up to recognize the pattern without these CLOBBERs. */
2394 if (GET_CODE (x) == PARALLEL)
2396 int i;
2398 /* Find the last non-clobber in the parallel. */
2399 for (i = XVECLEN (x, 0); i > 0; i--)
2401 rtx y = XVECEXP (x, 0, i - 1);
2402 if (GET_CODE (y) != CLOBBER
2403 || (!REG_P (XEXP (y, 0))
2404 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2405 break;
2408 if (i != XVECLEN (x, 0))
2410 rtx new_rtx;
2411 struct decision_head clobber_head;
2413 /* Build a similar insn without the clobbers. */
2414 if (i == 1)
2415 new_rtx = XVECEXP (x, 0, 0);
2416 else
2418 int j;
2420 new_rtx = rtx_alloc (PARALLEL);
2421 XVEC (new_rtx, 0) = rtvec_alloc (i);
2422 for (j = i - 1; j >= 0; j--)
2423 XVECEXP (new_rtx, 0, j) = XVECEXP (x, 0, j);
2426 /* Recognize it. */
2427 memset (&clobber_head, 0, sizeof (clobber_head));
2428 last = add_to_sequence (new_rtx, &clobber_head, &root_pos,
2429 type, 1);
2431 /* Find the end of the test chain on the last node. */
2432 for (test = last->tests; test->next; test = test->next)
2433 continue;
2435 /* We definitely have a new test to add -- create a new
2436 node if needed. */
2437 place = &test->next;
2438 if (test->type == DT_accept_op)
2440 last = new_decision (&root_pos, &last->success);
2441 place = &last->tests;
2444 /* Skip the C test if it's known to be true at compile
2445 time. */
2446 if (truth == -1)
2448 test = new_decision_test (DT_c_test, &place);
2449 test->u.c_test = c_test;
2452 test = new_decision_test (DT_accept_insn, &place);
2453 test->u.insn.code_number = next_insn_code;
2454 test->u.insn.lineno = pattern_lineno;
2455 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2457 merge_trees (&head, &clobber_head);
2460 break;
2462 case SPLIT:
2463 /* Define the subroutine we will call below and emit in genemit. */
2464 printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code);
2465 break;
2467 case PEEPHOLE2:
2468 /* Define the subroutine we will call below and emit in genemit. */
2469 printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
2470 next_insn_code);
2471 break;
2474 return head;
2477 static void
2478 process_tree (struct decision_head *head, enum routine_type subroutine_type)
2480 if (head->first == NULL)
2482 /* We can elide peephole2_insns, but not recog or split_insns. */
2483 if (subroutine_type == PEEPHOLE2)
2484 return;
2486 else
2488 factor_tests (head);
2490 next_subroutine_number = 0;
2491 break_out_subroutines (head, 1);
2492 find_afterward (head, NULL);
2494 /* We run this after find_afterward, because find_afterward needs
2495 the redundant DT_mode tests on predicates to determine whether
2496 two tests can both be true or not. */
2497 simplify_tests (head);
2499 write_subroutines (head, subroutine_type);
2502 write_subroutine (head, subroutine_type);
2505 extern int main (int, char **);
2508 main (int argc, char **argv)
2510 rtx desc;
2511 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2513 progname = "genrecog";
2515 memset (&recog_tree, 0, sizeof recog_tree);
2516 memset (&split_tree, 0, sizeof split_tree);
2517 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2519 if (!init_rtx_reader_args (argc, argv))
2520 return (FATAL_EXIT_CODE);
2522 next_insn_code = 0;
2524 write_header ();
2526 /* Read the machine description. */
2528 while (1)
2530 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2531 if (desc == NULL)
2532 break;
2534 switch (GET_CODE (desc))
2536 case DEFINE_INSN:
2537 h = make_insn_sequence (desc, RECOG);
2538 merge_trees (&recog_tree, &h);
2539 break;
2541 case DEFINE_SPLIT:
2542 h = make_insn_sequence (desc, SPLIT);
2543 merge_trees (&split_tree, &h);
2544 break;
2546 case DEFINE_PEEPHOLE2:
2547 h = make_insn_sequence (desc, PEEPHOLE2);
2548 merge_trees (&peephole2_tree, &h);
2550 default:
2551 /* do nothing */;
2555 if (have_error)
2556 return FATAL_EXIT_CODE;
2558 puts ("\n\n");
2560 process_tree (&recog_tree, RECOG);
2561 process_tree (&split_tree, SPLIT);
2562 process_tree (&peephole2_tree, PEEPHOLE2);
2564 fflush (stdout);
2565 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2568 static void
2569 debug_decision_2 (struct decision_test *test)
2571 switch (test->type)
2573 case DT_num_insns:
2574 fprintf (stderr, "num_insns=%d", test->u.num_insns);
2575 break;
2576 case DT_mode:
2577 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2578 break;
2579 case DT_code:
2580 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2581 break;
2582 case DT_veclen:
2583 fprintf (stderr, "veclen=%d", test->u.veclen);
2584 break;
2585 case DT_elt_zero_int:
2586 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2587 break;
2588 case DT_elt_one_int:
2589 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2590 break;
2591 case DT_elt_zero_wide:
2592 fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2593 break;
2594 case DT_elt_zero_wide_safe:
2595 fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2596 break;
2597 case DT_veclen_ge:
2598 fprintf (stderr, "veclen>=%d", test->u.veclen);
2599 break;
2600 case DT_dup:
2601 fprintf (stderr, "dup=%d", test->u.dup);
2602 break;
2603 case DT_pred:
2604 fprintf (stderr, "pred=(%s,%s)",
2605 test->u.pred.name, GET_MODE_NAME (test->u.pred.mode));
2606 break;
2607 case DT_c_test:
2609 char sub[16+4];
2610 strncpy (sub, test->u.c_test, sizeof (sub));
2611 memcpy (sub+16, "...", 4);
2612 fprintf (stderr, "c_test=\"%s\"", sub);
2614 break;
2615 case DT_accept_op:
2616 fprintf (stderr, "A_op=%d", test->u.opno);
2617 break;
2618 case DT_accept_insn:
2619 fprintf (stderr, "A_insn=(%d,%d)",
2620 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2621 break;
2623 default:
2624 gcc_unreachable ();
2628 static void
2629 debug_decision_1 (struct decision *d, int indent)
2631 int i;
2632 struct decision_test *test;
2634 if (d == NULL)
2636 for (i = 0; i < indent; ++i)
2637 putc (' ', stderr);
2638 fputs ("(nil)\n", stderr);
2639 return;
2642 for (i = 0; i < indent; ++i)
2643 putc (' ', stderr);
2645 putc ('{', stderr);
2646 test = d->tests;
2647 if (test)
2649 debug_decision_2 (test);
2650 while ((test = test->next) != NULL)
2652 fputs (" + ", stderr);
2653 debug_decision_2 (test);
2656 fprintf (stderr, "} %d n %d a %d\n", d->number,
2657 (d->next ? d->next->number : -1),
2658 (d->afterward ? d->afterward->number : -1));
2661 static void
2662 debug_decision_0 (struct decision *d, int indent, int maxdepth)
2664 struct decision *n;
2665 int i;
2667 if (maxdepth < 0)
2668 return;
2669 if (d == NULL)
2671 for (i = 0; i < indent; ++i)
2672 putc (' ', stderr);
2673 fputs ("(nil)\n", stderr);
2674 return;
2677 debug_decision_1 (d, indent);
2678 for (n = d->success.first; n ; n = n->next)
2679 debug_decision_0 (n, indent + 2, maxdepth - 1);
2682 DEBUG_FUNCTION void
2683 debug_decision (struct decision *d)
2685 debug_decision_0 (d, 0, 1000000);
2688 DEBUG_FUNCTION void
2689 debug_decision_list (struct decision *d)
2691 while (d)
2693 debug_decision_0 (d, 0, 0);
2694 d = d->next;