1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 88, 92-95, 97-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This program is used to produce insn-recog.c, which contains
23 a function called `recog' plus its subroutines.
24 These functions contain a decision tree
25 that recognizes whether an rtx, the argument given to recog,
26 is a valid instruction.
28 recog returns -1 if the rtx is not valid.
29 If the rtx is valid, recog returns a nonnegative number
30 which is the insn code number for the pattern that matched.
31 This is the same as the order in the machine description of the
32 entry that matched. This number can be used as an index into various
33 insn_* tables, such as insn_template, insn_outfun, and insn_n_operands
34 (found in insn-output.c).
36 The third argument to recog is an optional pointer to an int.
37 If present, recog will accept a pattern if it matches except for
38 missing CLOBBER expressions at the end. In that case, the value
39 pointed to by the optional pointer will be set to the number of
40 CLOBBERs that need to be added (it should be initialized to zero by
41 the caller). If it is set nonzero, the caller should allocate a
42 PARALLEL of the appropriate size, copy the initial entries, and call
43 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
45 This program also generates the function `split_insns',
46 which returns 0 if the rtl could not be split, or
47 it returns the split rtl in a SEQUENCE. */
55 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
56 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
58 static struct obstack obstack;
59 struct obstack *rtl_obstack = &obstack;
61 #define obstack_chunk_alloc xmalloc
62 #define obstack_chunk_free free
64 /* Holds an array of names indexed by insn_code_number. */
65 static char **insn_name_ptr = 0;
66 static int insn_name_ptr_size = 0;
68 /* Data structure for a listhead of decision trees. The alternatives
69 to a node are kept in a doublely-linked list so we can easily add nodes
70 to the proper place when merging. */
72 struct decision_head { struct decision *first, *last; };
74 /* Data structure for decision tree for recognizing
75 legitimate instructions. */
79 int number; /* Node number, used for labels */
80 char *position; /* String denoting position in pattern */
81 RTX_CODE code; /* Code to test for or UNKNOWN to suppress */
82 char ignore_code; /* If non-zero, need not test code */
83 char ignore_mode; /* If non-zero, need not test mode */
84 int veclen; /* Length of vector, if nonzero */
85 enum machine_mode mode; /* Machine mode of node */
86 char enforce_mode; /* If non-zero, test `mode' */
87 char retest_code, retest_mode; /* See write_tree_1 */
88 int test_elt_zero_int; /* Nonzero if should test XINT (rtl, 0) */
89 int elt_zero_int; /* Required value for XINT (rtl, 0) */
90 int test_elt_one_int; /* Nonzero if should test XINT (rtl, 1) */
91 int elt_one_int; /* Required value for XINT (rtl, 1) */
92 int test_elt_zero_wide; /* Nonzero if should test XWINT (rtl, 0) */
93 HOST_WIDE_INT elt_zero_wide; /* Required value for XWINT (rtl, 0) */
94 const char *tests; /* If nonzero predicate to call */
95 int pred; /* `preds' index of predicate or -1 */
96 char *c_test; /* Additional test to perform */
97 struct decision_head success; /* Nodes to test on success */
98 int insn_code_number; /* Insn number matched, if success */
99 int num_clobbers_to_add; /* Number of CLOBBERs to be added to pattern */
100 struct decision *next; /* Node to test on failure */
101 struct decision *prev; /* Node whose failure tests us */
102 struct decision *afterward; /* Node to test on success, but failure of
104 int opno; /* Operand number, if >= 0 */
105 int dupno; /* Number of operand to compare against */
106 int label_needed; /* Nonzero if label needed when writing tree */
107 int subroutine_number; /* Number of subroutine this node starts */
110 #define SUBROUTINE_THRESHOLD 50
112 static int next_subroutine_number;
114 /* We can write three types of subroutines: One for insn recognition,
115 one to split insns, and one for peephole-type optimizations. This
116 defines which type is being written. */
118 enum routine_type {RECOG, SPLIT, PEEPHOLE2};
120 #define IS_SPLIT(X) ((X) == SPLIT || (X)==PEEPHOLE2)
122 /* Next available node number for tree nodes. */
124 static int next_number;
126 /* Next number to use as an insn_code. */
128 static int next_insn_code;
130 /* Similar, but counts all expressions in the MD file; used for
133 static int next_index;
135 /* Record the highest depth we ever have so we know how many variables to
136 allocate in each subroutine we make. */
138 static int max_depth;
140 /* This table contains a list of the rtl codes that can possibly match a
141 predicate defined in recog.c. The function `not_both_true' uses it to
142 deduce that there are no expressions that can be matches by certain pairs
143 of tree nodes. Also, if a predicate can match only one code, we can
144 hardwire that code into the node testing the predicate. */
146 static struct pred_table
149 RTX_CODE codes[NUM_RTX_CODE];
151 = {{"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
152 LABEL_REF, SUBREG, REG, MEM}},
153 #ifdef PREDICATE_CODES
156 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
157 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
158 {"register_operand", {SUBREG, REG}},
159 {"scratch_operand", {SCRATCH, REG}},
160 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
162 {"const_int_operand", {CONST_INT}},
163 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
164 {"nonimmediate_operand", {SUBREG, REG, MEM}},
165 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
166 LABEL_REF, SUBREG, REG}},
167 {"push_operand", {MEM}},
168 {"pop_operand", {MEM}},
169 {"memory_operand", {SUBREG, MEM}},
170 {"indirect_operand", {SUBREG, MEM}},
171 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}},
172 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
173 LABEL_REF, SUBREG, REG, MEM}}};
175 #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
177 static struct decision_head make_insn_sequence PROTO((rtx, enum routine_type));
178 static struct decision *add_to_sequence PROTO((rtx, struct decision_head *,
180 enum routine_type, int));
181 static int not_both_true PROTO((struct decision *, struct decision *,
183 static int position_merit PROTO((struct decision *, enum machine_mode,
185 static struct decision_head merge_trees PROTO((struct decision_head,
186 struct decision_head));
187 static int break_out_subroutines PROTO((struct decision_head,
188 enum routine_type, int));
189 static void write_subroutine PROTO((struct decision *, enum routine_type));
190 static void write_tree_1 PROTO((struct decision *, const char *,
191 struct decision *, enum routine_type));
192 static void print_code PROTO((enum rtx_code));
193 static int same_codes PROTO((struct decision *, enum rtx_code));
194 static void clear_codes PROTO((struct decision *));
195 static int same_modes PROTO((struct decision *, enum machine_mode));
196 static void clear_modes PROTO((struct decision *));
197 static void write_tree PROTO((struct decision *, const char *,
198 struct decision *, int,
200 static void change_state PROTO((const char *, const char *, int,
203 /* Construct and return a sequence of decisions
204 that will recognize INSN.
206 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
208 static struct decision_head
209 make_insn_sequence (insn, type)
211 enum routine_type type;
214 char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
215 struct decision *last;
216 struct decision_head head;
219 static const char *last_real_name = "insn";
220 static int last_real_code = 0;
223 if (insn_name_ptr_size <= next_insn_code)
226 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
227 insn_name_ptr = xrealloc (insn_name_ptr, sizeof(char *) * new_size);
228 memset (insn_name_ptr + insn_name_ptr_size, 0,
229 sizeof(char *) * (new_size - insn_name_ptr_size));
230 insn_name_ptr_size = new_size;
234 name = XSTR (insn, 0);
235 if (!name || name[0] == '\0')
237 name = xmalloc (strlen (last_real_name) + 10);
238 sprintf (name, "%s+%d", last_real_name,
239 next_insn_code - last_real_code);
243 last_real_name = name;
244 last_real_code = next_insn_code;
247 insn_name_ptr[next_insn_code] = name;
250 if (type == PEEPHOLE2)
254 /* peephole2 gets special treatment:
255 - X always gets an outer parallel even if it's only one entry
256 - we remove all traces of outer-level match_scratch and match_dup
258 x = rtx_alloc (PARALLEL);
259 PUT_MODE (x, VOIDmode);
260 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
261 for (i = j = 0; i < XVECLEN (insn, 0); i++)
263 rtx tmp = XVECEXP (insn, 0, i);
264 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
266 XVECEXP (x, 0, j) = tmp;
272 else if (XVECLEN (insn, type == RECOG) == 1)
273 x = XVECEXP (insn, type == RECOG, 0);
276 x = rtx_alloc (PARALLEL);
277 XVEC (x, 0) = XVEC (insn, type == RECOG);
278 PUT_MODE (x, VOIDmode);
281 last = add_to_sequence (x, &head, "", type, 1);
284 last->c_test = c_test;
285 last->insn_code_number = next_insn_code;
286 last->num_clobbers_to_add = 0;
288 /* If this is not a DEFINE_SPLIT and X is a PARALLEL, see if it ends with a
289 group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. If so, set up
290 to recognize the pattern without these CLOBBERs. */
292 if (type == RECOG && GET_CODE (x) == PARALLEL)
296 for (i = XVECLEN (x, 0); i > 0; i--)
297 if (GET_CODE (XVECEXP (x, 0, i - 1)) != CLOBBER
298 || (GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != REG
299 && GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != MATCH_SCRATCH))
302 if (i != XVECLEN (x, 0))
305 struct decision_head clobber_head;
308 new = XVECEXP (x, 0, 0);
313 new = rtx_alloc (PARALLEL);
314 XVEC (new, 0) = rtvec_alloc (i);
315 for (j = i - 1; j >= 0; j--)
316 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
319 last = add_to_sequence (new, &clobber_head, "", type, 1);
322 last->c_test = c_test;
323 last->insn_code_number = next_insn_code;
324 last->num_clobbers_to_add = XVECLEN (x, 0) - i;
326 head = merge_trees (head, clobber_head);
333 /* Define the subroutine we will call below and emit in genemit. */
334 printf ("extern rtx gen_split_%d PROTO ((rtx *));\n",
335 last->insn_code_number);
337 else if (type == PEEPHOLE2)
338 /* Define the subroutine we will call below and emit in genemit. */
339 printf ("extern rtx gen_peephole2_%d PROTO ((rtx, rtx *));\n",
340 last->insn_code_number);
345 /* Create a chain of nodes to verify that an rtl expression matches
348 LAST is a pointer to the listhead in the previous node in the chain (or
349 in the calling function, for the first node).
351 POSITION is the string representing the current position in the insn.
353 INSN_TYPE is the type of insn for which we are emitting code.
355 A pointer to the final node in the chain is returned. */
357 static struct decision *
358 add_to_sequence (pattern, last, position, insn_type, top)
360 struct decision_head *last;
361 const char *position;
362 enum routine_type insn_type;
365 register RTX_CODE code;
366 register struct decision *new
367 = (struct decision *) xmalloc (sizeof (struct decision));
368 struct decision *this;
370 register const char *fmt;
372 int depth = strlen (position);
375 if (depth > max_depth)
378 new->number = next_number++;
379 new->position = xstrdup (position);
380 new->ignore_code = 0;
381 new->ignore_mode = 0;
382 new->enforce_mode = 1;
383 new->retest_code = new->retest_mode = 0;
385 new->test_elt_zero_int = 0;
386 new->test_elt_one_int = 0;
387 new->test_elt_zero_wide = 0;
388 new->elt_zero_int = 0;
389 new->elt_one_int = 0;
390 new->elt_zero_wide = 0;
394 new->success.first = new->success.last = 0;
395 new->insn_code_number = -1;
396 new->num_clobbers_to_add = 0;
402 new->label_needed = 0;
403 new->subroutine_number = 0;
407 last->first = last->last = new;
409 newpos = (char *) alloca (depth + 2);
410 strcpy (newpos, position);
411 newpos[depth + 1] = 0;
415 new->mode = GET_MODE (pattern);
416 new->code = code = GET_CODE (pattern);
421 /* Toplevel peephole pattern. */
422 if (insn_type == PEEPHOLE2 && top)
424 struct decision_head *place = last;
426 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
428 /* Which insn we're looking at is represented by A-Z. We don't
429 ever use 'A', however; it is always implied. */
431 newpos[depth] = 'A' + i;
434 new = add_to_sequence (XVECEXP (pattern, 0, i),
435 place, newpos, insn_type, 0);
436 place = &new->success;
446 new->opno = XINT (pattern, 0);
447 new->code = (code == MATCH_PARALLEL ? PARALLEL : UNKNOWN);
448 new->enforce_mode = 0;
450 if (code == MATCH_SCRATCH)
451 new->tests = "scratch_operand";
453 new->tests = XSTR (pattern, 1);
455 if (*new->tests == 0)
458 /* See if we know about this predicate and save its number. If we do,
459 and it only accepts one code, note that fact. The predicate
460 `const_int_operand' only tests for a CONST_INT, so if we do so we
461 can avoid calling it at all.
463 Finally, if we know that the predicate does not allow CONST_INT, we
464 know that the only way the predicate can match is if the modes match
465 (here we use the kludge of relying on the fact that "address_operand"
466 accepts CONST_INT; otherwise, it would have to be a special case),
467 so we can test the mode (but we need not). This fact should
468 considerably simplify the generated code. */
472 for (i = 0; i < NUM_KNOWN_PREDS; i++)
473 if (! strcmp (preds[i].name, new->tests))
476 int allows_const_int = 0;
480 if (preds[i].codes[1] == 0 && new->code == UNKNOWN)
482 new->code = preds[i].codes[0];
483 if (! strcmp ("const_int_operand", new->tests))
484 new->tests = 0, new->pred = -1;
487 for (j = 0; j < NUM_RTX_CODE && preds[i].codes[j] != 0; j++)
488 if (preds[i].codes[j] == CONST_INT)
489 allows_const_int = 1;
491 if (! allows_const_int)
492 new->enforce_mode = new->ignore_mode= 1;
497 #ifdef PREDICATE_CODES
498 /* If the port has a list of the predicates it uses but omits
500 if (i == NUM_KNOWN_PREDS)
501 fprintf (stderr, "Warning: `%s' not in PREDICATE_CODES\n",
506 if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
508 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
510 newpos[depth] = i + (code == MATCH_OPERATOR ? '0': 'a');
511 new = add_to_sequence (XVECEXP (pattern, 2, i),
512 &new->success, newpos, insn_type, 0);
519 new->opno = XINT (pattern, 0);
520 new->dupno = XINT (pattern, 0);
523 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
525 newpos[depth] = i + '0';
526 new = add_to_sequence (XVECEXP (pattern, 1, i),
527 &new->success, newpos, insn_type, 0);
533 new->dupno = XINT (pattern, 0);
535 new->enforce_mode = 0;
539 pattern = XEXP (pattern, 0);
543 /* The operands of a SET must have the same mode unless one is VOIDmode. */
544 if (GET_MODE (SET_SRC (pattern)) != VOIDmode
545 && GET_MODE (SET_DEST (pattern)) != VOIDmode
546 && GET_MODE (SET_SRC (pattern)) != GET_MODE (SET_DEST (pattern))
547 /* The mode of an ADDRESS_OPERAND is the mode of the memory reference,
548 not the mode of the address. */
549 && ! (GET_CODE (SET_SRC (pattern)) == MATCH_OPERAND
550 && ! strcmp (XSTR (SET_SRC (pattern), 1), "address_operand")))
552 print_rtl (stderr, pattern);
553 fputc ('\n', stderr);
554 fatal ("mode mismatch in SET");
557 new = add_to_sequence (SET_DEST (pattern), &new->success, newpos,
559 this->success.first->enforce_mode = 1;
561 new = add_to_sequence (SET_SRC (pattern), &new->success, newpos,
564 /* If set are setting CC0 from anything other than a COMPARE, we
565 must enforce the mode so that we do not produce ambiguous insns. */
566 if (GET_CODE (SET_DEST (pattern)) == CC0
567 && GET_CODE (SET_SRC (pattern)) != COMPARE)
568 this->success.first->enforce_mode = 1;
573 case STRICT_LOW_PART:
575 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos,
577 this->success.first->enforce_mode = 1;
581 this->test_elt_one_int = 1;
582 this->elt_one_int = XINT (pattern, 1);
584 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos,
586 this->success.first->enforce_mode = 1;
592 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos,
594 this->success.first->enforce_mode = 1;
596 new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos,
599 new = add_to_sequence (XEXP (pattern, 2), &new->success, newpos,
603 case EQ: case NE: case LE: case LT: case GE: case GT:
604 case LEU: case LTU: case GEU: case GTU:
605 /* If the first operand is (cc0), we don't have to do anything
607 if (GET_CODE (XEXP (pattern, 0)) == CC0)
610 /* ... fall through ... */
613 /* Enforce the mode on the first operand to avoid ambiguous insns. */
615 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos,
617 this->success.first->enforce_mode = 1;
619 new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos,
627 fmt = GET_RTX_FORMAT (code);
628 len = GET_RTX_LENGTH (code);
629 for (i = 0; i < (size_t) len; i++)
631 newpos[depth] = '0' + i;
632 if (fmt[i] == 'e' || fmt[i] == 'u')
633 new = add_to_sequence (XEXP (pattern, i), &new->success, newpos,
635 else if (fmt[i] == 'i' && i == 0)
637 this->test_elt_zero_int = 1;
638 this->elt_zero_int = XINT (pattern, i);
640 else if (fmt[i] == 'i' && i == 1)
642 this->test_elt_one_int = 1;
643 this->elt_one_int = XINT (pattern, i);
645 else if (fmt[i] == 'w' && i == 0)
647 this->test_elt_zero_wide = 1;
648 this->elt_zero_wide = XWINT (pattern, i);
650 else if (fmt[i] == 'E')
653 /* We do not handle a vector appearing as other than
654 the first item, just because nothing uses them
655 and by handling only the special case
656 we can use one element in newpos for either
657 the item number of a subexpression
658 or the element number in a vector. */
661 this->veclen = XVECLEN (pattern, i);
662 for (j = 0; j < XVECLEN (pattern, i); j++)
664 newpos[depth] = 'a' + j;
665 new = add_to_sequence (XVECEXP (pattern, i, j),
666 &new->success, newpos, insn_type, 0);
669 else if (fmt[i] != '0')
675 /* Return 1 if we can prove that there is no RTL that can match both
676 D1 and D2. Otherwise, return 0 (it may be that there is an RTL that
677 can match both or just that we couldn't prove there wasn't such an RTL).
679 TOPLEVEL is non-zero if we are to only look at the top level and not
680 recursively descend. */
683 not_both_true (d1, d2, toplevel)
684 struct decision *d1, *d2;
687 struct decision *p1, *p2;
690 /* Don't compare strings on the different positions in insn. Doing so
691 is incorrect and results in false matches from constructs like
693 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
694 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
696 [(set (match_operand:HI "register_operand" "r")
697 (match_operand:HI "register_operand" "r"))]
699 If we are presented with such, we are recursing through the remainder
700 of a node's success nodes (from the loop at the end of this function).
701 Skip forward until we come to a position that matches.
703 Due to the way position strings are constructed, we know that iterating
704 forward from the lexically lower position (e.g. "00") will run into
705 the lexically higher position (e.g. "1") and not the other way around.
706 This saves a bit of effort. */
708 cmp = strcmp (d1->position, d2->position);
714 /* If the d2->position was lexically lower, swap. */
716 p1 = d1, d1 = d2, d2 = p1;
718 if (d1->success.first == 0)
720 for (p1 = d1->success.first; p1; p1 = p1->next)
721 if (! not_both_true (p1, d2, 0))
727 /* If they are both to test modes and the modes are different, they aren't
728 both true. Similarly for codes, integer elements, and vector lengths. */
730 if ((d1->enforce_mode && d2->enforce_mode
731 && d1->mode != VOIDmode && d2->mode != VOIDmode && d1->mode != d2->mode)
732 || (d1->code != UNKNOWN && d2->code != UNKNOWN && d1->code != d2->code)
733 || (d1->test_elt_zero_int && d2->test_elt_zero_int
734 && d1->elt_zero_int != d2->elt_zero_int)
735 || (d1->test_elt_one_int && d2->test_elt_one_int
736 && d1->elt_one_int != d2->elt_one_int)
737 || (d1->test_elt_zero_wide && d2->test_elt_zero_wide
738 && d1->elt_zero_wide != d2->elt_zero_wide)
739 || (d1->veclen && d2->veclen && d1->veclen != d2->veclen))
742 /* If either is a wild-card MATCH_OPERAND without a predicate, it can match
743 absolutely anything, so we can't say that no intersection is possible.
744 This case is detected by having a zero TESTS field with a code of
747 if ((d1->tests == 0 && d1->code == UNKNOWN)
748 || (d2->tests == 0 && d2->code == UNKNOWN))
751 /* If either has a predicate that we know something about, set things up so
752 that D1 is the one that always has a known predicate. Then see if they
753 have any codes in common. */
755 if (d1->pred >= 0 || d2->pred >= 0)
760 p1 = d1, d1 = d2, d2 = p1;
762 /* If D2 tests an explicit code, see if it is in the list of valid codes
763 for D1's predicate. */
764 if (d2->code != UNKNOWN)
766 for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++)
767 if (preds[d1->pred].codes[i] == d2->code)
770 if (preds[d1->pred].codes[i] == 0)
774 /* Otherwise see if the predicates have any codes in common. */
776 else if (d2->pred >= 0)
778 for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++)
780 for (j = 0; j < NUM_RTX_CODE; j++)
781 if (preds[d2->pred].codes[j] == 0
782 || preds[d2->pred].codes[j] == preds[d1->pred].codes[i])
785 if (preds[d2->pred].codes[j] != 0)
789 if (preds[d1->pred].codes[i] == 0)
794 /* If we got here, we can't prove that D1 and D2 cannot both be true.
795 If we are only to check the top level, return 0. Otherwise, see if
796 we can prove that all choices in both successors are mutually
797 exclusive. If either does not have any successors, we can't prove
798 they can't both be true. */
800 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
803 for (p1 = d1->success.first; p1; p1 = p1->next)
804 for (p2 = d2->success.first; p2; p2 = p2->next)
805 if (! not_both_true (p1, p2, 0))
811 /* Assuming that we can reorder all the alternatives at a specific point in
812 the tree (see discussion in merge_trees), we would prefer an ordering of
813 nodes where groups of consecutive nodes test the same mode and, within each
814 mode, groups of nodes test the same code. With this order, we can
815 construct nested switch statements, the inner one to test the code and
816 the outer one to test the mode.
818 We would like to list nodes testing for specific codes before those
819 that test predicates to avoid unnecessary function calls. Similarly,
820 tests for specific modes should precede nodes that allow any mode.
822 This function returns the merit (with 0 being the best) of inserting
823 a test involving the specified MODE and CODE after node P. If P is
824 zero, we are to determine the merit of inserting the test at the front
828 position_merit (p, mode, code)
830 enum machine_mode mode;
833 enum machine_mode p_mode;
835 /* The only time the front of the list is anything other than the worst
836 position is if we are testing a mode that isn't VOIDmode. */
838 return mode == VOIDmode ? 3 : 2;
840 p_mode = p->enforce_mode ? p->mode : VOIDmode;
842 /* The best case is if the codes and modes both match. */
843 if (p_mode == mode && p->code== code)
846 /* If the codes don't match, the next best case is if the modes match.
847 In that case, the best position for this node depends on whether
848 we are testing for a specific code or not. If we are, the best place
849 is after some other test for an explicit code and our mode or after
850 the last test in the previous mode if every test in our mode is for
853 If we are testing for UNKNOWN, then the next best case is at the end of
857 && ((p_mode == mode && p->code != UNKNOWN)
858 || (p_mode != mode && p->next
859 && (p->next->enforce_mode ? p->next->mode : VOIDmode) == mode
860 && (p->next->code == UNKNOWN))))
861 || (code == UNKNOWN && p_mode == mode
863 || (p->next->enforce_mode ? p->next->mode : VOIDmode) != mode)))
866 /* The third best case occurs when nothing is testing MODE. If MODE
867 is not VOIDmode, then the third best case is after something of any
868 mode that is not VOIDmode. If we are testing VOIDmode, the third best
869 place is the end of the list. */
872 && ((mode != VOIDmode && p_mode != VOIDmode)
873 || (mode == VOIDmode && p->next == 0)))
876 /* Otherwise, we have the worst case. */
880 /* Merge two decision tree listheads OLDH and ADDH,
881 modifying OLDH destructively, and return the merged tree. */
883 static struct decision_head
884 merge_trees (oldh, addh)
885 register struct decision_head oldh, addh;
887 struct decision *add, *next;
895 /* If we are adding things at different positions, something is wrong. */
896 if (strcmp (oldh.first->position, addh.first->position))
899 for (add = addh.first; add; add = next)
901 enum machine_mode add_mode = add->enforce_mode ? add->mode : VOIDmode;
902 struct decision *best_position = 0;
904 struct decision *old;
908 /* The semantics of pattern matching state that the tests are done in
909 the order given in the MD file so that if an insn matches two
910 patterns, the first one will be used. However, in practice, most,
911 if not all, patterns are unambiguous so that their order is
912 independent. In that case, we can merge identical tests and
913 group all similar modes and codes together.
915 Scan starting from the end of OLDH until we reach a point
916 where we reach the head of the list or where we pass a pattern
917 that could also be true if NEW is true. If we find an identical
918 pattern, we can merge them. Also, record the last node that tests
919 the same code and mode and the last one that tests just the same mode.
921 If we have no match, place NEW after the closest match we found. */
923 for (old = oldh.last; old; old = old->prev)
927 /* If we don't have anything to test except an additional test,
928 do not consider the two nodes equal. If we did, the test below
929 would cause an infinite recursion. */
930 if (old->tests == 0 && old->test_elt_zero_int == 0
931 && old->test_elt_one_int == 0 && old->veclen == 0
932 && old->test_elt_zero_wide == 0
933 && old->dupno == -1 && old->mode == VOIDmode
934 && old->code == UNKNOWN
935 && (old->c_test != 0 || add->c_test != 0))
938 else if ((old->tests == add->tests
939 || (old->pred >= 0 && old->pred == add->pred)
940 || (old->tests && add->tests
941 && !strcmp (old->tests, add->tests)))
942 && old->test_elt_zero_int == add->test_elt_zero_int
943 && old->elt_zero_int == add->elt_zero_int
944 && old->test_elt_one_int == add->test_elt_one_int
945 && old->elt_one_int == add->elt_one_int
946 && old->test_elt_zero_wide == add->test_elt_zero_wide
947 && old->elt_zero_wide == add->elt_zero_wide
948 && old->veclen == add->veclen
949 && old->dupno == add->dupno
950 && old->opno == add->opno
951 && old->code == add->code
952 && old->enforce_mode == add->enforce_mode
953 && old->mode == add->mode)
955 /* If the additional test is not the same, split both nodes
956 into nodes that just contain all things tested before the
957 additional test and nodes that contain the additional test
958 and actions when it is true. This optimization is important
959 because of the case where we have almost identical patterns
960 with different tests on target flags. */
962 if (old->c_test != add->c_test
963 && ! (old->c_test && add->c_test
964 && !strcmp (old->c_test, add->c_test)))
966 if (old->insn_code_number >= 0 || old->opno >= 0)
968 struct decision *split
969 = (struct decision *) xmalloc (sizeof (struct decision));
971 memcpy (split, old, sizeof (struct decision));
973 old->success.first = old->success.last = split;
976 old->insn_code_number = -1;
977 old->num_clobbers_to_add = 0;
979 split->number = next_number++;
980 split->next = split->prev = 0;
981 split->mode = VOIDmode;
982 split->code = UNKNOWN;
984 split->test_elt_zero_int = 0;
985 split->test_elt_one_int = 0;
986 split->test_elt_zero_wide = 0;
992 if (add->insn_code_number >= 0 || add->opno >= 0)
994 struct decision *split
995 = (struct decision *) xmalloc (sizeof (struct decision));
997 memcpy (split, add, sizeof (struct decision));
999 add->success.first = add->success.last = split;
1002 add->insn_code_number = -1;
1003 add->num_clobbers_to_add = 0;
1005 split->number = next_number++;
1006 split->next = split->prev = 0;
1007 split->mode = VOIDmode;
1008 split->code = UNKNOWN;
1010 split->test_elt_zero_int = 0;
1011 split->test_elt_one_int = 0;
1012 split->test_elt_zero_wide = 0;
1019 if (old->insn_code_number >= 0 && add->insn_code_number >= 0)
1021 /* If one node is for a normal insn and the second is
1022 for the base insn with clobbers stripped off, the
1023 second node should be ignored. */
1025 if (old->num_clobbers_to_add == 0
1026 && add->num_clobbers_to_add > 0)
1027 /* Nothing to do here. */
1029 else if (old->num_clobbers_to_add > 0
1030 && add->num_clobbers_to_add == 0)
1032 /* In this case, replace OLD with ADD. */
1033 old->insn_code_number = add->insn_code_number;
1034 old->num_clobbers_to_add = 0;
1037 fatal ("Two actions at one point in tree for insns \"%s\" (%d) and \"%s\" (%d)",
1038 insn_name_ptr[old->insn_code_number],
1039 old->insn_code_number,
1040 insn_name_ptr[add->insn_code_number],
1041 add->insn_code_number);
1044 if (old->insn_code_number == -1)
1045 old->insn_code_number = add->insn_code_number;
1046 old->success = merge_trees (old->success, add->success);
1051 /* Unless we have already found the best possible insert point,
1052 see if this position is better. If so, record it. */
1055 && ((our_merit = position_merit (old, add_mode, add->code))
1057 best_merit = our_merit, best_position = old;
1059 if (! not_both_true (old, add, 0))
1063 /* If ADD was duplicate, we are done. */
1067 /* Otherwise, find the best place to insert ADD. Normally this is
1068 BEST_POSITION. However, if we went all the way to the top of
1069 the list, it might be better to insert at the top. */
1071 if (best_position == 0)
1075 && position_merit (NULL_PTR, add_mode, add->code) < best_merit)
1078 add->next = oldh.first;
1079 oldh.first->prev = add;
1085 add->prev = best_position;
1086 add->next = best_position->next;
1087 best_position->next = add;
1088 if (best_position == oldh.last)
1091 add->next->prev = add;
1098 /* Count the number of subnodes of HEAD. If the number is high enough,
1099 make the first node in HEAD start a separate subroutine in the C code
1102 TYPE gives the type of routine we are writing.
1104 INITIAL is non-zero if this is the highest-level node. We never write
1108 break_out_subroutines (head, type, initial)
1109 struct decision_head head;
1110 enum routine_type type;
1114 struct decision *sub;
1116 for (sub = head.first; sub; sub = sub->next)
1117 size += 1 + break_out_subroutines (sub->success, type, 0);
1119 if (size > SUBROUTINE_THRESHOLD && ! initial)
1121 head.first->subroutine_number = ++next_subroutine_number;
1122 write_subroutine (head.first, type);
1128 /* Write out a subroutine of type TYPE to do comparisons starting at node
1132 write_subroutine (tree, type)
1133 struct decision *tree;
1134 enum routine_type type;
1138 if (type == PEEPHOLE2)
1139 printf ("extern rtx peephole2");
1140 else if (type == SPLIT)
1141 printf ("extern rtx split");
1143 printf ("extern int recog");
1144 if (tree != 0 && tree->subroutine_number > 0)
1145 printf ("_%d", tree->subroutine_number);
1146 else if (type == SPLIT)
1148 printf (" PROTO ((rtx, rtx");
1151 else if (type == PEEPHOLE2)
1155 if (type == PEEPHOLE2)
1156 printf ("rtx\npeephole2");
1157 else if (type == SPLIT)
1158 printf ("rtx\nsplit");
1160 printf ("int\nrecog");
1162 if (tree != 0 && tree->subroutine_number > 0)
1163 printf ("_%d", tree->subroutine_number);
1164 else if (IS_SPLIT (type))
1167 printf (" (x0, insn");
1169 printf (", pnum_clobbers");
1170 else if (type == PEEPHOLE2)
1171 printf (", _plast_insn");
1174 /* The peephole2 pass uses the insn argument to determine which
1175 hard registers are available at that point. */
1176 printf (" register rtx x0;\n rtx insn ATTRIBUTE_UNUSED;\n");
1178 printf (" int *pnum_clobbers ATTRIBUTE_UNUSED;\n");
1179 else if (type == PEEPHOLE2)
1180 printf (" rtx *_plast_insn ATTRIBUTE_UNUSED;\n");
1183 printf (" register rtx *ro = &recog_data.operand[0];\n");
1185 printf (" register rtx ");
1186 for (i = 1; i < max_depth; i++)
1187 printf ("x%d ATTRIBUTE_UNUSED, ", i);
1189 printf ("x%d ATTRIBUTE_UNUSED;\n", max_depth);
1190 if (type == PEEPHOLE2)
1191 printf (" register rtx _last_insn = insn;\n");
1192 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
1193 write_tree (tree, "", NULL_PTR, 1, type);
1194 if (type == PEEPHOLE2)
1195 printf (" ret1:\n *_plast_insn = _last_insn;\n return tem;\n");
1196 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
1199 /* This table is used to indent the recog_* functions when we are inside
1200 conditions or switch statements. We only support small indentations
1201 and always indent at least two spaces. */
1203 static const char *indents[]
1204 = {" ", " ", " ", " ", " ", " ", " ", " ",
1205 "\t", "\t ", "\t ", "\t ", "\t ", "\t ", "\t ",
1206 "\t\t", "\t\t ", "\t\t ", "\t\t ", "\t\t ", "\t\t "};
1208 /* Write out C code to perform the decisions in TREE for a subroutine of
1209 type TYPE. If all of the choices fail, branch to node AFTERWARD, if
1210 non-zero, otherwise return. PREVPOS is the position of the node that
1211 branched to this test.
1213 When we merged all alternatives, we tried to set up a convenient order.
1214 Specifically, tests involving the same mode are all grouped together,
1215 followed by a group that does not contain a mode test. Within each group
1216 of the same mode, we also group tests with the same code, followed by a
1217 group that does not test a code.
1219 Occasionally, we cannot arbitrarily reorder the tests so that multiple
1220 sequence of groups as described above are present.
1222 We generate two nested switch statements, the outer statement for
1223 testing modes, and the inner switch for testing RTX codes. It is
1224 not worth optimizing cases when only a small number of modes or
1225 codes is tested, since the compiler can do that when compiling the
1226 resulting function. We do check for when every test is the same mode
1230 write_tree_1 (tree, prevpos, afterward, type)
1231 struct decision *tree;
1232 const char *prevpos;
1233 struct decision *afterward;
1234 enum routine_type type;
1236 register struct decision *p, *p1;
1237 register int depth = tree ? strlen (tree->position) : 0;
1238 enum machine_mode switch_mode = VOIDmode;
1239 RTX_CODE switch_code = UNKNOWN;
1241 char modemap[NUM_MACHINE_MODES];
1242 char codemap[NUM_RTX_CODE];
1246 /* One tricky area is what is the exact state when we branch to a
1247 node's label. There are two cases where we branch: when looking at
1248 successors to a node, or when a set of tests fails.
1250 In the former case, we are always branching to the first node in a
1251 decision list and we want all required tests to be performed. We
1252 put the labels for such nodes in front of any switch or test statements.
1253 These branches are done without updating the position to that of the
1256 In the latter case, we are branching to a node that is not the first
1257 node in a decision list. We have already checked that it is possible
1258 for both the node we originally tested at this level and the node we
1259 are branching to to both match some pattern. That means that they
1260 usually will be testing the same mode and code. So it is normally safe
1261 for such labels to be inside switch statements, since the tests done
1262 by virtue of arriving at that label will usually already have been
1263 done. The exception is a branch from a node that does not test a
1264 mode or code to one that does. In such cases, we set the `retest_mode'
1265 or `retest_code' flags. That will ensure that we start a new switch
1266 at that position and put the label before the switch.
1268 The branches in the latter case must set the position to that of the
1273 if (tree && tree->subroutine_number == 0)
1275 OUTPUT_LABEL (" ", tree->number);
1276 tree->label_needed = 0;
1281 change_state (prevpos, tree->position, 2, afterward);
1282 prevpos = tree->position;
1285 for (p = tree; p; p = p->next)
1287 enum machine_mode mode = p->enforce_mode ? p->mode : VOIDmode;
1289 int wrote_bracket = 0;
1292 if (p->success.first == 0 && p->insn_code_number < 0)
1295 /* Find the next alternative to p that might be true when p is true.
1296 Test that one next if p's successors fail. */
1298 for (p1 = p->next; p1 && not_both_true (p, p1, 1); p1 = p1->next)
1304 if (mode == VOIDmode && p1->enforce_mode && p1->mode != VOIDmode)
1305 p1->retest_mode = 1;
1306 if (p->code == UNKNOWN && p1->code != UNKNOWN)
1307 p1->retest_code = 1;
1308 p1->label_needed = 1;
1311 /* If we have a different code or mode than the last node and
1312 are in a switch on codes, we must either end the switch or
1313 go to another case. We must also end the switch if this
1314 node needs a label and to retest either the mode or code. */
1316 if (switch_code != UNKNOWN
1317 && (switch_code != p->code || switch_mode != mode
1318 || (p->label_needed && (p->retest_mode || p->retest_code))))
1320 enum rtx_code code = p->code;
1322 /* If P is testing a predicate that we know about and we haven't
1323 seen any of the codes that are valid for the predicate, we
1324 can write a series of "case" statement, one for each possible
1325 code. Since we are already in a switch, these redundant tests
1326 are very cheap and will reduce the number of predicate called. */
1330 for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i] != 0; i++)
1331 if (codemap[(int) preds[p->pred].codes[i]])
1334 if (preds[p->pred].codes[i] == 0)
1335 code = MATCH_OPERAND;
1338 if (code == UNKNOWN || codemap[(int) code]
1339 || switch_mode != mode
1340 || (p->label_needed && (p->retest_mode || p->retest_code)))
1342 printf ("%s}\n", indents[indent - 2]);
1343 switch_code = UNKNOWN;
1349 printf ("%sbreak;\n", indents[indent]);
1351 if (code == MATCH_OPERAND)
1353 for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i] != 0; i++)
1355 printf ("%scase ", indents[indent - 2]);
1356 print_code (preds[p->pred].codes[i]);
1358 codemap[(int) preds[p->pred].codes[i]] = 1;
1363 printf ("%scase ", indents[indent - 2]);
1366 codemap[(int) p->code] = 1;
1375 /* If we were previously in a switch on modes and now have a different
1376 mode, end at least the case, and maybe end the switch if we are
1377 not testing a mode or testing a mode whose case we already saw. */
1379 if (switch_mode != VOIDmode
1380 && (switch_mode != mode || (p->label_needed && p->retest_mode)))
1382 if (mode == VOIDmode || modemap[(int) mode]
1383 || (p->label_needed && p->retest_mode))
1385 printf ("%s}\n", indents[indent - 2]);
1386 switch_mode = VOIDmode;
1392 printf (" break;\n");
1393 printf (" case %smode:\n", GET_MODE_NAME (mode));
1395 modemap[(int) mode] = 1;
1401 /* If we are about to write dead code, something went wrong. */
1402 if (! p->label_needed && uncond)
1405 /* If we need a label and we will want to retest the mode or code at
1406 that label, write the label now. We have already ensured that
1407 things will be valid for the test. */
1409 if (p->label_needed && (p->retest_mode || p->retest_code))
1411 OUTPUT_LABEL (indents[indent - 2], p->number);
1412 p->label_needed = 0;
1417 /* If we are not in any switches, see if we can shortcut things
1418 by checking for identical modes and codes. */
1420 if (switch_mode == VOIDmode && switch_code == UNKNOWN)
1422 /* If p and its alternatives all want the same mode,
1423 reject all others at once, first, then ignore the mode. */
1425 if (mode != VOIDmode && p->next && same_modes (p, mode))
1427 printf (" if (GET_MODE (x%d) != %smode)\n",
1428 depth, GET_MODE_NAME (p->mode));
1432 change_state (p->position, afterward->position, 6,
1434 printf (" goto L%d;\n }\n", afterward->number);
1437 printf (" goto ret0;\n");
1442 /* If p and its alternatives all want the same code,
1443 reject all others at once, first, then ignore the code. */
1445 if (p->code != UNKNOWN && p->next && same_codes (p, p->code))
1447 printf (" if (GET_CODE (x%d) != ", depth);
1448 print_code (p->code);
1453 change_state (p->position, afterward->position, indent + 4,
1455 printf (" goto L%d;\n }\n", afterward->number);
1458 printf (" goto ret0;\n");
1463 /* If we are not in a mode switch and we are testing for a specific
1464 mode, start a mode switch unless we have just one node or the next
1465 node is not testing a mode (we have already tested for the case of
1466 more than one mode, but all of the same mode). */
1468 if (switch_mode == VOIDmode && mode != VOIDmode && p->next != 0
1469 && p->next->enforce_mode && p->next->mode != VOIDmode)
1471 memset (modemap, 0, sizeof modemap);
1472 printf ("%sswitch (GET_MODE (x%d))\n", indents[indent], depth);
1473 printf ("%s{\n", indents[indent + 2]);
1475 printf ("%sdefault:\n%sbreak;\n", indents[indent - 2],
1477 printf ("%scase %smode:\n", indents[indent - 2],
1478 GET_MODE_NAME (mode));
1479 modemap[(int) mode] = 1;
1483 /* Similarly for testing codes. */
1485 if (switch_code == UNKNOWN && p->code != UNKNOWN && ! p->ignore_code
1486 && p->next != 0 && p->next->code != UNKNOWN)
1488 memset (codemap, 0, sizeof codemap);
1489 printf ("%sswitch (GET_CODE (x%d))\n", indents[indent], depth);
1490 printf ("%s{\n", indents[indent + 2]);
1492 printf ("%sdefault:\n%sbreak;\n", indents[indent - 2],
1494 printf ("%scase ", indents[indent - 2]);
1495 print_code (p->code);
1497 codemap[(int) p->code] = 1;
1498 switch_code = p->code;
1501 /* Now that most mode and code tests have been done, we can write out
1502 a label for an inner node, if we haven't already. */
1503 if (p->label_needed)
1504 OUTPUT_LABEL (indents[indent - 2], p->number);
1506 inner_indent = indent;
1508 /* The only way we can have to do a mode or code test here is if
1509 this node needs such a test but is the only node to be tested.
1510 In that case, we won't have started a switch. Note that this is
1511 the only way the switch and test modes can disagree. */
1513 if ((mode != switch_mode && ! p->ignore_mode)
1514 || (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code)
1515 || p->test_elt_zero_int || p->test_elt_one_int
1516 || p->test_elt_zero_wide || p->veclen
1517 || p->dupno >= 0 || p->tests || p->num_clobbers_to_add)
1519 printf ("%sif (", indents[indent]);
1521 if (mode != switch_mode && ! p->ignore_mode)
1522 printf ("GET_MODE (x%d) == %smode && ",
1523 depth, GET_MODE_NAME (mode));
1524 if (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code)
1526 printf ("GET_CODE (x%d) == ", depth);
1527 print_code (p->code);
1531 if (p->test_elt_zero_int)
1532 printf ("XINT (x%d, 0) == %d && ", depth, p->elt_zero_int);
1533 if (p->test_elt_one_int)
1534 printf ("XINT (x%d, 1) == %d && ", depth, p->elt_one_int);
1535 if (p->test_elt_zero_wide)
1537 /* Set offset to 1 iff the number might get propagated to
1538 unsigned long by ANSI C rules, else 0.
1539 Prospective hosts are required to have at least 32 bit
1540 ints, and integer constants in machine descriptions
1541 must fit in 32 bit, thus it suffices to check only
1543 HOST_WIDE_INT offset = p->elt_zero_wide == -2147483647 - 1;
1544 printf ("XWINT (x%d, 0) == ", depth);
1545 printf (HOST_WIDE_INT_PRINT_DEC, p->elt_zero_wide + offset);
1546 printf ("%s && ", offset ? "-1" : "");
1549 printf ("XVECLEN (x%d, 0) == %d && ", depth, p->veclen);
1551 printf ("rtx_equal_p (x%d, ro[%d]) && ", depth, p->dupno);
1552 if (p->num_clobbers_to_add)
1553 printf ("pnum_clobbers != 0 && ");
1555 printf ("%s (x%d, %smode)", p->tests, depth,
1556 GET_MODE_NAME (p->mode));
1566 need_bracket = ! uncond;
1572 printf ("%s{\n", indents[inner_indent]);
1578 printf ("%sro[%d] = x%d;\n", indents[inner_indent], p->opno, depth);
1583 printf ("%sif (%s)\n", indents[inner_indent], p->c_test);
1589 if (p->insn_code_number >= 0)
1593 printf ("%sreturn gen_split_%d (operands);\n",
1594 indents[inner_indent], p->insn_code_number);
1596 else if (type == PEEPHOLE2)
1598 printf ("%s{\n", indents[inner_indent]);
1601 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1602 indents[inner_indent], p->insn_code_number);
1603 printf ("%sif (tem != 0) goto ret1;\n", indents[inner_indent]);
1605 printf ("%s}\n", indents[inner_indent]);
1609 if (p->num_clobbers_to_add)
1613 printf ("%s{\n", indents[inner_indent]);
1617 printf ("%s*pnum_clobbers = %d;\n",
1618 indents[inner_indent], p->num_clobbers_to_add);
1619 printf ("%sreturn %d;\n",
1620 indents[inner_indent], p->insn_code_number);
1625 printf ("%s}\n", indents[inner_indent]);
1629 printf ("%sreturn %d;\n",
1630 indents[inner_indent], p->insn_code_number);
1634 printf ("%sgoto L%d;\n", indents[inner_indent],
1635 p->success.first->number);
1638 printf ("%s}\n", indents[inner_indent - 2]);
1641 /* We have now tested all alternatives. End any switches we have open
1642 and branch to the alternative node unless we know that we can't fall
1643 through to the branch. */
1645 if (switch_code != UNKNOWN)
1647 printf ("%s}\n", indents[indent - 2]);
1652 if (switch_mode != VOIDmode)
1654 printf ("%s}\n", indents[indent - 2]);
1667 change_state (prevpos, afterward->position, 2, afterward);
1668 printf (" goto L%d;\n", afterward->number);
1671 printf (" goto ret0;\n");
1678 register const char *p1;
1679 for (p1 = GET_RTX_NAME (code); *p1; p1++)
1680 putchar (TOUPPER(*p1));
1684 same_codes (p, code)
1685 register struct decision *p;
1686 register enum rtx_code code;
1688 for (; p; p = p->next)
1689 if (p->code != code)
1697 register struct decision *p;
1699 for (; p; p = p->next)
1704 same_modes (p, mode)
1705 register struct decision *p;
1706 register enum machine_mode mode;
1708 for (; p; p = p->next)
1709 if ((p->enforce_mode ? p->mode : VOIDmode) != mode)
1717 register struct decision *p;
1719 for (; p; p = p->next)
1720 p->enforce_mode = 0;
1723 /* Write out the decision tree starting at TREE for a subroutine of type TYPE.
1725 PREVPOS is the position at the node that branched to this node.
1727 INITIAL is nonzero if this is the first node we are writing in a subroutine.
1729 If all nodes are false, branch to the node AFTERWARD. */
1732 write_tree (tree, prevpos, afterward, initial, type)
1733 struct decision *tree;
1734 const char *prevpos;
1735 struct decision *afterward;
1737 enum routine_type type;
1739 register struct decision *p;
1740 const char *name_prefix;
1741 const char *call_suffix;
1746 name_prefix = "split";
1750 name_prefix = "peephole2";
1751 call_suffix = ", _plast_insn";
1754 name_prefix = "recog";
1755 call_suffix = ", pnum_clobbers";
1760 if (! initial && tree->subroutine_number > 0)
1762 OUTPUT_LABEL (" ", tree->number);
1766 printf (" tem = %s_%d (x0, insn%s);\n",
1767 name_prefix, tree->subroutine_number, call_suffix);
1768 if (IS_SPLIT (type))
1769 printf (" if (tem != 0) return tem;\n");
1771 printf (" if (tem >= 0) return tem;\n");
1772 change_state (tree->position, afterward->position, 2, afterward);
1773 printf (" goto L%d;\n", afterward->number);
1776 printf (" return %s_%d (x0, insn%s);\n",
1777 name_prefix, tree->subroutine_number, call_suffix);
1781 write_tree_1 (tree, prevpos, afterward, type);
1783 for (p = tree; p; p = p->next)
1784 if (p->success.first)
1785 write_tree (p->success.first, p->position,
1786 p->afterward ? p->afterward : afterward, 0, type);
1790 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1791 actions are necessary to move to NEWPOS. If we fail to move to the
1792 new state, branch to node AFTERWARD if non-zero, otherwise return.
1794 INDENT says how many blanks to place at the front of lines.
1796 Failure to move to the new state can only occur if we are trying to
1797 match multiple insns and we try to step past the end of the
1801 change_state (oldpos, newpos, indent, afterward)
1805 struct decision *afterward;
1807 int odepth = strlen (oldpos);
1809 int ndepth = strlen (newpos);
1811 int old_has_insn, new_has_insn;
1813 /* Pop up as many levels as necessary. */
1815 while (strncmp (oldpos, newpos, depth))
1819 /* Make sure to reset the _last_insn pointer when popping back up. */
1820 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1821 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1823 for (new_has_insn = odepth - 1; new_has_insn >= 0; --new_has_insn)
1824 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1827 if (old_has_insn >= 0 && new_has_insn < 0)
1828 printf ("%s_last_insn = insn;\n", indents[indent]);
1830 /* Go down to desired level. */
1832 while (depth < ndepth)
1834 /* It's a different insn from the first one. */
1835 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1837 /* We can only fail if we're moving down the tree. */
1838 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1840 printf ("%s_last_insn = recog_next_insn (insn, %d);\n",
1841 indents[indent], newpos[depth] - 'A');
1845 printf ("%stem = recog_next_insn (insn, %d);\n",
1846 indents[indent], newpos[depth] - 'A');
1848 printf ("%sif (tem == NULL_RTX)\n", indents[indent]);
1850 printf ("%sgoto L%d;\n", indents[indent + 2],
1853 printf ("%sgoto ret0;\n", indents[indent + 2]);
1855 printf ("%s_last_insn = tem;\n", indents[indent]);
1857 printf ("%sx%d = PATTERN (_last_insn);\n",
1858 indents[indent], depth + 1);
1860 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1861 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1862 indents[indent], depth + 1, depth, newpos[depth] - 'a');
1864 printf ("%sx%d = XEXP (x%d, %c);\n",
1865 indents[indent], depth + 1, depth, newpos[depth]);
1874 register size_t len = strlen (input) + 1;
1875 register char *output = xmalloc (len);
1876 memcpy (output, input, len);
1881 xrealloc (old, size)
1887 ptr = (PTR) realloc (old, size);
1889 ptr = (PTR) malloc (size);
1891 fatal ("virtual memory exhausted");
1899 register PTR val = (PTR) malloc (size);
1902 fatal ("virtual memory exhausted");
1906 extern int main PROTO ((int, char **));
1914 struct decision_head recog_tree;
1915 struct decision_head split_tree;
1916 struct decision_head peephole2_tree;
1920 progname = "genrecog";
1921 obstack_init (rtl_obstack);
1922 recog_tree.first = recog_tree.last = split_tree.first = split_tree.last = 0;
1923 peephole2_tree.first = peephole2_tree.last = 0;
1926 fatal ("No input file name.");
1928 infile = fopen (argv[1], "r");
1932 return (FATAL_EXIT_CODE);
1938 printf ("/* Generated automatically by the program `genrecog'\n\
1939 from the machine description file `md'. */\n\n");
1941 printf ("#include \"config.h\"\n");
1942 printf ("#include \"system.h\"\n");
1943 printf ("#include \"rtl.h\"\n");
1944 printf ("#include \"tm_p.h\"\n");
1945 printf ("#include \"function.h\"\n");
1946 printf ("#include \"insn-config.h\"\n");
1947 printf ("#include \"recog.h\"\n");
1948 printf ("#include \"real.h\"\n");
1949 printf ("#include \"output.h\"\n");
1950 printf ("#include \"flags.h\"\n");
1953 /* Read the machine description. */
1957 c = read_skip_spaces (infile);
1962 desc = read_rtx (infile);
1963 if (GET_CODE (desc) == DEFINE_INSN)
1964 recog_tree = merge_trees (recog_tree,
1965 make_insn_sequence (desc, RECOG));
1966 else if (GET_CODE (desc) == DEFINE_SPLIT)
1967 split_tree = merge_trees (split_tree,
1968 make_insn_sequence (desc, SPLIT));
1969 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
1970 peephole2_tree = merge_trees (peephole2_tree,
1971 make_insn_sequence (desc, PEEPHOLE2));
1973 if (GET_CODE (desc) == DEFINE_PEEPHOLE
1974 || GET_CODE (desc) == DEFINE_EXPAND)
1980 /* `recog' contains a decision tree\n\
1981 that recognizes whether the rtx X0 is a valid instruction.\n\
1983 recog returns -1 if the rtx is not valid.\n\
1984 If the rtx is valid, recog returns a nonnegative number\n\
1985 which is the insn code number for the pattern that matched.\n");
1986 printf (" This is the same as the order in the machine description of\n\
1987 the entry that matched. This number can be used as an index into various\n\
1988 insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands\n\
1989 (found in insn-output.c).\n\n");
1990 printf (" The third argument to recog is an optional pointer to an int.\n\
1991 If present, recog will accept a pattern if it matches except for\n\
1992 missing CLOBBER expressions at the end. In that case, the value\n\
1993 pointed to by the optional pointer will be set to the number of\n\
1994 CLOBBERs that need to be added (it should be initialized to zero by\n\
1995 the caller). If it is set nonzero, the caller should allocate a\n\
1996 PARALLEL of the appropriate size, copy the initial entries, and call\n\
1997 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.");
1999 if (split_tree.first)
2000 printf ("\n\n The function split_insns returns 0 if the rtl could not\n\
2001 be split or the split rtl in a SEQUENCE if it can be.");
2003 if (peephole2_tree.first)
2004 printf ("\n\n The function peephole2_insns returns 0 if the rtl could not\n\
2005 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2006 and LAST_INSN will point to the last recognized insn in the old sequence.");
2010 printf ("#define operands recog_data.operand\n\n");
2012 next_subroutine_number = 0;
2013 break_out_subroutines (recog_tree, RECOG, 1);
2014 write_subroutine (recog_tree.first, RECOG);
2016 next_subroutine_number = 0;
2017 break_out_subroutines (split_tree, SPLIT, 1);
2018 write_subroutine (split_tree.first, SPLIT);
2020 if (peephole2_tree.first)
2022 next_subroutine_number = 0;
2023 break_out_subroutines (peephole2_tree, PEEPHOLE2, 1);
2024 write_subroutine (peephole2_tree.first, PEEPHOLE2);
2028 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2031 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2033 get_insn_name (code)
2036 if (code < insn_name_ptr_size)
2037 return insn_name_ptr[code];