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