Daily bump.
[official-gcc.git] / gcc / genrecog.c
blob1e8f8545f1c431aed70ba20bd7e6f097b1938bbb
1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
23 /* This program is used to produce insn-recog.c, which contains a
24 function called `recog' plus its subroutines. These functions
25 contain a decision tree that recognizes whether an rtx, the
26 argument given to recog, is a valid instruction.
28 recog returns -1 if the rtx is not valid. If the rtx is valid,
29 recog returns a nonnegative number which is the insn code number
30 for the pattern that matched. This is the same as the order in the
31 machine description of the entry that matched. This number can be
32 used as an index into various insn_* tables, such as insn_template,
33 insn_outfun, and insn_n_operands (found in insn-output.c).
35 The third argument to recog is an optional pointer to an int. If
36 present, recog will accept a pattern if it matches except for
37 missing CLOBBER expressions at the end. In that case, the value
38 pointed to by the optional pointer will be set to the number of
39 CLOBBERs that need to be added (it should be initialized to zero by
40 the caller). If it is set nonzero, the caller should allocate a
41 PARALLEL of the appropriate size, copy the initial entries, and
42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
44 This program also generates the function `split_insns', which
45 returns 0 if the rtl could not be split, or it returns the split
46 rtl in a SEQUENCE.
48 This program also generates the function `peephole2_insns', which
49 returns 0 if the rtl could not be matched. If there was a match,
50 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
53 #include "hconfig.h"
54 #include "system.h"
55 #include "rtl.h"
56 #include "errors.h"
57 #include "gensupport.h"
60 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
61 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
63 /* Holds an array of names indexed by insn_code_number. */
64 static char **insn_name_ptr = 0;
65 static int insn_name_ptr_size = 0;
67 /* A listhead of decision trees. The alternatives to a node are kept
68 in a doublely-linked list so we can easily add nodes to the proper
69 place when merging. */
71 struct decision_head
73 struct decision *first;
74 struct decision *last;
77 /* A single test. The two accept types aren't tests per-se, but
78 their equality (or lack thereof) does affect tree merging so
79 it is convenient to keep them here. */
81 struct decision_test
83 /* A linked list through the tests attached to a node. */
84 struct decision_test *next;
86 /* These types are roughly in the order in which we'd like to test them. */
87 enum decision_type
89 DT_mode, DT_code, DT_veclen,
90 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
91 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
92 DT_accept_op, DT_accept_insn
93 } type;
95 union
97 enum machine_mode mode; /* Machine mode of node. */
98 RTX_CODE code; /* Code to test. */
100 struct
102 const char *name; /* Predicate to call. */
103 int index; /* Index into `preds' or -1. */
104 enum machine_mode mode; /* Machine mode for node. */
105 } pred;
107 const char *c_test; /* Additional test to perform. */
108 int veclen; /* Length of vector. */
109 int dup; /* Number of operand to compare against. */
110 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
111 int opno; /* Operand number matched. */
113 struct {
114 int code_number; /* Insn number matched. */
115 int lineno; /* Line number of the insn. */
116 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
117 } insn;
118 } u;
121 /* Data structure for decision tree for recognizing legitimate insns. */
123 struct decision
125 struct decision_head success; /* Nodes to test on success. */
126 struct decision *next; /* Node to test on failure. */
127 struct decision *prev; /* Node whose failure tests us. */
128 struct decision *afterward; /* Node to test on success,
129 but failure of successor nodes. */
131 const char *position; /* String denoting position in pattern. */
133 struct decision_test *tests; /* The tests for this node. */
135 int number; /* Node number, used for labels */
136 int subroutine_number; /* Number of subroutine this node starts */
137 int need_label; /* Label needs to be output. */
140 #define SUBROUTINE_THRESHOLD 100
142 static int next_subroutine_number;
144 /* We can write three types of subroutines: One for insn recognition,
145 one to split insns, and one for peephole-type optimizations. This
146 defines which type is being written. */
148 enum routine_type {
149 RECOG, SPLIT, PEEPHOLE2
152 #define IS_SPLIT(X) ((X) != RECOG)
154 /* Next available node number for tree nodes. */
156 static int next_number;
158 /* Next number to use as an insn_code. */
160 static int next_insn_code;
162 /* Similar, but counts all expressions in the MD file; used for
163 error messages. */
165 static int next_index;
167 /* Record the highest depth we ever have so we know how many variables to
168 allocate in each subroutine we make. */
170 static int max_depth;
172 /* The line number of the start of the pattern currently being processed. */
173 static int pattern_lineno;
175 /* Count of errors. */
176 static int error_count;
178 /* This table contains a list of the rtl codes that can possibly match a
179 predicate defined in recog.c. The function `maybe_both_true' uses it to
180 deduce that there are no expressions that can be matches by certain pairs
181 of tree nodes. Also, if a predicate can match only one code, we can
182 hardwire that code into the node testing the predicate. */
184 static const struct pred_table
186 const char *const name;
187 const RTX_CODE codes[NUM_RTX_CODE];
188 } preds[] = {
189 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
190 LABEL_REF, SUBREG, REG, MEM}},
191 #ifdef PREDICATE_CODES
192 PREDICATE_CODES
193 #endif
194 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
195 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
196 {"register_operand", {SUBREG, REG}},
197 {"pmode_register_operand", {SUBREG, REG}},
198 {"scratch_operand", {SCRATCH, REG}},
199 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
200 LABEL_REF}},
201 {"const_int_operand", {CONST_INT}},
202 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
203 {"nonimmediate_operand", {SUBREG, REG, MEM}},
204 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
205 LABEL_REF, SUBREG, REG}},
206 {"push_operand", {MEM}},
207 {"pop_operand", {MEM}},
208 {"memory_operand", {SUBREG, MEM}},
209 {"indirect_operand", {SUBREG, MEM}},
210 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
211 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
212 UNLT, LTGT}},
213 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
214 LABEL_REF, SUBREG, REG, MEM}}
217 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
219 static const char *const special_mode_pred_table[] = {
220 #ifdef SPECIAL_MODE_PREDICATES
221 SPECIAL_MODE_PREDICATES
222 #endif
223 "pmode_register_operand"
226 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
228 static struct decision *new_decision
229 PARAMS ((const char *, struct decision_head *));
230 static struct decision_test *new_decision_test
231 PARAMS ((enum decision_type, struct decision_test ***));
232 static rtx find_operand
233 PARAMS ((rtx, int));
234 static rtx find_matching_operand
235 PARAMS ((rtx, int));
236 static void validate_pattern
237 PARAMS ((rtx, rtx, rtx, int));
238 static struct decision *add_to_sequence
239 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
241 static int maybe_both_true_2
242 PARAMS ((struct decision_test *, struct decision_test *));
243 static int maybe_both_true_1
244 PARAMS ((struct decision_test *, struct decision_test *));
245 static int maybe_both_true
246 PARAMS ((struct decision *, struct decision *, int));
248 static int nodes_identical_1
249 PARAMS ((struct decision_test *, struct decision_test *));
250 static int nodes_identical
251 PARAMS ((struct decision *, struct decision *));
252 static void merge_accept_insn
253 PARAMS ((struct decision *, struct decision *));
254 static void merge_trees
255 PARAMS ((struct decision_head *, struct decision_head *));
257 static void factor_tests
258 PARAMS ((struct decision_head *));
259 static void simplify_tests
260 PARAMS ((struct decision_head *));
261 static int break_out_subroutines
262 PARAMS ((struct decision_head *, int));
263 static void find_afterward
264 PARAMS ((struct decision_head *, struct decision *));
266 static void change_state
267 PARAMS ((const char *, const char *, struct decision *, const char *));
268 static void print_code
269 PARAMS ((enum rtx_code));
270 static void write_afterward
271 PARAMS ((struct decision *, struct decision *, const char *));
272 static struct decision *write_switch
273 PARAMS ((struct decision *, int));
274 static void write_cond
275 PARAMS ((struct decision_test *, int, enum routine_type));
276 static void write_action
277 PARAMS ((struct decision *, struct decision_test *, int, int,
278 struct decision *, enum routine_type));
279 static int is_unconditional
280 PARAMS ((struct decision_test *, enum routine_type));
281 static int write_node
282 PARAMS ((struct decision *, int, enum routine_type));
283 static void write_tree_1
284 PARAMS ((struct decision_head *, int, enum routine_type));
285 static void write_tree
286 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
287 static void write_subroutine
288 PARAMS ((struct decision_head *, enum routine_type));
289 static void write_subroutines
290 PARAMS ((struct decision_head *, enum routine_type));
291 static void write_header
292 PARAMS ((void));
294 static struct decision_head make_insn_sequence
295 PARAMS ((rtx, enum routine_type));
296 static void process_tree
297 PARAMS ((struct decision_head *, enum routine_type));
299 static void record_insn_name
300 PARAMS ((int, const char *));
302 static void debug_decision_0
303 PARAMS ((struct decision *, int, int));
304 static void debug_decision_1
305 PARAMS ((struct decision *, int));
306 static void debug_decision_2
307 PARAMS ((struct decision_test *));
308 extern void debug_decision
309 PARAMS ((struct decision *));
310 extern void debug_decision_list
311 PARAMS ((struct decision *));
313 /* Create a new node in sequence after LAST. */
315 static struct decision *
316 new_decision (position, last)
317 const char *position;
318 struct decision_head *last;
320 struct decision *new
321 = (struct decision *) xmalloc (sizeof (struct decision));
323 memset (new, 0, sizeof (*new));
324 new->success = *last;
325 new->position = xstrdup (position);
326 new->number = next_number++;
328 last->first = last->last = new;
329 return new;
332 /* Create a new test and link it in at PLACE. */
334 static struct decision_test *
335 new_decision_test (type, pplace)
336 enum decision_type type;
337 struct decision_test ***pplace;
339 struct decision_test **place = *pplace;
340 struct decision_test *test;
342 test = (struct decision_test *) xmalloc (sizeof (*test));
343 test->next = *place;
344 test->type = type;
345 *place = test;
347 place = &test->next;
348 *pplace = place;
350 return test;
353 /* Search for and return operand N. */
355 static rtx
356 find_operand (pattern, n)
357 rtx pattern;
358 int n;
360 const char *fmt;
361 RTX_CODE code;
362 int i, j, len;
363 rtx r;
365 code = GET_CODE (pattern);
366 if ((code == MATCH_SCRATCH
367 || code == MATCH_INSN
368 || code == MATCH_OPERAND
369 || code == MATCH_OPERATOR
370 || code == MATCH_PARALLEL)
371 && XINT (pattern, 0) == n)
372 return pattern;
374 fmt = GET_RTX_FORMAT (code);
375 len = GET_RTX_LENGTH (code);
376 for (i = 0; i < len; i++)
378 switch (fmt[i])
380 case 'e': case 'u':
381 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
382 return r;
383 break;
385 case 'V':
386 if (! XVEC (pattern, i))
387 break;
388 /* FALLTHRU */
390 case 'E':
391 for (j = 0; j < XVECLEN (pattern, i); j++)
392 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
393 return r;
394 break;
396 case 'i': case 'w': case '0': case 's':
397 break;
399 default:
400 abort ();
404 return NULL;
407 /* Search for and return operand M, such that it has a matching
408 constraint for operand N. */
410 static rtx
411 find_matching_operand (pattern, n)
412 rtx pattern;
413 int n;
415 const char *fmt;
416 RTX_CODE code;
417 int i, j, len;
418 rtx r;
420 code = GET_CODE (pattern);
421 if (code == MATCH_OPERAND
422 && (XSTR (pattern, 2)[0] == '0' + n
423 || (XSTR (pattern, 2)[0] == '%'
424 && XSTR (pattern, 2)[1] == '0' + n)))
425 return pattern;
427 fmt = GET_RTX_FORMAT (code);
428 len = GET_RTX_LENGTH (code);
429 for (i = 0; i < len; i++)
431 switch (fmt[i])
433 case 'e': case 'u':
434 if ((r = find_matching_operand (XEXP (pattern, i), n)))
435 return r;
436 break;
438 case 'V':
439 if (! XVEC (pattern, i))
440 break;
441 /* FALLTHRU */
443 case 'E':
444 for (j = 0; j < XVECLEN (pattern, i); j++)
445 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
446 return r;
447 break;
449 case 'i': case 'w': case '0': case 's':
450 break;
452 default:
453 abort ();
457 return NULL;
461 /* Check for various errors in patterns. SET is nonnull for a destination,
462 and is the complete set pattern. SET_CODE is '=' for normal sets, and
463 '+' within a context that requires in-out constraints. */
465 static void
466 validate_pattern (pattern, insn, set, set_code)
467 rtx pattern;
468 rtx insn;
469 rtx set;
470 int set_code;
472 const char *fmt;
473 RTX_CODE code;
474 size_t i, len;
475 int j;
477 code = GET_CODE (pattern);
478 switch (code)
480 case MATCH_SCRATCH:
481 return;
483 case MATCH_INSN:
484 case MATCH_OPERAND:
485 case MATCH_OPERATOR:
487 const char *pred_name = XSTR (pattern, 1);
488 int allows_non_lvalue = 1, allows_non_const = 1;
489 int special_mode_pred = 0;
490 const char *c_test;
492 if (GET_CODE (insn) == DEFINE_INSN)
493 c_test = XSTR (insn, 2);
494 else
495 c_test = XSTR (insn, 1);
497 if (pred_name[0] != 0)
499 for (i = 0; i < NUM_KNOWN_PREDS; i++)
500 if (! strcmp (preds[i].name, pred_name))
501 break;
503 if (i < NUM_KNOWN_PREDS)
505 int j;
507 allows_non_lvalue = allows_non_const = 0;
508 for (j = 0; preds[i].codes[j] != 0; j++)
510 RTX_CODE c = preds[i].codes[j];
511 if (c != LABEL_REF
512 && c != SYMBOL_REF
513 && c != CONST_INT
514 && c != CONST_DOUBLE
515 && c != CONST
516 && c != HIGH
517 && c != CONSTANT_P_RTX)
518 allows_non_const = 1;
520 if (c != REG
521 && c != SUBREG
522 && c != MEM
523 && c != CONCAT
524 && c != PARALLEL
525 && c != STRICT_LOW_PART)
526 allows_non_lvalue = 1;
529 else
531 #ifdef PREDICATE_CODES
532 /* If the port has a list of the predicates it uses but
533 omits one, warn. */
534 message_with_line (pattern_lineno,
535 "warning: `%s' not in PREDICATE_CODES",
536 pred_name);
537 #endif
540 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
541 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
543 special_mode_pred = 1;
544 break;
548 if (code == MATCH_OPERAND)
550 const char constraints0 = XSTR (pattern, 2)[0];
552 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
553 don't use the MATCH_OPERAND constraint, only the predicate.
554 This is confusing to folks doing new ports, so help them
555 not make the mistake. */
556 if (GET_CODE (insn) == DEFINE_EXPAND
557 || GET_CODE (insn) == DEFINE_SPLIT
558 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
560 if (constraints0)
561 message_with_line (pattern_lineno,
562 "warning: constraints not supported in %s",
563 rtx_name[GET_CODE (insn)]);
566 /* A MATCH_OPERAND that is a SET should have an output reload. */
567 else if (set && constraints0)
569 if (set_code == '+')
571 if (constraints0 == '+')
573 /* If we've only got an output reload for this operand,
574 we'd better have a matching input operand. */
575 else if (constraints0 == '='
576 && find_matching_operand (insn, XINT (pattern, 0)))
578 else
580 message_with_line (pattern_lineno,
581 "operand %d missing in-out reload",
582 XINT (pattern, 0));
583 error_count++;
586 else if (constraints0 != '=' && constraints0 != '+')
588 message_with_line (pattern_lineno,
589 "operand %d missing output reload",
590 XINT (pattern, 0));
591 error_count++;
596 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
597 while not likely to occur at runtime, results in less efficient
598 code from insn-recog.c. */
599 if (set
600 && pred_name[0] != '\0'
601 && allows_non_lvalue)
603 message_with_line (pattern_lineno,
604 "warning: destination operand %d allows non-lvalue",
605 XINT (pattern, 0));
608 /* A modeless MATCH_OPERAND can be handy when we can
609 check for multiple modes in the c_test. In most other cases,
610 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
611 and PEEP2 can FAIL within the output pattern. Exclude
612 address_operand, since its mode is related to the mode of
613 the memory not the operand. Exclude the SET_DEST of a call
614 instruction, as that is a common idiom. */
616 if (GET_MODE (pattern) == VOIDmode
617 && code == MATCH_OPERAND
618 && GET_CODE (insn) == DEFINE_INSN
619 && allows_non_const
620 && ! special_mode_pred
621 && pred_name[0] != '\0'
622 && strcmp (pred_name, "address_operand") != 0
623 && strstr (c_test, "operands") == NULL
624 && ! (set
625 && GET_CODE (set) == SET
626 && GET_CODE (SET_SRC (set)) == CALL))
628 message_with_line (pattern_lineno,
629 "warning: operand %d missing mode?",
630 XINT (pattern, 0));
632 return;
635 case SET:
637 enum machine_mode dmode, smode;
638 rtx dest, src;
640 dest = SET_DEST (pattern);
641 src = SET_SRC (pattern);
643 /* STRICT_LOW_PART is a wrapper. Its argument is the real
644 destination, and it's mode should match the source. */
645 if (GET_CODE (dest) == STRICT_LOW_PART)
646 dest = XEXP (dest, 0);
648 /* Find the referant for a DUP. */
650 if (GET_CODE (dest) == MATCH_DUP
651 || GET_CODE (dest) == MATCH_OP_DUP
652 || GET_CODE (dest) == MATCH_PAR_DUP)
653 dest = find_operand (insn, XINT (dest, 0));
655 if (GET_CODE (src) == MATCH_DUP
656 || GET_CODE (src) == MATCH_OP_DUP
657 || GET_CODE (src) == MATCH_PAR_DUP)
658 src = find_operand (insn, XINT (src, 0));
660 dmode = GET_MODE (dest);
661 smode = GET_MODE (src);
663 /* The mode of an ADDRESS_OPERAND is the mode of the memory
664 reference, not the mode of the address. */
665 if (GET_CODE (src) == MATCH_OPERAND
666 && ! strcmp (XSTR (src, 1), "address_operand"))
669 /* The operands of a SET must have the same mode unless one
670 is VOIDmode. */
671 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
673 message_with_line (pattern_lineno,
674 "mode mismatch in set: %smode vs %smode",
675 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
676 error_count++;
679 /* If only one of the operands is VOIDmode, and PC or CC0 is
680 not involved, it's probably a mistake. */
681 else if (dmode != smode
682 && GET_CODE (dest) != PC
683 && GET_CODE (dest) != CC0
684 && GET_CODE (src) != PC
685 && GET_CODE (src) != CC0
686 && GET_CODE (src) != CONST_INT)
688 const char *which;
689 which = (dmode == VOIDmode ? "destination" : "source");
690 message_with_line (pattern_lineno,
691 "warning: %s missing a mode?", which);
694 if (dest != SET_DEST (pattern))
695 validate_pattern (dest, insn, pattern, '=');
696 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
697 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
698 return;
701 case CLOBBER:
702 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
703 return;
705 case ZERO_EXTRACT:
706 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
707 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
708 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
709 return;
711 case STRICT_LOW_PART:
712 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
713 return;
715 case LABEL_REF:
716 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
718 message_with_line (pattern_lineno,
719 "operand to label_ref %smode not VOIDmode",
720 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
721 error_count++;
723 break;
725 default:
726 break;
729 fmt = GET_RTX_FORMAT (code);
730 len = GET_RTX_LENGTH (code);
731 for (i = 0; i < len; i++)
733 switch (fmt[i])
735 case 'e': case 'u':
736 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
737 break;
739 case 'E':
740 for (j = 0; j < XVECLEN (pattern, i); j++)
741 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
742 break;
744 case 'i': case 'w': case '0': case 's':
745 break;
747 default:
748 abort ();
753 /* Create a chain of nodes to verify that an rtl expression matches
754 PATTERN.
756 LAST is a pointer to the listhead in the previous node in the chain (or
757 in the calling function, for the first node).
759 POSITION is the string representing the current position in the insn.
761 INSN_TYPE is the type of insn for which we are emitting code.
763 A pointer to the final node in the chain is returned. */
765 static struct decision *
766 add_to_sequence (pattern, last, position, insn_type, top)
767 rtx pattern;
768 struct decision_head *last;
769 const char *position;
770 enum routine_type insn_type;
771 int top;
773 RTX_CODE code;
774 struct decision *this, *sub;
775 struct decision_test *test;
776 struct decision_test **place;
777 char *subpos;
778 size_t i;
779 const char *fmt;
780 int depth = strlen (position);
781 int len;
782 enum machine_mode mode;
784 if (depth > max_depth)
785 max_depth = depth;
787 subpos = (char *) xmalloc (depth + 2);
788 strcpy (subpos, position);
789 subpos[depth + 1] = 0;
791 sub = this = new_decision (position, last);
792 place = &this->tests;
794 restart:
795 mode = GET_MODE (pattern);
796 code = GET_CODE (pattern);
798 switch (code)
800 case PARALLEL:
801 /* Toplevel peephole pattern. */
802 if (insn_type == PEEPHOLE2 && top)
804 /* We don't need the node we just created -- unlink it. */
805 last->first = last->last = NULL;
807 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
809 /* Which insn we're looking at is represented by A-Z. We don't
810 ever use 'A', however; it is always implied. */
812 subpos[depth] = (i > 0 ? 'A' + i : 0);
813 sub = add_to_sequence (XVECEXP (pattern, 0, i),
814 last, subpos, insn_type, 0);
815 last = &sub->success;
817 goto ret;
820 /* Else nothing special. */
821 break;
823 case MATCH_PARALLEL:
824 /* The explicit patterns within a match_parallel enforce a minimum
825 length on the vector. The match_parallel predicate may allow
826 for more elements. We do need to check for this minimum here
827 or the code generated to match the internals may reference data
828 beyond the end of the vector. */
829 test = new_decision_test (DT_veclen_ge, &place);
830 test->u.veclen = XVECLEN (pattern, 2);
831 /* FALLTHRU */
833 case MATCH_OPERAND:
834 case MATCH_SCRATCH:
835 case MATCH_OPERATOR:
836 case MATCH_INSN:
838 const char *pred_name;
839 RTX_CODE was_code = code;
840 int allows_const_int = 1;
842 if (code == MATCH_SCRATCH)
844 pred_name = "scratch_operand";
845 code = UNKNOWN;
847 else
849 pred_name = XSTR (pattern, 1);
850 if (code == MATCH_PARALLEL)
851 code = PARALLEL;
852 else
853 code = UNKNOWN;
856 if (pred_name[0] != 0)
858 test = new_decision_test (DT_pred, &place);
859 test->u.pred.name = pred_name;
860 test->u.pred.mode = mode;
862 /* See if we know about this predicate and save its number.
863 If we do, and it only accepts one code, note that fact.
865 If we know that the predicate does not allow CONST_INT,
866 we know that the only way the predicate can match is if
867 the modes match (here we use the kludge of relying on the
868 fact that "address_operand" accepts CONST_INT; otherwise,
869 it would have to be a special case), so we can test the
870 mode (but we need not). This fact should considerably
871 simplify the generated code. */
873 for (i = 0; i < NUM_KNOWN_PREDS; i++)
874 if (! strcmp (preds[i].name, pred_name))
875 break;
877 if (i < NUM_KNOWN_PREDS)
879 int j;
881 test->u.pred.index = i;
883 if (preds[i].codes[1] == 0 && code == UNKNOWN)
884 code = preds[i].codes[0];
886 allows_const_int = 0;
887 for (j = 0; preds[i].codes[j] != 0; j++)
888 if (preds[i].codes[j] == CONST_INT)
890 allows_const_int = 1;
891 break;
894 else
895 test->u.pred.index = -1;
898 /* Can't enforce a mode if we allow const_int. */
899 if (allows_const_int)
900 mode = VOIDmode;
902 /* Accept the operand, ie. record it in `operands'. */
903 test = new_decision_test (DT_accept_op, &place);
904 test->u.opno = XINT (pattern, 0);
906 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
908 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
909 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
911 subpos[depth] = i + base;
912 sub = add_to_sequence (XVECEXP (pattern, 2, i),
913 &sub->success, subpos, insn_type, 0);
916 goto fini;
919 case MATCH_OP_DUP:
920 code = UNKNOWN;
922 test = new_decision_test (DT_dup, &place);
923 test->u.dup = XINT (pattern, 0);
925 test = new_decision_test (DT_accept_op, &place);
926 test->u.opno = XINT (pattern, 0);
928 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
930 subpos[depth] = i + '0';
931 sub = add_to_sequence (XVECEXP (pattern, 1, i),
932 &sub->success, subpos, insn_type, 0);
934 goto fini;
936 case MATCH_DUP:
937 case MATCH_PAR_DUP:
938 code = UNKNOWN;
940 test = new_decision_test (DT_dup, &place);
941 test->u.dup = XINT (pattern, 0);
942 goto fini;
944 case ADDRESS:
945 pattern = XEXP (pattern, 0);
946 goto restart;
948 default:
949 break;
952 fmt = GET_RTX_FORMAT (code);
953 len = GET_RTX_LENGTH (code);
955 /* Do tests against the current node first. */
956 for (i = 0; i < (size_t) len; i++)
958 if (fmt[i] == 'i')
960 if (i == 0)
962 test = new_decision_test (DT_elt_zero_int, &place);
963 test->u.intval = XINT (pattern, i);
965 else if (i == 1)
967 test = new_decision_test (DT_elt_one_int, &place);
968 test->u.intval = XINT (pattern, i);
970 else
971 abort ();
973 else if (fmt[i] == 'w')
975 /* If this value actually fits in an int, we can use a switch
976 statement here, so indicate that. */
977 enum decision_type type
978 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
979 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
981 if (i != 0)
982 abort ();
984 test = new_decision_test (type, &place);
985 test->u.intval = XWINT (pattern, i);
987 else if (fmt[i] == 'E')
989 if (i != 0)
990 abort ();
992 test = new_decision_test (DT_veclen, &place);
993 test->u.veclen = XVECLEN (pattern, i);
997 /* Now test our sub-patterns. */
998 for (i = 0; i < (size_t) len; i++)
1000 switch (fmt[i])
1002 case 'e': case 'u':
1003 subpos[depth] = '0' + i;
1004 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1005 subpos, insn_type, 0);
1006 break;
1008 case 'E':
1010 int j;
1011 for (j = 0; j < XVECLEN (pattern, i); j++)
1013 subpos[depth] = 'a' + j;
1014 sub = add_to_sequence (XVECEXP (pattern, i, j),
1015 &sub->success, subpos, insn_type, 0);
1017 break;
1020 case 'i': case 'w':
1021 /* Handled above. */
1022 break;
1023 case '0':
1024 break;
1026 default:
1027 abort ();
1031 fini:
1032 /* Insert nodes testing mode and code, if they're still relevant,
1033 before any of the nodes we may have added above. */
1034 if (code != UNKNOWN)
1036 place = &this->tests;
1037 test = new_decision_test (DT_code, &place);
1038 test->u.code = code;
1041 if (mode != VOIDmode)
1043 place = &this->tests;
1044 test = new_decision_test (DT_mode, &place);
1045 test->u.mode = mode;
1048 /* If we didn't insert any tests or accept nodes, hork. */
1049 if (this->tests == NULL)
1050 abort ();
1052 ret:
1053 free (subpos);
1054 return sub;
1057 /* A subroutine of maybe_both_true; examines only one test.
1058 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1060 static int
1061 maybe_both_true_2 (d1, d2)
1062 struct decision_test *d1, *d2;
1064 if (d1->type == d2->type)
1066 switch (d1->type)
1068 case DT_mode:
1069 return d1->u.mode == d2->u.mode;
1071 case DT_code:
1072 return d1->u.code == d2->u.code;
1074 case DT_veclen:
1075 return d1->u.veclen == d2->u.veclen;
1077 case DT_elt_zero_int:
1078 case DT_elt_one_int:
1079 case DT_elt_zero_wide:
1080 case DT_elt_zero_wide_safe:
1081 return d1->u.intval == d2->u.intval;
1083 default:
1084 break;
1088 /* If either has a predicate that we know something about, set
1089 things up so that D1 is the one that always has a known
1090 predicate. Then see if they have any codes in common. */
1092 if (d1->type == DT_pred || d2->type == DT_pred)
1094 if (d2->type == DT_pred)
1096 struct decision_test *tmp;
1097 tmp = d1, d1 = d2, d2 = tmp;
1100 /* If D2 tests a mode, see if it matches D1. */
1101 if (d1->u.pred.mode != VOIDmode)
1103 if (d2->type == DT_mode)
1105 if (d1->u.pred.mode != d2->u.mode
1106 /* The mode of an address_operand predicate is the
1107 mode of the memory, not the operand. It can only
1108 be used for testing the predicate, so we must
1109 ignore it here. */
1110 && strcmp (d1->u.pred.name, "address_operand") != 0)
1111 return 0;
1113 /* Don't check two predicate modes here, because if both predicates
1114 accept CONST_INT, then both can still be true even if the modes
1115 are different. If they don't accept CONST_INT, there will be a
1116 separate DT_mode that will make maybe_both_true_1 return 0. */
1119 if (d1->u.pred.index >= 0)
1121 /* If D2 tests a code, see if it is in the list of valid
1122 codes for D1's predicate. */
1123 if (d2->type == DT_code)
1125 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1126 while (*c != 0)
1128 if (*c == d2->u.code)
1129 break;
1130 ++c;
1132 if (*c == 0)
1133 return 0;
1136 /* Otherwise see if the predicates have any codes in common. */
1137 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1139 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1140 int common = 0;
1142 while (*c1 != 0 && !common)
1144 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1145 while (*c2 != 0 && !common)
1147 common = (*c1 == *c2);
1148 ++c2;
1150 ++c1;
1153 if (!common)
1154 return 0;
1159 /* Tests vs veclen may be known when strict equality is involved. */
1160 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1161 return d1->u.veclen >= d2->u.veclen;
1162 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1163 return d2->u.veclen >= d1->u.veclen;
1165 return -1;
1168 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1169 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1171 static int
1172 maybe_both_true_1 (d1, d2)
1173 struct decision_test *d1, *d2;
1175 struct decision_test *t1, *t2;
1177 /* A match_operand with no predicate can match anything. Recognize
1178 this by the existence of a lone DT_accept_op test. */
1179 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1180 return 1;
1182 /* Eliminate pairs of tests while they can exactly match. */
1183 while (d1 && d2 && d1->type == d2->type)
1185 if (maybe_both_true_2 (d1, d2) == 0)
1186 return 0;
1187 d1 = d1->next, d2 = d2->next;
1190 /* After that, consider all pairs. */
1191 for (t1 = d1; t1 ; t1 = t1->next)
1192 for (t2 = d2; t2 ; t2 = t2->next)
1193 if (maybe_both_true_2 (t1, t2) == 0)
1194 return 0;
1196 return -1;
1199 /* Return 0 if we can prove that there is no RTL that can match both
1200 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1201 can match both or just that we couldn't prove there wasn't such an RTL).
1203 TOPLEVEL is non-zero if we are to only look at the top level and not
1204 recursively descend. */
1206 static int
1207 maybe_both_true (d1, d2, toplevel)
1208 struct decision *d1, *d2;
1209 int toplevel;
1211 struct decision *p1, *p2;
1212 int cmp;
1214 /* Don't compare strings on the different positions in insn. Doing so
1215 is incorrect and results in false matches from constructs like
1217 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1218 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1220 [(set (match_operand:HI "register_operand" "r")
1221 (match_operand:HI "register_operand" "r"))]
1223 If we are presented with such, we are recursing through the remainder
1224 of a node's success nodes (from the loop at the end of this function).
1225 Skip forward until we come to a position that matches.
1227 Due to the way position strings are constructed, we know that iterating
1228 forward from the lexically lower position (e.g. "00") will run into
1229 the lexically higher position (e.g. "1") and not the other way around.
1230 This saves a bit of effort. */
1232 cmp = strcmp (d1->position, d2->position);
1233 if (cmp != 0)
1235 if (toplevel)
1236 abort ();
1238 /* If the d2->position was lexically lower, swap. */
1239 if (cmp > 0)
1240 p1 = d1, d1 = d2, d2 = p1;
1242 if (d1->success.first == 0)
1243 return 1;
1244 for (p1 = d1->success.first; p1; p1 = p1->next)
1245 if (maybe_both_true (p1, d2, 0))
1246 return 1;
1248 return 0;
1251 /* Test the current level. */
1252 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1253 if (cmp >= 0)
1254 return cmp;
1256 /* We can't prove that D1 and D2 cannot both be true. If we are only
1257 to check the top level, return 1. Otherwise, see if we can prove
1258 that all choices in both successors are mutually exclusive. If
1259 either does not have any successors, we can't prove they can't both
1260 be true. */
1262 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1263 return 1;
1265 for (p1 = d1->success.first; p1; p1 = p1->next)
1266 for (p2 = d2->success.first; p2; p2 = p2->next)
1267 if (maybe_both_true (p1, p2, 0))
1268 return 1;
1270 return 0;
1273 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1275 static int
1276 nodes_identical_1 (d1, d2)
1277 struct decision_test *d1, *d2;
1279 switch (d1->type)
1281 case DT_mode:
1282 return d1->u.mode == d2->u.mode;
1284 case DT_code:
1285 return d1->u.code == d2->u.code;
1287 case DT_pred:
1288 return (d1->u.pred.mode == d2->u.pred.mode
1289 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1291 case DT_c_test:
1292 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1294 case DT_veclen:
1295 case DT_veclen_ge:
1296 return d1->u.veclen == d2->u.veclen;
1298 case DT_dup:
1299 return d1->u.dup == d2->u.dup;
1301 case DT_elt_zero_int:
1302 case DT_elt_one_int:
1303 case DT_elt_zero_wide:
1304 case DT_elt_zero_wide_safe:
1305 return d1->u.intval == d2->u.intval;
1307 case DT_accept_op:
1308 return d1->u.opno == d2->u.opno;
1310 case DT_accept_insn:
1311 /* Differences will be handled in merge_accept_insn. */
1312 return 1;
1314 default:
1315 abort ();
1319 /* True iff the two nodes are identical (on one level only). Due
1320 to the way these lists are constructed, we shouldn't have to
1321 consider different orderings on the tests. */
1323 static int
1324 nodes_identical (d1, d2)
1325 struct decision *d1, *d2;
1327 struct decision_test *t1, *t2;
1329 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1331 if (t1->type != t2->type)
1332 return 0;
1333 if (! nodes_identical_1 (t1, t2))
1334 return 0;
1337 /* For success, they should now both be null. */
1338 if (t1 != t2)
1339 return 0;
1341 /* Check that their subnodes are at the same position, as any one set
1342 of sibling decisions must be at the same position. Allowing this
1343 requires complications to find_afterward and when change_state is
1344 invoked. */
1345 if (d1->success.first
1346 && d2->success.first
1347 && strcmp (d1->success.first->position, d2->success.first->position))
1348 return 0;
1350 return 1;
1353 /* A subroutine of merge_trees; given two nodes that have been declared
1354 identical, cope with two insn accept states. If they differ in the
1355 number of clobbers, then the conflict was created by make_insn_sequence
1356 and we can drop the with-clobbers version on the floor. If both
1357 nodes have no additional clobbers, we have found an ambiguity in the
1358 source machine description. */
1360 static void
1361 merge_accept_insn (oldd, addd)
1362 struct decision *oldd, *addd;
1364 struct decision_test *old, *add;
1366 for (old = oldd->tests; old; old = old->next)
1367 if (old->type == DT_accept_insn)
1368 break;
1369 if (old == NULL)
1370 return;
1372 for (add = addd->tests; add; add = add->next)
1373 if (add->type == DT_accept_insn)
1374 break;
1375 if (add == NULL)
1376 return;
1378 /* If one node is for a normal insn and the second is for the base
1379 insn with clobbers stripped off, the second node should be ignored. */
1381 if (old->u.insn.num_clobbers_to_add == 0
1382 && add->u.insn.num_clobbers_to_add > 0)
1384 /* Nothing to do here. */
1386 else if (old->u.insn.num_clobbers_to_add > 0
1387 && add->u.insn.num_clobbers_to_add == 0)
1389 /* In this case, replace OLD with ADD. */
1390 old->u.insn = add->u.insn;
1392 else
1394 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1395 get_insn_name (add->u.insn.code_number),
1396 get_insn_name (old->u.insn.code_number));
1397 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1398 get_insn_name (old->u.insn.code_number));
1399 error_count++;
1403 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1405 static void
1406 merge_trees (oldh, addh)
1407 struct decision_head *oldh, *addh;
1409 struct decision *next, *add;
1411 if (addh->first == 0)
1412 return;
1413 if (oldh->first == 0)
1415 *oldh = *addh;
1416 return;
1419 /* Trying to merge bits at different positions isn't possible. */
1420 if (strcmp (oldh->first->position, addh->first->position))
1421 abort ();
1423 for (add = addh->first; add ; add = next)
1425 struct decision *old, *insert_before = NULL;
1427 next = add->next;
1429 /* The semantics of pattern matching state that the tests are
1430 done in the order given in the MD file so that if an insn
1431 matches two patterns, the first one will be used. However,
1432 in practice, most, if not all, patterns are unambiguous so
1433 that their order is independent. In that case, we can merge
1434 identical tests and group all similar modes and codes together.
1436 Scan starting from the end of OLDH until we reach a point
1437 where we reach the head of the list or where we pass a
1438 pattern that could also be true if NEW is true. If we find
1439 an identical pattern, we can merge them. Also, record the
1440 last node that tests the same code and mode and the last one
1441 that tests just the same mode.
1443 If we have no match, place NEW after the closest match we found. */
1445 for (old = oldh->last; old; old = old->prev)
1447 if (nodes_identical (old, add))
1449 merge_accept_insn (old, add);
1450 merge_trees (&old->success, &add->success);
1451 goto merged_nodes;
1454 if (maybe_both_true (old, add, 0))
1455 break;
1457 /* Insert the nodes in DT test type order, which is roughly
1458 how expensive/important the test is. Given that the tests
1459 are also ordered within the list, examining the first is
1460 sufficient. */
1461 if ((int) add->tests->type < (int) old->tests->type)
1462 insert_before = old;
1465 if (insert_before == NULL)
1467 add->next = NULL;
1468 add->prev = oldh->last;
1469 oldh->last->next = add;
1470 oldh->last = add;
1472 else
1474 if ((add->prev = insert_before->prev) != NULL)
1475 add->prev->next = add;
1476 else
1477 oldh->first = add;
1478 add->next = insert_before;
1479 insert_before->prev = add;
1482 merged_nodes:;
1486 /* Walk the tree looking for sub-nodes that perform common tests.
1487 Factor out the common test into a new node. This enables us
1488 (depending on the test type) to emit switch statements later. */
1490 static void
1491 factor_tests (head)
1492 struct decision_head *head;
1494 struct decision *first, *next;
1496 for (first = head->first; first && first->next; first = next)
1498 enum decision_type type;
1499 struct decision *new, *old_last;
1501 type = first->tests->type;
1502 next = first->next;
1504 /* Want at least two compatible sequential nodes. */
1505 if (next->tests->type != type)
1506 continue;
1508 /* Don't want all node types, just those we can turn into
1509 switch statements. */
1510 if (type != DT_mode
1511 && type != DT_code
1512 && type != DT_veclen
1513 && type != DT_elt_zero_int
1514 && type != DT_elt_one_int
1515 && type != DT_elt_zero_wide_safe)
1516 continue;
1518 /* If we'd been performing more than one test, create a new node
1519 below our first test. */
1520 if (first->tests->next != NULL)
1522 new = new_decision (first->position, &first->success);
1523 new->tests = first->tests->next;
1524 first->tests->next = NULL;
1527 /* Crop the node tree off after our first test. */
1528 first->next = NULL;
1529 old_last = head->last;
1530 head->last = first;
1532 /* For each compatible test, adjust to perform only one test in
1533 the top level node, then merge the node back into the tree. */
1536 struct decision_head h;
1538 if (next->tests->next != NULL)
1540 new = new_decision (next->position, &next->success);
1541 new->tests = next->tests->next;
1542 next->tests->next = NULL;
1544 new = next;
1545 next = next->next;
1546 new->next = NULL;
1547 h.first = h.last = new;
1549 merge_trees (head, &h);
1551 while (next && next->tests->type == type);
1553 /* After we run out of compatible tests, graft the remaining nodes
1554 back onto the tree. */
1555 if (next)
1557 next->prev = head->last;
1558 head->last->next = next;
1559 head->last = old_last;
1563 /* Recurse. */
1564 for (first = head->first; first; first = first->next)
1565 factor_tests (&first->success);
1568 /* After factoring, try to simplify the tests on any one node.
1569 Tests that are useful for switch statements are recognizable
1570 by having only a single test on a node -- we'll be manipulating
1571 nodes with multiple tests:
1573 If we have mode tests or code tests that are redundant with
1574 predicates, remove them. */
1576 static void
1577 simplify_tests (head)
1578 struct decision_head *head;
1580 struct decision *tree;
1582 for (tree = head->first; tree; tree = tree->next)
1584 struct decision_test *a, *b;
1586 a = tree->tests;
1587 b = a->next;
1588 if (b == NULL)
1589 continue;
1591 /* Find a predicate node. */
1592 while (b && b->type != DT_pred)
1593 b = b->next;
1594 if (b)
1596 /* Due to how these tests are constructed, we don't even need
1597 to check that the mode and code are compatible -- they were
1598 generated from the predicate in the first place. */
1599 while (a->type == DT_mode || a->type == DT_code)
1600 a = a->next;
1601 tree->tests = a;
1605 /* Recurse. */
1606 for (tree = head->first; tree; tree = tree->next)
1607 simplify_tests (&tree->success);
1610 /* Count the number of subnodes of HEAD. If the number is high enough,
1611 make the first node in HEAD start a separate subroutine in the C code
1612 that is generated. */
1614 static int
1615 break_out_subroutines (head, initial)
1616 struct decision_head *head;
1617 int initial;
1619 int size = 0;
1620 struct decision *sub;
1622 for (sub = head->first; sub; sub = sub->next)
1623 size += 1 + break_out_subroutines (&sub->success, 0);
1625 if (size > SUBROUTINE_THRESHOLD && ! initial)
1627 head->first->subroutine_number = ++next_subroutine_number;
1628 size = 1;
1630 return size;
1633 /* For each node p, find the next alternative that might be true
1634 when p is true. */
1636 static void
1637 find_afterward (head, real_afterward)
1638 struct decision_head *head;
1639 struct decision *real_afterward;
1641 struct decision *p, *q, *afterward;
1643 /* We can't propagate alternatives across subroutine boundaries.
1644 This is not incorrect, merely a minor optimization loss. */
1646 p = head->first;
1647 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1649 for ( ; p ; p = p->next)
1651 /* Find the next node that might be true if this one fails. */
1652 for (q = p->next; q ; q = q->next)
1653 if (maybe_both_true (p, q, 1))
1654 break;
1656 /* If we reached the end of the list without finding one,
1657 use the incoming afterward position. */
1658 if (!q)
1659 q = afterward;
1660 p->afterward = q;
1661 if (q)
1662 q->need_label = 1;
1665 /* Recurse. */
1666 for (p = head->first; p ; p = p->next)
1667 if (p->success.first)
1668 find_afterward (&p->success, p->afterward);
1670 /* When we are generating a subroutine, record the real afterward
1671 position in the first node where write_tree can find it, and we
1672 can do the right thing at the subroutine call site. */
1673 p = head->first;
1674 if (p->subroutine_number > 0)
1675 p->afterward = real_afterward;
1678 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1679 actions are necessary to move to NEWPOS. If we fail to move to the
1680 new state, branch to node AFTERWARD if non-zero, otherwise return.
1682 Failure to move to the new state can only occur if we are trying to
1683 match multiple insns and we try to step past the end of the stream. */
1685 static void
1686 change_state (oldpos, newpos, afterward, indent)
1687 const char *oldpos;
1688 const char *newpos;
1689 struct decision *afterward;
1690 const char *indent;
1692 int odepth = strlen (oldpos);
1693 int ndepth = strlen (newpos);
1694 int depth;
1695 int old_has_insn, new_has_insn;
1697 /* Pop up as many levels as necessary. */
1698 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1699 continue;
1701 /* Hunt for the last [A-Z] in both strings. */
1702 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1703 if (ISUPPER (oldpos[old_has_insn]))
1704 break;
1705 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1706 if (ISUPPER (newpos[new_has_insn]))
1707 break;
1709 /* Go down to desired level. */
1710 while (depth < ndepth)
1712 /* It's a different insn from the first one. */
1713 if (ISUPPER (newpos[depth]))
1715 /* We can only fail if we're moving down the tree. */
1716 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1718 printf ("%stem = peep2_next_insn (%d);\n",
1719 indent, newpos[depth] - 'A');
1721 else
1723 printf ("%stem = peep2_next_insn (%d);\n",
1724 indent, newpos[depth] - 'A');
1725 printf ("%sif (tem == NULL_RTX)\n", indent);
1726 if (afterward)
1727 printf ("%s goto L%d;\n", indent, afterward->number);
1728 else
1729 printf ("%s goto ret0;\n", indent);
1731 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1733 else if (ISLOWER (newpos[depth]))
1734 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1735 indent, depth + 1, depth, newpos[depth] - 'a');
1736 else
1737 printf ("%sx%d = XEXP (x%d, %c);\n",
1738 indent, depth + 1, depth, newpos[depth]);
1739 ++depth;
1743 /* Print the enumerator constant for CODE -- the upcase version of
1744 the name. */
1746 static void
1747 print_code (code)
1748 enum rtx_code code;
1750 const char *p;
1751 for (p = GET_RTX_NAME (code); *p; p++)
1752 putchar (TOUPPER (*p));
1755 /* Emit code to cross an afterward link -- change state and branch. */
1757 static void
1758 write_afterward (start, afterward, indent)
1759 struct decision *start;
1760 struct decision *afterward;
1761 const char *indent;
1763 if (!afterward || start->subroutine_number > 0)
1764 printf("%sgoto ret0;\n", indent);
1765 else
1767 change_state (start->position, afterward->position, NULL, indent);
1768 printf ("%sgoto L%d;\n", indent, afterward->number);
1772 /* Emit a switch statement, if possible, for an initial sequence of
1773 nodes at START. Return the first node yet untested. */
1775 static struct decision *
1776 write_switch (start, depth)
1777 struct decision *start;
1778 int depth;
1780 struct decision *p = start;
1781 enum decision_type type = p->tests->type;
1782 struct decision *needs_label = NULL;
1784 /* If we have two or more nodes in sequence that test the same one
1785 thing, we may be able to use a switch statement. */
1787 if (!p->next
1788 || p->tests->next
1789 || p->next->tests->type != type
1790 || p->next->tests->next
1791 || nodes_identical_1 (p->tests, p->next->tests))
1792 return p;
1794 /* DT_code is special in that we can do interesting things with
1795 known predicates at the same time. */
1796 if (type == DT_code)
1798 char codemap[NUM_RTX_CODE];
1799 struct decision *ret;
1800 RTX_CODE code;
1802 memset (codemap, 0, sizeof(codemap));
1804 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1805 code = p->tests->u.code;
1808 if (p != start && p->need_label && needs_label == NULL)
1809 needs_label = p;
1811 printf (" case ");
1812 print_code (code);
1813 printf (":\n goto L%d;\n", p->success.first->number);
1814 p->success.first->need_label = 1;
1816 codemap[code] = 1;
1817 p = p->next;
1819 while (p
1820 && ! p->tests->next
1821 && p->tests->type == DT_code
1822 && ! codemap[code = p->tests->u.code]);
1824 /* If P is testing a predicate that we know about and we haven't
1825 seen any of the codes that are valid for the predicate, we can
1826 write a series of "case" statement, one for each possible code.
1827 Since we are already in a switch, these redundant tests are very
1828 cheap and will reduce the number of predicates called. */
1830 /* Note that while we write out cases for these predicates here,
1831 we don't actually write the test here, as it gets kinda messy.
1832 It is trivial to leave this to later by telling our caller that
1833 we only processed the CODE tests. */
1834 if (needs_label != NULL)
1835 ret = needs_label;
1836 else
1837 ret = p;
1839 while (p && p->tests->type == DT_pred
1840 && p->tests->u.pred.index >= 0)
1842 const RTX_CODE *c;
1844 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1845 if (codemap[(int) *c] != 0)
1846 goto pred_done;
1848 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1850 printf (" case ");
1851 print_code (*c);
1852 printf (":\n");
1853 codemap[(int) *c] = 1;
1856 printf (" goto L%d;\n", p->number);
1857 p->need_label = 1;
1858 p = p->next;
1861 pred_done:
1862 /* Make the default case skip the predicates we managed to match. */
1864 printf (" default:\n");
1865 if (p != ret)
1867 if (p)
1869 printf (" goto L%d;\n", p->number);
1870 p->need_label = 1;
1872 else
1873 write_afterward (start, start->afterward, " ");
1875 else
1876 printf (" break;\n");
1877 printf (" }\n");
1879 return ret;
1881 else if (type == DT_mode
1882 || type == DT_veclen
1883 || type == DT_elt_zero_int
1884 || type == DT_elt_one_int
1885 || type == DT_elt_zero_wide_safe)
1887 const char *indent = "";
1889 /* We cast switch parameter to integer, so we must ensure that the value
1890 fits. */
1891 if (type == DT_elt_zero_wide_safe)
1893 indent = " ";
1894 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1896 printf ("%s switch (", indent);
1897 switch (type)
1899 case DT_mode:
1900 printf ("GET_MODE (x%d)", depth);
1901 break;
1902 case DT_veclen:
1903 printf ("XVECLEN (x%d, 0)", depth);
1904 break;
1905 case DT_elt_zero_int:
1906 printf ("XINT (x%d, 0)", depth);
1907 break;
1908 case DT_elt_one_int:
1909 printf ("XINT (x%d, 1)", depth);
1910 break;
1911 case DT_elt_zero_wide_safe:
1912 /* Convert result of XWINT to int for portability since some C
1913 compilers won't do it and some will. */
1914 printf ("(int) XWINT (x%d, 0)", depth);
1915 break;
1916 default:
1917 abort ();
1919 printf (")\n%s {\n", indent);
1923 /* Merge trees will not unify identical nodes if their
1924 sub-nodes are at different levels. Thus we must check
1925 for duplicate cases. */
1926 struct decision *q;
1927 for (q = start; q != p; q = q->next)
1928 if (nodes_identical_1 (p->tests, q->tests))
1929 goto case_done;
1931 if (p != start && p->need_label && needs_label == NULL)
1932 needs_label = p;
1934 printf ("%s case ", indent);
1935 switch (type)
1937 case DT_mode:
1938 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1939 break;
1940 case DT_veclen:
1941 printf ("%d", p->tests->u.veclen);
1942 break;
1943 case DT_elt_zero_int:
1944 case DT_elt_one_int:
1945 case DT_elt_zero_wide:
1946 case DT_elt_zero_wide_safe:
1947 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1948 break;
1949 default:
1950 abort ();
1952 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1953 p->success.first->need_label = 1;
1955 p = p->next;
1957 while (p && p->tests->type == type && !p->tests->next);
1959 case_done:
1960 printf ("%s default:\n%s break;\n%s }\n",
1961 indent, indent, indent);
1963 return needs_label != NULL ? needs_label : p;
1965 else
1967 /* None of the other tests are ameanable. */
1968 return p;
1972 /* Emit code for one test. */
1974 static void
1975 write_cond (p, depth, subroutine_type)
1976 struct decision_test *p;
1977 int depth;
1978 enum routine_type subroutine_type;
1980 switch (p->type)
1982 case DT_mode:
1983 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1984 break;
1986 case DT_code:
1987 printf ("GET_CODE (x%d) == ", depth);
1988 print_code (p->u.code);
1989 break;
1991 case DT_veclen:
1992 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1993 break;
1995 case DT_elt_zero_int:
1996 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1997 break;
1999 case DT_elt_one_int:
2000 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
2001 break;
2003 case DT_elt_zero_wide:
2004 case DT_elt_zero_wide_safe:
2005 printf ("XWINT (x%d, 0) == ", depth);
2006 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
2007 break;
2009 case DT_veclen_ge:
2010 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2011 break;
2013 case DT_dup:
2014 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2015 break;
2017 case DT_pred:
2018 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2019 GET_MODE_NAME (p->u.pred.mode));
2020 break;
2022 case DT_c_test:
2023 printf ("(%s)", p->u.c_test);
2024 break;
2026 case DT_accept_insn:
2027 switch (subroutine_type)
2029 case RECOG:
2030 if (p->u.insn.num_clobbers_to_add == 0)
2031 abort ();
2032 printf ("pnum_clobbers != NULL");
2033 break;
2035 default:
2036 abort ();
2038 break;
2040 default:
2041 abort ();
2045 /* Emit code for one action. The previous tests have succeeded;
2046 TEST is the last of the chain. In the normal case we simply
2047 perform a state change. For the `accept' tests we must do more work. */
2049 static void
2050 write_action (p, test, depth, uncond, success, subroutine_type)
2051 struct decision *p;
2052 struct decision_test *test;
2053 int depth, uncond;
2054 struct decision *success;
2055 enum routine_type subroutine_type;
2057 const char *indent;
2058 int want_close = 0;
2060 if (uncond)
2061 indent = " ";
2062 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2064 fputs (" {\n", stdout);
2065 indent = " ";
2066 want_close = 1;
2068 else
2069 indent = " ";
2071 if (test->type == DT_accept_op)
2073 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2075 /* Only allow DT_accept_insn to follow. */
2076 if (test->next)
2078 test = test->next;
2079 if (test->type != DT_accept_insn)
2080 abort ();
2084 /* Sanity check that we're now at the end of the list of tests. */
2085 if (test->next)
2086 abort ();
2088 if (test->type == DT_accept_insn)
2090 switch (subroutine_type)
2092 case RECOG:
2093 if (test->u.insn.num_clobbers_to_add != 0)
2094 printf ("%s*pnum_clobbers = %d;\n",
2095 indent, test->u.insn.num_clobbers_to_add);
2096 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2097 break;
2099 case SPLIT:
2100 printf ("%sreturn gen_split_%d (operands);\n",
2101 indent, test->u.insn.code_number);
2102 break;
2104 case PEEPHOLE2:
2106 int match_len = 0, i;
2108 for (i = strlen (p->position) - 1; i >= 0; --i)
2109 if (ISUPPER (p->position[i]))
2111 match_len = p->position[i] - 'A';
2112 break;
2114 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2115 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2116 indent, test->u.insn.code_number);
2117 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2119 break;
2121 default:
2122 abort ();
2125 else
2127 printf("%sgoto L%d;\n", indent, success->number);
2128 success->need_label = 1;
2131 if (want_close)
2132 fputs (" }\n", stdout);
2135 /* Return 1 if the test is always true and has no fallthru path. Return -1
2136 if the test does have a fallthru path, but requires that the condition be
2137 terminated. Otherwise return 0 for a normal test. */
2138 /* ??? is_unconditional is a stupid name for a tri-state function. */
2140 static int
2141 is_unconditional (t, subroutine_type)
2142 struct decision_test *t;
2143 enum routine_type subroutine_type;
2145 if (t->type == DT_accept_op)
2146 return 1;
2148 if (t->type == DT_accept_insn)
2150 switch (subroutine_type)
2152 case RECOG:
2153 return (t->u.insn.num_clobbers_to_add == 0);
2154 case SPLIT:
2155 return 1;
2156 case PEEPHOLE2:
2157 return -1;
2158 default:
2159 abort ();
2163 return 0;
2166 /* Emit code for one node -- the conditional and the accompanying action.
2167 Return true if there is no fallthru path. */
2169 static int
2170 write_node (p, depth, subroutine_type)
2171 struct decision *p;
2172 int depth;
2173 enum routine_type subroutine_type;
2175 struct decision_test *test, *last_test;
2176 int uncond;
2178 last_test = test = p->tests;
2179 uncond = is_unconditional (test, subroutine_type);
2180 if (uncond == 0)
2182 printf (" if (");
2183 write_cond (test, depth, subroutine_type);
2185 while ((test = test->next) != NULL)
2187 int uncond2;
2189 last_test = test;
2190 uncond2 = is_unconditional (test, subroutine_type);
2191 if (uncond2 != 0)
2192 break;
2194 printf ("\n && ");
2195 write_cond (test, depth, subroutine_type);
2198 printf (")\n");
2201 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2203 return uncond > 0;
2206 /* Emit code for all of the sibling nodes of HEAD. */
2208 static void
2209 write_tree_1 (head, depth, subroutine_type)
2210 struct decision_head *head;
2211 int depth;
2212 enum routine_type subroutine_type;
2214 struct decision *p, *next;
2215 int uncond = 0;
2217 for (p = head->first; p ; p = next)
2219 /* The label for the first element was printed in write_tree. */
2220 if (p != head->first && p->need_label)
2221 OUTPUT_LABEL (" ", p->number);
2223 /* Attempt to write a switch statement for a whole sequence. */
2224 next = write_switch (p, depth);
2225 if (p != next)
2226 uncond = 0;
2227 else
2229 /* Failed -- fall back and write one node. */
2230 uncond = write_node (p, depth, subroutine_type);
2231 next = p->next;
2235 /* Finished with this chain. Close a fallthru path by branching
2236 to the afterward node. */
2237 if (! uncond)
2238 write_afterward (head->last, head->last->afterward, " ");
2241 /* Write out the decision tree starting at HEAD. PREVPOS is the
2242 position at the node that branched to this node. */
2244 static void
2245 write_tree (head, prevpos, type, initial)
2246 struct decision_head *head;
2247 const char *prevpos;
2248 enum routine_type type;
2249 int initial;
2251 struct decision *p = head->first;
2253 putchar ('\n');
2254 if (p->need_label)
2255 OUTPUT_LABEL (" ", p->number);
2257 if (! initial && p->subroutine_number > 0)
2259 static const char * const name_prefix[] = {
2260 "recog", "split", "peephole2"
2263 static const char * const call_suffix[] = {
2264 ", pnum_clobbers", "", ", _pmatch_len"
2267 /* This node has been broken out into a separate subroutine.
2268 Call it, test the result, and branch accordingly. */
2270 if (p->afterward)
2272 printf (" tem = %s_%d (x0, insn%s);\n",
2273 name_prefix[type], p->subroutine_number, call_suffix[type]);
2274 if (IS_SPLIT (type))
2275 printf (" if (tem != 0)\n return tem;\n");
2276 else
2277 printf (" if (tem >= 0)\n return tem;\n");
2279 change_state (p->position, p->afterward->position, NULL, " ");
2280 printf (" goto L%d;\n", p->afterward->number);
2282 else
2284 printf (" return %s_%d (x0, insn%s);\n",
2285 name_prefix[type], p->subroutine_number, call_suffix[type]);
2288 else
2290 int depth = strlen (p->position);
2292 change_state (prevpos, p->position, head->last->afterward, " ");
2293 write_tree_1 (head, depth, type);
2295 for (p = head->first; p; p = p->next)
2296 if (p->success.first)
2297 write_tree (&p->success, p->position, type, 0);
2301 /* Write out a subroutine of type TYPE to do comparisons starting at
2302 node TREE. */
2304 static void
2305 write_subroutine (head, type)
2306 struct decision_head *head;
2307 enum routine_type type;
2309 int subfunction = head->first ? head->first->subroutine_number : 0;
2310 const char *s_or_e;
2311 char extension[32];
2312 int i;
2314 s_or_e = subfunction ? "static " : "";
2316 if (subfunction)
2317 sprintf (extension, "_%d", subfunction);
2318 else if (type == RECOG)
2319 extension[0] = '\0';
2320 else
2321 strcpy (extension, "_insns");
2323 switch (type)
2325 case RECOG:
2326 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2327 printf ("%sint\n\
2328 recog%s (x0, insn, pnum_clobbers)\n\
2329 rtx x0 ATTRIBUTE_UNUSED;\n\
2330 rtx insn ATTRIBUTE_UNUSED;\n\
2331 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2332 break;
2333 case SPLIT:
2334 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2335 printf ("%srtx\n\
2336 split%s (x0, insn)\n\
2337 rtx x0 ATTRIBUTE_UNUSED;\n\
2338 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2339 break;
2340 case PEEPHOLE2:
2341 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2342 s_or_e, extension);
2343 printf ("%srtx\n\
2344 peephole2%s (x0, insn, _pmatch_len)\n\
2345 rtx x0 ATTRIBUTE_UNUSED;\n\
2346 rtx insn ATTRIBUTE_UNUSED;\n\
2347 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2348 break;
2351 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2352 for (i = 1; i <= max_depth; i++)
2353 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2355 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2357 if (!subfunction)
2358 printf (" recog_data.insn = NULL_RTX;\n");
2360 if (head->first)
2361 write_tree (head, "", type, 1);
2362 else
2363 printf (" goto ret0;\n");
2365 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2368 /* In break_out_subroutines, we discovered the boundaries for the
2369 subroutines, but did not write them out. Do so now. */
2371 static void
2372 write_subroutines (head, type)
2373 struct decision_head *head;
2374 enum routine_type type;
2376 struct decision *p;
2378 for (p = head->first; p ; p = p->next)
2379 if (p->success.first)
2380 write_subroutines (&p->success, type);
2382 if (head->first->subroutine_number > 0)
2383 write_subroutine (head, type);
2386 /* Begin the output file. */
2388 static void
2389 write_header ()
2391 puts ("\
2392 /* Generated automatically by the program `genrecog' from the target\n\
2393 machine description file. */\n\
2395 #include \"config.h\"\n\
2396 #include \"system.h\"\n\
2397 #include \"rtl.h\"\n\
2398 #include \"tm_p.h\"\n\
2399 #include \"function.h\"\n\
2400 #include \"insn-config.h\"\n\
2401 #include \"recog.h\"\n\
2402 #include \"real.h\"\n\
2403 #include \"output.h\"\n\
2404 #include \"flags.h\"\n\
2405 #include \"hard-reg-set.h\"\n\
2406 #include \"resource.h\"\n\
2407 #include \"toplev.h\"\n\
2408 #include \"reload.h\"\n\
2409 \n");
2411 puts ("\n\
2412 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2413 X0 is a valid instruction.\n\
2415 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2416 returns a nonnegative number which is the insn code number for the\n\
2417 pattern that matched. This is the same as the order in the machine\n\
2418 description of the entry that matched. This number can be used as an\n\
2419 index into `insn_data' and other tables.\n");
2420 puts ("\
2421 The third argument to recog is an optional pointer to an int. If\n\
2422 present, recog will accept a pattern if it matches except for missing\n\
2423 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2424 the optional pointer will be set to the number of CLOBBERs that need\n\
2425 to be added (it should be initialized to zero by the caller). If it");
2426 puts ("\
2427 is set nonzero, the caller should allocate a PARALLEL of the\n\
2428 appropriate size, copy the initial entries, and call add_clobbers\n\
2429 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2432 puts ("\n\
2433 The function split_insns returns 0 if the rtl could not\n\
2434 be split or the split rtl in a SEQUENCE if it can be.\n\
2436 The function peephole2_insns returns 0 if the rtl could not\n\
2437 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2438 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2439 */\n\n");
2443 /* Construct and return a sequence of decisions
2444 that will recognize INSN.
2446 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2448 static struct decision_head
2449 make_insn_sequence (insn, type)
2450 rtx insn;
2451 enum routine_type type;
2453 rtx x;
2454 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2455 struct decision *last;
2456 struct decision_test *test, **place;
2457 struct decision_head head;
2458 char c_test_pos[2];
2460 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2462 c_test_pos[0] = '\0';
2463 if (type == PEEPHOLE2)
2465 int i, j;
2467 /* peephole2 gets special treatment:
2468 - X always gets an outer parallel even if it's only one entry
2469 - we remove all traces of outer-level match_scratch and match_dup
2470 expressions here. */
2471 x = rtx_alloc (PARALLEL);
2472 PUT_MODE (x, VOIDmode);
2473 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2474 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2476 rtx tmp = XVECEXP (insn, 0, i);
2477 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2479 XVECEXP (x, 0, j) = tmp;
2480 j++;
2483 XVECLEN (x, 0) = j;
2485 c_test_pos[0] = 'A' + j - 1;
2486 c_test_pos[1] = '\0';
2488 else if (XVECLEN (insn, type == RECOG) == 1)
2489 x = XVECEXP (insn, type == RECOG, 0);
2490 else
2492 x = rtx_alloc (PARALLEL);
2493 XVEC (x, 0) = XVEC (insn, type == RECOG);
2494 PUT_MODE (x, VOIDmode);
2497 validate_pattern (x, insn, NULL_RTX, 0);
2499 memset(&head, 0, sizeof(head));
2500 last = add_to_sequence (x, &head, "", type, 1);
2502 /* Find the end of the test chain on the last node. */
2503 for (test = last->tests; test->next; test = test->next)
2504 continue;
2505 place = &test->next;
2507 if (c_test[0])
2509 /* Need a new node if we have another test to add. */
2510 if (test->type == DT_accept_op)
2512 last = new_decision (c_test_pos, &last->success);
2513 place = &last->tests;
2515 test = new_decision_test (DT_c_test, &place);
2516 test->u.c_test = c_test;
2519 test = new_decision_test (DT_accept_insn, &place);
2520 test->u.insn.code_number = next_insn_code;
2521 test->u.insn.lineno = pattern_lineno;
2522 test->u.insn.num_clobbers_to_add = 0;
2524 switch (type)
2526 case RECOG:
2527 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2528 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2529 If so, set up to recognize the pattern without these CLOBBERs. */
2531 if (GET_CODE (x) == PARALLEL)
2533 int i;
2535 /* Find the last non-clobber in the parallel. */
2536 for (i = XVECLEN (x, 0); i > 0; i--)
2538 rtx y = XVECEXP (x, 0, i - 1);
2539 if (GET_CODE (y) != CLOBBER
2540 || (GET_CODE (XEXP (y, 0)) != REG
2541 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2542 break;
2545 if (i != XVECLEN (x, 0))
2547 rtx new;
2548 struct decision_head clobber_head;
2550 /* Build a similar insn without the clobbers. */
2551 if (i == 1)
2552 new = XVECEXP (x, 0, 0);
2553 else
2555 int j;
2557 new = rtx_alloc (PARALLEL);
2558 XVEC (new, 0) = rtvec_alloc (i);
2559 for (j = i - 1; j >= 0; j--)
2560 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2563 /* Recognize it. */
2564 memset (&clobber_head, 0, sizeof(clobber_head));
2565 last = add_to_sequence (new, &clobber_head, "", type, 1);
2567 /* Find the end of the test chain on the last node. */
2568 for (test = last->tests; test->next; test = test->next)
2569 continue;
2571 /* We definitely have a new test to add -- create a new
2572 node if needed. */
2573 place = &test->next;
2574 if (test->type == DT_accept_op)
2576 last = new_decision ("", &last->success);
2577 place = &last->tests;
2580 if (c_test[0])
2582 test = new_decision_test (DT_c_test, &place);
2583 test->u.c_test = c_test;
2586 test = new_decision_test (DT_accept_insn, &place);
2587 test->u.insn.code_number = next_insn_code;
2588 test->u.insn.lineno = pattern_lineno;
2589 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2591 merge_trees (&head, &clobber_head);
2594 break;
2596 case SPLIT:
2597 /* Define the subroutine we will call below and emit in genemit. */
2598 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2599 break;
2601 case PEEPHOLE2:
2602 /* Define the subroutine we will call below and emit in genemit. */
2603 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2604 next_insn_code);
2605 break;
2608 return head;
2611 static void
2612 process_tree (head, subroutine_type)
2613 struct decision_head *head;
2614 enum routine_type subroutine_type;
2616 if (head->first == NULL)
2618 /* We can elide peephole2_insns, but not recog or split_insns. */
2619 if (subroutine_type == PEEPHOLE2)
2620 return;
2622 else
2624 factor_tests (head);
2626 next_subroutine_number = 0;
2627 break_out_subroutines (head, 1);
2628 find_afterward (head, NULL);
2630 /* We run this after find_afterward, because find_afterward needs
2631 the redundant DT_mode tests on predicates to determine whether
2632 two tests can both be true or not. */
2633 simplify_tests(head);
2635 write_subroutines (head, subroutine_type);
2638 write_subroutine (head, subroutine_type);
2641 extern int main PARAMS ((int, char **));
2644 main (argc, argv)
2645 int argc;
2646 char **argv;
2648 rtx desc;
2649 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2651 progname = "genrecog";
2653 memset (&recog_tree, 0, sizeof recog_tree);
2654 memset (&split_tree, 0, sizeof split_tree);
2655 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2657 if (argc <= 1)
2658 fatal ("no input file name");
2660 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2661 return (FATAL_EXIT_CODE);
2663 next_insn_code = 0;
2664 next_index = 0;
2666 write_header ();
2668 /* Read the machine description. */
2670 while (1)
2672 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2673 if (desc == NULL)
2674 break;
2676 if (GET_CODE (desc) == DEFINE_INSN)
2678 h = make_insn_sequence (desc, RECOG);
2679 merge_trees (&recog_tree, &h);
2681 else if (GET_CODE (desc) == DEFINE_SPLIT)
2683 h = make_insn_sequence (desc, SPLIT);
2684 merge_trees (&split_tree, &h);
2686 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2688 h = make_insn_sequence (desc, PEEPHOLE2);
2689 merge_trees (&peephole2_tree, &h);
2692 next_index++;
2695 if (error_count)
2696 return FATAL_EXIT_CODE;
2698 puts ("\n\n");
2700 process_tree (&recog_tree, RECOG);
2701 process_tree (&split_tree, SPLIT);
2702 process_tree (&peephole2_tree, PEEPHOLE2);
2704 fflush (stdout);
2705 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2708 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2709 const char *
2710 get_insn_name (code)
2711 int code;
2713 if (code < insn_name_ptr_size)
2714 return insn_name_ptr[code];
2715 else
2716 return NULL;
2719 static void
2720 record_insn_name (code, name)
2721 int code;
2722 const char *name;
2724 static const char *last_real_name = "insn";
2725 static int last_real_code = 0;
2726 char *new;
2728 if (insn_name_ptr_size <= code)
2730 int new_size;
2731 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2732 insn_name_ptr =
2733 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2734 memset (insn_name_ptr + insn_name_ptr_size, 0,
2735 sizeof(char *) * (new_size - insn_name_ptr_size));
2736 insn_name_ptr_size = new_size;
2739 if (!name || name[0] == '\0')
2741 new = xmalloc (strlen (last_real_name) + 10);
2742 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2744 else
2746 last_real_name = new = xstrdup (name);
2747 last_real_code = code;
2750 insn_name_ptr[code] = new;
2753 static void
2754 debug_decision_2 (test)
2755 struct decision_test *test;
2757 switch (test->type)
2759 case DT_mode:
2760 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2761 break;
2762 case DT_code:
2763 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2764 break;
2765 case DT_veclen:
2766 fprintf (stderr, "veclen=%d", test->u.veclen);
2767 break;
2768 case DT_elt_zero_int:
2769 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2770 break;
2771 case DT_elt_one_int:
2772 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2773 break;
2774 case DT_elt_zero_wide:
2775 fprintf (stderr, "elt0_w=");
2776 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2777 break;
2778 case DT_elt_zero_wide_safe:
2779 fprintf (stderr, "elt0_ws=");
2780 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2781 break;
2782 case DT_veclen_ge:
2783 fprintf (stderr, "veclen>=%d", test->u.veclen);
2784 break;
2785 case DT_dup:
2786 fprintf (stderr, "dup=%d", test->u.dup);
2787 break;
2788 case DT_pred:
2789 fprintf (stderr, "pred=(%s,%s)",
2790 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2791 break;
2792 case DT_c_test:
2794 char sub[16+4];
2795 strncpy (sub, test->u.c_test, sizeof(sub));
2796 memcpy (sub+16, "...", 4);
2797 fprintf (stderr, "c_test=\"%s\"", sub);
2799 break;
2800 case DT_accept_op:
2801 fprintf (stderr, "A_op=%d", test->u.opno);
2802 break;
2803 case DT_accept_insn:
2804 fprintf (stderr, "A_insn=(%d,%d)",
2805 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2806 break;
2808 default:
2809 abort ();
2813 static void
2814 debug_decision_1 (d, indent)
2815 struct decision *d;
2816 int indent;
2818 int i;
2819 struct decision_test *test;
2821 if (d == NULL)
2823 for (i = 0; i < indent; ++i)
2824 putc (' ', stderr);
2825 fputs ("(nil)\n", stderr);
2826 return;
2829 for (i = 0; i < indent; ++i)
2830 putc (' ', stderr);
2832 putc ('{', stderr);
2833 test = d->tests;
2834 if (test)
2836 debug_decision_2 (test);
2837 while ((test = test->next) != NULL)
2839 fputs (" + ", stderr);
2840 debug_decision_2 (test);
2843 fprintf (stderr, "} %d n %d a %d\n", d->number,
2844 (d->next ? d->next->number : -1),
2845 (d->afterward ? d->afterward->number : -1));
2848 static void
2849 debug_decision_0 (d, indent, maxdepth)
2850 struct decision *d;
2851 int indent, maxdepth;
2853 struct decision *n;
2854 int i;
2856 if (maxdepth < 0)
2857 return;
2858 if (d == NULL)
2860 for (i = 0; i < indent; ++i)
2861 putc (' ', stderr);
2862 fputs ("(nil)\n", stderr);
2863 return;
2866 debug_decision_1 (d, indent);
2867 for (n = d->success.first; n ; n = n->next)
2868 debug_decision_0 (n, indent + 2, maxdepth - 1);
2871 void
2872 debug_decision (d)
2873 struct decision *d;
2875 debug_decision_0 (d, 0, 1000000);
2878 void
2879 debug_decision_list (d)
2880 struct decision *d;
2882 while (d)
2884 debug_decision_0 (d, 0, 0);
2885 d = d->next;