gcc/stmt.c

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