index.html (3.10): Add note about mips atomicity.h.
[official-gcc.git] / gcc / genrecog.c
blobbaf8c7fffbc714a0ecbfe7c20a5df06bf89a62b3
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 as an INSN list.
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 an INSN list, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
53 #include "bconfig.h"
54 #include "system.h"
55 #include "coretypes.h"
56 #include "tm.h"
57 #include "rtl.h"
58 #include "errors.h"
59 #include "gensupport.h"
62 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
63 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
65 /* Holds an array of names indexed by insn_code_number. */
66 static char **insn_name_ptr = 0;
67 static int insn_name_ptr_size = 0;
69 /* A listhead of decision trees. The alternatives to a node are kept
70 in a doubly-linked list so we can easily add nodes to the proper
71 place when merging. */
73 struct decision_head
75 struct decision *first;
76 struct decision *last;
79 /* A single test. The two accept types aren't tests per-se, but
80 their equality (or lack thereof) does affect tree merging so
81 it is convenient to keep them here. */
83 struct decision_test
85 /* A linked list through the tests attached to a node. */
86 struct decision_test *next;
88 /* These types are roughly in the order in which we'd like to test them. */
89 enum decision_type
91 DT_mode, DT_code, DT_veclen,
92 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
93 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
94 DT_accept_op, DT_accept_insn
95 } type;
97 union
99 enum machine_mode mode; /* Machine mode of node. */
100 RTX_CODE code; /* Code to test. */
102 struct
104 const char *name; /* Predicate to call. */
105 int index; /* Index into `preds' or -1. */
106 enum machine_mode mode; /* Machine mode for node. */
107 } pred;
109 const char *c_test; /* Additional test to perform. */
110 int veclen; /* Length of vector. */
111 int dup; /* Number of operand to compare against. */
112 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
113 int opno; /* Operand number matched. */
115 struct {
116 int code_number; /* Insn number matched. */
117 int lineno; /* Line number of the insn. */
118 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
119 } insn;
120 } u;
123 /* Data structure for decision tree for recognizing legitimate insns. */
125 struct decision
127 struct decision_head success; /* Nodes to test on success. */
128 struct decision *next; /* Node to test on failure. */
129 struct decision *prev; /* Node whose failure tests us. */
130 struct decision *afterward; /* Node to test on success,
131 but failure of successor nodes. */
133 const char *position; /* String denoting position in pattern. */
135 struct decision_test *tests; /* The tests for this node. */
137 int number; /* Node number, used for labels */
138 int subroutine_number; /* Number of subroutine this node starts */
139 int need_label; /* Label needs to be output. */
142 #define SUBROUTINE_THRESHOLD 100
144 static int next_subroutine_number;
146 /* We can write three types of subroutines: One for insn recognition,
147 one to split insns, and one for peephole-type optimizations. This
148 defines which type is being written. */
150 enum routine_type {
151 RECOG, SPLIT, PEEPHOLE2
154 #define IS_SPLIT(X) ((X) != RECOG)
156 /* Next available node number for tree nodes. */
158 static int next_number;
160 /* Next number to use as an insn_code. */
162 static int next_insn_code;
164 /* Similar, but counts all expressions in the MD file; used for
165 error messages. */
167 static int next_index;
169 /* Record the highest depth we ever have so we know how many variables to
170 allocate in each subroutine we make. */
172 static int max_depth;
174 /* The line number of the start of the pattern currently being processed. */
175 static int pattern_lineno;
177 /* Count of errors. */
178 static int error_count;
180 /* This table contains a list of the rtl codes that can possibly match a
181 predicate defined in recog.c. The function `maybe_both_true' uses it to
182 deduce that there are no expressions that can be matches by certain pairs
183 of tree nodes. Also, if a predicate can match only one code, we can
184 hardwire that code into the node testing the predicate. */
186 static const struct pred_table
188 const char *const name;
189 const RTX_CODE codes[NUM_RTX_CODE];
190 } preds[] = {
191 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
192 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}},
193 #ifdef PREDICATE_CODES
194 PREDICATE_CODES
195 #endif
196 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
197 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF,
198 PLUS, MINUS, MULT}},
199 {"register_operand", {SUBREG, REG, ADDRESSOF}},
200 {"pmode_register_operand", {SUBREG, REG, ADDRESSOF}},
201 {"scratch_operand", {SCRATCH, REG}},
202 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
203 LABEL_REF}},
204 {"const_int_operand", {CONST_INT}},
205 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
206 {"nonimmediate_operand", {SUBREG, REG, MEM, ADDRESSOF}},
207 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
208 LABEL_REF, SUBREG, REG, ADDRESSOF}},
209 {"push_operand", {MEM}},
210 {"pop_operand", {MEM}},
211 {"memory_operand", {SUBREG, MEM}},
212 {"indirect_operand", {SUBREG, MEM}},
213 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
214 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
215 UNLT, LTGT}},
216 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
217 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}}
220 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
222 static const char *const special_mode_pred_table[] = {
223 #ifdef SPECIAL_MODE_PREDICATES
224 SPECIAL_MODE_PREDICATES
225 #endif
226 "pmode_register_operand"
229 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
231 static struct decision *new_decision
232 PARAMS ((const char *, struct decision_head *));
233 static struct decision_test *new_decision_test
234 PARAMS ((enum decision_type, struct decision_test ***));
235 static rtx find_operand
236 PARAMS ((rtx, int));
237 static rtx find_matching_operand
238 PARAMS ((rtx, int));
239 static void validate_pattern
240 PARAMS ((rtx, rtx, rtx, int));
241 static struct decision *add_to_sequence
242 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int));
244 static int maybe_both_true_2
245 PARAMS ((struct decision_test *, struct decision_test *));
246 static int maybe_both_true_1
247 PARAMS ((struct decision_test *, struct decision_test *));
248 static int maybe_both_true
249 PARAMS ((struct decision *, struct decision *, int));
251 static int nodes_identical_1
252 PARAMS ((struct decision_test *, struct decision_test *));
253 static int nodes_identical
254 PARAMS ((struct decision *, struct decision *));
255 static void merge_accept_insn
256 PARAMS ((struct decision *, struct decision *));
257 static void merge_trees
258 PARAMS ((struct decision_head *, struct decision_head *));
260 static void factor_tests
261 PARAMS ((struct decision_head *));
262 static void simplify_tests
263 PARAMS ((struct decision_head *));
264 static int break_out_subroutines
265 PARAMS ((struct decision_head *, int));
266 static void find_afterward
267 PARAMS ((struct decision_head *, struct decision *));
269 static void change_state
270 PARAMS ((const char *, const char *, struct decision *, const char *));
271 static void print_code
272 PARAMS ((enum rtx_code));
273 static void write_afterward
274 PARAMS ((struct decision *, struct decision *, const char *));
275 static struct decision *write_switch
276 PARAMS ((struct decision *, int));
277 static void write_cond
278 PARAMS ((struct decision_test *, int, enum routine_type));
279 static void write_action
280 PARAMS ((struct decision *, struct decision_test *, int, int,
281 struct decision *, enum routine_type));
282 static int is_unconditional
283 PARAMS ((struct decision_test *, enum routine_type));
284 static int write_node
285 PARAMS ((struct decision *, int, enum routine_type));
286 static void write_tree_1
287 PARAMS ((struct decision_head *, int, enum routine_type));
288 static void write_tree
289 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
290 static void write_subroutine
291 PARAMS ((struct decision_head *, enum routine_type));
292 static void write_subroutines
293 PARAMS ((struct decision_head *, enum routine_type));
294 static void write_header
295 PARAMS ((void));
297 static struct decision_head make_insn_sequence
298 PARAMS ((rtx, enum routine_type));
299 static void process_tree
300 PARAMS ((struct decision_head *, enum routine_type));
302 static void record_insn_name
303 PARAMS ((int, const char *));
305 static void debug_decision_0
306 PARAMS ((struct decision *, int, int));
307 static void debug_decision_1
308 PARAMS ((struct decision *, int));
309 static void debug_decision_2
310 PARAMS ((struct decision_test *));
311 extern void debug_decision
312 PARAMS ((struct decision *));
313 extern void debug_decision_list
314 PARAMS ((struct decision *));
316 /* Create a new node in sequence after LAST. */
318 static struct decision *
319 new_decision (position, last)
320 const char *position;
321 struct decision_head *last;
323 struct decision *new
324 = (struct decision *) xmalloc (sizeof (struct decision));
326 memset (new, 0, sizeof (*new));
327 new->success = *last;
328 new->position = xstrdup (position);
329 new->number = next_number++;
331 last->first = last->last = new;
332 return new;
335 /* Create a new test and link it in at PLACE. */
337 static struct decision_test *
338 new_decision_test (type, pplace)
339 enum decision_type type;
340 struct decision_test ***pplace;
342 struct decision_test **place = *pplace;
343 struct decision_test *test;
345 test = (struct decision_test *) xmalloc (sizeof (*test));
346 test->next = *place;
347 test->type = type;
348 *place = test;
350 place = &test->next;
351 *pplace = place;
353 return test;
356 /* Search for and return operand N. */
358 static rtx
359 find_operand (pattern, n)
360 rtx pattern;
361 int n;
363 const char *fmt;
364 RTX_CODE code;
365 int i, j, len;
366 rtx r;
368 code = GET_CODE (pattern);
369 if ((code == MATCH_SCRATCH
370 || code == MATCH_INSN
371 || code == MATCH_OPERAND
372 || code == MATCH_OPERATOR
373 || code == MATCH_PARALLEL)
374 && XINT (pattern, 0) == n)
375 return pattern;
377 fmt = GET_RTX_FORMAT (code);
378 len = GET_RTX_LENGTH (code);
379 for (i = 0; i < len; i++)
381 switch (fmt[i])
383 case 'e': case 'u':
384 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
385 return r;
386 break;
388 case 'V':
389 if (! XVEC (pattern, i))
390 break;
391 /* FALLTHRU */
393 case 'E':
394 for (j = 0; j < XVECLEN (pattern, i); j++)
395 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
396 return r;
397 break;
399 case 'i': case 'w': case '0': case 's':
400 break;
402 default:
403 abort ();
407 return NULL;
410 /* Search for and return operand M, such that it has a matching
411 constraint for operand N. */
413 static rtx
414 find_matching_operand (pattern, n)
415 rtx pattern;
416 int n;
418 const char *fmt;
419 RTX_CODE code;
420 int i, j, len;
421 rtx r;
423 code = GET_CODE (pattern);
424 if (code == MATCH_OPERAND
425 && (XSTR (pattern, 2)[0] == '0' + n
426 || (XSTR (pattern, 2)[0] == '%'
427 && XSTR (pattern, 2)[1] == '0' + n)))
428 return pattern;
430 fmt = GET_RTX_FORMAT (code);
431 len = GET_RTX_LENGTH (code);
432 for (i = 0; i < len; i++)
434 switch (fmt[i])
436 case 'e': case 'u':
437 if ((r = find_matching_operand (XEXP (pattern, i), n)))
438 return r;
439 break;
441 case 'V':
442 if (! XVEC (pattern, i))
443 break;
444 /* FALLTHRU */
446 case 'E':
447 for (j = 0; j < XVECLEN (pattern, i); j++)
448 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
449 return r;
450 break;
452 case 'i': case 'w': case '0': case 's':
453 break;
455 default:
456 abort ();
460 return NULL;
464 /* Check for various errors in patterns. SET is nonnull for a destination,
465 and is the complete set pattern. SET_CODE is '=' for normal sets, and
466 '+' within a context that requires in-out constraints. */
468 static void
469 validate_pattern (pattern, insn, set, set_code)
470 rtx pattern;
471 rtx insn;
472 rtx set;
473 int set_code;
475 const char *fmt;
476 RTX_CODE code;
477 size_t i, len;
478 int j;
480 code = GET_CODE (pattern);
481 switch (code)
483 case MATCH_SCRATCH:
484 return;
486 case MATCH_INSN:
487 case MATCH_OPERAND:
488 case MATCH_OPERATOR:
490 const char *pred_name = XSTR (pattern, 1);
491 int allows_non_lvalue = 1, allows_non_const = 1;
492 int special_mode_pred = 0;
493 const char *c_test;
495 if (GET_CODE (insn) == DEFINE_INSN)
496 c_test = XSTR (insn, 2);
497 else
498 c_test = XSTR (insn, 1);
500 if (pred_name[0] != 0)
502 for (i = 0; i < NUM_KNOWN_PREDS; i++)
503 if (! strcmp (preds[i].name, pred_name))
504 break;
506 if (i < NUM_KNOWN_PREDS)
508 int j;
510 allows_non_lvalue = allows_non_const = 0;
511 for (j = 0; preds[i].codes[j] != 0; j++)
513 RTX_CODE c = preds[i].codes[j];
514 if (c != LABEL_REF
515 && c != SYMBOL_REF
516 && c != CONST_INT
517 && c != CONST_DOUBLE
518 && c != CONST
519 && c != HIGH
520 && c != CONSTANT_P_RTX)
521 allows_non_const = 1;
523 if (c != REG
524 && c != SUBREG
525 && c != MEM
526 && c != ADDRESSOF
527 && c != CONCAT
528 && c != PARALLEL
529 && c != STRICT_LOW_PART)
530 allows_non_lvalue = 1;
533 else
535 #ifdef PREDICATE_CODES
536 /* If the port has a list of the predicates it uses but
537 omits one, warn. */
538 message_with_line (pattern_lineno,
539 "warning: `%s' not in PREDICATE_CODES",
540 pred_name);
541 #endif
544 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
545 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
547 special_mode_pred = 1;
548 break;
552 if (code == MATCH_OPERAND)
554 const char constraints0 = XSTR (pattern, 2)[0];
556 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
557 don't use the MATCH_OPERAND constraint, only the predicate.
558 This is confusing to folks doing new ports, so help them
559 not make the mistake. */
560 if (GET_CODE (insn) == DEFINE_EXPAND
561 || GET_CODE (insn) == DEFINE_SPLIT
562 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
564 if (constraints0)
565 message_with_line (pattern_lineno,
566 "warning: constraints not supported in %s",
567 rtx_name[GET_CODE (insn)]);
570 /* A MATCH_OPERAND that is a SET should have an output reload. */
571 else if (set && constraints0)
573 if (set_code == '+')
575 if (constraints0 == '+')
577 /* If we've only got an output reload for this operand,
578 we'd better have a matching input operand. */
579 else if (constraints0 == '='
580 && find_matching_operand (insn, XINT (pattern, 0)))
582 else
584 message_with_line (pattern_lineno,
585 "operand %d missing in-out reload",
586 XINT (pattern, 0));
587 error_count++;
590 else if (constraints0 != '=' && constraints0 != '+')
592 message_with_line (pattern_lineno,
593 "operand %d missing output reload",
594 XINT (pattern, 0));
595 error_count++;
600 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
601 while not likely to occur at runtime, results in less efficient
602 code from insn-recog.c. */
603 if (set
604 && pred_name[0] != '\0'
605 && allows_non_lvalue)
607 message_with_line (pattern_lineno,
608 "warning: destination operand %d allows non-lvalue",
609 XINT (pattern, 0));
612 /* A modeless MATCH_OPERAND can be handy when we can
613 check for multiple modes in the c_test. In most other cases,
614 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
615 and PEEP2 can FAIL within the output pattern. Exclude
616 address_operand, since its mode is related to the mode of
617 the memory not the operand. Exclude the SET_DEST of a call
618 instruction, as that is a common idiom. */
620 if (GET_MODE (pattern) == VOIDmode
621 && code == MATCH_OPERAND
622 && GET_CODE (insn) == DEFINE_INSN
623 && allows_non_const
624 && ! special_mode_pred
625 && pred_name[0] != '\0'
626 && strcmp (pred_name, "address_operand") != 0
627 && strstr (c_test, "operands") == NULL
628 && ! (set
629 && GET_CODE (set) == SET
630 && GET_CODE (SET_SRC (set)) == CALL))
632 message_with_line (pattern_lineno,
633 "warning: operand %d missing mode?",
634 XINT (pattern, 0));
636 return;
639 case SET:
641 enum machine_mode dmode, smode;
642 rtx dest, src;
644 dest = SET_DEST (pattern);
645 src = SET_SRC (pattern);
647 /* STRICT_LOW_PART is a wrapper. Its argument is the real
648 destination, and it's mode should match the source. */
649 if (GET_CODE (dest) == STRICT_LOW_PART)
650 dest = XEXP (dest, 0);
652 /* Find the referant for a DUP. */
654 if (GET_CODE (dest) == MATCH_DUP
655 || GET_CODE (dest) == MATCH_OP_DUP
656 || GET_CODE (dest) == MATCH_PAR_DUP)
657 dest = find_operand (insn, XINT (dest, 0));
659 if (GET_CODE (src) == MATCH_DUP
660 || GET_CODE (src) == MATCH_OP_DUP
661 || GET_CODE (src) == MATCH_PAR_DUP)
662 src = find_operand (insn, XINT (src, 0));
664 dmode = GET_MODE (dest);
665 smode = GET_MODE (src);
667 /* The mode of an ADDRESS_OPERAND is the mode of the memory
668 reference, not the mode of the address. */
669 if (GET_CODE (src) == MATCH_OPERAND
670 && ! strcmp (XSTR (src, 1), "address_operand"))
673 /* The operands of a SET must have the same mode unless one
674 is VOIDmode. */
675 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
677 message_with_line (pattern_lineno,
678 "mode mismatch in set: %smode vs %smode",
679 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
680 error_count++;
683 /* If only one of the operands is VOIDmode, and PC or CC0 is
684 not involved, it's probably a mistake. */
685 else if (dmode != smode
686 && GET_CODE (dest) != PC
687 && GET_CODE (dest) != CC0
688 && GET_CODE (src) != PC
689 && GET_CODE (src) != CC0
690 && GET_CODE (src) != CONST_INT)
692 const char *which;
693 which = (dmode == VOIDmode ? "destination" : "source");
694 message_with_line (pattern_lineno,
695 "warning: %s missing a mode?", which);
698 if (dest != SET_DEST (pattern))
699 validate_pattern (dest, insn, pattern, '=');
700 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
701 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
702 return;
705 case CLOBBER:
706 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
707 return;
709 case ZERO_EXTRACT:
710 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
711 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
712 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
713 return;
715 case STRICT_LOW_PART:
716 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
717 return;
719 case LABEL_REF:
720 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
722 message_with_line (pattern_lineno,
723 "operand to label_ref %smode not VOIDmode",
724 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
725 error_count++;
727 break;
729 default:
730 break;
733 fmt = GET_RTX_FORMAT (code);
734 len = GET_RTX_LENGTH (code);
735 for (i = 0; i < len; i++)
737 switch (fmt[i])
739 case 'e': case 'u':
740 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
741 break;
743 case 'E':
744 for (j = 0; j < XVECLEN (pattern, i); j++)
745 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
746 break;
748 case 'i': case 'w': case '0': case 's':
749 break;
751 default:
752 abort ();
757 /* Create a chain of nodes to verify that an rtl expression matches
758 PATTERN.
760 LAST is a pointer to the listhead in the previous node in the chain (or
761 in the calling function, for the first node).
763 POSITION is the string representing the current position in the insn.
765 INSN_TYPE is the type of insn for which we are emitting code.
767 A pointer to the final node in the chain is returned. */
769 static struct decision *
770 add_to_sequence (pattern, last, position, insn_type, top)
771 rtx pattern;
772 struct decision_head *last;
773 const char *position;
774 enum routine_type insn_type;
775 int top;
777 RTX_CODE code;
778 struct decision *this, *sub;
779 struct decision_test *test;
780 struct decision_test **place;
781 char *subpos;
782 size_t i;
783 const char *fmt;
784 int depth = strlen (position);
785 int len;
786 enum machine_mode mode;
788 if (depth > max_depth)
789 max_depth = depth;
791 subpos = (char *) xmalloc (depth + 2);
792 strcpy (subpos, position);
793 subpos[depth + 1] = 0;
795 sub = this = new_decision (position, last);
796 place = &this->tests;
798 restart:
799 mode = GET_MODE (pattern);
800 code = GET_CODE (pattern);
802 switch (code)
804 case PARALLEL:
805 /* Toplevel peephole pattern. */
806 if (insn_type == PEEPHOLE2 && top)
808 /* We don't need the node we just created -- unlink it. */
809 last->first = last->last = NULL;
811 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
813 /* Which insn we're looking at is represented by A-Z. We don't
814 ever use 'A', however; it is always implied. */
816 subpos[depth] = (i > 0 ? 'A' + i : 0);
817 sub = add_to_sequence (XVECEXP (pattern, 0, i),
818 last, subpos, insn_type, 0);
819 last = &sub->success;
821 goto ret;
824 /* Else nothing special. */
825 break;
827 case MATCH_PARALLEL:
828 /* The explicit patterns within a match_parallel enforce a minimum
829 length on the vector. The match_parallel predicate may allow
830 for more elements. We do need to check for this minimum here
831 or the code generated to match the internals may reference data
832 beyond the end of the vector. */
833 test = new_decision_test (DT_veclen_ge, &place);
834 test->u.veclen = XVECLEN (pattern, 2);
835 /* FALLTHRU */
837 case MATCH_OPERAND:
838 case MATCH_SCRATCH:
839 case MATCH_OPERATOR:
840 case MATCH_INSN:
842 const char *pred_name;
843 RTX_CODE was_code = code;
844 int allows_const_int = 1;
846 if (code == MATCH_SCRATCH)
848 pred_name = "scratch_operand";
849 code = UNKNOWN;
851 else
853 pred_name = XSTR (pattern, 1);
854 if (code == MATCH_PARALLEL)
855 code = PARALLEL;
856 else
857 code = UNKNOWN;
860 if (pred_name[0] != 0)
862 test = new_decision_test (DT_pred, &place);
863 test->u.pred.name = pred_name;
864 test->u.pred.mode = mode;
866 /* See if we know about this predicate and save its number.
867 If we do, and it only accepts one code, note that fact.
869 If we know that the predicate does not allow CONST_INT,
870 we know that the only way the predicate can match is if
871 the modes match (here we use the kludge of relying on the
872 fact that "address_operand" accepts CONST_INT; otherwise,
873 it would have to be a special case), so we can test the
874 mode (but we need not). This fact should considerably
875 simplify the generated code. */
877 for (i = 0; i < NUM_KNOWN_PREDS; i++)
878 if (! strcmp (preds[i].name, pred_name))
879 break;
881 if (i < NUM_KNOWN_PREDS)
883 int j;
885 test->u.pred.index = i;
887 if (preds[i].codes[1] == 0 && code == UNKNOWN)
888 code = preds[i].codes[0];
890 allows_const_int = 0;
891 for (j = 0; preds[i].codes[j] != 0; j++)
892 if (preds[i].codes[j] == CONST_INT)
894 allows_const_int = 1;
895 break;
898 else
899 test->u.pred.index = -1;
902 /* Can't enforce a mode if we allow const_int. */
903 if (allows_const_int)
904 mode = VOIDmode;
906 /* Accept the operand, ie. record it in `operands'. */
907 test = new_decision_test (DT_accept_op, &place);
908 test->u.opno = XINT (pattern, 0);
910 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
912 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
913 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
915 subpos[depth] = i + base;
916 sub = add_to_sequence (XVECEXP (pattern, 2, i),
917 &sub->success, subpos, insn_type, 0);
920 goto fini;
923 case MATCH_OP_DUP:
924 code = UNKNOWN;
926 test = new_decision_test (DT_dup, &place);
927 test->u.dup = XINT (pattern, 0);
929 test = new_decision_test (DT_accept_op, &place);
930 test->u.opno = XINT (pattern, 0);
932 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
934 subpos[depth] = i + '0';
935 sub = add_to_sequence (XVECEXP (pattern, 1, i),
936 &sub->success, subpos, insn_type, 0);
938 goto fini;
940 case MATCH_DUP:
941 case MATCH_PAR_DUP:
942 code = UNKNOWN;
944 test = new_decision_test (DT_dup, &place);
945 test->u.dup = XINT (pattern, 0);
946 goto fini;
948 case ADDRESS:
949 pattern = XEXP (pattern, 0);
950 goto restart;
952 default:
953 break;
956 fmt = GET_RTX_FORMAT (code);
957 len = GET_RTX_LENGTH (code);
959 /* Do tests against the current node first. */
960 for (i = 0; i < (size_t) len; i++)
962 if (fmt[i] == 'i')
964 if (i == 0)
966 test = new_decision_test (DT_elt_zero_int, &place);
967 test->u.intval = XINT (pattern, i);
969 else if (i == 1)
971 test = new_decision_test (DT_elt_one_int, &place);
972 test->u.intval = XINT (pattern, i);
974 else
975 abort ();
977 else if (fmt[i] == 'w')
979 /* If this value actually fits in an int, we can use a switch
980 statement here, so indicate that. */
981 enum decision_type type
982 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
983 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
985 if (i != 0)
986 abort ();
988 test = new_decision_test (type, &place);
989 test->u.intval = XWINT (pattern, i);
991 else if (fmt[i] == 'E')
993 if (i != 0)
994 abort ();
996 test = new_decision_test (DT_veclen, &place);
997 test->u.veclen = XVECLEN (pattern, i);
1001 /* Now test our sub-patterns. */
1002 for (i = 0; i < (size_t) len; i++)
1004 switch (fmt[i])
1006 case 'e': case 'u':
1007 subpos[depth] = '0' + i;
1008 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1009 subpos, insn_type, 0);
1010 break;
1012 case 'E':
1014 int j;
1015 for (j = 0; j < XVECLEN (pattern, i); j++)
1017 subpos[depth] = 'a' + j;
1018 sub = add_to_sequence (XVECEXP (pattern, i, j),
1019 &sub->success, subpos, insn_type, 0);
1021 break;
1024 case 'i': case 'w':
1025 /* Handled above. */
1026 break;
1027 case '0':
1028 break;
1030 default:
1031 abort ();
1035 fini:
1036 /* Insert nodes testing mode and code, if they're still relevant,
1037 before any of the nodes we may have added above. */
1038 if (code != UNKNOWN)
1040 place = &this->tests;
1041 test = new_decision_test (DT_code, &place);
1042 test->u.code = code;
1045 if (mode != VOIDmode)
1047 place = &this->tests;
1048 test = new_decision_test (DT_mode, &place);
1049 test->u.mode = mode;
1052 /* If we didn't insert any tests or accept nodes, hork. */
1053 if (this->tests == NULL)
1054 abort ();
1056 ret:
1057 free (subpos);
1058 return sub;
1061 /* A subroutine of maybe_both_true; examines only one test.
1062 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1064 static int
1065 maybe_both_true_2 (d1, d2)
1066 struct decision_test *d1, *d2;
1068 if (d1->type == d2->type)
1070 switch (d1->type)
1072 case DT_mode:
1073 return d1->u.mode == d2->u.mode;
1075 case DT_code:
1076 return d1->u.code == d2->u.code;
1078 case DT_veclen:
1079 return d1->u.veclen == d2->u.veclen;
1081 case DT_elt_zero_int:
1082 case DT_elt_one_int:
1083 case DT_elt_zero_wide:
1084 case DT_elt_zero_wide_safe:
1085 return d1->u.intval == d2->u.intval;
1087 default:
1088 break;
1092 /* If either has a predicate that we know something about, set
1093 things up so that D1 is the one that always has a known
1094 predicate. Then see if they have any codes in common. */
1096 if (d1->type == DT_pred || d2->type == DT_pred)
1098 if (d2->type == DT_pred)
1100 struct decision_test *tmp;
1101 tmp = d1, d1 = d2, d2 = tmp;
1104 /* If D2 tests a mode, see if it matches D1. */
1105 if (d1->u.pred.mode != VOIDmode)
1107 if (d2->type == DT_mode)
1109 if (d1->u.pred.mode != d2->u.mode
1110 /* The mode of an address_operand predicate is the
1111 mode of the memory, not the operand. It can only
1112 be used for testing the predicate, so we must
1113 ignore it here. */
1114 && strcmp (d1->u.pred.name, "address_operand") != 0)
1115 return 0;
1117 /* Don't check two predicate modes here, because if both predicates
1118 accept CONST_INT, then both can still be true even if the modes
1119 are different. If they don't accept CONST_INT, there will be a
1120 separate DT_mode that will make maybe_both_true_1 return 0. */
1123 if (d1->u.pred.index >= 0)
1125 /* If D2 tests a code, see if it is in the list of valid
1126 codes for D1's predicate. */
1127 if (d2->type == DT_code)
1129 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1130 while (*c != 0)
1132 if (*c == d2->u.code)
1133 break;
1134 ++c;
1136 if (*c == 0)
1137 return 0;
1140 /* Otherwise see if the predicates have any codes in common. */
1141 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1143 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1144 int common = 0;
1146 while (*c1 != 0 && !common)
1148 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1149 while (*c2 != 0 && !common)
1151 common = (*c1 == *c2);
1152 ++c2;
1154 ++c1;
1157 if (!common)
1158 return 0;
1163 /* Tests vs veclen may be known when strict equality is involved. */
1164 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1165 return d1->u.veclen >= d2->u.veclen;
1166 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1167 return d2->u.veclen >= d1->u.veclen;
1169 return -1;
1172 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1173 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1175 static int
1176 maybe_both_true_1 (d1, d2)
1177 struct decision_test *d1, *d2;
1179 struct decision_test *t1, *t2;
1181 /* A match_operand with no predicate can match anything. Recognize
1182 this by the existence of a lone DT_accept_op test. */
1183 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1184 return 1;
1186 /* Eliminate pairs of tests while they can exactly match. */
1187 while (d1 && d2 && d1->type == d2->type)
1189 if (maybe_both_true_2 (d1, d2) == 0)
1190 return 0;
1191 d1 = d1->next, d2 = d2->next;
1194 /* After that, consider all pairs. */
1195 for (t1 = d1; t1 ; t1 = t1->next)
1196 for (t2 = d2; t2 ; t2 = t2->next)
1197 if (maybe_both_true_2 (t1, t2) == 0)
1198 return 0;
1200 return -1;
1203 /* Return 0 if we can prove that there is no RTL that can match both
1204 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1205 can match both or just that we couldn't prove there wasn't such an RTL).
1207 TOPLEVEL is nonzero if we are to only look at the top level and not
1208 recursively descend. */
1210 static int
1211 maybe_both_true (d1, d2, toplevel)
1212 struct decision *d1, *d2;
1213 int toplevel;
1215 struct decision *p1, *p2;
1216 int cmp;
1218 /* Don't compare strings on the different positions in insn. Doing so
1219 is incorrect and results in false matches from constructs like
1221 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1222 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1224 [(set (match_operand:HI "register_operand" "r")
1225 (match_operand:HI "register_operand" "r"))]
1227 If we are presented with such, we are recursing through the remainder
1228 of a node's success nodes (from the loop at the end of this function).
1229 Skip forward until we come to a position that matches.
1231 Due to the way position strings are constructed, we know that iterating
1232 forward from the lexically lower position (e.g. "00") will run into
1233 the lexically higher position (e.g. "1") and not the other way around.
1234 This saves a bit of effort. */
1236 cmp = strcmp (d1->position, d2->position);
1237 if (cmp != 0)
1239 if (toplevel)
1240 abort ();
1242 /* If the d2->position was lexically lower, swap. */
1243 if (cmp > 0)
1244 p1 = d1, d1 = d2, d2 = p1;
1246 if (d1->success.first == 0)
1247 return 1;
1248 for (p1 = d1->success.first; p1; p1 = p1->next)
1249 if (maybe_both_true (p1, d2, 0))
1250 return 1;
1252 return 0;
1255 /* Test the current level. */
1256 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1257 if (cmp >= 0)
1258 return cmp;
1260 /* We can't prove that D1 and D2 cannot both be true. If we are only
1261 to check the top level, return 1. Otherwise, see if we can prove
1262 that all choices in both successors are mutually exclusive. If
1263 either does not have any successors, we can't prove they can't both
1264 be true. */
1266 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1267 return 1;
1269 for (p1 = d1->success.first; p1; p1 = p1->next)
1270 for (p2 = d2->success.first; p2; p2 = p2->next)
1271 if (maybe_both_true (p1, p2, 0))
1272 return 1;
1274 return 0;
1277 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1279 static int
1280 nodes_identical_1 (d1, d2)
1281 struct decision_test *d1, *d2;
1283 switch (d1->type)
1285 case DT_mode:
1286 return d1->u.mode == d2->u.mode;
1288 case DT_code:
1289 return d1->u.code == d2->u.code;
1291 case DT_pred:
1292 return (d1->u.pred.mode == d2->u.pred.mode
1293 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1295 case DT_c_test:
1296 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1298 case DT_veclen:
1299 case DT_veclen_ge:
1300 return d1->u.veclen == d2->u.veclen;
1302 case DT_dup:
1303 return d1->u.dup == d2->u.dup;
1305 case DT_elt_zero_int:
1306 case DT_elt_one_int:
1307 case DT_elt_zero_wide:
1308 case DT_elt_zero_wide_safe:
1309 return d1->u.intval == d2->u.intval;
1311 case DT_accept_op:
1312 return d1->u.opno == d2->u.opno;
1314 case DT_accept_insn:
1315 /* Differences will be handled in merge_accept_insn. */
1316 return 1;
1318 default:
1319 abort ();
1323 /* True iff the two nodes are identical (on one level only). Due
1324 to the way these lists are constructed, we shouldn't have to
1325 consider different orderings on the tests. */
1327 static int
1328 nodes_identical (d1, d2)
1329 struct decision *d1, *d2;
1331 struct decision_test *t1, *t2;
1333 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1335 if (t1->type != t2->type)
1336 return 0;
1337 if (! nodes_identical_1 (t1, t2))
1338 return 0;
1341 /* For success, they should now both be null. */
1342 if (t1 != t2)
1343 return 0;
1345 /* Check that their subnodes are at the same position, as any one set
1346 of sibling decisions must be at the same position. Allowing this
1347 requires complications to find_afterward and when change_state is
1348 invoked. */
1349 if (d1->success.first
1350 && d2->success.first
1351 && strcmp (d1->success.first->position, d2->success.first->position))
1352 return 0;
1354 return 1;
1357 /* A subroutine of merge_trees; given two nodes that have been declared
1358 identical, cope with two insn accept states. If they differ in the
1359 number of clobbers, then the conflict was created by make_insn_sequence
1360 and we can drop the with-clobbers version on the floor. If both
1361 nodes have no additional clobbers, we have found an ambiguity in the
1362 source machine description. */
1364 static void
1365 merge_accept_insn (oldd, addd)
1366 struct decision *oldd, *addd;
1368 struct decision_test *old, *add;
1370 for (old = oldd->tests; old; old = old->next)
1371 if (old->type == DT_accept_insn)
1372 break;
1373 if (old == NULL)
1374 return;
1376 for (add = addd->tests; add; add = add->next)
1377 if (add->type == DT_accept_insn)
1378 break;
1379 if (add == NULL)
1380 return;
1382 /* If one node is for a normal insn and the second is for the base
1383 insn with clobbers stripped off, the second node should be ignored. */
1385 if (old->u.insn.num_clobbers_to_add == 0
1386 && add->u.insn.num_clobbers_to_add > 0)
1388 /* Nothing to do here. */
1390 else if (old->u.insn.num_clobbers_to_add > 0
1391 && add->u.insn.num_clobbers_to_add == 0)
1393 /* In this case, replace OLD with ADD. */
1394 old->u.insn = add->u.insn;
1396 else
1398 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1399 get_insn_name (add->u.insn.code_number),
1400 get_insn_name (old->u.insn.code_number));
1401 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1402 get_insn_name (old->u.insn.code_number));
1403 error_count++;
1407 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1409 static void
1410 merge_trees (oldh, addh)
1411 struct decision_head *oldh, *addh;
1413 struct decision *next, *add;
1415 if (addh->first == 0)
1416 return;
1417 if (oldh->first == 0)
1419 *oldh = *addh;
1420 return;
1423 /* Trying to merge bits at different positions isn't possible. */
1424 if (strcmp (oldh->first->position, addh->first->position))
1425 abort ();
1427 for (add = addh->first; add ; add = next)
1429 struct decision *old, *insert_before = NULL;
1431 next = add->next;
1433 /* The semantics of pattern matching state that the tests are
1434 done in the order given in the MD file so that if an insn
1435 matches two patterns, the first one will be used. However,
1436 in practice, most, if not all, patterns are unambiguous so
1437 that their order is independent. In that case, we can merge
1438 identical tests and group all similar modes and codes together.
1440 Scan starting from the end of OLDH until we reach a point
1441 where we reach the head of the list or where we pass a
1442 pattern that could also be true if NEW is true. If we find
1443 an identical pattern, we can merge them. Also, record the
1444 last node that tests the same code and mode and the last one
1445 that tests just the same mode.
1447 If we have no match, place NEW after the closest match we found. */
1449 for (old = oldh->last; old; old = old->prev)
1451 if (nodes_identical (old, add))
1453 merge_accept_insn (old, add);
1454 merge_trees (&old->success, &add->success);
1455 goto merged_nodes;
1458 if (maybe_both_true (old, add, 0))
1459 break;
1461 /* Insert the nodes in DT test type order, which is roughly
1462 how expensive/important the test is. Given that the tests
1463 are also ordered within the list, examining the first is
1464 sufficient. */
1465 if ((int) add->tests->type < (int) old->tests->type)
1466 insert_before = old;
1469 if (insert_before == NULL)
1471 add->next = NULL;
1472 add->prev = oldh->last;
1473 oldh->last->next = add;
1474 oldh->last = add;
1476 else
1478 if ((add->prev = insert_before->prev) != NULL)
1479 add->prev->next = add;
1480 else
1481 oldh->first = add;
1482 add->next = insert_before;
1483 insert_before->prev = add;
1486 merged_nodes:;
1490 /* Walk the tree looking for sub-nodes that perform common tests.
1491 Factor out the common test into a new node. This enables us
1492 (depending on the test type) to emit switch statements later. */
1494 static void
1495 factor_tests (head)
1496 struct decision_head *head;
1498 struct decision *first, *next;
1500 for (first = head->first; first && first->next; first = next)
1502 enum decision_type type;
1503 struct decision *new, *old_last;
1505 type = first->tests->type;
1506 next = first->next;
1508 /* Want at least two compatible sequential nodes. */
1509 if (next->tests->type != type)
1510 continue;
1512 /* Don't want all node types, just those we can turn into
1513 switch statements. */
1514 if (type != DT_mode
1515 && type != DT_code
1516 && type != DT_veclen
1517 && type != DT_elt_zero_int
1518 && type != DT_elt_one_int
1519 && type != DT_elt_zero_wide_safe)
1520 continue;
1522 /* If we'd been performing more than one test, create a new node
1523 below our first test. */
1524 if (first->tests->next != NULL)
1526 new = new_decision (first->position, &first->success);
1527 new->tests = first->tests->next;
1528 first->tests->next = NULL;
1531 /* Crop the node tree off after our first test. */
1532 first->next = NULL;
1533 old_last = head->last;
1534 head->last = first;
1536 /* For each compatible test, adjust to perform only one test in
1537 the top level node, then merge the node back into the tree. */
1540 struct decision_head h;
1542 if (next->tests->next != NULL)
1544 new = new_decision (next->position, &next->success);
1545 new->tests = next->tests->next;
1546 next->tests->next = NULL;
1548 new = next;
1549 next = next->next;
1550 new->next = NULL;
1551 h.first = h.last = new;
1553 merge_trees (head, &h);
1555 while (next && next->tests->type == type);
1557 /* After we run out of compatible tests, graft the remaining nodes
1558 back onto the tree. */
1559 if (next)
1561 next->prev = head->last;
1562 head->last->next = next;
1563 head->last = old_last;
1567 /* Recurse. */
1568 for (first = head->first; first; first = first->next)
1569 factor_tests (&first->success);
1572 /* After factoring, try to simplify the tests on any one node.
1573 Tests that are useful for switch statements are recognizable
1574 by having only a single test on a node -- we'll be manipulating
1575 nodes with multiple tests:
1577 If we have mode tests or code tests that are redundant with
1578 predicates, remove them. */
1580 static void
1581 simplify_tests (head)
1582 struct decision_head *head;
1584 struct decision *tree;
1586 for (tree = head->first; tree; tree = tree->next)
1588 struct decision_test *a, *b;
1590 a = tree->tests;
1591 b = a->next;
1592 if (b == NULL)
1593 continue;
1595 /* Find a predicate node. */
1596 while (b && b->type != DT_pred)
1597 b = b->next;
1598 if (b)
1600 /* Due to how these tests are constructed, we don't even need
1601 to check that the mode and code are compatible -- they were
1602 generated from the predicate in the first place. */
1603 while (a->type == DT_mode || a->type == DT_code)
1604 a = a->next;
1605 tree->tests = a;
1609 /* Recurse. */
1610 for (tree = head->first; tree; tree = tree->next)
1611 simplify_tests (&tree->success);
1614 /* Count the number of subnodes of HEAD. If the number is high enough,
1615 make the first node in HEAD start a separate subroutine in the C code
1616 that is generated. */
1618 static int
1619 break_out_subroutines (head, initial)
1620 struct decision_head *head;
1621 int initial;
1623 int size = 0;
1624 struct decision *sub;
1626 for (sub = head->first; sub; sub = sub->next)
1627 size += 1 + break_out_subroutines (&sub->success, 0);
1629 if (size > SUBROUTINE_THRESHOLD && ! initial)
1631 head->first->subroutine_number = ++next_subroutine_number;
1632 size = 1;
1634 return size;
1637 /* For each node p, find the next alternative that might be true
1638 when p is true. */
1640 static void
1641 find_afterward (head, real_afterward)
1642 struct decision_head *head;
1643 struct decision *real_afterward;
1645 struct decision *p, *q, *afterward;
1647 /* We can't propagate alternatives across subroutine boundaries.
1648 This is not incorrect, merely a minor optimization loss. */
1650 p = head->first;
1651 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1653 for ( ; p ; p = p->next)
1655 /* Find the next node that might be true if this one fails. */
1656 for (q = p->next; q ; q = q->next)
1657 if (maybe_both_true (p, q, 1))
1658 break;
1660 /* If we reached the end of the list without finding one,
1661 use the incoming afterward position. */
1662 if (!q)
1663 q = afterward;
1664 p->afterward = q;
1665 if (q)
1666 q->need_label = 1;
1669 /* Recurse. */
1670 for (p = head->first; p ; p = p->next)
1671 if (p->success.first)
1672 find_afterward (&p->success, p->afterward);
1674 /* When we are generating a subroutine, record the real afterward
1675 position in the first node where write_tree can find it, and we
1676 can do the right thing at the subroutine call site. */
1677 p = head->first;
1678 if (p->subroutine_number > 0)
1679 p->afterward = real_afterward;
1682 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1683 actions are necessary to move to NEWPOS. If we fail to move to the
1684 new state, branch to node AFTERWARD if nonzero, otherwise return.
1686 Failure to move to the new state can only occur if we are trying to
1687 match multiple insns and we try to step past the end of the stream. */
1689 static void
1690 change_state (oldpos, newpos, afterward, indent)
1691 const char *oldpos;
1692 const char *newpos;
1693 struct decision *afterward;
1694 const char *indent;
1696 int odepth = strlen (oldpos);
1697 int ndepth = strlen (newpos);
1698 int depth;
1699 int old_has_insn, new_has_insn;
1701 /* Pop up as many levels as necessary. */
1702 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1703 continue;
1705 /* Hunt for the last [A-Z] in both strings. */
1706 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1707 if (ISUPPER (oldpos[old_has_insn]))
1708 break;
1709 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1710 if (ISUPPER (newpos[new_has_insn]))
1711 break;
1713 /* Go down to desired level. */
1714 while (depth < ndepth)
1716 /* It's a different insn from the first one. */
1717 if (ISUPPER (newpos[depth]))
1719 /* We can only fail if we're moving down the tree. */
1720 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1722 printf ("%stem = peep2_next_insn (%d);\n",
1723 indent, newpos[depth] - 'A');
1725 else
1727 printf ("%stem = peep2_next_insn (%d);\n",
1728 indent, newpos[depth] - 'A');
1729 printf ("%sif (tem == NULL_RTX)\n", indent);
1730 if (afterward)
1731 printf ("%s goto L%d;\n", indent, afterward->number);
1732 else
1733 printf ("%s goto ret0;\n", indent);
1735 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1737 else if (ISLOWER (newpos[depth]))
1738 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1739 indent, depth + 1, depth, newpos[depth] - 'a');
1740 else
1741 printf ("%sx%d = XEXP (x%d, %c);\n",
1742 indent, depth + 1, depth, newpos[depth]);
1743 ++depth;
1747 /* Print the enumerator constant for CODE -- the upcase version of
1748 the name. */
1750 static void
1751 print_code (code)
1752 enum rtx_code code;
1754 const char *p;
1755 for (p = GET_RTX_NAME (code); *p; p++)
1756 putchar (TOUPPER (*p));
1759 /* Emit code to cross an afterward link -- change state and branch. */
1761 static void
1762 write_afterward (start, afterward, indent)
1763 struct decision *start;
1764 struct decision *afterward;
1765 const char *indent;
1767 if (!afterward || start->subroutine_number > 0)
1768 printf("%sgoto ret0;\n", indent);
1769 else
1771 change_state (start->position, afterward->position, NULL, indent);
1772 printf ("%sgoto L%d;\n", indent, afterward->number);
1776 /* Emit a switch statement, if possible, for an initial sequence of
1777 nodes at START. Return the first node yet untested. */
1779 static struct decision *
1780 write_switch (start, depth)
1781 struct decision *start;
1782 int depth;
1784 struct decision *p = start;
1785 enum decision_type type = p->tests->type;
1786 struct decision *needs_label = NULL;
1788 /* If we have two or more nodes in sequence that test the same one
1789 thing, we may be able to use a switch statement. */
1791 if (!p->next
1792 || p->tests->next
1793 || p->next->tests->type != type
1794 || p->next->tests->next
1795 || nodes_identical_1 (p->tests, p->next->tests))
1796 return p;
1798 /* DT_code is special in that we can do interesting things with
1799 known predicates at the same time. */
1800 if (type == DT_code)
1802 char codemap[NUM_RTX_CODE];
1803 struct decision *ret;
1804 RTX_CODE code;
1806 memset (codemap, 0, sizeof(codemap));
1808 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1809 code = p->tests->u.code;
1812 if (p != start && p->need_label && needs_label == NULL)
1813 needs_label = p;
1815 printf (" case ");
1816 print_code (code);
1817 printf (":\n goto L%d;\n", p->success.first->number);
1818 p->success.first->need_label = 1;
1820 codemap[code] = 1;
1821 p = p->next;
1823 while (p
1824 && ! p->tests->next
1825 && p->tests->type == DT_code
1826 && ! codemap[code = p->tests->u.code]);
1828 /* If P is testing a predicate that we know about and we haven't
1829 seen any of the codes that are valid for the predicate, we can
1830 write a series of "case" statement, one for each possible code.
1831 Since we are already in a switch, these redundant tests are very
1832 cheap and will reduce the number of predicates called. */
1834 /* Note that while we write out cases for these predicates here,
1835 we don't actually write the test here, as it gets kinda messy.
1836 It is trivial to leave this to later by telling our caller that
1837 we only processed the CODE tests. */
1838 if (needs_label != NULL)
1839 ret = needs_label;
1840 else
1841 ret = p;
1843 while (p && p->tests->type == DT_pred
1844 && p->tests->u.pred.index >= 0)
1846 const RTX_CODE *c;
1848 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1849 if (codemap[(int) *c] != 0)
1850 goto pred_done;
1852 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1854 printf (" case ");
1855 print_code (*c);
1856 printf (":\n");
1857 codemap[(int) *c] = 1;
1860 printf (" goto L%d;\n", p->number);
1861 p->need_label = 1;
1862 p = p->next;
1865 pred_done:
1866 /* Make the default case skip the predicates we managed to match. */
1868 printf (" default:\n");
1869 if (p != ret)
1871 if (p)
1873 printf (" goto L%d;\n", p->number);
1874 p->need_label = 1;
1876 else
1877 write_afterward (start, start->afterward, " ");
1879 else
1880 printf (" break;\n");
1881 printf (" }\n");
1883 return ret;
1885 else if (type == DT_mode
1886 || type == DT_veclen
1887 || type == DT_elt_zero_int
1888 || type == DT_elt_one_int
1889 || type == DT_elt_zero_wide_safe)
1891 const char *indent = "";
1893 /* We cast switch parameter to integer, so we must ensure that the value
1894 fits. */
1895 if (type == DT_elt_zero_wide_safe)
1897 indent = " ";
1898 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1900 printf ("%s switch (", indent);
1901 switch (type)
1903 case DT_mode:
1904 printf ("GET_MODE (x%d)", depth);
1905 break;
1906 case DT_veclen:
1907 printf ("XVECLEN (x%d, 0)", depth);
1908 break;
1909 case DT_elt_zero_int:
1910 printf ("XINT (x%d, 0)", depth);
1911 break;
1912 case DT_elt_one_int:
1913 printf ("XINT (x%d, 1)", depth);
1914 break;
1915 case DT_elt_zero_wide_safe:
1916 /* Convert result of XWINT to int for portability since some C
1917 compilers won't do it and some will. */
1918 printf ("(int) XWINT (x%d, 0)", depth);
1919 break;
1920 default:
1921 abort ();
1923 printf (")\n%s {\n", indent);
1927 /* Merge trees will not unify identical nodes if their
1928 sub-nodes are at different levels. Thus we must check
1929 for duplicate cases. */
1930 struct decision *q;
1931 for (q = start; q != p; q = q->next)
1932 if (nodes_identical_1 (p->tests, q->tests))
1933 goto case_done;
1935 if (p != start && p->need_label && needs_label == NULL)
1936 needs_label = p;
1938 printf ("%s case ", indent);
1939 switch (type)
1941 case DT_mode:
1942 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1943 break;
1944 case DT_veclen:
1945 printf ("%d", p->tests->u.veclen);
1946 break;
1947 case DT_elt_zero_int:
1948 case DT_elt_one_int:
1949 case DT_elt_zero_wide:
1950 case DT_elt_zero_wide_safe:
1951 printf (HOST_WIDE_INT_PRINT_DEC_C, p->tests->u.intval);
1952 break;
1953 default:
1954 abort ();
1956 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1957 p->success.first->need_label = 1;
1959 p = p->next;
1961 while (p && p->tests->type == type && !p->tests->next);
1963 case_done:
1964 printf ("%s default:\n%s break;\n%s }\n",
1965 indent, indent, indent);
1967 return needs_label != NULL ? needs_label : p;
1969 else
1971 /* None of the other tests are amenable. */
1972 return p;
1976 /* Emit code for one test. */
1978 static void
1979 write_cond (p, depth, subroutine_type)
1980 struct decision_test *p;
1981 int depth;
1982 enum routine_type subroutine_type;
1984 switch (p->type)
1986 case DT_mode:
1987 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1988 break;
1990 case DT_code:
1991 printf ("GET_CODE (x%d) == ", depth);
1992 print_code (p->u.code);
1993 break;
1995 case DT_veclen:
1996 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1997 break;
1999 case DT_elt_zero_int:
2000 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
2001 break;
2003 case DT_elt_one_int:
2004 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
2005 break;
2007 case DT_elt_zero_wide:
2008 case DT_elt_zero_wide_safe:
2009 printf ("XWINT (x%d, 0) == ", depth);
2010 printf (HOST_WIDE_INT_PRINT_DEC_C, p->u.intval);
2011 break;
2013 case DT_veclen_ge:
2014 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2015 break;
2017 case DT_dup:
2018 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2019 break;
2021 case DT_pred:
2022 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2023 GET_MODE_NAME (p->u.pred.mode));
2024 break;
2026 case DT_c_test:
2027 printf ("(%s)", p->u.c_test);
2028 break;
2030 case DT_accept_insn:
2031 switch (subroutine_type)
2033 case RECOG:
2034 if (p->u.insn.num_clobbers_to_add == 0)
2035 abort ();
2036 printf ("pnum_clobbers != NULL");
2037 break;
2039 default:
2040 abort ();
2042 break;
2044 default:
2045 abort ();
2049 /* Emit code for one action. The previous tests have succeeded;
2050 TEST is the last of the chain. In the normal case we simply
2051 perform a state change. For the `accept' tests we must do more work. */
2053 static void
2054 write_action (p, test, depth, uncond, success, subroutine_type)
2055 struct decision *p;
2056 struct decision_test *test;
2057 int depth, uncond;
2058 struct decision *success;
2059 enum routine_type subroutine_type;
2061 const char *indent;
2062 int want_close = 0;
2064 if (uncond)
2065 indent = " ";
2066 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2068 fputs (" {\n", stdout);
2069 indent = " ";
2070 want_close = 1;
2072 else
2073 indent = " ";
2075 if (test->type == DT_accept_op)
2077 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2079 /* Only allow DT_accept_insn to follow. */
2080 if (test->next)
2082 test = test->next;
2083 if (test->type != DT_accept_insn)
2084 abort ();
2088 /* Sanity check that we're now at the end of the list of tests. */
2089 if (test->next)
2090 abort ();
2092 if (test->type == DT_accept_insn)
2094 switch (subroutine_type)
2096 case RECOG:
2097 if (test->u.insn.num_clobbers_to_add != 0)
2098 printf ("%s*pnum_clobbers = %d;\n",
2099 indent, test->u.insn.num_clobbers_to_add);
2100 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2101 break;
2103 case SPLIT:
2104 printf ("%sreturn gen_split_%d (operands);\n",
2105 indent, test->u.insn.code_number);
2106 break;
2108 case PEEPHOLE2:
2110 int match_len = 0, i;
2112 for (i = strlen (p->position) - 1; i >= 0; --i)
2113 if (ISUPPER (p->position[i]))
2115 match_len = p->position[i] - 'A';
2116 break;
2118 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2119 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2120 indent, test->u.insn.code_number);
2121 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2123 break;
2125 default:
2126 abort ();
2129 else
2131 printf("%sgoto L%d;\n", indent, success->number);
2132 success->need_label = 1;
2135 if (want_close)
2136 fputs (" }\n", stdout);
2139 /* Return 1 if the test is always true and has no fallthru path. Return -1
2140 if the test does have a fallthru path, but requires that the condition be
2141 terminated. Otherwise return 0 for a normal test. */
2142 /* ??? is_unconditional is a stupid name for a tri-state function. */
2144 static int
2145 is_unconditional (t, subroutine_type)
2146 struct decision_test *t;
2147 enum routine_type subroutine_type;
2149 if (t->type == DT_accept_op)
2150 return 1;
2152 if (t->type == DT_accept_insn)
2154 switch (subroutine_type)
2156 case RECOG:
2157 return (t->u.insn.num_clobbers_to_add == 0);
2158 case SPLIT:
2159 return 1;
2160 case PEEPHOLE2:
2161 return -1;
2162 default:
2163 abort ();
2167 return 0;
2170 /* Emit code for one node -- the conditional and the accompanying action.
2171 Return true if there is no fallthru path. */
2173 static int
2174 write_node (p, depth, subroutine_type)
2175 struct decision *p;
2176 int depth;
2177 enum routine_type subroutine_type;
2179 struct decision_test *test, *last_test;
2180 int uncond;
2182 last_test = test = p->tests;
2183 uncond = is_unconditional (test, subroutine_type);
2184 if (uncond == 0)
2186 printf (" if (");
2187 write_cond (test, depth, subroutine_type);
2189 while ((test = test->next) != NULL)
2191 int uncond2;
2193 last_test = test;
2194 uncond2 = is_unconditional (test, subroutine_type);
2195 if (uncond2 != 0)
2196 break;
2198 printf ("\n && ");
2199 write_cond (test, depth, subroutine_type);
2202 printf (")\n");
2205 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2207 return uncond > 0;
2210 /* Emit code for all of the sibling nodes of HEAD. */
2212 static void
2213 write_tree_1 (head, depth, subroutine_type)
2214 struct decision_head *head;
2215 int depth;
2216 enum routine_type subroutine_type;
2218 struct decision *p, *next;
2219 int uncond = 0;
2221 for (p = head->first; p ; p = next)
2223 /* The label for the first element was printed in write_tree. */
2224 if (p != head->first && p->need_label)
2225 OUTPUT_LABEL (" ", p->number);
2227 /* Attempt to write a switch statement for a whole sequence. */
2228 next = write_switch (p, depth);
2229 if (p != next)
2230 uncond = 0;
2231 else
2233 /* Failed -- fall back and write one node. */
2234 uncond = write_node (p, depth, subroutine_type);
2235 next = p->next;
2239 /* Finished with this chain. Close a fallthru path by branching
2240 to the afterward node. */
2241 if (! uncond)
2242 write_afterward (head->last, head->last->afterward, " ");
2245 /* Write out the decision tree starting at HEAD. PREVPOS is the
2246 position at the node that branched to this node. */
2248 static void
2249 write_tree (head, prevpos, type, initial)
2250 struct decision_head *head;
2251 const char *prevpos;
2252 enum routine_type type;
2253 int initial;
2255 struct decision *p = head->first;
2257 putchar ('\n');
2258 if (p->need_label)
2259 OUTPUT_LABEL (" ", p->number);
2261 if (! initial && p->subroutine_number > 0)
2263 static const char * const name_prefix[] = {
2264 "recog", "split", "peephole2"
2267 static const char * const call_suffix[] = {
2268 ", pnum_clobbers", "", ", _pmatch_len"
2271 /* This node has been broken out into a separate subroutine.
2272 Call it, test the result, and branch accordingly. */
2274 if (p->afterward)
2276 printf (" tem = %s_%d (x0, insn%s);\n",
2277 name_prefix[type], p->subroutine_number, call_suffix[type]);
2278 if (IS_SPLIT (type))
2279 printf (" if (tem != 0)\n return tem;\n");
2280 else
2281 printf (" if (tem >= 0)\n return tem;\n");
2283 change_state (p->position, p->afterward->position, NULL, " ");
2284 printf (" goto L%d;\n", p->afterward->number);
2286 else
2288 printf (" return %s_%d (x0, insn%s);\n",
2289 name_prefix[type], p->subroutine_number, call_suffix[type]);
2292 else
2294 int depth = strlen (p->position);
2296 change_state (prevpos, p->position, head->last->afterward, " ");
2297 write_tree_1 (head, depth, type);
2299 for (p = head->first; p; p = p->next)
2300 if (p->success.first)
2301 write_tree (&p->success, p->position, type, 0);
2305 /* Write out a subroutine of type TYPE to do comparisons starting at
2306 node TREE. */
2308 static void
2309 write_subroutine (head, type)
2310 struct decision_head *head;
2311 enum routine_type type;
2313 int subfunction = head->first ? head->first->subroutine_number : 0;
2314 const char *s_or_e;
2315 char extension[32];
2316 int i;
2318 s_or_e = subfunction ? "static " : "";
2320 if (subfunction)
2321 sprintf (extension, "_%d", subfunction);
2322 else if (type == RECOG)
2323 extension[0] = '\0';
2324 else
2325 strcpy (extension, "_insns");
2327 switch (type)
2329 case RECOG:
2330 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2331 printf ("%sint\n\
2332 recog%s (x0, insn, pnum_clobbers)\n\
2333 rtx x0 ATTRIBUTE_UNUSED;\n\
2334 rtx insn ATTRIBUTE_UNUSED;\n\
2335 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2336 break;
2337 case SPLIT:
2338 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2339 printf ("%srtx\n\
2340 split%s (x0, insn)\n\
2341 rtx x0 ATTRIBUTE_UNUSED;\n\
2342 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2343 break;
2344 case PEEPHOLE2:
2345 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2346 s_or_e, extension);
2347 printf ("%srtx\n\
2348 peephole2%s (x0, insn, _pmatch_len)\n\
2349 rtx x0 ATTRIBUTE_UNUSED;\n\
2350 rtx insn ATTRIBUTE_UNUSED;\n\
2351 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2352 break;
2355 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2356 for (i = 1; i <= max_depth; i++)
2357 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2359 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2361 if (!subfunction)
2362 printf (" recog_data.insn = NULL_RTX;\n");
2364 if (head->first)
2365 write_tree (head, "", type, 1);
2366 else
2367 printf (" goto ret0;\n");
2369 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2372 /* In break_out_subroutines, we discovered the boundaries for the
2373 subroutines, but did not write them out. Do so now. */
2375 static void
2376 write_subroutines (head, type)
2377 struct decision_head *head;
2378 enum routine_type type;
2380 struct decision *p;
2382 for (p = head->first; p ; p = p->next)
2383 if (p->success.first)
2384 write_subroutines (&p->success, type);
2386 if (head->first->subroutine_number > 0)
2387 write_subroutine (head, type);
2390 /* Begin the output file. */
2392 static void
2393 write_header ()
2395 puts ("\
2396 /* Generated automatically by the program `genrecog' from the target\n\
2397 machine description file. */\n\
2399 #include \"config.h\"\n\
2400 #include \"system.h\"\n\
2401 #include \"coretypes.h\"\n\
2402 #include \"tm.h\"\n\
2403 #include \"rtl.h\"\n\
2404 #include \"tm_p.h\"\n\
2405 #include \"function.h\"\n\
2406 #include \"insn-config.h\"\n\
2407 #include \"recog.h\"\n\
2408 #include \"real.h\"\n\
2409 #include \"output.h\"\n\
2410 #include \"flags.h\"\n\
2411 #include \"hard-reg-set.h\"\n\
2412 #include \"resource.h\"\n\
2413 #include \"toplev.h\"\n\
2414 #include \"reload.h\"\n\
2415 \n");
2417 puts ("\n\
2418 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2419 X0 is a valid instruction.\n\
2421 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2422 returns a nonnegative number which is the insn code number for the\n\
2423 pattern that matched. This is the same as the order in the machine\n\
2424 description of the entry that matched. This number can be used as an\n\
2425 index into `insn_data' and other tables.\n");
2426 puts ("\
2427 The third argument to recog is an optional pointer to an int. If\n\
2428 present, recog will accept a pattern if it matches except for missing\n\
2429 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2430 the optional pointer will be set to the number of CLOBBERs that need\n\
2431 to be added (it should be initialized to zero by the caller). If it");
2432 puts ("\
2433 is set nonzero, the caller should allocate a PARALLEL of the\n\
2434 appropriate size, copy the initial entries, and call add_clobbers\n\
2435 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2438 puts ("\n\
2439 The function split_insns returns 0 if the rtl could not\n\
2440 be split or the split rtl as an INSN list if it can be.\n\
2442 The function peephole2_insns returns 0 if the rtl could not\n\
2443 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2444 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2445 */\n\n");
2449 /* Construct and return a sequence of decisions
2450 that will recognize INSN.
2452 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2454 static struct decision_head
2455 make_insn_sequence (insn, type)
2456 rtx insn;
2457 enum routine_type type;
2459 rtx x;
2460 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2461 int truth = maybe_eval_c_test (c_test);
2462 struct decision *last;
2463 struct decision_test *test, **place;
2464 struct decision_head head;
2465 char c_test_pos[2];
2467 /* We should never see an insn whose C test is false at compile time. */
2468 if (truth == 0)
2469 abort ();
2471 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2473 c_test_pos[0] = '\0';
2474 if (type == PEEPHOLE2)
2476 int i, j;
2478 /* peephole2 gets special treatment:
2479 - X always gets an outer parallel even if it's only one entry
2480 - we remove all traces of outer-level match_scratch and match_dup
2481 expressions here. */
2482 x = rtx_alloc (PARALLEL);
2483 PUT_MODE (x, VOIDmode);
2484 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2485 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2487 rtx tmp = XVECEXP (insn, 0, i);
2488 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2490 XVECEXP (x, 0, j) = tmp;
2491 j++;
2494 XVECLEN (x, 0) = j;
2496 c_test_pos[0] = 'A' + j - 1;
2497 c_test_pos[1] = '\0';
2499 else if (XVECLEN (insn, type == RECOG) == 1)
2500 x = XVECEXP (insn, type == RECOG, 0);
2501 else
2503 x = rtx_alloc (PARALLEL);
2504 XVEC (x, 0) = XVEC (insn, type == RECOG);
2505 PUT_MODE (x, VOIDmode);
2508 validate_pattern (x, insn, NULL_RTX, 0);
2510 memset(&head, 0, sizeof(head));
2511 last = add_to_sequence (x, &head, "", type, 1);
2513 /* Find the end of the test chain on the last node. */
2514 for (test = last->tests; test->next; test = test->next)
2515 continue;
2516 place = &test->next;
2518 /* Skip the C test if it's known to be true at compile time. */
2519 if (truth == -1)
2521 /* Need a new node if we have another test to add. */
2522 if (test->type == DT_accept_op)
2524 last = new_decision (c_test_pos, &last->success);
2525 place = &last->tests;
2527 test = new_decision_test (DT_c_test, &place);
2528 test->u.c_test = c_test;
2531 test = new_decision_test (DT_accept_insn, &place);
2532 test->u.insn.code_number = next_insn_code;
2533 test->u.insn.lineno = pattern_lineno;
2534 test->u.insn.num_clobbers_to_add = 0;
2536 switch (type)
2538 case RECOG:
2539 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2540 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2541 If so, set up to recognize the pattern without these CLOBBERs. */
2543 if (GET_CODE (x) == PARALLEL)
2545 int i;
2547 /* Find the last non-clobber in the parallel. */
2548 for (i = XVECLEN (x, 0); i > 0; i--)
2550 rtx y = XVECEXP (x, 0, i - 1);
2551 if (GET_CODE (y) != CLOBBER
2552 || (GET_CODE (XEXP (y, 0)) != REG
2553 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2554 break;
2557 if (i != XVECLEN (x, 0))
2559 rtx new;
2560 struct decision_head clobber_head;
2562 /* Build a similar insn without the clobbers. */
2563 if (i == 1)
2564 new = XVECEXP (x, 0, 0);
2565 else
2567 int j;
2569 new = rtx_alloc (PARALLEL);
2570 XVEC (new, 0) = rtvec_alloc (i);
2571 for (j = i - 1; j >= 0; j--)
2572 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2575 /* Recognize it. */
2576 memset (&clobber_head, 0, sizeof(clobber_head));
2577 last = add_to_sequence (new, &clobber_head, "", type, 1);
2579 /* Find the end of the test chain on the last node. */
2580 for (test = last->tests; test->next; test = test->next)
2581 continue;
2583 /* We definitely have a new test to add -- create a new
2584 node if needed. */
2585 place = &test->next;
2586 if (test->type == DT_accept_op)
2588 last = new_decision ("", &last->success);
2589 place = &last->tests;
2592 /* Skip the C test if it's known to be true at compile
2593 time. */
2594 if (truth == -1)
2596 test = new_decision_test (DT_c_test, &place);
2597 test->u.c_test = c_test;
2600 test = new_decision_test (DT_accept_insn, &place);
2601 test->u.insn.code_number = next_insn_code;
2602 test->u.insn.lineno = pattern_lineno;
2603 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2605 merge_trees (&head, &clobber_head);
2608 break;
2610 case SPLIT:
2611 /* Define the subroutine we will call below and emit in genemit. */
2612 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2613 break;
2615 case PEEPHOLE2:
2616 /* Define the subroutine we will call below and emit in genemit. */
2617 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2618 next_insn_code);
2619 break;
2622 return head;
2625 static void
2626 process_tree (head, subroutine_type)
2627 struct decision_head *head;
2628 enum routine_type subroutine_type;
2630 if (head->first == NULL)
2632 /* We can elide peephole2_insns, but not recog or split_insns. */
2633 if (subroutine_type == PEEPHOLE2)
2634 return;
2636 else
2638 factor_tests (head);
2640 next_subroutine_number = 0;
2641 break_out_subroutines (head, 1);
2642 find_afterward (head, NULL);
2644 /* We run this after find_afterward, because find_afterward needs
2645 the redundant DT_mode tests on predicates to determine whether
2646 two tests can both be true or not. */
2647 simplify_tests(head);
2649 write_subroutines (head, subroutine_type);
2652 write_subroutine (head, subroutine_type);
2655 extern int main PARAMS ((int, char **));
2658 main (argc, argv)
2659 int argc;
2660 char **argv;
2662 rtx desc;
2663 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2665 progname = "genrecog";
2667 memset (&recog_tree, 0, sizeof recog_tree);
2668 memset (&split_tree, 0, sizeof split_tree);
2669 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2671 if (argc <= 1)
2672 fatal ("no input file name");
2674 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2675 return (FATAL_EXIT_CODE);
2677 next_insn_code = 0;
2678 next_index = 0;
2680 write_header ();
2682 /* Read the machine description. */
2684 while (1)
2686 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2687 if (desc == NULL)
2688 break;
2690 if (GET_CODE (desc) == DEFINE_INSN)
2692 h = make_insn_sequence (desc, RECOG);
2693 merge_trees (&recog_tree, &h);
2695 else if (GET_CODE (desc) == DEFINE_SPLIT)
2697 h = make_insn_sequence (desc, SPLIT);
2698 merge_trees (&split_tree, &h);
2700 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2702 h = make_insn_sequence (desc, PEEPHOLE2);
2703 merge_trees (&peephole2_tree, &h);
2706 next_index++;
2709 if (error_count)
2710 return FATAL_EXIT_CODE;
2712 puts ("\n\n");
2714 process_tree (&recog_tree, RECOG);
2715 process_tree (&split_tree, SPLIT);
2716 process_tree (&peephole2_tree, PEEPHOLE2);
2718 fflush (stdout);
2719 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2722 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2723 const char *
2724 get_insn_name (code)
2725 int code;
2727 if (code < insn_name_ptr_size)
2728 return insn_name_ptr[code];
2729 else
2730 return NULL;
2733 static void
2734 record_insn_name (code, name)
2735 int code;
2736 const char *name;
2738 static const char *last_real_name = "insn";
2739 static int last_real_code = 0;
2740 char *new;
2742 if (insn_name_ptr_size <= code)
2744 int new_size;
2745 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2746 insn_name_ptr =
2747 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2748 memset (insn_name_ptr + insn_name_ptr_size, 0,
2749 sizeof(char *) * (new_size - insn_name_ptr_size));
2750 insn_name_ptr_size = new_size;
2753 if (!name || name[0] == '\0')
2755 new = xmalloc (strlen (last_real_name) + 10);
2756 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2758 else
2760 last_real_name = new = xstrdup (name);
2761 last_real_code = code;
2764 insn_name_ptr[code] = new;
2767 static void
2768 debug_decision_2 (test)
2769 struct decision_test *test;
2771 switch (test->type)
2773 case DT_mode:
2774 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2775 break;
2776 case DT_code:
2777 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2778 break;
2779 case DT_veclen:
2780 fprintf (stderr, "veclen=%d", test->u.veclen);
2781 break;
2782 case DT_elt_zero_int:
2783 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2784 break;
2785 case DT_elt_one_int:
2786 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2787 break;
2788 case DT_elt_zero_wide:
2789 fprintf (stderr, "elt0_w=");
2790 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2791 break;
2792 case DT_elt_zero_wide_safe:
2793 fprintf (stderr, "elt0_ws=");
2794 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2795 break;
2796 case DT_veclen_ge:
2797 fprintf (stderr, "veclen>=%d", test->u.veclen);
2798 break;
2799 case DT_dup:
2800 fprintf (stderr, "dup=%d", test->u.dup);
2801 break;
2802 case DT_pred:
2803 fprintf (stderr, "pred=(%s,%s)",
2804 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2805 break;
2806 case DT_c_test:
2808 char sub[16+4];
2809 strncpy (sub, test->u.c_test, sizeof(sub));
2810 memcpy (sub+16, "...", 4);
2811 fprintf (stderr, "c_test=\"%s\"", sub);
2813 break;
2814 case DT_accept_op:
2815 fprintf (stderr, "A_op=%d", test->u.opno);
2816 break;
2817 case DT_accept_insn:
2818 fprintf (stderr, "A_insn=(%d,%d)",
2819 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2820 break;
2822 default:
2823 abort ();
2827 static void
2828 debug_decision_1 (d, indent)
2829 struct decision *d;
2830 int indent;
2832 int i;
2833 struct decision_test *test;
2835 if (d == NULL)
2837 for (i = 0; i < indent; ++i)
2838 putc (' ', stderr);
2839 fputs ("(nil)\n", stderr);
2840 return;
2843 for (i = 0; i < indent; ++i)
2844 putc (' ', stderr);
2846 putc ('{', stderr);
2847 test = d->tests;
2848 if (test)
2850 debug_decision_2 (test);
2851 while ((test = test->next) != NULL)
2853 fputs (" + ", stderr);
2854 debug_decision_2 (test);
2857 fprintf (stderr, "} %d n %d a %d\n", d->number,
2858 (d->next ? d->next->number : -1),
2859 (d->afterward ? d->afterward->number : -1));
2862 static void
2863 debug_decision_0 (d, indent, maxdepth)
2864 struct decision *d;
2865 int indent, maxdepth;
2867 struct decision *n;
2868 int i;
2870 if (maxdepth < 0)
2871 return;
2872 if (d == NULL)
2874 for (i = 0; i < indent; ++i)
2875 putc (' ', stderr);
2876 fputs ("(nil)\n", stderr);
2877 return;
2880 debug_decision_1 (d, indent);
2881 for (n = d->success.first; n ; n = n->next)
2882 debug_decision_0 (n, indent + 2, maxdepth - 1);
2885 void
2886 debug_decision (d)
2887 struct decision *d;
2889 debug_decision_0 (d, 0, 1000000);
2892 void
2893 debug_decision_list (d)
2894 struct decision *d;
2896 while (d)
2898 debug_decision_0 (d, 0, 0);
2899 d = d->next;