Mercurial > hg > CbC > CbC_gcc

comparison gcc/genrecog.c @ 0:a06113de4d67

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