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 a
23 function called `recog' plus its subroutines. These functions
24 contain a decision tree that recognizes whether an rtx, the
25 argument given to recog, is a valid instruction.
27 recog returns -1 if the rtx is not valid. If the rtx is valid,
28 recog returns a nonnegative number which is the insn code number
29 for the pattern that matched. This is the same as the order in the
30 machine description of the entry that matched. This number can be
31 used as an index into various insn_* tables, such as insn_template,
32 insn_outfun, and insn_n_operands (found in insn-output.c).
34 The third argument to recog is an optional pointer to an int. If
35 present, recog will accept a pattern if it matches except for
36 missing CLOBBER expressions at the end. In that case, the value
37 pointed to by the optional pointer will be set to the number of
38 CLOBBERs that need to be added (it should be initialized to zero by
39 the caller). If it is set nonzero, the caller should allocate a
40 PARALLEL of the appropriate size, copy the initial entries, and
41 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
43 This program also generates the function `split_insns', which
44 returns 0 if the rtl could not be split, or it returns the split
47 This program also generates the function `peephole2_insns', which
48 returns 0 if the rtl could not be matched. If there was a match,
49 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
50 to the last recognized insn in the old sequence. */
58 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
59 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
61 static struct obstack obstack;
62 struct obstack *rtl_obstack = &obstack;
64 #define obstack_chunk_alloc xmalloc
65 #define obstack_chunk_free free
67 /* Holds an array of names indexed by insn_code_number. */
68 static char **insn_name_ptr = 0;
69 static int insn_name_ptr_size = 0;
71 /* A listhead of decision trees. The alternatives to a node are kept
72 in a doublely-linked list so we can easily add nodes to the proper
73 place when merging. */
77 struct decision *first;
78 struct decision *last;
81 /* A single test. The two accept types aren't tests per-se, but
82 their equality (or lack thereof) does affect tree merging so
83 it is convenient to keep them here. */
87 /* A linked list through the tests attached to a node. */
88 struct decision_test *next;
90 /* These types are roughly in the order in which we'd like to test them. */
92 DT_mode, DT_code, DT_veclen,
93 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide,
94 DT_dup, DT_pred, DT_c_test,
95 DT_accept_op, DT_accept_insn
100 enum machine_mode mode; /* Machine mode of node. */
101 RTX_CODE code; /* Code to test. */
105 const char *name; /* Predicate to call. */
106 int index; /* Index into `preds' or -1. */
107 enum machine_mode mode; /* Machine mode for node. */
110 const char *c_test; /* Additional test to perform. */
111 int veclen; /* Length of vector. */
112 int dup; /* Number of operand to compare against. */
113 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
114 int opno; /* Operand number matched. */
117 int code_number; /* Insn number matched. */
118 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
123 /* Data structure for decision tree for recognizing legitimate insns. */
127 struct decision_head success; /* Nodes to test on success. */
128 struct decision *next; /* Node to test on failure. */
129 struct decision *prev; /* Node whose failure tests us. */
130 struct decision *afterward; /* Node to test on success,
131 but failure of successor nodes. */
133 const char *position; /* String denoting position in pattern. */
135 struct decision_test *tests; /* The tests for this node. */
137 int number; /* Node number, used for labels */
138 int subroutine_number; /* Number of subroutine this node starts */
139 int need_label; /* Label needs to be output. */
142 #define SUBROUTINE_THRESHOLD 100
144 static int next_subroutine_number;
146 /* We can write three types of subroutines: One for insn recognition,
147 one to split insns, and one for peephole-type optimizations. This
148 defines which type is being written. */
151 RECOG, SPLIT, PEEPHOLE2
154 #define IS_SPLIT(X) ((X) != RECOG)
156 /* Next available node number for tree nodes. */
158 static int next_number;
160 /* Next number to use as an insn_code. */
162 static int next_insn_code;
164 /* Similar, but counts all expressions in the MD file; used for
167 static int next_index;
169 /* Record the highest depth we ever have so we know how many variables to
170 allocate in each subroutine we make. */
172 static int max_depth;
174 /* This table contains a list of the rtl codes that can possibly match a
175 predicate defined in recog.c. The function `maybe_both_true' uses it to
176 deduce that there are no expressions that can be matches by certain pairs
177 of tree nodes. Also, if a predicate can match only one code, we can
178 hardwire that code into the node testing the predicate. */
180 static struct pred_table
183 RTX_CODE codes[NUM_RTX_CODE];
185 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
186 LABEL_REF, SUBREG, REG, MEM}},
187 #ifdef PREDICATE_CODES
190 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
191 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
192 {"register_operand", {SUBREG, REG}},
193 {"scratch_operand", {SCRATCH, REG}},
194 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
196 {"const_int_operand", {CONST_INT}},
197 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
198 {"nonimmediate_operand", {SUBREG, REG, MEM}},
199 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
200 LABEL_REF, SUBREG, REG}},
201 {"push_operand", {MEM}},
202 {"pop_operand", {MEM}},
203 {"memory_operand", {SUBREG, MEM}},
204 {"indirect_operand", {SUBREG, MEM}},
205 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}},
206 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
207 LABEL_REF, SUBREG, REG, MEM}}
210 #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
212 static struct decision *new_decision
213 PROTO((const char *, struct decision_head *));
214 static struct decision_test *new_decision_test
215 PROTO((enum decision_type, struct decision_test ***));
216 static struct decision *add_to_sequence
217 PROTO((rtx, struct decision_head *, const char *, enum routine_type, int));
219 static int maybe_both_true_2
220 PROTO((struct decision_test *, struct decision_test *));
221 static int maybe_both_true_1
222 PROTO((struct decision_test *, struct decision_test *));
223 static int maybe_both_true
224 PROTO((struct decision *, struct decision *, int));
226 static int nodes_identical_1
227 PROTO((struct decision_test *, struct decision_test *));
228 static int nodes_identical
229 PROTO((struct decision *, struct decision *));
230 static void merge_accept_insn
231 PROTO((struct decision *, struct decision *));
232 static void merge_trees
233 PROTO((struct decision_head *, struct decision_head *));
235 static void factor_tests
236 PROTO((struct decision_head *));
237 static void simplify_tests
238 PROTO((struct decision_head *));
239 static int break_out_subroutines
240 PROTO((struct decision_head *, int));
241 static void find_afterward
242 PROTO((struct decision_head *, struct decision *));
244 static void change_state
245 PROTO((const char *, const char *, struct decision *, const char *));
246 static void print_code
247 PROTO((enum rtx_code));
248 static void write_afterward
249 PROTO((struct decision *, struct decision *, const char *));
250 static struct decision *write_switch
251 PROTO((struct decision *, int));
252 static void write_cond
253 PROTO((struct decision_test *, int, enum routine_type));
254 static void write_action
255 PROTO((struct decision_test *, int, int, struct decision *,
257 static int is_unconditional
258 PROTO((struct decision_test *, enum routine_type));
259 static int write_node
260 PROTO((struct decision *, int, enum routine_type));
261 static void write_tree_1
262 PROTO((struct decision_head *, int, enum routine_type));
263 static void write_tree
264 PROTO((struct decision_head *, const char *, enum routine_type, int));
265 static void write_subroutine
266 PROTO((struct decision_head *, enum routine_type));
267 static void write_subroutines
268 PROTO((struct decision_head *, enum routine_type));
269 static void write_header
272 static struct decision_head make_insn_sequence
273 PROTO((rtx, enum routine_type));
274 static void process_tree
275 PROTO((struct decision_head *, enum routine_type));
277 static void record_insn_name
278 PROTO((int, const char *));
280 static void debug_decision_1
281 PROTO((struct decision *, int));
282 static void debug_decision_2
283 PROTO((struct decision_test *));
284 extern void debug_decision
285 PROTO((struct decision *));
287 /* Create a new node in sequence after LAST. */
289 static struct decision *
290 new_decision (position, last)
291 const char *position;
292 struct decision_head *last;
294 register struct decision *new
295 = (struct decision *) xmalloc (sizeof (struct decision));
297 memset (new, 0, sizeof (*new));
298 new->success = *last;
299 new->position = xstrdup (position);
300 new->number = next_number++;
302 last->first = last->last = new;
306 /* Create a new test and link it in at PLACE. */
308 static struct decision_test *
309 new_decision_test (type, pplace)
310 enum decision_type type;
311 struct decision_test ***pplace;
313 struct decision_test **place = *pplace;
314 struct decision_test *test;
316 test = (struct decision_test *) xmalloc (sizeof (*test));
327 /* Create a chain of nodes to verify that an rtl expression matches
330 LAST is a pointer to the listhead in the previous node in the chain (or
331 in the calling function, for the first node).
333 POSITION is the string representing the current position in the insn.
335 INSN_TYPE is the type of insn for which we are emitting code.
337 A pointer to the final node in the chain is returned. */
339 static struct decision *
340 add_to_sequence (pattern, last, position, insn_type, top)
342 struct decision_head *last;
343 const char *position;
344 enum routine_type insn_type;
348 struct decision *this, *sub;
349 struct decision_test *test;
350 struct decision_test **place;
353 register const char *fmt;
354 int depth = strlen (position);
356 enum machine_mode mode;
358 if (depth > max_depth)
361 subpos = (char *) alloca (depth + 2);
362 strcpy (subpos, position);
363 subpos[depth + 1] = 0;
365 sub = this = new_decision (position, last);
366 place = &this->tests;
369 mode = GET_MODE (pattern);
370 code = GET_CODE (pattern);
375 /* Toplevel peephole pattern. */
376 if (insn_type == PEEPHOLE2 && top)
378 /* We don't need the node we just created -- unlink it. */
379 last->first = last->last = NULL;
381 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
383 /* Which insn we're looking at is represented by A-Z. We don't
384 ever use 'A', however; it is always implied. */
386 subpos[depth] = (i > 0 ? 'A' + i : 0);
387 sub = add_to_sequence (XVECEXP (pattern, 0, i),
388 last, subpos, insn_type, 0);
389 last = &sub->success;
394 /* Else nothing special. */
403 const char *pred_name;
404 RTX_CODE was_code = code;
406 if (code == MATCH_SCRATCH)
408 pred_name = "scratch_operand";
413 pred_name = XSTR (pattern, 1);
414 if (code == MATCH_PARALLEL)
420 /* We know exactly what const_int_operand matches -- any CONST_INT. */
421 if (strcmp ("const_int_operand", pred_name) == 0)
426 else if (pred_name[0] != 0)
428 test = new_decision_test (DT_pred, &place);
429 test->u.pred.name = pred_name;
430 test->u.pred.mode = mode;
432 /* See if we know about this predicate and save its number. If
433 we do, and it only accepts one code, note that fact. The
434 predicate `const_int_operand' only tests for a CONST_INT, so
435 if we do so we can avoid calling it at all.
437 Finally, if we know that the predicate does not allow
438 CONST_INT, we know that the only way the predicate can match
439 is if the modes match (here we use the kludge of relying on
440 the fact that "address_operand" accepts CONST_INT; otherwise,
441 it would have to be a special case), so we can test the mode
442 (but we need not). This fact should considerably simplify the
445 for (i = 0; i < NUM_KNOWN_PREDS; i++)
446 if (! strcmp (preds[i].name, pred_name))
449 if (i < NUM_KNOWN_PREDS)
451 int allows_const_int, j;
453 test->u.pred.index = i;
455 if (preds[i].codes[1] == 0 && code == UNKNOWN)
456 code = preds[i].codes[0];
458 allows_const_int = 0;
459 for (j = 0; preds[i].codes[j] != 0; j++)
460 if (preds[i].codes[j] == CONST_INT)
462 allows_const_int = 1;
466 /* Can't enforce a mode if we allow const_int. */
467 if (allows_const_int)
472 test->u.pred.index = -1;
473 #ifdef PREDICATE_CODES
474 /* If the port has a list of the predicates it uses but
476 fprintf (stderr, "Warning: `%s' not in PREDICATE_CODES\n",
482 /* Accept the operand, ie. record it in `operands'. */
483 test = new_decision_test (DT_accept_op, &place);
484 test->u.opno = XINT (pattern, 0);
486 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
488 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
489 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
491 subpos[depth] = i + base;
492 sub = add_to_sequence (XVECEXP (pattern, 2, i),
493 &sub->success, subpos, insn_type, 0);
502 test = new_decision_test (DT_dup, &place);
503 test->u.dup = XINT (pattern, 0);
505 test = new_decision_test (DT_accept_op, &place);
506 test->u.opno = XINT (pattern, 0);
508 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
510 subpos[depth] = i + '0';
511 sub = add_to_sequence (XVECEXP (pattern, 1, i),
512 &sub->success, subpos, insn_type, 0);
520 test = new_decision_test (DT_dup, &place);
521 test->u.dup = XINT (pattern, 0);
525 pattern = XEXP (pattern, 0);
529 /* The operands of a SET must have the same mode unless one
531 if (GET_MODE (SET_SRC (pattern)) != VOIDmode
532 && GET_MODE (SET_DEST (pattern)) != VOIDmode
533 && GET_MODE (SET_SRC (pattern)) != GET_MODE (SET_DEST (pattern))
534 /* The mode of an ADDRESS_OPERAND is the mode of the memory
535 reference, not the mode of the address. */
536 && ! (GET_CODE (SET_SRC (pattern)) == MATCH_OPERAND
537 && ! strcmp (XSTR (SET_SRC (pattern), 1), "address_operand")))
539 print_rtl (stderr, pattern);
540 fputc ('\n', stderr);
541 fatal ("mode mismatch in SET");
544 /* Everything else is standard. */
551 fmt = GET_RTX_FORMAT (code);
552 len = GET_RTX_LENGTH (code);
554 /* Do tests against the current node first. */
555 for (i = 0; i < (size_t) len; i++)
561 test = new_decision_test (DT_elt_zero_int, &place);
562 test->u.intval = XINT (pattern, i);
566 test = new_decision_test (DT_elt_one_int, &place);
567 test->u.intval = XINT (pattern, i);
572 else if (fmt[i] == 'w')
577 test = new_decision_test (DT_elt_zero_wide, &place);
578 test->u.intval = XWINT (pattern, i);
580 else if (fmt[i] == 'E')
585 test = new_decision_test (DT_veclen, &place);
586 test->u.veclen = XVECLEN (pattern, i);
590 /* Now test our sub-patterns. */
591 for (i = 0; i < (size_t) len; i++)
596 subpos[depth] = '0' + i;
597 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
598 subpos, insn_type, 0);
604 for (j = 0; j < XVECLEN (pattern, i); j++)
606 subpos[depth] = 'a' + j;
607 sub = add_to_sequence (XVECEXP (pattern, i, j),
608 &sub->success, subpos, insn_type, 0);
625 /* Insert nodes testing mode and code, if they're still relevant,
626 before any of the nodes we may have added above. */
629 place = &this->tests;
630 test = new_decision_test (DT_code, &place);
634 if (mode != VOIDmode)
636 place = &this->tests;
637 test = new_decision_test (DT_mode, &place);
641 /* If we didn't insert any tests or accept nodes, hork. */
642 if (this->tests == NULL)
648 /* A subroutine of maybe_both_true; examines only one test.
649 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
652 maybe_both_true_2 (d1, d2)
653 struct decision_test *d1, *d2;
655 if (d1->type == d2->type)
660 return d1->u.mode == d2->u.mode;
663 return d1->u.code == d2->u.code;
666 return d1->u.veclen == d2->u.veclen;
668 case DT_elt_zero_int:
670 case DT_elt_zero_wide:
671 return d1->u.intval == d2->u.intval;
678 /* If either has a predicate that we know something about, set
679 things up so that D1 is the one that always has a known
680 predicate. Then see if they have any codes in common. */
682 if (d1->type == DT_pred || d2->type == DT_pred)
684 if (d2->type == DT_pred)
686 struct decision_test *tmp;
687 tmp = d1, d1 = d2, d2 = tmp;
690 /* If D2 tests a mode, see if it matches D1. */
691 if (d1->u.pred.mode != VOIDmode)
693 if (d2->type == DT_mode)
695 if (d1->u.pred.mode != d2->u.mode)
698 else if (d2->type == DT_pred)
700 if (d2->u.pred.mode != VOIDmode
701 && d1->u.pred.mode != d2->u.pred.mode)
706 if (d1->u.pred.index >= 0)
708 /* If D2 tests a code, see if it is in the list of valid
709 codes for D1's predicate. */
710 if (d2->type == DT_code)
712 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
715 if (*c == d2->u.code)
723 /* Otherwise see if the predicates have any codes in common. */
724 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
726 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
729 while (*c1 != 0 && !common)
731 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
732 while (*c2 != 0 && !common)
734 common = (*c1 == *c2);
749 /* A subroutine of maybe_both_true; examines all the tests for a given node.
750 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
753 maybe_both_true_1 (d1, d2)
754 struct decision_test *d1, *d2;
756 struct decision_test *t1, *t2;
758 /* A match_operand with no predicate can match anything. Recognize
759 this by the existance of a lone DT_accept_op test. */
760 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
763 /* Eliminate pairs of tests while they can exactly match. */
764 while (d1 && d2 && d1->type == d2->type)
766 if (maybe_both_true_2 (d1, d2) == 0)
768 d1 = d1->next, d2 = d2->next;
771 /* After that, consider all pairs. */
772 for (t1 = d1; t1 ; t1 = t1->next)
773 for (t2 = d2; t2 ; t2 = t2->next)
774 if (maybe_both_true_2 (t1, t2) == 0)
780 /* Return 0 if we can prove that there is no RTL that can match both
781 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
782 can match both or just that we couldn't prove there wasn't such an RTL).
784 TOPLEVEL is non-zero if we are to only look at the top level and not
785 recursively descend. */
788 maybe_both_true (d1, d2, toplevel)
789 struct decision *d1, *d2;
792 struct decision *p1, *p2;
795 /* Don't compare strings on the different positions in insn. Doing so
796 is incorrect and results in false matches from constructs like
798 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
799 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
801 [(set (match_operand:HI "register_operand" "r")
802 (match_operand:HI "register_operand" "r"))]
804 If we are presented with such, we are recursing through the remainder
805 of a node's success nodes (from the loop at the end of this function).
806 Skip forward until we come to a position that matches.
808 Due to the way position strings are constructed, we know that iterating
809 forward from the lexically lower position (e.g. "00") will run into
810 the lexically higher position (e.g. "1") and not the other way around.
811 This saves a bit of effort. */
813 cmp = strcmp (d1->position, d2->position);
819 /* If the d2->position was lexically lower, swap. */
821 p1 = d1, d1 = d2, d2 = p1;
823 if (d1->success.first == 0)
825 for (p1 = d1->success.first; p1; p1 = p1->next)
826 if (maybe_both_true (p1, d2, 0))
832 /* Test the current level. */
833 cmp = maybe_both_true_1 (d1->tests, d2->tests);
837 /* We can't prove that D1 and D2 cannot both be true. If we are only
838 to check the top level, return 1. Otherwise, see if we can prove
839 that all choices in both successors are mutually exclusive. If
840 either does not have any successors, we can't prove they can't both
843 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
846 for (p1 = d1->success.first; p1; p1 = p1->next)
847 for (p2 = d2->success.first; p2; p2 = p2->next)
848 if (maybe_both_true (p1, p2, 0))
854 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
857 nodes_identical_1 (d1, d2)
858 struct decision_test *d1, *d2;
863 return d1->u.mode == d2->u.mode;
866 return d1->u.code == d2->u.code;
869 return (d1->u.pred.mode == d2->u.pred.mode
870 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
873 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
876 return d1->u.veclen == d2->u.veclen;
879 return d1->u.dup == d2->u.dup;
881 case DT_elt_zero_int:
883 case DT_elt_zero_wide:
884 return d1->u.intval == d2->u.intval;
887 return d1->u.opno == d2->u.opno;
890 /* Differences will be handled in merge_accept_insn. */
898 /* True iff the two nodes are identical (on one level only). Due
899 to the way these lists are constructed, we shouldn't have to
900 consider different orderings on the tests. */
903 nodes_identical (d1, d2)
904 struct decision *d1, *d2;
906 struct decision_test *t1, *t2;
908 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
910 if (t1->type != t2->type)
912 if (! nodes_identical_1 (t1, t2))
916 /* For success, they should now both be null. */
920 /* A subroutine of merge_trees; given two nodes that have been declared
921 identical, cope with two insn accept states. If they differ in the
922 number of clobbers, then the conflict was created by make_insn_sequence
923 and we can drop the with-clobbers version on the floor. If both
924 nodes have no additional clobbers, we have found an ambiguity in the
925 source machine description. */
928 merge_accept_insn (oldd, addd)
929 struct decision *oldd, *addd;
931 struct decision_test *old, *add;
933 for (old = oldd->tests; old; old = old->next)
934 if (old->type == DT_accept_insn)
939 for (add = addd->tests; add; add = add->next)
940 if (add->type == DT_accept_insn)
945 /* If one node is for a normal insn and the second is for the base
946 insn with clobbers stripped off, the second node should be ignored. */
948 if (old->u.insn.num_clobbers_to_add == 0
949 && add->u.insn.num_clobbers_to_add > 0)
951 /* Nothing to do here. */
953 else if (old->u.insn.num_clobbers_to_add > 0
954 && add->u.insn.num_clobbers_to_add == 0)
956 /* In this case, replace OLD with ADD. */
957 old->u.insn = add->u.insn;
961 fatal ("Two actions at one point in tree for insns \"%s\" (%d) and \"%s\" (%d)",
962 get_insn_name (old->u.insn.code_number),
963 old->u.insn.code_number,
964 get_insn_name (add->u.insn.code_number),
965 add->u.insn.code_number);
969 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
972 merge_trees (oldh, addh)
973 struct decision_head *oldh, *addh;
975 struct decision *next, *add;
977 if (addh->first == 0)
979 if (oldh->first == 0)
985 /* Trying to merge bits at different positions isn't possible. */
986 if (strcmp (oldh->first->position, addh->first->position))
989 for (add = addh->first; add ; add = next)
991 struct decision *old, *insert_before = NULL;
995 /* The semantics of pattern matching state that the tests are
996 done in the order given in the MD file so that if an insn
997 matches two patterns, the first one will be used. However,
998 in practice, most, if not all, patterns are unambiguous so
999 that their order is independent. In that case, we can merge
1000 identical tests and group all similar modes and codes together.
1002 Scan starting from the end of OLDH until we reach a point
1003 where we reach the head of the list or where we pass a
1004 pattern that could also be true if NEW is true. If we find
1005 an identical pattern, we can merge them. Also, record the
1006 last node that tests the same code and mode and the last one
1007 that tests just the same mode.
1009 If we have no match, place NEW after the closest match we found. */
1011 for (old = oldh->last; old; old = old->prev)
1013 if (nodes_identical (old, add))
1015 merge_accept_insn (old, add);
1016 merge_trees (&old->success, &add->success);
1020 if (maybe_both_true (old, add, 0))
1023 /* Insert the nodes in DT test type order, which is roughly
1024 how expensive/important the test is. Given that the tests
1025 are also ordered within the list, examining the first is
1027 if (add->tests->type < old->tests->type)
1028 insert_before = old;
1031 if (insert_before == NULL)
1034 add->prev = oldh->last;
1035 oldh->last->next = add;
1040 if ((add->prev = insert_before->prev) != NULL)
1041 add->prev->next = add;
1044 add->next = insert_before;
1045 insert_before->prev = add;
1052 /* Walk the tree looking for sub-nodes that perform common tests.
1053 Factor out the common test into a new node. This enables us
1054 (depending on the test type) to emit switch statements later. */
1058 struct decision_head *head;
1060 struct decision *first, *next;
1062 for (first = head->first; first && first->next; first = next)
1064 enum decision_type type;
1065 struct decision *new, *old_last;
1067 type = first->tests->type;
1070 /* Want at least two compatible sequential nodes. */
1071 if (next->tests->type != type)
1074 /* Don't want all node types, just those we can turn into
1075 switch statements. */
1078 && type != DT_veclen
1079 && type != DT_elt_zero_int
1080 && type != DT_elt_one_int
1081 && type != DT_elt_zero_wide)
1084 /* If we'd been performing more than one test, create a new node
1085 below our first test. */
1086 if (first->tests->next != NULL)
1088 new = new_decision (first->position, &first->success);
1089 new->tests = first->tests->next;
1090 first->tests->next = NULL;
1093 /* Crop the node tree off after our first test. */
1095 old_last = head->last;
1098 /* For each compatible test, adjust to perform only one test in
1099 the top level node, then merge the node back into the tree. */
1102 struct decision_head h;
1104 if (next->tests->next != NULL)
1106 new = new_decision (next->position, &next->success);
1107 new->tests = next->tests->next;
1108 next->tests->next = NULL;
1113 h.first = h.last = new;
1115 merge_trees (head, &h);
1117 while (next && next->tests->type == type);
1119 /* After we run out of compatible tests, graft the remaining nodes
1120 back onto the tree. */
1123 next->prev = head->last;
1124 head->last->next = next;
1125 head->last = old_last;
1130 for (first = head->first; first; first = first->next)
1131 factor_tests (&first->success);
1134 /* After factoring, try to simplify the tests on any one node.
1135 Tests that are useful for switch statements are recognizable
1136 by having only a single test on a node -- we'll be manipulating
1137 nodes with multiple tests:
1139 If we have mode tests or code tests that are redundant with
1140 predicates, remove them. */
1143 simplify_tests (head)
1144 struct decision_head *head;
1146 struct decision *tree;
1148 for (tree = head->first; tree; tree = tree->next)
1150 struct decision_test *a, *b;
1157 /* Find a predicate node. */
1158 while (b && b->type != DT_pred)
1162 /* Due to how these tests are constructed, we don't even need
1163 to check that the mode and code are compatible -- they were
1164 generated from the predicate in the first place. */
1165 while (a->type == DT_mode || a->type == DT_code)
1172 for (tree = head->first; tree; tree = tree->next)
1173 simplify_tests (&tree->success);
1176 /* Count the number of subnodes of HEAD. If the number is high enough,
1177 make the first node in HEAD start a separate subroutine in the C code
1178 that is generated. */
1181 break_out_subroutines (head, initial)
1182 struct decision_head *head;
1186 struct decision *sub;
1188 for (sub = head->first; sub; sub = sub->next)
1189 size += 1 + break_out_subroutines (&sub->success, 0);
1191 if (size > SUBROUTINE_THRESHOLD && ! initial)
1193 head->first->subroutine_number = ++next_subroutine_number;
1199 /* For each node p, find the next alternative that might be true
1203 find_afterward (head, real_afterward)
1204 struct decision_head *head;
1205 struct decision *real_afterward;
1207 struct decision *p, *q, *afterward;
1209 /* We can't propogate alternatives across subroutine boundaries.
1210 This is not incorrect, merely a minor optimization loss. */
1213 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1215 for ( ; p ; p = p->next)
1217 /* Find the next node that might be true if this one fails. */
1218 for (q = p->next; q ; q = q->next)
1219 if (maybe_both_true (p, q, 1))
1222 /* If we reached the end of the list without finding one,
1223 use the incoming afterward position. */
1232 for (p = head->first; p ; p = p->next)
1233 if (p->success.first)
1234 find_afterward (&p->success, p->afterward);
1236 /* When we are generating a subroutine, record the real afterward
1237 position in the first node where write_tree can find it, and we
1238 can do the right thing at the subroutine call site. */
1240 if (p->subroutine_number > 0)
1241 p->afterward = real_afterward;
1244 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1245 actions are necessary to move to NEWPOS. If we fail to move to the
1246 new state, branch to node AFTERWARD if non-zero, otherwise return.
1248 Failure to move to the new state can only occur if we are trying to
1249 match multiple insns and we try to step past the end of the stream. */
1252 change_state (oldpos, newpos, afterward, indent)
1255 struct decision *afterward;
1258 int odepth = strlen (oldpos);
1259 int ndepth = strlen (newpos);
1261 int old_has_insn, new_has_insn;
1263 /* Pop up as many levels as necessary. */
1264 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1267 /* Hunt for the last [A-Z] in both strings. */
1268 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1269 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1271 for (new_has_insn = odepth - 1; new_has_insn >= 0; --new_has_insn)
1272 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1275 /* Make sure to reset the _last_insn pointer when popping back up. */
1276 if (old_has_insn >= 0 && new_has_insn < 0)
1277 printf ("%s_last_insn = insn;\n", indent);
1279 /* Go down to desired level. */
1280 while (depth < ndepth)
1282 /* It's a different insn from the first one. */
1283 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1285 /* We can only fail if we're moving down the tree. */
1286 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1288 printf ("%s_last_insn = recog_next_insn (insn, %d);\n",
1289 indent, newpos[depth] - 'A');
1293 printf ("%stem = recog_next_insn (insn, %d);\n",
1294 indent, newpos[depth] - 'A');
1295 printf ("%sif (tem == NULL_RTX)\n", indent);
1297 printf ("%s goto L%d;\n", indent, afterward->number);
1299 printf ("%s goto ret0;\n", indent);
1300 printf ("%s_last_insn = tem;\n", indent);
1302 printf ("%sx%d = PATTERN (_last_insn);\n", indent, depth + 1);
1304 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1305 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1306 indent, depth + 1, depth, newpos[depth] - 'a');
1308 printf ("%sx%d = XEXP (x%d, %c);\n",
1309 indent, depth + 1, depth, newpos[depth]);
1314 /* Print the enumerator constant for CODE -- the upcase version of
1321 register const char *p;
1322 for (p = GET_RTX_NAME (code); *p; p++)
1323 putchar (TOUPPER (*p));
1326 /* Emit code to cross an afterward link -- change state and branch. */
1329 write_afterward (start, afterward, indent)
1330 struct decision *start;
1331 struct decision *afterward;
1334 if (!afterward || start->subroutine_number > 0)
1335 printf("%sgoto ret0;\n", indent);
1338 change_state (start->position, afterward->position, NULL, indent);
1339 printf ("%sgoto L%d;\n", indent, afterward->number);
1343 /* Emit a switch statement, if possible, for an initial sequence of
1344 nodes at START. Return the first node yet untested. */
1346 static struct decision *
1347 write_switch (start, depth)
1348 struct decision *start;
1351 struct decision *p = start;
1352 enum decision_type type = p->tests->type;
1354 /* If we have two or more nodes in sequence that test the same one
1355 thing, we may be able to use a switch statement. */
1359 || p->next->tests->type != type
1360 || p->next->tests->next)
1363 /* DT_code is special in that we can do interesting things with
1364 known predicates at the same time. */
1365 if (type == DT_code)
1367 char codemap[NUM_RTX_CODE];
1368 struct decision *ret;
1370 memset (codemap, 0, sizeof(codemap));
1372 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1375 RTX_CODE code = p->tests->u.code;
1378 printf (":\n goto L%d;\n", p->success.first->number);
1379 p->success.first->need_label = 1;
1384 while (p && p->tests->type == DT_code && !p->tests->next);
1386 /* If P is testing a predicate that we know about and we haven't
1387 seen any of the codes that are valid for the predicate, we can
1388 write a series of "case" statement, one for each possible code.
1389 Since we are already in a switch, these redundant tests are very
1390 cheap and will reduce the number of predicates called. */
1392 /* Note that while we write out cases for these predicates here,
1393 we don't actually write the test here, as it gets kinda messy.
1394 It is trivial to leave this to later by telling our caller that
1395 we only processed the CODE tests. */
1398 while (p && p->tests->type == DT_pred
1399 && p->tests->u.pred.index >= 0)
1403 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1404 if (codemap[(int) *c] != 0)
1407 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1412 codemap[(int) *c] = 1;
1415 printf (" goto L%d;\n", p->number);
1421 /* Make the default case skip the predicates we managed to match. */
1423 printf (" default:\n");
1428 printf (" goto L%d;\n", p->number);
1432 write_afterward (start, start->afterward, " ");
1435 printf (" break;\n");
1440 else if (type == DT_mode
1441 || type == DT_veclen
1442 || type == DT_elt_zero_int
1443 || type == DT_elt_one_int
1444 || type == DT_elt_zero_wide)
1448 printf (" switch (");
1452 str = "GET_MODE (x%d)";
1455 str = "XVECLEN (x%d, 0)";
1457 case DT_elt_zero_int:
1458 str = "XINT (x%d, 0)";
1460 case DT_elt_one_int:
1461 str = "XINT (x%d, 1)";
1463 case DT_elt_zero_wide:
1464 str = "XWINT (x%d, 0)";
1469 printf (str, depth);
1478 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1481 printf ("%d", p->tests->u.veclen);
1483 case DT_elt_zero_int:
1484 case DT_elt_one_int:
1485 case DT_elt_zero_wide:
1486 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1491 printf (":\n goto L%d;\n", p->success.first->number);
1492 p->success.first->need_label = 1;
1496 while (p && p->tests->type == type && !p->tests->next);
1498 printf (" default:\n break;\n }\n");
1504 /* None of the other tests are ameanable. */
1509 /* Emit code for one test. */
1512 write_cond (p, depth, subroutine_type)
1513 struct decision_test *p;
1515 enum routine_type subroutine_type;
1520 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1524 printf ("GET_CODE (x%d) == ", depth);
1525 print_code (p->u.code);
1529 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1532 case DT_elt_zero_int:
1533 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1536 case DT_elt_one_int:
1537 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1540 case DT_elt_zero_wide:
1541 printf ("XWINT (x%d, 0) == ", depth);
1542 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1546 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1550 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1551 GET_MODE_NAME (p->u.pred.mode));
1555 printf ("(%s)", p->u.c_test);
1558 case DT_accept_insn:
1559 switch (subroutine_type)
1562 if (p->u.insn.num_clobbers_to_add == 0)
1564 printf ("pnum_clobbers != NULL");
1577 /* Emit code for one action. The previous tests have succeeded;
1578 TEST is the last of the chain. In the normal case we simply
1579 perform a state change. For the `accept' tests we must do more work. */
1582 write_action (test, depth, uncond, success, subroutine_type)
1583 struct decision_test *test;
1585 struct decision *success;
1586 enum routine_type subroutine_type;
1593 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1595 fputs (" {\n", stdout);
1602 if (test->type == DT_accept_op)
1604 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1606 /* Only allow DT_accept_insn to follow. */
1610 if (test->type != DT_accept_insn)
1615 /* Sanity check that we're now at the end of the list of tests. */
1619 if (test->type == DT_accept_insn)
1621 switch (subroutine_type)
1624 if (test->u.insn.num_clobbers_to_add != 0)
1625 printf ("%s*pnum_clobbers = %d;\n",
1626 indent, test->u.insn.num_clobbers_to_add);
1627 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
1631 printf ("%sreturn gen_split_%d (operands);\n",
1632 indent, test->u.insn.code_number);
1636 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1637 indent, test->u.insn.code_number);
1638 printf ("%sif (tem != 0)\n%s goto ret1;\n", indent, indent);
1647 printf("%sgoto L%d;\n", indent, success->number);
1648 success->need_label = 1;
1652 fputs (" }\n", stdout);
1655 /* Return 1 if the test is always true and has no fallthru path. Return -1
1656 if the test does have a fallthru path, but requires that the condition be
1657 terminated. Otherwise return 0 for a normal test. */
1658 /* ??? is_unconditional is a stupid name for a tri-state function. */
1661 is_unconditional (t, subroutine_type)
1662 struct decision_test *t;
1663 enum routine_type subroutine_type;
1665 if (t->type == DT_accept_op)
1668 if (t->type == DT_accept_insn)
1670 switch (subroutine_type)
1673 return (t->u.insn.num_clobbers_to_add == 0);
1686 /* Emit code for one node -- the conditional and the accompanying action.
1687 Return true if there is no fallthru path. */
1690 write_node (p, depth, subroutine_type)
1693 enum routine_type subroutine_type;
1695 struct decision_test *test, *last_test;
1698 last_test = test = p->tests;
1699 uncond = is_unconditional (test, subroutine_type);
1703 write_cond (test, depth, subroutine_type);
1705 while ((test = test->next) != NULL)
1710 uncond2 = is_unconditional (test, subroutine_type);
1715 write_cond (test, depth, subroutine_type);
1721 write_action (last_test, depth, uncond, p->success.first, subroutine_type);
1726 /* Emit code for all of the sibling nodes of HEAD. */
1729 write_tree_1 (head, depth, subroutine_type)
1730 struct decision_head *head;
1732 enum routine_type subroutine_type;
1734 struct decision *p, *next;
1737 for (p = head->first; p ; p = next)
1739 /* The label for the first element was printed in write_tree. */
1740 if (p != head->first && p->need_label)
1741 OUTPUT_LABEL (" ", p->number);
1743 /* Attempt to write a switch statement for a whole sequence. */
1744 next = write_switch (p, depth);
1749 /* Failed -- fall back and write one node. */
1750 uncond = write_node (p, depth, subroutine_type);
1755 /* Finished with this chain. Close a fallthru path by branching
1756 to the afterward node. */
1758 write_afterward (head->last, head->last->afterward, " ");
1761 /* Write out the decision tree starting at HEAD. PREVPOS is the
1762 position at the node that branched to this node. */
1765 write_tree (head, prevpos, type, initial)
1766 struct decision_head *head;
1767 const char *prevpos;
1768 enum routine_type type;
1771 register struct decision *p = head->first;
1775 OUTPUT_LABEL (" ", p->number);
1777 if (! initial && p->subroutine_number > 0)
1779 static const char * const name_prefix[] = {
1780 "recog", "split", "peephole2"
1783 static const char * const call_suffix[] = {
1784 ", pnum_clobbers", "", ", _plast_insn"
1787 /* This node has been broken out into a separate subroutine.
1788 Call it, test the result, and branch accordingly. */
1792 printf (" tem = %s_%d (x0, insn%s);\n",
1793 name_prefix[type], p->subroutine_number, call_suffix[type]);
1794 if (IS_SPLIT (type))
1795 printf (" if (tem != 0)\n return tem;\n");
1797 printf (" if (tem >= 0)\n return tem;\n");
1799 change_state (p->position, p->afterward->position, NULL, " ");
1800 printf (" goto L%d;\n", p->afterward->number);
1804 printf (" return %s_%d (x0, insn%s);\n",
1805 name_prefix[type], p->subroutine_number, call_suffix[type]);
1810 int depth = strlen (p->position);
1812 change_state (prevpos, p->position, head->last->afterward, " ");
1813 write_tree_1 (head, depth, type);
1815 for (p = head->first; p; p = p->next)
1816 if (p->success.first)
1817 write_tree (&p->success, p->position, type, 0);
1821 /* Write out a subroutine of type TYPE to do comparisons starting at
1825 write_subroutine (head, type)
1826 struct decision_head *head;
1827 enum routine_type type;
1829 static const char * const proto_pattern[] = {
1830 "%sint recog%s PROTO ((rtx, rtx, int *));\n",
1831 "%srtx split%s PROTO ((rtx, rtx));\n",
1832 "%srtx peephole2%s PROTO ((rtx, rtx, rtx *));\n"
1835 static const char * const decl_pattern[] = {
1837 recog%s (x0, insn, pnum_clobbers)\n\
1839 rtx insn ATTRIBUTE_UNUSED;\n\
1840 int *pnum_clobbers ATTRIBUTE_UNUSED;\n",
1843 split%s (x0, insn)\n\
1845 rtx insn ATTRIBUTE_UNUSED;\n",
1848 peephole2%s (x0, insn, _plast_insn)\n\
1850 rtx insn ATTRIBUTE_UNUSED;\n\
1851 rtx *_plast_insn ATTRIBUTE_UNUSED;\n"
1854 int subfunction = head->first->subroutine_number;
1859 s_or_e = subfunction ? "static " : "";
1862 sprintf (extension, "_%d", subfunction);
1863 else if (type == RECOG)
1864 extension[0] = '\0';
1866 strcpy (extension, "_insns");
1868 printf (proto_pattern[type], s_or_e, extension);
1869 printf (decl_pattern[type], s_or_e, extension);
1871 printf ("{\n register rtx * const operands = &recog_data.operand[0];\n");
1872 for (i = 1; i <= max_depth; i++)
1873 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
1875 if (type == PEEPHOLE2)
1876 printf (" register rtx _last_insn = insn;\n");
1877 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
1879 write_tree (head, "", type, 1);
1881 if (type == PEEPHOLE2)
1882 printf (" ret1:\n *_plast_insn = _last_insn;\n return tem;\n");
1883 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
1886 /* In break_out_subroutines, we discovered the boundaries for the
1887 subroutines, but did not write them out. Do so now. */
1890 write_subroutines (head, type)
1891 struct decision_head *head;
1892 enum routine_type type;
1896 for (p = head->first; p ; p = p->next)
1897 if (p->success.first)
1898 write_subroutines (&p->success, type);
1900 if (head->first->subroutine_number > 0)
1901 write_subroutine (head, type);
1904 /* Begin the output file. */
1910 /* Generated automatically by the program `genrecog' from the target\n\
1911 machine description file. */\n\
1913 #include \"config.h\"\n\
1914 #include \"system.h\"\n\
1915 #include \"rtl.h\"\n\
1916 #include \"tm_p.h\"\n\
1917 #include \"function.h\"\n\
1918 #include \"insn-config.h\"\n\
1919 #include \"recog.h\"\n\
1920 #include \"real.h\"\n\
1921 #include \"output.h\"\n\
1922 #include \"flags.h\"\n\
1926 /* `recog' contains a decision tree that recognizes whether the rtx\n\
1927 X0 is a valid instruction.\n\
1929 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
1930 returns a nonnegative number which is the insn code number for the\n\
1931 pattern that matched. This is the same as the order in the machine\n\
1932 description of the entry that matched. This number can be used as an\n\
1933 index into `insn_data' and other tables.\n\
1935 The third argument to recog is an optional pointer to an int. If\n\
1936 present, recog will accept a pattern if it matches except for missing\n\
1937 CLOBBER expressions at the end. In that case, the value pointed to by\n\
1938 the optional pointer will be set to the number of CLOBBERs that need\n\
1939 to be added (it should be initialized to zero by the caller). If it\n\
1940 is set nonzero, the caller should allocate a PARALLEL of the\n\
1941 appropriate size, copy the initial entries, and call add_clobbers\n\
1942 (found in insn-emit.c) to fill in the CLOBBERs.\n\
1946 The function split_insns returns 0 if the rtl could not\n\
1947 be split or the split rtl in a SEQUENCE if it can be.\n\
1949 The function peephole2_insns returns 0 if the rtl could not\n\
1950 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
1951 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
1956 /* Construct and return a sequence of decisions
1957 that will recognize INSN.
1959 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
1961 static struct decision_head
1962 make_insn_sequence (insn, type)
1964 enum routine_type type;
1967 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
1968 struct decision *last;
1969 struct decision_test *test, **place;
1970 struct decision_head head;
1972 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
1974 if (type == PEEPHOLE2)
1978 /* peephole2 gets special treatment:
1979 - X always gets an outer parallel even if it's only one entry
1980 - we remove all traces of outer-level match_scratch and match_dup
1981 expressions here. */
1982 x = rtx_alloc (PARALLEL);
1983 PUT_MODE (x, VOIDmode);
1984 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
1985 for (i = j = 0; i < XVECLEN (insn, 0); i++)
1987 rtx tmp = XVECEXP (insn, 0, i);
1988 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
1990 XVECEXP (x, 0, j) = tmp;
1996 else if (XVECLEN (insn, type == RECOG) == 1)
1997 x = XVECEXP (insn, type == RECOG, 0);
2000 x = rtx_alloc (PARALLEL);
2001 XVEC (x, 0) = XVEC (insn, type == RECOG);
2002 PUT_MODE (x, VOIDmode);
2005 memset(&head, 0, sizeof(head));
2006 last = add_to_sequence (x, &head, "", type, 1);
2008 /* Find the end of the test chain on the last node. */
2009 for (test = last->tests; test->next; test = test->next)
2011 place = &test->next;
2015 /* Need a new node if we have another test to add. */
2016 if (test->type == DT_accept_op)
2018 last = new_decision ("", &last->success);
2019 place = &last->tests;
2021 test = new_decision_test (DT_c_test, &place);
2022 test->u.c_test = c_test;
2025 test = new_decision_test (DT_accept_insn, &place);
2026 test->u.insn.code_number = next_insn_code;
2027 test->u.insn.num_clobbers_to_add = 0;
2032 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2033 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2034 If so, set up to recognize the pattern without these CLOBBERs. */
2036 if (GET_CODE (x) == PARALLEL)
2040 /* Find the last non-clobber in the parallel. */
2041 for (i = XVECLEN (x, 0); i > 0; i--)
2043 rtx y = XVECEXP (x, 0, i - 1);
2044 if (GET_CODE (y) != CLOBBER
2045 || (GET_CODE (XEXP (y, 0)) != REG
2046 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2050 if (i != XVECLEN (x, 0))
2053 struct decision_head clobber_head;
2055 /* Build a similar insn without the clobbers. */
2057 new = XVECEXP (x, 0, 0);
2062 new = rtx_alloc (PARALLEL);
2063 XVEC (new, 0) = rtvec_alloc (i);
2064 for (j = i - 1; j >= 0; j--)
2065 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2069 memset (&clobber_head, 0, sizeof(clobber_head));
2070 last = add_to_sequence (new, &clobber_head, "", type, 1);
2072 /* Find the end of the test chain on the last node. */
2073 for (test = last->tests; test->next; test = test->next)
2076 /* We definitely have a new test to add -- create a new
2078 place = &test->next;
2079 if (test->type == DT_accept_op)
2081 last = new_decision ("", &last->success);
2082 place = &last->tests;
2087 test = new_decision_test (DT_c_test, &place);
2088 test->u.c_test = c_test;
2091 test = new_decision_test (DT_accept_insn, &place);
2092 test->u.insn.code_number = next_insn_code;
2093 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2095 merge_trees (&head, &clobber_head);
2101 /* Define the subroutine we will call below and emit in genemit. */
2102 printf ("extern rtx gen_split_%d PROTO ((rtx *));\n", next_insn_code);
2106 /* Define the subroutine we will call below and emit in genemit. */
2107 printf ("extern rtx gen_peephole2_%d PROTO ((rtx, rtx *));\n",
2117 process_tree (head, subroutine_type)
2118 struct decision_head *head;
2119 enum routine_type subroutine_type;
2121 if (head->first == NULL)
2124 factor_tests (head);
2125 simplify_tests (head);
2127 next_subroutine_number = 0;
2128 break_out_subroutines (head, 1);
2129 find_afterward (head, NULL);
2131 write_subroutines (head, subroutine_type);
2132 write_subroutine (head, subroutine_type);
2141 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2145 progname = "genrecog";
2146 obstack_init (rtl_obstack);
2148 memset (&recog_tree, 0, sizeof recog_tree);
2149 memset (&split_tree, 0, sizeof split_tree);
2150 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2153 fatal ("No input file name.");
2155 infile = fopen (argv[1], "r");
2159 return FATAL_EXIT_CODE;
2167 /* Read the machine description. */
2171 c = read_skip_spaces (infile);
2176 desc = read_rtx (infile);
2177 if (GET_CODE (desc) == DEFINE_INSN)
2179 h = make_insn_sequence (desc, RECOG);
2180 merge_trees (&recog_tree, &h);
2182 else if (GET_CODE (desc) == DEFINE_SPLIT)
2184 h = make_insn_sequence (desc, SPLIT);
2185 merge_trees (&split_tree, &h);
2187 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2189 h = make_insn_sequence (desc, PEEPHOLE2);
2190 merge_trees (&peephole2_tree, &h);
2193 if (GET_CODE (desc) == DEFINE_PEEPHOLE
2194 || GET_CODE (desc) == DEFINE_EXPAND)
2201 process_tree (&recog_tree, RECOG);
2202 process_tree (&split_tree, SPLIT);
2203 process_tree (&peephole2_tree, PEEPHOLE2);
2206 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2209 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2211 get_insn_name (code)
2214 if (code < insn_name_ptr_size)
2215 return insn_name_ptr[code];
2221 record_insn_name (code, name)
2225 static const char *last_real_name = "insn";
2226 static int last_real_code = 0;
2229 if (insn_name_ptr_size <= code)
2232 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2234 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2235 memset (insn_name_ptr + insn_name_ptr_size, 0,
2236 sizeof(char *) * (new_size - insn_name_ptr_size));
2237 insn_name_ptr_size = new_size;
2240 if (!name || name[0] == '\0')
2242 new = xmalloc (strlen (last_real_name) + 10);
2243 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2247 last_real_name = new = xstrdup (name);
2248 last_real_code = code;
2251 insn_name_ptr[code] = new;
2258 register size_t len = strlen (input) + 1;
2259 register char *output = xmalloc (len);
2260 memcpy (output, input, len);
2265 xrealloc (old, size)
2271 ptr = (PTR) realloc (old, size);
2273 ptr = (PTR) malloc (size);
2275 fatal ("virtual memory exhausted");
2283 register PTR val = (PTR) malloc (size);
2286 fatal ("virtual memory exhausted");
2291 debug_decision_2 (test)
2292 struct decision_test *test;
2297 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2300 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2303 fprintf (stderr, "veclen=%d", test->u.veclen);
2305 case DT_elt_zero_int:
2306 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2308 case DT_elt_one_int:
2309 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2311 case DT_elt_zero_wide:
2312 fprintf (stderr, "elt0_w=");
2313 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2316 fprintf (stderr, "dup=%d", test->u.dup);
2319 fprintf (stderr, "pred=(%s,%s)",
2320 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2325 strncpy (sub, test->u.c_test, sizeof(sub));
2326 memcpy (sub+16, "...", 4);
2327 fprintf (stderr, "c_test=\"%s\"", sub);
2331 fprintf (stderr, "A_op=%d", test->u.opno);
2333 case DT_accept_insn:
2334 fprintf (stderr, "A_insn=(%d,%d)",
2335 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2344 debug_decision_1 (d, indent)
2349 struct decision_test *test;
2353 for (i = 0; i < indent; ++i)
2355 fputs ("(nil)\n", stderr);
2359 for (i = 0; i < indent; ++i)
2366 debug_decision_2 (test);
2367 while ((test = test->next) != NULL)
2369 fputs (" + ", stderr);
2370 debug_decision_2 (test);
2373 fprintf (stderr, "} %d\n", d->number);
2377 debug_decision_0 (d, indent, maxdepth)
2379 int indent, maxdepth;
2388 for (i = 0; i < indent; ++i)
2390 fputs ("(nil)\n", stderr);
2394 debug_decision_1 (d, indent);
2395 for (n = d->success.first; n ; n = n->next)
2396 debug_decision_0 (n, indent + 2, maxdepth - 1);
2403 debug_decision_0 (d, 0, 1000000);