1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 88, 92-95, 97-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This program is used to produce insn-recog.c, which contains
23 a function called `recog' plus its subroutines.
24 These functions contain a decision tree
25 that recognizes whether an rtx, the argument given to recog,
26 is a valid instruction.
28 recog returns -1 if the rtx is not valid.
29 If the rtx is valid, recog returns a nonnegative number
30 which is the insn code number for the pattern that matched.
31 This is the same as the order in the machine description of the
32 entry that matched. This number can be used as an index into various
33 insn_* tables, such as insn_template, insn_outfun, and insn_n_operands
34 (found in insn-output.c).
36 The third argument to recog is an optional pointer to an int.
37 If present, recog will accept a pattern if it matches except for
38 missing CLOBBER expressions at the end. In that case, the value
39 pointed to by the optional pointer will be set to the number of
40 CLOBBERs that need to be added (it should be initialized to zero by
41 the caller). If it is set nonzero, the caller should allocate a
42 PARALLEL of the appropriate size, copy the initial entries, and call
43 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
45 This program also generates the function `split_insns',
46 which returns 0 if the rtl could not be split, or
47 it returns the split rtl in a SEQUENCE. */
55 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
56 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
58 static struct obstack obstack
;
59 struct obstack
*rtl_obstack
= &obstack
;
61 #define obstack_chunk_alloc xmalloc
62 #define obstack_chunk_free free
64 /* Holds an array of names indexed by insn_code_number. */
65 char **insn_name_ptr
= 0;
66 int insn_name_ptr_size
= 0;
68 /* Data structure for a listhead of decision trees. The alternatives
69 to a node are kept in a doublely-linked list so we can easily add nodes
70 to the proper place when merging. */
72 struct decision_head
{ struct decision
*first
, *last
; };
74 /* Data structure for decision tree for recognizing
75 legitimate instructions. */
79 int number
; /* Node number, used for labels */
80 char *position
; /* String denoting position in pattern */
81 RTX_CODE code
; /* Code to test for or UNKNOWN to suppress */
82 char ignore_code
; /* If non-zero, need not test code */
83 char ignore_mode
; /* If non-zero, need not test mode */
84 int veclen
; /* Length of vector, if nonzero */
85 enum machine_mode mode
; /* Machine mode of node */
86 char enforce_mode
; /* If non-zero, test `mode' */
87 char retest_code
, retest_mode
; /* See write_tree_1 */
88 int test_elt_zero_int
; /* Nonzero if should test XINT (rtl, 0) */
89 int elt_zero_int
; /* Required value for XINT (rtl, 0) */
90 int test_elt_one_int
; /* Nonzero if should test XINT (rtl, 1) */
91 int elt_one_int
; /* Required value for XINT (rtl, 1) */
92 int test_elt_zero_wide
; /* Nonzero if should test XWINT (rtl, 0) */
93 HOST_WIDE_INT elt_zero_wide
; /* Required value for XWINT (rtl, 0) */
94 const char *tests
; /* If nonzero predicate to call */
95 int pred
; /* `preds' index of predicate or -1 */
96 char *c_test
; /* Additional test to perform */
97 struct decision_head success
; /* Nodes to test on success */
98 int insn_code_number
; /* Insn number matched, if success */
99 int num_clobbers_to_add
; /* Number of CLOBBERs to be added to pattern */
100 struct decision
*next
; /* Node to test on failure */
101 struct decision
*prev
; /* Node whose failure tests us */
102 struct decision
*afterward
; /* Node to test on success, but failure of
104 int opno
; /* Operand number, if >= 0 */
105 int dupno
; /* Number of operand to compare against */
106 int label_needed
; /* Nonzero if label needed when writing tree */
107 int subroutine_number
; /* Number of subroutine this node starts */
110 #define SUBROUTINE_THRESHOLD 50
112 static int next_subroutine_number
;
114 /* We can write three types of subroutines: One for insn recognition,
115 one to split insns, and one for peephole-type optimizations. This
116 defines which type is being written. */
118 enum routine_type
{RECOG
, SPLIT
, PEEPHOLE2
};
120 #define IS_SPLIT(X) ((X) == SPLIT || (X)==PEEPHOLE2)
122 /* Next available node number for tree nodes. */
124 static int next_number
;
126 /* Next number to use as an insn_code. */
128 static int next_insn_code
;
130 /* Similar, but counts all expressions in the MD file; used for
133 static int next_index
;
135 /* Record the highest depth we ever have so we know how many variables to
136 allocate in each subroutine we make. */
138 static int max_depth
;
140 /* This table contains a list of the rtl codes that can possibly match a
141 predicate defined in recog.c. The function `not_both_true' uses it to
142 deduce that there are no expressions that can be matches by certain pairs
143 of tree nodes. Also, if a predicate can match only one code, we can
144 hardwire that code into the node testing the predicate. */
146 static struct pred_table
149 RTX_CODE codes
[NUM_RTX_CODE
];
151 = {{"general_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
152 LABEL_REF
, SUBREG
, REG
, MEM
}},
153 #ifdef PREDICATE_CODES
156 {"address_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
157 LABEL_REF
, SUBREG
, REG
, MEM
, PLUS
, MINUS
, MULT
}},
158 {"register_operand", {SUBREG
, REG
}},
159 {"scratch_operand", {SCRATCH
, REG
}},
160 {"immediate_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
162 {"const_int_operand", {CONST_INT
}},
163 {"const_double_operand", {CONST_INT
, CONST_DOUBLE
}},
164 {"nonimmediate_operand", {SUBREG
, REG
, MEM
}},
165 {"nonmemory_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
166 LABEL_REF
, SUBREG
, REG
}},
167 {"push_operand", {MEM
}},
168 {"pop_operand", {MEM
}},
169 {"memory_operand", {SUBREG
, MEM
}},
170 {"indirect_operand", {SUBREG
, MEM
}},
171 {"comparison_operator", {EQ
, NE
, LE
, LT
, GE
, GT
, LEU
, LTU
, GEU
, GTU
}},
172 {"mode_independent_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
173 LABEL_REF
, SUBREG
, REG
, MEM
}}};
175 #define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0])
177 static struct decision_head make_insn_sequence
PROTO((rtx
, enum routine_type
));
178 static struct decision
*add_to_sequence
PROTO((rtx
, struct decision_head
*,
180 enum routine_type
, int));
181 static int not_both_true
PROTO((struct decision
*, struct decision
*,
183 static int position_merit
PROTO((struct decision
*, enum machine_mode
,
185 static struct decision_head merge_trees
PROTO((struct decision_head
,
186 struct decision_head
));
187 static int break_out_subroutines
PROTO((struct decision_head
,
188 enum routine_type
, int));
189 static void write_subroutine
PROTO((struct decision
*, enum routine_type
));
190 static void write_tree_1
PROTO((struct decision
*, const char *,
191 struct decision
*, enum routine_type
));
192 static void print_code
PROTO((enum rtx_code
));
193 static int same_codes
PROTO((struct decision
*, enum rtx_code
));
194 static void clear_codes
PROTO((struct decision
*));
195 static int same_modes
PROTO((struct decision
*, enum machine_mode
));
196 static void clear_modes
PROTO((struct decision
*));
197 static void write_tree
PROTO((struct decision
*, const char *,
198 struct decision
*, int,
200 static void change_state
PROTO((const char *, const char *, int,
203 /* Construct and return a sequence of decisions
204 that will recognize INSN.
206 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
208 static struct decision_head
209 make_insn_sequence (insn
, type
)
211 enum routine_type type
;
214 char *c_test
= XSTR (insn
, type
== RECOG
? 2 : 1);
215 struct decision
*last
;
216 struct decision_head head
;
219 static const char *last_real_name
= "insn";
220 static int last_real_code
= 0;
223 if (insn_name_ptr_size
<= next_insn_code
)
226 new_size
= (insn_name_ptr_size
? insn_name_ptr_size
* 2 : 512);
227 insn_name_ptr
= xrealloc (insn_name_ptr
, sizeof(char *) * new_size
);
228 bzero (insn_name_ptr
+ insn_name_ptr_size
,
229 sizeof(char *) * (new_size
- insn_name_ptr_size
));
230 insn_name_ptr_size
= new_size
;
234 name
= XSTR (insn
, 0);
235 if (!name
|| name
[0] == '\0')
237 name
= xmalloc (strlen (last_real_name
) + 10);
238 sprintf (name
, "%s+%d", last_real_name
,
239 next_insn_code
- last_real_code
);
243 last_real_name
= name
;
244 last_real_code
= next_insn_code
;
247 insn_name_ptr
[next_insn_code
] = name
;
250 if (type
== PEEPHOLE2
)
254 /* peephole2 gets special treatment:
255 - X always gets an outer parallel even if it's only one entry
256 - we remove all traces of outer-level match_scratch and match_dup
258 x
= rtx_alloc (PARALLEL
);
259 PUT_MODE (x
, VOIDmode
);
260 XVEC (x
, 0) = rtvec_alloc (XVECLEN (insn
, 0));
261 for (i
= j
= 0; i
< XVECLEN (insn
, 0); i
++)
263 rtx tmp
= XVECEXP (insn
, 0, i
);
264 if (GET_CODE (tmp
) != MATCH_SCRATCH
&& GET_CODE (tmp
) != MATCH_DUP
)
266 XVECEXP (x
, 0, j
) = tmp
;
272 else if (XVECLEN (insn
, type
== RECOG
) == 1)
273 x
= XVECEXP (insn
, type
== RECOG
, 0);
276 x
= rtx_alloc (PARALLEL
);
277 XVEC (x
, 0) = XVEC (insn
, type
== RECOG
);
278 PUT_MODE (x
, VOIDmode
);
281 last
= add_to_sequence (x
, &head
, "", type
, 1);
284 last
->c_test
= c_test
;
285 last
->insn_code_number
= next_insn_code
;
286 last
->num_clobbers_to_add
= 0;
288 /* If this is not a DEFINE_SPLIT and X is a PARALLEL, see if it ends with a
289 group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. If so, set up
290 to recognize the pattern without these CLOBBERs. */
292 if (type
== RECOG
&& GET_CODE (x
) == PARALLEL
)
296 for (i
= XVECLEN (x
, 0); i
> 0; i
--)
297 if (GET_CODE (XVECEXP (x
, 0, i
- 1)) != CLOBBER
298 || (GET_CODE (XEXP (XVECEXP (x
, 0, i
- 1), 0)) != REG
299 && GET_CODE (XEXP (XVECEXP (x
, 0, i
- 1), 0)) != MATCH_SCRATCH
))
302 if (i
!= XVECLEN (x
, 0))
305 struct decision_head clobber_head
;
308 new = XVECEXP (x
, 0, 0);
313 new = rtx_alloc (PARALLEL
);
314 XVEC (new, 0) = rtvec_alloc (i
);
315 for (j
= i
- 1; j
>= 0; j
--)
316 XVECEXP (new, 0, j
) = XVECEXP (x
, 0, j
);
319 last
= add_to_sequence (new, &clobber_head
, "", type
, 1);
322 last
->c_test
= c_test
;
323 last
->insn_code_number
= next_insn_code
;
324 last
->num_clobbers_to_add
= XVECLEN (x
, 0) - i
;
326 head
= merge_trees (head
, clobber_head
);
333 /* Define the subroutine we will call below and emit in genemit. */
334 printf ("extern rtx gen_split_%d PROTO ((rtx *));\n",
335 last
->insn_code_number
);
337 else if (type
== PEEPHOLE2
)
338 /* Define the subroutine we will call below and emit in genemit. */
339 printf ("extern rtx gen_peephole2_%d PROTO ((rtx, rtx *));\n",
340 last
->insn_code_number
);
345 /* Create a chain of nodes to verify that an rtl expression matches
348 LAST is a pointer to the listhead in the previous node in the chain (or
349 in the calling function, for the first node).
351 POSITION is the string representing the current position in the insn.
353 INSN_TYPE is the type of insn for which we are emitting code.
355 A pointer to the final node in the chain is returned. */
357 static struct decision
*
358 add_to_sequence (pattern
, last
, position
, insn_type
, top
)
360 struct decision_head
*last
;
361 const char *position
;
362 enum routine_type insn_type
;
365 register RTX_CODE code
;
366 register struct decision
*new
367 = (struct decision
*) xmalloc (sizeof (struct decision
));
368 struct decision
*this;
370 register const char *fmt
;
372 int depth
= strlen (position
);
375 if (depth
> max_depth
)
378 new->number
= next_number
++;
379 new->position
= xstrdup (position
);
380 new->ignore_code
= 0;
381 new->ignore_mode
= 0;
382 new->enforce_mode
= 1;
383 new->retest_code
= new->retest_mode
= 0;
385 new->test_elt_zero_int
= 0;
386 new->test_elt_one_int
= 0;
387 new->test_elt_zero_wide
= 0;
388 new->elt_zero_int
= 0;
389 new->elt_one_int
= 0;
390 new->elt_zero_wide
= 0;
394 new->success
.first
= new->success
.last
= 0;
395 new->insn_code_number
= -1;
396 new->num_clobbers_to_add
= 0;
402 new->label_needed
= 0;
403 new->subroutine_number
= 0;
407 last
->first
= last
->last
= new;
409 newpos
= (char *) alloca (depth
+ 2);
410 strcpy (newpos
, position
);
411 newpos
[depth
+ 1] = 0;
415 new->mode
= GET_MODE (pattern
);
416 new->code
= code
= GET_CODE (pattern
);
421 /* Toplevel peephole pattern. */
422 if (insn_type
== PEEPHOLE2
&& top
)
424 struct decision_head
*place
= last
;
426 for (i
= 0; i
< (size_t) XVECLEN (pattern
, 0); i
++)
428 /* Which insn we're looking at is represented by A-Z. We don't
429 ever use 'A', however; it is always implied. */
431 newpos
[depth
] = 'A' + i
;
434 new = add_to_sequence (XVECEXP (pattern
, 0, i
),
435 place
, newpos
, insn_type
, 0);
436 place
= &new->success
;
446 new->opno
= XINT (pattern
, 0);
447 new->code
= (code
== MATCH_PARALLEL
? PARALLEL
: UNKNOWN
);
448 new->enforce_mode
= 0;
450 if (code
== MATCH_SCRATCH
)
451 new->tests
= "scratch_operand";
453 new->tests
= XSTR (pattern
, 1);
455 if (*new->tests
== 0)
458 /* See if we know about this predicate and save its number. If we do,
459 and it only accepts one code, note that fact. The predicate
460 `const_int_operand' only tests for a CONST_INT, so if we do so we
461 can avoid calling it at all.
463 Finally, if we know that the predicate does not allow CONST_INT, we
464 know that the only way the predicate can match is if the modes match
465 (here we use the kludge of relying on the fact that "address_operand"
466 accepts CONST_INT; otherwise, it would have to be a special case),
467 so we can test the mode (but we need not). This fact should
468 considerably simplify the generated code. */
472 for (i
= 0; i
< NUM_KNOWN_PREDS
; i
++)
473 if (! strcmp (preds
[i
].name
, new->tests
))
476 int allows_const_int
= 0;
480 if (preds
[i
].codes
[1] == 0 && new->code
== UNKNOWN
)
482 new->code
= preds
[i
].codes
[0];
483 if (! strcmp ("const_int_operand", new->tests
))
484 new->tests
= 0, new->pred
= -1;
487 for (j
= 0; j
< NUM_RTX_CODE
&& preds
[i
].codes
[j
] != 0; j
++)
488 if (preds
[i
].codes
[j
] == CONST_INT
)
489 allows_const_int
= 1;
491 if (! allows_const_int
)
492 new->enforce_mode
= new->ignore_mode
= 1;
497 #ifdef PREDICATE_CODES
498 /* If the port has a list of the predicates it uses but omits
500 if (i
== NUM_KNOWN_PREDS
)
501 fprintf (stderr
, "Warning: `%s' not in PREDICATE_CODES\n",
506 if (code
== MATCH_OPERATOR
|| code
== MATCH_PARALLEL
)
508 for (i
= 0; i
< (size_t) XVECLEN (pattern
, 2); i
++)
510 newpos
[depth
] = i
+ (code
== MATCH_OPERATOR
? '0': 'a');
511 new = add_to_sequence (XVECEXP (pattern
, 2, i
),
512 &new->success
, newpos
, insn_type
, 0);
519 new->opno
= XINT (pattern
, 0);
520 new->dupno
= XINT (pattern
, 0);
523 for (i
= 0; i
< (size_t) XVECLEN (pattern
, 1); i
++)
525 newpos
[depth
] = i
+ '0';
526 new = add_to_sequence (XVECEXP (pattern
, 1, i
),
527 &new->success
, newpos
, insn_type
, 0);
533 new->dupno
= XINT (pattern
, 0);
535 new->enforce_mode
= 0;
539 pattern
= XEXP (pattern
, 0);
543 /* The operands of a SET must have the same mode unless one is VOIDmode. */
544 if (GET_MODE (SET_SRC (pattern
)) != VOIDmode
545 && GET_MODE (SET_DEST (pattern
)) != VOIDmode
546 && GET_MODE (SET_SRC (pattern
)) != GET_MODE (SET_DEST (pattern
))
547 /* The mode of an ADDRESS_OPERAND is the mode of the memory reference,
548 not the mode of the address. */
549 && ! (GET_CODE (SET_SRC (pattern
)) == MATCH_OPERAND
550 && ! strcmp (XSTR (SET_SRC (pattern
), 1), "address_operand")))
552 print_rtl (stderr
, pattern
);
553 fputc ('\n', stderr
);
554 fatal ("mode mismatch in SET");
557 new = add_to_sequence (SET_DEST (pattern
), &new->success
, newpos
,
559 this->success
.first
->enforce_mode
= 1;
561 new = add_to_sequence (SET_SRC (pattern
), &new->success
, newpos
,
564 /* If set are setting CC0 from anything other than a COMPARE, we
565 must enforce the mode so that we do not produce ambiguous insns. */
566 if (GET_CODE (SET_DEST (pattern
)) == CC0
567 && GET_CODE (SET_SRC (pattern
)) != COMPARE
)
568 this->success
.first
->enforce_mode
= 1;
573 case STRICT_LOW_PART
:
575 new = add_to_sequence (XEXP (pattern
, 0), &new->success
, newpos
,
577 this->success
.first
->enforce_mode
= 1;
581 this->test_elt_one_int
= 1;
582 this->elt_one_int
= XINT (pattern
, 1);
584 new = add_to_sequence (XEXP (pattern
, 0), &new->success
, newpos
,
586 this->success
.first
->enforce_mode
= 1;
592 new = add_to_sequence (XEXP (pattern
, 0), &new->success
, newpos
,
594 this->success
.first
->enforce_mode
= 1;
596 new = add_to_sequence (XEXP (pattern
, 1), &new->success
, newpos
,
599 new = add_to_sequence (XEXP (pattern
, 2), &new->success
, newpos
,
603 case EQ
: case NE
: case LE
: case LT
: case GE
: case GT
:
604 case LEU
: case LTU
: case GEU
: case GTU
:
605 /* If the first operand is (cc0), we don't have to do anything
607 if (GET_CODE (XEXP (pattern
, 0)) == CC0
)
610 /* ... fall through ... */
613 /* Enforce the mode on the first operand to avoid ambiguous insns. */
615 new = add_to_sequence (XEXP (pattern
, 0), &new->success
, newpos
,
617 this->success
.first
->enforce_mode
= 1;
619 new = add_to_sequence (XEXP (pattern
, 1), &new->success
, newpos
,
627 fmt
= GET_RTX_FORMAT (code
);
628 len
= GET_RTX_LENGTH (code
);
629 for (i
= 0; i
< (size_t) len
; i
++)
631 newpos
[depth
] = '0' + i
;
632 if (fmt
[i
] == 'e' || fmt
[i
] == 'u')
633 new = add_to_sequence (XEXP (pattern
, i
), &new->success
, newpos
,
635 else if (fmt
[i
] == 'i' && i
== 0)
637 this->test_elt_zero_int
= 1;
638 this->elt_zero_int
= XINT (pattern
, i
);
640 else if (fmt
[i
] == 'i' && i
== 1)
642 this->test_elt_one_int
= 1;
643 this->elt_one_int
= XINT (pattern
, i
);
645 else if (fmt
[i
] == 'w' && i
== 0)
647 this->test_elt_zero_wide
= 1;
648 this->elt_zero_wide
= XWINT (pattern
, i
);
650 else if (fmt
[i
] == 'E')
653 /* We do not handle a vector appearing as other than
654 the first item, just because nothing uses them
655 and by handling only the special case
656 we can use one element in newpos for either
657 the item number of a subexpression
658 or the element number in a vector. */
661 this->veclen
= XVECLEN (pattern
, i
);
662 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
664 newpos
[depth
] = 'a' + j
;
665 new = add_to_sequence (XVECEXP (pattern
, i
, j
),
666 &new->success
, newpos
, insn_type
, 0);
669 else if (fmt
[i
] != '0')
675 /* Return 1 if we can prove that there is no RTL that can match both
676 D1 and D2. Otherwise, return 0 (it may be that there is an RTL that
677 can match both or just that we couldn't prove there wasn't such an RTL).
679 TOPLEVEL is non-zero if we are to only look at the top level and not
680 recursively descend. */
683 not_both_true (d1
, d2
, toplevel
)
684 struct decision
*d1
, *d2
;
687 struct decision
*p1
, *p2
;
689 /* If they are both to test modes and the modes are different, they aren't
690 both true. Similarly for codes, integer elements, and vector lengths. */
692 if ((d1
->enforce_mode
&& d2
->enforce_mode
693 && d1
->mode
!= VOIDmode
&& d2
->mode
!= VOIDmode
&& d1
->mode
!= d2
->mode
)
694 || (d1
->code
!= UNKNOWN
&& d2
->code
!= UNKNOWN
&& d1
->code
!= d2
->code
)
695 || (d1
->test_elt_zero_int
&& d2
->test_elt_zero_int
696 && d1
->elt_zero_int
!= d2
->elt_zero_int
)
697 || (d1
->test_elt_one_int
&& d2
->test_elt_one_int
698 && d1
->elt_one_int
!= d2
->elt_one_int
)
699 || (d1
->test_elt_zero_wide
&& d2
->test_elt_zero_wide
700 && d1
->elt_zero_wide
!= d2
->elt_zero_wide
)
701 || (d1
->veclen
&& d2
->veclen
&& d1
->veclen
!= d2
->veclen
))
704 /* If either is a wild-card MATCH_OPERAND without a predicate, it can match
705 absolutely anything, so we can't say that no intersection is possible.
706 This case is detected by having a zero TESTS field with a code of
709 if ((d1
->tests
== 0 && d1
->code
== UNKNOWN
)
710 || (d2
->tests
== 0 && d2
->code
== UNKNOWN
))
713 /* If either has a predicate that we know something about, set things up so
714 that D1 is the one that always has a known predicate. Then see if they
715 have any codes in common. */
717 if (d1
->pred
>= 0 || d2
->pred
>= 0)
722 p1
= d1
, d1
= d2
, d2
= p1
;
724 /* If D2 tests an explicit code, see if it is in the list of valid codes
725 for D1's predicate. */
726 if (d2
->code
!= UNKNOWN
)
728 for (i
= 0; i
< NUM_RTX_CODE
&& preds
[d1
->pred
].codes
[i
] != 0; i
++)
729 if (preds
[d1
->pred
].codes
[i
] == d2
->code
)
732 if (preds
[d1
->pred
].codes
[i
] == 0)
736 /* Otherwise see if the predicates have any codes in common. */
738 else if (d2
->pred
>= 0)
740 for (i
= 0; i
< NUM_RTX_CODE
&& preds
[d1
->pred
].codes
[i
] != 0; i
++)
742 for (j
= 0; j
< NUM_RTX_CODE
; j
++)
743 if (preds
[d2
->pred
].codes
[j
] == 0
744 || preds
[d2
->pred
].codes
[j
] == preds
[d1
->pred
].codes
[i
])
747 if (preds
[d2
->pred
].codes
[j
] != 0)
751 if (preds
[d1
->pred
].codes
[i
] == 0)
756 /* If we got here, we can't prove that D1 and D2 cannot both be true.
757 If we are only to check the top level, return 0. Otherwise, see if
758 we can prove that all choices in both successors are mutually
759 exclusive. If either does not have any successors, we can't prove
760 they can't both be true. */
762 if (toplevel
|| d1
->success
.first
== 0 || d2
->success
.first
== 0)
765 for (p1
= d1
->success
.first
; p1
; p1
= p1
->next
)
766 for (p2
= d2
->success
.first
; p2
; p2
= p2
->next
)
767 if (! not_both_true (p1
, p2
, 0))
773 /* Assuming that we can reorder all the alternatives at a specific point in
774 the tree (see discussion in merge_trees), we would prefer an ordering of
775 nodes where groups of consecutive nodes test the same mode and, within each
776 mode, groups of nodes test the same code. With this order, we can
777 construct nested switch statements, the inner one to test the code and
778 the outer one to test the mode.
780 We would like to list nodes testing for specific codes before those
781 that test predicates to avoid unnecessary function calls. Similarly,
782 tests for specific modes should precede nodes that allow any mode.
784 This function returns the merit (with 0 being the best) of inserting
785 a test involving the specified MODE and CODE after node P. If P is
786 zero, we are to determine the merit of inserting the test at the front
790 position_merit (p
, mode
, code
)
792 enum machine_mode mode
;
795 enum machine_mode p_mode
;
797 /* The only time the front of the list is anything other than the worst
798 position is if we are testing a mode that isn't VOIDmode. */
800 return mode
== VOIDmode
? 3 : 2;
802 p_mode
= p
->enforce_mode
? p
->mode
: VOIDmode
;
804 /* The best case is if the codes and modes both match. */
805 if (p_mode
== mode
&& p
->code
== code
)
808 /* If the codes don't match, the next best case is if the modes match.
809 In that case, the best position for this node depends on whether
810 we are testing for a specific code or not. If we are, the best place
811 is after some other test for an explicit code and our mode or after
812 the last test in the previous mode if every test in our mode is for
815 If we are testing for UNKNOWN, then the next best case is at the end of
819 && ((p_mode
== mode
&& p
->code
!= UNKNOWN
)
820 || (p_mode
!= mode
&& p
->next
821 && (p
->next
->enforce_mode
? p
->next
->mode
: VOIDmode
) == mode
822 && (p
->next
->code
== UNKNOWN
))))
823 || (code
== UNKNOWN
&& p_mode
== mode
825 || (p
->next
->enforce_mode
? p
->next
->mode
: VOIDmode
) != mode
)))
828 /* The third best case occurs when nothing is testing MODE. If MODE
829 is not VOIDmode, then the third best case is after something of any
830 mode that is not VOIDmode. If we are testing VOIDmode, the third best
831 place is the end of the list. */
834 && ((mode
!= VOIDmode
&& p_mode
!= VOIDmode
)
835 || (mode
== VOIDmode
&& p
->next
== 0)))
838 /* Otherwise, we have the worst case. */
842 /* Merge two decision tree listheads OLDH and ADDH,
843 modifying OLDH destructively, and return the merged tree. */
845 static struct decision_head
846 merge_trees (oldh
, addh
)
847 register struct decision_head oldh
, addh
;
849 struct decision
*add
, *next
;
857 /* If we are adding things at different positions, something is wrong. */
858 if (strcmp (oldh
.first
->position
, addh
.first
->position
))
861 for (add
= addh
.first
; add
; add
= next
)
863 enum machine_mode add_mode
= add
->enforce_mode
? add
->mode
: VOIDmode
;
864 struct decision
*best_position
= 0;
866 struct decision
*old
;
870 /* The semantics of pattern matching state that the tests are done in
871 the order given in the MD file so that if an insn matches two
872 patterns, the first one will be used. However, in practice, most,
873 if not all, patterns are unambiguous so that their order is
874 independent. In that case, we can merge identical tests and
875 group all similar modes and codes together.
877 Scan starting from the end of OLDH until we reach a point
878 where we reach the head of the list or where we pass a pattern
879 that could also be true if NEW is true. If we find an identical
880 pattern, we can merge them. Also, record the last node that tests
881 the same code and mode and the last one that tests just the same mode.
883 If we have no match, place NEW after the closest match we found. */
885 for (old
= oldh
.last
; old
; old
= old
->prev
)
889 /* If we don't have anything to test except an additional test,
890 do not consider the two nodes equal. If we did, the test below
891 would cause an infinite recursion. */
892 if (old
->tests
== 0 && old
->test_elt_zero_int
== 0
893 && old
->test_elt_one_int
== 0 && old
->veclen
== 0
894 && old
->test_elt_zero_wide
== 0
895 && old
->dupno
== -1 && old
->mode
== VOIDmode
896 && old
->code
== UNKNOWN
897 && (old
->c_test
!= 0 || add
->c_test
!= 0))
900 else if ((old
->tests
== add
->tests
901 || (old
->pred
>= 0 && old
->pred
== add
->pred
)
902 || (old
->tests
&& add
->tests
903 && !strcmp (old
->tests
, add
->tests
)))
904 && old
->test_elt_zero_int
== add
->test_elt_zero_int
905 && old
->elt_zero_int
== add
->elt_zero_int
906 && old
->test_elt_one_int
== add
->test_elt_one_int
907 && old
->elt_one_int
== add
->elt_one_int
908 && old
->test_elt_zero_wide
== add
->test_elt_zero_wide
909 && old
->elt_zero_wide
== add
->elt_zero_wide
910 && old
->veclen
== add
->veclen
911 && old
->dupno
== add
->dupno
912 && old
->opno
== add
->opno
913 && old
->code
== add
->code
914 && old
->enforce_mode
== add
->enforce_mode
915 && old
->mode
== add
->mode
)
917 /* If the additional test is not the same, split both nodes
918 into nodes that just contain all things tested before the
919 additional test and nodes that contain the additional test
920 and actions when it is true. This optimization is important
921 because of the case where we have almost identical patterns
922 with different tests on target flags. */
924 if (old
->c_test
!= add
->c_test
925 && ! (old
->c_test
&& add
->c_test
926 && !strcmp (old
->c_test
, add
->c_test
)))
928 if (old
->insn_code_number
>= 0 || old
->opno
>= 0)
930 struct decision
*split
931 = (struct decision
*) xmalloc (sizeof (struct decision
));
933 memcpy (split
, old
, sizeof (struct decision
));
935 old
->success
.first
= old
->success
.last
= split
;
938 old
->insn_code_number
= -1;
939 old
->num_clobbers_to_add
= 0;
941 split
->number
= next_number
++;
942 split
->next
= split
->prev
= 0;
943 split
->mode
= VOIDmode
;
944 split
->code
= UNKNOWN
;
946 split
->test_elt_zero_int
= 0;
947 split
->test_elt_one_int
= 0;
948 split
->test_elt_zero_wide
= 0;
954 if (add
->insn_code_number
>= 0 || add
->opno
>= 0)
956 struct decision
*split
957 = (struct decision
*) xmalloc (sizeof (struct decision
));
959 memcpy (split
, add
, sizeof (struct decision
));
961 add
->success
.first
= add
->success
.last
= split
;
964 add
->insn_code_number
= -1;
965 add
->num_clobbers_to_add
= 0;
967 split
->number
= next_number
++;
968 split
->next
= split
->prev
= 0;
969 split
->mode
= VOIDmode
;
970 split
->code
= UNKNOWN
;
972 split
->test_elt_zero_int
= 0;
973 split
->test_elt_one_int
= 0;
974 split
->test_elt_zero_wide
= 0;
981 if (old
->insn_code_number
>= 0 && add
->insn_code_number
>= 0)
983 /* If one node is for a normal insn and the second is
984 for the base insn with clobbers stripped off, the
985 second node should be ignored. */
987 if (old
->num_clobbers_to_add
== 0
988 && add
->num_clobbers_to_add
> 0)
989 /* Nothing to do here. */
991 else if (old
->num_clobbers_to_add
> 0
992 && add
->num_clobbers_to_add
== 0)
994 /* In this case, replace OLD with ADD. */
995 old
->insn_code_number
= add
->insn_code_number
;
996 old
->num_clobbers_to_add
= 0;
999 fatal ("Two actions at one point in tree for insns \"%s\" (%d) and \"%s\" (%d)",
1000 insn_name_ptr
[old
->insn_code_number
],
1001 old
->insn_code_number
,
1002 insn_name_ptr
[add
->insn_code_number
],
1003 add
->insn_code_number
);
1006 if (old
->insn_code_number
== -1)
1007 old
->insn_code_number
= add
->insn_code_number
;
1008 old
->success
= merge_trees (old
->success
, add
->success
);
1013 /* Unless we have already found the best possible insert point,
1014 see if this position is better. If so, record it. */
1017 && ((our_merit
= position_merit (old
, add_mode
, add
->code
))
1019 best_merit
= our_merit
, best_position
= old
;
1021 if (! not_both_true (old
, add
, 0))
1025 /* If ADD was duplicate, we are done. */
1029 /* Otherwise, find the best place to insert ADD. Normally this is
1030 BEST_POSITION. However, if we went all the way to the top of
1031 the list, it might be better to insert at the top. */
1033 if (best_position
== 0)
1037 && position_merit (NULL_PTR
, add_mode
, add
->code
) < best_merit
)
1040 add
->next
= oldh
.first
;
1041 oldh
.first
->prev
= add
;
1047 add
->prev
= best_position
;
1048 add
->next
= best_position
->next
;
1049 best_position
->next
= add
;
1050 if (best_position
== oldh
.last
)
1053 add
->next
->prev
= add
;
1060 /* Count the number of subnodes of HEAD. If the number is high enough,
1061 make the first node in HEAD start a separate subroutine in the C code
1064 TYPE gives the type of routine we are writing.
1066 INITIAL is non-zero if this is the highest-level node. We never write
1070 break_out_subroutines (head
, type
, initial
)
1071 struct decision_head head
;
1072 enum routine_type type
;
1076 struct decision
*sub
;
1078 for (sub
= head
.first
; sub
; sub
= sub
->next
)
1079 size
+= 1 + break_out_subroutines (sub
->success
, type
, 0);
1081 if (size
> SUBROUTINE_THRESHOLD
&& ! initial
)
1083 head
.first
->subroutine_number
= ++next_subroutine_number
;
1084 write_subroutine (head
.first
, type
);
1090 /* Write out a subroutine of type TYPE to do comparisons starting at node
1094 write_subroutine (tree
, type
)
1095 struct decision
*tree
;
1096 enum routine_type type
;
1100 if (type
== PEEPHOLE2
)
1101 printf ("extern rtx peephole2");
1102 else if (type
== SPLIT
)
1103 printf ("extern rtx split");
1105 printf ("extern int recog");
1106 if (tree
!= 0 && tree
->subroutine_number
> 0)
1107 printf ("_%d", tree
->subroutine_number
);
1108 else if (type
== SPLIT
)
1110 printf (" PROTO ((rtx, rtx");
1113 else if (type
== PEEPHOLE2
)
1117 if (type
== PEEPHOLE2
)
1118 printf ("rtx\npeephole2");
1119 else if (type
== SPLIT
)
1120 printf ("rtx\nsplit");
1122 printf ("int\nrecog");
1124 if (tree
!= 0 && tree
->subroutine_number
> 0)
1125 printf ("_%d", tree
->subroutine_number
);
1126 else if (IS_SPLIT (type
))
1129 printf (" (x0, insn");
1131 printf (", pnum_clobbers");
1132 else if (type
== PEEPHOLE2
)
1133 printf (", _plast_insn");
1136 /* The peephole2 pass uses the insn argument to determine which
1137 hard registers are available at that point. */
1138 printf (" register rtx x0;\n rtx insn ATTRIBUTE_UNUSED;\n");
1140 printf (" int *pnum_clobbers ATTRIBUTE_UNUSED;\n");
1141 else if (type
== PEEPHOLE2
)
1142 printf (" rtx *_plast_insn ATTRIBUTE_UNUSED;\n");
1145 printf (" register rtx *ro = &recog_operand[0];\n");
1147 printf (" register rtx ");
1148 for (i
= 1; i
< max_depth
; i
++)
1149 printf ("x%d ATTRIBUTE_UNUSED, ", i
);
1151 printf ("x%d ATTRIBUTE_UNUSED;\n", max_depth
);
1152 if (type
== PEEPHOLE2
)
1153 printf (" register rtx _last_insn = insn;\n");
1154 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type
) ? "rtx" : "int");
1155 write_tree (tree
, "", NULL_PTR
, 1, type
);
1156 if (type
== PEEPHOLE2
)
1157 printf (" ret1:\n *_plast_insn = _last_insn;\n return tem;\n");
1158 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type
) ? 0 : -1);
1161 /* This table is used to indent the recog_* functions when we are inside
1162 conditions or switch statements. We only support small indentations
1163 and always indent at least two spaces. */
1165 static const char *indents
[]
1166 = {" ", " ", " ", " ", " ", " ", " ", " ",
1167 "\t", "\t ", "\t ", "\t ", "\t ", "\t ", "\t ",
1168 "\t\t", "\t\t ", "\t\t ", "\t\t ", "\t\t ", "\t\t "};
1170 /* Write out C code to perform the decisions in TREE for a subroutine of
1171 type TYPE. If all of the choices fail, branch to node AFTERWARD, if
1172 non-zero, otherwise return. PREVPOS is the position of the node that
1173 branched to this test.
1175 When we merged all alternatives, we tried to set up a convenient order.
1176 Specifically, tests involving the same mode are all grouped together,
1177 followed by a group that does not contain a mode test. Within each group
1178 of the same mode, we also group tests with the same code, followed by a
1179 group that does not test a code.
1181 Occasionally, we cannot arbitrarily reorder the tests so that multiple
1182 sequence of groups as described above are present.
1184 We generate two nested switch statements, the outer statement for
1185 testing modes, and the inner switch for testing RTX codes. It is
1186 not worth optimizing cases when only a small number of modes or
1187 codes is tested, since the compiler can do that when compiling the
1188 resulting function. We do check for when every test is the same mode
1192 write_tree_1 (tree
, prevpos
, afterward
, type
)
1193 struct decision
*tree
;
1194 const char *prevpos
;
1195 struct decision
*afterward
;
1196 enum routine_type type
;
1198 register struct decision
*p
, *p1
;
1199 register int depth
= tree
? strlen (tree
->position
) : 0;
1200 enum machine_mode switch_mode
= VOIDmode
;
1201 RTX_CODE switch_code
= UNKNOWN
;
1203 char modemap
[NUM_MACHINE_MODES
];
1204 char codemap
[NUM_RTX_CODE
];
1208 /* One tricky area is what is the exact state when we branch to a
1209 node's label. There are two cases where we branch: when looking at
1210 successors to a node, or when a set of tests fails.
1212 In the former case, we are always branching to the first node in a
1213 decision list and we want all required tests to be performed. We
1214 put the labels for such nodes in front of any switch or test statements.
1215 These branches are done without updating the position to that of the
1218 In the latter case, we are branching to a node that is not the first
1219 node in a decision list. We have already checked that it is possible
1220 for both the node we originally tested at this level and the node we
1221 are branching to to both match some pattern. That means that they
1222 usually will be testing the same mode and code. So it is normally safe
1223 for such labels to be inside switch statements, since the tests done
1224 by virtue of arriving at that label will usually already have been
1225 done. The exception is a branch from a node that does not test a
1226 mode or code to one that does. In such cases, we set the `retest_mode'
1227 or `retest_code' flags. That will ensure that we start a new switch
1228 at that position and put the label before the switch.
1230 The branches in the latter case must set the position to that of the
1235 if (tree
&& tree
->subroutine_number
== 0)
1237 OUTPUT_LABEL (" ", tree
->number
);
1238 tree
->label_needed
= 0;
1243 change_state (prevpos
, tree
->position
, 2, afterward
);
1244 prevpos
= tree
->position
;
1247 for (p
= tree
; p
; p
= p
->next
)
1249 enum machine_mode mode
= p
->enforce_mode
? p
->mode
: VOIDmode
;
1251 int wrote_bracket
= 0;
1254 if (p
->success
.first
== 0 && p
->insn_code_number
< 0)
1257 /* Find the next alternative to p that might be true when p is true.
1258 Test that one next if p's successors fail. */
1260 for (p1
= p
->next
; p1
&& not_both_true (p
, p1
, 1); p1
= p1
->next
)
1266 if (mode
== VOIDmode
&& p1
->enforce_mode
&& p1
->mode
!= VOIDmode
)
1267 p1
->retest_mode
= 1;
1268 if (p
->code
== UNKNOWN
&& p1
->code
!= UNKNOWN
)
1269 p1
->retest_code
= 1;
1270 p1
->label_needed
= 1;
1273 /* If we have a different code or mode than the last node and
1274 are in a switch on codes, we must either end the switch or
1275 go to another case. We must also end the switch if this
1276 node needs a label and to retest either the mode or code. */
1278 if (switch_code
!= UNKNOWN
1279 && (switch_code
!= p
->code
|| switch_mode
!= mode
1280 || (p
->label_needed
&& (p
->retest_mode
|| p
->retest_code
))))
1282 enum rtx_code code
= p
->code
;
1284 /* If P is testing a predicate that we know about and we haven't
1285 seen any of the codes that are valid for the predicate, we
1286 can write a series of "case" statement, one for each possible
1287 code. Since we are already in a switch, these redundant tests
1288 are very cheap and will reduce the number of predicate called. */
1292 for (i
= 0; i
< NUM_RTX_CODE
&& preds
[p
->pred
].codes
[i
] != 0; i
++)
1293 if (codemap
[(int) preds
[p
->pred
].codes
[i
]])
1296 if (preds
[p
->pred
].codes
[i
] == 0)
1297 code
= MATCH_OPERAND
;
1300 if (code
== UNKNOWN
|| codemap
[(int) code
]
1301 || switch_mode
!= mode
1302 || (p
->label_needed
&& (p
->retest_mode
|| p
->retest_code
)))
1304 printf ("%s}\n", indents
[indent
- 2]);
1305 switch_code
= UNKNOWN
;
1311 printf ("%sbreak;\n", indents
[indent
]);
1313 if (code
== MATCH_OPERAND
)
1315 for (i
= 0; i
< NUM_RTX_CODE
&& preds
[p
->pred
].codes
[i
] != 0; i
++)
1317 printf ("%scase ", indents
[indent
- 2]);
1318 print_code (preds
[p
->pred
].codes
[i
]);
1320 codemap
[(int) preds
[p
->pred
].codes
[i
]] = 1;
1325 printf ("%scase ", indents
[indent
- 2]);
1328 codemap
[(int) p
->code
] = 1;
1337 /* If we were previously in a switch on modes and now have a different
1338 mode, end at least the case, and maybe end the switch if we are
1339 not testing a mode or testing a mode whose case we already saw. */
1341 if (switch_mode
!= VOIDmode
1342 && (switch_mode
!= mode
|| (p
->label_needed
&& p
->retest_mode
)))
1344 if (mode
== VOIDmode
|| modemap
[(int) mode
]
1345 || (p
->label_needed
&& p
->retest_mode
))
1347 printf ("%s}\n", indents
[indent
- 2]);
1348 switch_mode
= VOIDmode
;
1354 printf (" break;\n");
1355 printf (" case %smode:\n", GET_MODE_NAME (mode
));
1357 modemap
[(int) mode
] = 1;
1363 /* If we are about to write dead code, something went wrong. */
1364 if (! p
->label_needed
&& uncond
)
1367 /* If we need a label and we will want to retest the mode or code at
1368 that label, write the label now. We have already ensured that
1369 things will be valid for the test. */
1371 if (p
->label_needed
&& (p
->retest_mode
|| p
->retest_code
))
1373 OUTPUT_LABEL (indents
[indent
- 2], p
->number
);
1374 p
->label_needed
= 0;
1379 /* If we are not in any switches, see if we can shortcut things
1380 by checking for identical modes and codes. */
1382 if (switch_mode
== VOIDmode
&& switch_code
== UNKNOWN
)
1384 /* If p and its alternatives all want the same mode,
1385 reject all others at once, first, then ignore the mode. */
1387 if (mode
!= VOIDmode
&& p
->next
&& same_modes (p
, mode
))
1389 printf (" if (GET_MODE (x%d) != %smode)\n",
1390 depth
, GET_MODE_NAME (p
->mode
));
1394 change_state (p
->position
, afterward
->position
, 6,
1396 printf (" goto L%d;\n }\n", afterward
->number
);
1399 printf (" goto ret0;\n");
1404 /* If p and its alternatives all want the same code,
1405 reject all others at once, first, then ignore the code. */
1407 if (p
->code
!= UNKNOWN
&& p
->next
&& same_codes (p
, p
->code
))
1409 printf (" if (GET_CODE (x%d) != ", depth
);
1410 print_code (p
->code
);
1415 change_state (p
->position
, afterward
->position
, indent
+ 4,
1417 printf (" goto L%d;\n }\n", afterward
->number
);
1420 printf (" goto ret0;\n");
1425 /* If we are not in a mode switch and we are testing for a specific
1426 mode, start a mode switch unless we have just one node or the next
1427 node is not testing a mode (we have already tested for the case of
1428 more than one mode, but all of the same mode). */
1430 if (switch_mode
== VOIDmode
&& mode
!= VOIDmode
&& p
->next
!= 0
1431 && p
->next
->enforce_mode
&& p
->next
->mode
!= VOIDmode
)
1433 memset (modemap
, 0, sizeof modemap
);
1434 printf ("%sswitch (GET_MODE (x%d))\n", indents
[indent
], depth
);
1435 printf ("%s{\n", indents
[indent
+ 2]);
1437 printf ("%sdefault:\n%sbreak;\n", indents
[indent
- 2],
1439 printf ("%scase %smode:\n", indents
[indent
- 2],
1440 GET_MODE_NAME (mode
));
1441 modemap
[(int) mode
] = 1;
1445 /* Similarly for testing codes. */
1447 if (switch_code
== UNKNOWN
&& p
->code
!= UNKNOWN
&& ! p
->ignore_code
1448 && p
->next
!= 0 && p
->next
->code
!= UNKNOWN
)
1450 memset (codemap
, 0, sizeof codemap
);
1451 printf ("%sswitch (GET_CODE (x%d))\n", indents
[indent
], depth
);
1452 printf ("%s{\n", indents
[indent
+ 2]);
1454 printf ("%sdefault:\n%sbreak;\n", indents
[indent
- 2],
1456 printf ("%scase ", indents
[indent
- 2]);
1457 print_code (p
->code
);
1459 codemap
[(int) p
->code
] = 1;
1460 switch_code
= p
->code
;
1463 /* Now that most mode and code tests have been done, we can write out
1464 a label for an inner node, if we haven't already. */
1465 if (p
->label_needed
)
1466 OUTPUT_LABEL (indents
[indent
- 2], p
->number
);
1468 inner_indent
= indent
;
1470 /* The only way we can have to do a mode or code test here is if
1471 this node needs such a test but is the only node to be tested.
1472 In that case, we won't have started a switch. Note that this is
1473 the only way the switch and test modes can disagree. */
1475 if ((mode
!= switch_mode
&& ! p
->ignore_mode
)
1476 || (p
->code
!= switch_code
&& p
->code
!= UNKNOWN
&& ! p
->ignore_code
)
1477 || p
->test_elt_zero_int
|| p
->test_elt_one_int
1478 || p
->test_elt_zero_wide
|| p
->veclen
1479 || p
->dupno
>= 0 || p
->tests
|| p
->num_clobbers_to_add
)
1481 printf ("%sif (", indents
[indent
]);
1483 if (mode
!= switch_mode
&& ! p
->ignore_mode
)
1484 printf ("GET_MODE (x%d) == %smode && ",
1485 depth
, GET_MODE_NAME (mode
));
1486 if (p
->code
!= switch_code
&& p
->code
!= UNKNOWN
&& ! p
->ignore_code
)
1488 printf ("GET_CODE (x%d) == ", depth
);
1489 print_code (p
->code
);
1493 if (p
->test_elt_zero_int
)
1494 printf ("XINT (x%d, 0) == %d && ", depth
, p
->elt_zero_int
);
1495 if (p
->test_elt_one_int
)
1496 printf ("XINT (x%d, 1) == %d && ", depth
, p
->elt_one_int
);
1497 if (p
->test_elt_zero_wide
)
1499 /* Set offset to 1 iff the number might get propagated to
1500 unsigned long by ANSI C rules, else 0.
1501 Prospective hosts are required to have at least 32 bit
1502 ints, and integer constants in machine descriptions
1503 must fit in 32 bit, thus it suffices to check only
1505 HOST_WIDE_INT offset
= p
->elt_zero_wide
== -2147483647 - 1;
1506 printf ("XWINT (x%d, 0) == ", depth
);
1507 printf (HOST_WIDE_INT_PRINT_DEC
, p
->elt_zero_wide
+ offset
);
1508 printf ("%s && ", offset
? "-1" : "");
1511 printf ("XVECLEN (x%d, 0) == %d && ", depth
, p
->veclen
);
1513 printf ("rtx_equal_p (x%d, ro[%d]) && ", depth
, p
->dupno
);
1514 if (p
->num_clobbers_to_add
)
1515 printf ("pnum_clobbers != 0 && ");
1517 printf ("%s (x%d, %smode)", p
->tests
, depth
,
1518 GET_MODE_NAME (p
->mode
));
1528 need_bracket
= ! uncond
;
1534 printf ("%s{\n", indents
[inner_indent
]);
1540 printf ("%sro[%d] = x%d;\n", indents
[inner_indent
], p
->opno
, depth
);
1545 printf ("%sif (%s)\n", indents
[inner_indent
], p
->c_test
);
1551 if (p
->insn_code_number
>= 0)
1555 printf ("%sreturn gen_split_%d (operands);\n",
1556 indents
[inner_indent
], p
->insn_code_number
);
1558 else if (type
== PEEPHOLE2
)
1560 printf ("%s{\n", indents
[inner_indent
]);
1563 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1564 indents
[inner_indent
], p
->insn_code_number
);
1565 printf ("%sif (tem != 0) goto ret1;\n", indents
[inner_indent
]);
1567 printf ("%s}\n", indents
[inner_indent
]);
1571 if (p
->num_clobbers_to_add
)
1575 printf ("%s{\n", indents
[inner_indent
]);
1579 printf ("%s*pnum_clobbers = %d;\n",
1580 indents
[inner_indent
], p
->num_clobbers_to_add
);
1581 printf ("%sreturn %d;\n",
1582 indents
[inner_indent
], p
->insn_code_number
);
1587 printf ("%s}\n", indents
[inner_indent
]);
1591 printf ("%sreturn %d;\n",
1592 indents
[inner_indent
], p
->insn_code_number
);
1596 printf ("%sgoto L%d;\n", indents
[inner_indent
],
1597 p
->success
.first
->number
);
1600 printf ("%s}\n", indents
[inner_indent
- 2]);
1603 /* We have now tested all alternatives. End any switches we have open
1604 and branch to the alternative node unless we know that we can't fall
1605 through to the branch. */
1607 if (switch_code
!= UNKNOWN
)
1609 printf ("%s}\n", indents
[indent
- 2]);
1614 if (switch_mode
!= VOIDmode
)
1616 printf ("%s}\n", indents
[indent
- 2]);
1629 change_state (prevpos
, afterward
->position
, 2, afterward
);
1630 printf (" goto L%d;\n", afterward
->number
);
1633 printf (" goto ret0;\n");
1640 register const char *p1
;
1641 for (p1
= GET_RTX_NAME (code
); *p1
; p1
++)
1643 if (*p1
>= 'a' && *p1
<= 'z')
1644 putchar (*p1
+ 'A' - 'a');
1651 same_codes (p
, code
)
1652 register struct decision
*p
;
1653 register enum rtx_code code
;
1655 for (; p
; p
= p
->next
)
1656 if (p
->code
!= code
)
1664 register struct decision
*p
;
1666 for (; p
; p
= p
->next
)
1671 same_modes (p
, mode
)
1672 register struct decision
*p
;
1673 register enum machine_mode mode
;
1675 for (; p
; p
= p
->next
)
1676 if ((p
->enforce_mode
? p
->mode
: VOIDmode
) != mode
)
1684 register struct decision
*p
;
1686 for (; p
; p
= p
->next
)
1687 p
->enforce_mode
= 0;
1690 /* Write out the decision tree starting at TREE for a subroutine of type TYPE.
1692 PREVPOS is the position at the node that branched to this node.
1694 INITIAL is nonzero if this is the first node we are writing in a subroutine.
1696 If all nodes are false, branch to the node AFTERWARD. */
1699 write_tree (tree
, prevpos
, afterward
, initial
, type
)
1700 struct decision
*tree
;
1701 const char *prevpos
;
1702 struct decision
*afterward
;
1704 enum routine_type type
;
1706 register struct decision
*p
;
1707 const char *name_prefix
;
1708 const char *call_suffix
;
1713 name_prefix
= "split";
1717 name_prefix
= "peephole2";
1718 call_suffix
= ", _plast_insn";
1721 name_prefix
= "recog";
1722 call_suffix
= ", pnum_clobbers";
1725 if (! initial
&& tree
->subroutine_number
> 0)
1727 OUTPUT_LABEL (" ", tree
->number
);
1731 printf (" tem = %s_%d (x0, insn%s);\n",
1732 name_prefix
, tree
->subroutine_number
, call_suffix
);
1733 if (IS_SPLIT (type
))
1734 printf (" if (tem != 0) return tem;\n");
1736 printf (" if (tem >= 0) return tem;\n");
1737 change_state (tree
->position
, afterward
->position
, 2, afterward
);
1738 printf (" goto L%d;\n", afterward
->number
);
1741 printf (" return %s_%d (x0, insn%s);\n",
1742 name_prefix
, tree
->subroutine_number
, call_suffix
);
1746 write_tree_1 (tree
, prevpos
, afterward
, type
);
1748 for (p
= tree
; p
; p
= p
->next
)
1749 if (p
->success
.first
)
1750 write_tree (p
->success
.first
, p
->position
,
1751 p
->afterward
? p
->afterward
: afterward
, 0, type
);
1755 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1756 actions are necessary to move to NEWPOS. If we fail to move to the
1757 new state, branch to node AFTERWARD if non-zero, otherwise return.
1759 INDENT says how many blanks to place at the front of lines.
1761 Failure to move to the new state can only occur if we are trying to
1762 match multiple insns and we try to step past the end of the
1766 change_state (oldpos
, newpos
, indent
, afterward
)
1770 struct decision
*afterward
;
1772 int odepth
= strlen (oldpos
);
1774 int ndepth
= strlen (newpos
);
1776 int old_has_insn
, new_has_insn
;
1778 /* Pop up as many levels as necessary. */
1780 while (strncmp (oldpos
, newpos
, depth
))
1784 /* Make sure to reset the _last_insn pointer when popping back up. */
1785 for (old_has_insn
= odepth
- 1; old_has_insn
>= 0; --old_has_insn
)
1786 if (oldpos
[old_has_insn
] >= 'A' && oldpos
[old_has_insn
] <= 'Z')
1788 for (new_has_insn
= odepth
- 1; new_has_insn
>= 0; --new_has_insn
)
1789 if (newpos
[new_has_insn
] >= 'A' && newpos
[new_has_insn
] <= 'Z')
1792 if (old_has_insn
>= 0 && new_has_insn
< 0)
1793 printf ("%s_last_insn = insn;\n", indents
[indent
]);
1795 /* Go down to desired level. */
1797 while (depth
< ndepth
)
1799 /* It's a different insn from the first one. */
1800 if (newpos
[depth
] >= 'A' && newpos
[depth
] <= 'Z')
1802 /* We can only fail if we're moving down the tree. */
1803 if (old_has_insn
>= 0 && oldpos
[old_has_insn
] >= newpos
[depth
])
1805 printf ("%s_last_insn = recog_next_insn (insn, %d);\n",
1806 indents
[indent
], newpos
[depth
] - 'A');
1810 printf ("%stem = recog_next_insn (insn, %d);\n",
1811 indents
[indent
], newpos
[depth
] - 'A');
1813 printf ("%sif (tem == NULL_RTX)\n", indents
[indent
]);
1815 printf ("%sgoto L%d;\n", indents
[indent
+ 2],
1818 printf ("%sgoto ret0;\n", indents
[indent
+ 2]);
1820 printf ("%s_last_insn = tem;\n", indents
[indent
]);
1822 printf ("%sx%d = PATTERN (_last_insn);\n",
1823 indents
[indent
], depth
+ 1);
1825 else if (newpos
[depth
] >= 'a' && newpos
[depth
] <= 'z')
1826 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1827 indents
[indent
], depth
+ 1, depth
, newpos
[depth
] - 'a');
1829 printf ("%sx%d = XEXP (x%d, %c);\n",
1830 indents
[indent
], depth
+ 1, depth
, newpos
[depth
]);
1839 register size_t len
= strlen (input
) + 1;
1840 register char *output
= xmalloc (len
);
1841 memcpy (output
, input
, len
);
1846 xrealloc (old
, size
)
1852 ptr
= (PTR
) realloc (old
, size
);
1854 ptr
= (PTR
) malloc (size
);
1856 fatal ("virtual memory exhausted");
1864 register PTR val
= (PTR
) malloc (size
);
1867 fatal ("virtual memory exhausted");
1877 struct decision_head recog_tree
;
1878 struct decision_head split_tree
;
1879 struct decision_head peephole2_tree
;
1883 progname
= "genrecog";
1884 obstack_init (rtl_obstack
);
1885 recog_tree
.first
= recog_tree
.last
= split_tree
.first
= split_tree
.last
= 0;
1886 peephole2_tree
.first
= peephole2_tree
.last
= 0;
1889 fatal ("No input file name.");
1891 infile
= fopen (argv
[1], "r");
1895 exit (FATAL_EXIT_CODE
);
1901 printf ("/* Generated automatically by the program `genrecog'\n\
1902 from the machine description file `md'. */\n\n");
1904 printf ("#include \"config.h\"\n");
1905 printf ("#include \"system.h\"\n");
1906 printf ("#include \"rtl.h\"\n");
1907 printf ("#include \"function.h\"\n");
1908 printf ("#include \"insn-config.h\"\n");
1909 printf ("#include \"recog.h\"\n");
1910 printf ("#include \"real.h\"\n");
1911 printf ("#include \"output.h\"\n");
1912 printf ("#include \"flags.h\"\n");
1915 /* Read the machine description. */
1919 c
= read_skip_spaces (infile
);
1924 desc
= read_rtx (infile
);
1925 if (GET_CODE (desc
) == DEFINE_INSN
)
1926 recog_tree
= merge_trees (recog_tree
,
1927 make_insn_sequence (desc
, RECOG
));
1928 else if (GET_CODE (desc
) == DEFINE_SPLIT
)
1929 split_tree
= merge_trees (split_tree
,
1930 make_insn_sequence (desc
, SPLIT
));
1931 else if (GET_CODE (desc
) == DEFINE_PEEPHOLE2
)
1932 peephole2_tree
= merge_trees (peephole2_tree
,
1933 make_insn_sequence (desc
, PEEPHOLE2
));
1935 if (GET_CODE (desc
) == DEFINE_PEEPHOLE
1936 || GET_CODE (desc
) == DEFINE_EXPAND
)
1942 /* `recog' contains a decision tree\n\
1943 that recognizes whether the rtx X0 is a valid instruction.\n\
1945 recog returns -1 if the rtx is not valid.\n\
1946 If the rtx is valid, recog returns a nonnegative number\n\
1947 which is the insn code number for the pattern that matched.\n");
1948 printf (" This is the same as the order in the machine description of\n\
1949 the entry that matched. This number can be used as an index into various\n\
1950 insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands\n\
1951 (found in insn-output.c).\n\n");
1952 printf (" The third argument to recog is an optional pointer to an int.\n\
1953 If present, recog will accept a pattern if it matches except for\n\
1954 missing CLOBBER expressions at the end. In that case, the value\n\
1955 pointed to by the optional pointer will be set to the number of\n\
1956 CLOBBERs that need to be added (it should be initialized to zero by\n\
1957 the caller). If it is set nonzero, the caller should allocate a\n\
1958 PARALLEL of the appropriate size, copy the initial entries, and call\n\
1959 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.");
1961 if (split_tree
.first
)
1962 printf ("\n\n The function split_insns returns 0 if the rtl could not\n\
1963 be split or the split rtl in a SEQUENCE if it can be.");
1965 if (peephole2_tree
.first
)
1966 printf ("\n\n The function peephole2_insns returns 0 if the rtl could not\n\
1967 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
1968 and LAST_INSN will point to the last recognized insn in the old sequence.");
1972 printf ("#define operands recog_operand\n\n");
1974 next_subroutine_number
= 0;
1975 break_out_subroutines (recog_tree
, RECOG
, 1);
1976 write_subroutine (recog_tree
.first
, RECOG
);
1978 next_subroutine_number
= 0;
1979 break_out_subroutines (split_tree
, SPLIT
, 1);
1980 write_subroutine (split_tree
.first
, SPLIT
);
1982 if (peephole2_tree
.first
)
1984 next_subroutine_number
= 0;
1985 break_out_subroutines (peephole2_tree
, PEEPHOLE2
, 1);
1986 write_subroutine (peephole2_tree
.first
, PEEPHOLE2
);
1990 exit (ferror (stdout
) != 0 ? FATAL_EXIT_CODE
: SUCCESS_EXIT_CODE
);