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