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

Subversion Repositories openrisc

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

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Expands front end tree to back end RTL for GCC
2
   Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3
   1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4
   2010, 2011, 2012 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 under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
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
/* This file handles the generation of rtl code from tree structure
23
   above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
24
   The functions whose names start with `expand_' are called by the
25
   expander to generate RTL instructions for various kinds of constructs.  */
26
 
27
#include "config.h"
28
#include "system.h"
29
#include "coretypes.h"
30
#include "tm.h"
31
 
32
#include "rtl.h"
33
#include "hard-reg-set.h"
34
#include "tree.h"
35
#include "tm_p.h"
36
#include "flags.h"
37
#include "except.h"
38
#include "function.h"
39
#include "insn-config.h"
40
#include "expr.h"
41
#include "libfuncs.h"
42
#include "recog.h"
43
#include "machmode.h"
44
#include "diagnostic-core.h"
45
#include "output.h"
46
#include "ggc.h"
47
#include "langhooks.h"
48
#include "predict.h"
49
#include "optabs.h"
50
#include "target.h"
51
#include "gimple.h"
52
#include "regs.h"
53
#include "alloc-pool.h"
54
#include "pretty-print.h"
55
#include "bitmap.h"
56
#include "params.h"
57
 
58
 
59
/* Functions and data structures for expanding case statements.  */
60
 
61
/* Case label structure, used to hold info on labels within case
62
   statements.  We handle "range" labels; for a single-value label
63
   as in C, the high and low limits are the same.
64
 
65
   We start with a vector of case nodes sorted in ascending order, and
66
   the default label as the last element in the vector.  Before expanding
67
   to RTL, we transform this vector into a list linked via the RIGHT
68
   fields in the case_node struct.  Nodes with higher case values are
69
   later in the list.
70
 
71
   Switch statements can be output in three forms.  A branch table is
72
   used if there are more than a few labels and the labels are dense
73
   within the range between the smallest and largest case value.  If a
74
   branch table is used, no further manipulations are done with the case
75
   node chain.
76
 
77
   The alternative to the use of a branch table is to generate a series
78
   of compare and jump insns.  When that is done, we use the LEFT, RIGHT,
79
   and PARENT fields to hold a binary tree.  Initially the tree is
80
   totally unbalanced, with everything on the right.  We balance the tree
81
   with nodes on the left having lower case values than the parent
82
   and nodes on the right having higher values.  We then output the tree
83
   in order.
84
 
85
   For very small, suitable switch statements, we can generate a series
86
   of simple bit test and branches instead.  */
87
 
88
struct case_node
89
{
90
  struct case_node      *left;  /* Left son in binary tree */
91
  struct case_node      *right; /* Right son in binary tree; also node chain */
92
  struct case_node      *parent; /* Parent of node in binary tree */
93
  tree                  low;    /* Lowest index value for this label */
94
  tree                  high;   /* Highest index value for this label */
95
  tree                  code_label; /* Label to jump to when node matches */
96
};
97
 
98
typedef struct case_node case_node;
99
typedef struct case_node *case_node_ptr;
100
 
101
/* These are used by estimate_case_costs and balance_case_nodes.  */
102
 
103
/* This must be a signed type, and non-ANSI compilers lack signed char.  */
104
static short cost_table_[129];
105
static int use_cost_table;
106
static int cost_table_initialized;
107
 
108
/* Special care is needed because we allow -1, but TREE_INT_CST_LOW
109
   is unsigned.  */
110
#define COST_TABLE(I)  cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
111
 
112
static int n_occurrences (int, const char *);
113
static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
114
static void expand_nl_goto_receiver (void);
115
static bool check_operand_nalternatives (tree, tree);
116
static bool check_unique_operand_names (tree, tree, tree);
117
static char *resolve_operand_name_1 (char *, tree, tree, tree);
118
static void expand_null_return_1 (void);
119
static void expand_value_return (rtx);
120
static int estimate_case_costs (case_node_ptr);
121
static bool lshift_cheap_p (void);
122
static int case_bit_test_cmp (const void *, const void *);
123
static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
124
static void balance_case_nodes (case_node_ptr *, case_node_ptr);
125
static int node_has_low_bound (case_node_ptr, tree);
126
static int node_has_high_bound (case_node_ptr, tree);
127
static int node_is_bounded (case_node_ptr, tree);
128
static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
129
static struct case_node *add_case_node (struct case_node *, tree,
130
                                        tree, tree, tree, alloc_pool);
131
 
132
 
133
/* Return the rtx-label that corresponds to a LABEL_DECL,
134
   creating it if necessary.  */
135
 
136
rtx
137
label_rtx (tree label)
138
{
139
  gcc_assert (TREE_CODE (label) == LABEL_DECL);
140
 
141
  if (!DECL_RTL_SET_P (label))
142
    {
143
      rtx r = gen_label_rtx ();
144
      SET_DECL_RTL (label, r);
145
      if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
146
        LABEL_PRESERVE_P (r) = 1;
147
    }
148
 
149
  return DECL_RTL (label);
150
}
151
 
152
/* As above, but also put it on the forced-reference list of the
153
   function that contains it.  */
154
rtx
155
force_label_rtx (tree label)
156
{
157
  rtx ref = label_rtx (label);
158
  tree function = decl_function_context (label);
159
 
160
  gcc_assert (function);
161
 
162
  forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
163
  return ref;
164
}
165
 
166
/* Add an unconditional jump to LABEL as the next sequential instruction.  */
167
 
168
void
169
emit_jump (rtx label)
170
{
171
  do_pending_stack_adjust ();
172
  emit_jump_insn (gen_jump (label));
173
  emit_barrier ();
174
}
175
 
176
/* Emit code to jump to the address
177
   specified by the pointer expression EXP.  */
178
 
179
void
180
expand_computed_goto (tree exp)
181
{
182
  rtx x = expand_normal (exp);
183
 
184
  x = convert_memory_address (Pmode, x);
185
 
186
  do_pending_stack_adjust ();
187
  emit_indirect_jump (x);
188
}
189
 
190
/* Handle goto statements and the labels that they can go to.  */
191
 
192
/* Specify the location in the RTL code of a label LABEL,
193
   which is a LABEL_DECL tree node.
194
 
195
   This is used for the kind of label that the user can jump to with a
196
   goto statement, and for alternatives of a switch or case statement.
197
   RTL labels generated for loops and conditionals don't go through here;
198
   they are generated directly at the RTL level, by other functions below.
199
 
200
   Note that this has nothing to do with defining label *names*.
201
   Languages vary in how they do that and what that even means.  */
202
 
203
void
204
expand_label (tree label)
205
{
206
  rtx label_r = label_rtx (label);
207
 
208
  do_pending_stack_adjust ();
209
  emit_label (label_r);
210
  if (DECL_NAME (label))
211
    LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
212
 
213
  if (DECL_NONLOCAL (label))
214
    {
215
      expand_nl_goto_receiver ();
216
      nonlocal_goto_handler_labels
217
        = gen_rtx_EXPR_LIST (VOIDmode, label_r,
218
                             nonlocal_goto_handler_labels);
219
    }
220
 
221
  if (FORCED_LABEL (label))
222
    forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
223
 
224
  if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
225
    maybe_set_first_label_num (label_r);
226
}
227
 
228
/* Generate RTL code for a `goto' statement with target label LABEL.
229
   LABEL should be a LABEL_DECL tree node that was or will later be
230
   defined with `expand_label'.  */
231
 
232
void
233
expand_goto (tree label)
234
{
235
#ifdef ENABLE_CHECKING
236
  /* Check for a nonlocal goto to a containing function.  Should have
237
     gotten translated to __builtin_nonlocal_goto.  */
238
  tree context = decl_function_context (label);
239
  gcc_assert (!context || context == current_function_decl);
240
#endif
241
 
242
  emit_jump (label_rtx (label));
243
}
244
 
245
/* Return the number of times character C occurs in string S.  */
246
static int
247
n_occurrences (int c, const char *s)
248
{
249
  int n = 0;
250
  while (*s)
251
    n += (*s++ == c);
252
  return n;
253
}
254
 
255
/* Generate RTL for an asm statement (explicit assembler code).
256
   STRING is a STRING_CST node containing the assembler code text,
257
   or an ADDR_EXPR containing a STRING_CST.  VOL nonzero means the
258
   insn is volatile; don't optimize it.  */
259
 
260
static void
261
expand_asm_loc (tree string, int vol, location_t locus)
262
{
263
  rtx body;
264
 
265
  if (TREE_CODE (string) == ADDR_EXPR)
266
    string = TREE_OPERAND (string, 0);
267
 
268
  body = gen_rtx_ASM_INPUT_loc (VOIDmode,
269
                                ggc_strdup (TREE_STRING_POINTER (string)),
270
                                locus);
271
 
272
  MEM_VOLATILE_P (body) = vol;
273
 
274
  emit_insn (body);
275
}
276
 
277
/* Parse the output constraint pointed to by *CONSTRAINT_P.  It is the
278
   OPERAND_NUMth output operand, indexed from zero.  There are NINPUTS
279
   inputs and NOUTPUTS outputs to this extended-asm.  Upon return,
280
   *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
281
   memory operand.  Similarly, *ALLOWS_REG will be TRUE iff the
282
   constraint allows the use of a register operand.  And, *IS_INOUT
283
   will be true if the operand is read-write, i.e., if it is used as
284
   an input as well as an output.  If *CONSTRAINT_P is not in
285
   canonical form, it will be made canonical.  (Note that `+' will be
286
   replaced with `=' as part of this process.)
287
 
288
   Returns TRUE if all went well; FALSE if an error occurred.  */
289
 
290
bool
291
parse_output_constraint (const char **constraint_p, int operand_num,
292
                         int ninputs, int noutputs, bool *allows_mem,
293
                         bool *allows_reg, bool *is_inout)
294
{
295
  const char *constraint = *constraint_p;
296
  const char *p;
297
 
298
  /* Assume the constraint doesn't allow the use of either a register
299
     or memory.  */
300
  *allows_mem = false;
301
  *allows_reg = false;
302
 
303
  /* Allow the `=' or `+' to not be at the beginning of the string,
304
     since it wasn't explicitly documented that way, and there is a
305
     large body of code that puts it last.  Swap the character to
306
     the front, so as not to uglify any place else.  */
307
  p = strchr (constraint, '=');
308
  if (!p)
309
    p = strchr (constraint, '+');
310
 
311
  /* If the string doesn't contain an `=', issue an error
312
     message.  */
313
  if (!p)
314
    {
315
      error ("output operand constraint lacks %<=%>");
316
      return false;
317
    }
318
 
319
  /* If the constraint begins with `+', then the operand is both read
320
     from and written to.  */
321
  *is_inout = (*p == '+');
322
 
323
  /* Canonicalize the output constraint so that it begins with `='.  */
324
  if (p != constraint || *is_inout)
325
    {
326
      char *buf;
327
      size_t c_len = strlen (constraint);
328
 
329
      if (p != constraint)
330
        warning (0, "output constraint %qc for operand %d "
331
                 "is not at the beginning",
332
                 *p, operand_num);
333
 
334
      /* Make a copy of the constraint.  */
335
      buf = XALLOCAVEC (char, c_len + 1);
336
      strcpy (buf, constraint);
337
      /* Swap the first character and the `=' or `+'.  */
338
      buf[p - constraint] = buf[0];
339
      /* Make sure the first character is an `='.  (Until we do this,
340
         it might be a `+'.)  */
341
      buf[0] = '=';
342
      /* Replace the constraint with the canonicalized string.  */
343
      *constraint_p = ggc_alloc_string (buf, c_len);
344
      constraint = *constraint_p;
345
    }
346
 
347
  /* Loop through the constraint string.  */
348
  for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
349
    switch (*p)
350
      {
351
      case '+':
352
      case '=':
353
        error ("operand constraint contains incorrectly positioned "
354
               "%<+%> or %<=%>");
355
        return false;
356
 
357
      case '%':
358
        if (operand_num + 1 == ninputs + noutputs)
359
          {
360
            error ("%<%%%> constraint used with last operand");
361
            return false;
362
          }
363
        break;
364
 
365
      case 'V':  case TARGET_MEM_CONSTRAINT:  case 'o':
366
        *allows_mem = true;
367
        break;
368
 
369
      case '?':  case '!':  case '*':  case '&':  case '#':
370
      case 'E':  case 'F':  case 'G':  case 'H':
371
      case 's':  case 'i':  case 'n':
372
      case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
373
      case 'N':  case 'O':  case 'P':  case ',':
374
        break;
375
 
376
      case '0':  case '1':  case '2':  case '3':  case '4':
377
      case '5':  case '6':  case '7':  case '8':  case '9':
378
      case '[':
379
        error ("matching constraint not valid in output operand");
380
        return false;
381
 
382
      case '<':  case '>':
383
        /* ??? Before flow, auto inc/dec insns are not supposed to exist,
384
           excepting those that expand_call created.  So match memory
385
           and hope.  */
386
        *allows_mem = true;
387
        break;
388
 
389
      case 'g':  case 'X':
390
        *allows_reg = true;
391
        *allows_mem = true;
392
        break;
393
 
394
      case 'p': case 'r':
395
        *allows_reg = true;
396
        break;
397
 
398
      default:
399
        if (!ISALPHA (*p))
400
          break;
401
        if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
402
          *allows_reg = true;
403
#ifdef EXTRA_CONSTRAINT_STR
404
        else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
405
          *allows_reg = true;
406
        else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
407
          *allows_mem = true;
408
        else
409
          {
410
            /* Otherwise we can't assume anything about the nature of
411
               the constraint except that it isn't purely registers.
412
               Treat it like "g" and hope for the best.  */
413
            *allows_reg = true;
414
            *allows_mem = true;
415
          }
416
#endif
417
        break;
418
      }
419
 
420
  return true;
421
}
422
 
