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",
483 /* Wildcard match. Can't enforce a mode because we allow
484 anything -- const_int included. */
488 /* Accept the operand, ie. record it in `operands'. */
489 test = new_decision_test (DT_accept_op, &place);
490 test->u.opno = XINT (pattern, 0);
492 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
494 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
495 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
497 subpos[depth] = i + base;
498 sub = add_to_sequence (XVECEXP (pattern, 2, i),
499 &sub->success, subpos, insn_type, 0);
508 test = new_decision_test (DT_dup, &place);
509 test->u.dup = XINT (pattern, 0);
511 test = new_decision_test (DT_accept_op, &place);
512 test->u.opno = XINT (pattern, 0);
514 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
516 subpos[depth] = i + '0';
517 sub = add_to_sequence (XVECEXP (pattern, 1, i),
518 &sub->success, subpos, insn_type, 0);
526 test = new_decision_test (DT_dup, &place);
527 test->u.dup = XINT (pattern, 0);
531 pattern = XEXP (pattern, 0);
535 /* The operands of a SET must have the same mode unless one
537 if (GET_MODE (SET_SRC (pattern)) != VOIDmode
538 && GET_MODE (SET_DEST (pattern)) != VOIDmode
539 && GET_MODE (SET_SRC (pattern)) != GET_MODE (SET_DEST (pattern))
540 /* The mode of an ADDRESS_OPERAND is the mode of the memory
541 reference, not the mode of the address. */
542 && ! (GET_CODE (SET_SRC (pattern)) == MATCH_OPERAND
543 && ! strcmp (XSTR (SET_SRC (pattern), 1), "address_operand")))
545 print_rtl (stderr, pattern);
546 fputc ('\n', stderr);
547 fatal ("mode mismatch in SET");
552 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
554 print_rtl (stderr, pattern);
555 fputc ('\n', stderr);
556 fatal ("operand to LABEL_REF not VOIDmode");
564 fmt = GET_RTX_FORMAT (code);
565 len = GET_RTX_LENGTH (code);
567 /* Do tests against the current node first. */
568 for (i = 0; i < (size_t) len; i++)
574 test = new_decision_test (DT_elt_zero_int, &place);
575 test->u.intval = XINT (pattern, i);
579 test = new_decision_test (DT_elt_one_int, &place);
580 test->u.intval = XINT (pattern, i);
585 else if (fmt[i] == 'w')
590 test = new_decision_test (DT_elt_zero_wide, &place);
591 test->u.intval = XWINT (pattern, i);
593 else if (fmt[i] == 'E')
598 test = new_decision_test (DT_veclen, &place);
599 test->u.veclen = XVECLEN (pattern, i);
603 /* Now test our sub-patterns. */
604 for (i = 0; i < (size_t) len; i++)
609 subpos[depth] = '0' + i;
610 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
611 subpos, insn_type, 0);
617 for (j = 0; j < XVECLEN (pattern, i); j++)
619 subpos[depth] = 'a' + j;
620 sub = add_to_sequence (XVECEXP (pattern, i, j),
621 &sub->success, subpos, insn_type, 0);
638 /* Insert nodes testing mode and code, if they're still relevant,
639 before any of the nodes we may have added above. */
642 place = &this->tests;
643 test = new_decision_test (DT_code, &place);
647 if (mode != VOIDmode)
649 place = &this->tests;
650 test = new_decision_test (DT_mode, &place);
654 /* If we didn't insert any tests or accept nodes, hork. */
655 if (this->tests == NULL)
661 /* A subroutine of maybe_both_true; examines only one test.
662 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
665 maybe_both_true_2 (d1, d2)
666 struct decision_test *d1, *d2;
668 if (d1->type == d2->type)
673 return d1->u.mode == d2->u.mode;
676 return d1->u.code == d2->u.code;
679 return d1->u.veclen == d2->u.veclen;
681 case DT_elt_zero_int:
683 case DT_elt_zero_wide:
684 return d1->u.intval == d2->u.intval;
691 /* If either has a predicate that we know something about, set
692 things up so that D1 is the one that always has a known
693 predicate. Then see if they have any codes in common. */
695 if (d1->type == DT_pred || d2->type == DT_pred)
697 if (d2->type == DT_pred)
699 struct decision_test *tmp;
700 tmp = d1, d1 = d2, d2 = tmp;
703 /* If D2 tests a mode, see if it matches D1. */
704 if (d1->u.pred.mode != VOIDmode)
706 if (d2->type == DT_mode)
708 if (d1->u.pred.mode != d2->u.mode)
711 else if (d2->type == DT_pred)
713 if (d2->u.pred.mode != VOIDmode
714 && d1->u.pred.mode != d2->u.pred.mode)
719 if (d1->u.pred.index >= 0)
721 /* If D2 tests a code, see if it is in the list of valid
722 codes for D1's predicate. */
723 if (d2->type == DT_code)
725 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
728 if (*c == d2->u.code)
736 /* Otherwise see if the predicates have any codes in common. */
737 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
739 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
742 while (*c1 != 0 && !common)
744 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
745 while (*c2 != 0 && !common)
747 common = (*c1 == *c2);
762 /* A subroutine of maybe_both_true; examines all the tests for a given node.
763 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
766 maybe_both_true_1 (d1, d2)
767 struct decision_test *d1, *d2;
769 struct decision_test *t1, *t2;
771 /* A match_operand with no predicate can match anything. Recognize
772 this by the existance of a lone DT_accept_op test. */
773 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
776 /* Eliminate pairs of tests while they can exactly match. */
777 while (d1 && d2 && d1->type == d2->type)
779 if (maybe_both_true_2 (d1, d2) == 0)
781 d1 = d1->next, d2 = d2->next;
784 /* After that, consider all pairs. */
785 for (t1 = d1; t1 ; t1 = t1->next)
786 for (t2 = d2; t2 ; t2 = t2->next)
787 if (maybe_both_true_2 (t1, t2) == 0)
793 /* Return 0 if we can prove that there is no RTL that can match both
794 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
795 can match both or just that we couldn't prove there wasn't such an RTL).
797 TOPLEVEL is non-zero if we are to only look at the top level and not
798 recursively descend. */
801 maybe_both_true (d1, d2, toplevel)
802 struct decision *d1, *d2;
805 struct decision *p1, *p2;
808 /* Don't compare strings on the different positions in insn. Doing so
809 is incorrect and results in false matches from constructs like
811 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
812 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
814 [(set (match_operand:HI "register_operand" "r")
815 (match_operand:HI "register_operand" "r"))]
817 If we are presented with such, we are recursing through the remainder
818 of a node's success nodes (from the loop at the end of this function).
819 Skip forward until we come to a position that matches.
821 Due to the way position strings are constructed, we know that iterating
822 forward from the lexically lower position (e.g. "00") will run into
823 the lexically higher position (e.g. "1") and not the other way around.
824 This saves a bit of effort. */
826 cmp = strcmp (d1->position, d2->position);
832 /* If the d2->position was lexically lower, swap. */
834 p1 = d1, d1 = d2, d2 = p1;
836 if (d1->success.first == 0)
838 for (p1 = d1->success.first; p1; p1 = p1->next)
839 if (maybe_both_true (p1, d2, 0))
845 /* Test the current level. */
846 cmp = maybe_both_true_1 (d1->tests, d2->tests);
850 /* We can't prove that D1 and D2 cannot both be true. If we are only
851 to check the top level, return 1. Otherwise, see if we can prove
852 that all choices in both successors are mutually exclusive. If
853 either does not have any successors, we can't prove they can't both
856 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
859 for (p1 = d1->success.first; p1; p1 = p1->next)
860 for (p2 = d2->success.first; p2; p2 = p2->next)
861 if (maybe_both_true (p1, p2, 0))
867 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
870 nodes_identical_1 (d1, d2)
871 struct decision_test *d1, *d2;
876 return d1->u.mode == d2->u.mode;
879 return d1->u.code == d2->u.code;
882 return (d1->u.pred.mode == d2->u.pred.mode
883 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
886 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
889 return d1->u.veclen == d2->u.veclen;
892 return d1->u.dup == d2->u.dup;
894 case DT_elt_zero_int:
896 case DT_elt_zero_wide:
897 return d1->u.intval == d2->u.intval;
900 return d1->u.opno == d2->u.opno;
903 /* Differences will be handled in merge_accept_insn. */
911 /* True iff the two nodes are identical (on one level only). Due
912 to the way these lists are constructed, we shouldn't have to
913 consider different orderings on the tests. */
916 nodes_identical (d1, d2)
917 struct decision *d1, *d2;
919 struct decision_test *t1, *t2;
921 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
923 if (t1->type != t2->type)
925 if (! nodes_identical_1 (t1, t2))
929 /* For success, they should now both be null. */
933 /* A subroutine of merge_trees; given two nodes that have been declared
934 identical, cope with two insn accept states. If they differ in the
935 number of clobbers, then the conflict was created by make_insn_sequence
936 and we can drop the with-clobbers version on the floor. If both
937 nodes have no additional clobbers, we have found an ambiguity in the
938 source machine description. */
941 merge_accept_insn (oldd, addd)
942 struct decision *oldd, *addd;
944 struct decision_test *old, *add;
946 for (old = oldd->tests; old; old = old->next)
947 if (old->type == DT_accept_insn)
952 for (add = addd->tests; add; add = add->next)
953 if (add->type == DT_accept_insn)
958 /* If one node is for a normal insn and the second is for the base
959 insn with clobbers stripped off, the second node should be ignored. */
961 if (old->u.insn.num_clobbers_to_add == 0
962 && add->u.insn.num_clobbers_to_add > 0)
964 /* Nothing to do here. */
966 else if (old->u.insn.num_clobbers_to_add > 0
967 && add->u.insn.num_clobbers_to_add == 0)
969 /* In this case, replace OLD with ADD. */
970 old->u.insn = add->u.insn;
974 fatal ("Two actions at one point in tree for insns \"%s\" (%d) and \"%s\" (%d)",
975 get_insn_name (old->u.insn.code_number),
976 old->u.insn.code_number,
977 get_insn_name (add->u.insn.code_number),
978 add->u.insn.code_number);
982 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
985 merge_trees (oldh, addh)
986 struct decision_head *oldh, *addh;
988 struct decision *next, *add;
990 if (addh->first == 0)
992 if (oldh->first == 0)
998 /* Trying to merge bits at different positions isn't possible. */
999 if (strcmp (oldh->first->position, addh->first->position))
1002 for (add = addh->first; add ; add = next)
1004 struct decision *old, *insert_before = NULL;
1008 /* The semantics of pattern matching state that the tests are
1009 done in the order given in the MD file so that if an insn
1010 matches two patterns, the first one will be used. However,
1011 in practice, most, if not all, patterns are unambiguous so
1012 that their order is independent. In that case, we can merge
1013 identical tests and group all similar modes and codes together.
1015 Scan starting from the end of OLDH until we reach a point
1016 where we reach the head of the list or where we pass a
1017 pattern that could also be true if NEW is true. If we find
1018 an identical pattern, we can merge them. Also, record the
1019 last node that tests the same code and mode and the last one
1020 that tests just the same mode.
1022 If we have no match, place NEW after the closest match we found. */
1024 for (old = oldh->last; old; old = old->prev)
1026 if (nodes_identical (old, add))
1028 merge_accept_insn (old, add);
1029 merge_trees (&old->success, &add->success);
1033 if (maybe_both_true (old, add, 0))
1036 /* Insert the nodes in DT test type order, which is roughly
1037 how expensive/important the test is. Given that the tests
1038 are also ordered within the list, examining the first is
1040 if (add->tests->type < old->tests->type)
1041 insert_before = old;
1044 if (insert_before == NULL)
1047 add->prev = oldh->last;
1048 oldh->last->next = add;
1053 if ((add->prev = insert_before->prev) != NULL)
1054 add->prev->next = add;
1057 add->next = insert_before;
1058 insert_before->prev = add;
1065 /* Walk the tree looking for sub-nodes that perform common tests.
1066 Factor out the common test into a new node. This enables us
1067 (depending on the test type) to emit switch statements later. */
1071 struct decision_head *head;
1073 struct decision *first, *next;
1075 for (first = head->first; first && first->next; first = next)
1077 enum decision_type type;
1078 struct decision *new, *old_last;
1080 type = first->tests->type;
1083 /* Want at least two compatible sequential nodes. */
1084 if (next->tests->type != type)
1087 /* Don't want all node types, just those we can turn into
1088 switch statements. */
1091 && type != DT_veclen
1092 && type != DT_elt_zero_int
1093 && type != DT_elt_one_int
1094 && type != DT_elt_zero_wide)
1097 /* If we'd been performing more than one test, create a new node
1098 below our first test. */
1099 if (first->tests->next != NULL)
1101 new = new_decision (first->position, &first->success);
1102 new->tests = first->tests->next;
1103 first->tests->next = NULL;
1106 /* Crop the node tree off after our first test. */
1108 old_last = head->last;
1111 /* For each compatible test, adjust to perform only one test in
1112 the top level node, then merge the node back into the tree. */
1115 struct decision_head h;
1117 if (next->tests->next != NULL)
1119 new = new_decision (next->position, &next->success);
1120 new->tests = next->tests->next;
1121 next->tests->next = NULL;
1126 h.first = h.last = new;
1128 merge_trees (head, &h);
1130 while (next && next->tests->type == type);
1132 /* After we run out of compatible tests, graft the remaining nodes
1133 back onto the tree. */
1136 next->prev = head->last;
1137 head->last->next = next;
1138 head->last = old_last;
1143 for (first = head->first; first; first = first->next)
1144 factor_tests (&first->success);
1147 /* After factoring, try to simplify the tests on any one node.
1148 Tests that are useful for switch statements are recognizable
1149 by having only a single test on a node -- we'll be manipulating
1150 nodes with multiple tests:
1152 If we have mode tests or code tests that are redundant with
1153 predicates, remove them. */
1156 simplify_tests (head)
1157 struct decision_head *head;
1159 struct decision *tree;
1161 for (tree = head->first; tree; tree = tree->next)
1163 struct decision_test *a, *b;
1170 /* Find a predicate node. */
1171 while (b && b->type != DT_pred)
1175 /* Due to how these tests are constructed, we don't even need
1176 to check that the mode and code are compatible -- they were
1177 generated from the predicate in the first place. */
1178 while (a->type == DT_mode || a->type == DT_code)
1185 for (tree = head->first; tree; tree = tree->next)
1186 simplify_tests (&tree->success);
1189 /* Count the number of subnodes of HEAD. If the number is high enough,
1190 make the first node in HEAD start a separate subroutine in the C code
1191 that is generated. */
1194 break_out_subroutines (head, initial)
1195 struct decision_head *head;
1199 struct decision *sub;
1201 for (sub = head->first; sub; sub = sub->next)
1202 size += 1 + break_out_subroutines (&sub->success, 0);
1204 if (size > SUBROUTINE_THRESHOLD && ! initial)
1206 head->first->subroutine_number = ++next_subroutine_number;
1212 /* For each node p, find the next alternative that might be true
1216 find_afterward (head, real_afterward)
1217 struct decision_head *head;
1218 struct decision *real_afterward;
1220 struct decision *p, *q, *afterward;
1222 /* We can't propogate alternatives across subroutine boundaries.
1223 This is not incorrect, merely a minor optimization loss. */
1226 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1228 for ( ; p ; p = p->next)
1230 /* Find the next node that might be true if this one fails. */
1231 for (q = p->next; q ; q = q->next)
1232 if (maybe_both_true (p, q, 1))
1235 /* If we reached the end of the list without finding one,
1236 use the incoming afterward position. */
1245 for (p = head->first; p ; p = p->next)
1246 if (p->success.first)
1247 find_afterward (&p->success, p->afterward);
1249 /* When we are generating a subroutine, record the real afterward
1250 position in the first node where write_tree can find it, and we
1251 can do the right thing at the subroutine call site. */
1253 if (p->subroutine_number > 0)
1254 p->afterward = real_afterward;
1257 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1258 actions are necessary to move to NEWPOS. If we fail to move to the
1259 new state, branch to node AFTERWARD if non-zero, otherwise return.
1261 Failure to move to the new state can only occur if we are trying to
1262 match multiple insns and we try to step past the end of the stream. */
1265 change_state (oldpos, newpos, afterward, indent)
1268 struct decision *afterward;
1271 int odepth = strlen (oldpos);
1272 int ndepth = strlen (newpos);
1274 int old_has_insn, new_has_insn;
1276 /* Pop up as many levels as necessary. */
1277 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1280 /* Hunt for the last [A-Z] in both strings. */
1281 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1282 if (oldpos[old_has_insn] >= 'A' && oldpos[old_has_insn] <= 'Z')
1284 for (new_has_insn = odepth - 1; new_has_insn >= 0; --new_has_insn)
1285 if (newpos[new_has_insn] >= 'A' && newpos[new_has_insn] <= 'Z')
1288 /* Make sure to reset the _last_insn pointer when popping back up. */
1289 if (old_has_insn >= 0 && new_has_insn < 0)
1290 printf ("%s_last_insn = insn;\n", indent);
1292 /* Go down to desired level. */
1293 while (depth < ndepth)
1295 /* It's a different insn from the first one. */
1296 if (newpos[depth] >= 'A' && newpos[depth] <= 'Z')
1298 /* We can only fail if we're moving down the tree. */
1299 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1301 printf ("%s_last_insn = recog_next_insn (insn, %d);\n",
1302 indent, newpos[depth] - 'A');
1306 printf ("%stem = recog_next_insn (insn, %d);\n",
1307 indent, newpos[depth] - 'A');
1308 printf ("%sif (tem == NULL_RTX)\n", indent);
1310 printf ("%s goto L%d;\n", indent, afterward->number);
1312 printf ("%s goto ret0;\n", indent);
1313 printf ("%s_last_insn = tem;\n", indent);
1315 printf ("%sx%d = PATTERN (_last_insn);\n", indent, depth + 1);
1317 else if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1318 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1319 indent, depth + 1, depth, newpos[depth] - 'a');
1321 printf ("%sx%d = XEXP (x%d, %c);\n",
1322 indent, depth + 1, depth, newpos[depth]);
1327 /* Print the enumerator constant for CODE -- the upcase version of
1334 register const char *p;
1335 for (p = GET_RTX_NAME (code); *p; p++)
1336 putchar (TOUPPER (*p));
1339 /* Emit code to cross an afterward link -- change state and branch. */
1342 write_afterward (start, afterward, indent)
1343 struct decision *start;
1344 struct decision *afterward;
1347 if (!afterward || start->subroutine_number > 0)
1348 printf("%sgoto ret0;\n", indent);
1351 change_state (start->position, afterward->position, NULL, indent);
1352 printf ("%sgoto L%d;\n", indent, afterward->number);
1356 /* Emit a switch statement, if possible, for an initial sequence of
1357 nodes at START. Return the first node yet untested. */
1359 static struct decision *
1360 write_switch (start, depth)
1361 struct decision *start;
1364 struct decision *p = start;
1365 enum decision_type type = p->tests->type;
1367 /* If we have two or more nodes in sequence that test the same one
1368 thing, we may be able to use a switch statement. */
1372 || p->next->tests->type != type
1373 || p->next->tests->next)
1376 /* DT_code is special in that we can do interesting things with
1377 known predicates at the same time. */
1378 if (type == DT_code)
1380 char codemap[NUM_RTX_CODE];
1381 struct decision *ret;
1383 memset (codemap, 0, sizeof(codemap));
1385 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1388 RTX_CODE code = p->tests->u.code;
1391 printf (":\n goto L%d;\n", p->success.first->number);
1392 p->success.first->need_label = 1;
1397 while (p && p->tests->type == DT_code && !p->tests->next);
1399 /* If P is testing a predicate that we know about and we haven't
1400 seen any of the codes that are valid for the predicate, we can
1401 write a series of "case" statement, one for each possible code.
1402 Since we are already in a switch, these redundant tests are very
1403 cheap and will reduce the number of predicates called. */
1405 /* Note that while we write out cases for these predicates here,
1406 we don't actually write the test here, as it gets kinda messy.
1407 It is trivial to leave this to later by telling our caller that
1408 we only processed the CODE tests. */
1411 while (p && p->tests->type == DT_pred
1412 && p->tests->u.pred.index >= 0)
1416 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1417 if (codemap[(int) *c] != 0)
1420 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1425 codemap[(int) *c] = 1;
1428 printf (" goto L%d;\n", p->number);
1434 /* Make the default case skip the predicates we managed to match. */
1436 printf (" default:\n");
1441 printf (" goto L%d;\n", p->number);
1445 write_afterward (start, start->afterward, " ");
1448 printf (" break;\n");
1453 else if (type == DT_mode
1454 || type == DT_veclen
1455 || type == DT_elt_zero_int
1456 || type == DT_elt_one_int
1457 || type == DT_elt_zero_wide)
1461 printf (" switch (");
1465 str = "GET_MODE (x%d)";
1468 str = "XVECLEN (x%d, 0)";
1470 case DT_elt_zero_int:
1471 str = "XINT (x%d, 0)";
1473 case DT_elt_one_int:
1474 str = "XINT (x%d, 1)";
1476 case DT_elt_zero_wide:
1477 str = "XWINT (x%d, 0)";
1482 printf (str, depth);
1491 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1494 printf ("%d", p->tests->u.veclen);
1496 case DT_elt_zero_int:
1497 case DT_elt_one_int:
1498 case DT_elt_zero_wide:
1499 printf (HOST_WIDE_INT_PRINT_DEC, p->tests->u.intval);
1504 printf (":\n goto L%d;\n", p->success.first->number);
1505 p->success.first->need_label = 1;
1509 while (p && p->tests->type == type && !p->tests->next);
1511 printf (" default:\n break;\n }\n");
1517 /* None of the other tests are ameanable. */
1522 /* Emit code for one test. */
1525 write_cond (p, depth, subroutine_type)
1526 struct decision_test *p;
1528 enum routine_type subroutine_type;
1533 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1537 printf ("GET_CODE (x%d) == ", depth);
1538 print_code (p->u.code);
1542 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1545 case DT_elt_zero_int:
1546 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1549 case DT_elt_one_int:
1550 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1553 case DT_elt_zero_wide:
1554 printf ("XWINT (x%d, 0) == ", depth);
1555 printf (HOST_WIDE_INT_PRINT_DEC, p->u.intval);
1559 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1563 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1564 GET_MODE_NAME (p->u.pred.mode));
1568 printf ("(%s)", p->u.c_test);
1571 case DT_accept_insn:
1572 switch (subroutine_type)
1575 if (p->u.insn.num_clobbers_to_add == 0)
1577 printf ("pnum_clobbers != NULL");
1590 /* Emit code for one action. The previous tests have succeeded;
1591 TEST is the last of the chain. In the normal case we simply
1592 perform a state change. For the `accept' tests we must do more work. */
1595 write_action (test, depth, uncond, success, subroutine_type)
1596 struct decision_test *test;
1598 struct decision *success;
1599 enum routine_type subroutine_type;
1606 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1608 fputs (" {\n", stdout);
1615 if (test->type == DT_accept_op)
1617 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1619 /* Only allow DT_accept_insn to follow. */
1623 if (test->type != DT_accept_insn)
1628 /* Sanity check that we're now at the end of the list of tests. */
1632 if (test->type == DT_accept_insn)
1634 switch (subroutine_type)
1637 if (test->u.insn.num_clobbers_to_add != 0)
1638 printf ("%s*pnum_clobbers = %d;\n",
1639 indent, test->u.insn.num_clobbers_to_add);
1640 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
1644 printf ("%sreturn gen_split_%d (operands);\n",
1645 indent, test->u.insn.code_number);
1649 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1650 indent, test->u.insn.code_number);
1651 printf ("%sif (tem != 0)\n%s goto ret1;\n", indent, indent);
1660 printf("%sgoto L%d;\n", indent, success->number);
1661 success->need_label = 1;
1665 fputs (" }\n", stdout);
1668 /* Return 1 if the test is always true and has no fallthru path. Return -1
1669 if the test does have a fallthru path, but requires that the condition be
1670 terminated. Otherwise return 0 for a normal test. */
1671 /* ??? is_unconditional is a stupid name for a tri-state function. */
1674 is_unconditional (t, subroutine_type)
1675 struct decision_test *t;
1676 enum routine_type subroutine_type;
1678 if (t->type == DT_accept_op)
1681 if (t->type == DT_accept_insn)
1683 switch (subroutine_type)
1686 return (t->u.insn.num_clobbers_to_add == 0);
1699 /* Emit code for one node -- the conditional and the accompanying action.
1700 Return true if there is no fallthru path. */
1703 write_node (p, depth, subroutine_type)
1706 enum routine_type subroutine_type;
1708 struct decision_test *test, *last_test;
1711 last_test = test = p->tests;
1712 uncond = is_unconditional (test, subroutine_type);
1716 write_cond (test, depth, subroutine_type);
1718 while ((test = test->next) != NULL)
1723 uncond2 = is_unconditional (test, subroutine_type);
1728 write_cond (test, depth, subroutine_type);
1734 write_action (last_test, depth, uncond, p->success.first, subroutine_type);
1739 /* Emit code for all of the sibling nodes of HEAD. */
1742 write_tree_1 (head, depth, subroutine_type)
1743 struct decision_head *head;
1745 enum routine_type subroutine_type;
1747 struct decision *p, *next;
1750 for (p = head->first; p ; p = next)
1752 /* The label for the first element was printed in write_tree. */
1753 if (p != head->first && p->need_label)
1754 OUTPUT_LABEL (" ", p->number);
1756 /* Attempt to write a switch statement for a whole sequence. */
1757 next = write_switch (p, depth);
1762 /* Failed -- fall back and write one node. */
1763 uncond = write_node (p, depth, subroutine_type);
1768 /* Finished with this chain. Close a fallthru path by branching
1769 to the afterward node. */
1771 write_afterward (head->last, head->last->afterward, " ");
1774 /* Write out the decision tree starting at HEAD. PREVPOS is the
1775 position at the node that branched to this node. */
1778 write_tree (head, prevpos, type, initial)
1779 struct decision_head *head;
1780 const char *prevpos;
1781 enum routine_type type;
1784 register struct decision *p = head->first;
1788 OUTPUT_LABEL (" ", p->number);
1790 if (! initial && p->subroutine_number > 0)
1792 static const char * const name_prefix[] = {
1793 "recog", "split", "peephole2"
1796 static const char * const call_suffix[] = {
1797 ", pnum_clobbers", "", ", _plast_insn"
1800 /* This node has been broken out into a separate subroutine.
1801 Call it, test the result, and branch accordingly. */
1805 printf (" tem = %s_%d (x0, insn%s);\n",
1806 name_prefix[type], p->subroutine_number, call_suffix[type]);
1807 if (IS_SPLIT (type))
1808 printf (" if (tem != 0)\n return tem;\n");
1810 printf (" if (tem >= 0)\n return tem;\n");
1812 change_state (p->position, p->afterward->position, NULL, " ");
1813 printf (" goto L%d;\n", p->afterward->number);
1817 printf (" return %s_%d (x0, insn%s);\n",
1818 name_prefix[type], p->subroutine_number, call_suffix[type]);
1823 int depth = strlen (p->position);
1825 change_state (prevpos, p->position, head->last->afterward, " ");
1826 write_tree_1 (head, depth, type);
1828 for (p = head->first; p; p = p->next)
1829 if (p->success.first)
1830 write_tree (&p->success, p->position, type, 0);
1834 /* Write out a subroutine of type TYPE to do comparisons starting at
1838 write_subroutine (head, type)
1839 struct decision_head *head;
1840 enum routine_type type;
1842 static const char * const proto_pattern[] = {
1843 "%sint recog%s PROTO ((rtx, rtx, int *));\n",
1844 "%srtx split%s PROTO ((rtx, rtx));\n",
1845 "%srtx peephole2%s PROTO ((rtx, rtx, rtx *));\n"
1848 static const char * const decl_pattern[] = {
1850 recog%s (x0, insn, pnum_clobbers)\n\
1852 rtx insn ATTRIBUTE_UNUSED;\n\
1853 int *pnum_clobbers ATTRIBUTE_UNUSED;\n",
1856 split%s (x0, insn)\n\
1858 rtx insn ATTRIBUTE_UNUSED;\n",
1861 peephole2%s (x0, insn, _plast_insn)\n\
1863 rtx insn ATTRIBUTE_UNUSED;\n\
1864 rtx *_plast_insn ATTRIBUTE_UNUSED;\n"
1867 int subfunction = head->first->subroutine_number;
1872 s_or_e = subfunction ? "static " : "";
1875 sprintf (extension, "_%d", subfunction);
1876 else if (type == RECOG)
1877 extension[0] = '\0';
1879 strcpy (extension, "_insns");
1881 printf (proto_pattern[type], s_or_e, extension);
1882 printf (decl_pattern[type], s_or_e, extension);
1884 printf ("{\n register rtx * const operands = &recog_data.operand[0];\n");
1885 for (i = 1; i <= max_depth; i++)
1886 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i);
1888 if (type == PEEPHOLE2)
1889 printf (" register rtx _last_insn = insn;\n");
1890 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
1892 write_tree (head, "", type, 1);
1894 if (type == PEEPHOLE2)
1895 printf (" ret1:\n *_plast_insn = _last_insn;\n return tem;\n");
1896 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
1899 /* In break_out_subroutines, we discovered the boundaries for the
1900 subroutines, but did not write them out. Do so now. */
1903 write_subroutines (head, type)
1904 struct decision_head *head;
1905 enum routine_type type;
1909 for (p = head->first; p ; p = p->next)
1910 if (p->success.first)
1911 write_subroutines (&p->success, type);
1913 if (head->first->subroutine_number > 0)
1914 write_subroutine (head, type);
1917 /* Begin the output file. */
1923 /* Generated automatically by the program `genrecog' from the target\n\
1924 machine description file. */\n\
1926 #include \"config.h\"\n\
1927 #include \"system.h\"\n\
1928 #include \"rtl.h\"\n\
1929 #include \"tm_p.h\"\n\
1930 #include \"function.h\"\n\
1931 #include \"insn-config.h\"\n\
1932 #include \"recog.h\"\n\
1933 #include \"real.h\"\n\
1934 #include \"output.h\"\n\
1935 #include \"flags.h\"\n\
1936 #include \"hard-reg-set.h\"\n\
1937 #include \"resource.h\"\n\
1941 /* `recog' contains a decision tree that recognizes whether the rtx\n\
1942 X0 is a valid instruction.\n\
1944 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
1945 returns a nonnegative number which is the insn code number for the\n\
1946 pattern that matched. This is the same as the order in the machine\n\
1947 description of the entry that matched. This number can be used as an\n\
1948 index into `insn_data' and other tables.\n\
1950 The third argument to recog is an optional pointer to an int. If\n\
1951 present, recog will accept a pattern if it matches except for missing\n\
1952 CLOBBER expressions at the end. In that case, the value pointed to by\n\
1953 the optional pointer will be set to the number of CLOBBERs that need\n\
1954 to be added (it should be initialized to zero by the caller). If it\n\
1955 is set nonzero, the caller should allocate a PARALLEL of the\n\
1956 appropriate size, copy the initial entries, and call add_clobbers\n\
1957 (found in insn-emit.c) to fill in the CLOBBERs.\n\
1961 The function split_insns returns 0 if the rtl could not\n\
1962 be split or the split rtl in a SEQUENCE if it can be.\n\
1964 The function peephole2_insns returns 0 if the rtl could not\n\
1965 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
1966 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
1971 /* Construct and return a sequence of decisions
1972 that will recognize INSN.
1974 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
1976 static struct decision_head
1977 make_insn_sequence (insn, type)
1979 enum routine_type type;
1982 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
1983 struct decision *last;
1984 struct decision_test *test, **place;
1985 struct decision_head head;
1987 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
1989 if (type == PEEPHOLE2)
1993 /* peephole2 gets special treatment:
1994 - X always gets an outer parallel even if it's only one entry
1995 - we remove all traces of outer-level match_scratch and match_dup
1996 expressions here. */
1997 x = rtx_alloc (PARALLEL);
1998 PUT_MODE (x, VOIDmode);
1999 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2000 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2002 rtx tmp = XVECEXP (insn, 0, i);
2003 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2005 XVECEXP (x, 0, j) = tmp;
2011 else if (XVECLEN (insn, type == RECOG) == 1)
2012 x = XVECEXP (insn, type == RECOG, 0);
2015 x = rtx_alloc (PARALLEL);
2016 XVEC (x, 0) = XVEC (insn, type == RECOG);
2017 PUT_MODE (x, VOIDmode);
2020 memset(&head, 0, sizeof(head));
2021 last = add_to_sequence (x, &head, "", type, 1);
2023 /* Find the end of the test chain on the last node. */
2024 for (test = last->tests; test->next; test = test->next)
2026 place = &test->next;
2030 /* Need a new node if we have another test to add. */
2031 if (test->type == DT_accept_op)
2033 last = new_decision ("", &last->success);
2034 place = &last->tests;
2036 test = new_decision_test (DT_c_test, &place);
2037 test->u.c_test = c_test;
2040 test = new_decision_test (DT_accept_insn, &place);
2041 test->u.insn.code_number = next_insn_code;
2042 test->u.insn.num_clobbers_to_add = 0;
2047 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2048 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2049 If so, set up to recognize the pattern without these CLOBBERs. */
2051 if (GET_CODE (x) == PARALLEL)
2055 /* Find the last non-clobber in the parallel. */
2056 for (i = XVECLEN (x, 0); i > 0; i--)
2058 rtx y = XVECEXP (x, 0, i - 1);
2059 if (GET_CODE (y) != CLOBBER
2060 || (GET_CODE (XEXP (y, 0)) != REG
2061 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2065 if (i != XVECLEN (x, 0))
2068 struct decision_head clobber_head;
2070 /* Build a similar insn without the clobbers. */
2072 new = XVECEXP (x, 0, 0);
2077 new = rtx_alloc (PARALLEL);
2078 XVEC (new, 0) = rtvec_alloc (i);
2079 for (j = i - 1; j >= 0; j--)
2080 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2084 memset (&clobber_head, 0, sizeof(clobber_head));
2085 last = add_to_sequence (new, &clobber_head, "", type, 1);
2087 /* Find the end of the test chain on the last node. */
2088 for (test = last->tests; test->next; test = test->next)
2091 /* We definitely have a new test to add -- create a new
2093 place = &test->next;
2094 if (test->type == DT_accept_op)
2096 last = new_decision ("", &last->success);
2097 place = &last->tests;
2102 test = new_decision_test (DT_c_test, &place);
2103 test->u.c_test = c_test;
2106 test = new_decision_test (DT_accept_insn, &place);
2107 test->u.insn.code_number = next_insn_code;
2108 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2110 merge_trees (&head, &clobber_head);
2116 /* Define the subroutine we will call below and emit in genemit. */
2117 printf ("extern rtx gen_split_%d PROTO ((rtx *));\n", next_insn_code);
2121 /* Define the subroutine we will call below and emit in genemit. */
2122 printf ("extern rtx gen_peephole2_%d PROTO ((rtx, rtx *));\n",
2132 process_tree (head, subroutine_type)
2133 struct decision_head *head;
2134 enum routine_type subroutine_type;
2136 if (head->first == NULL)
2139 factor_tests (head);
2140 simplify_tests (head);
2142 next_subroutine_number = 0;
2143 break_out_subroutines (head, 1);
2144 find_afterward (head, NULL);
2146 write_subroutines (head, subroutine_type);
2147 write_subroutine (head, subroutine_type);
2156 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2160 progname = "genrecog";
2161 obstack_init (rtl_obstack);
2163 memset (&recog_tree, 0, sizeof recog_tree);
2164 memset (&split_tree, 0, sizeof split_tree);
2165 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2168 fatal ("No input file name.");
2170 infile = fopen (argv[1], "r");
2174 return FATAL_EXIT_CODE;
2182 /* Read the machine description. */
2186 c = read_skip_spaces (infile);
2191 desc = read_rtx (infile);
2192 if (GET_CODE (desc) == DEFINE_INSN)
2194 h = make_insn_sequence (desc, RECOG);
2195 merge_trees (&recog_tree, &h);
2197 else if (GET_CODE (desc) == DEFINE_SPLIT)
2199 h = make_insn_sequence (desc, SPLIT);
2200 merge_trees (&split_tree, &h);
2202 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2204 h = make_insn_sequence (desc, PEEPHOLE2);
2205 merge_trees (&peephole2_tree, &h);
2208 if (GET_CODE (desc) == DEFINE_PEEPHOLE
2209 || GET_CODE (desc) == DEFINE_EXPAND)
2216 process_tree (&recog_tree, RECOG);
2217 process_tree (&split_tree, SPLIT);
2218 process_tree (&peephole2_tree, PEEPHOLE2);
2221 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2224 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2226 get_insn_name (code)
2229 if (code < insn_name_ptr_size)
2230 return insn_name_ptr[code];
2236 record_insn_name (code, name)
2240 static const char *last_real_name = "insn";
2241 static int last_real_code = 0;
2244 if (insn_name_ptr_size <= code)
2247 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2249 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2250 memset (insn_name_ptr + insn_name_ptr_size, 0,
2251 sizeof(char *) * (new_size - insn_name_ptr_size));
2252 insn_name_ptr_size = new_size;
2255 if (!name || name[0] == '\0')
2257 new = xmalloc (strlen (last_real_name) + 10);
2258 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2262 last_real_name = new = xstrdup (name);
2263 last_real_code = code;
2266 insn_name_ptr[code] = new;
2273 register size_t len = strlen (input) + 1;
2274 register char *output = xmalloc (len);
2275 memcpy (output, input, len);
2280 xrealloc (old, size)
2286 ptr = (PTR) realloc (old, size);
2288 ptr = (PTR) malloc (size);
2290 fatal ("virtual memory exhausted");
2298 register PTR val = (PTR) malloc (size);
2301 fatal ("virtual memory exhausted");
2306 debug_decision_2 (test)
2307 struct decision_test *test;
2312 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2315 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2318 fprintf (stderr, "veclen=%d", test->u.veclen);
2320 case DT_elt_zero_int:
2321 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2323 case DT_elt_one_int:
2324 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2326 case DT_elt_zero_wide:
2327 fprintf (stderr, "elt0_w=");
2328 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2331 fprintf (stderr, "dup=%d", test->u.dup);
2334 fprintf (stderr, "pred=(%s,%s)",
2335 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2340 strncpy (sub, test->u.c_test, sizeof(sub));
2341 memcpy (sub+16, "...", 4);
2342 fprintf (stderr, "c_test=\"%s\"", sub);
2346 fprintf (stderr, "A_op=%d", test->u.opno);
2348 case DT_accept_insn:
2349 fprintf (stderr, "A_insn=(%d,%d)",
2350 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2359 debug_decision_1 (d, indent)
2364 struct decision_test *test;
2368 for (i = 0; i < indent; ++i)
2370 fputs ("(nil)\n", stderr);
2374 for (i = 0; i < indent; ++i)
2381 debug_decision_2 (test);
2382 while ((test = test->next) != NULL)
2384 fputs (" + ", stderr);
2385 debug_decision_2 (test);
2388 fprintf (stderr, "} %d\n", d->number);
2392 debug_decision_0 (d, indent, maxdepth)
2394 int indent, maxdepth;
2403 for (i = 0; i < indent; ++i)
2405 fputs ("(nil)\n", stderr);
2409 debug_decision_1 (d, indent);
2410 for (n = d->success.first; n ; n = n->next)
2411 debug_decision_0 (n, indent + 2, maxdepth - 1);
2418 debug_decision_0 (d, 0, 1000000);