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