423
/* Similar, but for input constraints.  */
424
 
425
bool
426
parse_input_constraint (const char **constraint_p, int input_num,
427
                        int ninputs, int noutputs, int ninout,
428
                        const char * const * constraints,
429
                        bool *allows_mem, bool *allows_reg)
430
{
431
  const char *constraint = *constraint_p;
432
  const char *orig_constraint = constraint;
433
  size_t c_len = strlen (constraint);
434
  size_t j;
435
  bool saw_match = false;
436
 
437
  /* Assume the constraint doesn't allow the use of either
438
     a register or memory.  */
439
  *allows_mem = false;
440
  *allows_reg = false;
441
 
442
  /* Make sure constraint has neither `=', `+', nor '&'.  */
443
 
444
  for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
445
    switch (constraint[j])
446
      {
447
      case '+':  case '=':  case '&':
448
        if (constraint == orig_constraint)
449
          {
450
            error ("input operand constraint contains %qc", constraint[j]);
451
            return false;
452
          }
453
        break;
454
 
455
      case '%':
456
        if (constraint == orig_constraint
457
            && input_num + 1 == ninputs - ninout)
458
          {
459
            error ("%<%%%> constraint used with last operand");
460
            return false;
461
          }
462
        break;
463
 
464
      case 'V':  case TARGET_MEM_CONSTRAINT:  case 'o':
465
        *allows_mem = true;
466
        break;
467
 
468
      case '<':  case '>':
469
      case '?':  case '!':  case '*':  case '#':
470
      case 'E':  case 'F':  case 'G':  case 'H':
471
      case 's':  case 'i':  case 'n':
472
      case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
473
      case 'N':  case 'O':  case 'P':  case ',':
474
        break;
475
 
476
        /* Whether or not a numeric constraint allows a register is
477
           decided by the matching constraint, and so there is no need
478
           to do anything special with them.  We must handle them in
479
           the default case, so that we don't unnecessarily force
480
           operands to memory.  */
481
      case '0':  case '1':  case '2':  case '3':  case '4':
482
      case '5':  case '6':  case '7':  case '8':  case '9':
483
        {
484
          char *end;
485
          unsigned long match;
486
 
487
          saw_match = true;
488
 
489
          match = strtoul (constraint + j, &end, 10);
490
          if (match >= (unsigned long) noutputs)
491
            {
492
              error ("matching constraint references invalid operand number");
493
              return false;
494
            }
495
 
496
          /* Try and find the real constraint for this dup.  Only do this
497
             if the matching constraint is the only alternative.  */
498
          if (*end == '\0'
499
              && (j == 0 || (j == 1 && constraint[0] == '%')))
500
            {
501
              constraint = constraints[match];
502
              *constraint_p = constraint;
503
              c_len = strlen (constraint);
504
              j = 0;
505
              /* ??? At the end of the loop, we will skip the first part of
506
                 the matched constraint.  This assumes not only that the
507
                 other constraint is an output constraint, but also that
508
                 the '=' or '+' come first.  */
509
              break;
510
            }
511
          else
512
            j = end - constraint;
513
          /* Anticipate increment at end of loop.  */
514
          j--;
515
        }
516
        /* Fall through.  */
517
 
518
      case 'p':  case 'r':
519
        *allows_reg = true;
520
        break;
521
 
522
      case 'g':  case 'X':
523
        *allows_reg = true;
524
        *allows_mem = true;
525
        break;
526
 
527
      default:
528
        if (! ISALPHA (constraint[j]))
529
          {
530
            error ("invalid punctuation %qc in constraint", constraint[j]);
531
            return false;
532
          }
533
        if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
534
            != NO_REGS)
535
          *allows_reg = true;
536
#ifdef EXTRA_CONSTRAINT_STR
537
        else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
538
          *allows_reg = true;
539
        else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
540
          *allows_mem = true;
541
        else
542
          {
543
            /* Otherwise we can't assume anything about the nature of
544
               the constraint except that it isn't purely registers.
545
               Treat it like "g" and hope for the best.  */
546
            *allows_reg = true;
547
            *allows_mem = true;
548
          }
549
#endif
550
        break;
551
      }
552
 
553
  if (saw_match && !*allows_reg)
554
    warning (0, "matching constraint does not allow a register");
555
 
556
  return true;
557
}
558
 
559
/* Return DECL iff there's an overlap between *REGS and DECL, where DECL
560
   can be an asm-declared register.  Called via walk_tree.  */
561
 
562
static tree
563
decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
564
                              void *data)
565
{
566
  tree decl = *declp;
567
  const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
568
 
569
  if (TREE_CODE (decl) == VAR_DECL)
570
    {
571
      if (DECL_HARD_REGISTER (decl)
572
          && REG_P (DECL_RTL (decl))
573
          && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
574
        {
575
          rtx reg = DECL_RTL (decl);
576
 
577
          if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
578
            return decl;
579
        }
580
      walk_subtrees = 0;
581
    }
582
  else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
583
    walk_subtrees = 0;
584
  return NULL_TREE;
585
}
586
 
587
/* If there is an overlap between *REGS and DECL, return the first overlap
588
   found.  */
589
tree
590
tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
591
{
592
  return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
593
}
594
 
595
/* Check for overlap between registers marked in CLOBBERED_REGS and
596
   anything inappropriate in T.  Emit error and return the register
597
   variable definition for error, NULL_TREE for ok.  */
598
 
599
static bool
600
tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
601
{
602
  /* Conflicts between asm-declared register variables and the clobber
603
     list are not allowed.  */
604
  tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
605
 
606
  if (overlap)
607
    {
608
      error ("asm-specifier for variable %qE conflicts with asm clobber list",
609
             DECL_NAME (overlap));
610
 
611
      /* Reset registerness to stop multiple errors emitted for a single
612
         variable.  */
613
      DECL_REGISTER (overlap) = 0;
614
      return true;
615
    }
616
 
617
  return false;
618
}
619
 
620
/* Generate RTL for an asm statement with arguments.
621
   STRING is the instruction template.
622
   OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
623
   Each output or input has an expression in the TREE_VALUE and
624
   a tree list in TREE_PURPOSE which in turn contains a constraint
625
   name in TREE_VALUE (or NULL_TREE) and a constraint string
626
   in TREE_PURPOSE.
627
   CLOBBERS is a list of STRING_CST nodes each naming a hard register
628
   that is clobbered by this insn.
629
 
630
   Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
631
   Some elements of OUTPUTS may be replaced with trees representing temporary
632
   values.  The caller should copy those temporary values to the originally
633
   specified lvalues.
634
 
635
   VOL nonzero means the insn is volatile; don't optimize it.  */
636
 
637
static void
638
expand_asm_operands (tree string, tree outputs, tree inputs,
639
                     tree clobbers, tree labels, int vol, location_t locus)
640
{
641
  rtvec argvec, constraintvec, labelvec;
642
  rtx body;
643
  int ninputs = list_length (inputs);
644
  int noutputs = list_length (outputs);
645
  int nlabels = list_length (labels);
646
  int ninout;
647
  int nclobbers;
648
  HARD_REG_SET clobbered_regs;
649
  int clobber_conflict_found = 0;
650
  tree tail;
651
  tree t;
652
  int i;
653
  /* Vector of RTX's of evaluated output operands.  */
654
  rtx *output_rtx = XALLOCAVEC (rtx, noutputs);
655
  int *inout_opnum = XALLOCAVEC (int, noutputs);
656
  rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs);
657
  enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs);
658
  const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs);
659
  int old_generating_concat_p = generating_concat_p;
660
 
661
  /* An ASM with no outputs needs to be treated as volatile, for now.  */
662
  if (noutputs == 0)
663
    vol = 1;
664
 
665
  if (! check_operand_nalternatives (outputs, inputs))
666
    return;
667
 
668
  string = resolve_asm_operand_names (string, outputs, inputs, labels);
669
 
670
  /* Collect constraints.  */
671
  i = 0;
672
  for (t = outputs; t ; t = TREE_CHAIN (t), i++)
673
    constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
674
  for (t = inputs; t ; t = TREE_CHAIN (t), i++)
675
    constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
676
 
677
  /* Sometimes we wish to automatically clobber registers across an asm.
678
     Case in point is when the i386 backend moved from cc0 to a hard reg --
679
     maintaining source-level compatibility means automatically clobbering
680
     the flags register.  */
681
  clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
682
 
683
  /* Count the number of meaningful clobbered registers, ignoring what
684
     we would ignore later.  */
685
  nclobbers = 0;
686
  CLEAR_HARD_REG_SET (clobbered_regs);
687
  for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
688
    {
689
      const char *regname;
690
      int nregs;
691
 
692
      if (TREE_VALUE (tail) == error_mark_node)
693
        return;
694
      regname = TREE_STRING_POINTER (TREE_VALUE (tail));
695
 
696
      i = decode_reg_name_and_count (regname, &nregs);
697
      if (i == -4)
698
        ++nclobbers;
699
      else if (i == -2)
700
        error ("unknown register name %qs in %<asm%>", regname);
701
 
702
      /* Mark clobbered registers.  */
703
      if (i >= 0)
704
        {
705
          int reg;
706
 
707
          for (reg = i; reg < i + nregs; reg++)
708
            {
709
              ++nclobbers;
710
 
711
              /* Clobbering the PIC register is an error.  */
712
              if (reg == (int) PIC_OFFSET_TABLE_REGNUM)
713
                {
714
                  error ("PIC register clobbered by %qs in %<asm%>", regname);
715
                  return;
716
                }
717
 
718
              SET_HARD_REG_BIT (clobbered_regs, reg);
719
            }
720
        }
721
    }
722
 
723
  /* First pass over inputs and outputs checks validity and sets
724
     mark_addressable if needed.  */
725
 
726
  ninout = 0;
727
  for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
728
    {
729
      tree val = TREE_VALUE (tail);
730
      tree type = TREE_TYPE (val);
731
      const char *constraint;
732
      bool is_inout;
733
      bool allows_reg;
734
      bool allows_mem;
735
 
736
      /* If there's an erroneous arg, emit no insn.  */
737
      if (type == error_mark_node)
738
        return;
739
 
740
      /* Try to parse the output constraint.  If that fails, there's
741
         no point in going further.  */
742
      constraint = constraints[i];
743
      if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
744
                                    &allows_mem, &allows_reg, &is_inout))
745
        return;
746
 
747
      if (! allows_reg
748
          && (allows_mem
749
              || is_inout
750
              || (DECL_P (val)
751
                  && REG_P (DECL_RTL (val))
752
                  && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
753
        mark_addressable (val);
754
 
755
      if (is_inout)
756
        ninout++;
757
    }
758
 
759
  ninputs += ninout;
760
  if (ninputs + noutputs > MAX_RECOG_OPERANDS)
761
    {
762
      error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
763
      return;
764
    }
765
 
766
  for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
767
    {
768
      bool allows_reg, allows_mem;
769
      const char *constraint;
770
 
771
      /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
772
         would get VOIDmode and that could cause a crash in reload.  */
773
      if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
774
        return;
775
 
776
      constraint = constraints[i + noutputs];
777
      if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
778
                                    constraints, &allows_mem, &allows_reg))
779
        return;
780
 
781
      if (! allows_reg && allows_mem)
782
        mark_addressable (TREE_VALUE (tail));
783
    }
784
 
785
  /* Second pass evaluates arguments.  */
786
 
787
  /* Make sure stack is consistent for asm goto.  */
788
  if (nlabels > 0)
789
    do_pending_stack_adjust ();
790
 
791
  ninout = 0;
792
  for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
793
    {
794
      tree val = TREE_VALUE (tail);
795
      tree type = TREE_TYPE (val);
796
      bool is_inout;
797
      bool allows_reg;
798
      bool allows_mem;
799
      rtx op;
800
      bool ok;
801
 
802
      ok = parse_output_constraint (&constraints[i], i, ninputs,
803
                                    noutputs, &allows_mem, &allows_reg,
804
                                    &is_inout);
805
      gcc_assert (ok);
806
 
807
      /* If an output operand is not a decl or indirect ref and our constraint
808
         allows a register, make a temporary to act as an intermediate.
809
         Make the asm insn write into that, then our caller will copy it to
810
         the real output operand.  Likewise for promoted variables.  */
811
 
812
      generating_concat_p = 0;
813
 
814
      real_output_rtx[i] = NULL_RTX;
815
      if ((TREE_CODE (val) == INDIRECT_REF
816
           && allows_mem)
817
          || (DECL_P (val)
818
              && (allows_mem || REG_P (DECL_RTL (val)))
819
              && ! (REG_P (DECL_RTL (val))
820
                    && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
821
          || ! allows_reg
822
          || is_inout)
823
        {
824
          op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
825
          if (MEM_P (op))
826
            op = validize_mem (op);
827
 
828
          if (! allows_reg && !MEM_P (op))
829
            error ("output number %d not directly addressable", i);
830
          if ((! allows_mem && MEM_P (op))
831
              || GET_CODE (op) == CONCAT)
832
            {
833
              real_output_rtx[i] = op;
834
              op = gen_reg_rtx (GET_MODE (op));
835
              if (is_inout)
836
                emit_move_insn (op, real_output_rtx[i]);
837
            }
838
        }
839
      else
840
        {
841
          op = assign_temp (type, 0, 0, 1);
842
          op = validize_mem (op);
843
          if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
844
            set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
845
          TREE_VALUE (tail) = make_tree (type, op);
846
        }
847
      output_rtx[i] = op;
848
 
849
      generating_concat_p = old_generating_concat_p;
850
 
851
      if (is_inout)
852
        {
853
          inout_mode[ninout] = TYPE_MODE (type);
854
          inout_opnum[ninout++] = i;
855
        }
856
 
857
      if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
858
        clobber_conflict_found = 1;
859
    }
860
 
861
  /* Make vectors for the expression-rtx, constraint strings,
862
     and named operands.  */
863
 
864
  argvec = rtvec_alloc (ninputs);
865
  constraintvec = rtvec_alloc (ninputs);
866
  labelvec = rtvec_alloc (nlabels);
867
 
868
  body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
869
                                : GET_MODE (output_rtx[0])),
870
                               ggc_strdup (TREE_STRING_POINTER (string)),
871
                               empty_string, 0, argvec, constraintvec,
872
                               labelvec, locus);
