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