![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to genrecog.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to genrecog.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Generate code from machine description to recognize rtl as insns.
2: Copyright (C) 1987, 1988, 1992 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
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)
9: any later version.
10:
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.
15:
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, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* This program is used to produce insn-recog.c, which contains
22: a function called `recog' plus its subroutines.
23: These functions contain a decision tree
24: that recognizes whether an rtx, the argument given to recog,
25: is a valid instruction.
26:
27: recog returns -1 if the rtx is not valid.
28: If the rtx is valid, recog returns a nonnegative number
29: which is the insn code number for the pattern that matched.
30: This is the same as the order in the machine description of the
31: entry that matched. This number can be used as an index into various
32: insn_* tables, such as insn_template, insn_outfun, and insn_n_operands
33: (found in insn-output.c).
34:
35: The third argument to recog is an optional pointer to an int.
36: If present, recog will accept a pattern if it matches except for
37: missing CLOBBER expressions at the end. In that case, the value
38: pointed to by the optional pointer will be set to the number of
39: CLOBBERs that need to be added (it should be initialized to zero by
40: the caller). If it is set nonzero, the caller should allocate a
41: PARALLEL of the appropriate size, copy the initial entries, and call
42: add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
43:
44: This program also generates the function `split_insns',
45: which returns 0 if the rtl could not be split, or
46: it returns the split rtl in a SEQUENCE. */
47:
48: #include <stdio.h>
49: #include "config.h"
50: #include "rtl.h"
51: #include "obstack.h"
52:
53: static struct obstack obstack;
54: struct obstack *rtl_obstack = &obstack;
55:
56: #define obstack_chunk_alloc xmalloc
57: #define obstack_chunk_free free
58:
59: extern void free ();
1.1.1.2 ! root 60: extern rtx read_rtx ();
1.1 root 61:
62: /* Data structure for a listhead of decision trees. The alternatives
63: to a node are kept in a doublely-linked list so we can easily add nodes
64: to the proper place when merging. */
65:
66: struct decision_head { struct decision *first, *last; };
67:
68: /* Data structure for decision tree for recognizing
69: legitimate instructions. */
70:
71: struct decision
72: {
73: int number; /* Node number, used for labels */
74: char *position; /* String denoting position in pattern */
75: RTX_CODE code; /* Code to test for or UNKNOWN to suppress */
76: char ignore_code; /* If non-zero, need not test code */
77: char ignore_mode; /* If non-zero, need not test mode */
78: int veclen; /* Length of vector, if nonzero */
79: enum machine_mode mode; /* Machine mode of node */
80: char enforce_mode; /* If non-zero, test `mode' */
81: char retest_code, retest_mode; /* See write_tree_1 */
82: int test_elt_zero_int; /* Nonzero if should test XINT (rtl, 0) */
83: int elt_zero_int; /* Required value for XINT (rtl, 0) */
84: int test_elt_one_int; /* Nonzero if should test XINT (rtl, 1) */
85: int elt_one_int; /* Required value for XINT (rtl, 1) */
86: char *tests; /* If nonzero predicate to call */
87: int pred; /* `preds' index of predicate or -1 */
88: char *c_test; /* Additional test to perform */
89: struct decision_head success; /* Nodes to test on success */
90: int insn_code_number; /* Insn number matched, if success */
91: int num_clobbers_to_add; /* Number of CLOBBERs to be added to pattern */
92: struct decision *next; /* Node to test on failure */
93: struct decision *prev; /* Node whose failure tests us */
94: struct decision *afterward; /* Node to test on success, but failure of
95: successor nodes */
96: int opno; /* Operand number, if >= 0 */
97: int dupno; /* Number of operand to compare against */
98: int label_needed; /* Nonzero if label needed when writing tree */
99: int subroutine_number; /* Number of subroutine this node starts */
100: };
101:
102: #define SUBROUTINE_THRESHOLD 50
103:
104: static int next_subroutine_number;
105:
106: /* We can write two types of subroutines: One for insn recognition and
107: one to split insns. This defines which type is being written. */
108:
109: enum routine_type {RECOG, SPLIT};
110:
111: /* Next available node number for tree nodes. */
112:
113: static int next_number;
114:
115: /* Next number to use as an insn_code. */
116:
117: static int next_insn_code;
118:
119: /* Similar, but counts all expressions in the MD file; used for
120: error messages. */
121:
122: static int next_index;
123:
124: /* Record the highest depth we ever have so we know how many variables to
125: allocate in each subroutine we make. */
126:
127: static int max_depth;
128:
129: /* This table contains a list of the rtl codes that can possibly match a
130: predicate defined in recog.c. The function `not_both_true' uses it to
131: deduce that there are no expressions that can be matches by certain pairs
132: of tree nodes. Also, if a predicate can match only one code, we can
133: hardwire that code into the node testing the predicate. */
134:
135: static struct pred_table
136: {
137: char *name;
138: RTX_CODE codes[NUM_RTX_CODE];
139: } preds[]
140: = {{"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
141: LABEL_REF, SUBREG, REG, MEM}},
142: #ifdef PREDICATE_CODES
143: PREDICATE_CODES
144: #endif
145: {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
146: LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}},
147: {"register_operand", {SUBREG, REG}},
148: {"scratch_operand", {SCRATCH, REG}},
149: {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
150: LABEL_REF}},
151: {"const_int_operand", {CONST_INT}},
152: {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
153: {"nonimmediate_operand", {SUBREG, REG, MEM}},
154: {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
155: LABEL_REF, SUBREG, REG}},
156: {"push_operand", {MEM}},
157: {"memory_operand", {SUBREG, MEM}},
158: {"indirect_operand", {SUBREG, MEM}},
159: {"comparison_operation", {EQ, NE, LE, LT, GE, LT, LEU, LTU, GEU, GTU}},
160: {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
161: LABEL_REF, SUBREG, REG, MEM}}};
162:
163: #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
164:
165: static int try_merge_1 ();
166: static int no_same_mode ();
167: static int same_codes ();
168: static int same_modes ();
169: char *xmalloc ();
170: static struct decision *add_to_sequence ();
171: static struct decision_head merge_trees ();
172: static struct decision *try_merge_2 ();
173: static void write_subroutine ();
174: static void print_code ();
175: static void clear_codes ();
176: static void clear_modes ();
177: static void change_state ();
178: static void write_tree ();
179: static char *copystr ();
180: static char *concat ();
181: static void fatal ();
182: void fancy_abort ();
183: static void mybzero ();
184: static void mybcopy ();
185:
186: /* Construct and return a sequence of decisions
187: that will recognize INSN.
188:
189: TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
190:
191: static struct decision_head
192: make_insn_sequence (insn, type)
193: rtx insn;
194: enum routine_type type;
195: {
196: rtx x;
197: char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
198: struct decision *last;
199: struct decision_head head;
200:
201: if (XVECLEN (insn, type == RECOG) == 1)
202: x = XVECEXP (insn, type == RECOG, 0);
203: else
204: {
205: x = rtx_alloc (PARALLEL);
206: XVEC (x, 0) = XVEC (insn, type == RECOG);
207: PUT_MODE (x, VOIDmode);
208: }
209:
210: last = add_to_sequence (x, &head, "");
211:
212: if (c_test[0])
213: last->c_test = c_test;
214: last->insn_code_number = next_insn_code;
215: last->num_clobbers_to_add = 0;
216:
217: /* If this is not a DEFINE_SPLIT and X is a PARALLEL, see if it ends with a
218: group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. If so, set up
219: to recognize the pattern without these CLOBBERs. */
220:
221: if (type == RECOG && GET_CODE (x) == PARALLEL)
222: {
223: int i;
224:
225: for (i = XVECLEN (x, 0); i > 0; i--)
226: if (GET_CODE (XVECEXP (x, 0, i - 1)) != CLOBBER
227: || (GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != REG
228: && GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != MATCH_SCRATCH))
229: break;
230:
231: if (i != XVECLEN (x, 0))
232: {
233: rtx new;
234: struct decision_head clobber_head;
235:
236: if (i == 1)
237: new = XVECEXP (x, 0, 0);
238: else
239: {
240: int j;
241:
242: new = rtx_alloc (PARALLEL);
243: XVEC (new, 0) = rtvec_alloc (i);
244: for (j = i - 1; j >= 0; j--)
245: XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
246: }
247:
248: last = add_to_sequence (new, &clobber_head, "");
249:
250: if (c_test[0])
251: last->c_test = c_test;
252: last->insn_code_number = next_insn_code;
253: last->num_clobbers_to_add = XVECLEN (x, 0) - i;
254:
255: head = merge_trees (head, clobber_head);
256: }
257: }
258:
259: next_insn_code++;
260:
261: if (type == SPLIT)
262: /* Define the subroutine we will call below and emit in genemit. */
263: printf ("extern rtx gen_split_%d ();\n", last->insn_code_number);
264:
265: return head;
266: }
267:
268: /* Create a chain of nodes to verify that an rtl expression matches
269: PATTERN.
270:
271: LAST is a pointer to the listhead in the previous node in the chain (or
272: in the calling function, for the first node).
273:
274: POSITION is the string representing the current position in the insn.
275:
276: A pointer to the final node in the chain is returned. */
277:
278: static struct decision *
279: add_to_sequence (pattern, last, position)
280: rtx pattern;
281: struct decision_head *last;
282: char *position;
283: {
284: register RTX_CODE code;
285: register struct decision *new
286: = (struct decision *) xmalloc (sizeof (struct decision));
287: struct decision *this;
288: char *newpos;
289: register char *fmt;
290: register int i;
291: int depth = strlen (position);
292: int len;
293:
294: if (depth > max_depth)
295: max_depth = depth;
296:
297: new->number = next_number++;
298: new->position = copystr (position);
299: new->ignore_code = 0;
300: new->ignore_mode = 0;
301: new->enforce_mode = 1;
302: new->retest_code = new->retest_mode = 0;
303: new->veclen = 0;
304: new->test_elt_zero_int = 0;
305: new->test_elt_one_int = 0;
306: new->elt_zero_int = 0;
307: new->elt_one_int = 0;
308: new->tests = 0;
309: new->pred = -1;
310: new->c_test = 0;
311: new->success.first = new->success.last = 0;
312: new->insn_code_number = -1;
313: new->num_clobbers_to_add = 0;
314: new->next = 0;
315: new->prev = 0;
316: new->afterward = 0;
317: new->opno = -1;
318: new->dupno = -1;
319: new->label_needed = 0;
320: new->subroutine_number = 0;
321:
322: this = new;
323:
324: last->first = last->last = new;
325:
326: newpos = (char *) alloca (depth + 2);
327: strcpy (newpos, position);
328: newpos[depth + 1] = 0;
329:
330: restart:
331:
332: new->mode = GET_MODE (pattern);
333: new->code = code = GET_CODE (pattern);
334:
335: switch (code)
336: {
337: case MATCH_OPERAND:
338: case MATCH_SCRATCH:
339: case MATCH_OPERATOR:
340: case MATCH_PARALLEL:
341: new->opno = XINT (pattern, 0);
342: new->code = (code == MATCH_PARALLEL ? PARALLEL : UNKNOWN);
343: new->enforce_mode = 0;
344:
345: if (code == MATCH_SCRATCH)
346: new->tests = "scratch_operand";
347: else
348: new->tests = XSTR (pattern, 1);
349:
350: if (*new->tests == 0)
351: new->tests = 0;
352:
353: /* See if we know about this predicate and save its number. If we do,
354: and it only accepts one code, note that fact. The predicate
355: `const_int_operand' only tests for a CONST_INT, so if we do so we
356: can avoid calling it at all.
357:
358: Finally, if we know that the predicate does not allow CONST_INT, we
359: know that the only way the predicate can match is if the modes match
360: (here we use the kluge of relying on the fact that "address_operand"
361: accepts CONST_INT; otherwise, it would have to be a special case),
362: so we can test the mode (but we need not). This fact should
363: considerably simplify the generated code. */
364:
365: if (new->tests)
366: for (i = 0; i < NUM_KNOWN_PREDS; i++)
367: if (! strcmp (preds[i].name, new->tests))
368: {
369: int j;
370: int allows_const_int = 0;
371:
372: new->pred = i;
373:
374: if (preds[i].codes[1] == 0 && new->code == UNKNOWN)
375: {
376: new->code = preds[i].codes[0];
377: if (! strcmp ("const_int_operand", new->tests))
378: new->tests = 0, new->pred = -1;
379: }
380:
381: for (j = 0; j < NUM_RTX_CODE && preds[i].codes[j] != 0; j++)
382: if (preds[i].codes[j] == CONST_INT)
383: allows_const_int = 1;
384:
385: if (! allows_const_int)
386: new->enforce_mode = new->ignore_mode= 1;
387:
388: break;
389: }
390:
391: if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
392: {
393: for (i = 0; i < XVECLEN (pattern, 2); i++)
394: {
395: newpos[depth] = i + (code == MATCH_OPERATOR ? '0': 'a');
396: new = add_to_sequence (XVECEXP (pattern, 2, i),
397: &new->success, newpos);
398: }
399:
400: this->success.first->enforce_mode = 0;
401: }
402:
403: return new;
404:
405: case MATCH_OP_DUP:
406: new->opno = XINT (pattern, 0);
407: new->dupno = XINT (pattern, 0);
408: new->code = UNKNOWN;
409: new->tests = 0;
410: for (i = 0; i < XVECLEN (pattern, 1); i++)
411: {
412: newpos[depth] = i + '0';
413: new = add_to_sequence (XVECEXP (pattern, 1, i),
414: &new->success, newpos);
415: }
416: this->success.first->enforce_mode = 0;
417: return new;
418:
419: case MATCH_DUP:
420: new->dupno = XINT (pattern, 0);
421: new->code = UNKNOWN;
422: new->enforce_mode = 0;
423: return new;
424:
425: case ADDRESS:
426: pattern = XEXP (pattern, 0);
427: goto restart;
428:
429: case SET:
430: newpos[depth] = '0';
431: new = add_to_sequence (SET_DEST (pattern), &new->success, newpos);
432: this->success.first->enforce_mode = 1;
433: newpos[depth] = '1';
434: new = add_to_sequence (SET_SRC (pattern), &new->success, newpos);
435:
436: /* If set are setting CC0 from anything other than a COMPARE, we
437: must enforce the mode so that we do not produce ambiguous insns. */
438: if (GET_CODE (SET_DEST (pattern)) == CC0
439: && GET_CODE (SET_SRC (pattern)) != COMPARE)
440: this->success.first->enforce_mode = 1;
441: return new;
442:
443: case SIGN_EXTEND:
444: case ZERO_EXTEND:
445: case STRICT_LOW_PART:
446: newpos[depth] = '0';
447: new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
448: this->success.first->enforce_mode = 1;
449: return new;
450:
451: case SUBREG:
452: this->test_elt_one_int = 1;
453: this->elt_one_int = XINT (pattern, 1);
454: newpos[depth] = '0';
455: new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
456: this->success.first->enforce_mode = 1;
457: return new;
458:
459: case ZERO_EXTRACT:
460: case SIGN_EXTRACT:
461: newpos[depth] = '0';
462: new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
463: this->success.first->enforce_mode = 1;
464: newpos[depth] = '1';
465: new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos);
466: newpos[depth] = '2';
467: new = add_to_sequence (XEXP (pattern, 2), &new->success, newpos);
468: return new;
469:
470: case EQ: case NE: case LE: case LT: case GE: case GT:
471: case LEU: case LTU: case GEU: case GTU:
472: /* If the first operand is (cc0), we don't have to do anything
473: special. */
474: if (GET_CODE (XEXP (pattern, 0)) == CC0)
475: break;
476:
477: /* ... fall through ... */
478:
479: case COMPARE:
480: /* Enforce the mode on the first operand to avoid ambiguous insns. */
481: newpos[depth] = '0';
482: new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
483: this->success.first->enforce_mode = 1;
484: newpos[depth] = '1';
485: new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos);
486: return new;
487: }
488:
489: fmt = GET_RTX_FORMAT (code);
490: len = GET_RTX_LENGTH (code);
491: for (i = 0; i < len; i++)
492: {
493: newpos[depth] = '0' + i;
494: if (fmt[i] == 'e' || fmt[i] == 'u')
495: new = add_to_sequence (XEXP (pattern, i), &new->success, newpos);
496: else if (fmt[i] == 'i' && i == 0)
497: {
498: this->test_elt_zero_int = 1;
499: this->elt_zero_int = XINT (pattern, i);
500: }
501: else if (fmt[i] == 'i' && i == 1)
502: {
503: this->test_elt_one_int = 1;
504: this->elt_one_int = XINT (pattern, i);
505: }
506: else if (fmt[i] == 'E')
507: {
508: register int j;
509: /* We do not handle a vector appearing as other than
510: the first item, just because nothing uses them
511: and by handling only the special case
512: we can use one element in newpos for either
513: the item number of a subexpression
514: or the element number in a vector. */
515: if (i != 0)
516: abort ();
517: this->veclen = XVECLEN (pattern, i);
518: for (j = 0; j < XVECLEN (pattern, i); j++)
519: {
520: newpos[depth] = 'a' + j;
521: new = add_to_sequence (XVECEXP (pattern, i, j),
522: &new->success, newpos);
523: }
524: }
525: else if (fmt[i] != '0')
526: abort ();
527: }
528: return new;
529: }
530:
531: /* Return 1 if we can prove that there is no RTL that can match both
532: D1 and D2. Otherwise, return 0 (it may be that there is an RTL that
533: can match both or just that we couldn't prove there wasn't such an RTL).
534:
535: TOPLEVEL is non-zero if we are to only look at the top level and not
536: recursively descend. */
537:
538: static int
539: not_both_true (d1, d2, toplevel)
540: struct decision *d1, *d2;
541: int toplevel;
542: {
543: struct decision *p1, *p2;
544:
545: /* If they are both to test modes and the modes are different, they aren't
546: both true. Similarly for codes, integer elements, and vector lengths. */
547:
548: if ((d1->enforce_mode && d2->enforce_mode
549: && d1->mode != VOIDmode && d2->mode != VOIDmode && d1->mode != d2->mode)
550: || (d1->code != UNKNOWN && d2->code != UNKNOWN && d1->code != d2->code)
551: || (d1->test_elt_zero_int && d2->test_elt_zero_int
552: && d1->elt_zero_int != d2->elt_zero_int)
553: || (d1->test_elt_one_int && d2->test_elt_one_int
554: && d1->elt_one_int != d2->elt_one_int)
555: || (d1->veclen && d2->veclen && d1->veclen != d2->veclen))
556: return 1;
557:
558: /* If either is a wild-card MATCH_OPERAND without a predicate, it can match
559: absolutely anything, so we can't say that no intersection is possible.
560: This case is detected by having a zero TESTS field with a code of
561: UNKNOWN. */
562:
563: if ((d1->tests == 0 && d1->code == UNKNOWN)
564: || (d2->tests == 0 && d2->code == UNKNOWN))
565: return 0;
566:
567: /* If either has a predicate that we know something about, set things up so
568: that D1 is the one that always has a known predicate. Then see if they
569: have any codes in common. */
570:
571: if (d1->pred >= 0 || d2->pred >= 0)
572: {
573: int i, j;
574:
575: if (d2->pred >= 0)
576: p1 = d1, d1 = d2, d2 = p1;
577:
578: /* If D2 tests an explicit code, see if it is in the list of valid codes
579: for D1's predicate. */
580: if (d2->code != UNKNOWN)
581: {
582: for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i]; i++)
583: if (preds[d1->pred].codes[i] == d2->code)
584: break;
585:
586: if (preds[d1->pred].codes[i] == 0)
587: return 1;
588: }
589:
590: /* Otherwise see if the predicates have any codes in common. */
591:
592: else if (d2->pred >= 0)
593: {
594: for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i]; i++)
595: {
596: for (j = 0; j < NUM_RTX_CODE; j++)
597: if (preds[d2->pred].codes[j] == 0
598: || preds[d2->pred].codes[j] == preds[d1->pred].codes[i])
599: break;
600:
601: if (preds[d2->pred].codes[j] != 0)
602: break;
603: }
604:
605: if (preds[d1->pred].codes[i] == 0)
606: return 1;
607: }
608: }
609:
610: /* If we got here, we can't prove that D1 and D2 cannot both be true.
611: If we are only to check the top level, return 0. Otherwise, see if
612: we can prove that all choices in both successors are mutually
613: exclusive. If either does not have any successors, we can't prove
614: they can't both be true. */
615:
616: if (toplevel || d1->success.first == 0 || d2->success.first == 0)
617: return 0;
618:
619: for (p1 = d1->success.first; p1; p1 = p1->next)
620: for (p2 = d2->success.first; p2; p2 = p2->next)
621: if (! not_both_true (p1, p2, 0))
622: return 0;
623:
624: return 1;
625: }
626:
627: /* Assuming that we can reorder all the alternatives at a specific point in
628: the tree (see discussion in merge_trees), we would prefer an ordering of
629: nodes where groups of consecutive nodes test the same mode and, within each
630: mode, groups of nodes test the same code. With this order, we can
631: construct nested switch statements, the inner one to test the code and
632: the outer one to test the mode.
633:
634: We would like to list nodes testing for specific codes before those
635: that test predicates to avoid unnecessary function calls. Similarly,
1.1.1.2 ! root 636: tests for specific modes should precede nodes that allow any mode.
1.1 root 637:
638: This function returns the merit (with 0 being the best) of inserting
639: a test involving the specified MODE and CODE after node P. If P is
640: zero, we are to determine the merit of inserting the test at the front
641: of the list. */
642:
643: static int
644: position_merit (p, mode, code)
645: struct decision *p;
646: enum machine_mode mode;
647: RTX_CODE code;
648: {
649: enum machine_mode p_mode;
650:
651: /* The only time the front of the list is anything other than the worst
652: position is if we are testing a mode that isn't VOIDmode. */
653: if (p == 0)
654: return mode == VOIDmode ? 3 : 2;
655:
656: p_mode = p->enforce_mode ? p->mode : VOIDmode;
657:
658: /* The best case is if the codes and modes both match. */
659: if (p_mode == mode && p->code== code)
660: return 0;
661:
662: /* If the codes don't match, the next best case is if the modes match.
663: In that case, the best position for this node depends on whether
664: we are testing for a specific code or not. If we are, the best place
665: is after some other test for an explicit code and our mode or after
666: the last test in the previous mode if every test in our mode is for
667: an unknown code.
668:
669: If we are testing for UNKNOWN, then the next best case is at the end of
670: our mode. */
671:
672: if ((code != UNKNOWN
673: && ((p_mode == mode && p->code != UNKNOWN)
674: || (p_mode != mode && p->next
675: && (p->next->enforce_mode ? p->next->mode : VOIDmode) == mode
676: && (p->next->code == UNKNOWN))))
677: || (code == UNKNOWN && p_mode == mode
678: && (p->next == 0
679: || (p->next->enforce_mode ? p->next->mode : VOIDmode) != mode)))
680: return 1;
681:
682: /* The third best case occurs when nothing is testing MODE. If MODE
683: is not VOIDmode, then the third best case is after something of any
684: mode that is not VOIDmode. If we are testing VOIDmode, the third best
685: place is the end of the list. */
686:
687: if (p_mode != mode
688: && ((mode != VOIDmode && p_mode != VOIDmode)
689: || (mode == VOIDmode && p->next == 0)))
690: return 2;
691:
692: /* Otherwise, we have the worst case. */
693: return 3;
694: }
695:
696: /* Merge two decision tree listheads OLDH and ADDH,
697: modifying OLDH destructively, and return the merged tree. */
698:
699: static struct decision_head
700: merge_trees (oldh, addh)
701: register struct decision_head oldh, addh;
702: {
703: struct decision *add, *next;
704:
705: if (oldh.first == 0)
706: return addh;
707:
708: if (addh.first == 0)
709: return oldh;
710:
711: /* If we are adding things at different positions, something is wrong. */
712: if (strcmp (oldh.first->position, addh.first->position))
713: abort ();
714:
715: for (add = addh.first; add; add = next)
716: {
717: enum machine_mode add_mode = add->enforce_mode ? add->mode : VOIDmode;
718: struct decision *best_position = 0;
719: int best_merit = 4;
720: struct decision *old;
721:
722: next = add->next;
723:
724: /* The semantics of pattern matching state that the tests are done in
725: the order given in the MD file so that if an insn matches two
726: patterns, the first one will be used. However, in practice, most,
727: if not all, patterns are unambiguous so that their order is
728: independent. In that case, we can merge identical tests and
729: group all similar modes and codes together.
730:
731: Scan starting from the end of OLDH until we reach a point
732: where we reach the head of the list or where we pass a pattern
733: that could also be true if NEW is true. If we find an identical
734: pattern, we can merge them. Also, record the last node that tests
735: the same code and mode and the last one that tests just the same mode.
736:
737: If we have no match, place NEW after the closest match we found. */
738:
739: for (old = oldh.last; old; old = old->prev)
740: {
741: int our_merit;
742:
743: /* If we don't have anything to test except an additional test,
744: do not consider the two nodes equal. If we did, the test below
745: would cause an infinite recursion. */
746: if (old->tests == 0 && old->test_elt_zero_int == 0
747: && old->test_elt_one_int == 0 && old->veclen == 0
748: && old->dupno == -1 && old->mode == VOIDmode
749: && old->code == UNKNOWN
750: && (old->c_test != 0 || add->c_test != 0))
751: ;
752:
753: else if ((old->tests == add->tests
754: || (old->pred >= 0 && old->pred == add->pred)
755: || (old->tests && add->tests
756: && !strcmp (old->tests, add->tests)))
757: && old->test_elt_zero_int == add->test_elt_zero_int
758: && old->elt_zero_int == add->elt_zero_int
759: && old->test_elt_one_int == add->test_elt_one_int
760: && old->elt_one_int == add->elt_one_int
761: && old->veclen == add->veclen
762: && old->dupno == add->dupno
763: && old->opno == add->opno
764: && old->code == add->code
765: && old->enforce_mode == add->enforce_mode
766: && old->mode == add->mode)
767: {
768: /* If the additional test is not the same, split both nodes
769: into nodes that just contain all things tested before the
770: additional test and nodes that contain the additional test
771: and actions when it is true. This optimization is important
772: because of the case where we have almost identical patterns
773: with different tests on target flags. */
774:
775: if (old->c_test != add->c_test
776: && ! (old->c_test && add->c_test
777: && !strcmp (old->c_test, add->c_test)))
778: {
779: if (old->insn_code_number >= 0 || old->opno >= 0)
780: {
781: struct decision *split
782: = (struct decision *) xmalloc (sizeof (struct decision));
783:
784: mybcopy (old, split, sizeof (struct decision));
785:
786: old->success.first = old->success.last = split;
787: old->c_test = 0;
788: old->opno = -1;
789: old->insn_code_number = -1;
790: old->num_clobbers_to_add = 0;
791:
792: split->number = next_number++;
793: split->next = split->prev = 0;
794: split->mode = VOIDmode;
795: split->code = UNKNOWN;
796: split->veclen = 0;
797: split->test_elt_zero_int = 0;
798: split->test_elt_one_int = 0;
799: split->tests = 0;
800: split->pred = -1;
801: }
802:
803: if (add->insn_code_number >= 0 || add->opno >= 0)
804: {
805: struct decision *split
806: = (struct decision *) xmalloc (sizeof (struct decision));
807:
808: mybcopy (add, split, sizeof (struct decision));
809:
810: add->success.first = add->success.last = split;
811: add->c_test = 0;
812: add->opno = -1;
813: add->insn_code_number = -1;
814: add->num_clobbers_to_add = 0;
815:
816: split->number = next_number++;
817: split->next = split->prev = 0;
818: split->mode = VOIDmode;
819: split->code = UNKNOWN;
820: split->veclen = 0;
821: split->test_elt_zero_int = 0;
822: split->test_elt_one_int = 0;
823: split->tests = 0;
824: split->pred = -1;
825: }
826: }
827:
828: if (old->insn_code_number >= 0 && add->insn_code_number >= 0)
829: {
830: /* If one node is for a normal insn and the second is
831: for the base insn with clobbers stripped off, the
832: second node should be ignored. */
833:
834: if (old->num_clobbers_to_add == 0
835: && add->num_clobbers_to_add > 0)
836: /* Nothing to do here. */
837: ;
838: else if (old->num_clobbers_to_add > 0
839: && add->num_clobbers_to_add == 0)
840: {
841: /* In this case, replace OLD with ADD. */
842: old->insn_code_number = add->insn_code_number;
843: old->num_clobbers_to_add = 0;
844: }
845: else
846: fatal ("Two actions at one point in tree");
847: }
848:
849: if (old->insn_code_number == -1)
850: old->insn_code_number = add->insn_code_number;
851: old->success = merge_trees (old->success, add->success);
852: add = 0;
853: break;
854: }
855:
856: /* Unless we have already found the best possible insert point,
857: see if this position is better. If so, record it. */
858:
859: if (best_merit != 0
860: && ((our_merit = position_merit (old, add_mode, add->code))
861: < best_merit))
862: best_merit = our_merit, best_position = old;
863:
864: if (! not_both_true (old, add, 0))
865: break;
866: }
867:
868: /* If ADD was duplicate, we are done. */
869: if (add == 0)
870: continue;
871:
872: /* Otherwise, find the best place to insert ADD. Normally this is
873: BEST_POSITION. However, if we went all the way to the top of
874: the list, it might be better to insert at the top. */
875:
876: if (best_position == 0)
877: abort ();
878:
879: if (old == 0 && position_merit (0, add_mode, add->code) < best_merit)
880: {
881: add->prev = 0;
882: add->next = oldh.first;
883: oldh.first->prev = add;
884: oldh.first = add;
885: }
886:
887: else
888: {
889: add->prev = best_position;
890: add->next = best_position->next;
891: best_position->next = add;
892: if (best_position == oldh.last)
893: oldh.last = add;
894: else
895: add->next->prev = add;
896: }
897: }
898:
899: return oldh;
900: }
901:
902: /* Count the number of subnodes of HEAD. If the number is high enough,
903: make the first node in HEAD start a separate subroutine in the C code
904: that is generated.
905:
906: TYPE gives the type of routine we are writing.
907:
908: INITIAL is non-zero if this is the highest-level node. We never write
909: it out here. */
910:
911: static int
912: break_out_subroutines (head, type, initial)
913: struct decision_head head;
914: enum routine_type type;
915: int initial;
916: {
917: int size = 0;
918: struct decision *node, *sub;
919:
920: for (sub = head.first; sub; sub = sub->next)
921: size += 1 + break_out_subroutines (sub->success, type, 0);
922:
923: if (size > SUBROUTINE_THRESHOLD && ! initial)
924: {
925: head.first->subroutine_number = ++next_subroutine_number;
926: write_subroutine (head.first, type);
927: size = 1;
928: }
929: return size;
930: }
931:
932: /* Write out a subroutine of type TYPE to do comparisons starting at node
933: TREE. */
934:
935: static void
936: write_subroutine (tree, type)
937: struct decision *tree;
938: enum routine_type type;
939: {
940: int i;
941:
942: if (type == SPLIT)
943: printf ("rtx\nsplit");
944: else
945: printf ("int\nrecog");
946:
947: if (tree != 0 && tree->subroutine_number > 0)
948: printf ("_%d", tree->subroutine_number);
949: else if (type == SPLIT)
950: printf ("_insns");
951:
952: printf (" (x0, insn");
953: if (type == RECOG)
954: printf (", pnum_clobbers");
955:
956: printf (")\n");
957: printf (" register rtx x0;\n rtx insn;\n");
958: if (type == RECOG)
959: printf (" int *pnum_clobbers;\n");
960:
961: printf ("{\n");
962: printf (" register rtx *ro = &recog_operand[0];\n");
963:
964: printf (" register rtx ");
965: for (i = 1; i < max_depth; i++)
966: printf ("x%d, ", i);
967:
968: printf ("x%d;\n", max_depth);
969: printf (" %s tem;\n", type == SPLIT ? "rtx" : "int");
970: write_tree (tree, "", 0, 1, type);
971: printf (" ret0: return %d;\n}\n\n", type == SPLIT ? 0 : -1);
972: }
973:
974: /* This table is used to indent the recog_* functions when we are inside
975: conditions or switch statements. We only support small indentations
976: and always indent at least two spaces. */
977:
978: static char *indents[]
979: = {" ", " ", " ", " ", " ", " ", " ", " ",
980: "\t", "\t ", "\t ", "\t ", "\t ", "\t ", "\t ",
981: "\t\t", "\t\t ", "\t\t ", "\t\t ", "\t\t ", "\t\t "};
982:
983: /* Write out C code to perform the decisions in TREE for a subroutine of
984: type TYPE. If all of the choices fail, branch to node AFTERWARD, if
985: non-zero, otherwise return. PREVPOS is the position of the node that
986: branched to this test.
987:
988: When we merged all alternatives, we tried to set up a convenient order.
989: Specifically, tests involving the same mode are all grouped together,
990: followed by a group that does not contain a mode test. Within each group
991: of the same mode, we also group tests with the same code, followed by a
992: group that does not test a code.
993:
1.1.1.2 ! root 994: Occasionally, we cannot arbitrarily reorder the tests so that multiple
1.1 root 995: sequence of groups as described above are present.
996:
997: We generate two nested switch statements, the outer statement for
998: testing modes, and the inner switch for testing RTX codes. It is
999: not worth optimizing cases when only a small number of modes or
1000: codes is tested, since the compiler can do that when compiling the
1001: resulting function. We do check for when every test is the same mode
1002: or code. */
1003:
1004: void
1005: write_tree_1 (tree, prevpos, afterward, type)
1006: struct decision *tree;
1007: char *prevpos;
1008: struct decision *afterward;
1009: enum routine_type type;
1010: {
1011: register struct decision *p, *p1;
1012: register int depth = tree ? strlen (tree->position) : 0;
1013: enum machine_mode switch_mode = VOIDmode;
1014: RTX_CODE switch_code = UNKNOWN;
1015: int uncond = 0;
1016: char modemap[NUM_MACHINE_MODES];
1017: char codemap[NUM_RTX_CODE];
1018: int indent = 2;
1019: int i;
1020:
1021: /* One tricky area is what is the exact state when we branch to a
1022: node's label. There are two cases where we branch: when looking at
1023: successors to a node, or when a set of tests fails.
1024:
1025: In the former case, we are always branching to the first node in a
1026: decision list and we want all required tests to be performed. We
1027: put the labels for such nodes in front of any switch or test statements.
1028: These branches are done without updating the position to that of the
1029: target node.
1030:
1031: In the latter case, we are branching to a node that is not the first
1032: node in a decision list. We have already checked that it is possible
1033: for both the node we originally tested at this level and the node we
1034: are branching to to be both match some pattern. That means that they
1035: usually will be testing the same mode and code. So it is normally safe
1036: for such labels to be inside switch statements, since the tests done
1037: by virtue of arriving at that label will usually already have been
1038: done. The exception is a branch from a node that does not test a
1039: mode or code to one that does. In such cases, we set the `retest_mode'
1040: or `retest_code' flags. That will ensure that we start a new switch
1041: at that position and put the label before the switch.
1042:
1043: The branches in the latter case must set the position to that of the
1044: target node. */
1045:
1046:
1047: printf ("\n");
1048: if (tree && tree->subroutine_number == 0)
1049: {
1050: printf (" L%d:\n", tree->number);
1051: tree->label_needed = 0;
1052: }
1053:
1054: if (tree)
1055: {
1056: change_state (prevpos, tree->position, 2);
1057: prevpos = tree->position;
1058: }
1059:
1060: for (p = tree; p; p = p->next)
1061: {
1062: enum machine_mode mode = p->enforce_mode ? p->mode : VOIDmode;
1063: int need_bracket;
1064: int wrote_bracket = 0;
1065: int inner_indent;
1066:
1067: if (p->success.first == 0 && p->insn_code_number < 0)
1068: abort ();
1069:
1070: /* Find the next alternative to p that might be true when p is true.
1071: Test that one next if p's successors fail. */
1072:
1073: for (p1 = p->next; p1 && not_both_true (p, p1, 1); p1 = p1->next)
1074: ;
1075: p->afterward = p1;
1076:
1077: if (p1)
1078: {
1079: if (mode == VOIDmode && p1->enforce_mode && p1->mode != VOIDmode)
1080: p1->retest_mode = 1;
1081: if (p->code == UNKNOWN && p1->code != UNKNOWN)
1082: p1->retest_code = 1;
1083: p1->label_needed = 1;
1084: }
1085:
1086: /* If we have a different code or mode than the last node and
1087: are in a switch on codes, we must either end the switch or
1088: go to another case. We must also end the switch if this
1089: node needs a label and to retest either the mode or code. */
1090:
1091: if (switch_code != UNKNOWN
1092: && (switch_code != p->code || switch_mode != mode
1093: || (p->label_needed && (p->retest_mode || p->retest_code))))
1094: {
1095: enum rtx_code code = p->code;
1096:
1097: /* If P is testing a predicate that we know about and we haven't
1098: seen any of the codes that are valid for the predicate, we
1099: can write a series of "case" statement, one for each possible
1100: code. Since we are already in a switch, these redundant tests
1101: are very cheap and will reduce the number of predicate called. */
1102:
1103: if (p->pred >= 0)
1104: {
1105: for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i]; i++)
1106: if (codemap[(int) preds[p->pred].codes[i]])
1107: break;
1108:
1109: if (preds[p->pred].codes[i] == 0)
1110: code = MATCH_OPERAND;
1111: }
1112:
1113: if (code == UNKNOWN || codemap[(int) code]
1114: || switch_mode != mode
1115: || (p->label_needed && (p->retest_mode || p->retest_code)))
1116: {
1117: printf ("%s}\n", indents[indent - 2]);
1118: switch_code = UNKNOWN;
1119: indent -= 4;
1120: }
1121: else
1122: {
1123: if (! uncond)
1124: printf ("%sbreak;\n", indents[indent]);
1125:
1126: if (code == MATCH_OPERAND)
1127: {
1128: for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i]; i++)
1129: {
1130: printf ("%scase ", indents[indent - 2]);
1131: print_code (preds[p->pred].codes[i]);
1132: printf (":\n");
1133: codemap[(int) preds[p->pred].codes[i]] = 1;
1134: }
1135: }
1136: else
1137: {
1138: printf ("%scase ", indents[indent - 2]);
1139: print_code (code);
1140: printf (":\n");
1141: codemap[(int) p->code] = 1;
1142: }
1143:
1144: switch_code = code;
1145: }
1146:
1147: uncond = 0;
1148: }
1149:
1150: /* If we were previously in a switch on modes and now have a different
1151: mode, end at least the case, and maybe end the switch if we are
1152: not testing a mode or testing a mode whose case we already saw. */
1153:
1154: if (switch_mode != VOIDmode
1155: && (switch_mode != mode || (p->label_needed && p->retest_mode)))
1156: {
1157: if (mode == VOIDmode || modemap[(int) mode]
1158: || (p->label_needed && p->retest_mode))
1159: {
1160: printf ("%s}\n", indents[indent - 2]);
1161: switch_mode = VOIDmode;
1162: indent -= 4;
1163: }
1164: else
1165: {
1166: if (! uncond)
1167: printf (" break;\n");
1168: printf (" case %smode:\n", GET_MODE_NAME (mode));
1169: switch_mode = mode;
1170: modemap[(int) mode] = 1;
1171: }
1172:
1173: uncond = 0;
1174: }
1175:
1176: /* If we are about to write dead code, something went wrong. */
1177: if (! p->label_needed && uncond)
1178: abort ();
1179:
1180: /* If we need a label and we will want to retest the mode or code at
1181: that label, write the label now. We have already ensured that
1182: things will be valid for the test. */
1183:
1184: if (p->label_needed && (p->retest_mode || p->retest_code))
1185: {
1186: printf ("%sL%d:\n", indents[indent - 2], p->number);
1187: p->label_needed = 0;
1188: }
1189:
1190: uncond = 0;
1191:
1192: /* If we are not in any switches, see if we can shortcut things
1193: by checking for identical modes and codes. */
1194:
1195: if (switch_mode == VOIDmode && switch_code == UNKNOWN)
1196: {
1197: /* If p and its alternatives all want the same mode,
1198: reject all others at once, first, then ignore the mode. */
1199:
1200: if (mode != VOIDmode && p->next && same_modes (p, mode))
1201: {
1202: printf (" if (GET_MODE (x%d) != %smode)\n",
1203: depth, GET_MODE_NAME (p->mode));
1204: if (afterward)
1205: {
1206: printf (" {\n");
1207: change_state (p->position, afterward->position, 6);
1208: printf (" goto L%d;\n }\n", afterward->number);
1209: }
1210: else
1211: printf (" goto ret0;\n");
1212: clear_modes (p);
1213: mode = VOIDmode;
1214: }
1215:
1216: /* If p and its alternatives all want the same code,
1217: reject all others at once, first, then ignore the code. */
1218:
1219: if (p->code != UNKNOWN && p->next && same_codes (p, p->code))
1220: {
1221: printf (" if (GET_CODE (x%d) != ", depth);
1222: print_code (p->code);
1223: printf (")\n");
1224: if (afterward)
1225: {
1226: printf (" {\n");
1227: change_state (p->position, afterward->position, indent + 4);
1228: printf (" goto L%d;\n }\n", afterward->number);
1229: }
1230: else
1231: printf (" goto ret0;\n");
1232: clear_codes (p);
1233: }
1234: }
1235:
1236: /* If we are not in a mode switch and we are testing for a specific
1237: mode, start a mode switch unless we have just one node or the next
1238: node is not testing a mode (we have already tested for the case of
1239: more than one mode, but all of the same mode). */
1240:
1241: if (switch_mode == VOIDmode && mode != VOIDmode && p->next != 0
1242: && p->next->enforce_mode && p->next->mode != VOIDmode)
1243: {
1244: mybzero (modemap, sizeof modemap);
1245: printf ("%sswitch (GET_MODE (x%d))\n", indents[indent], depth);
1246: printf ("%s{\n", indents[indent + 2]);
1247: indent += 4;
1248: printf ("%scase %smode:\n", indents[indent - 2],
1249: GET_MODE_NAME (mode));
1250: modemap[(int) mode] = 1;
1251: switch_mode = mode;
1252: }
1253:
1254: /* Similarly for testing codes. */
1255:
1256: if (switch_code == UNKNOWN && p->code != UNKNOWN && ! p->ignore_code
1257: && p->next != 0 && p->next->code != UNKNOWN)
1258: {
1259: mybzero (codemap, sizeof codemap);
1260: printf ("%sswitch (GET_CODE (x%d))\n", indents[indent], depth);
1261: printf ("%s{\n", indents[indent + 2]);
1262: indent += 4;
1263: printf ("%scase ", indents[indent - 2]);
1264: print_code (p->code);
1265: printf (":\n");
1266: codemap[(int) p->code] = 1;
1267: switch_code = p->code;
1268: }
1269:
1270: /* Now that most mode and code tests have been done, we can write out
1271: a label for an inner node, if we haven't already. */
1272: if (p->label_needed)
1273: printf ("%sL%d:\n", indents[indent - 2], p->number);
1274:
1275: inner_indent = indent;
1276:
1277: /* The only way we can have to do a mode or code test here is if
1278: this node needs such a test but is the only node to be tested.
1279: In that case, we won't have started a switch. Note that this is
1280: the only way the switch and test modes can disagree. */
1281:
1282: if ((mode != switch_mode && ! p->ignore_mode)
1283: || (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code)
1284: || p->test_elt_zero_int || p->test_elt_one_int || p->veclen
1285: || p->dupno >= 0 || p->tests || p->num_clobbers_to_add)
1286: {
1287: printf ("%sif (", indents[indent]);
1288:
1289: if (mode != switch_mode && ! p->ignore_mode)
1290: printf ("GET_MODE (x%d) == %smode && ",
1291: depth, GET_MODE_NAME (mode));
1292: if (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code)
1293: {
1294: printf ("GET_CODE (x%d) == ", depth);
1295: print_code (p->code);
1296: printf (" && ");
1297: }
1298:
1299: if (p->test_elt_zero_int)
1300: printf ("XINT (x%d, 0) == %d && ", depth, p->elt_zero_int);
1301: if (p->test_elt_one_int)
1302: printf ("XINT (x%d, 1) == %d && ", depth, p->elt_one_int);
1303: if (p->veclen)
1304: printf ("XVECLEN (x%d, 0) == %d && ", depth, p->veclen);
1305: if (p->dupno >= 0)
1306: printf ("rtx_equal_p (x%d, ro[%d]) && ", depth, p->dupno);
1307: if (p->num_clobbers_to_add)
1308: printf ("pnum_clobbers != 0 && ");
1309: if (p->tests)
1310: printf ("%s (x%d, %smode)", p->tests, depth,
1311: GET_MODE_NAME (p->mode));
1312: else
1313: printf ("1");
1314:
1315: printf (")\n");
1316: inner_indent += 2;
1317: }
1318: else
1319: uncond = 1;
1320:
1321: need_bracket = ! uncond;
1322:
1323: if (p->opno >= 0)
1324: {
1325: if (need_bracket)
1326: {
1327: printf ("%s{\n", indents[inner_indent]);
1328: inner_indent += 2;
1329: wrote_bracket = 1;
1330: need_bracket = 0;
1331: }
1332:
1333: printf ("%sro[%d] = x%d;\n", indents[inner_indent], p->opno, depth);
1334: }
1335:
1336: if (p->c_test)
1337: {
1338: printf ("%sif (%s)\n", indents[inner_indent], p->c_test);
1339: inner_indent += 2;
1340: uncond = 0;
1341: need_bracket = 1;
1342: }
1343:
1344: if (p->insn_code_number >= 0)
1345: {
1346: if (type == SPLIT)
1347: printf ("%sreturn gen_split_%d (operands);\n",
1348: indents[inner_indent], p->insn_code_number);
1349: else
1350: {
1351: if (p->num_clobbers_to_add)
1352: {
1353: if (need_bracket)
1354: {
1355: printf ("%s{\n", indents[inner_indent]);
1356: inner_indent += 2;
1357: }
1358:
1359: printf ("%s*pnum_clobbers = %d;\n",
1360: indents[inner_indent], p->num_clobbers_to_add);
1361: printf ("%sreturn %d;\n",
1362: indents[inner_indent], p->insn_code_number);
1363:
1364: if (need_bracket)
1365: {
1366: inner_indent -= 2;
1367: printf ("%s}\n", indents[inner_indent]);
1368: }
1369: }
1370: else
1371: printf ("%sreturn %d;\n",
1372: indents[inner_indent], p->insn_code_number);
1373: }
1374: }
1375: else
1376: printf ("%sgoto L%d;\n", indents[inner_indent],
1377: p->success.first->number);
1378:
1379: if (wrote_bracket)
1380: printf ("%s}\n", indents[inner_indent - 2]);
1381: }
1382:
1383: /* We have now tested all alternatives. End any switches we have open
1384: and branch to the alternative node unless we know that we can't fall
1385: through to the branch. */
1386:
1387: if (switch_code != UNKNOWN)
1388: {
1389: printf ("%s}\n", indents[indent - 2]);
1390: indent -= 4;
1391: uncond = 0;
1392: }
1393:
1394: if (switch_mode != VOIDmode)
1395: {
1396: printf ("%s}\n", indents[indent - 2]);
1397: indent -= 4;
1398: uncond = 0;
1399: }
1400:
1401: if (indent != 2)
1402: abort ();
1403:
1404: if (uncond)
1405: return;
1406:
1407: if (afterward)
1408: {
1409: change_state (prevpos, afterward->position, 2);
1410: printf (" goto L%d;\n", afterward->number);
1411: }
1412: else
1413: printf (" goto ret0;\n");
1414: }
1415:
1416: static void
1417: print_code (code)
1418: RTX_CODE code;
1419: {
1420: register char *p1;
1421: for (p1 = GET_RTX_NAME (code); *p1; p1++)
1422: {
1423: if (*p1 >= 'a' && *p1 <= 'z')
1424: putchar (*p1 + 'A' - 'a');
1425: else
1426: putchar (*p1);
1427: }
1428: }
1429:
1430: static int
1431: same_codes (p, code)
1432: register struct decision *p;
1433: register RTX_CODE code;
1434: {
1435: for (; p; p = p->next)
1436: if (p->code != code)
1437: return 0;
1438:
1439: return 1;
1440: }
1441:
1442: static void
1443: clear_codes (p)
1444: register struct decision *p;
1445: {
1446: for (; p; p = p->next)
1447: p->ignore_code = 1;
1448: }
1449:
1450: static int
1451: same_modes (p, mode)
1452: register struct decision *p;
1453: register enum machine_mode mode;
1454: {
1455: for (; p; p = p->next)
1456: if ((p->enforce_mode ? p->mode : VOIDmode) != mode)
1457: return 0;
1458:
1459: return 1;
1460: }
1461:
1462: static void
1463: clear_modes (p)
1464: register struct decision *p;
1465: {
1466: for (; p; p = p->next)
1467: p->enforce_mode = 0;
1468: }
1469:
1470: /* Write out the decision tree starting at TREE for a subroutine of type TYPE.
1471:
1472: PREVPOS is the position at the node that branched to this node.
1473:
1474: INITIAL is nonzero if this is the first node we are writing in a subroutine.
1475:
1476: If all nodes are false, branch to the node AFTERWARD. */
1477:
1478: static void
1479: write_tree (tree, prevpos, afterward, initial, type)
1480: struct decision *tree;
1481: char *prevpos;
1482: struct decision *afterward;
1483: int initial;
1484: enum routine_type type;
1485: {
1486: register struct decision *p;
1487: char *name_prefix = (type == SPLIT ? "split" : "recog");
1488: char *call_suffix = (type == SPLIT ? "" : ", pnum_clobbers");
1489:
1490: if (! initial && tree->subroutine_number > 0)
1491: {
1492: printf (" L%d:\n", tree->number);
1493:
1494: if (afterward)
1495: {
1496: printf (" tem = %s_%d (x0, insn%s);\n",
1497: name_prefix, tree->subroutine_number, call_suffix);
1498: printf (" if (tem >= 0) return tem;\n");
1499: change_state (tree->position, afterward->position, 2);
1500: printf (" goto L%d;\n", afterward->number);
1501: }
1502: else
1503: printf (" return %s_%d (x0, insn%s);\n",
1504: name_prefix, tree->subroutine_number, call_suffix);
1505: return;
1506: }
1507:
1508: write_tree_1 (tree, prevpos, afterward, type);
1509:
1510: for (p = tree; p; p = p->next)
1511: if (p->success.first)
1512: write_tree (p->success.first, p->position,
1513: p->afterward ? p->afterward : afterward, 0, type);
1514: }
1515:
1516:
1517: /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1518: actions are necessary to move to NEWPOS.
1519:
1520: INDENT says how many blanks to place at the front of lines. */
1521:
1522: static void
1523: change_state (oldpos, newpos, indent)
1524: char *oldpos;
1525: char *newpos;
1526: int indent;
1527: {
1528: int odepth = strlen (oldpos);
1529: int depth = odepth;
1530: int ndepth = strlen (newpos);
1531:
1532: /* Pop up as many levels as necessary. */
1533:
1534: while (strncmp (oldpos, newpos, depth))
1535: --depth;
1536:
1537: /* Go down to desired level. */
1538:
1539: while (depth < ndepth)
1540: {
1541: if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1542: printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1543: indents[indent], depth + 1, depth, newpos[depth] - 'a');
1544: else
1545: printf ("%sx%d = XEXP (x%d, %c);\n",
1546: indents[indent], depth + 1, depth, newpos[depth]);
1547: ++depth;
1548: }
1549: }
1550:
1551: static char *
1552: copystr (s1)
1553: char *s1;
1554: {
1555: register char *tem;
1556:
1557: if (s1 == 0)
1558: return 0;
1559:
1560: tem = (char *) xmalloc (strlen (s1) + 1);
1561: strcpy (tem, s1);
1562:
1563: return tem;
1564: }
1565:
1566: static void
1567: mybzero (b, length)
1568: register char *b;
1569: register unsigned length;
1570: {
1571: while (length-- > 0)
1572: *b++ = 0;
1573: }
1574:
1575: static void
1576: mybcopy (in, out, length)
1577: register char *in, *out;
1578: register unsigned length;
1579: {
1580: while (length-- > 0)
1581: *out++ = *in++;
1582: }
1583:
1584: static char *
1585: concat (s1, s2)
1586: char *s1, *s2;
1587: {
1588: register char *tem;
1589:
1590: if (s1 == 0)
1591: return s2;
1592: if (s2 == 0)
1593: return s1;
1594:
1595: tem = (char *) xmalloc (strlen (s1) + strlen (s2) + 2);
1596: strcpy (tem, s1);
1597: strcat (tem, " ");
1598: strcat (tem, s2);
1599:
1600: return tem;
1601: }
1602:
1603: char *
1604: xrealloc (ptr, size)
1605: char *ptr;
1606: unsigned size;
1607: {
1608: char *result = (char *) realloc (ptr, size);
1609: if (!result)
1610: fatal ("virtual memory exhausted");
1611: return result;
1612: }
1613:
1614: char *
1615: xmalloc (size)
1616: unsigned size;
1617: {
1618: register char *val = (char *) malloc (size);
1619:
1620: if (val == 0)
1621: fatal ("virtual memory exhausted");
1622: return val;
1623: }
1624:
1625: static void
1626: fatal (s, a1, a2)
1627: char *s;
1628: {
1629: fprintf (stderr, "genrecog: ");
1630: fprintf (stderr, s, a1, a2);
1631: fprintf (stderr, "\n");
1632: fprintf (stderr, "after %d definitions\n", next_index);
1633: exit (FATAL_EXIT_CODE);
1634: }
1635:
1636: /* More 'friendly' abort that prints the line and file.
1637: config.h can #define abort fancy_abort if you like that sort of thing. */
1638:
1639: void
1640: fancy_abort ()
1641: {
1642: fatal ("Internal gcc abort.");
1643: }
1644:
1645: int
1646: main (argc, argv)
1647: int argc;
1648: char **argv;
1649: {
1650: rtx desc;
1651: struct decision_head recog_tree;
1652: struct decision_head split_tree;
1653: FILE *infile;
1654: register int c;
1655:
1656: obstack_init (rtl_obstack);
1657: recog_tree.first = recog_tree.last = split_tree.first = split_tree.last = 0;
1658:
1659: if (argc <= 1)
1660: fatal ("No input file name.");
1661:
1662: infile = fopen (argv[1], "r");
1663: if (infile == 0)
1664: {
1665: perror (argv[1]);
1666: exit (FATAL_EXIT_CODE);
1667: }
1668:
1669: init_rtl ();
1670: next_insn_code = 0;
1671: next_index = 0;
1672:
1673: printf ("/* Generated automatically by the program `genrecog'\n\
1674: from the machine description file `md'. */\n\n");
1675:
1676: printf ("#include \"config.h\"\n");
1677: printf ("#include \"rtl.h\"\n");
1678: printf ("#include \"insn-config.h\"\n");
1679: printf ("#include \"recog.h\"\n");
1680: printf ("#include \"real.h\"\n");
1681: printf ("#include \"output.h\"\n");
1682: printf ("#include \"flags.h\"\n");
1683: printf ("\n");
1684:
1685: /* Read the machine description. */
1686:
1687: while (1)
1688: {
1689: c = read_skip_spaces (infile);
1690: if (c == EOF)
1691: break;
1692: ungetc (c, infile);
1693:
1694: desc = read_rtx (infile);
1695: if (GET_CODE (desc) == DEFINE_INSN)
1696: recog_tree = merge_trees (recog_tree,
1697: make_insn_sequence (desc, RECOG));
1698: else if (GET_CODE (desc) == DEFINE_SPLIT)
1699: split_tree = merge_trees (split_tree,
1700: make_insn_sequence (desc, SPLIT));
1701: if (GET_CODE (desc) == DEFINE_PEEPHOLE
1702: || GET_CODE (desc) == DEFINE_EXPAND)
1703: next_insn_code++;
1704: next_index++;
1705: }
1706:
1707: printf ("\n\
1708: /* `recog' contains a decision tree\n\
1709: that recognizes whether the rtx X0 is a valid instruction.\n\
1710: \n\
1711: recog returns -1 if the rtx is not valid.\n\
1712: If the rtx is valid, recog returns a nonnegative number\n\
1713: which is the insn code number for the pattern that matched.\n");
1714: printf (" This is the same as the order in the machine description of\n\
1715: the entry that matched. This number can be used as an index into\n\
1716: entry that matched. This number can be used as an index into various\n\
1717: insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands\n\
1718: (found in insn-output.c).\n\n");
1719: printf (" The third argument to recog is an optional pointer to an int.\n\
1720: If present, recog will accept a pattern if it matches except for\n\
1721: missing CLOBBER expressions at the end. In that case, the value\n\
1722: pointed to by the optional pointer will be set to the number of\n\
1723: CLOBBERs that need to be added (it should be initialized to zero by\n\
1724: the caller). If it is set nonzero, the caller should allocate a\n\
1725: PARALLEL of the appropriate size, copy the initial entries, and call\n\
1726: add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.");
1727:
1728: if (split_tree.first)
1729: printf ("\n\n The function split_insns returns 0 if the rtl could not\n\
1730: be split or the split rtl in a SEQUENCE if it can be.");
1731:
1732: printf ("*/\n\n");
1733:
1734: printf ("rtx recog_operand[MAX_RECOG_OPERANDS];\n\n");
1735: printf ("rtx *recog_operand_loc[MAX_RECOG_OPERANDS];\n\n");
1736: printf ("rtx *recog_dup_loc[MAX_DUP_OPERANDS];\n\n");
1737: printf ("char recog_dup_num[MAX_DUP_OPERANDS];\n\n");
1738: printf ("#define operands recog_operand\n\n");
1739:
1740: next_subroutine_number = 0;
1741: break_out_subroutines (recog_tree, RECOG, 1);
1742: write_subroutine (recog_tree.first, RECOG);
1743:
1744: next_subroutine_number = 0;
1745: break_out_subroutines (split_tree, SPLIT, 1);
1746: write_subroutine (split_tree.first, SPLIT);
1747:
1748: fflush (stdout);
1749: exit (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
1750: /* NOTREACHED */
1751: return 0;
1752: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.