873
 
874
  MEM_VOLATILE_P (body) = vol;
875
 
876
  /* Eval the inputs and put them into ARGVEC.
877
     Put their constraints into ASM_INPUTs and store in CONSTRAINTS.  */
878
 
879
  for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
880
    {
881
      bool allows_reg, allows_mem;
882
      const char *constraint;
883
      tree val, type;
884
      rtx op;
885
      bool ok;
886
 
887
      constraint = constraints[i + noutputs];
888
      ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
889
                                   constraints, &allows_mem, &allows_reg);
890
      gcc_assert (ok);
891
 
892
      generating_concat_p = 0;
893
 
894
      val = TREE_VALUE (tail);
895
      type = TREE_TYPE (val);
896
      /* EXPAND_INITIALIZER will not generate code for valid initializer
897
         constants, but will still generate code for other types of operand.
898
         This is the behavior we want for constant constraints.  */
899
      op = expand_expr (val, NULL_RTX, VOIDmode,
900
                        allows_reg ? EXPAND_NORMAL
901
                        : allows_mem ? EXPAND_MEMORY
902
                        : EXPAND_INITIALIZER);
903
 
904
      /* Never pass a CONCAT to an ASM.  */
905
      if (GET_CODE (op) == CONCAT)
906
        op = force_reg (GET_MODE (op), op);
907
      else if (MEM_P (op))
908
        op = validize_mem (op);
909
 
910
      if (asm_operand_ok (op, constraint, NULL) <= 0)
911
        {
912
          if (allows_reg && TYPE_MODE (type) != BLKmode)
913
            op = force_reg (TYPE_MODE (type), op);
914
          else if (!allows_mem)
915
            warning (0, "asm operand %d probably doesn%'t match constraints",
916
                     i + noutputs);
917
          else if (MEM_P (op))
918
            {
919
              /* We won't recognize either volatile memory or memory
920
                 with a queued address as available a memory_operand
921
                 at this point.  Ignore it: clearly this *is* a memory.  */
922
            }
923
          else
924
            {
925
              warning (0, "use of memory input without lvalue in "
926
                       "asm operand %d is deprecated", i + noutputs);
927
 
928
              if (CONSTANT_P (op))
929
                {
930
                  rtx mem = force_const_mem (TYPE_MODE (type), op);
931
                  if (mem)
932
                    op = validize_mem (mem);
933
                  else
934
                    op = force_reg (TYPE_MODE (type), op);
935
                }
936
              if (REG_P (op)
937
                  || GET_CODE (op) == SUBREG
938
                  || GET_CODE (op) == CONCAT)
939
                {
940
                  tree qual_type = build_qualified_type (type,
941
                                                         (TYPE_QUALS (type)
942
                                                          | TYPE_QUAL_CONST));
943
                  rtx memloc = assign_temp (qual_type, 1, 1, 1);
944
                  memloc = validize_mem (memloc);
945
                  emit_move_insn (memloc, op);
946
                  op = memloc;
947
                }
948
            }
949
        }
950
 
951
      generating_concat_p = old_generating_concat_p;
952
      ASM_OPERANDS_INPUT (body, i) = op;
953
 
954
      ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
955
        = gen_rtx_ASM_INPUT (TYPE_MODE (type),
956
                             ggc_strdup (constraints[i + noutputs]));
957
 
958
      if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
959
        clobber_conflict_found = 1;
960
    }
961
 
962
  /* Protect all the operands from the queue now that they have all been
963
     evaluated.  */
964
 
965
  generating_concat_p = 0;
966
 
967
  /* For in-out operands, copy output rtx to input rtx.  */
968
  for (i = 0; i < ninout; i++)
969
    {
970
      int j = inout_opnum[i];
971
      char buffer[16];
972
 
973
      ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
974
        = output_rtx[j];
975
 
976
      sprintf (buffer, "%d", j);
977
      ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
978
        = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
979
    }
980
 
981
  /* Copy labels to the vector.  */
982
  for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail))
983
    ASM_OPERANDS_LABEL (body, i)
984
      = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail)));
985
 
986
  generating_concat_p = old_generating_concat_p;
987
 
988
  /* Now, for each output, construct an rtx
989
     (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
990
                               ARGVEC CONSTRAINTS OPNAMES))
991
     If there is more than one, put them inside a PARALLEL.  */
992
 
993
  if (nlabels > 0 && nclobbers == 0)
994
    {
995
      gcc_assert (noutputs == 0);
996
      emit_jump_insn (body);
997
    }
998
  else if (noutputs == 0 && nclobbers == 0)
999
    {
1000
      /* No output operands: put in a raw ASM_OPERANDS rtx.  */
1001
      emit_insn (body);
1002
    }
1003
  else if (noutputs == 1 && nclobbers == 0)
1004
    {
1005
      ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
1006
      emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1007
    }
1008
  else
1009
    {
1010
      rtx obody = body;
1011
      int num = noutputs;
1012
 
1013
      if (num == 0)
1014
        num = 1;
1015
 
1016
      body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1017
 
1018
      /* For each output operand, store a SET.  */
1019
      for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1020
        {
1021
          XVECEXP (body, 0, i)
1022
            = gen_rtx_SET (VOIDmode,
1023
                           output_rtx[i],
1024
                           gen_rtx_ASM_OPERANDS
1025
                           (GET_MODE (output_rtx[i]),
1026
                            ggc_strdup (TREE_STRING_POINTER (string)),
1027
                            ggc_strdup (constraints[i]),
1028
                            i, argvec, constraintvec, labelvec, locus));
1029
 
1030
          MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1031
        }
1032
 
1033
      /* If there are no outputs (but there are some clobbers)
1034
         store the bare ASM_OPERANDS into the PARALLEL.  */
1035
 
1036
      if (i == 0)
1037
        XVECEXP (body, 0, i++) = obody;
1038
 
1039
      /* Store (clobber REG) for each clobbered register specified.  */
1040
 
1041
      for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1042
        {
1043
          const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1044
          int reg, nregs;
1045
          int j = decode_reg_name_and_count (regname, &nregs);
1046
          rtx clobbered_reg;
1047
 
1048
          if (j < 0)
1049
            {
1050
              if (j == -3)      /* `cc', which is not a register */
1051
                continue;
1052
 
1053
              if (j == -4)      /* `memory', don't cache memory across asm */
1054
                {
1055
                  XVECEXP (body, 0, i++)
1056
                    = gen_rtx_CLOBBER (VOIDmode,
1057
                                       gen_rtx_MEM
1058
                                       (BLKmode,
1059
                                        gen_rtx_SCRATCH (VOIDmode)));
1060
                  continue;
1061
                }
1062
 
1063
              /* Ignore unknown register, error already signaled.  */
1064
              continue;
1065
            }
1066
 
1067
          for (reg = j; reg < j + nregs; reg++)
1068
            {
1069
              /* Use QImode since that's guaranteed to clobber just
1070
               * one reg.  */
1071
              clobbered_reg = gen_rtx_REG (QImode, reg);
1072
 
1073
              /* Do sanity check for overlap between clobbers and
1074
                 respectively input and outputs that hasn't been
1075
                 handled.  Such overlap should have been detected and
1076
                 reported above.  */
1077
              if (!clobber_conflict_found)
1078
                {
1079
                  int opno;
1080
 
1081
                  /* We test the old body (obody) contents to avoid
1082
                     tripping over the under-construction body.  */
1083
                  for (opno = 0; opno < noutputs; opno++)
1084
                    if (reg_overlap_mentioned_p (clobbered_reg,
1085
                                                 output_rtx[opno]))
1086
                      internal_error
1087
                        ("asm clobber conflict with output operand");
1088
 
1089
                  for (opno = 0; opno < ninputs - ninout; opno++)
1090
                    if (reg_overlap_mentioned_p (clobbered_reg,
1091
                                                 ASM_OPERANDS_INPUT (obody,
1092
                                                                     opno)))
1093
                      internal_error
1094
                        ("asm clobber conflict with input operand");
1095
                }
1096
 
1097
              XVECEXP (body, 0, i++)
1098
                = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1099
            }
1100
        }
1101
 
1102
      if (nlabels > 0)
1103
        emit_jump_insn (body);
1104
      else
1105
        emit_insn (body);
1106
    }
1107
 
1108
  /* For any outputs that needed reloading into registers, spill them
1109
     back to where they belong.  */
1110
  for (i = 0; i < noutputs; ++i)
1111
    if (real_output_rtx[i])
1112
      emit_move_insn (real_output_rtx[i], output_rtx[i]);
1113
 
1114
  crtl->has_asm_statement = 1;
1115
  free_temp_slots ();
1116
}
1117
 
1118
void
1119
expand_asm_stmt (gimple stmt)
1120
{
1121
  int noutputs;
1122
  tree outputs, tail, t;
1123
  tree *o;
1124
  size_t i, n;
1125
  const char *s;
1126
  tree str, out, in, cl, labels;
1127
  location_t locus = gimple_location (stmt);
1128
 
1129
  /* Meh... convert the gimple asm operands into real tree lists.
1130
     Eventually we should make all routines work on the vectors instead
1131
     of relying on TREE_CHAIN.  */
1132
  out = NULL_TREE;
1133
  n = gimple_asm_noutputs (stmt);
1134
  if (n > 0)
1135
    {
1136
      t = out = gimple_asm_output_op (stmt, 0);
1137
      for (i = 1; i < n; i++)
1138
        t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
1139
    }
1140
 
1141
  in = NULL_TREE;
1142
  n = gimple_asm_ninputs (stmt);
1143
  if (n > 0)
1144
    {
1145
      t = in = gimple_asm_input_op (stmt, 0);
1146
      for (i = 1; i < n; i++)
1147
        t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
1148
    }
1149
 
1150
  cl = NULL_TREE;
1151
  n = gimple_asm_nclobbers (stmt);
1152
  if (n > 0)
1153
    {
1154
      t = cl = gimple_asm_clobber_op (stmt, 0);
1155
      for (i = 1; i < n; i++)
1156
        t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
1157
    }
1158
 
1159
  labels = NULL_TREE;
1160
  n = gimple_asm_nlabels (stmt);
1161
  if (n > 0)
1162
    {
1163
      t = labels = gimple_asm_label_op (stmt, 0);
1164
      for (i = 1; i < n; i++)
1165
        t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i);
1166
    }
1167
 
1168
  s = gimple_asm_string (stmt);
1169
  str = build_string (strlen (s), s);
1170
 
1171
  if (gimple_asm_input_p (stmt))
1172
    {
1173
      expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus);
1174
      return;
1175
    }
1176
 
1177
  outputs = out;
1178
  noutputs = gimple_asm_noutputs (stmt);
1179
  /* o[I] is the place that output number I should be written.  */
1180
  o = (tree *) alloca (noutputs * sizeof (tree));
1181
 
1182
  /* Record the contents of OUTPUTS before it is modified.  */
1183
  for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1184
    o[i] = TREE_VALUE (tail);
1185
 
1186
  /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1187
     OUTPUTS some trees for where the values were actually stored.  */
1188
  expand_asm_operands (str, outputs, in, cl, labels,
1189
                       gimple_asm_volatile_p (stmt), locus);
1190
 
1191
  /* Copy all the intermediate outputs into the specified outputs.  */
1192
  for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1193
    {
1194
      if (o[i] != TREE_VALUE (tail))
1195
        {
1196
          expand_assignment (o[i], TREE_VALUE (tail), false);
1197
          free_temp_slots ();
1198
 
1199
          /* Restore the original value so that it's correct the next
1200
             time we expand this function.  */
1201
          TREE_VALUE (tail) = o[i];
1202
        }
1203
    }
1204
}
1205
 
1206
/* A subroutine of expand_asm_operands.  Check that all operands have
1207
   the same number of alternatives.  Return true if so.  */
1208
 
1209
static bool
1210
check_operand_nalternatives (tree outputs, tree inputs)
1211
{
1212
  if (outputs || inputs)
1213
    {
1214
      tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1215
      int nalternatives
1216
        = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1217
      tree next = inputs;
1218
 
1219
      if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1220
        {
1221
          error ("too many alternatives in %<asm%>");
1222
          return false;
1223
        }
1224
 
1225
      tmp = outputs;
1226
      while (tmp)
1227
        {
1228
          const char *constraint
1229
            = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1230
 
1231
          if (n_occurrences (',', constraint) != nalternatives)
1232
            {
1233
              error ("operand constraints for %<asm%> differ "
1234
                     "in number of alternatives");
1235
              return false;
1236
            }
1237
 
1238
          if (TREE_CHAIN (tmp))
1239
            tmp = TREE_CHAIN (tmp);
1240
          else
1241
            tmp = next, next = 0;
1242
        }
1243
    }
1244
 
1245
  return true;
1246
}
1247
 
1248
/* A subroutine of expand_asm_operands.  Check that all operand names
1249
   are unique.  Return true if so.  We rely on the fact that these names
1250
   are identifiers, and so have been canonicalized by get_identifier,
1251
   so all we need are pointer comparisons.  */
1252
 
