gcc/stmt.c

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