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