1 /* Generate code from machine description to recognize rtl as insns.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* This program is used to produce insn-recog.c, which contains a
24 function called `recog' plus its subroutines. These functions
25 contain a decision tree that recognizes whether an rtx, the
26 argument given to recog, is a valid instruction.
28 recog returns -1 if the rtx is not valid. If the rtx is valid,
29 recog returns a nonnegative number which is the insn code number
30 for the pattern that matched. This is the same as the order in the
31 machine description of the entry that matched. This number can be
32 used as an index into various insn_* tables, such as insn_template,
33 insn_outfun, and insn_n_operands (found in insn-output.c).
35 The third argument to recog is an optional pointer to an int. If
36 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
42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
44 This program also generates the function `split_insns', which
45 returns 0 if the rtl could not be split, or it returns the split
48 This program also generates the function `peephole2_insns', which
49 returns 0 if the rtl could not be matched. If there was a match,
50 the new rtl is returned in a SEQUENCE, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
57 #include "gensupport.h"
60 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
61 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
63 /* Holds an array of names indexed by insn_code_number. */
64 static char **insn_name_ptr
= 0;
65 static int insn_name_ptr_size
= 0;
67 /* A listhead of decision trees. The alternatives to a node are kept
68 in a doublely-linked list so we can easily add nodes to the proper
69 place when merging. */
73 struct decision
*first
;
74 struct decision
*last
;
77 /* A single test. The two accept types aren't tests per-se, but
78 their equality (or lack thereof) does affect tree merging so
79 it is convenient to keep them here. */
83 /* A linked list through the tests attached to a node. */
84 struct decision_test
*next
;
86 /* These types are roughly in the order in which we'd like to test them. */
88 DT_mode
, DT_code
, DT_veclen
,
89 DT_elt_zero_int
, DT_elt_one_int
, DT_elt_zero_wide
,
90 DT_dup
, DT_pred
, DT_c_test
,
91 DT_accept_op
, DT_accept_insn
96 enum machine_mode mode
; /* Machine mode of node. */
97 RTX_CODE code
; /* Code to test. */
101 const char *name
; /* Predicate to call. */
102 int index
; /* Index into `preds' or -1. */
103 enum machine_mode mode
; /* Machine mode for node. */
106 const char *c_test
; /* Additional test to perform. */
107 int veclen
; /* Length of vector. */
108 int dup
; /* Number of operand to compare against. */
109 HOST_WIDE_INT intval
; /* Value for XINT for XWINT. */
110 int opno
; /* Operand number matched. */
113 int code_number
; /* Insn number matched. */
114 int lineno
; /* Line number of the insn. */
115 int num_clobbers_to_add
; /* Number of CLOBBERs to be added. */
120 /* Data structure for decision tree for recognizing legitimate insns. */
124 struct decision_head success
; /* Nodes to test on success. */
125 struct decision
*next
; /* Node to test on failure. */
126 struct decision
*prev
; /* Node whose failure tests us. */
127 struct decision
*afterward
; /* Node to test on success,
128 but failure of successor nodes. */
130 const char *position
; /* String denoting position in pattern. */
132 struct decision_test
*tests
; /* The tests for this node. */
134 int number
; /* Node number, used for labels */
135 int subroutine_number
; /* Number of subroutine this node starts */
136 int need_label
; /* Label needs to be output. */
139 #define SUBROUTINE_THRESHOLD 100
141 static int next_subroutine_number
;
143 /* We can write three types of subroutines: One for insn recognition,
144 one to split insns, and one for peephole-type optimizations. This
145 defines which type is being written. */
148 RECOG
, SPLIT
, PEEPHOLE2
151 #define IS_SPLIT(X) ((X) != RECOG)
153 /* Next available node number for tree nodes. */
155 static int next_number
;
157 /* Next number to use as an insn_code. */
159 static int next_insn_code
;
161 /* Similar, but counts all expressions in the MD file; used for
164 static int next_index
;
166 /* Record the highest depth we ever have so we know how many variables to
167 allocate in each subroutine we make. */
169 static int max_depth
;
171 /* The line number of the start of the pattern currently being processed. */
172 static int pattern_lineno
;
174 /* Count of errors. */
175 static int error_count
;
177 /* This table contains a list of the rtl codes that can possibly match a
178 predicate defined in recog.c. The function `maybe_both_true' uses it to
179 deduce that there are no expressions that can be matches by certain pairs
180 of tree nodes. Also, if a predicate can match only one code, we can
181 hardwire that code into the node testing the predicate. */
183 static struct pred_table
186 RTX_CODE codes
[NUM_RTX_CODE
];
188 {"general_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
189 LABEL_REF
, SUBREG
, REG
, MEM
}},
190 #ifdef PREDICATE_CODES
193 {"address_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
194 LABEL_REF
, SUBREG
, REG
, MEM
, PLUS
, MINUS
, MULT
}},
195 {"register_operand", {SUBREG
, REG
}},
196 {"pmode_register_operand", {SUBREG
, REG
}},
197 {"scratch_operand", {SCRATCH
, REG
}},
198 {"immediate_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
200 {"const_int_operand", {CONST_INT
}},
201 {"const_double_operand", {CONST_INT
, CONST_DOUBLE
}},
202 {"nonimmediate_operand", {SUBREG
, REG
, MEM
}},
203 {"nonmemory_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
204 LABEL_REF
, SUBREG
, REG
}},
205 {"push_operand", {MEM
}},
206 {"pop_operand", {MEM
}},
207 {"memory_operand", {SUBREG
, MEM
}},
208 {"indirect_operand", {SUBREG
, MEM
}},
209 {"comparison_operator", {EQ
, NE
, LE
, LT
, GE
, GT
, LEU
, LTU
, GEU
, GTU
,
210 UNORDERED
, ORDERED
, UNEQ
, UNGE
, UNGT
, UNLE
,
212 {"mode_independent_operand", {CONST_INT
, CONST_DOUBLE
, CONST
, SYMBOL_REF
,
213 LABEL_REF
, SUBREG
, REG
, MEM
}}
216 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
218 static const char * special_mode_pred_table
[] = {
219 #ifdef SPECIAL_MODE_PREDICATES
220 SPECIAL_MODE_PREDICATES
222 "pmode_register_operand"
225 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
227 static struct decision
*new_decision
228 PARAMS ((const char *, struct decision_head
*));
229 static struct decision_test
*new_decision_test
230 PARAMS ((enum decision_type
, struct decision_test
***));
231 static rtx find_operand
233 static void validate_pattern
234 PARAMS ((rtx
, rtx
, rtx
));
235 static struct decision
*add_to_sequence
236 PARAMS ((rtx
, struct decision_head
*, const char *, enum routine_type
, int));
238 static int maybe_both_true_2
239 PARAMS ((struct decision_test
*, struct decision_test
*));
240 static int maybe_both_true_1
241 PARAMS ((struct decision_test
*, struct decision_test
*));
242 static int maybe_both_true
243 PARAMS ((struct decision
*, struct decision
*, int));
245 static int nodes_identical_1
246 PARAMS ((struct decision_test
*, struct decision_test
*));
247 static int nodes_identical
248 PARAMS ((struct decision
*, struct decision
*));
249 static void merge_accept_insn
250 PARAMS ((struct decision
*, struct decision
*));
251 static void merge_trees
252 PARAMS ((struct decision_head
*, struct decision_head
*));
254 static void factor_tests
255 PARAMS ((struct decision_head
*));
256 static void simplify_tests
257 PARAMS ((struct decision_head
*));
258 static int break_out_subroutines
259 PARAMS ((struct decision_head
*, int));
260 static void find_afterward
261 PARAMS ((struct decision_head
*, struct decision
*));
263 static void change_state
264 PARAMS ((const char *, const char *, struct decision
*, const char *));
265 static void print_code
266 PARAMS ((enum rtx_code
));
267 static void write_afterward
268 PARAMS ((struct decision
*, struct decision
*, const char *));
269 static struct decision
*write_switch
270 PARAMS ((struct decision
*, int));
271 static void write_cond
272 PARAMS ((struct decision_test
*, int, enum routine_type
));
273 static void write_action
274 PARAMS ((struct decision
*, struct decision_test
*, int, int,
275 struct decision
*, enum routine_type
));
276 static int is_unconditional
277 PARAMS ((struct decision_test
*, enum routine_type
));
278 static int write_node
279 PARAMS ((struct decision
*, int, enum routine_type
));
280 static void write_tree_1
281 PARAMS ((struct decision_head
*, int, enum routine_type
));
282 static void write_tree
283 PARAMS ((struct decision_head
*, const char *, enum routine_type
, int));
284 static void write_subroutine
285 PARAMS ((struct decision_head
*, enum routine_type
));
286 static void write_subroutines
287 PARAMS ((struct decision_head
*, enum routine_type
));
288 static void write_header
291 static struct decision_head make_insn_sequence
292 PARAMS ((rtx
, enum routine_type
));
293 static void process_tree
294 PARAMS ((struct decision_head
*, enum routine_type
));
296 static void record_insn_name
297 PARAMS ((int, const char *));
299 static void debug_decision_0
300 PARAMS ((struct decision
*, int, int));
301 static void debug_decision_1
302 PARAMS ((struct decision
*, int));
303 static void debug_decision_2
304 PARAMS ((struct decision_test
*));
305 extern void debug_decision
306 PARAMS ((struct decision
*));
307 extern void debug_decision_list
308 PARAMS ((struct decision
*));
310 /* Create a new node in sequence after LAST. */
312 static struct decision
*
313 new_decision (position
, last
)
314 const char *position
;
315 struct decision_head
*last
;
317 register struct decision
*new
318 = (struct decision
*) xmalloc (sizeof (struct decision
));
320 memset (new, 0, sizeof (*new));
321 new->success
= *last
;
322 new->position
= xstrdup (position
);
323 new->number
= next_number
++;
325 last
->first
= last
->last
= new;
329 /* Create a new test and link it in at PLACE. */
331 static struct decision_test
*
332 new_decision_test (type
, pplace
)
333 enum decision_type type
;
334 struct decision_test
***pplace
;
336 struct decision_test
**place
= *pplace
;
337 struct decision_test
*test
;
339 test
= (struct decision_test
*) xmalloc (sizeof (*test
));
350 /* Search for and return operand N. */
353 find_operand (pattern
, n
)
362 code
= GET_CODE (pattern
);
363 if ((code
== MATCH_SCRATCH
364 || code
== MATCH_INSN
365 || code
== MATCH_OPERAND
366 || code
== MATCH_OPERATOR
367 || code
== MATCH_PARALLEL
)
368 && XINT (pattern
, 0) == n
)
371 fmt
= GET_RTX_FORMAT (code
);
372 len
= GET_RTX_LENGTH (code
);
373 for (i
= 0; i
< len
; i
++)
378 if ((r
= find_operand (XEXP (pattern
, i
), n
)) != NULL_RTX
)
383 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
384 if ((r
= find_operand (XVECEXP (pattern
, i
, j
), n
)) != NULL_RTX
)
388 case 'i': case 'w': case '0': case 's':
399 /* Check for various errors in patterns. SET is nonnull for a destination,
400 and is the complete set pattern. */
403 validate_pattern (pattern
, insn
, set
)
413 code
= GET_CODE (pattern
);
423 const char *pred_name
= XSTR (pattern
, 1);
424 int allows_non_lvalue
= 1, allows_non_const
= 1;
425 int special_mode_pred
= 0;
428 if (GET_CODE (insn
) == DEFINE_INSN
)
429 c_test
= XSTR (insn
, 2);
431 c_test
= XSTR (insn
, 1);
433 if (pred_name
[0] != 0)
435 for (i
= 0; i
< NUM_KNOWN_PREDS
; i
++)
436 if (! strcmp (preds
[i
].name
, pred_name
))
439 if (i
< NUM_KNOWN_PREDS
)
443 allows_non_lvalue
= allows_non_const
= 0;
444 for (j
= 0; preds
[i
].codes
[j
] != 0; j
++)
446 RTX_CODE c
= preds
[i
].codes
[j
];
453 && c
!= CONSTANT_P_RTX
)
454 allows_non_const
= 1;
461 && c
!= STRICT_LOW_PART
)
462 allows_non_lvalue
= 1;
467 #ifdef PREDICATE_CODES
468 /* If the port has a list of the predicates it uses but
470 message_with_line (pattern_lineno
,
471 "warning: `%s' not in PREDICATE_CODES",
476 for (i
= 0; i
< NUM_SPECIAL_MODE_PREDS
; ++i
)
477 if (strcmp (pred_name
, special_mode_pred_table
[i
]) == 0)
479 special_mode_pred
= 1;
484 /* A MATCH_OPERAND that is a SET should have an output reload. */
486 && code
== MATCH_OPERAND
487 && XSTR (pattern
, 2)[0] != '\0'
488 && XSTR (pattern
, 2)[0] != '='
489 && XSTR (pattern
, 2)[0] != '+')
491 message_with_line (pattern_lineno
,
492 "operand %d missing output reload",
497 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
498 while not likely to occur at runtime, results in less efficient
499 code from insn-recog.c. */
501 && pred_name
[0] != '\0'
502 && allows_non_lvalue
)
504 message_with_line (pattern_lineno
,
505 "warning: destination operand %d allows non-lvalue",
509 /* A modeless MATCH_OPERAND can be handy when we can
510 check for multiple modes in the c_test. In most other cases,
511 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
512 and PEEP2 can FAIL within the output pattern. Exclude
513 address_operand, since its mode is related to the mode of
514 the memory not the operand. Exclude the SET_DEST of a call
515 instruction, as that is a common idiom. */
517 if (GET_MODE (pattern
) == VOIDmode
518 && code
== MATCH_OPERAND
519 && GET_CODE (insn
) == DEFINE_INSN
521 && ! special_mode_pred
522 && pred_name
[0] != '\0'
523 && strcmp (pred_name
, "address_operand") != 0
524 && strstr (c_test
, "operands") == NULL
526 && GET_CODE (set
) == SET
527 && GET_CODE (SET_SRC (set
)) == CALL
))
529 message_with_line (pattern_lineno
,
530 "warning: operand %d missing mode?",
538 enum machine_mode dmode
, smode
;
541 dest
= SET_DEST (pattern
);
542 src
= SET_SRC (pattern
);
544 /* Find the referant for a DUP. */
546 if (GET_CODE (dest
) == MATCH_DUP
547 || GET_CODE (dest
) == MATCH_OP_DUP
548 || GET_CODE (dest
) == MATCH_PAR_DUP
)
549 dest
= find_operand (insn
, XINT (dest
, 0));
551 if (GET_CODE (src
) == MATCH_DUP
552 || GET_CODE (src
) == MATCH_OP_DUP
553 || GET_CODE (src
) == MATCH_PAR_DUP
)
554 src
= find_operand (insn
, XINT (src
, 0));
556 /* STRICT_LOW_PART is a wrapper. Its argument is the real
557 destination, and it's mode should match the source. */
558 if (GET_CODE (dest
) == STRICT_LOW_PART
)
559 dest
= XEXP (dest
, 0);
561 dmode
= GET_MODE (dest
);
562 smode
= GET_MODE (src
);
564 /* The mode of an ADDRESS_OPERAND is the mode of the memory
565 reference, not the mode of the address. */
566 if (GET_CODE (src
) == MATCH_OPERAND
567 && ! strcmp (XSTR (src
, 1), "address_operand"))
570 /* The operands of a SET must have the same mode unless one
572 else if (dmode
!= VOIDmode
&& smode
!= VOIDmode
&& dmode
!= smode
)
574 message_with_line (pattern_lineno
,
575 "mode mismatch in set: %smode vs %smode",
576 GET_MODE_NAME (dmode
), GET_MODE_NAME (smode
));
580 /* If only one of the operands is VOIDmode, and PC or CC0 is
581 not involved, it's probably a mistake. */
582 else if (dmode
!= smode
583 && GET_CODE (dest
) != PC
584 && GET_CODE (dest
) != CC0
585 && GET_CODE (src
) != PC
586 && GET_CODE (src
) != CC0
587 && GET_CODE (src
) != CONST_INT
)
590 which
= (dmode
== VOIDmode
? "destination" : "source");
591 message_with_line (pattern_lineno
,
592 "warning: %s missing a mode?", which
);
595 if (dest
!= SET_DEST (pattern
))
596 validate_pattern (dest
, insn
, pattern
);
597 validate_pattern (SET_DEST (pattern
), insn
, pattern
);
598 validate_pattern (SET_SRC (pattern
), insn
, NULL_RTX
);
603 validate_pattern (SET_DEST (pattern
), insn
, pattern
);
607 if (GET_MODE (XEXP (pattern
, 0)) != VOIDmode
)
609 message_with_line (pattern_lineno
,
610 "operand to label_ref %smode not VOIDmode",
611 GET_MODE_NAME (GET_MODE (XEXP (pattern
, 0))));
620 fmt
= GET_RTX_FORMAT (code
);
621 len
= GET_RTX_LENGTH (code
);
622 for (i
= 0; i
< len
; i
++)
627 validate_pattern (XEXP (pattern
, i
), insn
, NULL_RTX
);
631 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
632 validate_pattern (XVECEXP (pattern
, i
, j
), insn
, NULL_RTX
);
635 case 'i': case 'w': case '0': case 's':
644 /* Create a chain of nodes to verify that an rtl expression matches
647 LAST is a pointer to the listhead in the previous node in the chain (or
648 in the calling function, for the first node).
650 POSITION is the string representing the current position in the insn.
652 INSN_TYPE is the type of insn for which we are emitting code.
654 A pointer to the final node in the chain is returned. */
656 static struct decision
*
657 add_to_sequence (pattern
, last
, position
, insn_type
, top
)
659 struct decision_head
*last
;
660 const char *position
;
661 enum routine_type insn_type
;
665 struct decision
*this, *sub
;
666 struct decision_test
*test
;
667 struct decision_test
**place
;
670 register const char *fmt
;
671 int depth
= strlen (position
);
673 enum machine_mode mode
;
675 if (depth
> max_depth
)
678 subpos
= (char *) alloca (depth
+ 2);
679 strcpy (subpos
, position
);
680 subpos
[depth
+ 1] = 0;
682 sub
= this = new_decision (position
, last
);
683 place
= &this->tests
;
686 mode
= GET_MODE (pattern
);
687 code
= GET_CODE (pattern
);
692 /* Toplevel peephole pattern. */
693 if (insn_type
== PEEPHOLE2
&& top
)
695 /* We don't need the node we just created -- unlink it. */
696 last
->first
= last
->last
= NULL
;
698 for (i
= 0; i
< (size_t) XVECLEN (pattern
, 0); i
++)
700 /* Which insn we're looking at is represented by A-Z. We don't
701 ever use 'A', however; it is always implied. */
703 subpos
[depth
] = (i
> 0 ? 'A' + i
: 0);
704 sub
= add_to_sequence (XVECEXP (pattern
, 0, i
),
705 last
, subpos
, insn_type
, 0);
706 last
= &sub
->success
;
711 /* Else nothing special. */
720 const char *pred_name
;
721 RTX_CODE was_code
= code
;
722 int allows_const_int
= 1;
724 if (code
== MATCH_SCRATCH
)
726 pred_name
= "scratch_operand";
731 pred_name
= XSTR (pattern
, 1);
732 if (code
== MATCH_PARALLEL
)
738 /* We know exactly what const_int_operand matches -- any CONST_INT. */
739 if (strcmp ("const_int_operand", pred_name
) == 0)
744 else if (pred_name
[0] != 0)
746 test
= new_decision_test (DT_pred
, &place
);
747 test
->u
.pred
.name
= pred_name
;
748 test
->u
.pred
.mode
= mode
;
750 /* See if we know about this predicate and save its number. If
751 we do, and it only accepts one code, note that fact. The
752 predicate `const_int_operand' only tests for a CONST_INT, so
753 if we do so we can avoid calling it at all.
755 Finally, if we know that the predicate does not allow
756 CONST_INT, we know that the only way the predicate can match
757 is if the modes match (here we use the kludge of relying on
758 the fact that "address_operand" accepts CONST_INT; otherwise,
759 it would have to be a special case), so we can test the mode
760 (but we need not). This fact should considerably simplify the
763 for (i
= 0; i
< NUM_KNOWN_PREDS
; i
++)
764 if (! strcmp (preds
[i
].name
, pred_name
))
767 if (i
< NUM_KNOWN_PREDS
)
771 test
->u
.pred
.index
= i
;
773 if (preds
[i
].codes
[1] == 0 && code
== UNKNOWN
)
774 code
= preds
[i
].codes
[0];
776 allows_const_int
= 0;
777 for (j
= 0; preds
[i
].codes
[j
] != 0; j
++)
778 if (preds
[i
].codes
[j
] == CONST_INT
)
780 allows_const_int
= 1;
785 test
->u
.pred
.index
= -1;
788 /* Can't enforce a mode if we allow const_int. */
789 if (allows_const_int
)
792 /* Accept the operand, ie. record it in `operands'. */
793 test
= new_decision_test (DT_accept_op
, &place
);
794 test
->u
.opno
= XINT (pattern
, 0);
796 if (was_code
== MATCH_OPERATOR
|| was_code
== MATCH_PARALLEL
)
798 char base
= (was_code
== MATCH_OPERATOR
? '0' : 'a');
799 for (i
= 0; i
< (size_t) XVECLEN (pattern
, 2); i
++)
801 subpos
[depth
] = i
+ base
;
802 sub
= add_to_sequence (XVECEXP (pattern
, 2, i
),
803 &sub
->success
, subpos
, insn_type
, 0);
812 test
= new_decision_test (DT_dup
, &place
);
813 test
->u
.dup
= XINT (pattern
, 0);
815 test
= new_decision_test (DT_accept_op
, &place
);
816 test
->u
.opno
= XINT (pattern
, 0);
818 for (i
= 0; i
< (size_t) XVECLEN (pattern
, 1); i
++)
820 subpos
[depth
] = i
+ '0';
821 sub
= add_to_sequence (XVECEXP (pattern
, 1, i
),
822 &sub
->success
, subpos
, insn_type
, 0);
830 test
= new_decision_test (DT_dup
, &place
);
831 test
->u
.dup
= XINT (pattern
, 0);
835 pattern
= XEXP (pattern
, 0);
842 fmt
= GET_RTX_FORMAT (code
);
843 len
= GET_RTX_LENGTH (code
);
845 /* Do tests against the current node first. */
846 for (i
= 0; i
< (size_t) len
; i
++)
852 test
= new_decision_test (DT_elt_zero_int
, &place
);
853 test
->u
.intval
= XINT (pattern
, i
);
857 test
= new_decision_test (DT_elt_one_int
, &place
);
858 test
->u
.intval
= XINT (pattern
, i
);
863 else if (fmt
[i
] == 'w')
868 test
= new_decision_test (DT_elt_zero_wide
, &place
);
869 test
->u
.intval
= XWINT (pattern
, i
);
871 else if (fmt
[i
] == 'E')
876 test
= new_decision_test (DT_veclen
, &place
);
877 test
->u
.veclen
= XVECLEN (pattern
, i
);
881 /* Now test our sub-patterns. */
882 for (i
= 0; i
< (size_t) len
; i
++)
887 subpos
[depth
] = '0' + i
;
888 sub
= add_to_sequence (XEXP (pattern
, i
), &sub
->success
,
889 subpos
, insn_type
, 0);
895 for (j
= 0; j
< XVECLEN (pattern
, i
); j
++)
897 subpos
[depth
] = 'a' + j
;
898 sub
= add_to_sequence (XVECEXP (pattern
, i
, j
),
899 &sub
->success
, subpos
, insn_type
, 0);
916 /* Insert nodes testing mode and code, if they're still relevant,
917 before any of the nodes we may have added above. */
920 place
= &this->tests
;
921 test
= new_decision_test (DT_code
, &place
);
925 if (mode
!= VOIDmode
)
927 place
= &this->tests
;
928 test
= new_decision_test (DT_mode
, &place
);
932 /* If we didn't insert any tests or accept nodes, hork. */
933 if (this->tests
== NULL
)
939 /* A subroutine of maybe_both_true; examines only one test.
940 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
943 maybe_both_true_2 (d1
, d2
)
944 struct decision_test
*d1
, *d2
;
946 if (d1
->type
== d2
->type
)
951 return d1
->u
.mode
== d2
->u
.mode
;
954 return d1
->u
.code
== d2
->u
.code
;
957 return d1
->u
.veclen
== d2
->u
.veclen
;
959 case DT_elt_zero_int
:
961 case DT_elt_zero_wide
:
962 return d1
->u
.intval
== d2
->u
.intval
;
969 /* If either has a predicate that we know something about, set
970 things up so that D1 is the one that always has a known
971 predicate. Then see if they have any codes in common. */
973 if (d1
->type
== DT_pred
|| d2
->type
== DT_pred
)
975 if (d2
->type
== DT_pred
)
977 struct decision_test
*tmp
;
978 tmp
= d1
, d1
= d2
, d2
= tmp
;
981 /* If D2 tests a mode, see if it matches D1. */
982 if (d1
->u
.pred
.mode
!= VOIDmode
)
984 if (d2
->type
== DT_mode
)
986 if (d1
->u
.pred
.mode
!= d2
->u
.mode
987 /* The mode of an address_operand predicate is the
988 mode of the memory, not the operand. It can only
989 be used for testing the predicate, so we must
991 && strcmp (d1
->u
.pred
.name
, "address_operand") != 0)
994 /* Don't check two predicate modes here, because if both predicates
995 accept CONST_INT, then both can still be true even if the modes
996 are different. If they don't accept CONST_INT, there will be a
997 separate DT_mode that will make maybe_both_true_1 return 0. */
1000 if (d1
->u
.pred
.index
>= 0)
1002 /* If D2 tests a code, see if it is in the list of valid
1003 codes for D1's predicate. */
1004 if (d2
->type
== DT_code
)
1006 const RTX_CODE
*c
= &preds
[d1
->u
.pred
.index
].codes
[0];
1009 if (*c
== d2
->u
.code
)
1017 /* Otherwise see if the predicates have any codes in common. */
1018 else if (d2
->type
== DT_pred
&& d2
->u
.pred
.index
>= 0)
1020 const RTX_CODE
*c1
= &preds
[d1
->u
.pred
.index
].codes
[0];
1023 while (*c1
!= 0 && !common
)
1025 const RTX_CODE
*c2
= &preds
[d2
->u
.pred
.index
].codes
[0];
1026 while (*c2
!= 0 && !common
)
1028 common
= (*c1
== *c2
);
1043 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1044 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1047 maybe_both_true_1 (d1
, d2
)
1048 struct decision_test
*d1
, *d2
;
1050 struct decision_test
*t1
, *t2
;
1052 /* A match_operand with no predicate can match anything. Recognize
1053 this by the existance of a lone DT_accept_op test. */
1054 if (d1
->type
== DT_accept_op
|| d2
->type
== DT_accept_op
)
1057 /* Eliminate pairs of tests while they can exactly match. */
1058 while (d1
&& d2
&& d1
->type
== d2
->type
)
1060 if (maybe_both_true_2 (d1
, d2
) == 0)
1062 d1
= d1
->next
, d2
= d2
->next
;
1065 /* After that, consider all pairs. */
1066 for (t1
= d1
; t1
; t1
= t1
->next
)
1067 for (t2
= d2
; t2
; t2
= t2
->next
)
1068 if (maybe_both_true_2 (t1
, t2
) == 0)
1074 /* Return 0 if we can prove that there is no RTL that can match both
1075 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1076 can match both or just that we couldn't prove there wasn't such an RTL).
1078 TOPLEVEL is non-zero if we are to only look at the top level and not
1079 recursively descend. */
1082 maybe_both_true (d1
, d2
, toplevel
)
1083 struct decision
*d1
, *d2
;
1086 struct decision
*p1
, *p2
;
1089 /* Don't compare strings on the different positions in insn. Doing so
1090 is incorrect and results in false matches from constructs like
1092 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1093 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1095 [(set (match_operand:HI "register_operand" "r")
1096 (match_operand:HI "register_operand" "r"))]
1098 If we are presented with such, we are recursing through the remainder
1099 of a node's success nodes (from the loop at the end of this function).
1100 Skip forward until we come to a position that matches.
1102 Due to the way position strings are constructed, we know that iterating
1103 forward from the lexically lower position (e.g. "00") will run into
1104 the lexically higher position (e.g. "1") and not the other way around.
1105 This saves a bit of effort. */
1107 cmp
= strcmp (d1
->position
, d2
->position
);
1113 /* If the d2->position was lexically lower, swap. */
1115 p1
= d1
, d1
= d2
, d2
= p1
;
1117 if (d1
->success
.first
== 0)
1119 for (p1
= d1
->success
.first
; p1
; p1
= p1
->next
)
1120 if (maybe_both_true (p1
, d2
, 0))
1126 /* Test the current level. */
1127 cmp
= maybe_both_true_1 (d1
->tests
, d2
->tests
);
1131 /* We can't prove that D1 and D2 cannot both be true. If we are only
1132 to check the top level, return 1. Otherwise, see if we can prove
1133 that all choices in both successors are mutually exclusive. If
1134 either does not have any successors, we can't prove they can't both
1137 if (toplevel
|| d1
->success
.first
== 0 || d2
->success
.first
== 0)
1140 for (p1
= d1
->success
.first
; p1
; p1
= p1
->next
)
1141 for (p2
= d2
->success
.first
; p2
; p2
= p2
->next
)
1142 if (maybe_both_true (p1
, p2
, 0))
1148 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1151 nodes_identical_1 (d1
, d2
)
1152 struct decision_test
*d1
, *d2
;
1157 return d1
->u
.mode
== d2
->u
.mode
;
1160 return d1
->u
.code
== d2
->u
.code
;
1163 return (d1
->u
.pred
.mode
== d2
->u
.pred
.mode
1164 && strcmp (d1
->u
.pred
.name
, d2
->u
.pred
.name
) == 0);
1167 return strcmp (d1
->u
.c_test
, d2
->u
.c_test
) == 0;
1170 return d1
->u
.veclen
== d2
->u
.veclen
;
1173 return d1
->u
.dup
== d2
->u
.dup
;
1175 case DT_elt_zero_int
:
1176 case DT_elt_one_int
:
1177 case DT_elt_zero_wide
:
1178 return d1
->u
.intval
== d2
->u
.intval
;
1181 return d1
->u
.opno
== d2
->u
.opno
;
1183 case DT_accept_insn
:
1184 /* Differences will be handled in merge_accept_insn. */
1192 /* True iff the two nodes are identical (on one level only). Due
1193 to the way these lists are constructed, we shouldn't have to
1194 consider different orderings on the tests. */
1197 nodes_identical (d1
, d2
)
1198 struct decision
*d1
, *d2
;
1200 struct decision_test
*t1
, *t2
;
1202 for (t1
= d1
->tests
, t2
= d2
->tests
; t1
&& t2
; t1
= t1
->next
, t2
= t2
->next
)
1204 if (t1
->type
!= t2
->type
)
1206 if (! nodes_identical_1 (t1
, t2
))
1210 /* For success, they should now both be null. */
1214 /* Check that their subnodes are at the same position, as any one set
1215 of sibling decisions must be at the same position. */
1216 if (d1
->success
.first
1217 && d2
->success
.first
1218 && strcmp (d1
->success
.first
->position
, d2
->success
.first
->position
))
1224 /* A subroutine of merge_trees; given two nodes that have been declared
1225 identical, cope with two insn accept states. If they differ in the
1226 number of clobbers, then the conflict was created by make_insn_sequence
1227 and we can drop the with-clobbers version on the floor. If both
1228 nodes have no additional clobbers, we have found an ambiguity in the
1229 source machine description. */
1232 merge_accept_insn (oldd
, addd
)
1233 struct decision
*oldd
, *addd
;
1235 struct decision_test
*old
, *add
;
1237 for (old
= oldd
->tests
; old
; old
= old
->next
)
1238 if (old
->type
== DT_accept_insn
)
1243 for (add
= addd
->tests
; add
; add
= add
->next
)
1244 if (add
->type
== DT_accept_insn
)
1249 /* If one node is for a normal insn and the second is for the base
1250 insn with clobbers stripped off, the second node should be ignored. */
1252 if (old
->u
.insn
.num_clobbers_to_add
== 0
1253 && add
->u
.insn
.num_clobbers_to_add
> 0)
1255 /* Nothing to do here. */
1257 else if (old
->u
.insn
.num_clobbers_to_add
> 0
1258 && add
->u
.insn
.num_clobbers_to_add
== 0)
1260 /* In this case, replace OLD with ADD. */
1261 old
->u
.insn
= add
->u
.insn
;
1265 message_with_line (add
->u
.insn
.lineno
, "`%s' matches `%s'",
1266 get_insn_name (add
->u
.insn
.code_number
),
1267 get_insn_name (old
->u
.insn
.code_number
));
1268 message_with_line (old
->u
.insn
.lineno
, "previous definition of `%s'",
1269 get_insn_name (old
->u
.insn
.code_number
));
1274 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1277 merge_trees (oldh
, addh
)
1278 struct decision_head
*oldh
, *addh
;
1280 struct decision
*next
, *add
;
1282 if (addh
->first
== 0)
1284 if (oldh
->first
== 0)
1290 /* Trying to merge bits at different positions isn't possible. */
1291 if (strcmp (oldh
->first
->position
, addh
->first
->position
))
1294 for (add
= addh
->first
; add
; add
= next
)
1296 struct decision
*old
, *insert_before
= NULL
;
1300 /* The semantics of pattern matching state that the tests are
1301 done in the order given in the MD file so that if an insn
1302 matches two patterns, the first one will be used. However,
1303 in practice, most, if not all, patterns are unambiguous so
1304 that their order is independent. In that case, we can merge
1305 identical tests and group all similar modes and codes together.
1307 Scan starting from the end of OLDH until we reach a point
1308 where we reach the head of the list or where we pass a
1309 pattern that could also be true if NEW is true. If we find
1310 an identical pattern, we can merge them. Also, record the
1311 last node that tests the same code and mode and the last one
1312 that tests just the same mode.
1314 If we have no match, place NEW after the closest match we found. */
1316 for (old
= oldh
->last
; old
; old
= old
->prev
)
1318 if (nodes_identical (old
, add
))
1320 merge_accept_insn (old
, add
);
1321 merge_trees (&old
->success
, &add
->success
);
1325 if (maybe_both_true (old
, add
, 0))
1328 /* Insert the nodes in DT test type order, which is roughly
1329 how expensive/important the test is. Given that the tests
1330 are also ordered within the list, examining the first is
1332 if (add
->tests
->type
< old
->tests
->type
)
1333 insert_before
= old
;
1336 if (insert_before
== NULL
)
1339 add
->prev
= oldh
->last
;
1340 oldh
->last
->next
= add
;
1345 if ((add
->prev
= insert_before
->prev
) != NULL
)
1346 add
->prev
->next
= add
;
1349 add
->next
= insert_before
;
1350 insert_before
->prev
= add
;
1357 /* Walk the tree looking for sub-nodes that perform common tests.
1358 Factor out the common test into a new node. This enables us
1359 (depending on the test type) to emit switch statements later. */
1363 struct decision_head
*head
;
1365 struct decision
*first
, *next
;
1367 for (first
= head
->first
; first
&& first
->next
; first
= next
)
1369 enum decision_type type
;
1370 struct decision
*new, *old_last
;
1372 type
= first
->tests
->type
;
1375 /* Want at least two compatible sequential nodes. */
1376 if (next
->tests
->type
!= type
)
1379 /* Don't want all node types, just those we can turn into
1380 switch statements. */
1383 && type
!= DT_veclen
1384 && type
!= DT_elt_zero_int
1385 && type
!= DT_elt_one_int
1386 && type
!= DT_elt_zero_wide
)
1389 /* If we'd been performing more than one test, create a new node
1390 below our first test. */
1391 if (first
->tests
->next
!= NULL
)
1393 new = new_decision (first
->position
, &first
->success
);
1394 new->tests
= first
->tests
->next
;
1395 first
->tests
->next
= NULL
;
1398 /* Crop the node tree off after our first test. */
1400 old_last
= head
->last
;
1403 /* For each compatible test, adjust to perform only one test in
1404 the top level node, then merge the node back into the tree. */
1407 struct decision_head h
;
1409 if (next
->tests
->next
!= NULL
)
1411 new = new_decision (next
->position
, &next
->success
);
1412 new->tests
= next
->tests
->next
;
1413 next
->tests
->next
= NULL
;
1418 h
.first
= h
.last
= new;
1420 merge_trees (head
, &h
);
1422 while (next
&& next
->tests
->type
== type
);
1424 /* After we run out of compatible tests, graft the remaining nodes
1425 back onto the tree. */
1428 next
->prev
= head
->last
;
1429 head
->last
->next
= next
;
1430 head
->last
= old_last
;
1435 for (first
= head
->first
; first
; first
= first
->next
)
1436 factor_tests (&first
->success
);
1439 /* After factoring, try to simplify the tests on any one node.
1440 Tests that are useful for switch statements are recognizable
1441 by having only a single test on a node -- we'll be manipulating
1442 nodes with multiple tests:
1444 If we have mode tests or code tests that are redundant with
1445 predicates, remove them. */
1448 simplify_tests (head
)
1449 struct decision_head
*head
;
1451 struct decision
*tree
;
1453 for (tree
= head
->first
; tree
; tree
= tree
->next
)
1455 struct decision_test
*a
, *b
;
1462 /* Find a predicate node. */
1463 while (b
&& b
->type
!= DT_pred
)
1467 /* Due to how these tests are constructed, we don't even need
1468 to check that the mode and code are compatible -- they were
1469 generated from the predicate in the first place. */
1470 while (a
->type
== DT_mode
|| a
->type
== DT_code
)
1477 for (tree
= head
->first
; tree
; tree
= tree
->next
)
1478 simplify_tests (&tree
->success
);
1481 /* Count the number of subnodes of HEAD. If the number is high enough,
1482 make the first node in HEAD start a separate subroutine in the C code
1483 that is generated. */
1486 break_out_subroutines (head
, initial
)
1487 struct decision_head
*head
;
1491 struct decision
*sub
;
1493 for (sub
= head
->first
; sub
; sub
= sub
->next
)
1494 size
+= 1 + break_out_subroutines (&sub
->success
, 0);
1496 if (size
> SUBROUTINE_THRESHOLD
&& ! initial
)
1498 head
->first
->subroutine_number
= ++next_subroutine_number
;
1504 /* For each node p, find the next alternative that might be true
1508 find_afterward (head
, real_afterward
)
1509 struct decision_head
*head
;
1510 struct decision
*real_afterward
;
1512 struct decision
*p
, *q
, *afterward
;
1514 /* We can't propogate alternatives across subroutine boundaries.
1515 This is not incorrect, merely a minor optimization loss. */
1518 afterward
= (p
->subroutine_number
> 0 ? NULL
: real_afterward
);
1520 for ( ; p
; p
= p
->next
)
1522 /* Find the next node that might be true if this one fails. */
1523 for (q
= p
->next
; q
; q
= q
->next
)
1524 if (maybe_both_true (p
, q
, 1))
1527 /* If we reached the end of the list without finding one,
1528 use the incoming afterward position. */
1537 for (p
= head
->first
; p
; p
= p
->next
)
1538 if (p
->success
.first
)
1539 find_afterward (&p
->success
, p
->afterward
);
1541 /* When we are generating a subroutine, record the real afterward
1542 position in the first node where write_tree can find it, and we
1543 can do the right thing at the subroutine call site. */
1545 if (p
->subroutine_number
> 0)
1546 p
->afterward
= real_afterward
;
1549 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1550 actions are necessary to move to NEWPOS. If we fail to move to the
1551 new state, branch to node AFTERWARD if non-zero, otherwise return.
1553 Failure to move to the new state can only occur if we are trying to
1554 match multiple insns and we try to step past the end of the stream. */
1557 change_state (oldpos
, newpos
, afterward
, indent
)
1560 struct decision
*afterward
;
1563 int odepth
= strlen (oldpos
);
1564 int ndepth
= strlen (newpos
);
1566 int old_has_insn
, new_has_insn
;
1568 /* Pop up as many levels as necessary. */
1569 for (depth
= odepth
; strncmp (oldpos
, newpos
, depth
) != 0; --depth
)
1572 /* Hunt for the last [A-Z] in both strings. */
1573 for (old_has_insn
= odepth
- 1; old_has_insn
>= 0; --old_has_insn
)
1574 if (oldpos
[old_has_insn
] >= 'A' && oldpos
[old_has_insn
] <= 'Z')
1576 for (new_has_insn
= ndepth
- 1; new_has_insn
>= 0; --new_has_insn
)
1577 if (newpos
[new_has_insn
] >= 'A' && newpos
[new_has_insn
] <= 'Z')
1580 /* Go down to desired level. */
1581 while (depth
< ndepth
)
1583 /* It's a different insn from the first one. */
1584 if (newpos
[depth
] >= 'A' && newpos
[depth
] <= 'Z')
1586 /* We can only fail if we're moving down the tree. */
1587 if (old_has_insn
>= 0 && oldpos
[old_has_insn
] >= newpos
[depth
])
1589 printf ("%stem = peep2_next_insn (%d);\n",
1590 indent
, newpos
[depth
] - 'A');
1594 printf ("%stem = peep2_next_insn (%d);\n",
1595 indent
, newpos
[depth
] - 'A');
1596 printf ("%sif (tem == NULL_RTX)\n", indent
);
1598 printf ("%s goto L%d;\n", indent
, afterward
->number
);
1600 printf ("%s goto ret0;\n", indent
);
1602 printf ("%sx%d = PATTERN (tem);\n", indent
, depth
+ 1);
1604 else if (newpos
[depth
] >= 'a' && newpos
[depth
] <= 'z')
1605 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1606 indent
, depth
+ 1, depth
, newpos
[depth
] - 'a');
1608 printf ("%sx%d = XEXP (x%d, %c);\n",
1609 indent
, depth
+ 1, depth
, newpos
[depth
]);
1614 /* Print the enumerator constant for CODE -- the upcase version of
1621 register const char *p
;
1622 for (p
= GET_RTX_NAME (code
); *p
; p
++)
1623 putchar (TOUPPER (*p
));
1626 /* Emit code to cross an afterward link -- change state and branch. */
1629 write_afterward (start
, afterward
, indent
)
1630 struct decision
*start
;
1631 struct decision
*afterward
;
1634 if (!afterward
|| start
->subroutine_number
> 0)
1635 printf("%sgoto ret0;\n", indent
);
1638 change_state (start
->position
, afterward
->position
, NULL
, indent
);
1639 printf ("%sgoto L%d;\n", indent
, afterward
->number
);
1643 /* Emit a switch statement, if possible, for an initial sequence of
1644 nodes at START. Return the first node yet untested. */
1646 static struct decision
*
1647 write_switch (start
, depth
)
1648 struct decision
*start
;
1651 struct decision
*p
= start
;
1652 enum decision_type type
= p
->tests
->type
;
1653 struct decision
*needs_label
= NULL
;
1655 /* If we have two or more nodes in sequence that test the same one
1656 thing, we may be able to use a switch statement. */
1660 || p
->next
->tests
->type
!= type
1661 || p
->next
->tests
->next
)
1664 /* DT_code is special in that we can do interesting things with
1665 known predicates at the same time. */
1666 if (type
== DT_code
)
1668 char codemap
[NUM_RTX_CODE
];
1669 struct decision
*ret
;
1672 memset (codemap
, 0, sizeof(codemap
));
1674 printf (" switch (GET_CODE (x%d))\n {\n", depth
);
1675 code
= p
->tests
->u
.code
;
1678 if (p
!= start
&& p
->need_label
&& needs_label
== NULL
)
1683 printf (":\n goto L%d;\n", p
->success
.first
->number
);
1684 p
->success
.first
->need_label
= 1;
1691 && p
->tests
->type
== DT_code
1692 && ! codemap
[code
= p
->tests
->u
.code
]);
1694 /* If P is testing a predicate that we know about and we haven't
1695 seen any of the codes that are valid for the predicate, we can
1696 write a series of "case" statement, one for each possible code.
1697 Since we are already in a switch, these redundant tests are very
1698 cheap and will reduce the number of predicates called. */
1700 /* Note that while we write out cases for these predicates here,
1701 we don't actually write the test here, as it gets kinda messy.
1702 It is trivial to leave this to later by telling our caller that
1703 we only processed the CODE tests. */
1704 if (needs_label
!= NULL
)
1709 while (p
&& p
->tests
->type
== DT_pred
1710 && p
->tests
->u
.pred
.index
>= 0)
1714 for (c
= &preds
[p
->tests
->u
.pred
.index
].codes
[0]; *c
; ++c
)
1715 if (codemap
[(int) *c
] != 0)
1718 for (c
= &preds
[p
->tests
->u
.pred
.index
].codes
[0]; *c
; ++c
)
1723 codemap
[(int) *c
] = 1;
1726 printf (" goto L%d;\n", p
->number
);
1732 /* Make the default case skip the predicates we managed to match. */
1734 printf (" default:\n");
1739 printf (" goto L%d;\n", p
->number
);
1743 write_afterward (start
, start
->afterward
, " ");
1746 printf (" break;\n");
1751 else if (type
== DT_mode
1752 || type
== DT_veclen
1753 || type
== DT_elt_zero_int
1754 || type
== DT_elt_one_int
1755 || type
== DT_elt_zero_wide
)
1757 printf (" switch (");
1761 printf ("GET_MODE (x%d)", depth
);
1764 printf ("XVECLEN (x%d, 0)", depth
);
1766 case DT_elt_zero_int
:
1767 printf ("XINT (x%d, 0)", depth
);
1769 case DT_elt_one_int
:
1770 printf ("XINT (x%d, 1)", depth
);
1772 case DT_elt_zero_wide
:
1773 /* Convert result of XWINT to int for portability since some C
1774 compilers won't do it and some will. */
1775 printf ("(int) XWINT (x%d, 0)", depth
);
1784 if (p
!= start
&& p
->need_label
&& needs_label
== NULL
)
1791 printf ("%smode", GET_MODE_NAME (p
->tests
->u
.mode
));
1794 printf ("%d", p
->tests
->u
.veclen
);
1796 case DT_elt_zero_int
:
1797 case DT_elt_one_int
:
1798 case DT_elt_zero_wide
:
1799 printf (HOST_WIDE_INT_PRINT_DEC
, p
->tests
->u
.intval
);
1804 printf (":\n goto L%d;\n", p
->success
.first
->number
);
1805 p
->success
.first
->need_label
= 1;
1809 while (p
&& p
->tests
->type
== type
&& !p
->tests
->next
);
1811 printf (" default:\n break;\n }\n");
1813 return needs_label
!= NULL
? needs_label
: p
;
1817 /* None of the other tests are ameanable. */
1822 /* Emit code for one test. */
1825 write_cond (p
, depth
, subroutine_type
)
1826 struct decision_test
*p
;
1828 enum routine_type subroutine_type
;
1833 printf ("GET_MODE (x%d) == %smode", depth
, GET_MODE_NAME (p
->u
.mode
));
1837 printf ("GET_CODE (x%d) == ", depth
);
1838 print_code (p
->u
.code
);
1842 printf ("XVECLEN (x%d, 0) == %d", depth
, p
->u
.veclen
);
1845 case DT_elt_zero_int
:
1846 printf ("XINT (x%d, 0) == %d", depth
, (int) p
->u
.intval
);
1849 case DT_elt_one_int
:
1850 printf ("XINT (x%d, 1) == %d", depth
, (int) p
->u
.intval
);
1853 case DT_elt_zero_wide
:
1854 printf ("XWINT (x%d, 0) == ", depth
);
1855 printf (HOST_WIDE_INT_PRINT_DEC
, p
->u
.intval
);
1859 printf ("rtx_equal_p (x%d, operands[%d])", depth
, p
->u
.dup
);
1863 printf ("%s (x%d, %smode)", p
->u
.pred
.name
, depth
,
1864 GET_MODE_NAME (p
->u
.pred
.mode
));
1868 printf ("(%s)", p
->u
.c_test
);
1871 case DT_accept_insn
:
1872 switch (subroutine_type
)
1875 if (p
->u
.insn
.num_clobbers_to_add
== 0)
1877 printf ("pnum_clobbers != NULL");
1890 /* Emit code for one action. The previous tests have succeeded;
1891 TEST is the last of the chain. In the normal case we simply
1892 perform a state change. For the `accept' tests we must do more work. */
1895 write_action (p
, test
, depth
, uncond
, success
, subroutine_type
)
1897 struct decision_test
*test
;
1899 struct decision
*success
;
1900 enum routine_type subroutine_type
;
1907 else if (test
->type
== DT_accept_op
|| test
->type
== DT_accept_insn
)
1909 fputs (" {\n", stdout
);
1916 if (test
->type
== DT_accept_op
)
1918 printf("%soperands[%d] = x%d;\n", indent
, test
->u
.opno
, depth
);
1920 /* Only allow DT_accept_insn to follow. */
1924 if (test
->type
!= DT_accept_insn
)
1929 /* Sanity check that we're now at the end of the list of tests. */
1933 if (test
->type
== DT_accept_insn
)
1935 switch (subroutine_type
)
1938 if (test
->u
.insn
.num_clobbers_to_add
!= 0)
1939 printf ("%s*pnum_clobbers = %d;\n",
1940 indent
, test
->u
.insn
.num_clobbers_to_add
);
1941 printf ("%sreturn %d;\n", indent
, test
->u
.insn
.code_number
);
1945 printf ("%sreturn gen_split_%d (operands);\n",
1946 indent
, test
->u
.insn
.code_number
);
1951 int match_len
= 0, i
;
1953 for (i
= strlen (p
->position
) - 1; i
>= 0; --i
)
1954 if (p
->position
[i
] >= 'A' && p
->position
[i
] <= 'Z')
1956 match_len
= p
->position
[i
] - 'A';
1959 printf ("%s*_pmatch_len = %d;\n", indent
, match_len
);
1960 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
1961 indent
, test
->u
.insn
.code_number
);
1962 printf ("%sif (tem != 0)\n%s return tem;\n", indent
, indent
);
1972 printf("%sgoto L%d;\n", indent
, success
->number
);
1973 success
->need_label
= 1;
1977 fputs (" }\n", stdout
);
1980 /* Return 1 if the test is always true and has no fallthru path. Return -1
1981 if the test does have a fallthru path, but requires that the condition be
1982 terminated. Otherwise return 0 for a normal test. */
1983 /* ??? is_unconditional is a stupid name for a tri-state function. */
1986 is_unconditional (t
, subroutine_type
)
1987 struct decision_test
*t
;
1988 enum routine_type subroutine_type
;
1990 if (t
->type
== DT_accept_op
)
1993 if (t
->type
== DT_accept_insn
)
1995 switch (subroutine_type
)
1998 return (t
->u
.insn
.num_clobbers_to_add
== 0);
2011 /* Emit code for one node -- the conditional and the accompanying action.
2012 Return true if there is no fallthru path. */
2015 write_node (p
, depth
, subroutine_type
)
2018 enum routine_type subroutine_type
;
2020 struct decision_test
*test
, *last_test
;
2023 last_test
= test
= p
->tests
;
2024 uncond
= is_unconditional (test
, subroutine_type
);
2028 write_cond (test
, depth
, subroutine_type
);
2030 while ((test
= test
->next
) != NULL
)
2035 uncond2
= is_unconditional (test
, subroutine_type
);
2040 write_cond (test
, depth
, subroutine_type
);
2046 write_action (p
, last_test
, depth
, uncond
, p
->success
.first
, subroutine_type
);
2051 /* Emit code for all of the sibling nodes of HEAD. */
2054 write_tree_1 (head
, depth
, subroutine_type
)
2055 struct decision_head
*head
;
2057 enum routine_type subroutine_type
;
2059 struct decision
*p
, *next
;
2062 for (p
= head
->first
; p
; p
= next
)
2064 /* The label for the first element was printed in write_tree. */
2065 if (p
!= head
->first
&& p
->need_label
)
2066 OUTPUT_LABEL (" ", p
->number
);
2068 /* Attempt to write a switch statement for a whole sequence. */
2069 next
= write_switch (p
, depth
);
2074 /* Failed -- fall back and write one node. */
2075 uncond
= write_node (p
, depth
, subroutine_type
);
2080 /* Finished with this chain. Close a fallthru path by branching
2081 to the afterward node. */
2083 write_afterward (head
->last
, head
->last
->afterward
, " ");
2086 /* Write out the decision tree starting at HEAD. PREVPOS is the
2087 position at the node that branched to this node. */
2090 write_tree (head
, prevpos
, type
, initial
)
2091 struct decision_head
*head
;
2092 const char *prevpos
;
2093 enum routine_type type
;
2096 register struct decision
*p
= head
->first
;
2100 OUTPUT_LABEL (" ", p
->number
);
2102 if (! initial
&& p
->subroutine_number
> 0)
2104 static const char * const name_prefix
[] = {
2105 "recog", "split", "peephole2"
2108 static const char * const call_suffix
[] = {
2109 ", pnum_clobbers", "", ", _pmatch_len"
2112 /* This node has been broken out into a separate subroutine.
2113 Call it, test the result, and branch accordingly. */
2117 printf (" tem = %s_%d (x0, insn%s);\n",
2118 name_prefix
[type
], p
->subroutine_number
, call_suffix
[type
]);
2119 if (IS_SPLIT (type
))
2120 printf (" if (tem != 0)\n return tem;\n");
2122 printf (" if (tem >= 0)\n return tem;\n");
2124 change_state (p
->position
, p
->afterward
->position
, NULL
, " ");
2125 printf (" goto L%d;\n", p
->afterward
->number
);
2129 printf (" return %s_%d (x0, insn%s);\n",
2130 name_prefix
[type
], p
->subroutine_number
, call_suffix
[type
]);
2135 int depth
= strlen (p
->position
);
2137 change_state (prevpos
, p
->position
, head
->last
->afterward
, " ");
2138 write_tree_1 (head
, depth
, type
);
2140 for (p
= head
->first
; p
; p
= p
->next
)
2141 if (p
->success
.first
)
2142 write_tree (&p
->success
, p
->position
, type
, 0);
2146 /* Write out a subroutine of type TYPE to do comparisons starting at
2150 write_subroutine (head
, type
)
2151 struct decision_head
*head
;
2152 enum routine_type type
;
2154 int subfunction
= head
->first
? head
->first
->subroutine_number
: 0;
2159 s_or_e
= subfunction
? "static " : "";
2162 sprintf (extension
, "_%d", subfunction
);
2163 else if (type
== RECOG
)
2164 extension
[0] = '\0';
2166 strcpy (extension
, "_insns");
2171 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e
, extension
);
2173 recog%s (x0, insn, pnum_clobbers)\n\
2175 rtx insn ATTRIBUTE_UNUSED;\n\
2176 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e
, extension
);
2179 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e
, extension
);
2181 split%s (x0, insn)\n\
2183 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e
, extension
);
2186 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n",
2189 peephole2%s (x0, insn, _pmatch_len)\n\
2191 rtx insn ATTRIBUTE_UNUSED;\n\
2192 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e
, extension
);
2196 printf ("{\n register rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2197 for (i
= 1; i
<= max_depth
; i
++)
2198 printf (" register rtx x%d ATTRIBUTE_UNUSED;\n", i
);
2200 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type
) ? "rtx" : "int");
2203 printf (" recog_data.insn = NULL_RTX;\n");
2206 write_tree (head
, "", type
, 1);
2208 printf (" goto ret0;\n");
2210 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type
) ? 0 : -1);
2213 /* In break_out_subroutines, we discovered the boundaries for the
2214 subroutines, but did not write them out. Do so now. */
2217 write_subroutines (head
, type
)
2218 struct decision_head
*head
;
2219 enum routine_type type
;
2223 for (p
= head
->first
; p
; p
= p
->next
)
2224 if (p
->success
.first
)
2225 write_subroutines (&p
->success
, type
);
2227 if (head
->first
->subroutine_number
> 0)
2228 write_subroutine (head
, type
);
2231 /* Begin the output file. */
2237 /* Generated automatically by the program `genrecog' from the target\n\
2238 machine description file. */\n\
2240 #include \"config.h\"\n\
2241 #include \"system.h\"\n\
2242 #include \"rtl.h\"\n\
2243 #include \"tm_p.h\"\n\
2244 #include \"function.h\"\n\
2245 #include \"insn-config.h\"\n\
2246 #include \"recog.h\"\n\
2247 #include \"real.h\"\n\
2248 #include \"output.h\"\n\
2249 #include \"flags.h\"\n\
2250 #include \"hard-reg-set.h\"\n\
2251 #include \"resource.h\"\n\
2255 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2256 X0 is a valid instruction.\n\
2258 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2259 returns a nonnegative number which is the insn code number for the\n\
2260 pattern that matched. This is the same as the order in the machine\n\
2261 description of the entry that matched. This number can be used as an\n\
2262 index into `insn_data' and other tables.\n");
2264 The third argument to recog is an optional pointer to an int. If\n\
2265 present, recog will accept a pattern if it matches except for missing\n\
2266 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2267 the optional pointer will be set to the number of CLOBBERs that need\n\
2268 to be added (it should be initialized to zero by the caller). If it");
2270 is set nonzero, the caller should allocate a PARALLEL of the\n\
2271 appropriate size, copy the initial entries, and call add_clobbers\n\
2272 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2276 The function split_insns returns 0 if the rtl could not\n\
2277 be split or the split rtl in a SEQUENCE if it can be.\n\
2279 The function peephole2_insns returns 0 if the rtl could not\n\
2280 be matched. If there was a match, the new rtl is returned in a SEQUENCE,\n\
2281 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2286 /* Construct and return a sequence of decisions
2287 that will recognize INSN.
2289 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2291 static struct decision_head
2292 make_insn_sequence (insn
, type
)
2294 enum routine_type type
;
2297 const char *c_test
= XSTR (insn
, type
== RECOG
? 2 : 1);
2298 struct decision
*last
;
2299 struct decision_test
*test
, **place
;
2300 struct decision_head head
;
2303 record_insn_name (next_insn_code
, (type
== RECOG
? XSTR (insn
, 0) : NULL
));
2305 c_test_pos
[0] = '\0';
2306 if (type
== PEEPHOLE2
)
2310 /* peephole2 gets special treatment:
2311 - X always gets an outer parallel even if it's only one entry
2312 - we remove all traces of outer-level match_scratch and match_dup
2313 expressions here. */
2314 x
= rtx_alloc (PARALLEL
);
2315 PUT_MODE (x
, VOIDmode
);
2316 XVEC (x
, 0) = rtvec_alloc (XVECLEN (insn
, 0));
2317 for (i
= j
= 0; i
< XVECLEN (insn
, 0); i
++)
2319 rtx tmp
= XVECEXP (insn
, 0, i
);
2320 if (GET_CODE (tmp
) != MATCH_SCRATCH
&& GET_CODE (tmp
) != MATCH_DUP
)
2322 XVECEXP (x
, 0, j
) = tmp
;
2328 c_test_pos
[0] = 'A' + j
- 1;
2329 c_test_pos
[1] = '\0';
2331 else if (XVECLEN (insn
, type
== RECOG
) == 1)
2332 x
= XVECEXP (insn
, type
== RECOG
, 0);
2335 x
= rtx_alloc (PARALLEL
);
2336 XVEC (x
, 0) = XVEC (insn
, type
== RECOG
);
2337 PUT_MODE (x
, VOIDmode
);
2340 validate_pattern (x
, insn
, NULL_RTX
);
2342 memset(&head
, 0, sizeof(head
));
2343 last
= add_to_sequence (x
, &head
, "", type
, 1);
2345 /* Find the end of the test chain on the last node. */
2346 for (test
= last
->tests
; test
->next
; test
= test
->next
)
2348 place
= &test
->next
;
2352 /* Need a new node if we have another test to add. */
2353 if (test
->type
== DT_accept_op
)
2355 last
= new_decision (c_test_pos
, &last
->success
);
2356 place
= &last
->tests
;
2358 test
= new_decision_test (DT_c_test
, &place
);
2359 test
->u
.c_test
= c_test
;
2362 test
= new_decision_test (DT_accept_insn
, &place
);
2363 test
->u
.insn
.code_number
= next_insn_code
;
2364 test
->u
.insn
.lineno
= pattern_lineno
;
2365 test
->u
.insn
.num_clobbers_to_add
= 0;
2370 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2371 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2372 If so, set up to recognize the pattern without these CLOBBERs. */
2374 if (GET_CODE (x
) == PARALLEL
)
2378 /* Find the last non-clobber in the parallel. */
2379 for (i
= XVECLEN (x
, 0); i
> 0; i
--)
2381 rtx y
= XVECEXP (x
, 0, i
- 1);
2382 if (GET_CODE (y
) != CLOBBER
2383 || (GET_CODE (XEXP (y
, 0)) != REG
2384 && GET_CODE (XEXP (y
, 0)) != MATCH_SCRATCH
))
2388 if (i
!= XVECLEN (x
, 0))
2391 struct decision_head clobber_head
;
2393 /* Build a similar insn without the clobbers. */
2395 new = XVECEXP (x
, 0, 0);
2400 new = rtx_alloc (PARALLEL
);
2401 XVEC (new, 0) = rtvec_alloc (i
);
2402 for (j
= i
- 1; j
>= 0; j
--)
2403 XVECEXP (new, 0, j
) = XVECEXP (x
, 0, j
);
2407 memset (&clobber_head
, 0, sizeof(clobber_head
));
2408 last
= add_to_sequence (new, &clobber_head
, "", type
, 1);
2410 /* Find the end of the test chain on the last node. */
2411 for (test
= last
->tests
; test
->next
; test
= test
->next
)
2414 /* We definitely have a new test to add -- create a new
2416 place
= &test
->next
;
2417 if (test
->type
== DT_accept_op
)
2419 last
= new_decision ("", &last
->success
);
2420 place
= &last
->tests
;
2425 test
= new_decision_test (DT_c_test
, &place
);
2426 test
->u
.c_test
= c_test
;
2429 test
= new_decision_test (DT_accept_insn
, &place
);
2430 test
->u
.insn
.code_number
= next_insn_code
;
2431 test
->u
.insn
.lineno
= pattern_lineno
;
2432 test
->u
.insn
.num_clobbers_to_add
= XVECLEN (x
, 0) - i
;
2434 merge_trees (&head
, &clobber_head
);
2440 /* Define the subroutine we will call below and emit in genemit. */
2441 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code
);
2445 /* Define the subroutine we will call below and emit in genemit. */
2446 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2455 process_tree (head
, subroutine_type
)
2456 struct decision_head
*head
;
2457 enum routine_type subroutine_type
;
2459 if (head
->first
== NULL
)
2461 /* We can elide peephole2_insns, but not recog or split_insns. */
2462 if (subroutine_type
== PEEPHOLE2
)
2467 factor_tests (head
);
2469 next_subroutine_number
= 0;
2470 break_out_subroutines (head
, 1);
2471 find_afterward (head
, NULL
);
2473 /* We run this after find_afterward, because find_afterward needs
2474 the redundant DT_mode tests on predicates to determine whether
2475 two tests can both be true or not. */
2476 simplify_tests(head
);
2478 write_subroutines (head
, subroutine_type
);
2481 write_subroutine (head
, subroutine_type
);
2484 extern int main
PARAMS ((int, char **));
2492 struct decision_head recog_tree
, split_tree
, peephole2_tree
, h
;
2494 progname
= "genrecog";
2496 memset (&recog_tree
, 0, sizeof recog_tree
);
2497 memset (&split_tree
, 0, sizeof split_tree
);
2498 memset (&peephole2_tree
, 0, sizeof peephole2_tree
);
2501 fatal ("No input file name.");
2503 if (init_md_reader (argv
[1]) != SUCCESS_EXIT_CODE
)
2504 return (FATAL_EXIT_CODE
);
2511 /* Read the machine description. */
2515 desc
= read_md_rtx (&pattern_lineno
, &next_insn_code
);
2519 if (GET_CODE (desc
) == DEFINE_INSN
)
2521 h
= make_insn_sequence (desc
, RECOG
);
2522 merge_trees (&recog_tree
, &h
);
2524 else if (GET_CODE (desc
) == DEFINE_SPLIT
)
2526 h
= make_insn_sequence (desc
, SPLIT
);
2527 merge_trees (&split_tree
, &h
);
2529 else if (GET_CODE (desc
) == DEFINE_PEEPHOLE2
)
2531 h
= make_insn_sequence (desc
, PEEPHOLE2
);
2532 merge_trees (&peephole2_tree
, &h
);
2539 return FATAL_EXIT_CODE
;
2543 process_tree (&recog_tree
, RECOG
);
2544 process_tree (&split_tree
, SPLIT
);
2545 process_tree (&peephole2_tree
, PEEPHOLE2
);
2548 return (ferror (stdout
) != 0 ? FATAL_EXIT_CODE
: SUCCESS_EXIT_CODE
);
2551 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2553 get_insn_name (code
)
2556 if (code
< insn_name_ptr_size
)
2557 return insn_name_ptr
[code
];
2563 record_insn_name (code
, name
)
2567 static const char *last_real_name
= "insn";
2568 static int last_real_code
= 0;
2571 if (insn_name_ptr_size
<= code
)
2574 new_size
= (insn_name_ptr_size
? insn_name_ptr_size
* 2 : 512);
2576 (char **) xrealloc (insn_name_ptr
, sizeof(char *) * new_size
);
2577 memset (insn_name_ptr
+ insn_name_ptr_size
, 0,
2578 sizeof(char *) * (new_size
- insn_name_ptr_size
));
2579 insn_name_ptr_size
= new_size
;
2582 if (!name
|| name
[0] == '\0')
2584 new = xmalloc (strlen (last_real_name
) + 10);
2585 sprintf (new, "%s+%d", last_real_name
, code
- last_real_code
);
2589 last_real_name
= new = xstrdup (name
);
2590 last_real_code
= code
;
2593 insn_name_ptr
[code
] = new;
2597 debug_decision_2 (test
)
2598 struct decision_test
*test
;
2603 fprintf (stderr
, "mode=%s", GET_MODE_NAME (test
->u
.mode
));
2606 fprintf (stderr
, "code=%s", GET_RTX_NAME (test
->u
.code
));
2609 fprintf (stderr
, "veclen=%d", test
->u
.veclen
);
2611 case DT_elt_zero_int
:
2612 fprintf (stderr
, "elt0_i=%d", (int) test
->u
.intval
);
2614 case DT_elt_one_int
:
2615 fprintf (stderr
, "elt1_i=%d", (int) test
->u
.intval
);
2617 case DT_elt_zero_wide
:
2618 fprintf (stderr
, "elt0_w=");
2619 fprintf (stderr
, HOST_WIDE_INT_PRINT_DEC
, test
->u
.intval
);
2622 fprintf (stderr
, "dup=%d", test
->u
.dup
);
2625 fprintf (stderr
, "pred=(%s,%s)",
2626 test
->u
.pred
.name
, GET_MODE_NAME(test
->u
.pred
.mode
));
2631 strncpy (sub
, test
->u
.c_test
, sizeof(sub
));
2632 memcpy (sub
+16, "...", 4);
2633 fprintf (stderr
, "c_test=\"%s\"", sub
);
2637 fprintf (stderr
, "A_op=%d", test
->u
.opno
);
2639 case DT_accept_insn
:
2640 fprintf (stderr
, "A_insn=(%d,%d)",
2641 test
->u
.insn
.code_number
, test
->u
.insn
.num_clobbers_to_add
);
2650 debug_decision_1 (d
, indent
)
2655 struct decision_test
*test
;
2659 for (i
= 0; i
< indent
; ++i
)
2661 fputs ("(nil)\n", stderr
);
2665 for (i
= 0; i
< indent
; ++i
)
2672 debug_decision_2 (test
);
2673 while ((test
= test
->next
) != NULL
)
2675 fputs (" + ", stderr
);
2676 debug_decision_2 (test
);
2679 fprintf (stderr
, "} %d n %d a %d\n", d
->number
,
2680 (d
->next
? d
->next
->number
: -1),
2681 (d
->afterward
? d
->afterward
->number
: -1));
2685 debug_decision_0 (d
, indent
, maxdepth
)
2687 int indent
, maxdepth
;
2696 for (i
= 0; i
< indent
; ++i
)
2698 fputs ("(nil)\n", stderr
);
2702 debug_decision_1 (d
, indent
);
2703 for (n
= d
->success
.first
; n
; n
= n
->next
)
2704 debug_decision_0 (n
, indent
+ 2, maxdepth
- 1);
2711 debug_decision_0 (d
, 0, 1000000);
2715 debug_decision_list (d
)
2720 debug_decision_0 (d
, 0, 0);