gcc/stmt.c

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