1253
static bool
1254
check_unique_operand_names (tree outputs, tree inputs, tree labels)
1255
{
1256
  tree i, j, i_name = NULL_TREE;
1257
 
1258
  for (i = outputs; i ; i = TREE_CHAIN (i))
1259
    {
1260
      i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1261
      if (! i_name)
1262
        continue;
1263
 
1264
      for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1265
        if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1266
          goto failure;
1267
    }
1268
 
1269
  for (i = inputs; i ; i = TREE_CHAIN (i))
1270
    {
1271
      i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1272
      if (! i_name)
1273
        continue;
1274
 
1275
      for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1276
        if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1277
          goto failure;
1278
      for (j = outputs; j ; j = TREE_CHAIN (j))
1279
        if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1280
          goto failure;
1281
    }
1282
 
1283
  for (i = labels; i ; i = TREE_CHAIN (i))
1284
    {
1285
      i_name = TREE_PURPOSE (i);
1286
      if (! i_name)
1287
        continue;
1288
 
1289
      for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1290
        if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
1291
          goto failure;
1292
      for (j = inputs; j ; j = TREE_CHAIN (j))
1293
        if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1294
          goto failure;
1295
    }
1296
 
1297
  return true;
1298
 
1299
 failure:
1300
  error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
1301
  return false;
1302
}
1303
 
1304
/* A subroutine of expand_asm_operands.  Resolve the names of the operands
1305
   in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1306
   STRING and in the constraints to those numbers.  */
1307
 
1308
tree
1309
resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
1310
{
1311
  char *buffer;
1312
  char *p;
1313
  const char *c;
1314
  tree t;
1315
 
1316
  check_unique_operand_names (outputs, inputs, labels);
1317
 
1318
  /* Substitute [<name>] in input constraint strings.  There should be no
1319
     named operands in output constraints.  */
1320
  for (t = inputs; t ; t = TREE_CHAIN (t))
1321
    {
1322
      c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1323
      if (strchr (c, '[') != NULL)
1324
        {
1325
          p = buffer = xstrdup (c);
1326
          while ((p = strchr (p, '[')) != NULL)
1327
            p = resolve_operand_name_1 (p, outputs, inputs, NULL);
1328
          TREE_VALUE (TREE_PURPOSE (t))
1329
            = build_string (strlen (buffer), buffer);
1330
          free (buffer);
1331
        }
1332
    }
1333
 
1334
  /* Now check for any needed substitutions in the template.  */
1335
  c = TREE_STRING_POINTER (string);
1336
  while ((c = strchr (c, '%')) != NULL)
1337
    {
1338
      if (c[1] == '[')
1339
        break;
1340
      else if (ISALPHA (c[1]) && c[2] == '[')
1341
        break;
1342
      else
1343
        {
1344
          c += 1 + (c[1] == '%');
1345
          continue;
1346
        }
1347
    }
1348
 
1349
  if (c)
1350
    {
1351
      /* OK, we need to make a copy so we can perform the substitutions.
1352
         Assume that we will not need extra space--we get to remove '['
1353
         and ']', which means we cannot have a problem until we have more
1354
         than 999 operands.  */
1355
      buffer = xstrdup (TREE_STRING_POINTER (string));
1356
      p = buffer + (c - TREE_STRING_POINTER (string));
1357
 
1358
      while ((p = strchr (p, '%')) != NULL)
1359
        {
1360
          if (p[1] == '[')
1361
            p += 1;
1362
          else if (ISALPHA (p[1]) && p[2] == '[')
1363
            p += 2;
1364
          else
1365
            {
1366
              p += 1 + (p[1] == '%');
1367
              continue;
1368
            }
1369
 
1370
          p = resolve_operand_name_1 (p, outputs, inputs, labels);
1371
        }
1372
 
1373
      string = build_string (strlen (buffer), buffer);
1374
      free (buffer);
1375
    }
1376
 
1377
  return string;
1378
}
1379
 
1380
/* A subroutine of resolve_operand_names.  P points to the '[' for a
1381
   potential named operand of the form [<name>].  In place, replace
1382
   the name and brackets with a number.  Return a pointer to the
1383
   balance of the string after substitution.  */
1384
 
1385
static char *
1386
resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
1387
{
1388
  char *q;
1389
  int op;
1390
  tree t;
1391
 
1392
  /* Collect the operand name.  */
1393
  q = strchr (++p, ']');
1394
  if (!q)
1395
    {
1396
      error ("missing close brace for named operand");
1397
      return strchr (p, '\0');
1398
    }
1399
  *q = '\0';
1400
 
1401
  /* Resolve the name to a number.  */
1402
  for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1403
    {
1404
      tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1405
      if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1406
        goto found;
1407
    }
1408
  for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1409
    {
1410
      tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1411
      if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1412
        goto found;
1413
    }
1414
  for (t = labels; t ; t = TREE_CHAIN (t), op++)
1415
    {
1416
      tree name = TREE_PURPOSE (t);
1417
      if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1418
        goto found;
1419
    }
1420
 
1421
  error ("undefined named operand %qs", identifier_to_locale (p));
1422
  op = 0;
1423
 
1424
 found:
1425
  /* Replace the name with the number.  Unfortunately, not all libraries
1426
     get the return value of sprintf correct, so search for the end of the
1427
     generated string by hand.  */
1428
  sprintf (--p, "%d", op);
1429
  p = strchr (p, '\0');
1430
 
1431
  /* Verify the no extra buffer space assumption.  */
1432
  gcc_assert (p <= q);
1433
 
1434
  /* Shift the rest of the buffer down to fill the gap.  */
1435
  memmove (p, q + 1, strlen (q + 1) + 1);
1436
 
1437
  return p;
1438
}
1439
 
1440
/* Generate RTL to evaluate the expression EXP.  */
1441
 
1442
void
1443
expand_expr_stmt (tree exp)
1444
{
1445
  rtx value;
1446
  tree type;
1447
 
1448
  value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1449
  type = TREE_TYPE (exp);
1450
 
1451
  /* If all we do is reference a volatile value in memory,
1452
     copy it to a register to be sure it is actually touched.  */
1453
  if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1454
    {
1455
      if (TYPE_MODE (type) == VOIDmode)
1456
        ;
1457
      else if (TYPE_MODE (type) != BLKmode)
1458
        copy_to_reg (value);
1459
      else
1460
        {
1461
          rtx lab = gen_label_rtx ();
1462
 
1463
          /* Compare the value with itself to reference it.  */
1464
          emit_cmp_and_jump_insns (value, value, EQ,
1465
                                   expand_normal (TYPE_SIZE (type)),
1466
                                   BLKmode, 0, lab);
1467
          emit_label (lab);
1468
        }
1469
    }
1470
 
1471
  /* Free any temporaries used to evaluate this expression.  */
1472
  free_temp_slots ();
1473
}
1474
 
1475
/* Warn if EXP contains any computations whose results are not used.
1476
   Return 1 if a warning is printed; 0 otherwise.  LOCUS is the
1477
   (potential) location of the expression.  */
1478
 
1479
int
1480
warn_if_unused_value (const_tree exp, location_t locus)
1481
{
1482
 restart:
1483
  if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1484
    return 0;
1485
 
1486
  /* Don't warn about void constructs.  This includes casting to void,
1487
     void function calls, and statement expressions with a final cast
1488
     to void.  */
1489
  if (VOID_TYPE_P (TREE_TYPE (exp)))
1490
    return 0;
1491
 
1492
  if (EXPR_HAS_LOCATION (exp))
1493
    locus = EXPR_LOCATION (exp);
1494
 
1495
  switch (TREE_CODE (exp))
1496
    {
1497
    case PREINCREMENT_EXPR:
1498
    case POSTINCREMENT_EXPR:
1499
    case PREDECREMENT_EXPR:
1500
    case POSTDECREMENT_EXPR:
1501
    case MODIFY_EXPR:
1502
    case INIT_EXPR:
1503
    case TARGET_EXPR:
1504
    case CALL_EXPR:
1505
    case TRY_CATCH_EXPR:
1506
    case WITH_CLEANUP_EXPR:
1507
    case EXIT_EXPR:
1508
    case VA_ARG_EXPR:
1509
      return 0;
1510
 
1511
    case BIND_EXPR:
1512
      /* For a binding, warn if no side effect within it.  */
1513
      exp = BIND_EXPR_BODY (exp);
1514
      goto restart;
1515
 
1516
    case SAVE_EXPR:
1517
    case NON_LVALUE_EXPR:
1518
      exp = TREE_OPERAND (exp, 0);
1519
      goto restart;
1520
 
1521
    case TRUTH_ORIF_EXPR:
1522
    case TRUTH_ANDIF_EXPR:
1523
      /* In && or ||, warn if 2nd operand has no side effect.  */
1524
      exp = TREE_OPERAND (exp, 1);
1525
      goto restart;
1526
 
1527
    case COMPOUND_EXPR:
1528
      if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1529
        return 1;
1530
      /* Let people do `(foo (), 0)' without a warning.  */
1531
      if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1532
        return 0;
1533
      exp = TREE_OPERAND (exp, 1);
1534
      goto restart;
1535
 
1536
    case COND_EXPR:
1537
      /* If this is an expression with side effects, don't warn; this
1538
         case commonly appears in macro expansions.  */
1539
      if (TREE_SIDE_EFFECTS (exp))
1540
        return 0;
1541
      goto warn;
1542
 
1543
    case INDIRECT_REF:
1544
      /* Don't warn about automatic dereferencing of references, since
1545
         the user cannot control it.  */
1546
      if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1547
        {
1548
          exp = TREE_OPERAND (exp, 0);
1549
          goto restart;
1550
        }
1551
      /* Fall through.  */
1552
 
1553
    default:
1554
      /* Referencing a volatile value is a side effect, so don't warn.  */
1555
      if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1556
          && TREE_THIS_VOLATILE (exp))
1557
        return 0;
1558
 
1559
      /* If this is an expression which has no operands, there is no value
1560
         to be unused.  There are no such language-independent codes,
1561
         but front ends may define such.  */
1562
      if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1563
        return 0;
1564
 
1565
    warn:
1566
      warning_at (locus, OPT_Wunused_value, "value computed is not used");
1567
      return 1;
1568
    }
1569
}
1570
 
1571
 
1572
/* Generate RTL to return from the current function, with no value.
1573
   (That is, we do not do anything about returning any value.)  */
1574
 
1575
void
1576
expand_null_return (void)
1577
{
1578
  /* If this function was declared to return a value, but we
1579
     didn't, clobber the return registers so that they are not
1580
     propagated live to the rest of the function.  */
1581
  clobber_return_register ();
1582
 
1583
  expand_null_return_1 ();
1584
}
1585
 
1586
/* Generate RTL to return directly from the current function.
1587
   (That is, we bypass any return value.)  */
1588
 
1589
void
1590
expand_naked_return (void)
1591
{
1592
  rtx end_label;
1593
 
1594
  clear_pending_stack_adjust ();
1595
  do_pending_stack_adjust ();
1596
 
1597
  end_label = naked_return_label;
1598
  if (end_label == 0)
1599
    end_label = naked_return_label = gen_label_rtx ();
1600
 
1601
  emit_jump (end_label);
1602
}
1603
 
1604
/* Generate RTL to return from the current function, with value VAL.  */
1605
 
1606
static void
1607
expand_value_return (rtx val)
1608
{
1609
  /* Copy the value to the return location unless it's already there.  */
1610
 
1611
  tree decl = DECL_RESULT (current_function_decl);
1612
  rtx return_reg = DECL_RTL (decl);
1613
  if (return_reg != val)
1614
    {
1615
      tree funtype = TREE_TYPE (current_function_decl);
1616
      tree type = TREE_TYPE (decl);
1617
      int unsignedp = TYPE_UNSIGNED (type);
1618
      enum machine_mode old_mode = DECL_MODE (decl);
1619
      enum machine_mode mode;
1620
      if (DECL_BY_REFERENCE (decl))
1621
        mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2);
1622
      else
1623
        mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1);
1624
 
1625
      if (mode != old_mode)
1626
        val = convert_modes (mode, old_mode, val, unsignedp);
1627
 
1628
      if (GET_CODE (return_reg) == PARALLEL)
1629
        emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1630
      else
1631
        emit_move_insn (return_reg, val);
1632
    }
1633
 
1634
  expand_null_return_1 ();
1635
}
1636
 
1637
/* Output a return with no value.  */
1638
 
1639
static void
1640
expand_null_return_1 (void)
1641
{
1642
  clear_pending_stack_adjust ();
1643
  do_pending_stack_adjust ();
1644
  emit_jump (return_label);
1645
}
1646
 
1647
/* Generate RTL to evaluate the expression RETVAL and return it
1648
   from the current function.  */
1649
 
