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