gcc/stmt.c

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