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, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
21
22
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.
27
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).
34
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.
43
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
46 rtl as an INSN list.
47
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 an INSN list, and LAST_INSN will point
51 to the last recognized insn in the old sequence. */
52
53 #include "bconfig.h"
54 #include "system.h"
55 #include "coretypes.h"
56 #include "tm.h"
57 #include "rtl.h"
58 #include "errors.h"
59 #include "gensupport.h"
60
61
62 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
63 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
64
65 /* Holds an array of names indexed by insn_code_number. */
66 static char **insn_name_ptr = 0;
67 static int insn_name_ptr_size = 0;
68
69 /* A listhead of decision trees. The alternatives to a node are kept
70 in a doubly-linked list so we can easily add nodes to the proper
71 place when merging. */
72
73 struct decision_head
74 {
75 struct decision *first;
76 struct decision *last;
77 };
78
79 /* A single test. The two accept types aren't tests per-se, but
80 their equality (or lack thereof) does affect tree merging so
81 it is convenient to keep them here. */
82
83 struct decision_test
84 {
85 /* A linked list through the tests attached to a node. */
86 struct decision_test *next;
87
88 /* These types are roughly in the order in which we'd like to test them. */
89 enum decision_type
90 {
91 DT_mode, DT_code, DT_veclen,
92 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
93 DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
94 DT_accept_op, DT_accept_insn
95 } type;
96
97 union
98 {
99 enum machine_mode mode; /* Machine mode of node. */
100 RTX_CODE code; /* Code to test. */
101
102 struct
103 {
104 const char *name; /* Predicate to call. */
105 int index; /* Index into `preds' or -1. */
106 enum machine_mode mode; /* Machine mode for node. */
107 } pred;
108
109 const char *c_test; /* Additional test to perform. */
110 int veclen; /* Length of vector. */
111 int dup; /* Number of operand to compare against. */
112 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
113 int opno; /* Operand number matched. */
114
115 struct {
116 int code_number; /* Insn number matched. */
117 int lineno; /* Line number of the insn. */
118 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
119 } insn;
120 } u;
121 };
122
123 /* Data structure for decision tree for recognizing legitimate insns. */
124
125 struct decision
126 {
127 struct decision_head success; /* Nodes to test on success. */
128 struct decision *next; /* Node to test on failure. */
129 struct decision *prev; /* Node whose failure tests us. */
130 struct decision *afterward; /* Node to test on success,
131 but failure of successor nodes. */
132
133 const char *position; /* String denoting position in pattern. */
134
135 struct decision_test *tests; /* The tests for this node. */
136
137 int number; /* Node number, used for labels */
138 int subroutine_number; /* Number of subroutine this node starts */
139 int need_label; /* Label needs to be output. */
140 };
141
142 #define SUBROUTINE_THRESHOLD 100
143
144 static int next_subroutine_number;
145
146 /* We can write three types of subroutines: One for insn recognition,
147 one to split insns, and one for peephole-type optimizations. This
148 defines which type is being written. */
149
150 enum routine_type {
151 RECOG, SPLIT, PEEPHOLE2
152 };
153
154 #define IS_SPLIT(X) ((X) != RECOG)
155
156 /* Next available node number for tree nodes. */
157
158 static int next_number;
159
160 /* Next number to use as an insn_code. */
161
162 static int next_insn_code;
163
164 /* Similar, but counts all expressions in the MD file; used for
165 error messages. */
166
167 static int next_index;
168
169 /* Record the highest depth we ever have so we know how many variables to
170 allocate in each subroutine we make. */
171
172 static int max_depth;
173
174 /* The line number of the start of the pattern currently being processed. */
175 static int pattern_lineno;
176
177 /* Count of errors. */
178 static int error_count;
179
180 /* This table contains a list of the rtl codes that can possibly match a
181 predicate defined in recog.c. The function `maybe_both_true' uses it to
182 deduce that there are no expressions that can be matches by certain pairs
183 of tree nodes. Also, if a predicate can match only one code, we can
184 hardwire that code into the node testing the predicate. */
185
186 static const struct pred_table
187 {
188 const char *const name;
189 const RTX_CODE codes[NUM_RTX_CODE];
190 } preds[] = {
191 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
192 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}},
193 #ifdef PREDICATE_CODES
194 PREDICATE_CODES
195 #endif
196 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
197 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF,
198 PLUS, MINUS, MULT}},
199 {"register_operand", {SUBREG, REG, ADDRESSOF}},
200 {"pmode_register_operand", {SUBREG, REG, ADDRESSOF}},
201 {"scratch_operand", {SCRATCH, REG}},
202 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
203 LABEL_REF}},
204 {"const_int_operand", {CONST_INT}},
205 {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
206 {"nonimmediate_operand", {SUBREG, REG, MEM, ADDRESSOF}},
207 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
208 LABEL_REF, SUBREG, REG, ADDRESSOF}},
209 {"push_operand", {MEM}},
210 {"pop_operand", {MEM}},
211 {"memory_operand", {SUBREG, MEM}},
212 {"indirect_operand", {SUBREG, MEM}},
213 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
214 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
215 UNLT, LTGT}}
216 };
217
218 #define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
219
220 static const char *const special_mode_pred_table[] = {
221 #ifdef SPECIAL_MODE_PREDICATES
222 SPECIAL_MODE_PREDICATES
223 #endif
224 "pmode_register_operand"
225 };
226
227 #define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
228
229 static struct decision *new_decision
230 (const char *, struct decision_head *);
231 static struct decision_test *new_decision_test
232 (enum decision_type, struct decision_test ***);
233 static rtx find_operand
234 (rtx, int, rtx);
235 static rtx find_matching_operand
236 (rtx, int);
237 static void validate_pattern
238 (rtx, rtx, rtx, int);
239 static struct decision *add_to_sequence
240 (rtx, struct decision_head *, const char *, enum routine_type, int);
241
242 static int maybe_both_true_2
243 (struct decision_test *, struct decision_test *);
244 static int maybe_both_true_1
245 (struct decision_test *, struct decision_test *);
246 static int maybe_both_true
247 (struct decision *, struct decision *, int);
248
249 static int nodes_identical_1
250 (struct decision_test *, struct decision_test *);
251 static int nodes_identical
252 (struct decision *, struct decision *);
253 static void merge_accept_insn
254 (struct decision *, struct decision *);
255 static void merge_trees
256 (struct decision_head *, struct decision_head *);
257
258 static void factor_tests
259 (struct decision_head *);
260 static void simplify_tests
261 (struct decision_head *);
262 static int break_out_subroutines
263 (struct decision_head *, int);
264 static void find_afterward
265 (struct decision_head *, struct decision *);
266
267 static void change_state
268 (const char *, const char *, struct decision *, const char *);
269 static void print_code
270 (enum rtx_code);
271 static void write_afterward
272 (struct decision *, struct decision *, const char *);
273 static struct decision *write_switch
274 (struct decision *, int);
275 static void write_cond
276 (struct decision_test *, int, enum routine_type);
277 static void write_action
278 (struct decision *, struct decision_test *, int, int,
279 struct decision *, enum routine_type);
280 static int is_unconditional
281 (struct decision_test *, enum routine_type);
282 static int write_node
283 (struct decision *, int, enum routine_type);
284 static void write_tree_1
285 (struct decision_head *, int, enum routine_type);
286 static void write_tree
287 (struct decision_head *, const char *, enum routine_type, int);
288 static void write_subroutine
289 (struct decision_head *, enum routine_type);
290 static void write_subroutines
291 (struct decision_head *, enum routine_type);
292 static void write_header
293 (void);
294
295 static struct decision_head make_insn_sequence
296 (rtx, enum routine_type);
297 static void process_tree
298 (struct decision_head *, enum routine_type);
299
300 static void record_insn_name
301 (int, const char *);
302
303 static void debug_decision_0
304 (struct decision *, int, int);
305 static void debug_decision_1
306 (struct decision *, int);
307 static void debug_decision_2
308 (struct decision_test *);
309 extern void debug_decision
310 (struct decision *);
311 extern void debug_decision_list
312 (struct decision *);
313
314 /* Create a new node in sequence after LAST. */
315
316 static struct decision *
new_decision(const char * position,struct decision_head * last)317 new_decision (const char *position, struct decision_head *last)
318 {
319 struct decision *new = xcalloc (1, sizeof (struct decision));
320
321 new->success = *last;
322 new->position = xstrdup (position);
323 new->number = next_number++;
324
325 last->first = last->last = new;
326 return new;
327 }
328
329 /* Create a new test and link it in at PLACE. */
330
331 static struct decision_test *
new_decision_test(enum decision_type type,struct decision_test *** pplace)332 new_decision_test (enum decision_type type, struct decision_test ***pplace)
333 {
334 struct decision_test **place = *pplace;
335 struct decision_test *test;
336
337 test = xmalloc (sizeof (*test));
338 test->next = *place;
339 test->type = type;
340 *place = test;
341
342 place = &test->next;
343 *pplace = place;
344
345 return test;
346 }
347
348 /* Search for and return operand N, stop when reaching node STOP. */
349
350 static rtx
find_operand(rtx pattern,int n,rtx stop)351 find_operand (rtx pattern, int n, rtx stop)
352 {
353 const char *fmt;
354 RTX_CODE code;
355 int i, j, len;
356 rtx r;
357
358 if (pattern == stop)
359 return stop;
360
361 code = GET_CODE (pattern);
362 if ((code == MATCH_SCRATCH
363 || code == MATCH_INSN
364 || code == MATCH_OPERAND
365 || code == MATCH_OPERATOR
366 || code == MATCH_PARALLEL)
367 && XINT (pattern, 0) == n)
368 return pattern;
369
370 fmt = GET_RTX_FORMAT (code);
371 len = GET_RTX_LENGTH (code);
372 for (i = 0; i < len; i++)
373 {
374 switch (fmt[i])
375 {
376 case 'e': case 'u':
377 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
378 return r;
379 break;
380
381 case 'V':
382 if (! XVEC (pattern, i))
383 break;
384 /* Fall through. */
385
386 case 'E':
387 for (j = 0; j < XVECLEN (pattern, i); j++)
388 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
389 != NULL_RTX)
390 return r;
391 break;
392
393 case 'i': case 'w': case '0': case 's':
394 break;
395
396 default:
397 abort ();
398 }
399 }
400
401 return NULL;
402 }
403
404 /* Search for and return operand M, such that it has a matching
405 constraint for operand N. */
406
407 static rtx
find_matching_operand(rtx pattern,int n)408 find_matching_operand (rtx pattern, int n)
409 {
410 const char *fmt;
411 RTX_CODE code;
412 int i, j, len;
413 rtx r;
414
415 code = GET_CODE (pattern);
416 if (code == MATCH_OPERAND
417 && (XSTR (pattern, 2)[0] == '0' + n
418 || (XSTR (pattern, 2)[0] == '%'
419 && XSTR (pattern, 2)[1] == '0' + n)))
420 return pattern;
421
422 fmt = GET_RTX_FORMAT (code);
423 len = GET_RTX_LENGTH (code);
424 for (i = 0; i < len; i++)
425 {
426 switch (fmt[i])
427 {
428 case 'e': case 'u':
429 if ((r = find_matching_operand (XEXP (pattern, i), n)))
430 return r;
431 break;
432
433 case 'V':
434 if (! XVEC (pattern, i))
435 break;
436 /* Fall through. */
437
438 case 'E':
439 for (j = 0; j < XVECLEN (pattern, i); j++)
440 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
441 return r;
442 break;
443
444 case 'i': case 'w': case '0': case 's':
445 break;
446
447 default:
448 abort ();
449 }
450 }
451
452 return NULL;
453 }
454
455
456 /* Check for various errors in patterns. SET is nonnull for a destination,
457 and is the complete set pattern. SET_CODE is '=' for normal sets, and
458 '+' within a context that requires in-out constraints. */
459
460 static void
validate_pattern(rtx pattern,rtx insn,rtx set,int set_code)461 validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
462 {
463 const char *fmt;
464 RTX_CODE code;
465 size_t i, len;
466 int j;
467
468 code = GET_CODE (pattern);
469 switch (code)
470 {
471 case MATCH_SCRATCH:
472 return;
473 case MATCH_DUP:
474 case MATCH_OP_DUP:
475 case MATCH_PAR_DUP:
476 if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
477 {
478 message_with_line (pattern_lineno,
479 "operand %i duplicated before defined",
480 XINT (pattern, 0));
481 error_count++;
482 }
483 break;
484 case MATCH_INSN:
485 case MATCH_OPERAND:
486 case MATCH_OPERATOR:
487 {
488 const char *pred_name = XSTR (pattern, 1);
489 int allows_non_lvalue = 1, allows_non_const = 1;
490 int special_mode_pred = 0;
491 const char *c_test;
492
493 if (GET_CODE (insn) == DEFINE_INSN)
494 c_test = XSTR (insn, 2);
495 else
496 c_test = XSTR (insn, 1);
497
498 if (pred_name[0] != 0)
499 {
500 for (i = 0; i < NUM_KNOWN_PREDS; i++)
501 if (! strcmp (preds[i].name, pred_name))
502 break;
503
504 if (i < NUM_KNOWN_PREDS)
505 {
506 int j;
507
508 allows_non_lvalue = allows_non_const = 0;
509 for (j = 0; preds[i].codes[j] != 0; j++)
510 {
511 RTX_CODE c = preds[i].codes[j];
512 if (c != LABEL_REF
513 && c != SYMBOL_REF
514 && c != CONST_INT
515 && c != CONST_DOUBLE
516 && c != CONST
517 && c != HIGH
518 && c != CONSTANT_P_RTX)
519 allows_non_const = 1;
520
521 if (c != REG
522 && c != SUBREG
523 && c != MEM
524 && c != ADDRESSOF
525 && c != CONCAT
526 && c != PARALLEL
527 && c != STRICT_LOW_PART)
528 allows_non_lvalue = 1;
529 }
530 }
531 else
532 {
533 #ifdef PREDICATE_CODES
534 /* If the port has a list of the predicates it uses but
535 omits one, warn. */
536 message_with_line (pattern_lineno,
537 "warning: `%s' not in PREDICATE_CODES",
538 pred_name);
539 #endif
540 }
541
542 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
543 if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
544 {
545 special_mode_pred = 1;
546 break;
547 }
548 }
549
550 if (code == MATCH_OPERAND)
551 {
552 const char constraints0 = XSTR (pattern, 2)[0];
553
554 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
555 don't use the MATCH_OPERAND constraint, only the predicate.
556 This is confusing to folks doing new ports, so help them
557 not make the mistake. */
558 if (GET_CODE (insn) == DEFINE_EXPAND
559 || GET_CODE (insn) == DEFINE_SPLIT
560 || GET_CODE (insn) == DEFINE_PEEPHOLE2)
561 {
562 if (constraints0)
563 message_with_line (pattern_lineno,
564 "warning: constraints not supported in %s",
565 rtx_name[GET_CODE (insn)]);
566 }
567
568 /* A MATCH_OPERAND that is a SET should have an output reload. */
569 else if (set && constraints0)
570 {
571 if (set_code == '+')
572 {
573 if (constraints0 == '+')
574 ;
575 /* If we've only got an output reload for this operand,
576 we'd better have a matching input operand. */
577 else if (constraints0 == '='
578 && find_matching_operand (insn, XINT (pattern, 0)))
579 ;
580 else
581 {
582 message_with_line (pattern_lineno,
583 "operand %d missing in-out reload",
584 XINT (pattern, 0));
585 error_count++;
586 }
587 }
588 else if (constraints0 != '=' && constraints0 != '+')
589 {
590 message_with_line (pattern_lineno,
591 "operand %d missing output reload",
592 XINT (pattern, 0));
593 error_count++;
594 }
595 }
596 }
597
598 /* Allowing non-lvalues in destinations -- particularly CONST_INT --
599 while not likely to occur at runtime, results in less efficient
600 code from insn-recog.c. */
601 if (set
602 && pred_name[0] != '\0'
603 && allows_non_lvalue)
604 {
605 message_with_line (pattern_lineno,
606 "warning: destination operand %d allows non-lvalue",
607 XINT (pattern, 0));
608 }
609
610 /* A modeless MATCH_OPERAND can be handy when we can
611 check for multiple modes in the c_test. In most other cases,
612 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT
613 and PEEP2 can FAIL within the output pattern. Exclude
614 address_operand, since its mode is related to the mode of
615 the memory not the operand. Exclude the SET_DEST of a call
616 instruction, as that is a common idiom. */
617
618 if (GET_MODE (pattern) == VOIDmode
619 && code == MATCH_OPERAND
620 && GET_CODE (insn) == DEFINE_INSN
621 && allows_non_const
622 && ! special_mode_pred
623 && pred_name[0] != '\0'
624 && strcmp (pred_name, "address_operand") != 0
625 && strstr (c_test, "operands") == NULL
626 && ! (set
627 && GET_CODE (set) == SET
628 && GET_CODE (SET_SRC (set)) == CALL))
629 {
630 message_with_line (pattern_lineno,
631 "warning: operand %d missing mode?",
632 XINT (pattern, 0));
633 }
634 return;
635 }
636
637 case SET:
638 {
639 enum machine_mode dmode, smode;
640 rtx dest, src;
641
642 dest = SET_DEST (pattern);
643 src = SET_SRC (pattern);
644
645 /* STRICT_LOW_PART is a wrapper. Its argument is the real
646 destination, and it's mode should match the source. */
647 if (GET_CODE (dest) == STRICT_LOW_PART)
648 dest = XEXP (dest, 0);
649
650 /* Find the referent for a DUP. */
651
652 if (GET_CODE (dest) == MATCH_DUP
653 || GET_CODE (dest) == MATCH_OP_DUP
654 || GET_CODE (dest) == MATCH_PAR_DUP)
655 dest = find_operand (insn, XINT (dest, 0), NULL);
656
657 if (GET_CODE (src) == MATCH_DUP
658 || GET_CODE (src) == MATCH_OP_DUP
659 || GET_CODE (src) == MATCH_PAR_DUP)
660 src = find_operand (insn, XINT (src, 0), NULL);
661
662 dmode = GET_MODE (dest);
663 smode = GET_MODE (src);
664
665 /* The mode of an ADDRESS_OPERAND is the mode of the memory
666 reference, not the mode of the address. */
667 if (GET_CODE (src) == MATCH_OPERAND
668 && ! strcmp (XSTR (src, 1), "address_operand"))
669 ;
670
671 /* The operands of a SET must have the same mode unless one
672 is VOIDmode. */
673 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
674 {
675 message_with_line (pattern_lineno,
676 "mode mismatch in set: %smode vs %smode",
677 GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
678 error_count++;
679 }
680
681 /* If only one of the operands is VOIDmode, and PC or CC0 is
682 not involved, it's probably a mistake. */
683 else if (dmode != smode
684 && GET_CODE (dest) != PC
685 && GET_CODE (dest) != CC0
686 && GET_CODE (src) != PC
687 && GET_CODE (src) != CC0
688 && GET_CODE (src) != CONST_INT)
689 {
690 const char *which;
691 which = (dmode == VOIDmode ? "destination" : "source");
692 message_with_line (pattern_lineno,
693 "warning: %s missing a mode?", which);
694 }
695
696 if (dest != SET_DEST (pattern))
697 validate_pattern (dest, insn, pattern, '=');
698 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
699 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
700 return;
701 }
702
703 case CLOBBER:
704 validate_pattern (SET_DEST (pattern), insn, pattern, '=');
705 return;
706
707 case ZERO_EXTRACT:
708 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
709 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
710 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
711 return;
712
713 case STRICT_LOW_PART:
714 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
715 return;
716
717 case LABEL_REF:
718 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
719 {
720 message_with_line (pattern_lineno,
721 "operand to label_ref %smode not VOIDmode",
722 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
723 error_count++;
724 }
725 break;
726
727 default:
728 break;
729 }
730
731 fmt = GET_RTX_FORMAT (code);
732 len = GET_RTX_LENGTH (code);
733 for (i = 0; i < len; i++)
734 {
735 switch (fmt[i])
736 {
737 case 'e': case 'u':
738 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
739 break;
740
741 case 'E':
742 for (j = 0; j < XVECLEN (pattern, i); j++)
743 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
744 break;
745
746 case 'i': case 'w': case '0': case 's':
747 break;
748
749 default:
750 abort ();
751 }
752 }
753 }
754
755 /* Create a chain of nodes to verify that an rtl expression matches
756 PATTERN.
757
758 LAST is a pointer to the listhead in the previous node in the chain (or
759 in the calling function, for the first node).
760
761 POSITION is the string representing the current position in the insn.
762
763 INSN_TYPE is the type of insn for which we are emitting code.
764
765 A pointer to the final node in the chain is returned. */
766
767 static struct decision *
add_to_sequence(rtx pattern,struct decision_head * last,const char * position,enum routine_type insn_type,int top)768 add_to_sequence (rtx pattern, struct decision_head *last, const char *position,
769 enum routine_type insn_type, int top)
770 {
771 RTX_CODE code;
772 struct decision *this, *sub;
773 struct decision_test *test;
774 struct decision_test **place;
775 char *subpos;
776 size_t i;
777 const char *fmt;
778 int depth = strlen (position);
779 int len;
780 enum machine_mode mode;
781
782 if (depth > max_depth)
783 max_depth = depth;
784
785 subpos = xmalloc (depth + 2);
786 strcpy (subpos, position);
787 subpos[depth + 1] = 0;
788
789 sub = this = new_decision (position, last);
790 place = &this->tests;
791
792 restart:
793 mode = GET_MODE (pattern);
794 code = GET_CODE (pattern);
795
796 switch (code)
797 {
798 case PARALLEL:
799 /* Toplevel peephole pattern. */
800 if (insn_type == PEEPHOLE2 && top)
801 {
802 /* We don't need the node we just created -- unlink it. */
803 last->first = last->last = NULL;
804
805 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
806 {
807 /* Which insn we're looking at is represented by A-Z. We don't
808 ever use 'A', however; it is always implied. */
809
810 subpos[depth] = (i > 0 ? 'A' + i : 0);
811 sub = add_to_sequence (XVECEXP (pattern, 0, i),
812 last, subpos, insn_type, 0);
813 last = &sub->success;
814 }
815 goto ret;
816 }
817
818 /* Else nothing special. */
819 break;
820
821 case MATCH_PARALLEL:
822 /* The explicit patterns within a match_parallel enforce a minimum
823 length on the vector. The match_parallel predicate may allow
824 for more elements. We do need to check for this minimum here
825 or the code generated to match the internals may reference data
826 beyond the end of the vector. */
827 test = new_decision_test (DT_veclen_ge, &place);
828 test->u.veclen = XVECLEN (pattern, 2);
829 /* Fall through. */
830
831 case MATCH_OPERAND:
832 case MATCH_SCRATCH:
833 case MATCH_OPERATOR:
834 case MATCH_INSN:
835 {
836 const char *pred_name;
837 RTX_CODE was_code = code;
838 int allows_const_int = 1;
839
840 if (code == MATCH_SCRATCH)
841 {
842 pred_name = "scratch_operand";
843 code = UNKNOWN;
844 }
845 else
846 {
847 pred_name = XSTR (pattern, 1);
848 if (code == MATCH_PARALLEL)
849 code = PARALLEL;
850 else
851 code = UNKNOWN;
852 }
853
854 if (pred_name[0] != 0)
855 {
856 test = new_decision_test (DT_pred, &place);
857 test->u.pred.name = pred_name;
858 test->u.pred.mode = mode;
859
860 /* See if we know about this predicate and save its number.
861 If we do, and it only accepts one code, note that fact.
862
863 If we know that the predicate does not allow CONST_INT,
864 we know that the only way the predicate can match is if
865 the modes match (here we use the kludge of relying on the
866 fact that "address_operand" accepts CONST_INT; otherwise,
867 it would have to be a special case), so we can test the
868 mode (but we need not). This fact should considerably
869 simplify the generated code. */
870
871 for (i = 0; i < NUM_KNOWN_PREDS; i++)
872 if (! strcmp (preds[i].name, pred_name))
873 break;
874
875 if (i < NUM_KNOWN_PREDS)
876 {
877 int j;
878
879 test->u.pred.index = i;
880
881 if (preds[i].codes[1] == 0 && code == UNKNOWN)
882 code = preds[i].codes[0];
883
884 allows_const_int = 0;
885 for (j = 0; preds[i].codes[j] != 0; j++)
886 if (preds[i].codes[j] == CONST_INT)
887 {
888 allows_const_int = 1;
889 break;
890 }
891 }
892 else
893 test->u.pred.index = -1;
894 }
895
896 /* Can't enforce a mode if we allow const_int. */
897 if (allows_const_int)
898 mode = VOIDmode;
899
900 /* Accept the operand, ie. record it in `operands'. */
901 test = new_decision_test (DT_accept_op, &place);
902 test->u.opno = XINT (pattern, 0);
903
904 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
905 {
906 char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
907 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
908 {
909 subpos[depth] = i + base;
910 sub = add_to_sequence (XVECEXP (pattern, 2, i),
911 &sub->success, subpos, insn_type, 0);
912 }
913 }
914 goto fini;
915 }
916
917 case MATCH_OP_DUP:
918 code = UNKNOWN;
919
920 test = new_decision_test (DT_dup, &place);
921 test->u.dup = XINT (pattern, 0);
922
923 test = new_decision_test (DT_accept_op, &place);
924 test->u.opno = XINT (pattern, 0);
925
926 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
927 {
928 subpos[depth] = i + '0';
929 sub = add_to_sequence (XVECEXP (pattern, 1, i),
930 &sub->success, subpos, insn_type, 0);
931 }
932 goto fini;
933
934 case MATCH_DUP:
935 case MATCH_PAR_DUP:
936 code = UNKNOWN;
937
938 test = new_decision_test (DT_dup, &place);
939 test->u.dup = XINT (pattern, 0);
940 goto fini;
941
942 case ADDRESS:
943 pattern = XEXP (pattern, 0);
944 goto restart;
945
946 default:
947 break;
948 }
949
950 fmt = GET_RTX_FORMAT (code);
951 len = GET_RTX_LENGTH (code);
952
953 /* Do tests against the current node first. */
954 for (i = 0; i < (size_t) len; i++)
955 {
956 if (fmt[i] == 'i')
957 {
958 if (i == 0)
959 {
960 test = new_decision_test (DT_elt_zero_int, &place);
961 test->u.intval = XINT (pattern, i);
962 }
963 else if (i == 1)
964 {
965 test = new_decision_test (DT_elt_one_int, &place);
966 test->u.intval = XINT (pattern, i);
967 }
968 else
969 abort ();
970 }
971 else if (fmt[i] == 'w')
972 {
973 /* If this value actually fits in an int, we can use a switch
974 statement here, so indicate that. */
975 enum decision_type type
976 = ((int) XWINT (pattern, i) == XWINT (pattern, i))
977 ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
978
979 if (i != 0)
980 abort ();
981
982 test = new_decision_test (type, &place);
983 test->u.intval = XWINT (pattern, i);
984 }
985 else if (fmt[i] == 'E')
986 {
987 if (i != 0)
988 abort ();
989
990 test = new_decision_test (DT_veclen, &place);
991 test->u.veclen = XVECLEN (pattern, i);
992 }
993 }
994
995 /* Now test our sub-patterns. */
996 for (i = 0; i < (size_t) len; i++)
997 {
998 switch (fmt[i])
999 {
1000 case 'e': case 'u':
1001 subpos[depth] = '0' + i;
1002 sub = add_to_sequence (XEXP (pattern, i), &sub->success,
1003 subpos, insn_type, 0);
1004 break;
1005
1006 case 'E':
1007 {
1008 int j;
1009 for (j = 0; j < XVECLEN (pattern, i); j++)
1010 {
1011 subpos[depth] = 'a' + j;
1012 sub = add_to_sequence (XVECEXP (pattern, i, j),
1013 &sub->success, subpos, insn_type, 0);
1014 }
1015 break;
1016 }
1017
1018 case 'i': case 'w':
1019 /* Handled above. */
1020 break;
1021 case '0':
1022 break;
1023
1024 default:
1025 abort ();
1026 }
1027 }
1028
1029 fini:
1030 /* Insert nodes testing mode and code, if they're still relevant,
1031 before any of the nodes we may have added above. */
1032 if (code != UNKNOWN)
1033 {
1034 place = &this->tests;
1035 test = new_decision_test (DT_code, &place);
1036 test->u.code = code;
1037 }
1038
1039 if (mode != VOIDmode)
1040 {
1041 place = &this->tests;
1042 test = new_decision_test (DT_mode, &place);
1043 test->u.mode = mode;
1044 }
1045
1046 /* If we didn't insert any tests or accept nodes, hork. */
1047 if (this->tests == NULL)
1048 abort ();
1049
1050 ret:
1051 free (subpos);
1052 return sub;
1053 }
1054
1055 /* A subroutine of maybe_both_true; examines only one test.
1056 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1057
1058 static int
maybe_both_true_2(struct decision_test * d1,struct decision_test * d2)1059 maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
1060 {
1061 if (d1->type == d2->type)
1062 {
1063 switch (d1->type)
1064 {
1065 case DT_mode:
1066 return d1->u.mode == d2->u.mode;
1067
1068 case DT_code:
1069 return d1->u.code == d2->u.code;
1070
1071 case DT_veclen:
1072 return d1->u.veclen == d2->u.veclen;
1073
1074 case DT_elt_zero_int:
1075 case DT_elt_one_int:
1076 case DT_elt_zero_wide:
1077 case DT_elt_zero_wide_safe:
1078 return d1->u.intval == d2->u.intval;
1079
1080 default:
1081 break;
1082 }
1083 }
1084
1085 /* If either has a predicate that we know something about, set
1086 things up so that D1 is the one that always has a known
1087 predicate. Then see if they have any codes in common. */
1088
1089 if (d1->type == DT_pred || d2->type == DT_pred)
1090 {
1091 if (d2->type == DT_pred)
1092 {
1093 struct decision_test *tmp;
1094 tmp = d1, d1 = d2, d2 = tmp;
1095 }
1096
1097 /* If D2 tests a mode, see if it matches D1. */
1098 if (d1->u.pred.mode != VOIDmode)
1099 {
1100 if (d2->type == DT_mode)
1101 {
1102 if (d1->u.pred.mode != d2->u.mode
1103 /* The mode of an address_operand predicate is the
1104 mode of the memory, not the operand. It can only
1105 be used for testing the predicate, so we must
1106 ignore it here. */
1107 && strcmp (d1->u.pred.name, "address_operand") != 0)
1108 return 0;
1109 }
1110 /* Don't check two predicate modes here, because if both predicates
1111 accept CONST_INT, then both can still be true even if the modes
1112 are different. If they don't accept CONST_INT, there will be a
1113 separate DT_mode that will make maybe_both_true_1 return 0. */
1114 }
1115
1116 if (d1->u.pred.index >= 0)
1117 {
1118 /* If D2 tests a code, see if it is in the list of valid
1119 codes for D1's predicate. */
1120 if (d2->type == DT_code)
1121 {
1122 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
1123 while (*c != 0)
1124 {
1125 if (*c == d2->u.code)
1126 break;
1127 ++c;
1128 }
1129 if (*c == 0)
1130 return 0;
1131 }
1132
1133 /* Otherwise see if the predicates have any codes in common. */
1134 else if (d2->type == DT_pred && d2->u.pred.index >= 0)
1135 {
1136 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
1137 int common = 0;
1138
1139 while (*c1 != 0 && !common)
1140 {
1141 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
1142 while (*c2 != 0 && !common)
1143 {
1144 common = (*c1 == *c2);
1145 ++c2;
1146 }
1147 ++c1;
1148 }
1149
1150 if (!common)
1151 return 0;
1152 }
1153 }
1154 }
1155
1156 /* Tests vs veclen may be known when strict equality is involved. */
1157 if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1158 return d1->u.veclen >= d2->u.veclen;
1159 if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1160 return d2->u.veclen >= d1->u.veclen;
1161
1162 return -1;
1163 }
1164
1165 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1166 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
1167
1168 static int
maybe_both_true_1(struct decision_test * d1,struct decision_test * d2)1169 maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
1170 {
1171 struct decision_test *t1, *t2;
1172
1173 /* A match_operand with no predicate can match anything. Recognize
1174 this by the existence of a lone DT_accept_op test. */
1175 if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1176 return 1;
1177
1178 /* Eliminate pairs of tests while they can exactly match. */
1179 while (d1 && d2 && d1->type == d2->type)
1180 {
1181 if (maybe_both_true_2 (d1, d2) == 0)
1182 return 0;
1183 d1 = d1->next, d2 = d2->next;
1184 }
1185
1186 /* After that, consider all pairs. */
1187 for (t1 = d1; t1 ; t1 = t1->next)
1188 for (t2 = d2; t2 ; t2 = t2->next)
1189 if (maybe_both_true_2 (t1, t2) == 0)
1190 return 0;
1191
1192 return -1;
1193 }
1194
1195 /* Return 0 if we can prove that there is no RTL that can match both
1196 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
1197 can match both or just that we couldn't prove there wasn't such an RTL).
1198
1199 TOPLEVEL is nonzero if we are to only look at the top level and not
1200 recursively descend. */
1201
1202 static int
maybe_both_true(struct decision * d1,struct decision * d2,int toplevel)1203 maybe_both_true (struct decision *d1, struct decision *d2,
1204 int toplevel)
1205 {
1206 struct decision *p1, *p2;
1207 int cmp;
1208
1209 /* Don't compare strings on the different positions in insn. Doing so
1210 is incorrect and results in false matches from constructs like
1211
1212 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1213 (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1214 vs
1215 [(set (match_operand:HI "register_operand" "r")
1216 (match_operand:HI "register_operand" "r"))]
1217
1218 If we are presented with such, we are recursing through the remainder
1219 of a node's success nodes (from the loop at the end of this function).
1220 Skip forward until we come to a position that matches.
1221
1222 Due to the way position strings are constructed, we know that iterating
1223 forward from the lexically lower position (e.g. "00") will run into
1224 the lexically higher position (e.g. "1") and not the other way around.
1225 This saves a bit of effort. */
1226
1227 cmp = strcmp (d1->position, d2->position);
1228 if (cmp != 0)
1229 {
1230 if (toplevel)
1231 abort ();
1232
1233 /* If the d2->position was lexically lower, swap. */
1234 if (cmp > 0)
1235 p1 = d1, d1 = d2, d2 = p1;
1236
1237 if (d1->success.first == 0)
1238 return 1;
1239 for (p1 = d1->success.first; p1; p1 = p1->next)
1240 if (maybe_both_true (p1, d2, 0))
1241 return 1;
1242
1243 return 0;
1244 }
1245
1246 /* Test the current level. */
1247 cmp = maybe_both_true_1 (d1->tests, d2->tests);
1248 if (cmp >= 0)
1249 return cmp;
1250
1251 /* We can't prove that D1 and D2 cannot both be true. If we are only
1252 to check the top level, return 1. Otherwise, see if we can prove
1253 that all choices in both successors are mutually exclusive. If
1254 either does not have any successors, we can't prove they can't both
1255 be true. */
1256
1257 if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1258 return 1;
1259
1260 for (p1 = d1->success.first; p1; p1 = p1->next)
1261 for (p2 = d2->success.first; p2; p2 = p2->next)
1262 if (maybe_both_true (p1, p2, 0))
1263 return 1;
1264
1265 return 0;
1266 }
1267
1268 /* A subroutine of nodes_identical. Examine two tests for equivalence. */
1269
1270 static int
nodes_identical_1(struct decision_test * d1,struct decision_test * d2)1271 nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
1272 {
1273 switch (d1->type)
1274 {
1275 case DT_mode:
1276 return d1->u.mode == d2->u.mode;
1277
1278 case DT_code:
1279 return d1->u.code == d2->u.code;
1280
1281 case DT_pred:
1282 return (d1->u.pred.mode == d2->u.pred.mode
1283 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1284
1285 case DT_c_test:
1286 return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1287
1288 case DT_veclen:
1289 case DT_veclen_ge:
1290 return d1->u.veclen == d2->u.veclen;
1291
1292 case DT_dup:
1293 return d1->u.dup == d2->u.dup;
1294
1295 case DT_elt_zero_int:
1296 case DT_elt_one_int:
1297 case DT_elt_zero_wide:
1298 case DT_elt_zero_wide_safe:
1299 return d1->u.intval == d2->u.intval;
1300
1301 case DT_accept_op:
1302 return d1->u.opno == d2->u.opno;
1303
1304 case DT_accept_insn:
1305 /* Differences will be handled in merge_accept_insn. */
1306 return 1;
1307
1308 default:
1309 abort ();
1310 }
1311 }
1312
1313 /* True iff the two nodes are identical (on one level only). Due
1314 to the way these lists are constructed, we shouldn't have to
1315 consider different orderings on the tests. */
1316
1317 static int
nodes_identical(struct decision * d1,struct decision * d2)1318 nodes_identical (struct decision *d1, struct decision *d2)
1319 {
1320 struct decision_test *t1, *t2;
1321
1322 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1323 {
1324 if (t1->type != t2->type)
1325 return 0;
1326 if (! nodes_identical_1 (t1, t2))
1327 return 0;
1328 }
1329
1330 /* For success, they should now both be null. */
1331 if (t1 != t2)
1332 return 0;
1333
1334 /* Check that their subnodes are at the same position, as any one set
1335 of sibling decisions must be at the same position. Allowing this
1336 requires complications to find_afterward and when change_state is
1337 invoked. */
1338 if (d1->success.first
1339 && d2->success.first
1340 && strcmp (d1->success.first->position, d2->success.first->position))
1341 return 0;
1342
1343 return 1;
1344 }
1345
1346 /* A subroutine of merge_trees; given two nodes that have been declared
1347 identical, cope with two insn accept states. If they differ in the
1348 number of clobbers, then the conflict was created by make_insn_sequence
1349 and we can drop the with-clobbers version on the floor. If both
1350 nodes have no additional clobbers, we have found an ambiguity in the
1351 source machine description. */
1352
1353 static void
merge_accept_insn(struct decision * oldd,struct decision * addd)1354 merge_accept_insn (struct decision *oldd, struct decision *addd)
1355 {
1356 struct decision_test *old, *add;
1357
1358 for (old = oldd->tests; old; old = old->next)
1359 if (old->type == DT_accept_insn)
1360 break;
1361 if (old == NULL)
1362 return;
1363
1364 for (add = addd->tests; add; add = add->next)
1365 if (add->type == DT_accept_insn)
1366 break;
1367 if (add == NULL)
1368 return;
1369
1370 /* If one node is for a normal insn and the second is for the base
1371 insn with clobbers stripped off, the second node should be ignored. */
1372
1373 if (old->u.insn.num_clobbers_to_add == 0
1374 && add->u.insn.num_clobbers_to_add > 0)
1375 {
1376 /* Nothing to do here. */
1377 }
1378 else if (old->u.insn.num_clobbers_to_add > 0
1379 && add->u.insn.num_clobbers_to_add == 0)
1380 {
1381 /* In this case, replace OLD with ADD. */
1382 old->u.insn = add->u.insn;
1383 }
1384 else
1385 {
1386 message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1387 get_insn_name (add->u.insn.code_number),
1388 get_insn_name (old->u.insn.code_number));
1389 message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1390 get_insn_name (old->u.insn.code_number));
1391 error_count++;
1392 }
1393 }
1394
1395 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
1396
1397 static void
merge_trees(struct decision_head * oldh,struct decision_head * addh)1398 merge_trees (struct decision_head *oldh, struct decision_head *addh)
1399 {
1400 struct decision *next, *add;
1401
1402 if (addh->first == 0)
1403 return;
1404 if (oldh->first == 0)
1405 {
1406 *oldh = *addh;
1407 return;
1408 }
1409
1410 /* Trying to merge bits at different positions isn't possible. */
1411 if (strcmp (oldh->first->position, addh->first->position))
1412 abort ();
1413
1414 for (add = addh->first; add ; add = next)
1415 {
1416 struct decision *old, *insert_before = NULL;
1417
1418 next = add->next;
1419
1420 /* The semantics of pattern matching state that the tests are
1421 done in the order given in the MD file so that if an insn
1422 matches two patterns, the first one will be used. However,
1423 in practice, most, if not all, patterns are unambiguous so
1424 that their order is independent. In that case, we can merge
1425 identical tests and group all similar modes and codes together.
1426
1427 Scan starting from the end of OLDH until we reach a point
1428 where we reach the head of the list or where we pass a
1429 pattern that could also be true if NEW is true. If we find
1430 an identical pattern, we can merge them. Also, record the
1431 last node that tests the same code and mode and the last one
1432 that tests just the same mode.
1433
1434 If we have no match, place NEW after the closest match we found. */
1435
1436 for (old = oldh->last; old; old = old->prev)
1437 {
1438 if (nodes_identical (old, add))
1439 {
1440 merge_accept_insn (old, add);
1441 merge_trees (&old->success, &add->success);
1442 goto merged_nodes;
1443 }
1444
1445 if (maybe_both_true (old, add, 0))
1446 break;
1447
1448 /* Insert the nodes in DT test type order, which is roughly
1449 how expensive/important the test is. Given that the tests
1450 are also ordered within the list, examining the first is
1451 sufficient. */
1452 if ((int) add->tests->type < (int) old->tests->type)
1453 insert_before = old;
1454 }
1455
1456 if (insert_before == NULL)
1457 {
1458 add->next = NULL;
1459 add->prev = oldh->last;
1460 oldh->last->next = add;
1461 oldh->last = add;
1462 }
1463 else
1464 {
1465 if ((add->prev = insert_before->prev) != NULL)
1466 add->prev->next = add;
1467 else
1468 oldh->first = add;
1469 add->next = insert_before;
1470 insert_before->prev = add;
1471 }
1472
1473 merged_nodes:;
1474 }
1475 }
1476
1477 /* Walk the tree looking for sub-nodes that perform common tests.
1478 Factor out the common test into a new node. This enables us
1479 (depending on the test type) to emit switch statements later. */
1480
1481 static void
factor_tests(struct decision_head * head)1482 factor_tests (struct decision_head *head)
1483 {
1484 struct decision *first, *next;
1485
1486 for (first = head->first; first && first->next; first = next)
1487 {
1488 enum decision_type type;
1489 struct decision *new, *old_last;
1490
1491 type = first->tests->type;
1492 next = first->next;
1493
1494 /* Want at least two compatible sequential nodes. */
1495 if (next->tests->type != type)
1496 continue;
1497
1498 /* Don't want all node types, just those we can turn into
1499 switch statements. */
1500 if (type != DT_mode
1501 && type != DT_code
1502 && type != DT_veclen
1503 && type != DT_elt_zero_int
1504 && type != DT_elt_one_int
1505 && type != DT_elt_zero_wide_safe)
1506 continue;
1507
1508 /* If we'd been performing more than one test, create a new node
1509 below our first test. */
1510 if (first->tests->next != NULL)
1511 {
1512 new = new_decision (first->position, &first->success);
1513 new->tests = first->tests->next;
1514 first->tests->next = NULL;
1515 }
1516
1517 /* Crop the node tree off after our first test. */
1518 first->next = NULL;
1519 old_last = head->last;
1520 head->last = first;
1521
1522 /* For each compatible test, adjust to perform only one test in
1523 the top level node, then merge the node back into the tree. */
1524 do
1525 {
1526 struct decision_head h;
1527
1528 if (next->tests->next != NULL)
1529 {
1530 new = new_decision (next->position, &next->success);
1531 new->tests = next->tests->next;
1532 next->tests->next = NULL;
1533 }
1534 new = next;
1535 next = next->next;
1536 new->next = NULL;
1537 h.first = h.last = new;
1538
1539 merge_trees (head, &h);
1540 }
1541 while (next && next->tests->type == type);
1542
1543 /* After we run out of compatible tests, graft the remaining nodes
1544 back onto the tree. */
1545 if (next)
1546 {
1547 next->prev = head->last;
1548 head->last->next = next;
1549 head->last = old_last;
1550 }
1551 }
1552
1553 /* Recurse. */
1554 for (first = head->first; first; first = first->next)
1555 factor_tests (&first->success);
1556 }
1557
1558 /* After factoring, try to simplify the tests on any one node.
1559 Tests that are useful for switch statements are recognizable
1560 by having only a single test on a node -- we'll be manipulating
1561 nodes with multiple tests:
1562
1563 If we have mode tests or code tests that are redundant with
1564 predicates, remove them. */
1565
1566 static void
simplify_tests(struct decision_head * head)1567 simplify_tests (struct decision_head *head)
1568 {
1569 struct decision *tree;
1570
1571 for (tree = head->first; tree; tree = tree->next)
1572 {
1573 struct decision_test *a, *b;
1574
1575 a = tree->tests;
1576 b = a->next;
1577 if (b == NULL)
1578 continue;
1579
1580 /* Find a predicate node. */
1581 while (b && b->type != DT_pred)
1582 b = b->next;
1583 if (b)
1584 {
1585 /* Due to how these tests are constructed, we don't even need
1586 to check that the mode and code are compatible -- they were
1587 generated from the predicate in the first place. */
1588 while (a->type == DT_mode || a->type == DT_code)
1589 a = a->next;
1590 tree->tests = a;
1591 }
1592 }
1593
1594 /* Recurse. */
1595 for (tree = head->first; tree; tree = tree->next)
1596 simplify_tests (&tree->success);
1597 }
1598
1599 /* Count the number of subnodes of HEAD. If the number is high enough,
1600 make the first node in HEAD start a separate subroutine in the C code
1601 that is generated. */
1602
1603 static int
break_out_subroutines(struct decision_head * head,int initial)1604 break_out_subroutines (struct decision_head *head, int initial)
1605 {
1606 int size = 0;
1607 struct decision *sub;
1608
1609 for (sub = head->first; sub; sub = sub->next)
1610 size += 1 + break_out_subroutines (&sub->success, 0);
1611
1612 if (size > SUBROUTINE_THRESHOLD && ! initial)
1613 {
1614 head->first->subroutine_number = ++next_subroutine_number;
1615 size = 1;
1616 }
1617 return size;
1618 }
1619
1620 /* For each node p, find the next alternative that might be true
1621 when p is true. */
1622
1623 static void
find_afterward(struct decision_head * head,struct decision * real_afterward)1624 find_afterward (struct decision_head *head, struct decision *real_afterward)
1625 {
1626 struct decision *p, *q, *afterward;
1627
1628 /* We can't propagate alternatives across subroutine boundaries.
1629 This is not incorrect, merely a minor optimization loss. */
1630
1631 p = head->first;
1632 afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1633
1634 for ( ; p ; p = p->next)
1635 {
1636 /* Find the next node that might be true if this one fails. */
1637 for (q = p->next; q ; q = q->next)
1638 if (maybe_both_true (p, q, 1))
1639 break;
1640
1641 /* If we reached the end of the list without finding one,
1642 use the incoming afterward position. */
1643 if (!q)
1644 q = afterward;
1645 p->afterward = q;
1646 if (q)
1647 q->need_label = 1;
1648 }
1649
1650 /* Recurse. */
1651 for (p = head->first; p ; p = p->next)
1652 if (p->success.first)
1653 find_afterward (&p->success, p->afterward);
1654
1655 /* When we are generating a subroutine, record the real afterward
1656 position in the first node where write_tree can find it, and we
1657 can do the right thing at the subroutine call site. */
1658 p = head->first;
1659 if (p->subroutine_number > 0)
1660 p->afterward = real_afterward;
1661 }
1662
1663 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1664 actions are necessary to move to NEWPOS. If we fail to move to the
1665 new state, branch to node AFTERWARD if nonzero, otherwise return.
1666
1667 Failure to move to the new state can only occur if we are trying to
1668 match multiple insns and we try to step past the end of the stream. */
1669
1670 static void
change_state(const char * oldpos,const char * newpos,struct decision * afterward,const char * indent)1671 change_state (const char *oldpos, const char *newpos,
1672 struct decision *afterward, const char *indent)
1673 {
1674 int odepth = strlen (oldpos);
1675 int ndepth = strlen (newpos);
1676 int depth;
1677 int old_has_insn, new_has_insn;
1678
1679 /* Pop up as many levels as necessary. */
1680 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
1681 continue;
1682
1683 /* Hunt for the last [A-Z] in both strings. */
1684 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
1685 if (ISUPPER (oldpos[old_has_insn]))
1686 break;
1687 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
1688 if (ISUPPER (newpos[new_has_insn]))
1689 break;
1690
1691 /* Go down to desired level. */
1692 while (depth < ndepth)
1693 {
1694 /* It's a different insn from the first one. */
1695 if (ISUPPER (newpos[depth]))
1696 {
1697 /* We can only fail if we're moving down the tree. */
1698 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
1699 {
1700 printf ("%stem = peep2_next_insn (%d);\n",
1701 indent, newpos[depth] - 'A');
1702 }
1703 else
1704 {
1705 printf ("%stem = peep2_next_insn (%d);\n",
1706 indent, newpos[depth] - 'A');
1707 printf ("%sif (tem == NULL_RTX)\n", indent);
1708 if (afterward)
1709 printf ("%s goto L%d;\n", indent, afterward->number);
1710 else
1711 printf ("%s goto ret0;\n", indent);
1712 }
1713 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
1714 }
1715 else if (ISLOWER (newpos[depth]))
1716 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1717 indent, depth + 1, depth, newpos[depth] - 'a');
1718 else
1719 printf ("%sx%d = XEXP (x%d, %c);\n",
1720 indent, depth + 1, depth, newpos[depth]);
1721 ++depth;
1722 }
1723 }
1724
1725 /* Print the enumerator constant for CODE -- the upcase version of
1726 the name. */
1727
1728 static void
print_code(enum rtx_code code)1729 print_code (enum rtx_code code)
1730 {
1731 const char *p;
1732 for (p = GET_RTX_NAME (code); *p; p++)
1733 putchar (TOUPPER (*p));
1734 }
1735
1736 /* Emit code to cross an afterward link -- change state and branch. */
1737
1738 static void
write_afterward(struct decision * start,struct decision * afterward,const char * indent)1739 write_afterward (struct decision *start, struct decision *afterward,
1740 const char *indent)
1741 {
1742 if (!afterward || start->subroutine_number > 0)
1743 printf("%sgoto ret0;\n", indent);
1744 else
1745 {
1746 change_state (start->position, afterward->position, NULL, indent);
1747 printf ("%sgoto L%d;\n", indent, afterward->number);
1748 }
1749 }
1750
1751 /* Emit a HOST_WIDE_INT as an integer constant expression. We need to take
1752 special care to avoid "decimal constant is so large that it is unsigned"
1753 warnings in the resulting code. */
1754
1755 static void
print_host_wide_int(HOST_WIDE_INT val)1756 print_host_wide_int (HOST_WIDE_INT val)
1757 {
1758 HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
1759 if (val == min)
1760 printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
1761 else
1762 printf (HOST_WIDE_INT_PRINT_DEC_C, val);
1763 }
1764
1765 /* Emit a switch statement, if possible, for an initial sequence of
1766 nodes at START. Return the first node yet untested. */
1767
1768 static struct decision *
write_switch(struct decision * start,int depth)1769 write_switch (struct decision *start, int depth)
1770 {
1771 struct decision *p = start;
1772 enum decision_type type = p->tests->type;
1773 struct decision *needs_label = NULL;
1774
1775 /* If we have two or more nodes in sequence that test the same one
1776 thing, we may be able to use a switch statement. */
1777
1778 if (!p->next
1779 || p->tests->next
1780 || p->next->tests->type != type
1781 || p->next->tests->next
1782 || nodes_identical_1 (p->tests, p->next->tests))
1783 return p;
1784
1785 /* DT_code is special in that we can do interesting things with
1786 known predicates at the same time. */
1787 if (type == DT_code)
1788 {
1789 char codemap[NUM_RTX_CODE];
1790 struct decision *ret;
1791 RTX_CODE code;
1792
1793 memset (codemap, 0, sizeof(codemap));
1794
1795 printf (" switch (GET_CODE (x%d))\n {\n", depth);
1796 code = p->tests->u.code;
1797 do
1798 {
1799 if (p != start && p->need_label && needs_label == NULL)
1800 needs_label = p;
1801
1802 printf (" case ");
1803 print_code (code);
1804 printf (":\n goto L%d;\n", p->success.first->number);
1805 p->success.first->need_label = 1;
1806
1807 codemap[code] = 1;
1808 p = p->next;
1809 }
1810 while (p
1811 && ! p->tests->next
1812 && p->tests->type == DT_code
1813 && ! codemap[code = p->tests->u.code]);
1814
1815 /* If P is testing a predicate that we know about and we haven't
1816 seen any of the codes that are valid for the predicate, we can
1817 write a series of "case" statement, one for each possible code.
1818 Since we are already in a switch, these redundant tests are very
1819 cheap and will reduce the number of predicates called. */
1820
1821 /* Note that while we write out cases for these predicates here,
1822 we don't actually write the test here, as it gets kinda messy.
1823 It is trivial to leave this to later by telling our caller that
1824 we only processed the CODE tests. */
1825 if (needs_label != NULL)
1826 ret = needs_label;
1827 else
1828 ret = p;
1829
1830 while (p && p->tests->type == DT_pred
1831 && p->tests->u.pred.index >= 0)
1832 {
1833 const RTX_CODE *c;
1834
1835 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1836 if (codemap[(int) *c] != 0)
1837 goto pred_done;
1838
1839 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
1840 {
1841 printf (" case ");
1842 print_code (*c);
1843 printf (":\n");
1844 codemap[(int) *c] = 1;
1845 }
1846
1847 printf (" goto L%d;\n", p->number);
1848 p->need_label = 1;
1849 p = p->next;
1850 }
1851
1852 pred_done:
1853 /* Make the default case skip the predicates we managed to match. */
1854
1855 printf (" default:\n");
1856 if (p != ret)
1857 {
1858 if (p)
1859 {
1860 printf (" goto L%d;\n", p->number);
1861 p->need_label = 1;
1862 }
1863 else
1864 write_afterward (start, start->afterward, " ");
1865 }
1866 else
1867 printf (" break;\n");
1868 printf (" }\n");
1869
1870 return ret;
1871 }
1872 else if (type == DT_mode
1873 || type == DT_veclen
1874 || type == DT_elt_zero_int
1875 || type == DT_elt_one_int
1876 || type == DT_elt_zero_wide_safe)
1877 {
1878 const char *indent = "";
1879
1880 /* We cast switch parameter to integer, so we must ensure that the value
1881 fits. */
1882 if (type == DT_elt_zero_wide_safe)
1883 {
1884 indent = " ";
1885 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
1886 }
1887 printf ("%s switch (", indent);
1888 switch (type)
1889 {
1890 case DT_mode:
1891 printf ("GET_MODE (x%d)", depth);
1892 break;
1893 case DT_veclen:
1894 printf ("XVECLEN (x%d, 0)", depth);
1895 break;
1896 case DT_elt_zero_int:
1897 printf ("XINT (x%d, 0)", depth);
1898 break;
1899 case DT_elt_one_int:
1900 printf ("XINT (x%d, 1)", depth);
1901 break;
1902 case DT_elt_zero_wide_safe:
1903 /* Convert result of XWINT to int for portability since some C
1904 compilers won't do it and some will. */
1905 printf ("(int) XWINT (x%d, 0)", depth);
1906 break;
1907 default:
1908 abort ();
1909 }
1910 printf (")\n%s {\n", indent);
1911
1912 do
1913 {
1914 /* Merge trees will not unify identical nodes if their
1915 sub-nodes are at different levels. Thus we must check
1916 for duplicate cases. */
1917 struct decision *q;
1918 for (q = start; q != p; q = q->next)
1919 if (nodes_identical_1 (p->tests, q->tests))
1920 goto case_done;
1921
1922 if (p != start && p->need_label && needs_label == NULL)
1923 needs_label = p;
1924
1925 printf ("%s case ", indent);
1926 switch (type)
1927 {
1928 case DT_mode:
1929 printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1930 break;
1931 case DT_veclen:
1932 printf ("%d", p->tests->u.veclen);
1933 break;
1934 case DT_elt_zero_int:
1935 case DT_elt_one_int:
1936 case DT_elt_zero_wide:
1937 case DT_elt_zero_wide_safe:
1938 print_host_wide_int (p->tests->u.intval);
1939 break;
1940 default:
1941 abort ();
1942 }
1943 printf (":\n%s goto L%d;\n", indent, p->success.first->number);
1944 p->success.first->need_label = 1;
1945
1946 p = p->next;
1947 }
1948 while (p && p->tests->type == type && !p->tests->next);
1949
1950 case_done:
1951 printf ("%s default:\n%s break;\n%s }\n",
1952 indent, indent, indent);
1953
1954 return needs_label != NULL ? needs_label : p;
1955 }
1956 else
1957 {
1958 /* None of the other tests are amenable. */
1959 return p;
1960 }
1961 }
1962
1963 /* Emit code for one test. */
1964
1965 static void
write_cond(struct decision_test * p,int depth,enum routine_type subroutine_type)1966 write_cond (struct decision_test *p, int depth,
1967 enum routine_type subroutine_type)
1968 {
1969 switch (p->type)
1970 {
1971 case DT_mode:
1972 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1973 break;
1974
1975 case DT_code:
1976 printf ("GET_CODE (x%d) == ", depth);
1977 print_code (p->u.code);
1978 break;
1979
1980 case DT_veclen:
1981 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1982 break;
1983
1984 case DT_elt_zero_int:
1985 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1986 break;
1987
1988 case DT_elt_one_int:
1989 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1990 break;
1991
1992 case DT_elt_zero_wide:
1993 case DT_elt_zero_wide_safe:
1994 printf ("XWINT (x%d, 0) == ", depth);
1995 print_host_wide_int (p->u.intval);
1996 break;
1997
1998 case DT_veclen_ge:
1999 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
2000 break;
2001
2002 case DT_dup:
2003 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
2004 break;
2005
2006 case DT_pred:
2007 printf ("%s (x%d, %smode)", p->u.pred.name, depth,
2008 GET_MODE_NAME (p->u.pred.mode));
2009 break;
2010
2011 case DT_c_test:
2012 printf ("(%s)", p->u.c_test);
2013 break;
2014
2015 case DT_accept_insn:
2016 switch (subroutine_type)
2017 {
2018 case RECOG:
2019 if (p->u.insn.num_clobbers_to_add == 0)
2020 abort ();
2021 printf ("pnum_clobbers != NULL");
2022 break;
2023
2024 default:
2025 abort ();
2026 }
2027 break;
2028
2029 default:
2030 abort ();
2031 }
2032 }
2033
2034 /* Emit code for one action. The previous tests have succeeded;
2035 TEST is the last of the chain. In the normal case we simply
2036 perform a state change. For the `accept' tests we must do more work. */
2037
2038 static void
write_action(struct decision * p,struct decision_test * test,int depth,int uncond,struct decision * success,enum routine_type subroutine_type)2039 write_action (struct decision *p, struct decision_test *test,
2040 int depth, int uncond, struct decision *success,
2041 enum routine_type subroutine_type)
2042 {
2043 const char *indent;
2044 int want_close = 0;
2045
2046 if (uncond)
2047 indent = " ";
2048 else if (test->type == DT_accept_op || test->type == DT_accept_insn)
2049 {
2050 fputs (" {\n", stdout);
2051 indent = " ";
2052 want_close = 1;
2053 }
2054 else
2055 indent = " ";
2056
2057 if (test->type == DT_accept_op)
2058 {
2059 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
2060
2061 /* Only allow DT_accept_insn to follow. */
2062 if (test->next)
2063 {
2064 test = test->next;
2065 if (test->type != DT_accept_insn)
2066 abort ();
2067 }
2068 }
2069
2070 /* Sanity check that we're now at the end of the list of tests. */
2071 if (test->next)
2072 abort ();
2073
2074 if (test->type == DT_accept_insn)
2075 {
2076 switch (subroutine_type)
2077 {
2078 case RECOG:
2079 if (test->u.insn.num_clobbers_to_add != 0)
2080 printf ("%s*pnum_clobbers = %d;\n",
2081 indent, test->u.insn.num_clobbers_to_add);
2082 printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
2083 break;
2084
2085 case SPLIT:
2086 printf ("%sreturn gen_split_%d (operands);\n",
2087 indent, test->u.insn.code_number);
2088 break;
2089
2090 case PEEPHOLE2:
2091 {
2092 int match_len = 0, i;
2093
2094 for (i = strlen (p->position) - 1; i >= 0; --i)
2095 if (ISUPPER (p->position[i]))
2096 {
2097 match_len = p->position[i] - 'A';
2098 break;
2099 }
2100 printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2101 printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2102 indent, test->u.insn.code_number);
2103 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
2104 }
2105 break;
2106
2107 default:
2108 abort ();
2109 }
2110 }
2111 else
2112 {
2113 printf("%sgoto L%d;\n", indent, success->number);
2114 success->need_label = 1;
2115 }
2116
2117 if (want_close)
2118 fputs (" }\n", stdout);
2119 }
2120
2121 /* Return 1 if the test is always true and has no fallthru path. Return -1
2122 if the test does have a fallthru path, but requires that the condition be
2123 terminated. Otherwise return 0 for a normal test. */
2124 /* ??? is_unconditional is a stupid name for a tri-state function. */
2125
2126 static int
is_unconditional(struct decision_test * t,enum routine_type subroutine_type)2127 is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
2128 {
2129 if (t->type == DT_accept_op)
2130 return 1;
2131
2132 if (t->type == DT_accept_insn)
2133 {
2134 switch (subroutine_type)
2135 {
2136 case RECOG:
2137 return (t->u.insn.num_clobbers_to_add == 0);
2138 case SPLIT:
2139 return 1;
2140 case PEEPHOLE2:
2141 return -1;
2142 default:
2143 abort ();
2144 }
2145 }
2146
2147 return 0;
2148 }
2149
2150 /* Emit code for one node -- the conditional and the accompanying action.
2151 Return true if there is no fallthru path. */
2152
2153 static int
write_node(struct decision * p,int depth,enum routine_type subroutine_type)2154 write_node (struct decision *p, int depth,
2155 enum routine_type subroutine_type)
2156 {
2157 struct decision_test *test, *last_test;
2158 int uncond;
2159
2160 last_test = test = p->tests;
2161 uncond = is_unconditional (test, subroutine_type);
2162 if (uncond == 0)
2163 {
2164 printf (" if (");
2165 write_cond (test, depth, subroutine_type);
2166
2167 while ((test = test->next) != NULL)
2168 {
2169 int uncond2;
2170
2171 last_test = test;
2172 uncond2 = is_unconditional (test, subroutine_type);
2173 if (uncond2 != 0)
2174 break;
2175
2176 printf ("\n && ");
2177 write_cond (test, depth, subroutine_type);
2178 }
2179
2180 printf (")\n");
2181 }
2182
2183 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2184
2185 return uncond > 0;
2186 }
2187
2188 /* Emit code for all of the sibling nodes of HEAD. */
2189
2190 static void
write_tree_1(struct decision_head * head,int depth,enum routine_type subroutine_type)2191 write_tree_1 (struct decision_head *head, int depth,
2192 enum routine_type subroutine_type)
2193 {
2194 struct decision *p, *next;
2195 int uncond = 0;
2196
2197 for (p = head->first; p ; p = next)
2198 {
2199 /* The label for the first element was printed in write_tree. */
2200 if (p != head->first && p->need_label)
2201 OUTPUT_LABEL (" ", p->number);
2202
2203 /* Attempt to write a switch statement for a whole sequence. */
2204 next = write_switch (p, depth);
2205 if (p != next)
2206 uncond = 0;
2207 else
2208 {
2209 /* Failed -- fall back and write one node. */
2210 uncond = write_node (p, depth, subroutine_type);
2211 next = p->next;
2212 }
2213 }
2214
2215 /* Finished with this chain. Close a fallthru path by branching
2216 to the afterward node. */
2217 if (! uncond)
2218 write_afterward (head->last, head->last->afterward, " ");
2219 }
2220
2221 /* Write out the decision tree starting at HEAD. PREVPOS is the
2222 position at the node that branched to this node. */
2223
2224 static void
write_tree(struct decision_head * head,const char * prevpos,enum routine_type type,int initial)2225 write_tree (struct decision_head *head, const char *prevpos,
2226 enum routine_type type, int initial)
2227 {
2228 struct decision *p = head->first;
2229
2230 putchar ('\n');
2231 if (p->need_label)
2232 OUTPUT_LABEL (" ", p->number);
2233
2234 if (! initial && p->subroutine_number > 0)
2235 {
2236 static const char * const name_prefix[] = {
2237 "recog", "split", "peephole2"
2238 };
2239
2240 static const char * const call_suffix[] = {
2241 ", pnum_clobbers", "", ", _pmatch_len"
2242 };
2243
2244 /* This node has been broken out into a separate subroutine.
2245 Call it, test the result, and branch accordingly. */
2246
2247 if (p->afterward)
2248 {
2249 printf (" tem = %s_%d (x0, insn%s);\n",
2250 name_prefix[type], p->subroutine_number, call_suffix[type]);
2251 if (IS_SPLIT (type))
2252 printf (" if (tem != 0)\n return tem;\n");
2253 else
2254 printf (" if (tem >= 0)\n return tem;\n");
2255
2256 change_state (p->position, p->afterward->position, NULL, " ");
2257 printf (" goto L%d;\n", p->afterward->number);
2258 }
2259 else
2260 {
2261 printf (" return %s_%d (x0, insn%s);\n",
2262 name_prefix[type], p->subroutine_number, call_suffix[type]);
2263 }
2264 }
2265 else
2266 {
2267 int depth = strlen (p->position);
2268
2269 change_state (prevpos, p->position, head->last->afterward, " ");
2270 write_tree_1 (head, depth, type);
2271
2272 for (p = head->first; p; p = p->next)
2273 if (p->success.first)
2274 write_tree (&p->success, p->position, type, 0);
2275 }
2276 }
2277
2278 /* Write out a subroutine of type TYPE to do comparisons starting at
2279 node TREE. */
2280
2281 static void
write_subroutine(struct decision_head * head,enum routine_type type)2282 write_subroutine (struct decision_head *head, enum routine_type type)
2283 {
2284 int subfunction = head->first ? head->first->subroutine_number : 0;
2285 const char *s_or_e;
2286 char extension[32];
2287 int i;
2288
2289 s_or_e = subfunction ? "static " : "";
2290
2291 if (subfunction)
2292 sprintf (extension, "_%d", subfunction);
2293 else if (type == RECOG)
2294 extension[0] = '\0';
2295 else
2296 strcpy (extension, "_insns");
2297
2298 switch (type)
2299 {
2300 case RECOG:
2301 printf ("%sint\n\
2302 recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
2303 break;
2304 case SPLIT:
2305 printf ("%srtx\n\
2306 split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
2307 s_or_e, extension);
2308 break;
2309 case PEEPHOLE2:
2310 printf ("%srtx\n\
2311 peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
2312 s_or_e, extension);
2313 break;
2314 }
2315
2316 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2317 for (i = 1; i <= max_depth; i++)
2318 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
2319
2320 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2321
2322 if (!subfunction)
2323 printf (" recog_data.insn = NULL_RTX;\n");
2324
2325 if (head->first)
2326 write_tree (head, "", type, 1);
2327 else
2328 printf (" goto ret0;\n");
2329
2330 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2331 }
2332
2333 /* In break_out_subroutines, we discovered the boundaries for the
2334 subroutines, but did not write them out. Do so now. */
2335
2336 static void
write_subroutines(struct decision_head * head,enum routine_type type)2337 write_subroutines (struct decision_head *head, enum routine_type type)
2338 {
2339 struct decision *p;
2340
2341 for (p = head->first; p ; p = p->next)
2342 if (p->success.first)
2343 write_subroutines (&p->success, type);
2344
2345 if (head->first->subroutine_number > 0)
2346 write_subroutine (head, type);
2347 }
2348
2349 /* Begin the output file. */
2350
2351 static void
write_header(void)2352 write_header (void)
2353 {
2354 puts ("\
2355 /* Generated automatically by the program `genrecog' from the target\n\
2356 machine description file. */\n\
2357 \n\
2358 #include \"config.h\"\n\
2359 #include \"system.h\"\n\
2360 #include \"coretypes.h\"\n\
2361 #include \"tm.h\"\n\
2362 #include \"rtl.h\"\n\
2363 #include \"tm_p.h\"\n\
2364 #include \"function.h\"\n\
2365 #include \"insn-config.h\"\n\
2366 #include \"recog.h\"\n\
2367 #include \"real.h\"\n\
2368 #include \"output.h\"\n\
2369 #include \"flags.h\"\n\
2370 #include \"hard-reg-set.h\"\n\
2371 #include \"resource.h\"\n\
2372 #include \"toplev.h\"\n\
2373 #include \"reload.h\"\n\
2374 \n");
2375
2376 puts ("\n\
2377 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2378 X0 is a valid instruction.\n\
2379 \n\
2380 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
2381 returns a nonnegative number which is the insn code number for the\n\
2382 pattern that matched. This is the same as the order in the machine\n\
2383 description of the entry that matched. This number can be used as an\n\
2384 index into `insn_data' and other tables.\n");
2385 puts ("\
2386 The third argument to recog is an optional pointer to an int. If\n\
2387 present, recog will accept a pattern if it matches except for missing\n\
2388 CLOBBER expressions at the end. In that case, the value pointed to by\n\
2389 the optional pointer will be set to the number of CLOBBERs that need\n\
2390 to be added (it should be initialized to zero by the caller). If it");
2391 puts ("\
2392 is set nonzero, the caller should allocate a PARALLEL of the\n\
2393 appropriate size, copy the initial entries, and call add_clobbers\n\
2394 (found in insn-emit.c) to fill in the CLOBBERs.\n\
2395 ");
2396
2397 puts ("\n\
2398 The function split_insns returns 0 if the rtl could not\n\
2399 be split or the split rtl as an INSN list if it can be.\n\
2400 \n\
2401 The function peephole2_insns returns 0 if the rtl could not\n\
2402 be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2403 and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2404 */\n\n");
2405 }
2406
2407
2408 /* Construct and return a sequence of decisions
2409 that will recognize INSN.
2410
2411 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
2412
2413 static struct decision_head
make_insn_sequence(rtx insn,enum routine_type type)2414 make_insn_sequence (rtx insn, enum routine_type type)
2415 {
2416 rtx x;
2417 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2418 int truth = maybe_eval_c_test (c_test);
2419 struct decision *last;
2420 struct decision_test *test, **place;
2421 struct decision_head head;
2422 char c_test_pos[2];
2423
2424 /* We should never see an insn whose C test is false at compile time. */
2425 if (truth == 0)
2426 abort ();
2427
2428 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2429
2430 c_test_pos[0] = '\0';
2431 if (type == PEEPHOLE2)
2432 {
2433 int i, j;
2434
2435 /* peephole2 gets special treatment:
2436 - X always gets an outer parallel even if it's only one entry
2437 - we remove all traces of outer-level match_scratch and match_dup
2438 expressions here. */
2439 x = rtx_alloc (PARALLEL);
2440 PUT_MODE (x, VOIDmode);
2441 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2442 for (i = j = 0; i < XVECLEN (insn, 0); i++)
2443 {
2444 rtx tmp = XVECEXP (insn, 0, i);
2445 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2446 {
2447 XVECEXP (x, 0, j) = tmp;
2448 j++;
2449 }
2450 }
2451 XVECLEN (x, 0) = j;
2452
2453 c_test_pos[0] = 'A' + j - 1;
2454 c_test_pos[1] = '\0';
2455 }
2456 else if (XVECLEN (insn, type == RECOG) == 1)
2457 x = XVECEXP (insn, type == RECOG, 0);
2458 else
2459 {
2460 x = rtx_alloc (PARALLEL);
2461 XVEC (x, 0) = XVEC (insn, type == RECOG);
2462 PUT_MODE (x, VOIDmode);
2463 }
2464
2465 validate_pattern (x, insn, NULL_RTX, 0);
2466
2467 memset(&head, 0, sizeof(head));
2468 last = add_to_sequence (x, &head, "", type, 1);
2469
2470 /* Find the end of the test chain on the last node. */
2471 for (test = last->tests; test->next; test = test->next)
2472 continue;
2473 place = &test->next;
2474
2475 /* Skip the C test if it's known to be true at compile time. */
2476 if (truth == -1)
2477 {
2478 /* Need a new node if we have another test to add. */
2479 if (test->type == DT_accept_op)
2480 {
2481 last = new_decision (c_test_pos, &last->success);
2482 place = &last->tests;
2483 }
2484 test = new_decision_test (DT_c_test, &place);
2485 test->u.c_test = c_test;
2486 }
2487
2488 test = new_decision_test (DT_accept_insn, &place);
2489 test->u.insn.code_number = next_insn_code;
2490 test->u.insn.lineno = pattern_lineno;
2491 test->u.insn.num_clobbers_to_add = 0;
2492
2493 switch (type)
2494 {
2495 case RECOG:
2496 /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
2497 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2498 If so, set up to recognize the pattern without these CLOBBERs. */
2499
2500 if (GET_CODE (x) == PARALLEL)
2501 {
2502 int i;
2503
2504 /* Find the last non-clobber in the parallel. */
2505 for (i = XVECLEN (x, 0); i > 0; i--)
2506 {
2507 rtx y = XVECEXP (x, 0, i - 1);
2508 if (GET_CODE (y) != CLOBBER
2509 || (GET_CODE (XEXP (y, 0)) != REG
2510 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2511 break;
2512 }
2513
2514 if (i != XVECLEN (x, 0))
2515 {
2516 rtx new;
2517 struct decision_head clobber_head;
2518
2519 /* Build a similar insn without the clobbers. */
2520 if (i == 1)
2521 new = XVECEXP (x, 0, 0);
2522 else
2523 {
2524 int j;
2525
2526 new = rtx_alloc (PARALLEL);
2527 XVEC (new, 0) = rtvec_alloc (i);
2528 for (j = i - 1; j >= 0; j--)
2529 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2530 }
2531
2532 /* Recognize it. */
2533 memset (&clobber_head, 0, sizeof(clobber_head));
2534 last = add_to_sequence (new, &clobber_head, "", type, 1);
2535
2536 /* Find the end of the test chain on the last node. */
2537 for (test = last->tests; test->next; test = test->next)
2538 continue;
2539
2540 /* We definitely have a new test to add -- create a new
2541 node if needed. */
2542 place = &test->next;
2543 if (test->type == DT_accept_op)
2544 {
2545 last = new_decision ("", &last->success);
2546 place = &last->tests;
2547 }
2548
2549 /* Skip the C test if it's known to be true at compile
2550 time. */
2551 if (truth == -1)
2552 {
2553 test = new_decision_test (DT_c_test, &place);
2554 test->u.c_test = c_test;
2555 }
2556
2557 test = new_decision_test (DT_accept_insn, &place);
2558 test->u.insn.code_number = next_insn_code;
2559 test->u.insn.lineno = pattern_lineno;
2560 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2561
2562 merge_trees (&head, &clobber_head);
2563 }
2564 }
2565 break;
2566
2567 case SPLIT:
2568 /* Define the subroutine we will call below and emit in genemit. */
2569 printf ("extern rtx gen_split_%d (rtx *);\n", next_insn_code);
2570 break;
2571
2572 case PEEPHOLE2:
2573 /* Define the subroutine we will call below and emit in genemit. */
2574 printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
2575 next_insn_code);
2576 break;
2577 }
2578
2579 return head;
2580 }
2581
2582 static void
process_tree(struct decision_head * head,enum routine_type subroutine_type)2583 process_tree (struct decision_head *head, enum routine_type subroutine_type)
2584 {
2585 if (head->first == NULL)
2586 {
2587 /* We can elide peephole2_insns, but not recog or split_insns. */
2588 if (subroutine_type == PEEPHOLE2)
2589 return;
2590 }
2591 else
2592 {
2593 factor_tests (head);
2594
2595 next_subroutine_number = 0;
2596 break_out_subroutines (head, 1);
2597 find_afterward (head, NULL);
2598
2599 /* We run this after find_afterward, because find_afterward needs
2600 the redundant DT_mode tests on predicates to determine whether
2601 two tests can both be true or not. */
2602 simplify_tests(head);
2603
2604 write_subroutines (head, subroutine_type);
2605 }
2606
2607 write_subroutine (head, subroutine_type);
2608 }
2609
2610 extern int main (int, char **);
2611
2612 int
main(int argc,char ** argv)2613 main (int argc, char **argv)
2614 {
2615 rtx desc;
2616 struct decision_head recog_tree, split_tree, peephole2_tree, h;
2617
2618 progname = "genrecog";
2619
2620 memset (&recog_tree, 0, sizeof recog_tree);
2621 memset (&split_tree, 0, sizeof split_tree);
2622 memset (&peephole2_tree, 0, sizeof peephole2_tree);
2623
2624 if (argc <= 1)
2625 fatal ("no input file name");
2626
2627 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2628 return (FATAL_EXIT_CODE);
2629
2630 next_insn_code = 0;
2631 next_index = 0;
2632
2633 write_header ();
2634
2635 /* Read the machine description. */
2636
2637 while (1)
2638 {
2639 desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2640 if (desc == NULL)
2641 break;
2642
2643 if (GET_CODE (desc) == DEFINE_INSN)
2644 {
2645 h = make_insn_sequence (desc, RECOG);
2646 merge_trees (&recog_tree, &h);
2647 }
2648 else if (GET_CODE (desc) == DEFINE_SPLIT)
2649 {
2650 h = make_insn_sequence (desc, SPLIT);
2651 merge_trees (&split_tree, &h);
2652 }
2653 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2654 {
2655 h = make_insn_sequence (desc, PEEPHOLE2);
2656 merge_trees (&peephole2_tree, &h);
2657 }
2658
2659 next_index++;
2660 }
2661
2662 if (error_count)
2663 return FATAL_EXIT_CODE;
2664
2665 puts ("\n\n");
2666
2667 process_tree (&recog_tree, RECOG);
2668 process_tree (&split_tree, SPLIT);
2669 process_tree (&peephole2_tree, PEEPHOLE2);
2670
2671 fflush (stdout);
2672 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2673 }
2674
2675 /* Define this so we can link with print-rtl.o to get debug_rtx function. */
2676 const char *
get_insn_name(int code)2677 get_insn_name (int code)
2678 {
2679 if (code < insn_name_ptr_size)
2680 return insn_name_ptr[code];
2681 else
2682 return NULL;
2683 }
2684
2685 static void
record_insn_name(int code,const char * name)2686 record_insn_name (int code, const char *name)
2687 {
2688 static const char *last_real_name = "insn";
2689 static int last_real_code = 0;
2690 char *new;
2691
2692 if (insn_name_ptr_size <= code)
2693 {
2694 int new_size;
2695 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2696 insn_name_ptr = xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2697 memset (insn_name_ptr + insn_name_ptr_size, 0,
2698 sizeof(char *) * (new_size - insn_name_ptr_size));
2699 insn_name_ptr_size = new_size;
2700 }
2701
2702 if (!name || name[0] == '\0')
2703 {
2704 new = xmalloc (strlen (last_real_name) + 10);
2705 sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2706 }
2707 else
2708 {
2709 last_real_name = new = xstrdup (name);
2710 last_real_code = code;
2711 }
2712
2713 insn_name_ptr[code] = new;
2714 }
2715
2716 static void
debug_decision_2(struct decision_test * test)2717 debug_decision_2 (struct decision_test *test)
2718 {
2719 switch (test->type)
2720 {
2721 case DT_mode:
2722 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2723 break;
2724 case DT_code:
2725 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2726 break;
2727 case DT_veclen:
2728 fprintf (stderr, "veclen=%d", test->u.veclen);
2729 break;
2730 case DT_elt_zero_int:
2731 fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2732 break;
2733 case DT_elt_one_int:
2734 fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2735 break;
2736 case DT_elt_zero_wide:
2737 fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2738 break;
2739 case DT_elt_zero_wide_safe:
2740 fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2741 break;
2742 case DT_veclen_ge:
2743 fprintf (stderr, "veclen>=%d", test->u.veclen);
2744 break;
2745 case DT_dup:
2746 fprintf (stderr, "dup=%d", test->u.dup);
2747 break;
2748 case DT_pred:
2749 fprintf (stderr, "pred=(%s,%s)",
2750 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2751 break;
2752 case DT_c_test:
2753 {
2754 char sub[16+4];
2755 strncpy (sub, test->u.c_test, sizeof(sub));
2756 memcpy (sub+16, "...", 4);
2757 fprintf (stderr, "c_test=\"%s\"", sub);
2758 }
2759 break;
2760 case DT_accept_op:
2761 fprintf (stderr, "A_op=%d", test->u.opno);
2762 break;
2763 case DT_accept_insn:
2764 fprintf (stderr, "A_insn=(%d,%d)",
2765 test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2766 break;
2767
2768 default:
2769 abort ();
2770 }
2771 }
2772
2773 static void
debug_decision_1(struct decision * d,int indent)2774 debug_decision_1 (struct decision *d, int indent)
2775 {
2776 int i;
2777 struct decision_test *test;
2778
2779 if (d == NULL)
2780 {
2781 for (i = 0; i < indent; ++i)
2782 putc (' ', stderr);
2783 fputs ("(nil)\n", stderr);
2784 return;
2785 }
2786
2787 for (i = 0; i < indent; ++i)
2788 putc (' ', stderr);
2789
2790 putc ('{', stderr);
2791 test = d->tests;
2792 if (test)
2793 {
2794 debug_decision_2 (test);
2795 while ((test = test->next) != NULL)
2796 {
2797 fputs (" + ", stderr);
2798 debug_decision_2 (test);
2799 }
2800 }
2801 fprintf (stderr, "} %d n %d a %d\n", d->number,
2802 (d->next ? d->next->number : -1),
2803 (d->afterward ? d->afterward->number : -1));
2804 }
2805
2806 static void
debug_decision_0(struct decision * d,int indent,int maxdepth)2807 debug_decision_0 (struct decision *d, int indent, int maxdepth)
2808 {
2809 struct decision *n;
2810 int i;
2811
2812 if (maxdepth < 0)
2813 return;
2814 if (d == NULL)
2815 {
2816 for (i = 0; i < indent; ++i)
2817 putc (' ', stderr);
2818 fputs ("(nil)\n", stderr);
2819 return;
2820 }
2821
2822 debug_decision_1 (d, indent);
2823 for (n = d->success.first; n ; n = n->next)
2824 debug_decision_0 (n, indent + 2, maxdepth - 1);
2825 }
2826
2827 void
debug_decision(struct decision * d)2828 debug_decision (struct decision *d)
2829 {
2830 debug_decision_0 (d, 0, 1000000);
2831 }
2832
2833 void
debug_decision_list(struct decision * d)2834 debug_decision_list (struct decision *d)
2835 {
2836 while (d)
2837 {
2838 debug_decision_0 (d, 0, 0);
2839 d = d->next;
2840 }
2841 }
2842