1650
void
1651
expand_return (tree retval)
1652
{
1653
  rtx result_rtl;
1654
  rtx val = 0;
1655
  tree retval_rhs;
1656
 
1657
  /* If function wants no value, give it none.  */
1658
  if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1659
    {
1660
      expand_normal (retval);
1661
      expand_null_return ();
1662
      return;
1663
    }
1664
 
1665
  if (retval == error_mark_node)
1666
    {
1667
      /* Treat this like a return of no value from a function that
1668
         returns a value.  */
1669
      expand_null_return ();
1670
      return;
1671
    }
1672
  else if ((TREE_CODE (retval) == MODIFY_EXPR
1673
            || TREE_CODE (retval) == INIT_EXPR)
1674
           && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1675
    retval_rhs = TREE_OPERAND (retval, 1);
1676
  else
1677
    retval_rhs = retval;
1678
 
1679
  result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1680
 
1681
  /* If we are returning the RESULT_DECL, then the value has already
1682
     been stored into it, so we don't have to do anything special.  */
1683
  if (TREE_CODE (retval_rhs) == RESULT_DECL)
1684
    expand_value_return (result_rtl);
1685
 
1686
  /* If the result is an aggregate that is being returned in one (or more)
1687
     registers, load the registers here.  */
1688
 
1689
  else if (retval_rhs != 0
1690
           && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1691
           && REG_P (result_rtl))
1692
    {
1693
      val = copy_blkmode_to_reg (GET_MODE (result_rtl), retval_rhs);
1694
      if (val)
1695
        {
1696
          /* Use the mode of the result value on the return register.  */
1697
          PUT_MODE (result_rtl, GET_MODE (val));
1698
          expand_value_return (val);
1699
        }
1700
      else
1701
        expand_null_return ();
1702
    }
1703
  else if (retval_rhs != 0
1704
           && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1705
           && (REG_P (result_rtl)
1706
               || (GET_CODE (result_rtl) == PARALLEL)))
1707
    {
1708
      /* Calculate the return value into a temporary (usually a pseudo
1709
         reg).  */
1710
      tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1711
      tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1712
 
1713
      val = assign_temp (nt, 0, 0, 1);
1714
      val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1715
      val = force_not_mem (val);
1716
      /* Return the calculated value.  */
1717
      expand_value_return (val);
1718
    }
1719
  else
1720
    {
1721
      /* No hard reg used; calculate value into hard return reg.  */
1722
      expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1723
      expand_value_return (result_rtl);
1724
    }
1725
}
1726
 
1727
/* Emit code to restore vital registers at the beginning of a nonlocal goto
1728
   handler.  */
1729
static void
1730
expand_nl_goto_receiver (void)
1731
{
1732
  rtx chain;
1733
 
1734
  /* Clobber the FP when we get here, so we have to make sure it's
1735
     marked as used by this function.  */
1736
  emit_use (hard_frame_pointer_rtx);
1737
 
1738
  /* Mark the static chain as clobbered here so life information
1739
     doesn't get messed up for it.  */
1740
  chain = targetm.calls.static_chain (current_function_decl, true);
1741
  if (chain && REG_P (chain))
1742
    emit_clobber (chain);
1743
 
1744
#ifdef HAVE_nonlocal_goto
1745
  if (! HAVE_nonlocal_goto)
1746
#endif
1747
    /* First adjust our frame pointer to its actual value.  It was
1748
       previously set to the start of the virtual area corresponding to
1749
       the stacked variables when we branched here and now needs to be
1750
       adjusted to the actual hardware fp value.
1751
 
1752
       Assignments are to virtual registers are converted by
1753
       instantiate_virtual_regs into the corresponding assignment
1754
       to the underlying register (fp in this case) that makes
1755
       the original assignment true.
1756
       So the following insn will actually be
1757
       decrementing fp by STARTING_FRAME_OFFSET.  */
1758
    emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1759
 
1760
#if !HARD_FRAME_POINTER_IS_ARG_POINTER
1761
  if (fixed_regs[ARG_POINTER_REGNUM])
1762
    {
1763
#ifdef ELIMINABLE_REGS
1764
      /* If the argument pointer can be eliminated in favor of the
1765
         frame pointer, we don't need to restore it.  We assume here
1766
         that if such an elimination is present, it can always be used.
1767
         This is the case on all known machines; if we don't make this
1768
         assumption, we do unnecessary saving on many machines.  */
1769
      static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1770
      size_t i;
1771
 
1772
      for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1773
        if (elim_regs[i].from == ARG_POINTER_REGNUM
1774
            && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1775
          break;
1776
 
1777
      if (i == ARRAY_SIZE (elim_regs))
1778
#endif
1779
        {
1780
          /* Now restore our arg pointer from the address at which it
1781
             was saved in our stack frame.  */
1782
          emit_move_insn (crtl->args.internal_arg_pointer,
1783
                          copy_to_reg (get_arg_pointer_save_area ()));
1784
        }
1785
    }
1786
#endif
1787
 
1788
#ifdef HAVE_nonlocal_goto_receiver
1789
  if (HAVE_nonlocal_goto_receiver)
1790
    emit_insn (gen_nonlocal_goto_receiver ());
1791
#endif
1792
 
1793
  /* We must not allow the code we just generated to be reordered by
1794
     scheduling.  Specifically, the update of the frame pointer must
1795
     happen immediately, not later.  */
1796
  emit_insn (gen_blockage ());
1797
}
1798
 
1799
/* Generate RTL for the automatic variable declaration DECL.
1800
   (Other kinds of declarations are simply ignored if seen here.)  */
1801
 
1802
void
1803
expand_decl (tree decl)
1804
{
1805
  tree type;
1806
 
1807
  type = TREE_TYPE (decl);
1808
 
1809
  /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1810
     type in case this node is used in a reference.  */
1811
  if (TREE_CODE (decl) == CONST_DECL)
1812
    {
1813
      DECL_MODE (decl) = TYPE_MODE (type);
1814
      DECL_ALIGN (decl) = TYPE_ALIGN (type);
1815
      DECL_SIZE (decl) = TYPE_SIZE (type);
1816
      DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1817
      return;
1818
    }
1819
 
1820
  /* Otherwise, only automatic variables need any expansion done.  Static and
1821
     external variables, and external functions, will be handled by
1822
     `assemble_variable' (called from finish_decl).  TYPE_DECL requires
1823
     nothing.  PARM_DECLs are handled in `assign_parms'.  */
1824
  if (TREE_CODE (decl) != VAR_DECL)
1825
    return;
1826
 
1827
  if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1828
    return;
1829
 
1830
  /* Create the RTL representation for the variable.  */
1831
 
1832
  if (type == error_mark_node)
1833
    SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1834
 
1835
  else if (DECL_SIZE (decl) == 0)
1836
    {
1837
      /* Variable with incomplete type.  */
1838
      rtx x;
1839
      if (DECL_INITIAL (decl) == 0)
1840
        /* Error message was already done; now avoid a crash.  */
1841
        x = gen_rtx_MEM (BLKmode, const0_rtx);
1842
      else
1843
        /* An initializer is going to decide the size of this array.
1844
           Until we know the size, represent its address with a reg.  */
1845
        x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1846
 
1847
      set_mem_attributes (x, decl, 1);
1848
      SET_DECL_RTL (decl, x);
1849
    }
1850
  else if (use_register_for_decl (decl))
1851
    {
1852
      /* Automatic variable that can go in a register.  */
1853
      enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
1854
 
1855
      SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1856
 
1857
      /* Note if the object is a user variable.  */
1858
      if (!DECL_ARTIFICIAL (decl))
1859
          mark_user_reg (DECL_RTL (decl));
1860
 
1861
      if (POINTER_TYPE_P (type))
1862
        mark_reg_pointer (DECL_RTL (decl),
1863
                          TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1864
    }
1865
 
1866
  else
1867
    {
1868
      rtx oldaddr = 0;
1869
      rtx addr;
1870
      rtx x;
1871
 
1872
      /* Variable-sized decls are dealt with in the gimplifier.  */
1873
      gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
1874
 
1875
      /* If we previously made RTL for this decl, it must be an array
1876
         whose size was determined by the initializer.
1877
         The old address was a register; set that register now
1878
         to the proper address.  */
1879
      if (DECL_RTL_SET_P (decl))
1880
        {
1881
          gcc_assert (MEM_P (DECL_RTL (decl)));
1882
          gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1883
          oldaddr = XEXP (DECL_RTL (decl), 0);
1884
        }
1885
 
1886
      /* Set alignment we actually gave this decl.  */
1887
      DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1888
                           : GET_MODE_BITSIZE (DECL_MODE (decl)));
1889
      DECL_USER_ALIGN (decl) = 0;
1890
 
1891
      x = assign_temp (decl, 1, 1, 1);
1892
      set_mem_attributes (x, decl, 1);
1893
      SET_DECL_RTL (decl, x);
1894
 
1895
      if (oldaddr)
1896
        {
1897
          addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1898
          if (addr != oldaddr)
1899
            emit_move_insn (oldaddr, addr);
1900
        }
1901
    }
1902
}
1903
 
1904
/* Emit code to save the current value of stack.  */
1905
rtx
1906
expand_stack_save (void)
1907
{
1908
  rtx ret = NULL_RTX;
1909
 
1910
  do_pending_stack_adjust ();
1911
  emit_stack_save (SAVE_BLOCK, &ret);
1912
  return ret;
1913
}
1914
 
1915
/* Emit code to restore the current value of stack.  */
1916
void
1917
expand_stack_restore (tree var)
1918
{
1919
  rtx prev, sa = expand_normal (var);
1920
 
1921
  sa = convert_memory_address (Pmode, sa);
1922
 
1923
  prev = get_last_insn ();
1924
  emit_stack_restore (SAVE_BLOCK, sa);
1925
  fixup_args_size_notes (prev, get_last_insn (), 0);
1926
}
1927
 
1928
/* Do the insertion of a case label into case_list.  The labels are
1929
   fed to us in descending order from the sorted vector of case labels used
1930
   in the tree part of the middle end.  So the list we construct is
1931
   sorted in ascending order.  The bounds on the case range, LOW and HIGH,
1932
   are converted to case's index type TYPE.  */
1933
 
1934
static struct case_node *
1935
add_case_node (struct case_node *head, tree type, tree low, tree high,
1936
               tree label, alloc_pool case_node_pool)
1937
{
1938
  tree min_value, max_value;
1939
  struct case_node *r;
1940
 
1941
  gcc_assert (TREE_CODE (low) == INTEGER_CST);
1942
  gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
1943
 
1944
  min_value = TYPE_MIN_VALUE (type);
1945
  max_value = TYPE_MAX_VALUE (type);
1946
 
1947
  /* If there's no HIGH value, then this is not a case range; it's
1948
     just a simple case label.  But that's just a degenerate case
1949
     range.
1950
     If the bounds are equal, turn this into the one-value case.  */
1951
  if (!high || tree_int_cst_equal (low, high))
1952
    {
1953
      /* If the simple case value is unreachable, ignore it.  */
1954
      if ((TREE_CODE (min_value) == INTEGER_CST
1955
            && tree_int_cst_compare (low, min_value) < 0)
1956
          || (TREE_CODE (max_value) == INTEGER_CST
1957
              && tree_int_cst_compare (low, max_value) > 0))
1958
        return head;
1959
      low = fold_convert (type, low);
1960
      high = low;
1961
    }
1962
  else
1963
    {
1964
      /* If the entire case range is unreachable, ignore it.  */
1965
      if ((TREE_CODE (min_value) == INTEGER_CST
1966
            && tree_int_cst_compare (high, min_value) < 0)
1967
          || (TREE_CODE (max_value) == INTEGER_CST
1968
              && tree_int_cst_compare (low, max_value) > 0))
1969
        return head;
1970
 
1971
      /* If the lower bound is less than the index type's minimum
1972
         value, truncate the range bounds.  */
1973
      if (TREE_CODE (min_value) == INTEGER_CST
1974
            && tree_int_cst_compare (low, min_value) < 0)
1975
        low = min_value;
1976
      low = fold_convert (type, low);
1977
 
1978
      /* If the upper bound is greater than the index type's maximum
1979
         value, truncate the range bounds.  */
1980
      if (TREE_CODE (max_value) == INTEGER_CST
1981
          && tree_int_cst_compare (high, max_value) > 0)
1982
        high = max_value;
1983
      high = fold_convert (type, high);
1984
    }
1985
 
1986
 
1987
  /* Add this label to the chain.  Make sure to drop overflow flags.  */
1988
  r = (struct case_node *) pool_alloc (case_node_pool);
1989
  r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
1990
                               TREE_INT_CST_HIGH (low));
1991
  r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
1992
                                TREE_INT_CST_HIGH (high));
1993
  r->code_label = label;
1994
  r->parent = r->left = NULL;
1995
  r->right = head;
1996
  return r;
1997
}
1998
 
1999
/* Maximum number of case bit tests.  */
2000
#define MAX_CASE_BIT_TESTS  3
2001
 
2002
/* By default, enable case bit tests on targets with ashlsi3.  */
2003
#ifndef CASE_USE_BIT_TESTS
2004
#define CASE_USE_BIT_TESTS  (optab_handler (ashl_optab, word_mode) \
2005
                             != CODE_FOR_nothing)
2006
#endif
2007
 
2008
 
2009
/* A case_bit_test represents a set of case nodes that may be
2010
   selected from using a bit-wise comparison.  HI and LO hold
2011
   the integer to be tested against, LABEL contains the label
2012
   to jump to upon success and BITS counts the number of case
2013
   nodes handled by this test, typically the number of bits
2014
   set in HI:LO.  */
2015
 
2016
struct case_bit_test
2017
{
2018
  HOST_WIDE_INT hi;
2019
  HOST_WIDE_INT lo;
2020
  rtx label;
2021
  int bits;
2022
};
2023
 
2024
/* Determine whether "1 << x" is relatively cheap in word_mode.  */
2025
 
2026
static
2027
bool lshift_cheap_p (void)
2028
{
2029
  static bool init[2] = {false, false};
2030
  static bool cheap[2] = {true, true};
2031
 
2032
  bool speed_p = optimize_insn_for_speed_p ();
2033
 
2034
  if (!init[speed_p])
2035
    {
2036
      rtx reg = gen_rtx_REG (word_mode, 10000);
2037
      int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
2038
                               speed_p);
2039
      cheap[speed_p] = cost < COSTS_N_INSNS (3);
2040
      init[speed_p] = true;
2041
    }
2042
 
2043
  return cheap[speed_p];
2044
}
2045
 
2046
/* Comparison function for qsort to order bit tests by decreasing
2047
   number of case nodes, i.e. the node with the most cases gets
2048
   tested first.  */
2049
 
