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