contrib/gcc/stmt.c

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