gcc/stmt.c

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