OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [genrecog.c] - Blame information for rev 684

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.