2050
static int
2051
case_bit_test_cmp (const void *p1, const void *p2)
2052
{
2053
  const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
2054
  const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
2055
 
2056
  if (d2->bits != d1->bits)
2057
    return d2->bits - d1->bits;
2058
 
2059
  /* Stabilize the sort.  */
2060
  return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2061
}
2062
 
2063
/*  Expand a switch statement by a short sequence of bit-wise
2064
    comparisons.  "switch(x)" is effectively converted into
2065
    "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2066
    integer constants.
2067
 
2068
    INDEX_EXPR is the value being switched on, which is of
2069
    type INDEX_TYPE.  MINVAL is the lowest case value of in
2070
    the case nodes, of INDEX_TYPE type, and RANGE is highest
2071
    value minus MINVAL, also of type INDEX_TYPE.  NODES is
2072
    the set of case nodes, and DEFAULT_LABEL is the label to
2073
    branch to should none of the cases match.
2074
 
2075
    There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2076
    node targets.  */
2077
 
2078
static void
2079
emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2080
                     tree range, case_node_ptr nodes, rtx default_label)
2081
{
2082
  struct case_bit_test test[MAX_CASE_BIT_TESTS];
2083
  enum machine_mode mode;
2084
  rtx expr, index, label;
2085
  unsigned int i,j,lo,hi;
2086
  struct case_node *n;
2087
  unsigned int count;
2088
 
2089
  count = 0;
2090
  for (n = nodes; n; n = n->right)
2091
    {
2092
      label = label_rtx (n->code_label);
2093
      for (i = 0; i < count; i++)
2094
        if (label == test[i].label)
2095
          break;
2096
 
2097
      if (i == count)
2098
        {
2099
          gcc_assert (count < MAX_CASE_BIT_TESTS);
2100
          test[i].hi = 0;
2101
          test[i].lo = 0;
2102
          test[i].label = label;
2103
          test[i].bits = 1;
2104
          count++;
2105
        }
2106
      else
2107
        test[i].bits++;
2108
 
2109
      lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2110
                                      n->low, minval), 1);
2111
      hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2112
                                      n->high, minval), 1);
2113
      for (j = lo; j <= hi; j++)
2114
        if (j >= HOST_BITS_PER_WIDE_INT)
2115
          test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2116
        else
2117
          test[i].lo |= (HOST_WIDE_INT) 1 << j;
2118
    }
2119
 
2120
  qsort (test, count, sizeof(*test), case_bit_test_cmp);
2121
 
2122
  index_expr = fold_build2 (MINUS_EXPR, index_type,
2123
                            fold_convert (index_type, index_expr),
2124
                            fold_convert (index_type, minval));
2125
  index = expand_normal (index_expr);
2126
  do_pending_stack_adjust ();
2127
 
2128
  mode = TYPE_MODE (index_type);
2129
  expr = expand_normal (range);
2130
  if (default_label)
2131
    emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2132
                             default_label);
2133
 
2134
  index = convert_to_mode (word_mode, index, 0);
2135
  index = expand_binop (word_mode, ashl_optab, const1_rtx,
2136
                        index, NULL_RTX, 1, OPTAB_WIDEN);
2137
 
2138
  for (i = 0; i < count; i++)
2139
    {
2140
      expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2141
      expr = expand_binop (word_mode, and_optab, index, expr,
2142
                           NULL_RTX, 1, OPTAB_WIDEN);
2143
      emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2144
                               word_mode, 1, test[i].label);
2145
    }
2146
 
2147
  if (default_label)
2148
    emit_jump (default_label);
2149
}
2150
 
2151
#ifndef HAVE_casesi
2152
#define HAVE_casesi 0
2153
#endif
2154
 
2155
#ifndef HAVE_tablejump
2156
#define HAVE_tablejump 0
2157
#endif
2158
 
2159
/* Return true if a switch should be expanded as a bit test.
2160
   INDEX_EXPR is the index expression, RANGE is the difference between
2161
   highest and lowest case, UNIQ is number of unique case node targets
2162
   not counting the default case and COUNT is the number of comparisons
2163
   needed, not counting the default case.  */
2164
bool
2165
expand_switch_using_bit_tests_p (tree index_expr, tree range,
2166
                                 unsigned int uniq, unsigned int count)
2167
{
2168
  return (CASE_USE_BIT_TESTS
2169
          && ! TREE_CONSTANT (index_expr)
2170
          && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2171
          && compare_tree_int (range, 0) > 0
2172
          && lshift_cheap_p ()
2173
          && ((uniq == 1 && count >= 3)
2174
              || (uniq == 2 && count >= 5)
2175
              || (uniq == 3 && count >= 6)));
2176
}
2177
 
2178
/* Return the smallest number of different values for which it is best to use a
2179
   jump-table instead of a tree of conditional branches.  */
2180
 
2181
static unsigned int
2182
case_values_threshold (void)
2183
{
2184
  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
2185
 
2186
  if (threshold == 0)
2187
    threshold = targetm.case_values_threshold ();
2188
 
2189
  return threshold;
2190
}
2191
 
2192
/* Terminate a case (Pascal/Ada) or switch (C) statement
2193
   in which ORIG_INDEX is the expression to be tested.
2194
   If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2195
   type as given in the source before any compiler conversions.
2196
   Generate the code to test it and jump to the right place.  */
2197
 
2198
void
2199
expand_case (gimple stmt)
2200
{
2201
  tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2202
  rtx default_label = 0;
2203
  struct case_node *n;
2204
  unsigned int count, uniq;
2205
  rtx index;
2206
  rtx table_label;
2207
  int ncases;
2208
  rtx *labelvec;
2209
  int i;
2210
  rtx before_case, end, lab;
2211
 
2212
  tree index_expr = gimple_switch_index (stmt);
2213
  tree index_type = TREE_TYPE (index_expr);
2214
  int unsignedp = TYPE_UNSIGNED (index_type);
2215
 
2216
  /* The insn after which the case dispatch should finally
2217
     be emitted.  Zero for a dummy.  */
2218
  rtx start;
2219
 
2220
  /* A list of case labels; it is first built as a list and it may then
2221
     be rearranged into a nearly balanced binary tree.  */
2222
  struct case_node *case_list = 0;
2223
 
2224
  /* Label to jump to if no case matches.  */
2225
  tree default_label_decl = NULL_TREE;
2226
 
2227
  alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2228
                                                 sizeof (struct case_node),
2229
                                                 100);
2230
 
2231
  do_pending_stack_adjust ();
2232
 
2233
  /* An ERROR_MARK occurs for various reasons including invalid data type.  */
2234
  if (index_type != error_mark_node)
2235
    {
2236
      tree elt;
2237
      bitmap label_bitmap;
2238
      int stopi = 0;
2239
 
2240
      /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2241
         expressions being INTEGER_CST.  */
2242
      gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2243
 
2244
      /* The default case, if ever taken, is the first element.  */
2245
      elt = gimple_switch_label (stmt, 0);
2246
      if (!CASE_LOW (elt) && !CASE_HIGH (elt))
2247
        {
2248
          default_label_decl = CASE_LABEL (elt);
2249
          stopi = 1;
2250
        }
2251
 
2252
      for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
2253
        {
2254
          tree low, high;
2255
          elt = gimple_switch_label (stmt, i);
2256
 
2257
          low = CASE_LOW (elt);
2258
          gcc_assert (low);
2259
          high = CASE_HIGH (elt);
2260
 
2261
          /* Discard empty ranges.  */
2262
          if (high && tree_int_cst_lt (high, low))
2263
            continue;
2264
 
2265
          case_list = add_case_node (case_list, index_type, low, high,
2266
                                     CASE_LABEL (elt), case_node_pool);
2267
        }
2268
 
2269
 
2270
      before_case = start = get_last_insn ();
2271
      if (default_label_decl)
2272
        default_label = label_rtx (default_label_decl);
2273
 
2274
      /* Get upper and lower bounds of case values.  */
2275
 
2276
      uniq = 0;
2277
      count = 0;
2278
      label_bitmap = BITMAP_ALLOC (NULL);
2279
      for (n = case_list; n; n = n->right)
2280
        {
2281
          /* Count the elements and track the largest and smallest
2282
             of them (treating them as signed even if they are not).  */
2283
          if (count++ == 0)
2284
            {
2285
              minval = n->low;
2286
              maxval = n->high;
2287
            }
2288
          else
2289
            {
2290
              if (tree_int_cst_lt (n->low, minval))
2291
                minval = n->low;
2292
              if (tree_int_cst_lt (maxval, n->high))
2293
                maxval = n->high;
2294
            }
2295
          /* A range counts double, since it requires two compares.  */
2296
          if (! tree_int_cst_equal (n->low, n->high))
2297
            count++;
2298
 
2299
          /* If we have not seen this label yet, then increase the
2300
             number of unique case node targets seen.  */
2301
          lab = label_rtx (n->code_label);
2302
          if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
2303
            uniq++;
2304
        }
2305
 
2306
      BITMAP_FREE (label_bitmap);
2307
 
2308
      /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2309
         destination, such as one with a default case only.  However,
2310
         it doesn't remove cases that are out of range for the switch
2311
         type, so we may still get a zero here.  */
2312
      if (count == 0)
2313
        {
2314
          if (default_label)
2315
            emit_jump (default_label);
2316
          free_alloc_pool (case_node_pool);
2317
          return;
2318
        }
2319
 
2320
      /* Compute span of values.  */
2321
      range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2322
 
2323
      /* Try implementing this switch statement by a short sequence of
2324
         bit-wise comparisons.  However, we let the binary-tree case
2325
         below handle constant index expressions.  */
2326
      if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count))
2327
        {
2328
          /* Optimize the case where all the case values fit in a
2329
             word without having to subtract MINVAL.  In this case,
2330
             we can optimize away the subtraction.  */
2331
          if (compare_tree_int (minval, 0) > 0
2332
              && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2333
            {
2334
              minval = build_int_cst (index_type, 0);
2335
              range = maxval;
2336
            }
2337
          emit_case_bit_tests (index_type, index_expr, minval, range,
2338
                               case_list, default_label);
2339
        }
2340
 
2341
      /* If range of values is much bigger than number of values,
2342
         make a sequence of conditional branches instead of a dispatch.
2343
         If the switch-index is a constant, do it this way
2344
         because we can optimize it.  */
2345
 
2346
      else if (count < case_values_threshold ()
2347
               || compare_tree_int (range,
2348
                                    (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
2349
               /* RANGE may be signed, and really large ranges will show up
2350
                  as negative numbers.  */
2351
               || compare_tree_int (range, 0) < 0
2352
#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2353
               || flag_pic
2354
#endif
2355
               || !flag_jump_tables
2356
               || TREE_CONSTANT (index_expr)
2357
               /* If neither casesi or tablejump is available, we can
2358
                  only go this way.  */
2359
               || (!HAVE_casesi && !HAVE_tablejump))
2360
        {
2361
          index = expand_normal (index_expr);
2362
 
2363
          /* If the index is a short or char that we do not have
2364
             an insn to handle comparisons directly, convert it to
2365
             a full integer now, rather than letting each comparison
2366
             generate the conversion.  */
2367
 
2368
          if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2369
              && ! have_insn_for (COMPARE, GET_MODE (index)))
2370
            {
2371
              enum machine_mode wider_mode;
2372
              for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2373
                   wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2374
                if (have_insn_for (COMPARE, wider_mode))
2375
                  {
2376
                    index = convert_to_mode (wider_mode, index, unsignedp);
2377
                    break;
2378
                  }
2379
            }
2380
 
2381
          do_pending_stack_adjust ();
2382
 
2383
          if (MEM_P (index))
2384
            index = copy_to_reg (index);
2385
 
2386
          /* We generate a binary decision tree to select the
2387
             appropriate target code.  This is done as follows:
2388
 
2389
             The list of cases is rearranged into a binary tree,
2390
             nearly optimal assuming equal probability for each case.
2391
 
2392
             The tree is transformed into RTL, eliminating
2393
             redundant test conditions at the same time.
2394
 
2395
             If program flow could reach the end of the
2396
             decision tree an unconditional jump to the
2397
             default code is emitted.  */
2398
 
2399
          use_cost_table = estimate_case_costs (case_list);
2400
          balance_case_nodes (&case_list, NULL);
2401
          emit_case_nodes (index, case_list, default_label, index_type);
2402
          if (default_label)
2403
            emit_jump (default_label);
2404
        }
2405
      else
2406
        {
2407
          rtx fallback_label = label_rtx (case_list->code_label);
2408
          table_label = gen_label_rtx ();
2409
          if (! try_casesi (index_type, index_expr, minval, range,
2410
                            table_label, default_label, fallback_label))
2411
            {
2412
              bool ok;
2413
 
2414
              /* Index jumptables from zero for suitable values of
2415
                 minval to avoid a subtraction.  */
2416
              if (optimize_insn_for_speed_p ()
2417
                  && compare_tree_int (minval, 0) > 0
2418
                  && compare_tree_int (minval, 3) < 0)
2419
                {
2420
                  minval = build_int_cst (index_type, 0);
2421
                  range = maxval;
2422
                }
2423
 
2424
              ok = try_tablejump (index_type, index_expr, minval, range,
2425
                                  table_label, default_label);
2426
              gcc_assert (ok);
2427
            }
2428
 
2429
          /* Get table of labels to jump to, in order of case index.  */
2430
 
2431
          ncases = tree_low_cst (range, 0) + 1;
2432
          labelvec = XALLOCAVEC (rtx, ncases);
2433
          memset (labelvec, 0, ncases * sizeof (rtx));
2434
 
2435
          for (n = case_list; n; n = n->right)
2436
            {
2437
              /* Compute the low and high bounds relative to the minimum
2438
                 value since that should fit in a HOST_WIDE_INT while the
2439
                 actual values may not.  */
2440
              HOST_WIDE_INT i_low
2441
                = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2442
                                             n->low, minval), 1);
2443
              HOST_WIDE_INT i_high
2444
                = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2445
                                             n->high, minval), 1);
