Remove some compile time warnings about duplicate definitions.
[official-gcc.git] / gcc / genrecog.c
blobfe1a42bbc5425ff40959978a0271e9c49b2ea378
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 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_mode
242 PARAMS ((enum machine_mode, enum machine_mode));
243 static int maybe_both_true_2
244 PARAMS ((struct decision_test *, struct decision_test *));
245 static int maybe_both_true_1
246 PARAMS ((struct decision_test *, struct decision_test *));
247 static int maybe_both_true
248 PARAMS ((struct decision *, struct decision *, int));
250 static int nodes_identical_1
251 PARAMS ((struct decision_test *, struct decision_test *));
252 static int nodes_identical
253 PARAMS ((struct decision *, struct decision *));
254 static void merge_accept_insn
255 PARAMS ((struct decision *, struct decision *));
256 static void merge_trees
257 PARAMS ((struct decision_head *, struct decision_head *));
259 static void factor_tests
260 PARAMS ((struct decision_head *));
261 static void simplify_tests
262 PARAMS ((struct decision_head *));
263 static int break_out_subroutines
264 PARAMS ((struct decision_head *, int));
265 static void find_afterward
266 PARAMS ((struct decision_head *, struct decision *));
268 static void change_state
269 PARAMS ((const char *, const char *, struct decision *, const char *));
270 static void print_code
271 PARAMS ((enum rtx_code));
272 static void write_afterward
273 PARAMS ((struct decision *, struct decision *, const char *));
274 static struct decision *write_switch
275 PARAMS ((struct decision *, int));
276 static void write_cond
277 PARAMS ((struct decision_test *, int, enum routine_type));
278 static void write_action
279 PARAMS ((struct decision *, struct decision_test *, int, int,
280 struct decision *, enum routine_type));
281 static int is_unconditional
282 PARAMS ((struct decision_test *, enum routine_type));
283 static int write_node
284 PARAMS ((struct decision *, int, enum routine_type));
285 static void write_tree_1
286 PARAMS ((struct decision_head *, int, enum routine_type));
287 static void write_tree
288 PARAMS ((struct decision_head *, const char *, enum routine_type, int));
289 static void write_subroutine
290 PARAMS ((struct decision_head *, enum routine_type));
291 static void write_subroutines
292 PARAMS ((struct decision_head *, enum routine_type));
293 static void write_header
294 PARAMS ((void));
296 static struct decision_head make_insn_sequence
297 PARAMS ((rtx, enum routine_type));
298 static void process_tree
299 PARAMS ((struct decision_head *, enum routine_type));
301 static void record_insn_name
302 PARAMS ((int, const char *));
304 static void debug_decision_0
305 PARAMS ((struct decision *, int, int));
306 static void debug_decision_1
307 PARAMS ((struct decision *, int));
308 static void debug_decision_2
309 PARAMS ((struct decision_test *));
310 extern void debug_decision
311 PARAMS ((struct decision *));
312 extern void debug_decision_list
313 PARAMS ((struct decision *));
315 /* Create a new node in sequence after LAST. */
317 static struct decision *
318 new_decision (position, last)
319 const char *position;
320 struct decision_head *last;
322 struct decision *new
323 = (struct decision *) xmalloc (sizeof (struct decision));
325 memset (new, 0, sizeof (*new));
326 new->success = *last;
327 new->position = xstrdup (position);
328 new->number = next_number++;
330 last->first = last->last = new;
331 return new;
334 /* Create a new test and link it in at PLACE. */
336 static struct decision_test *
337 new_decision_test (type, pplace)
338 enum decision_type type;
339 struct decision_test ***pplace;
341 struct decision_test **place = *pplace;
342 struct decision_test *test;
344 test = (struct decision_test *) xmalloc (sizeof (*test));
345 test->next = *place;
346 test->type = type;
347 *place = test;
349 place = &test->next;
350 *pplace = place;
352 return test;
355 /* Search for and return operand N. */
357 static rtx
358 find_operand (pattern, n)
359 rtx pattern;
360 int n;
362 const char *fmt;
363 RTX_CODE code;
364 int i, j, len;
365 rtx r;
367 code = GET_CODE (pattern);
368 if ((code == MATCH_SCRATCH
369 || code == MATCH_INSN
370 || code == MATCH_OPERAND
371 || code == MATCH_OPERATOR
372 || code == MATCH_PARALLEL)
373 && XINT (pattern, 0) == n)
374 return pattern;
376 fmt = GET_RTX_FORMAT (code);
377 len = GET_RTX_LENGTH (code);
378 for (i = 0; i < len; i++)
380 switch (fmt[i])
382 case 'e': case 'u':
383 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX)
384 return r;
385 break;
387 case 'V':
388 if (! XVEC (pattern, i))
389 break;
390 /* FALLTHRU */
392 case 'E':
393 for (j = 0; j < XVECLEN (pattern, i); j++)
394 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX)
395 return r;
396 break;
398 case 'i': case 'w': case '0': case 's':
399 break;
401 default:
402 abort ();
406 return NULL;
409 /* Search for and return operand M, such that it has a matching
410 constraint for operand N. */
412 static rtx
413 find_matching_operand (pattern, n)
414 rtx pattern;
415 int n;
417 const char *fmt;
418 RTX_CODE code;
419 int i, j, len;
420 rtx r;
422 code = GET_CODE (pattern);
423 if (code == MATCH_OPERAND
424 && (XSTR (pattern, 2)[0] == '0' + n
425 || (XSTR (pattern, 2)[0] == '%'
426 && XSTR (pattern, 2)[1] == '0' + n)))
427 return pattern;
429 fmt = GET_RTX_FORMAT (code);
430 len = GET_RTX_LENGTH (code);
431 for (i = 0; i < len; i++)
433 switch (fmt[i])
435 case 'e': case 'u':
436 if ((r = find_matching_operand (XEXP (pattern, i), n)))
437 return r;
438 break;
440 case 'V':
441 if (! XVEC (pattern, i))
442 break;
443 /* FALLTHRU */
445 case 'E':
446 for (j = 0; j < XVECLEN (pattern, i); j++)
447 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
448 return r;
449 break;
451 case 'i': case 'w': case '0': case 's':
452 break;
454 default:
455 abort ();
459 return NULL;
463 /* Check for various errors in patterns. SET is nonnull for a destination,
464 and is the complete set pattern. SET_CODE is '=' for normal sets, and
465 '+' within a context that requires in-out constraints. */
467 static void
468 validate_pattern (pattern, insn, set, set_code)
469 rtx pattern;
470 rtx insn;
471 rtx set;
472 int set_code;
474 const char *fmt;
475 RTX_CODE code;
476 size_t i, len;
477 int j;
479 code = GET_CODE (pattern);
480 switch (code)
482 case MATCH_SCRATCH:
483 return;
485 case MATCH_INSN:
486 case MATCH_OPERAND:
487 case MATCH_OPERATOR:
489 const char *pred_name = XSTR (pattern, 1);
490 int allows_non_lvalue = 1, allows_non_const = 1;
491 int special_mode_pred = 0;
492 const char *c_test;
494 if (GET_CODE (insn) == DEFINE_INSN)
495 c_test = XSTR (insn, 2);
496 else
497 c_test = XSTR (insn, 1);
499 if (pred_name[0] != 0)
501 for (i = 0; i < NUM_KNOWN_PREDS; i++)
502 if (! strcmp (preds[i].name, pred_name))
503 break;
505 if (i < NUM_KNOWN_PREDS)
507 int j;
509 allows_non_lvalue = allows_non_const = 0;
510 for (j = 0; preds[i].codes[j] != 0; j++)
512 RTX_CODE c = preds[i].codes[j];
513 if (c != LABEL_REF
514 && c != SYMBOL_REF
515 && c != CONST_INT
516 && c != CONST_DOUBLE
517 && c != CONST
518 && c != HIGH
519 && c != CONSTANT_P_RTX)
520 allows_non_const = 1;
522 if (c != REG
523 && c != SUBREG
524 && c != MEM
525 && c != CONCAT
526 && c != PARALLEL
527 && c != STRICT_LOW_PART)
528 allows_non_lvalue = 1;
531 else
533 #ifdef PREDICATE_CODES
534 /* If the port has a list of the predicates it uses but
535 omits one, warn. */
536 message_with_line (pattern_lineno,
537 "warning: `%s' not in PREDICATE_CODES",
538 pred_name);
539 #endif
542 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
543 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
545 special_mode_pred = 1;
546 break;
550 if (code == MATCH_OPERAND)
552 const char constraints0 = XSTR (pattern, 2)[0];
554 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
555 don't use the MATCH_OPERAND constraint, only the predicate.
556 This is confusing to folks doing new ports, so help them
557 not make the mistake. */
558 if (GET_CODE (insn) == DEFINE_EXPAND
559 || GET_CODE (insn) == DEFINE_SPLIT
560 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
562 if (constraints0)
563 message_with_line (pattern_lineno,
564 "warning: constraints not supported in %s",
565 rtx_name[GET_CODE (insn)]);
568 /* A MATCH_OPERAND that is a SET should have an output reload. */
569 else if (set && constraints0)
571 if (set_code == '+')
573 if (constraints0 == '+')
575 /* If we've only got an output reload for this operand,
576 we'd better have a matching input operand. */
577 else if (constraints0 == '='
578 && find_matching_operand (insn, XINT (pattern, 0)))
580 else
582 message_with_line (pattern_lineno,
583 "operand %d missing in-out reload",
584 XINT (pattern, 0));
585 error_count++;
588 else if (constraints0 != '=' && constraints0 != '+')
590 message_with_line (pattern_lineno,
591 "operand %d missing output reload",
592 XINT (pattern, 0));
593 error_count++;
598 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
599 while not likely to occur at runtime, results in less efficient
600 code from insn-recog.c. */
601 if (set
602 && pred_name[0] != '\0'
603 && allows_non_lvalue)
605 message_with_line (pattern_lineno,
606 "warning: destination operand %d allows non-lvalue",
607 XINT (pattern, 0));
610 /* A modeless MATCH_OPERAND can be handy when we can
611 check for multiple modes in the c_test. In most other cases,
612 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
613 and PEEP2 can FAIL within the output pattern. Exclude
614 address_operand, since its mode is related to the mode of
615 the memory not the operand. Exclude the SET_DEST of a call
616 instruction, as that is a common idiom. */
618 if (GET_MODE (pattern) == VOIDmode
619 && code == MATCH_OPERAND
620 && GET_CODE (insn) == DEFINE_INSN
621 && allows_non_const
622 && ! special_mode_pred
623 && pred_name[0] != '\0'
624 && strcmp (pred_name, "address_operand") != 0
625 && strstr (c_test, "operands") == NULL
626 && ! (set
627 && GET_CODE (set) == SET
628 && GET_CODE (SET_SRC (set)) == CALL))
630 message_with_line (pattern_lineno,
631 "warning: operand %d missing mode?",
632 XINT (pattern, 0));
634 return;
637 case SET:
639 enum machine_mode dmode, smode;
640 rtx dest, src;
642 dest = SET_DEST (pattern);
643 src = SET_SRC (pattern);
645 /* STRICT_LOW_PART is a wrapper. Its argument is the real
646 destination, and it's mode should match the source. */
647 if (GET_CODE (dest) == STRICT_LOW_PART)
648 dest = XEXP (dest, 0);
650 /* Find the referant for a DUP. */
652 if (GET_CODE (dest) == MATCH_DUP
653 || GET_CODE (dest) == MATCH_OP_DUP
654 || GET_CODE (dest) == MATCH_PAR_DUP)
655 dest = find_operand (insn, XINT (dest, 0));
657 if (GET_CODE (src) == MATCH_DUP
658 || GET_CODE (src) == MATCH_OP_DUP
659 || GET_CODE (src) == MATCH_PAR_DUP)
660 src = find_operand (insn, XINT (src, 0));
662 dmode = GET_MODE (dest);
663 smode = GET_MODE (src);
665 /* The mode of an ADDRESS_OPERAND is the mode of the memory
666 reference, not the mode of the address. */
667 if (GET_CODE (src) == MATCH_OPERAND
668 && ! strcmp (XSTR (src, 1), "address_operand"))
671 /* The operands of a SET must have the same mode unless one
672 is VOIDmode. */
673 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
675 message_with_line (pattern_lineno,
676 "mode mismatch in set: %smode vs %smode",
677 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
678 error_count++;
681 /* If only one of the operands is VOIDmode, and PC or CC0 is
682 not involved, it's probably a mistake. */
683 else if (dmode != smode
684 && GET_CODE (dest) != PC
685 && GET_CODE (dest) != CC0
686 && GET_CODE (src) != PC
687 && GET_CODE (src) != CC0
688 && GET_CODE (src) != CONST_INT)
690 const char *which;
691 which = (dmode == VOIDmode ? "destination" : "source");
692 message_with_line (pattern_lineno,
693 "warning: %s missing a mode?", which);
696 if (dest != SET_DEST (pattern))
697 validate_pattern (dest, insn, pattern, '=');
698 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
699 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
700 return;
703 case CLOBBER:
704 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
705 return;
707 case ZERO_EXTRACT:
708 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
709 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
710 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
711 return;
713 case STRICT_LOW_PART:
714 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
715 return;
717 case LABEL_REF:
718 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
720 message_with_line (pattern_lineno,
721 "operand to label_ref %smode not VOIDmode",
722 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
723 error_count++;
725 break;
727 default:
728 break;
731 fmt = GET_RTX_FORMAT (code);
732 len = GET_RTX_LENGTH (code);
733 for (i = 0; i < len; i++)
735 switch (fmt[i])
737 case 'e': case 'u':
738 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
739 break;
741 case 'E':
742 for (j = 0; j < XVECLEN (pattern, i); j++)
743 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
744 break;
746 case 'i': case 'w': case '0': case 's':
747 break;
749 default:
750 abort ();
755 /* Create a chain of nodes to verify that an rtl expression matches
756 PATTERN.
758 LAST is a pointer to the listhead in the previous node in the chain (or
759 in the calling function, for the first node).
761 POSITION is the string representing the current position in the insn.
763 INSN_TYPE is the type of insn for which we are emitting code.
765 A pointer to the final node in the chain is returned. */
767 static struct decision *
768 add_to_sequence (pattern, last, position, insn_type, top)
769 rtx pattern;
770 struct decision_head *last;
771 const char *position;
772 enum routine_type insn_type;
773 int top;
775 RTX_CODE code;
776 struct decision *this, *sub;
777 struct decision_test *test;
778 struct decision_test **place;
779 char *subpos;
780 size_t i;
781 const char *fmt;
782 int depth = strlen (position);
783 int len;
784 enum machine_mode mode;
786 if (depth > max_depth)
787 max_depth = depth;
789 subpos = (char *) xmalloc (depth + 2);
790 strcpy (subpos, position);
791 subpos[depth + 1] = 0;
793 sub = this = new_decision (position, last);
794 place = &this->tests;
796 restart:
797 mode = GET_MODE (pattern);
798 code = GET_CODE (pattern);
800 switch (code)
802 case PARALLEL:
803 /* Toplevel peephole pattern. */
804 if (insn_type == PEEPHOLE2 && top)
806 /* We don't need the node we just created -- unlink it. */
807 last->first = last->last = NULL;
809 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
811 /* Which insn we're looking at is represented by A-Z. We don't
812 ever use 'A', however; it is always implied. */
814 subpos[depth] = (i > 0 ? 'A' + i : 0);
815 sub = add_to_sequence (XVECEXP (pattern, 0, i),
816 last, subpos, insn_type, 0);
817 last = &sub->success;
819 goto ret;
822 /* Else nothing special. */
823 break;
825 case MATCH_PARALLEL:
826 /* The explicit patterns within a match_parallel enforce a minimum
827 length on the vector. The match_parallel predicate may allow
828 for more elements. We do need to check for this minimum here
829 or the code generated to match the internals may reference data
830 beyond the end of the vector. */
831 test = new_decision_test (DT_veclen_ge, &place);
832 test->u.veclen = XVECLEN (pattern, 2);
833 /* FALLTHRU */
835 case MATCH_OPERAND:
836 case MATCH_SCRATCH:
837 case MATCH_OPERATOR:
838 case MATCH_INSN:
840 const char *pred_name;
841 RTX_CODE was_code = code;
842 int allows_const_int = 1;
844 if (code == MATCH_SCRATCH)
846 pred_name = "scratch_operand";
847 code = UNKNOWN;
849 else
851 pred_name = XSTR (pattern, 1);
852 if (code == MATCH_PARALLEL)
853 code = PARALLEL;
854 else
855 code = UNKNOWN;
858 if (pred_name[0] != 0)
860 test = new_decision_test (DT_pred, &place);
861 test->u.pred.name = pred_name;
862 test->u.pred.mode = mode;
864 /* See if we know about this predicate and save its number.
865 If we do, and it only accepts one code, note that fact.
867 If we know that the predicate does not allow CONST_INT,
868 we know that the only way the predicate can match is if
869 the modes match (here we use the kludge of relying on the
870 fact that "address_operand" accepts CONST_INT; otherwise,
871 it would have to be a special case), so we can test the
872 mode (but we need not). This fact should considerably
873 simplify the generated code. */
875 for (i = 0; i < NUM_KNOWN_PREDS; i++)
876 if (! strcmp (preds[i].name, pred_name))
877 break;
879 if (i < NUM_KNOWN_PREDS)
881 int j;
883 test->u.pred.index = i;
885 if (preds[i].codes[1] == 0 && code == UNKNOWN)
886 code = preds[i].codes[0];
888 allows_const_int = 0;
889 for (j = 0; preds[i].codes[j] != 0; j++)
890 if (preds[i].codes[j] == CONST_INT)
892 allows_const_int = 1;
893 break;
896 else
897 test->u.pred.index = -1;
900 /* Can't enforce a mode if we allow const_int. */
901 if (allows_const_int)
902 mode = VOIDmode;
904 /* Accept the operand, ie. record it in `operands'. */
905 test = new_decision_test (DT_accept_op, &place);
906 test->u.opno = XINT (pattern, 0);
908 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
910 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
911 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
913 subpos[depth] = i + base;
914 sub = add_to_sequence (XVECEXP (pattern, 2, i),
915 &sub->success, subpos, insn_type, 0);
918 goto fini;
921 case MATCH_OP_DUP:
922 code = UNKNOWN;
924 test = new_decision_test (DT_dup, &place);
925 test->u.dup = XINT (pattern, 0);
927 test = new_decision_test (DT_accept_op, &place);
928 test->u.opno = XINT (pattern, 0);
930 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
932 subpos[depth] = i + '0';
933 sub = add_to_sequence (XVECEXP (pattern, 1, i),
934 &sub->success, subpos, insn_type, 0);
936 goto fini;
938 case MATCH_DUP:
939 case MATCH_PAR_DUP:
940 code = UNKNOWN;
942 test = new_decision_test (DT_dup, &place);
943 test->u.dup = XINT (pattern, 0);
944 goto fini;
946 case ADDRESS:
947 pattern = XEXP (pattern, 0);
948 goto restart;
950 default:
951 break;
954 fmt = GET_RTX_FORMAT (code);
955 len = GET_RTX_LENGTH (code);
957 /* Do tests against the current node first. */
958 for (i = 0; i < (size_t) len; i++)
960 if (fmt[i] == 'i')
962 if (i == 0)
964 test = new_decision_test (DT_elt_zero_int, &place);
965 test->u.intval = XINT (pattern, i);
967 else if (i == 1)
969 test = new_decision_test (DT_elt_one_int, &place);
970 test->u.intval = XINT (pattern, i);
972 else
973 abort ();
975 else if (fmt[i] == 'w')
977 /* If this value actually fits in an int, we can use a switch
978 statement here, so indicate that. */
979 enum decision_type type
980 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
981 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
983 if (i != 0)
984 abort ();
986 test = new_decision_test (type, &place);
987 test->u.intval = XWINT (pattern, i);
989 else if (fmt[i] == 'E')
991 if (i != 0)
992 abort ();
994 test = new_decision_test (DT_veclen, &place);
995 test->u.veclen = XVECLEN (pattern, i);
999 /* Now test our sub-patterns. */
1000 for (i = 0; i < (size_t) len; i++)
1002 switch (fmt[i])
1004 case 'e': case 'u':
1005 subpos[depth] = '0' + i;
1006 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1007 subpos, insn_type, 0);
1008 break;
1010 case 'E':
1012 int j;
1013 for (j = 0; j < XVECLEN (pattern, i); j++)
1015 subpos[depth] = 'a' + j;
1016 sub = add_to_sequence (XVECEXP (pattern, i, j),
1017 &sub->success, subpos, insn_type, 0);
1019 break;
1022 case 'i': case 'w':
1023 /* Handled above. */
1024 break;
1025 case '0':
1026 break;
1028 default:
1029 abort ();
1033 fini:
1034 /* Insert nodes testing mode and code, if they're still relevant,
1035 before any of the nodes we may have added above. */
1036 if (code != UNKNOWN)
1038 place = &this->tests;
1039 test = new_decision_test (DT_code, &place);
1040 test->u.code = code;
1043 if (mode != VOIDmode)
1045 place = &this->tests;
1046 test = new_decision_test (DT_mode, &place);
1047 test->u.mode = mode;
1050 /* If we didn't insert any tests or accept nodes, hork. */
1051 if (this->tests == NULL)
1052 abort ();
1054 ret:
1055 free (subpos);
1056 return sub;
1059 /* A subroutine of maybe_both_true; compares two modes.
1060 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1062 static int
1063 maybe_both_true_mode (m1, m2)
1064 enum machine_mode m1, m2;
1066 enum mode_class other_mode_class;
1068 /* Pmode is not a distinct mode. We do know that it is
1069 either MODE_INT or MODE_PARTIAL_INT though. */
1070 if (m1 == Pmode)
1071 other_mode_class = GET_MODE_CLASS (m2);
1072 else if (m2 == Pmode)
1073 other_mode_class = GET_MODE_CLASS (m1);
1074 else
1075 return m1 == m2;
1077 return (other_mode_class == MODE_INT
1078 || other_mode_class == MODE_PARTIAL_INT
1079 ? -1 : 0);
1082 /* A subroutine of maybe_both_true; examines only one test.
1083 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1085 static int
1086 maybe_both_true_2 (d1, d2)
1087 struct decision_test *d1, *d2;
1089 if (d1->type == d2->type)
1091 switch (d1->type)
1093 case DT_mode:
1094 return maybe_both_true_mode (d1->u.mode, d2->u.mode);
1096 case DT_code:
1097 return d1->u.code == d2->u.code;
1099 case DT_veclen:
1100 return d1->u.veclen == d2->u.veclen;
1102 case DT_elt_zero_int:
1103 case DT_elt_one_int:
1104 case DT_elt_zero_wide:
1105 case DT_elt_zero_wide_safe:
1106 return d1->u.intval == d2->u.intval;
1108 default:
1109 break;
1113 /* If either has a predicate that we know something about, set
1114 things up so that D1 is the one that always has a known
1115 predicate. Then see if they have any codes in common. */
1117 if (d1->type == DT_pred || d2->type == DT_pred)
1119 if (d2->type == DT_pred)
1121 struct decision_test *tmp;
1122 tmp = d1, d1 = d2, d2 = tmp;
1125 /* If D2 tests a mode, see if it matches D1. */
1126 if (d1->u.pred.mode != VOIDmode)
1128 if (d2->type == DT_mode)
1130 if (maybe_both_true_mode (d1->u.pred.mode, d2->u.mode) == 0
1131 /* The mode of an address_operand predicate is the
1132 mode of the memory, not the operand. It can only
1133 be used for testing the predicate, so we must
1134 ignore it here. */
1135 && strcmp (d1->u.pred.name, "address_operand") != 0)
1136 return 0;
1138 /* Don't check two predicate modes here, because if both predicates
1139 accept CONST_INT, then both can still be true even if the modes
1140 are different. If they don't accept CONST_INT, there will be a
1141 separate DT_mode that will make maybe_both_true_1 return 0. */
1144 if (d1->u.pred.index >= 0)
1146 /* If D2 tests a code, see if it is in the list of valid
1147 codes for D1's predicate. */
1148 if (d2->type == DT_code)
1150 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1151 while (*c != 0)
1153 if (*c == d2->u.code)
1154 break;
1155 ++c;
1157 if (*c == 0)
1158 return 0;
1161 /* Otherwise see if the predicates have any codes in common. */
1162 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1164 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1165 int common = 0;
1167 while (*c1 != 0 && !common)
1169 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1170 while (*c2 != 0 && !common)
1172 common = (*c1 == *c2);
1173 ++c2;
1175 ++c1;
1178 if (!common)
1179 return 0;
1184 /* Tests vs veclen may be known when strict equality is involved. */
1185 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1186 return d1->u.veclen >= d2->u.veclen;
1187 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1188 return d2->u.veclen >= d1->u.veclen;
1190 return -1;
1193 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1194 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1196 static int
1197 maybe_both_true_1 (d1, d2)
1198 struct decision_test *d1, *d2;
1200 struct decision_test *t1, *t2;
1202 /* A match_operand with no predicate can match anything. Recognize
1203 this by the existence of a lone DT_accept_op test. */
1204 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1205 return 1;
1207 /* Eliminate pairs of tests while they can exactly match. */
1208 while (d1 && d2 && d1->type == d2->type)
1210 if (maybe_both_true_2 (d1, d2) == 0)
1211 return 0;
1212 d1 = d1->next, d2 = d2->next;
1215 /* After that, consider all pairs. */
1216 for (t1 = d1; t1 ; t1 = t1->next)
1217 for (t2 = d2; t2 ; t2 = t2->next)
1218 if (maybe_both_true_2 (t1, t2) == 0)
1219 return 0;
1221 return -1;
1224 /* Return 0 if we can prove that there is no RTL that can match both
1225 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1226 can match both or just that we couldn't prove there wasn't such an RTL).
1228 TOPLEVEL is non-zero if we are to only look at the top level and not
1229 recursively descend. */
1231 static int
1232 maybe_both_true (d1, d2, toplevel)
1233 struct decision *d1, *d2;
1234 int toplevel;
1236 struct decision *p1, *p2;
1237 int cmp;
1239 /* Don't compare strings on the different positions in insn. Doing so
1240 is incorrect and results in false matches from constructs like
1242 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1243 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1245 [(set (match_operand:HI "register_operand" "r")
1246 (match_operand:HI "register_operand" "r"))]
1248 If we are presented with such, we are recursing through the remainder
1249 of a node's success nodes (from the loop at the end of this function).
1250 Skip forward until we come to a position that matches.
1252 Due to the way position strings are constructed, we know that iterating
1253 forward from the lexically lower position (e.g. "00") will run into
1254 the lexically higher position (e.g. "1") and not the other way around.
1255 This saves a bit of effort. */
1257 cmp = strcmp (d1->position, d2->position);
1258 if (cmp != 0)
1260 if (toplevel)
1261 abort();
1263 /* If the d2->position was lexically lower, swap. */
1264 if (cmp > 0)
1265 p1 = d1, d1 = d2, d2 = p1;
1267 if (d1->success.first == 0)
1268 return 1;
1269 for (p1 = d1->success.first; p1; p1 = p1->next)
1270 if (maybe_both_true (p1, d2, 0))
1271 return 1;
1273 return 0;
1276 /* Test the current level. */
1277 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1278 if (cmp >= 0)
1279 return cmp;
1281 /* We can't prove that D1 and D2 cannot both be true. If we are only
1282 to check the top level, return 1. Otherwise, see if we can prove
1283 that all choices in both successors are mutually exclusive. If
1284 either does not have any successors, we can't prove they can't both
1285 be true. */
1287 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1288 return 1;
1290 for (p1 = d1->success.first; p1; p1 = p1->next)
1291 for (p2 = d2->success.first; p2; p2 = p2->next)
1292 if (maybe_both_true (p1, p2, 0))
1293 return 1;
1295 return 0;
1298 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1300 static int
1301 nodes_identical_1 (d1, d2)
1302 struct decision_test *d1, *d2;
1304 switch (d1->type)
1306 case DT_mode:
1307 return d1->u.mode == d2->u.mode;
1309 case DT_code:
1310 return d1->u.code == d2->u.code;
1312 case DT_pred:
1313 return (d1->u.pred.mode == d2->u.pred.mode
1314 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1316 case DT_c_test:
1317 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1319 case DT_veclen:
1320 case DT_veclen_ge:
1321 return d1->u.veclen == d2->u.veclen;
1323 case DT_dup:
1324 return d1->u.dup == d2->u.dup;
1326 case DT_elt_zero_int:
1327 case DT_elt_one_int:
1328 case DT_elt_zero_wide:
1329 case DT_elt_zero_wide_safe:
1330 return d1->u.intval == d2->u.intval;
1332 case DT_accept_op:
1333 return d1->u.opno == d2->u.opno;
1335 case DT_accept_insn:
1336 /* Differences will be handled in merge_accept_insn. */
1337 return 1;
1339 default:
1340 abort ();
1344 /* True iff the two nodes are identical (on one level only). Due
1345 to the way these lists are constructed, we shouldn't have to
1346 consider different orderings on the tests. */
1348 static int
1349 nodes_identical (d1, d2)
1350 struct decision *d1, *d2;
1352 struct decision_test *t1, *t2;
1354 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1356 if (t1->type != t2->type)
1357 return 0;
1358 if (! nodes_identical_1 (t1, t2))
1359 return 0;
1362 /* For success, they should now both be null. */
1363 if (t1 != t2)
1364 return 0;
1366 /* Check that their subnodes are at the same position, as any one set
1367 of sibling decisions must be at the same position. Allowing this
1368 requires complications to find_afterward and when change_state is
1369 invoked. */
1370 if (d1->success.first
1371 && d2->success.first
1372 && strcmp (d1->success.first->position, d2->success.first->position))
1373 return 0;
1375 return 1;
1378 /* A subroutine of merge_trees; given two nodes that have been declared
1379 identical, cope with two insn accept states. If they differ in the
1380 number of clobbers, then the conflict was created by make_insn_sequence
1381 and we can drop the with-clobbers version on the floor. If both
1382 nodes have no additional clobbers, we have found an ambiguity in the
1383 source machine description. */
1385 static void
1386 merge_accept_insn (oldd, addd)
1387 struct decision *oldd, *addd;
1389 struct decision_test *old, *add;
1391 for (old = oldd->tests; old; old = old->next)
1392 if (old->type == DT_accept_insn)
1393 break;
1394 if (old == NULL)
1395 return;
1397 for (add = addd->tests; add; add = add->next)
1398 if (add->type == DT_accept_insn)
1399 break;
1400 if (add == NULL)
1401 return;
1403 /* If one node is for a normal insn and the second is for the base
1404 insn with clobbers stripped off, the second node should be ignored. */
1406 if (old->u.insn.num_clobbers_to_add == 0
1407 && add->u.insn.num_clobbers_to_add > 0)
1409 /* Nothing to do here. */
1411 else if (old->u.insn.num_clobbers_to_add > 0
1412 && add->u.insn.num_clobbers_to_add == 0)
1414 /* In this case, replace OLD with ADD. */
1415 old->u.insn = add->u.insn;
1417 else
1419 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1420 get_insn_name (add->u.insn.code_number),
1421 get_insn_name (old->u.insn.code_number));
1422 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1423 get_insn_name (old->u.insn.code_number));
1424 error_count++;
1428 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1430 static void
1431 merge_trees (oldh, addh)
1432 struct decision_head *oldh, *addh;
1434 struct decision *next, *add;
1436 if (addh->first == 0)
1437 return;
1438 if (oldh->first == 0)
1440 *oldh = *addh;
1441 return;
1444 /* Trying to merge bits at different positions isn't possible. */
1445 if (strcmp (oldh->first->position, addh->first->position))
1446 abort ();
1448 for (add = addh->first; add ; add = next)
1450 struct decision *old, *insert_before = NULL;
1452 next = add->next;
1454 /* The semantics of pattern matching state that the tests are
1455 done in the order given in the MD file so that if an insn
1456 matches two patterns, the first one will be used. However,
1457 in practice, most, if not all, patterns are unambiguous so
1458 that their order is independent. In that case, we can merge
1459 identical tests and group all similar modes and codes together.
1461 Scan starting from the end of OLDH until we reach a point
1462 where we reach the head of the list or where we pass a
1463 pattern that could also be true if NEW is true. If we find
1464 an identical pattern, we can merge them. Also, record the
1465 last node that tests the same code and mode and the last one
1466 that tests just the same mode.
1468 If we have no match, place NEW after the closest match we found. */
1470 for (old = oldh->last; old; old = old->prev)
1472 if (nodes_identical (old, add))
1474 merge_accept_insn (old, add);
1475 merge_trees (&old->success, &add->success);
1476 goto merged_nodes;
1479 if (maybe_both_true (old, add, 0))
1480 break;
1482 /* Insert the nodes in DT test type order, which is roughly
1483 how expensive/important the test is. Given that the tests
1484 are also ordered within the list, examining the first is
1485 sufficient. */
1486 if ((int) add->tests->type < (int) old->tests->type)
1487 insert_before = old;
1490 if (insert_before == NULL)
1492 add->next = NULL;
1493 add->prev = oldh->last;
1494 oldh->last->next = add;
1495 oldh->last = add;
1497 else
1499 if ((add->prev = insert_before->prev) != NULL)
1500 add->prev->next = add;
1501 else
1502 oldh->first = add;
1503 add->next = insert_before;
1504 insert_before->prev = add;
1507 merged_nodes:;
1511 /* Walk the tree looking for sub-nodes that perform common tests.
1512 Factor out the common test into a new node. This enables us
1513 (depending on the test type) to emit switch statements later. */
1515 static void
1516 factor_tests (head)
1517 struct decision_head *head;
1519 struct decision *first, *next;
1521 for (first = head->first; first && first->next; first = next)
1523 enum decision_type type;
1524 struct decision *new, *old_last;
1526 type = first->tests->type;
1527 next = first->next;
1529 /* Want at least two compatible sequential nodes. */
1530 if (next->tests->type != type)
1531 continue;
1533 /* Don't want all node types, just those we can turn into
1534 switch statements. */
1535 if (type != DT_mode
1536 && type != DT_code
1537 && type != DT_veclen
1538 && type != DT_elt_zero_int
1539 && type != DT_elt_one_int
1540 && type != DT_elt_zero_wide_safe)
1541 continue;
1543 /* If we'd been performing more than one test, create a new node
1544 below our first test. */
1545 if (first->tests->next != NULL)
1547 new = new_decision (first->position, &first->success);
1548 new->tests = first->tests->next;
1549 first->tests->next = NULL;
1552 /* Crop the node tree off after our first test. */
1553 first->next = NULL;
1554 old_last = head->last;
1555 head->last = first;
1557 /* For each compatible test, adjust to perform only one test in
1558 the top level node, then merge the node back into the tree. */
1561 struct decision_head h;
1563 if (next->tests->next != NULL)
1565 new = new_decision (next->position, &next->success);
1566 new->tests = next->tests->next;
1567 next->tests->next = NULL;
1569 new = next;
1570 next = next->next;
1571 new->next = NULL;
1572 h.first = h.last = new;
1574 merge_trees (head, &h);
1576 while (next && next->tests->type == type);
1578 /* After we run out of compatible tests, graft the remaining nodes
1579 back onto the tree. */
1580 if (next)
1582 next->prev = head->last;
1583 head->last->next = next;
1584 head->last = old_last;
1588 /* Recurse. */
1589 for (first = head->first; first; first = first->next)
1590 factor_tests (&first->success);
1593 /* After factoring, try to simplify the tests on any one node.
1594 Tests that are useful for switch statements are recognizable
1595 by having only a single test on a node -- we'll be manipulating
1596 nodes with multiple tests:
1598 If we have mode tests or code tests that are redundant with
1599 predicates, remove them. */
1601 static void
1602 simplify_tests (head)
1603 struct decision_head *head;
1605 struct decision *tree;
1607 for (tree = head->first; tree; tree = tree->next)
1609 struct decision_test *a, *b;
1611 a = tree->tests;
1612 b = a->next;
1613 if (b == NULL)
1614 continue;
1616 /* Find a predicate node. */
1617 while (b && b->type != DT_pred)
1618 b = b->next;
1619 if (b)
1621 /* Due to how these tests are constructed, we don't even need
1622 to check that the mode and code are compatible -- they were
1623 generated from the predicate in the first place. */
1624 while (a->type == DT_mode || a->type == DT_code)
1625 a = a->next;
1626 tree->tests = a;
1630 /* Recurse. */
1631 for (tree = head->first; tree; tree = tree->next)
1632 simplify_tests (&tree->success);
1635 /* Count the number of subnodes of HEAD. If the number is high enough,
1636 make the first node in HEAD start a separate subroutine in the C code
1637 that is generated. */
1639 static int
1640 break_out_subroutines (head, initial)
1641 struct decision_head *head;
1642 int initial;
1644 int size = 0;
1645 struct decision *sub;
1647 for (sub = head->first; sub; sub = sub->next)
1648 size += 1 + break_out_subroutines (&sub->success, 0);
1650 if (size > SUBROUTINE_THRESHOLD && ! initial)
1652 head->first->subroutine_number = ++next_subroutine_number;
1653 size = 1;
1655 return size;
1658 /* For each node p, find the next alternative that might be true
1659 when p is true. */
1661 static void
1662 find_afterward (head, real_afterward)
1663 struct decision_head *head;
1664 struct decision *real_afterward;
1666 struct decision *p, *q, *afterward;
1668 /* We can't propagate alternatives across subroutine boundaries.
1669 This is not incorrect, merely a minor optimization loss. */
1671 p = head->first;
1672 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1674 for ( ; p ; p = p->next)
1676 /* Find the next node that might be true if this one fails. */
1677 for (q = p->next; q ; q = q->next)
1678 if (maybe_both_true (p, q, 1))
1679 break;
1681 /* If we reached the end of the list without finding one,
1682 use the incoming afterward position. */
1683 if (!q)
1684 q = afterward;
1685 p->afterward = q;
1686 if (q)
1687 q->need_label = 1;
1690 /* Recurse. */
1691 for (p = head->first; p ; p = p->next)
1692 if (p->success.first)
1693 find_afterward (&p->success, p->afterward);
1695 /* When we are generating a subroutine, record the real afterward
1696 position in the first node where write_tree can find it, and we
1697 can do the right thing at the subroutine call site. */
1698 p = head->first;
1699 if (p->subroutine_number > 0)
1700 p->afterward = real_afterward;
1703 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1704 actions are necessary to move to NEWPOS. If we fail to move to the
1705 new state, branch to node AFTERWARD if non-zero, otherwise return.
1707 Failure to move to the new state can only occur if we are trying to
1708 match multiple insns and we try to step past the end of the stream. */
1710 static void
1711 change_state (oldpos, newpos, afterward, indent)
1712 const char *oldpos;
1713 const char *newpos;
1714 struct decision *afterward;
1715 const char *indent;
1717 int odepth = strlen (oldpos);
1718 int ndepth = strlen (newpos);
1719 int depth;
1720 int old_has_insn, new_has_insn;
1722 /* Pop up as many levels as necessary. */
1723 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1724 continue;
1726 /* Hunt for the last [A-Z] in both strings. */
1727 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1728 if (ISUPPER (oldpos[old_has_insn]))
1729 break;
1730 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1731 if (ISUPPER (newpos[new_has_insn]))
1732 break;
1734 /* Go down to desired level. */
1735 while (depth < ndepth)
1737 /* It's a different insn from the first one. */
1738 if (ISUPPER (newpos[depth]))
1740 /* We can only fail if we're moving down the tree. */
1741 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1743 printf ("%stem = peep2_next_insn (%d);\n",
1744 indent, newpos[depth] - 'A');
1746 else
1748 printf ("%stem = peep2_next_insn (%d);\n",
1749 indent, newpos[depth] - 'A');
1750 printf ("%sif (tem == NULL_RTX)\n", indent);
1751 if (afterward)
1752 printf ("%s goto L%d;\n", indent, afterward->number);
1753 else
1754 printf ("%s goto ret0;\n", indent);
1756 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1758 else if (ISLOWER (newpos[depth]))
1759 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1760 indent, depth + 1, depth, newpos[depth] - 'a');
1761 else
1762 printf ("%sx%d = XEXP (x%d, %c);\n",
1763 indent, depth + 1, depth, newpos[depth]);
1764 ++depth;
1768 /* Print the enumerator constant for CODE -- the upcase version of
1769 the name. */
1771 static void
1772 print_code (code)
1773 enum rtx_code code;
1775 const char *p;
1776 for (p = GET_RTX_NAME (code); *p; p++)
1777 putchar (TOUPPER (*p));
1780 /* Emit code to cross an afterward link -- change state and branch. */
1782 static void
1783 write_afterward (start, afterward, indent)
1784 struct decision *start;
1785 struct decision *afterward;
1786 const char *indent;
1788 if (!afterward || start->subroutine_number > 0)
1789 printf("%sgoto ret0;\n", indent);
1790 else
1792 change_state (start->position, afterward->position, NULL, indent);
1793 printf ("%sgoto L%d;\n", indent, afterward->number);
1797 /* Emit a switch statement, if possible, for an initial sequence of
1798 nodes at START. Return the first node yet untested. */
1800 static struct decision *
1801 write_switch (start, depth)
1802 struct decision *start;
1803 int depth;
1805 struct decision *p = start;
1806 enum decision_type type = p->tests->type;
1807 struct decision *needs_label = NULL;
1809 /* If we have two or more nodes in sequence that test the same one
1810 thing, we may be able to use a switch statement. */
1812 if (!p->next
1813 || p->tests->next
1814 || p->next->tests->type != type
1815 || p->next->tests->next
1816 || nodes_identical_1 (p->tests, p->next->tests))
1817 return p;
1819 /* DT_code is special in that we can do interesting things with
1820 known predicates at the same time. */
1821 if (type == DT_code)
1823 char codemap[NUM_RTX_CODE];
1824 struct decision *ret;
1825 RTX_CODE code;
1827 memset (codemap, 0, sizeof(codemap));
1829 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1830 code = p->tests->u.code;
1833 if (p != start && p->need_label && needs_label == NULL)
1834 needs_label = p;
1836 printf (" case ");
1837 print_code (code);
1838 printf (":\n goto L%d;\n", p->success.first->number);
1839 p->success.first->need_label = 1;
1841 codemap[code] = 1;
1842 p = p->next;
1844 while (p
1845 && ! p->tests->next
1846 && p->tests->type == DT_code
1847 && ! codemap[code = p->tests->u.code]);
1849 /* If P is testing a predicate that we know about and we haven't
1850 seen any of the codes that are valid for the predicate, we can
1851 write a series of "case" statement, one for each possible code.
1852 Since we are already in a switch, these redundant tests are very
1853 cheap and will reduce the number of predicates called. */
1855 /* Note that while we write out cases for these predicates here,
1856 we don't actually write the test here, as it gets kinda messy.
1857 It is trivial to leave this to later by telling our caller that
1858 we only processed the CODE tests. */
1859 if (needs_label != NULL)
1860 ret = needs_label;
1861 else
1862 ret = p;
1864 while (p && p->tests->type == DT_pred
1865 && p->tests->u.pred.index >= 0)
1867 const RTX_CODE *c;
1869 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1870 if (codemap[(int) *c] != 0)
1871 goto pred_done;
1873 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1875 printf (" case ");
1876 print_code (*c);
1877 printf (":\n");
1878 codemap[(int) *c] = 1;
1881 printf (" goto L%d;\n", p->number);
1882 p->need_label = 1;
1883 p = p->next;
1886 pred_done:
1887 /* Make the default case skip the predicates we managed to match. */
1889 printf (" default:\n");
1890 if (p != ret)
1892 if (p)
1894 printf (" goto L%d;\n", p->number);
1895 p->need_label = 1;
1897 else
1898 write_afterward (start, start->afterward, " ");
1900 else
1901 printf (" break;\n");
1902 printf (" }\n");
1904 return ret;
1906 else if (type == DT_mode
1907 || type == DT_veclen
1908 || type == DT_elt_zero_int
1909 || type == DT_elt_one_int
1910 || type == DT_elt_zero_wide_safe)
1912 const char *indent = "";
1913 /* Pmode may not be a compile-time constant. */
1914 if (type == DT_mode && p->tests->u.mode == Pmode)
1915 return p;
1917 /* We cast switch parameter to integer, so we must ensure that the value
1918 fits. */
1919 if (type == DT_elt_zero_wide_safe)
1921 indent = " ";
1922 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1924 printf ("%s switch (", indent);
1925 switch (type)
1927 case DT_mode:
1928 printf ("GET_MODE (x%d)", depth);
1929 break;
1930 case DT_veclen:
1931 printf ("XVECLEN (x%d, 0)", depth);
1932 break;
1933 case DT_elt_zero_int:
1934 printf ("XINT (x%d, 0)", depth);
1935 break;
1936 case DT_elt_one_int:
1937 printf ("XINT (x%d, 1)", depth);
1938 break;
1939 case DT_elt_zero_wide_safe:
1940 /* Convert result of XWINT to int for portability since some C
1941 compilers won't do it and some will. */
1942 printf ("(int) XWINT (x%d, 0)", depth);
1943 break;
1944 default:
1945 abort ();
1947 printf (")\n%s {\n", indent);
1951 /* Merge trees will not unify identical nodes if their
1952 sub-nodes are at different levels. Thus we must check
1953 for duplicate cases. */
1954 struct decision *q;
1955 for (q = start; q != p; q = q->next)
1956 if (nodes_identical_1 (p->tests, q->tests))
1957 goto case_done;
1959 /* Pmode may not be a compile-time constant. */
1960 if (type == DT_mode && p->tests->u.mode == Pmode)
1961 goto case_done;
1963 if (p != start && p->need_label && needs_label == NULL)
1964 needs_label = p;
1966 printf ("%s case ", indent);
1967 switch (type)
1969 case DT_mode:
1970 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1971 break;
1972 case DT_veclen:
1973 printf ("%d", p->tests->u.veclen);
1974 break;
1975 case DT_elt_zero_int:
1976 case DT_elt_one_int:
1977 case DT_elt_zero_wide:
1978 case DT_elt_zero_wide_safe:
1979 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1980 break;
1981 default:
1982 abort ();
1984 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1985 p->success.first->need_label = 1;
1987 p = p->next;
1989 while (p && p->tests->type == type && !p->tests->next);
1991 case_done:
1992 printf ("%s default:\n%s break;\n%s }\n",
1993 indent, indent, indent);
1995 return needs_label != NULL ? needs_label : p;
1997 else
1999 /* None of the other tests are ameanable. */
2000 return p;
2004 /* Emit code for one test. */
2006 static void
2007 write_cond (p, depth, subroutine_type)
2008 struct decision_test *p;
2009 int depth;
2010 enum routine_type subroutine_type;
2012 switch (p->type)
2014 case DT_mode:
2015 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
2016 break;
2018 case DT_code:
2019 printf ("GET_CODE (x%d) == ", depth);
2020 print_code (p->u.code);
2021 break;
2023 case DT_veclen:
2024 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
2025 break;
2027 case DT_elt_zero_int:
2028 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
2029 break;
2031 case DT_elt_one_int:
2032 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
2033 break;
2035 case DT_elt_zero_wide:
2036 case DT_elt_zero_wide_safe:
2037 printf ("XWINT (x%d, 0) == ", depth);
2038 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
2039 break;
2041 case DT_veclen_ge:
2042 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2043 break;
2045 case DT_dup:
2046 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2047 break;
2049 case DT_pred:
2050 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2051 GET_MODE_NAME (p->u.pred.mode));
2052 break;
2054 case DT_c_test:
2055 printf ("(%s)", p->u.c_test);
2056 break;
2058 case DT_accept_insn:
2059 switch (subroutine_type)
2061 case RECOG:
2062 if (p->u.insn.num_clobbers_to_add == 0)
2063 abort ();
2064 printf ("pnum_clobbers != NULL");
2065 break;
2067 default:
2068 abort ();
2070 break;
2072 default:
2073 abort ();
2077 /* Emit code for one action. The previous tests have succeeded;
2078 TEST is the last of the chain. In the normal case we simply
2079 perform a state change. For the `accept' tests we must do more work. */
2081 static void
2082 write_action (p, test, depth, uncond, success, subroutine_type)
2083 struct decision *p;
2084 struct decision_test *test;
2085 int depth, uncond;
2086 struct decision *success;
2087 enum routine_type subroutine_type;
2089 const char *indent;
2090 int want_close = 0;
2092 if (uncond)
2093 indent = " ";
2094 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2096 fputs (" {\n", stdout);
2097 indent = " ";
2098 want_close = 1;
2100 else
2101 indent = " ";
2103 if (test->type == DT_accept_op)
2105 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2107 /* Only allow DT_accept_insn to follow. */
2108 if (test->next)
2110 test = test->next;
2111 if (test->type != DT_accept_insn)
2112 abort ();
2116 /* Sanity check that we're now at the end of the list of tests. */
2117 if (test->next)
2118 abort ();
2120 if (test->type == DT_accept_insn)
2122 switch (subroutine_type)
2124 case RECOG:
2125 if (test->u.insn.num_clobbers_to_add != 0)
2126 printf ("%s*pnum_clobbers = %d;\n",
2127 indent, test->u.insn.num_clobbers_to_add);
2128 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2129 break;
2131 case SPLIT:
2132 printf ("%sreturn gen_split_%d (operands);\n",
2133 indent, test->u.insn.code_number);
2134 break;
2136 case PEEPHOLE2:
2138 int match_len = 0, i;
2140 for (i = strlen (p->position) - 1; i >= 0; --i)
2141 if (ISUPPER (p->position[i]))
2143 match_len = p->position[i] - 'A';
2144 break;
2146 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2147 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2148 indent, test->u.insn.code_number);
2149 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2151 break;
2153 default:
2154 abort ();
2157 else
2159 printf("%sgoto L%d;\n", indent, success->number);
2160 success->need_label = 1;
2163 if (want_close)
2164 fputs (" }\n", stdout);
2167 /* Return 1 if the test is always true and has no fallthru path. Return -1
2168 if the test does have a fallthru path, but requires that the condition be
2169 terminated. Otherwise return 0 for a normal test. */
2170 /* ??? is_unconditional is a stupid name for a tri-state function. */
2172 static int
2173 is_unconditional (t, subroutine_type)
2174 struct decision_test *t;
2175 enum routine_type subroutine_type;
2177 if (t->type == DT_accept_op)
2178 return 1;
2180 if (t->type == DT_accept_insn)
2182 switch (subroutine_type)
2184 case RECOG:
2185 return (t->u.insn.num_clobbers_to_add == 0);
2186 case SPLIT:
2187 return 1;
2188 case PEEPHOLE2:
2189 return -1;
2190 default:
2191 abort ();
2195 return 0;
2198 /* Emit code for one node -- the conditional and the accompanying action.
2199 Return true if there is no fallthru path. */
2201 static int
2202 write_node (p, depth, subroutine_type)
2203 struct decision *p;
2204 int depth;
2205 enum routine_type subroutine_type;
2207 struct decision_test *test, *last_test;
2208 int uncond;
2210 last_test = test = p->tests;
2211 uncond = is_unconditional (test, subroutine_type);
2212 if (uncond == 0)
2214 printf (" if (");
2215 write_cond (test, depth, subroutine_type);
2217 while ((test = test->next) != NULL)
2219 int uncond2;
2221 last_test = test;
2222 uncond2 = is_unconditional (test, subroutine_type);
2223 if (uncond2 != 0)
2224 break;
2226 printf ("\n && ");
2227 write_cond (test, depth, subroutine_type);
2230 printf (")\n");
2233 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2235 return uncond > 0;
2238 /* Emit code for all of the sibling nodes of HEAD. */
2240 static void
2241 write_tree_1 (head, depth, subroutine_type)
2242 struct decision_head *head;
2243 int depth;
2244 enum routine_type subroutine_type;
2246 struct decision *p, *next;
2247 int uncond = 0;
2249 for (p = head->first; p ; p = next)
2251 /* The label for the first element was printed in write_tree. */
2252 if (p != head->first && p->need_label)
2253 OUTPUT_LABEL (" ", p->number);
2255 /* Attempt to write a switch statement for a whole sequence. */
2256 next = write_switch (p, depth);
2257 if (p != next)
2258 uncond = 0;
2259 else
2261 /* Failed -- fall back and write one node. */
2262 uncond = write_node (p, depth, subroutine_type);
2263 next = p->next;
2267 /* Finished with this chain. Close a fallthru path by branching
2268 to the afterward node. */
2269 if (! uncond)
2270 write_afterward (head->last, head->last->afterward, " ");
2273 /* Write out the decision tree starting at HEAD. PREVPOS is the
2274 position at the node that branched to this node. */
2276 static void
2277 write_tree (head, prevpos, type, initial)
2278 struct decision_head *head;
2279 const char *prevpos;
2280 enum routine_type type;
2281 int initial;
2283 struct decision *p = head->first;
2285 putchar ('\n');
2286 if (p->need_label)
2287 OUTPUT_LABEL (" ", p->number);
2289 if (! initial && p->subroutine_number > 0)
2291 static const char * const name_prefix[] = {
2292 "recog", "split", "peephole2"
2295 static const char * const call_suffix[] = {
2296 ", pnum_clobbers", "", ", _pmatch_len"
2299 /* This node has been broken out into a separate subroutine.
2300 Call it, test the result, and branch accordingly. */
2302 if (p->afterward)
2304 printf (" tem = %s_%d (x0, insn%s);\n",
2305 name_prefix[type], p->subroutine_number, call_suffix[type]);
2306 if (IS_SPLIT (type))
2307 printf (" if (tem != 0)\n return tem;\n");
2308 else
2309 printf (" if (tem >= 0)\n return tem;\n");
2311 change_state (p->position, p->afterward->position, NULL, " ");
2312 printf (" goto L%d;\n", p->afterward->number);
2314 else
2316 printf (" return %s_%d (x0, insn%s);\n",
2317 name_prefix[type], p->subroutine_number, call_suffix[type]);
2320 else
2322 int depth = strlen (p->position);
2324 change_state (prevpos, p->position, head->last->afterward, " ");
2325 write_tree_1 (head, depth, type);
2327 for (p = head->first; p; p = p->next)
2328 if (p->success.first)
2329 write_tree (&p->success, p->position, type, 0);
2333 /* Write out a subroutine of type TYPE to do comparisons starting at
2334 node TREE. */
2336 static void
2337 write_subroutine (head, type)
2338 struct decision_head *head;
2339 enum routine_type type;
2341 int subfunction = head->first ? head->first->subroutine_number : 0;
2342 const char *s_or_e;
2343 char extension[32];
2344 int i;
2346 s_or_e = subfunction ? "static " : "";
2348 if (subfunction)
2349 sprintf (extension, "_%d", subfunction);
2350 else if (type == RECOG)
2351 extension[0] = '\0';
2352 else
2353 strcpy (extension, "_insns");
2355 switch (type)
2357 case RECOG:
2358 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension);
2359 printf ("%sint\n\
2360 recog%s (x0, insn, pnum_clobbers)\n\
2361 rtx x0 ATTRIBUTE_UNUSED;\n\
2362 rtx insn ATTRIBUTE_UNUSED;\n\
2363 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2364 break;
2365 case SPLIT:
2366 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension);
2367 printf ("%srtx\n\
2368 split%s (x0, insn)\n\
2369 rtx x0 ATTRIBUTE_UNUSED;\n\
2370 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2371 break;
2372 case PEEPHOLE2:
2373 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2374 s_or_e, extension);
2375 printf ("%srtx\n\
2376 peephole2%s (x0, insn, _pmatch_len)\n\
2377 rtx x0 ATTRIBUTE_UNUSED;\n\
2378 rtx insn ATTRIBUTE_UNUSED;\n\
2379 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension);
2380 break;
2383 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2384 for (i = 1; i <= max_depth; i++)
2385 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2387 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2389 if (!subfunction)
2390 printf (" recog_data.insn = NULL_RTX;\n");
2392 if (head->first)
2393 write_tree (head, "", type, 1);
2394 else
2395 printf (" goto ret0;\n");
2397 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2400 /* In break_out_subroutines, we discovered the boundaries for the
2401 subroutines, but did not write them out. Do so now. */
2403 static void
2404 write_subroutines (head, type)
2405 struct decision_head *head;
2406 enum routine_type type;
2408 struct decision *p;
2410 for (p = head->first; p ; p = p->next)
2411 if (p->success.first)
2412 write_subroutines (&p->success, type);
2414 if (head->first->subroutine_number > 0)
2415 write_subroutine (head, type);
2418 /* Begin the output file. */
2420 static void
2421 write_header ()
2423 puts ("\
2424 /* Generated automatically by the program `genrecog' from the target\n\
2425 machine description file. */\n\
2427 #include \"config.h\"\n\
2428 #include \"system.h\"\n\
2429 #include \"rtl.h\"\n\
2430 #include \"tm_p.h\"\n\
2431 #include \"function.h\"\n\
2432 #include \"insn-config.h\"\n\
2433 #include \"recog.h\"\n\
2434 #include \"real.h\"\n\
2435 #include \"output.h\"\n\
2436 #include \"flags.h\"\n\
2437 #include \"hard-reg-set.h\"\n\
2438 #include \"resource.h\"\n\
2439 #include \"toplev.h\"\n\
2440 #include \"reload.h\"\n\
2441 \n");
2443 puts ("\n\
2444 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2445 X0 is a valid instruction.\n\
2447 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2448 returns a nonnegative number which is the insn code number for the\n\
2449 pattern that matched. This is the same as the order in the machine\n\
2450 description of the entry that matched. This number can be used as an\n\
2451 index into `insn_data' and other tables.\n");
2452 puts ("\
2453 The third argument to recog is an optional pointer to an int. If\n\
2454 present, recog will accept a pattern if it matches except for missing\n\
2455 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2456 the optional pointer will be set to the number of CLOBBERs that need\n\
2457 to be added (it should be initialized to zero by the caller). If it");
2458 puts ("\
2459 is set nonzero, the caller should allocate a PARALLEL of the\n\
2460 appropriate size, copy the initial entries, and call add_clobbers\n\
2461 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2464 puts ("\n\
2465 The function split_insns returns 0 if the rtl could not\n\
2466 be split or the split rtl in a SEQUENCE if it can be.\n\
2468 The function peephole2_insns returns 0 if the rtl could not\n\
2469 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2470 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2471 */\n\n");
2475 /* Construct and return a sequence of decisions
2476 that will recognize INSN.
2478 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2480 static struct decision_head
2481 make_insn_sequence (insn, type)
2482 rtx insn;
2483 enum routine_type type;
2485 rtx x;
2486 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2487 struct decision *last;
2488 struct decision_test *test, **place;
2489 struct decision_head head;
2490 char c_test_pos[2];
2492 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2494 c_test_pos[0] = '\0';
2495 if (type == PEEPHOLE2)
2497 int i, j;
2499 /* peephole2 gets special treatment:
2500 - X always gets an outer parallel even if it's only one entry
2501 - we remove all traces of outer-level match_scratch and match_dup
2502 expressions here. */
2503 x = rtx_alloc (PARALLEL);
2504 PUT_MODE (x, VOIDmode);
2505 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2506 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2508 rtx tmp = XVECEXP (insn, 0, i);
2509 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2511 XVECEXP (x, 0, j) = tmp;
2512 j++;
2515 XVECLEN (x, 0) = j;
2517 c_test_pos[0] = 'A' + j - 1;
2518 c_test_pos[1] = '\0';
2520 else if (XVECLEN (insn, type == RECOG) == 1)
2521 x = XVECEXP (insn, type == RECOG, 0);
2522 else
2524 x = rtx_alloc (PARALLEL);
2525 XVEC (x, 0) = XVEC (insn, type == RECOG);
2526 PUT_MODE (x, VOIDmode);
2529 validate_pattern (x, insn, NULL_RTX, 0);
2531 memset(&head, 0, sizeof(head));
2532 last = add_to_sequence (x, &head, "", type, 1);
2534 /* Find the end of the test chain on the last node. */
2535 for (test = last->tests; test->next; test = test->next)
2536 continue;
2537 place = &test->next;
2539 if (c_test[0])
2541 /* Need a new node if we have another test to add. */
2542 if (test->type == DT_accept_op)
2544 last = new_decision (c_test_pos, &last->success);
2545 place = &last->tests;
2547 test = new_decision_test (DT_c_test, &place);
2548 test->u.c_test = c_test;
2551 test = new_decision_test (DT_accept_insn, &place);
2552 test->u.insn.code_number = next_insn_code;
2553 test->u.insn.lineno = pattern_lineno;
2554 test->u.insn.num_clobbers_to_add = 0;
2556 switch (type)
2558 case RECOG:
2559 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2560 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2561 If so, set up to recognize the pattern without these CLOBBERs. */
2563 if (GET_CODE (x) == PARALLEL)
2565 int i;
2567 /* Find the last non-clobber in the parallel. */
2568 for (i = XVECLEN (x, 0); i > 0; i--)
2570 rtx y = XVECEXP (x, 0, i - 1);
2571 if (GET_CODE (y) != CLOBBER
2572 || (GET_CODE (XEXP (y, 0)) != REG
2573 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2574 break;
2577 if (i != XVECLEN (x, 0))
2579 rtx new;
2580 struct decision_head clobber_head;
2582 /* Build a similar insn without the clobbers. */
2583 if (i == 1)
2584 new = XVECEXP (x, 0, 0);
2585 else
2587 int j;
2589 new = rtx_alloc (PARALLEL);
2590 XVEC (new, 0) = rtvec_alloc (i);
2591 for (j = i - 1; j >= 0; j--)
2592 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2595 /* Recognize it. */
2596 memset (&clobber_head, 0, sizeof(clobber_head));
2597 last = add_to_sequence (new, &clobber_head, "", type, 1);
2599 /* Find the end of the test chain on the last node. */
2600 for (test = last->tests; test->next; test = test->next)
2601 continue;
2603 /* We definitely have a new test to add -- create a new
2604 node if needed. */
2605 place = &test->next;
2606 if (test->type == DT_accept_op)
2608 last = new_decision ("", &last->success);
2609 place = &last->tests;
2612 if (c_test[0])
2614 test = new_decision_test (DT_c_test, &place);
2615 test->u.c_test = c_test;
2618 test = new_decision_test (DT_accept_insn, &place);
2619 test->u.insn.code_number = next_insn_code;
2620 test->u.insn.lineno = pattern_lineno;
2621 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2623 merge_trees (&head, &clobber_head);
2626 break;
2628 case SPLIT:
2629 /* Define the subroutine we will call below and emit in genemit. */
2630 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2631 break;
2633 case PEEPHOLE2:
2634 /* Define the subroutine we will call below and emit in genemit. */
2635 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2636 next_insn_code);
2637 break;
2640 return head;
2643 static void
2644 process_tree (head, subroutine_type)
2645 struct decision_head *head;
2646 enum routine_type subroutine_type;
2648 if (head->first == NULL)
2650 /* We can elide peephole2_insns, but not recog or split_insns. */
2651 if (subroutine_type == PEEPHOLE2)
2652 return;
2654 else
2656 factor_tests (head);
2658 next_subroutine_number = 0;
2659 break_out_subroutines (head, 1);
2660 find_afterward (head, NULL);
2662 /* We run this after find_afterward, because find_afterward needs
2663 the redundant DT_mode tests on predicates to determine whether
2664 two tests can both be true or not. */
2665 simplify_tests(head);
2667 write_subroutines (head, subroutine_type);
2670 write_subroutine (head, subroutine_type);
2673 extern int main PARAMS ((int, char **));
2676 main (argc, argv)
2677 int argc;
2678 char **argv;
2680 rtx desc;
2681 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2683 progname = "genrecog";
2685 memset (&recog_tree, 0, sizeof recog_tree);
2686 memset (&split_tree, 0, sizeof split_tree);
2687 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2689 if (argc <= 1)
2690 fatal ("No input file name.");
2692 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2693 return (FATAL_EXIT_CODE);
2695 next_insn_code = 0;
2696 next_index = 0;
2698 write_header ();
2700 /* Read the machine description. */
2702 while (1)
2704 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2705 if (desc == NULL)
2706 break;
2708 if (GET_CODE (desc) == DEFINE_INSN)
2710 h = make_insn_sequence (desc, RECOG);
2711 merge_trees (&recog_tree, &h);
2713 else if (GET_CODE (desc) == DEFINE_SPLIT)
2715 h = make_insn_sequence (desc, SPLIT);
2716 merge_trees (&split_tree, &h);
2718 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2720 h = make_insn_sequence (desc, PEEPHOLE2);
2721 merge_trees (&peephole2_tree, &h);
2724 next_index++;
2727 if (error_count)
2728 return FATAL_EXIT_CODE;
2730 puts ("\n\n");
2732 process_tree (&recog_tree, RECOG);
2733 process_tree (&split_tree, SPLIT);
2734 process_tree (&peephole2_tree, PEEPHOLE2);
2736 fflush (stdout);
2737 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2740 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2741 const char *
2742 get_insn_name (code)
2743 int code;
2745 if (code < insn_name_ptr_size)
2746 return insn_name_ptr[code];
2747 else
2748 return NULL;
2751 static void
2752 record_insn_name (code, name)
2753 int code;
2754 const char *name;
2756 static const char *last_real_name = "insn";
2757 static int last_real_code = 0;
2758 char *new;
2760 if (insn_name_ptr_size <= code)
2762 int new_size;
2763 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2764 insn_name_ptr =
2765 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2766 memset (insn_name_ptr + insn_name_ptr_size, 0,
2767 sizeof(char *) * (new_size - insn_name_ptr_size));
2768 insn_name_ptr_size = new_size;
2771 if (!name || name[0] == '\0')
2773 new = xmalloc (strlen (last_real_name) + 10);
2774 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2776 else
2778 last_real_name = new = xstrdup (name);
2779 last_real_code = code;
2782 insn_name_ptr[code] = new;
2785 static void
2786 debug_decision_2 (test)
2787 struct decision_test *test;
2789 switch (test->type)
2791 case DT_mode:
2792 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2793 break;
2794 case DT_code:
2795 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2796 break;
2797 case DT_veclen:
2798 fprintf (stderr, "veclen=%d", test->u.veclen);
2799 break;
2800 case DT_elt_zero_int:
2801 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2802 break;
2803 case DT_elt_one_int:
2804 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2805 break;
2806 case DT_elt_zero_wide:
2807 fprintf (stderr, "elt0_w=");
2808 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2809 break;
2810 case DT_elt_zero_wide_safe:
2811 fprintf (stderr, "elt0_ws=");
2812 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2813 break;
2814 case DT_veclen_ge:
2815 fprintf (stderr, "veclen>=%d", test->u.veclen);
2816 break;
2817 case DT_dup:
2818 fprintf (stderr, "dup=%d", test->u.dup);
2819 break;
2820 case DT_pred:
2821 fprintf (stderr, "pred=(%s,%s)",
2822 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2823 break;
2824 case DT_c_test:
2826 char sub[16+4];
2827 strncpy (sub, test->u.c_test, sizeof(sub));
2828 memcpy (sub+16, "...", 4);
2829 fprintf (stderr, "c_test=\"%s\"", sub);
2831 break;
2832 case DT_accept_op:
2833 fprintf (stderr, "A_op=%d", test->u.opno);
2834 break;
2835 case DT_accept_insn:
2836 fprintf (stderr, "A_insn=(%d,%d)",
2837 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2838 break;
2840 default:
2841 abort ();
2845 static void
2846 debug_decision_1 (d, indent)
2847 struct decision *d;
2848 int indent;
2850 int i;
2851 struct decision_test *test;
2853 if (d == NULL)
2855 for (i = 0; i < indent; ++i)
2856 putc (' ', stderr);
2857 fputs ("(nil)\n", stderr);
2858 return;
2861 for (i = 0; i < indent; ++i)
2862 putc (' ', stderr);
2864 putc ('{', stderr);
2865 test = d->tests;
2866 if (test)
2868 debug_decision_2 (test);
2869 while ((test = test->next) != NULL)
2871 fputs (" + ", stderr);
2872 debug_decision_2 (test);
2875 fprintf (stderr, "} %d n %d a %d\n", d->number,
2876 (d->next ? d->next->number : -1),
2877 (d->afterward ? d->afterward->number : -1));
2880 static void
2881 debug_decision_0 (d, indent, maxdepth)
2882 struct decision *d;
2883 int indent, maxdepth;
2885 struct decision *n;
2886 int i;
2888 if (maxdepth < 0)
2889 return;
2890 if (d == NULL)
2892 for (i = 0; i < indent; ++i)
2893 putc (' ', stderr);
2894 fputs ("(nil)\n", stderr);
2895 return;
2898 debug_decision_1 (d, indent);
2899 for (n = d->success.first; n ; n = n->next)
2900 debug_decision_0 (n, indent + 2, maxdepth - 1);
2903 void
2904 debug_decision (d)
2905 struct decision *d;
2907 debug_decision_0 (d, 0, 1000000);
2910 void
2911 debug_decision_list (d)
2912 struct decision *d;
2914 while (d)
2916 debug_decision_0 (d, 0, 0);
2917 d = d->next;