2446
              HOST_WIDE_INT i;
2447
 
2448
              for (i = i_low; i <= i_high; i ++)
2449
                labelvec[i]
2450
                  = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2451
            }
2452
 
2453
          /* Fill in the gaps with the default.  We may have gaps at
2454
             the beginning if we tried to avoid the minval subtraction,
2455
             so substitute some label even if the default label was
2456
             deemed unreachable.  */
2457
          if (!default_label)
2458
            default_label = fallback_label;
2459
          for (i = 0; i < ncases; i++)
2460
            if (labelvec[i] == 0)
2461
              labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2462
 
2463
          /* Output the table.  */
2464
          emit_label (table_label);
2465
 
2466
          if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2467
            emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2468
                                                   gen_rtx_LABEL_REF (Pmode, table_label),
2469
                                                   gen_rtvec_v (ncases, labelvec),
2470
                                                   const0_rtx, const0_rtx));
2471
          else
2472
            emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2473
                                              gen_rtvec_v (ncases, labelvec)));
2474
 
2475
          /* Record no drop-through after the table.  */
2476
          emit_barrier ();
2477
        }
2478
 
2479
      before_case = NEXT_INSN (before_case);
2480
      end = get_last_insn ();
2481
      reorder_insns (before_case, end, start);
2482
    }
2483
 
2484
  free_temp_slots ();
2485
  free_alloc_pool (case_node_pool);
2486
}
2487
 
2488
/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.  */
2489
 
2490
static void
2491
do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2492
                  int unsignedp)
2493
{
2494
  do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2495
                           NULL_RTX, NULL_RTX, label, -1);
2496
}
2497
 
2498
/* Not all case values are encountered equally.  This function
2499
   uses a heuristic to weight case labels, in cases where that
2500
   looks like a reasonable thing to do.
2501
 
2502
   Right now, all we try to guess is text, and we establish the
2503
   following weights:
2504
 
2505
        chars above space:      16
2506
        digits:                 16
2507
        default:                12
2508
        space, punct:           8
2509
        tab:                    4
2510
        newline:                2
2511
        other "\" chars:        1
2512
        remaining chars:        0
2513
 
2514
   If we find any cases in the switch that are not either -1 or in the range
2515
   of valid ASCII characters, or are control characters other than those
2516
   commonly used with "\", don't treat this switch scanning text.
2517
 
2518
   Return 1 if these nodes are suitable for cost estimation, otherwise
2519
   return 0.  */
2520
 
2521
static int
2522
estimate_case_costs (case_node_ptr node)
2523
{
2524
  tree min_ascii = integer_minus_one_node;
2525
  tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2526
  case_node_ptr n;
2527
  int i;
2528
 
2529
  /* If we haven't already made the cost table, make it now.  Note that the
2530
     lower bound of the table is -1, not zero.  */
2531
 
2532
  if (! cost_table_initialized)
2533
    {
2534
      cost_table_initialized = 1;
2535
 
2536
      for (i = 0; i < 128; i++)
2537
        {
2538
          if (ISALNUM (i))
2539
            COST_TABLE (i) = 16;
2540
          else if (ISPUNCT (i))
2541
            COST_TABLE (i) = 8;
2542
          else if (ISCNTRL (i))
2543
            COST_TABLE (i) = -1;
2544
        }
2545
 
2546
      COST_TABLE (' ') = 8;
2547
      COST_TABLE ('\t') = 4;
2548
      COST_TABLE ('\0') = 4;
2549
      COST_TABLE ('\n') = 2;
2550
      COST_TABLE ('\f') = 1;
2551
      COST_TABLE ('\v') = 1;
2552
      COST_TABLE ('\b') = 1;
2553
    }
2554
 
2555
  /* See if all the case expressions look like text.  It is text if the
2556
     constant is >= -1 and the highest constant is <= 127.  Do all comparisons
2557
     as signed arithmetic since we don't want to ever access cost_table with a
2558
     value less than -1.  Also check that none of the constants in a range
2559
     are strange control characters.  */
2560
 
2561
  for (n = node; n; n = n->right)
2562
    {
2563
      if (tree_int_cst_lt (n->low, min_ascii)
2564
          || tree_int_cst_lt (max_ascii, n->high))
2565
        return 0;
2566
 
2567
      for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2568
           i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2569
        if (COST_TABLE (i) < 0)
2570
          return 0;
2571
    }
2572
 
2573
  /* All interesting values are within the range of interesting
2574
     ASCII characters.  */
2575
  return 1;
2576
}
2577
 
2578
/* Take an ordered list of case nodes
2579
   and transform them into a near optimal binary tree,
2580
   on the assumption that any target code selection value is as
2581
   likely as any other.
2582
 
2583
   The transformation is performed by splitting the ordered
2584
   list into two equal sections plus a pivot.  The parts are
2585
   then attached to the pivot as left and right branches.  Each
2586
   branch is then transformed recursively.  */
2587
 
2588
static void
2589
balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2590
{
2591
  case_node_ptr np;
2592
 
2593
  np = *head;
2594
  if (np)
2595
    {
2596
      int cost = 0;
2597
      int i = 0;
2598
      int ranges = 0;
2599
      case_node_ptr *npp;
2600
      case_node_ptr left;
2601
 
2602
      /* Count the number of entries on branch.  Also count the ranges.  */
2603
 
2604
      while (np)
2605
        {
2606
          if (!tree_int_cst_equal (np->low, np->high))
2607
            {
2608
              ranges++;
2609
              if (use_cost_table)
2610
                cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2611
            }
2612
 
2613
          if (use_cost_table)
2614
            cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2615
 
2616
          i++;
2617
          np = np->right;
2618
        }
2619
 
2620
      if (i > 2)
2621
        {
2622
          /* Split this list if it is long enough for that to help.  */
2623
          npp = head;
2624
          left = *npp;
2625
          if (use_cost_table)
2626
            {
2627
              /* Find the place in the list that bisects the list's total cost,
2628
                 Here I gets half the total cost.  */
2629
              int n_moved = 0;
2630
              i = (cost + 1) / 2;
2631
              while (1)
2632
                {
2633
                  /* Skip nodes while their cost does not reach that amount.  */
2634
                  if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2635
                    i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2636
                  i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2637
                  if (i <= 0)
2638
                    break;
2639
                  npp = &(*npp)->right;
2640
                  n_moved += 1;
2641
                }
2642
              if (n_moved == 0)
2643
                {
2644
                  /* Leave this branch lopsided, but optimize left-hand
2645
                     side and fill in `parent' fields for right-hand side.  */
2646
                  np = *head;
2647
                  np->parent = parent;
2648
                  balance_case_nodes (&np->left, np);
2649
                  for (; np->right; np = np->right)
2650
                    np->right->parent = np;
2651
                  return;
2652
                }
2653
            }
2654
          /* If there are just three nodes, split at the middle one.  */
2655
          else if (i == 3)
2656
            npp = &(*npp)->right;
2657
          else
2658
            {
2659
              /* Find the place in the list that bisects the list's total cost,
2660
                 where ranges count as 2.
2661
                 Here I gets half the total cost.  */
2662
              i = (i + ranges + 1) / 2;
2663
              while (1)
2664
                {
2665
                  /* Skip nodes while their cost does not reach that amount.  */
2666
                  if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2667
                    i--;
2668
                  i--;
2669
                  if (i <= 0)
2670
                    break;
2671
                  npp = &(*npp)->right;
2672
                }
2673
            }
2674
          *head = np = *npp;
2675
          *npp = 0;
2676
          np->parent = parent;
2677
          np->left = left;
2678
 
2679
          /* Optimize each of the two split parts.  */
2680
          balance_case_nodes (&np->left, np);
2681
          balance_case_nodes (&np->right, np);
2682
        }
2683
      else
2684
        {
2685
          /* Else leave this branch as one level,
2686
             but fill in `parent' fields.  */
2687
          np = *head;
2688
          np->parent = parent;
2689
          for (; np->right; np = np->right)
2690
            np->right->parent = np;
2691
        }
2692
    }
2693
}
2694
 
2695
/* Search the parent sections of the case node tree
2696
   to see if a test for the lower bound of NODE would be redundant.
2697
   INDEX_TYPE is the type of the index expression.
2698
 
2699
   The instructions to generate the case decision tree are
2700
   output in the same order as nodes are processed so it is
2701
   known that if a parent node checks the range of the current
2702
   node minus one that the current node is bounded at its lower
2703
   span.  Thus the test would be redundant.  */
2704
 
2705
static int
2706
node_has_low_bound (case_node_ptr node, tree index_type)
2707
{
2708
  tree low_minus_one;
2709
  case_node_ptr pnode;
2710
 
2711
  /* If the lower bound of this node is the lowest value in the index type,
2712
     we need not test it.  */
2713
 
2714
  if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2715
    return 1;
2716
 
2717
  /* If this node has a left branch, the value at the left must be less
2718
     than that at this node, so it cannot be bounded at the bottom and
2719
     we need not bother testing any further.  */
2720
 
2721
  if (node->left)
2722
    return 0;
2723
 
2724
  low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2725
                               node->low,
2726
                               build_int_cst (TREE_TYPE (node->low), 1));
2727
 
2728
  /* If the subtraction above overflowed, we can't verify anything.
2729
     Otherwise, look for a parent that tests our value - 1.  */
2730
 
2731
  if (! tree_int_cst_lt (low_minus_one, node->low))
2732
    return 0;
2733
 
2734
  for (pnode = node->parent; pnode; pnode = pnode->parent)
2735
    if (tree_int_cst_equal (low_minus_one, pnode->high))
2736
      return 1;
2737
 
2738
  return 0;
2739
}
2740
 
2741
/* Search the parent sections of the case node tree
2742
   to see if a test for the upper bound of NODE would be redundant.
2743
   INDEX_TYPE is the type of the index expression.
2744
 
2745
   The instructions to generate the case decision tree are
2746
   output in the same order as nodes are processed so it is
2747
   known that if a parent node checks the range of the current
2748
   node plus one that the current node is bounded at its upper
2749
   span.  Thus the test would be redundant.  */
2750
 
2751
static int
2752
node_has_high_bound (case_node_ptr node, tree index_type)
2753
{
2754
  tree high_plus_one;
2755
  case_node_ptr pnode;
2756
 
2757
  /* If there is no upper bound, obviously no test is needed.  */
2758
 
2759
  if (TYPE_MAX_VALUE (index_type) == NULL)
2760
    return 1;
2761
 
2762
  /* If the upper bound of this node is the highest value in the type
2763
     of the index expression, we need not test against it.  */
2764
 
2765
  if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2766
    return 1;
2767
 
2768
  /* If this node has a right branch, the value at the right must be greater
2769
     than that at this node, so it cannot be bounded at the top and
2770
     we need not bother testing any further.  */
2771
 
2772
  if (node->right)
2773
    return 0;
2774
 
2775
  high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2776
                               node->high,
2777
                               build_int_cst (TREE_TYPE (node->high), 1));
2778
 
2779
  /* If the addition above overflowed, we can't verify anything.
2780
     Otherwise, look for a parent that tests our value + 1.  */
2781
 
2782
  if (! tree_int_cst_lt (node->high, high_plus_one))
2783
    return 0;
2784
 
2785
  for (pnode = node->parent; pnode; pnode = pnode->parent)
2786
    if (tree_int_cst_equal (high_plus_one, pnode->low))
2787
      return 1;
2788
 
2789
  return 0;
2790
}
2791
 
2792
/* Search the parent sections of the
2793
   case node tree to see if both tests for the upper and lower
2794
   bounds of NODE would be redundant.  */
2795
 
2796
static int
2797
node_is_bounded (case_node_ptr node, tree index_type)
2798
{
2799
  return (node_has_low_bound (node, index_type)
2800
          && node_has_high_bound (node, index_type));
2801
}
2802
 
2803
/* Emit step-by-step code to select a case for the value of INDEX.
2804
   The thus generated decision tree follows the form of the
2805
   case-node binary tree NODE, whose nodes represent test conditions.
2806
   INDEX_TYPE is the type of the index of the switch.
2807
 
2808
   Care is taken to prune redundant tests from the decision tree
2809
   by detecting any boundary conditions already checked by
2810
   emitted rtx.  (See node_has_high_bound, node_has_low_bound
2811
   and node_is_bounded, above.)
2812
 
2813
   Where the test conditions can be shown to be redundant we emit
2814
   an unconditional jump to the target code.  As a further
2815
   optimization, the subordinates of a tree node are examined to
2816
   check for bounded nodes.  In this case conditional and/or
2817
   unconditional jumps as a result of the boundary check for the
2818
   current node are arranged to target the subordinates associated
2819
   code for out of bound conditions on the current node.
2820
 
2821
   We can assume that when control reaches the code generated here,
2822
   the index value has already been compared with the parents
2823
   of this node, and determined to be on the same side of each parent
2824
   as this node is.  Thus, if this node tests for the value 51,
2825
   and a parent tested for 52, we don't need to consider
2826
   the possibility of a value greater than 51.  If another parent
2827
   tests for the value 50, then this node need not test anything.  */
2828
 
2829
static void
2830
emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2831
                 tree index_type)
2832
{
2833
  /* If INDEX has an unsigned type, we must make unsigned branches.  */
2834
  int unsignedp = TYPE_UNSIGNED (index_type);
2835
  enum machine_mode mode = GET_MODE (index);
2836
  enum machine_mode imode = TYPE_MODE (index_type);
2837
 
2838
  /* Handle indices detected as constant during RTL expansion.  */
2839
  if (mode == VOIDmode)
2840
    mode = imode;
2841
 
2842
  /* See if our parents have already tested everything for us.
2843
     If they have, emit an unconditional jump for this node.  */
2844
  if (node_is_bounded (node, index_type))
2845
    emit_jump (label_rtx (node->code_label));
2846
 
2847
  else if (tree_int_cst_equal (node->low, node->high))
2848
    {
2849
      /* Node is single valued.  First see if the index expression matches
2850
         this node and then check our children, if any.  */
2851
 
2852
      do_jump_if_equal (mode, index,
2853
                        convert_modes (mode, imode,
2854
                                       expand_normal (node->low),
2855
                                       unsignedp),
2856
                        label_rtx (node->code_label), unsignedp);
2857
 
2858
      if (node->right != 0 && node->left != 0)
2859
        {
2860
          /* This node has children on both sides.
2861
             Dispatch to one side or the other
2862
             by comparing the index value with this node's value.
2863
             If one subtree is bounded, check that one first,
2864
             so we can avoid real branches in the tree.  */
2865
 
2866
          if (node_is_bounded (node->right, index_type))
2867
            {
2868
              emit_cmp_and_jump_insns (index,
2869
                                       convert_modes
2870
                                       (mode, imode,
2871
                                        expand_normal (node->high),
2872
                                        unsignedp),
2873
                                       GT, NULL_RTX, mode, unsignedp,
2874
                                       label_rtx (node->right->code_label));
2875
              emit_case_nodes (index, node->left, default_label, index_type);
2876
            }
2877
 
2878
          else if (node_is_bounded (node->left, index_type))
2879
            {
2880
              emit_cmp_and_jump_insns (index,
2881
                                       convert_modes
2882
                                       (mode, imode,
2883
                                        expand_normal (node->high),
2884
                                        unsignedp),
2885
                                       LT, NULL_RTX, mode, unsignedp,
2886
                                       label_rtx (node->left->code_label));
2887
              emit_case_nodes (index, node->right, default_label, index_type);
2888
            }
2889
 
2890
          /* If both children are single-valued cases with no
2891
             children, finish up all the work.  This way, we can save
2892
             one ordered comparison.  */
2893
          else if (tree_int_cst_equal (node->right->low, node->right->high)
2894
                   && node->right->left == 0
2895
                   && node->right->right == 0
2896
                   && tree_int_cst_equal (node->left->low, node->left->high)
2897
                   && node->left->left == 0
2898
                   && node->left->right == 0)
2899
            {
2900
              /* Neither node is bounded.  First distinguish the two sides;
2901
                 then emit the code for one side at a time.  */
2902
 
2903
              /* See if the value matches what the right hand side
2904
                 wants.  */
2905
              do_jump_if_equal (mode, index,
2906
                                convert_modes (mode, imode,
2907
                                               expand_normal (node->right->low),
2908
                                               unsignedp),
2909
                                label_rtx (node->right->code_label),
2910
                                unsignedp);
2911
 
2912
              /* See if the value matches what the left hand side
2913
                 wants.  */
2914
              do_jump_if_equal (mode, index,
2915
                                convert_modes (mode, imode,
2916
                                               expand_normal (node->left->low),
2917
                                               unsignedp),
2918
                                label_rtx (node->left->code_label),
2919
                                unsignedp);
2920
            }
2921
 
2922
          else
2923
            {
2924
              /* Neither node is bounded.  First distinguish the two sides;
2925
                 then emit the code for one side at a time.  */
2926
 
2927
              tree test_label
2928
                = build_decl (CURR_INSN_LOCATION,
2929
                              LABEL_DECL, NULL_TREE, NULL_TREE);
2930
 
2931
              /* See if the value is on the right.  */
2932
              emit_cmp_and_jump_insns (index,
2933
                                       convert_modes
2934
                                       (mode, imode,
2935
                                        expand_normal (node->high),
2936
                                        unsignedp),
2937
                                       GT, NULL_RTX, mode, unsignedp,
2938
                                       label_rtx (test_label));
2939
 
2940
              /* Value must be on the left.
2941
                 Handle the left-hand subtree.  */
2942
              emit_case_nodes (index, node->left, default_label, index_type);
2943
              /* If left-hand subtree does nothing,
2944
                 go to default.  */
2945
              if (default_label)
2946
                emit_jump (default_label);
2947
 
2948
              /* Code branches here for the right-hand subtree.  */
2949
              expand_label (test_label);
2950
              emit_case_nodes (index, node->right, default_label, index_type);
2951
            }
2952
        }
2953
 
2954
      else if (node->right != 0 && node->left == 0)
2955
        {
2956
          /* Here we have a right child but no left so we issue a conditional
2957
             branch to default and process the right child.
2958
 
2959
             Omit the conditional branch to default if the right child
2960
             does not have any children and is single valued; it would
2961
             cost too much space to save so little time.  */
2962
 
2963
          if (node->right->right || node->right->left
2964
              || !tree_int_cst_equal (node->right->low, node->right->high))
2965
            {
2966
              if (!node_has_low_bound (node, index_type))
2967
                {
2968
                  emit_cmp_and_jump_insns (index,
2969
                                           convert_modes
2970
                                           (mode, imode,
2971
                                            expand_normal (node->high),
2972
                                            unsignedp),
2973
                                           LT, NULL_RTX, mode, unsignedp,
2974
                                           default_label);
2975
                }
2976
 
2977
              emit_case_nodes (index, node->right, default_label, index_type);
2978
            }
2979
          else
2980
            /* We cannot process node->right normally
2981
               since we haven't ruled out the numbers less than
2982
               this node's value.  So handle node->right explicitly.  */
2983
            do_jump_if_equal (mode, index,
2984
                              convert_modes
2985
                              (mode, imode,
2986
                               expand_normal (node->right->low),
2987
                               unsignedp),
2988
                              label_rtx (node->right->code_label), unsignedp);
2989
        }
2990
 
2991
      else if (node->right == 0 && node->left != 0)
2992
        {
2993
          /* Just one subtree, on the left.  */
2994
          if (node->left->left || node->left->right
2995
              || !tree_int_cst_equal (node->left->low, node->left->high))
2996
            {
2997
              if (!node_has_high_bound (node, index_type))
2998
                {
2999
                  emit_cmp_and_jump_insns (index,
3000
                                           convert_modes
3001
                                           (mode, imode,
3002
                                            expand_normal (node->high),
3003
                                            unsignedp),
3004
                                           GT, NULL_RTX, mode, unsignedp,
3005
                                           default_label);
3006
                }
3007
 
3008
              emit_case_nodes (index, node->left, default_label, index_type);
3009
            }
3010
          else
3011
            /* We cannot process node->left normally
3012
               since we haven't ruled out the numbers less than
3013
               this node's value.  So handle node->left explicitly.  */
3014
            do_jump_if_equal (mode, index,
3015
                              convert_modes
3016
                              (mode, imode,
3017
                               expand_normal (node->left->low),
3018
                               unsignedp),
3019
                              label_rtx (node->left->code_label), unsignedp);
3020
        }
3021
    }
3022
  else
3023
    {
3024
      /* Node is a range.  These cases are very similar to those for a single
3025
         value, except that we do not start by testing whether this node
3026
         is the one to branch to.  */
3027
 
3028
      if (node->right != 0 && node->left != 0)
3029
        {
3030
          /* Node has subtrees on both sides.
3031
             If the right-hand subtree is bounded,
3032
             test for it first, since we can go straight there.
3033
             Otherwise, we need to make a branch in the control structure,
3034
             then handle the two subtrees.  */
3035
          tree test_label = 0;
3036
 
3037
          if (node_is_bounded (node->right, index_type))
3038
            /* Right hand node is fully bounded so we can eliminate any
3039
               testing and branch directly to the target code.  */
3040
            emit_cmp_and_jump_insns (index,
3041
                                     convert_modes
3042
                                     (mode, imode,
3043
                                      expand_normal (node->high),
3044
                                      unsignedp),
3045
                                     GT, NULL_RTX, mode, unsignedp,
3046
                                     label_rtx (node->right->code_label));
3047
          else
3048
            {
3049
              /* Right hand node requires testing.
3050
                 Branch to a label where we will handle it later.  */
3051
 
3052
              test_label = build_decl (CURR_INSN_LOCATION,
3053
                                       LABEL_DECL, NULL_TREE, NULL_TREE);
3054
              emit_cmp_and_jump_insns (index,
3055
                                       convert_modes
3056
                                       (mode, imode,
3057
                                        expand_normal (node->high),
3058
                                        unsignedp),
3059
                                       GT, NULL_RTX, mode, unsignedp,
3060
                                       label_rtx (test_label));
3061
            }
3062
 
3063
          /* Value belongs to this node or to the left-hand subtree.  */
3064
 
3065
          emit_cmp_and_jump_insns (index,
3066
                                   convert_modes
3067
                                   (mode, imode,
3068
                                    expand_normal (node->low),
3069
                                    unsignedp),
3070
                                   GE, NULL_RTX, mode, unsignedp,
3071
                                   label_rtx (node->code_label));
3072
 
3073
          /* Handle the left-hand subtree.  */
3074
          emit_case_nodes (index, node->left, default_label, index_type);
3075
 
3076
          /* If right node had to be handled later, do that now.  */
3077
 
3078
          if (test_label)
3079
            {
3080
              /* If the left-hand subtree fell through,
3081
                 don't let it fall into the right-hand subtree.  */
3082
              if (default_label)
3083
                emit_jump (default_label);
3084
 
3085
              expand_label (test_label);
3086
              emit_case_nodes (index, node->right, default_label, index_type);
3087
            }
3088
        }
3089
 
3090
      else if (node->right != 0 && node->left == 0)
3091
        {
3092
          /* Deal with values to the left of this node,
3093
             if they are possible.  */
3094
          if (!node_has_low_bound (node, index_type))
3095
            {
3096
              emit_cmp_and_jump_insns (index,
3097
                                       convert_modes
3098
                                       (mode, imode,
3099
                                        expand_normal (node->low),
3100
                                        unsignedp),
3101
                                       LT, NULL_RTX, mode, unsignedp,
3102
                                       default_label);
3103
            }
3104
 
3105
          /* Value belongs to this node or to the right-hand subtree.  */
3106
 
3107
          emit_cmp_and_jump_insns (index,
3108
                                   convert_modes
3109
                                   (mode, imode,
3110
                                    expand_normal (node->high),
3111
                                    unsignedp),
3112
                                   LE, NULL_RTX, mode, unsignedp,
3113
                                   label_rtx (node->code_label));
3114
 
3115
          emit_case_nodes (index, node->right, default_label, index_type);
3116
        }
3117
 
3118
      else if (node->right == 0 && node->left != 0)
3119
        {
3120
          /* Deal with values to the right of this node,
3121
             if they are possible.  */
3122
          if (!node_has_high_bound (node, index_type))
3123
            {
3124
              emit_cmp_and_jump_insns (index,
3125
                                       convert_modes
3126
                                       (mode, imode,
3127
                                        expand_normal (node->high),
3128
                                        unsignedp),
3129
                                       GT, NULL_RTX, mode, unsignedp,
3130
                                       default_label);
3131
            }
3132
 
3133
          /* Value belongs to this node or to the left-hand subtree.  */
3134
 
3135
          emit_cmp_and_jump_insns (index,
3136
                                   convert_modes
3137
                                   (mode, imode,
3138
                                    expand_normal (node->low),
3139
                                    unsignedp),
3140
                                   GE, NULL_RTX, mode, unsignedp,
3141
                                   label_rtx (node->code_label));
3142
 
3143
          emit_case_nodes (index, node->left, default_label, index_type);
3144
        }
3145
 
3146
      else
3147
        {
3148
          /* Node has no children so we check low and high bounds to remove
3149
             redundant tests.  Only one of the bounds can exist,
3150
             since otherwise this node is bounded--a case tested already.  */
3151
          int high_bound = node_has_high_bound (node, index_type);
3152
          int low_bound = node_has_low_bound (node, index_type);
3153
 
3154
          if (!high_bound && low_bound)
3155
            {
3156
              emit_cmp_and_jump_insns (index,
3157
                                       convert_modes
3158
                                       (mode, imode,
3159
                                        expand_normal (node->high),
3160
                                        unsignedp),
3161
                                       GT, NULL_RTX, mode, unsignedp,
3162
                                       default_label);
3163
            }
3164
 
3165
          else if (!low_bound && high_bound)
3166
            {
3167
              emit_cmp_and_jump_insns (index,
3168
                                       convert_modes
3169
                                       (mode, imode,
3170
                                        expand_normal (node->low),
3171
                                        unsignedp),
3172
                                       LT, NULL_RTX, mode, unsignedp,
3173
                                       default_label);
3174
            }
3175
          else if (!low_bound && !high_bound)
3176
            {
3177
              /* Widen LOW and HIGH to the same width as INDEX.  */
3178
              tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3179
              tree low = build1 (CONVERT_EXPR, type, node->low);
3180
              tree high = build1 (CONVERT_EXPR, type, node->high);
3181
              rtx low_rtx, new_index, new_bound;
3182
 
3183
              /* Instead of doing two branches, emit one unsigned branch for
3184
                 (index-low) > (high-low).  */
3185
              low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3186
              new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3187
                                               NULL_RTX, unsignedp,
3188
                                               OPTAB_WIDEN);
3189
              new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3190
                                                    high, low),
3191
                                       NULL_RTX, mode, EXPAND_NORMAL);
3192
 
3193
              emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3194
                                       mode, 1, default_label);
3195
            }
3196
 
3197
          emit_jump (label_rtx (node->code_label));
3198
        }
3199
    }
3200
}

powered by: WebSVN 2.1.0

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