gcc/stmt.c

   1 /* Expands front end tree to back end RTL for GCC
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
   3    1998, 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file handles the generation of rtl code from tree structure
  23    above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
  24    It also creates the rtl expressions for parameters and auto variables
  25    and has full responsibility for allocating stack slots.
  26
  27    The functions whose names start with `expand_' are called by the
  28    parser to generate RTL instructions for various kinds of constructs.
  29
  30    Some control and binding constructs require calling several such
  31    functions at different times.  For example, a simple if-then
  32    is expanded by calling `expand_start_cond' (with the condition-expression
  33    as argument) before parsing the then-clause and calling `expand_end_cond'
  34    after parsing the then-clause.  */
  35
  36 #include "config.h"
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tm.h"
  40
  41 #include "rtl.h"
  42 #include "tree.h"
  43 #include "tm_p.h"
  44 #include "flags.h"
  45 #include "except.h"
  46 #include "function.h"
  47 #include "insn-config.h"
  48 #include "expr.h"
  49 #include "libfuncs.h"
  50 #include "hard-reg-set.h"
  51 #include "loop.h"
  52 #include "recog.h"
  53 #include "machmode.h"
  54 #include "toplev.h"
  55 #include "output.h"
  56 #include "ggc.h"
  57 #include "langhooks.h"
  58 #include "predict.h"
  59 #include "optabs.h"
  60 #include "target.h"
  61 #include "regs.h"
  62 \f
  63 /* Functions and data structures for expanding case statements.  */
  64
  65 /* Case label structure, used to hold info on labels within case
  66    statements.  We handle "range" labels; for a single-value label
  67    as in C, the high and low limits are the same.
  68
  69    An AVL tree of case nodes is initially created, and later transformed
  70    to a list linked via the RIGHT fields in the nodes.  Nodes with
  71    higher case values are later in the list.
  72
  73    Switch statements can be output in one of two forms.  A branch table
  74    is used if there are more than a few labels and the labels are dense
  75    within the range between the smallest and largest case value.  If a
  76    branch table is used, no further manipulations are done with the case
  77    node chain.
  78
  79    The alternative to the use of a branch table is to generate a series
  80    of compare and jump insns.  When that is done, we use the LEFT, RIGHT,
  81    and PARENT fields to hold a binary tree.  Initially the tree is
  82    totally unbalanced, with everything on the right.  We balance the tree
  83    with nodes on the left having lower case values than the parent
  84    and nodes on the right having higher values.  We then output the tree
  85    in order.  */
  86
  87 struct case_node GTY(())
  88 {
  89   struct case_node      *left;  /* Left son in binary tree */
  90   struct case_node      *right; /* Right son in binary tree; also node chain */
  91   struct case_node      *parent; /* Parent of node in binary tree */
  92   tree                  low;    /* Lowest index value for this label */
  93   tree                  high;   /* Highest index value for this label */
  94   tree                  code_label; /* Label to jump to when node matches */
  95   int                   balance;
  96 };
  97
  98 typedef struct case_node case_node;
  99 typedef struct case_node *case_node_ptr;
 100
 101 /* These are used by estimate_case_costs and balance_case_nodes.  */
 102
 103 /* This must be a signed type, and non-ANSI compilers lack signed char.  */
 104 static short cost_table_[129];
 105 static int use_cost_table;
 106 static int cost_table_initialized;
 107
 108 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
 109    is unsigned.  */
 110 #define COST_TABLE(I)  cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
 111 \f
 112 /* Stack of control and binding constructs we are currently inside.
 113
 114    These constructs begin when you call `expand_start_WHATEVER'
 115    and end when you call `expand_end_WHATEVER'.  This stack records
 116    info about how the construct began that tells the end-function
 117    what to do.  It also may provide information about the construct
 118    to alter the behavior of other constructs within the body.
 119    For example, they may affect the behavior of C `break' and `continue'.
 120
 121    Each construct gets one `struct nesting' object.
 122    All of these objects are chained through the `all' field.
 123    `nesting_stack' points to the first object (innermost construct).
 124    The position of an entry on `nesting_stack' is in its `depth' field.
 125
 126    Each type of construct has its own individual stack.
 127    For example, loops have `loop_stack'.  Each object points to the
 128    next object of the same type through the `next' field.
 129
 130    Some constructs are visible to `break' exit-statements and others
 131    are not.  Which constructs are visible depends on the language.
 132    Therefore, the data structure allows each construct to be visible
 133    or not, according to the args given when the construct is started.
 134    The construct is visible if the `exit_label' field is non-null.
 135    In that case, the value should be a CODE_LABEL rtx.  */
 136
 137 struct nesting GTY(())
 138 {
 139   struct nesting *all;
 140   struct nesting *next;
 141   int depth;
 142   rtx exit_label;
 143   enum nesting_desc {
 144     COND_NESTING,
 145     LOOP_NESTING,
 146     BLOCK_NESTING,
 147     CASE_NESTING
 148   } desc;
 149   union nesting_u
 150     {
 151       /* For conds (if-then and if-then-else statements).  */
 152       struct nesting_cond
 153         {
 154           /* Label for the end of the if construct.
 155              There is none if EXITFLAG was not set
 156              and no `else' has been seen yet.  */
 157           rtx endif_label;
 158           /* Label for the end of this alternative.
 159              This may be the end of the if or the next else/elseif.  */
 160           rtx next_label;
 161         } GTY ((tag ("COND_NESTING"))) cond;
 162       /* For loops.  */
 163       struct nesting_loop
 164         {
 165           /* Label at the top of the loop; place to loop back to.  */
 166           rtx start_label;
 167           /* Label at the end of the whole construct.  */
 168           rtx end_label;
 169           /* Label for `continue' statement to jump to;
 170              this is in front of the stepper of the loop.  */
 171           rtx continue_label;
 172         } GTY ((tag ("LOOP_NESTING"))) loop;
 173       /* For variable binding contours.  */
 174       struct nesting_block
 175         {
 176           /* Sequence number of this binding contour within the function,
 177              in order of entry.  */
 178           int block_start_count;
 179           /* Nonzero => value to restore stack to on exit.  */
 180           rtx stack_level;
 181           /* The NOTE that starts this contour.
 182              Used by expand_goto to check whether the destination
 183              is within each contour or not.  */
 184           rtx first_insn;
 185           /* Innermost containing binding contour that has a stack level.  */
 186           struct nesting *innermost_stack_block;
 187           /* List of cleanups to be run on exit from this contour.
 188              This is a list of expressions to be evaluated.
 189              The TREE_PURPOSE of each link is the ..._DECL node
 190              which the cleanup pertains to.  */
 191           tree cleanups;
 192           /* List of cleanup-lists of blocks containing this block,
 193              as they were at the locus where this block appears.
 194              There is an element for each containing block,
 195              ordered innermost containing block first.
 196              The tail of this list can be 0,
 197              if all remaining elements would be empty lists.
 198              The element's TREE_VALUE is the cleanup-list of that block,
 199              which may be null.  */
 200           tree outer_cleanups;
 201           /* Chain of labels defined inside this binding contour.
 202              For contours that have stack levels or cleanups.  */
 203           struct label_chain *label_chain;
 204           /* Nonzero if this is associated with an EH region.  */
 205           int exception_region;
 206           /* The saved target_temp_slot_level from our outer block.
 207              We may reset target_temp_slot_level to be the level of
 208              this block, if that is done, target_temp_slot_level
 209              reverts to the saved target_temp_slot_level at the very
 210              end of the block.  */
 211           int block_target_temp_slot_level;
 212           /* True if we are currently emitting insns in an area of
 213              output code that is controlled by a conditional
 214              expression.  This is used by the cleanup handling code to
 215              generate conditional cleanup actions.  */
 216           int conditional_code;
 217           /* A place to move the start of the exception region for any
 218              of the conditional cleanups, must be at the end or after
 219              the start of the last unconditional cleanup, and before any
 220              conditional branch points.  */
 221           rtx last_unconditional_cleanup;
 222         } GTY ((tag ("BLOCK_NESTING"))) block;
 223       /* For switch (C) or case (Pascal) statements.  */
 224       struct nesting_case
 225         {
 226           /* The insn after which the case dispatch should finally
 227              be emitted.  Zero for a dummy.  */
 228           rtx start;
 229           /* A list of case labels; it is first built as an AVL tree.
 230              During expand_end_case, this is converted to a list, and may be
 231              rearranged into a nearly balanced binary tree.  */
 232           struct case_node *case_list;
 233           /* Label to jump to if no case matches.  */
 234           tree default_label;
 235           /* The expression to be dispatched on.  */
 236           tree index_expr;
 237           /* Type that INDEX_EXPR should be converted to.  */
 238           tree nominal_type;
 239           /* Name of this kind of statement, for warnings.  */
 240           const char *printname;
 241           /* Used to save no_line_numbers till we see the first case label.
 242              We set this to -1 when we see the first case label in this
 243              case statement.  */
 244           int line_number_status;
 245         } GTY ((tag ("CASE_NESTING"))) case_stmt;
 246     } GTY ((desc ("%1.desc"))) data;
 247 };
 248
 249 /* Allocate and return a new `struct nesting'.  */
 250
 251 #define ALLOC_NESTING() ggc_alloc (sizeof (struct nesting))
 252
 253 /* Pop the nesting stack element by element until we pop off
 254    the element which is at the top of STACK.
 255    Update all the other stacks, popping off elements from them
 256    as we pop them from nesting_stack.  */
 257
 258 #define POPSTACK(STACK)                                 \
 259 do { struct nesting *target = STACK;                    \
 260      struct nesting *this;                              \
 261      do { this = nesting_stack;                         \
 262           if (loop_stack == this)                       \
 263             loop_stack = loop_stack->next;              \
 264           if (cond_stack == this)                       \
 265             cond_stack = cond_stack->next;              \
 266           if (block_stack == this)                      \
 267             block_stack = block_stack->next;            \
 268           if (stack_block_stack == this)                \
 269             stack_block_stack = stack_block_stack->next; \
 270           if (case_stack == this)                       \
 271             case_stack = case_stack->next;              \
 272           nesting_depth = nesting_stack->depth - 1;     \
 273           nesting_stack = this->all; }                  \
 274      while (this != target); } while (0)
 275 \f
 276 /* In some cases it is impossible to generate code for a forward goto
 277    until the label definition is seen.  This happens when it may be necessary
 278    for the goto to reset the stack pointer: we don't yet know how to do that.
 279    So expand_goto puts an entry on this fixup list.
 280    Each time a binding contour that resets the stack is exited,
 281    we check each fixup.
 282    If the target label has now been defined, we can insert the proper code.  */
 283
 284 struct goto_fixup GTY(())
 285 {
 286   /* Points to following fixup.  */
 287   struct goto_fixup *next;
 288   /* Points to the insn before the jump insn.
 289      If more code must be inserted, it goes after this insn.  */
 290   rtx before_jump;
 291   /* The LABEL_DECL that this jump is jumping to, or 0
 292      for break, continue or return.  */
 293   tree target;
 294   /* The BLOCK for the place where this goto was found.  */
 295   tree context;
 296   /* The CODE_LABEL rtx that this is jumping to.  */
 297   rtx target_rtl;
 298   /* Number of binding contours started in current function
 299      before the label reference.  */
 300   int block_start_count;
 301   /* The outermost stack level that should be restored for this jump.
 302      Each time a binding contour that resets the stack is exited,
 303      if the target label is *not* yet defined, this slot is updated.  */
 304   rtx stack_level;
 305   /* List of lists of cleanup expressions to be run by this goto.
 306      There is one element for each block that this goto is within.
 307      The tail of this list can be 0,
 308      if all remaining elements would be empty.
 309      The TREE_VALUE contains the cleanup list of that block as of the
 310      time this goto was seen.
 311      The TREE_ADDRESSABLE flag is 1 for a block that has been exited.  */
 312   tree cleanup_list_list;
 313 };
 314
 315 /* Within any binding contour that must restore a stack level,
 316    all labels are recorded with a chain of these structures.  */
 317
 318 struct label_chain GTY(())
 319 {
 320   /* Points to following fixup.  */
 321   struct label_chain *next;
 322   tree label;
 323 };
 324
 325 struct stmt_status GTY(())
 326 {
 327   /* Chain of all pending binding contours.  */
 328   struct nesting * x_block_stack;
 329
 330   /* If any new stacks are added here, add them to POPSTACKS too.  */
 331
 332   /* Chain of all pending binding contours that restore stack levels
 333      or have cleanups.  */
 334   struct nesting * x_stack_block_stack;
 335
 336   /* Chain of all pending conditional statements.  */
 337   struct nesting * x_cond_stack;
 338
 339   /* Chain of all pending loops.  */
 340   struct nesting * x_loop_stack;
 341
 342   /* Chain of all pending case or switch statements.  */
 343   struct nesting * x_case_stack;
 344
 345   /* Separate chain including all of the above,
 346      chained through the `all' field.  */
 347   struct nesting * x_nesting_stack;
 348
 349   /* Number of entries on nesting_stack now.  */
 350   int x_nesting_depth;
 351
 352   /* Number of binding contours started so far in this function.  */
 353   int x_block_start_count;
 354
 355   /* Each time we expand an expression-statement,
 356      record the expr's type and its RTL value here.  */
 357   tree x_last_expr_type;
 358   rtx x_last_expr_value;
 359   rtx x_last_expr_alt_rtl;
 360
 361   /* Nonzero if within a ({...}) grouping, in which case we must
 362      always compute a value for each expr-stmt in case it is the last one.  */
 363   int x_expr_stmts_for_value;
 364
 365   /* Location of last line-number note, whether we actually
 366      emitted it or not.  */
 367   location_t x_emit_locus;
 368
 369   struct goto_fixup *x_goto_fixup_chain;
 370 };
 371
 372 #define block_stack (cfun->stmt->x_block_stack)
 373 #define stack_block_stack (cfun->stmt->x_stack_block_stack)
 374 #define cond_stack (cfun->stmt->x_cond_stack)
 375 #define loop_stack (cfun->stmt->x_loop_stack)
 376 #define case_stack (cfun->stmt->x_case_stack)
 377 #define nesting_stack (cfun->stmt->x_nesting_stack)
 378 #define nesting_depth (cfun->stmt->x_nesting_depth)
 379 #define current_block_start_count (cfun->stmt->x_block_start_count)
 380 #define last_expr_type (cfun->stmt->x_last_expr_type)
 381 #define last_expr_value (cfun->stmt->x_last_expr_value)
 382 #define last_expr_alt_rtl (cfun->stmt->x_last_expr_alt_rtl)
 383 #define expr_stmts_for_value (cfun->stmt->x_expr_stmts_for_value)
 384 #define emit_locus (cfun->stmt->x_emit_locus)
 385 #define goto_fixup_chain (cfun->stmt->x_goto_fixup_chain)
 386
 387 /* Nonzero if we are using EH to handle cleanups.  */
 388 static int using_eh_for_cleanups_p = 0;
 389
 390 static int n_occurrences (int, const char *);
 391 static bool decl_conflicts_with_clobbers_p (tree, const HARD_REG_SET);
 392 static void expand_goto_internal (tree, rtx, rtx);
 393 static int expand_fixup (tree, rtx, rtx);
 394 static rtx expand_nl_handler_label (rtx, rtx);
 395 static void expand_nl_goto_receiver (void);
 396 static void expand_nl_goto_receivers (struct nesting *);
 397 static void fixup_gotos (struct nesting *, rtx, tree, rtx, int);
 398 static bool check_operand_nalternatives (tree, tree);
 399 static bool check_unique_operand_names (tree, tree);
 400 static char *resolve_operand_name_1 (char *, tree, tree);
 401 static void expand_null_return_1 (rtx);
 402 static enum br_predictor return_prediction (rtx);
 403 static rtx shift_return_value (rtx);
 404 static void expand_value_return (rtx);
 405 static int tail_recursion_args (tree, tree);
 406 static void expand_cleanups (tree, int, int);
 407 static void check_seenlabel (void);
 408 static void do_jump_if_equal (rtx, rtx, rtx, int);
 409 static int estimate_case_costs (case_node_ptr);
 410 static bool same_case_target_p (rtx, rtx);
 411 static void strip_default_case_nodes (case_node_ptr *, rtx);
 412 static bool lshift_cheap_p (void);
 413 static int case_bit_test_cmp (const void *, const void *);
 414 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
 415 static void group_case_nodes (case_node_ptr);
 416 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
 417 static int node_has_low_bound (case_node_ptr, tree);
 418 static int node_has_high_bound (case_node_ptr, tree);
 419 static int node_is_bounded (case_node_ptr, tree);
 420 static void emit_jump_if_reachable (rtx);
 421 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
 422 static struct case_node *case_tree2list (case_node *, case_node *);
 423 \f
 424 void
 425 using_eh_for_cleanups (void)
 426 {
 427   using_eh_for_cleanups_p = 1;
 428 }
 429
 430 void
 431 init_stmt_for_function (void)
 432 {
 433   cfun->stmt = ggc_alloc_cleared (sizeof (struct stmt_status));
 434 }
 435 \f
 436 /* Record the current file and line.  Called from emit_line_note.  */
 437
 438 void
 439 set_file_and_line_for_stmt (location_t location)
 440 {
 441   /* If we're outputting an inline function, and we add a line note,
 442      there may be no CFUN->STMT information.  So, there's no need to
 443      update it.  */
 444   if (cfun->stmt)
 445     emit_locus = location;
 446 }
 447
 448 /* Emit a no-op instruction.  */
 449
 450 void
 451 emit_nop (void)
 452 {
 453   rtx last_insn;
 454
 455   last_insn = get_last_insn ();
 456   if (!optimize
 457       && (GET_CODE (last_insn) == CODE_LABEL
 458           || (GET_CODE (last_insn) == NOTE
 459               && prev_real_insn (last_insn) == 0)))
 460     emit_insn (gen_nop ());
 461 }
 462 \f
 463 /* Return the rtx-label that corresponds to a LABEL_DECL,
 464    creating it if necessary.  */
 465
 466 rtx
 467 label_rtx (tree label)
 468 {
 469   if (TREE_CODE (label) != LABEL_DECL)
 470     abort ();
 471
 472   if (!DECL_RTL_SET_P (label))
 473     SET_DECL_RTL (label, gen_label_rtx ());
 474
 475   return DECL_RTL (label);
 476 }
 477
 478 /* As above, but also put it on the forced-reference list of the
 479    function that contains it.  */
 480 rtx
 481 force_label_rtx (tree label)
 482 {
 483   rtx ref = label_rtx (label);
 484   tree function = decl_function_context (label);
 485   struct function *p;
 486
 487   if (!function)
 488     abort ();
 489
 490   if (function != current_function_decl
 491       && function != inline_function_decl)
 492     p = find_function_data (function);
 493   else
 494     p = cfun;
 495
 496   p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref,
 497                                                 p->expr->x_forced_labels);
 498   return ref;
 499 }
 500
 501 /* Add an unconditional jump to LABEL as the next sequential instruction.  */
 502
 503 void
 504 emit_jump (rtx label)
 505 {
 506   do_pending_stack_adjust ();
 507   emit_jump_insn (gen_jump (label));
 508   emit_barrier ();
 509 }
 510
 511 /* Emit code to jump to the address
 512    specified by the pointer expression EXP.  */
 513
 514 void
 515 expand_computed_goto (tree exp)
 516 {
 517   rtx x = expand_expr (exp, NULL_RTX, VOIDmode, 0);
 518
 519   x = convert_memory_address (Pmode, x);
 520
 521   emit_queue ();
 522
 523   if (! cfun->computed_goto_common_label)
 524     {
 525       cfun->computed_goto_common_reg = copy_to_mode_reg (Pmode, x);
 526       cfun->computed_goto_common_label = gen_label_rtx ();
 527
 528       do_pending_stack_adjust ();
 529       emit_label (cfun->computed_goto_common_label);
 530       emit_indirect_jump (cfun->computed_goto_common_reg);
 531
 532       current_function_has_computed_jump = 1;
 533     }
 534   else
 535     {
 536       emit_move_insn (cfun->computed_goto_common_reg, x);
 537       emit_jump (cfun->computed_goto_common_label);
 538     }
 539 }
 540 \f
 541 /* Handle goto statements and the labels that they can go to.  */
 542
 543 /* Specify the location in the RTL code of a label LABEL,
 544    which is a LABEL_DECL tree node.
 545
 546    This is used for the kind of label that the user can jump to with a
 547    goto statement, and for alternatives of a switch or case statement.
 548    RTL labels generated for loops and conditionals don't go through here;
 549    they are generated directly at the RTL level, by other functions below.
 550
 551    Note that this has nothing to do with defining label *names*.
 552    Languages vary in how they do that and what that even means.  */
 553
 554 void
 555 expand_label (tree label)
 556 {
 557   struct label_chain *p;
 558
 559   do_pending_stack_adjust ();
 560   emit_label (label_rtx (label));
 561   if (DECL_NAME (label))
 562     LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
 563
 564   if (stack_block_stack != 0)
 565     {
 566       p = ggc_alloc (sizeof (struct label_chain));
 567       p->next = stack_block_stack->data.block.label_chain;
 568       stack_block_stack->data.block.label_chain = p;
 569       p->label = label;
 570     }
 571 }
 572
 573 /* Declare that LABEL (a LABEL_DECL) may be used for nonlocal gotos
 574    from nested functions.  */
 575
 576 void
 577 declare_nonlocal_label (tree label)
 578 {
 579   rtx slot = assign_stack_local (Pmode, GET_MODE_SIZE (Pmode), 0);
 580
 581   nonlocal_labels = tree_cons (NULL_TREE, label, nonlocal_labels);
 582   LABEL_PRESERVE_P (label_rtx (label)) = 1;
 583   if (nonlocal_goto_handler_slots == 0)
 584     {
 585       emit_stack_save (SAVE_NONLOCAL,
 586                        &nonlocal_goto_stack_level,
 587                        PREV_INSN (tail_recursion_reentry));
 588     }
 589   nonlocal_goto_handler_slots
 590     = gen_rtx_EXPR_LIST (VOIDmode, slot, nonlocal_goto_handler_slots);
 591 }
 592
 593 /* Generate RTL code for a `goto' statement with target label LABEL.
 594    LABEL should be a LABEL_DECL tree node that was or will later be
 595    defined with `expand_label'.  */
 596
 597 void
 598 expand_goto (tree label)
 599 {
 600   tree context;
 601
 602   /* Check for a nonlocal goto to a containing function.  */
 603   context = decl_function_context (label);
 604   if (context != 0 && context != current_function_decl)
 605     {
 606       struct function *p = find_function_data (context);
 607       rtx label_ref = gen_rtx_LABEL_REF (Pmode, label_rtx (label));
 608       rtx handler_slot, static_chain, save_area, insn;
 609       tree link;
 610
 611       /* Find the corresponding handler slot for this label.  */
 612       handler_slot = p->x_nonlocal_goto_handler_slots;
 613       for (link = p->x_nonlocal_labels; TREE_VALUE (link) != label;
 614            link = TREE_CHAIN (link))
 615         handler_slot = XEXP (handler_slot, 1);
 616       handler_slot = XEXP (handler_slot, 0);
 617
 618       p->has_nonlocal_label = 1;
 619       current_function_has_nonlocal_goto = 1;
 620       LABEL_REF_NONLOCAL_P (label_ref) = 1;
 621
 622       /* Copy the rtl for the slots so that they won't be shared in
 623          case the virtual stack vars register gets instantiated differently
 624          in the parent than in the child.  */
 625
 626       static_chain = copy_to_reg (lookup_static_chain (label));
 627
 628       /* Get addr of containing function's current nonlocal goto handler,
 629          which will do any cleanups and then jump to the label.  */
 630       handler_slot = copy_to_reg (replace_rtx (copy_rtx (handler_slot),
 631                                                virtual_stack_vars_rtx,
 632                                                static_chain));
 633
 634       /* Get addr of containing function's nonlocal save area.  */
 635       save_area = p->x_nonlocal_goto_stack_level;
 636       if (save_area)
 637         save_area = replace_rtx (copy_rtx (save_area),
 638                                  virtual_stack_vars_rtx, static_chain);
 639
 640 #if HAVE_nonlocal_goto
 641       if (HAVE_nonlocal_goto)
 642         emit_insn (gen_nonlocal_goto (static_chain, handler_slot,
 643                                       save_area, label_ref));
 644       else
 645 #endif
 646         {
 647           emit_insn (gen_rtx_CLOBBER (VOIDmode,
 648                                       gen_rtx_MEM (BLKmode,
 649                                                    gen_rtx_SCRATCH (VOIDmode))));
 650           emit_insn (gen_rtx_CLOBBER (VOIDmode,
 651                                       gen_rtx_MEM (BLKmode,
 652                                                    hard_frame_pointer_rtx)));
 653
 654           /* Restore frame pointer for containing function.
 655              This sets the actual hard register used for the frame pointer
 656              to the location of the function's incoming static chain info.
 657              The non-local goto handler will then adjust it to contain the
 658              proper value and reload the argument pointer, if needed.  */
 659           emit_move_insn (hard_frame_pointer_rtx, static_chain);
 660           emit_stack_restore (SAVE_NONLOCAL, save_area, NULL_RTX);
 661
 662           /* USE of hard_frame_pointer_rtx added for consistency;
 663              not clear if really needed.  */
 664           emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
 665           emit_insn (gen_rtx_USE (VOIDmode, stack_pointer_rtx));
 666           emit_indirect_jump (handler_slot);
 667         }
 668
 669       /* Search backwards to the jump insn and mark it as a
 670          non-local goto.  */
 671       for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 672         {
 673           if (GET_CODE (insn) == JUMP_INSN)
 674             {
 675               REG_NOTES (insn) = alloc_EXPR_LIST (REG_NON_LOCAL_GOTO,
 676                                                   const0_rtx, REG_NOTES (insn));
 677               break;
 678             }
 679           else if (GET_CODE (insn) == CALL_INSN)
 680               break;
 681         }
 682     }
 683   else
 684     expand_goto_internal (label, label_rtx (label), NULL_RTX);
 685 }
 686
 687 /* Generate RTL code for a `goto' statement with target label BODY.
 688    LABEL should be a LABEL_REF.
 689    LAST_INSN, if non-0, is the rtx we should consider as the last
 690    insn emitted (for the purposes of cleaning up a return).  */
 691
 692 static void
 693 expand_goto_internal (tree body, rtx label, rtx last_insn)
 694 {
 695   struct nesting *block;
 696   rtx stack_level = 0;
 697
 698   if (GET_CODE (label) != CODE_LABEL)
 699     abort ();
 700
 701   /* If label has already been defined, we can tell now
 702      whether and how we must alter the stack level.  */
 703
 704   if (PREV_INSN (label) != 0)
 705     {
 706       /* Find the innermost pending block that contains the label.
 707          (Check containment by comparing insn-uids.)
 708          Then restore the outermost stack level within that block,
 709          and do cleanups of all blocks contained in it.  */
 710       for (block = block_stack; block; block = block->next)
 711         {
 712           if (INSN_UID (block->data.block.first_insn) < INSN_UID (label))
 713             break;
 714           if (block->data.block.stack_level != 0)
 715             stack_level = block->data.block.stack_level;
 716           /* Execute the cleanups for blocks we are exiting.  */
 717           if (block->data.block.cleanups != 0)
 718             {
 719               expand_cleanups (block->data.block.cleanups, 1, 1);
 720               do_pending_stack_adjust ();
 721             }
 722         }
 723
 724       if (stack_level)
 725         {
 726           /* Ensure stack adjust isn't done by emit_jump, as this
 727              would clobber the stack pointer.  This one should be
 728              deleted as dead by flow.  */
 729           clear_pending_stack_adjust ();
 730           do_pending_stack_adjust ();
 731
 732           /* Don't do this adjust if it's to the end label and this function
 733              is to return with a depressed stack pointer.  */
 734           if (label == return_label
 735               && (((TREE_CODE (TREE_TYPE (current_function_decl))
 736                    == FUNCTION_TYPE)
 737                    && (TYPE_RETURNS_STACK_DEPRESSED
 738                        (TREE_TYPE (current_function_decl))))))
 739             ;
 740           else
 741             emit_stack_restore (SAVE_BLOCK, stack_level, NULL_RTX);
 742         }
 743
 744       if (body != 0 && DECL_TOO_LATE (body))
 745         error ("jump to `%s' invalidly jumps into binding contour",
 746                IDENTIFIER_POINTER (DECL_NAME (body)));
 747     }
 748   /* Label not yet defined: may need to put this goto
 749      on the fixup list.  */
 750   else if (! expand_fixup (body, label, last_insn))
 751     {
 752       /* No fixup needed.  Record that the label is the target
 753          of at least one goto that has no fixup.  */
 754       if (body != 0)
 755         TREE_ADDRESSABLE (body) = 1;
 756     }
 757
 758   emit_jump (label);
 759 }
 760 \f
 761 /* Generate if necessary a fixup for a goto
 762    whose target label in tree structure (if any) is TREE_LABEL
 763    and whose target in rtl is RTL_LABEL.
 764
 765    If LAST_INSN is nonzero, we pretend that the jump appears
 766    after insn LAST_INSN instead of at the current point in the insn stream.
 767
 768    The fixup will be used later to insert insns just before the goto.
 769    Those insns will restore the stack level as appropriate for the
 770    target label, and will (in the case of C++) also invoke any object
 771    destructors which have to be invoked when we exit the scopes which
 772    are exited by the goto.
 773
 774    Value is nonzero if a fixup is made.  */
 775
 776 static int
 777 expand_fixup (tree tree_label, rtx rtl_label, rtx last_insn)
 778 {
 779   struct nesting *block, *end_block;
 780
 781   /* See if we can recognize which block the label will be output in.
 782      This is possible in some very common cases.
 783      If we succeed, set END_BLOCK to that block.
 784      Otherwise, set it to 0.  */
 785
 786   if (cond_stack
 787       && (rtl_label == cond_stack->data.cond.endif_label
 788           || rtl_label == cond_stack->data.cond.next_label))
 789     end_block = cond_stack;
 790   /* If we are in a loop, recognize certain labels which
 791      are likely targets.  This reduces the number of fixups
 792      we need to create.  */
 793   else if (loop_stack
 794       && (rtl_label == loop_stack->data.loop.start_label
 795           || rtl_label == loop_stack->data.loop.end_label
 796           || rtl_label == loop_stack->data.loop.continue_label))
 797     end_block = loop_stack;
 798   else
 799     end_block = 0;
 800
 801   /* Now set END_BLOCK to the binding level to which we will return.  */
 802
 803   if (end_block)
 804     {
 805       struct nesting *next_block = end_block->all;
 806       block = block_stack;
 807
 808       /* First see if the END_BLOCK is inside the innermost binding level.
 809          If so, then no cleanups or stack levels are relevant.  */
 810       while (next_block && next_block != block)
 811         next_block = next_block->all;
 812
 813       if (next_block)
 814         return 0;
 815
 816       /* Otherwise, set END_BLOCK to the innermost binding level
 817          which is outside the relevant control-structure nesting.  */
 818       next_block = block_stack->next;
 819       for (block = block_stack; block != end_block; block = block->all)
 820         if (block == next_block)
 821           next_block = next_block->next;
 822       end_block = next_block;
 823     }
 824
 825   /* Does any containing block have a stack level or cleanups?
 826      If not, no fixup is needed, and that is the normal case
 827      (the only case, for standard C).  */
 828   for (block = block_stack; block != end_block; block = block->next)
 829     if (block->data.block.stack_level != 0
 830         || block->data.block.cleanups != 0)
 831       break;
 832
 833   if (block != end_block)
 834     {
 835       /* Ok, a fixup is needed.  Add a fixup to the list of such.  */
 836       struct goto_fixup *fixup = ggc_alloc (sizeof (struct goto_fixup));
 837       /* In case an old stack level is restored, make sure that comes
 838          after any pending stack adjust.  */
 839       /* ?? If the fixup isn't to come at the present position,
 840          doing the stack adjust here isn't useful.  Doing it with our
 841          settings at that location isn't useful either.  Let's hope
 842          someone does it!  */
 843       if (last_insn == 0)
 844         do_pending_stack_adjust ();
 845       fixup->target = tree_label;
 846       fixup->target_rtl = rtl_label;
 847
 848       /* Create a BLOCK node and a corresponding matched set of
 849          NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes at
 850          this point.  The notes will encapsulate any and all fixup
 851          code which we might later insert at this point in the insn
 852          stream.  Also, the BLOCK node will be the parent (i.e. the
 853          `SUPERBLOCK') of any other BLOCK nodes which we might create
 854          later on when we are expanding the fixup code.
 855
 856          Note that optimization passes (including expand_end_loop)
 857          might move the *_BLOCK notes away, so we use a NOTE_INSN_DELETED
 858          as a placeholder.  */
 859
 860       {
 861         rtx original_before_jump
 862           = last_insn ? last_insn : get_last_insn ();
 863         rtx start;
 864         rtx end;
 865         tree block;
 866
 867         block = make_node (BLOCK);
 868         TREE_USED (block) = 1;
 869
 870         if (!cfun->x_whole_function_mode_p)
 871           lang_hooks.decls.insert_block (block);
 872         else
 873           {
 874             BLOCK_CHAIN (block)
 875               = BLOCK_CHAIN (DECL_INITIAL (current_function_decl));
 876             BLOCK_CHAIN (DECL_INITIAL (current_function_decl))
 877               = block;
 878           }
 879
 880         start_sequence ();
 881         start = emit_note (NOTE_INSN_BLOCK_BEG);
 882         if (cfun->x_whole_function_mode_p)
 883           NOTE_BLOCK (start) = block;
 884         fixup->before_jump = emit_note (NOTE_INSN_DELETED);
 885         end = emit_note (NOTE_INSN_BLOCK_END);
 886         if (cfun->x_whole_function_mode_p)
 887           NOTE_BLOCK (end) = block;
 888         fixup->context = block;
 889         end_sequence ();
 890         emit_insn_after (start, original_before_jump);
 891       }
 892
 893       fixup->block_start_count = current_block_start_count;
 894       fixup->stack_level = 0;
 895       fixup->cleanup_list_list
 896         = ((block->data.block.outer_cleanups
 897             || block->data.block.cleanups)
 898            ? tree_cons (NULL_TREE, block->data.block.cleanups,
 899                         block->data.block.outer_cleanups)
 900            : 0);
 901       fixup->next = goto_fixup_chain;
 902       goto_fixup_chain = fixup;
 903     }
 904
 905   return block != 0;
 906 }
 907 \f
 908 /* Expand any needed fixups in the outputmost binding level of the
 909    function.  FIRST_INSN is the first insn in the function.  */
 910
 911 void
 912 expand_fixups (rtx first_insn)
 913 {
 914   fixup_gotos (NULL, NULL_RTX, NULL_TREE, first_insn, 0);
 915 }
 916
 917 /* When exiting a binding contour, process all pending gotos requiring fixups.
 918    THISBLOCK is the structure that describes the block being exited.
 919    STACK_LEVEL is the rtx for the stack level to restore exiting this contour.
 920    CLEANUP_LIST is a list of expressions to evaluate on exiting this contour.
 921    FIRST_INSN is the insn that began this contour.
 922
 923    Gotos that jump out of this contour must restore the
 924    stack level and do the cleanups before actually jumping.
 925
 926    DONT_JUMP_IN positive means report error if there is a jump into this
 927    contour from before the beginning of the contour.  This is also done if
 928    STACK_LEVEL is nonzero unless DONT_JUMP_IN is negative.  */
 929
 930 static void
 931 fixup_gotos (struct nesting *thisblock, rtx stack_level,
 932              tree cleanup_list, rtx first_insn, int dont_jump_in)
 933 {
 934   struct goto_fixup *f, *prev;
 935
 936   /* F is the fixup we are considering; PREV is the previous one.  */
 937   /* We run this loop in two passes so that cleanups of exited blocks
 938      are run first, and blocks that are exited are marked so
 939      afterwards.  */
 940
 941   for (prev = 0, f = goto_fixup_chain; f; prev = f, f = f->next)
 942     {
 943       /* Test for a fixup that is inactive because it is already handled.  */
 944       if (f->before_jump == 0)
 945         {
 946           /* Delete inactive fixup from the chain, if that is easy to do.  */
 947           if (prev != 0)
 948             prev->next = f->next;
 949         }
 950       /* Has this fixup's target label been defined?
 951          If so, we can finalize it.  */
 952       else if (PREV_INSN (f->target_rtl) != 0)
 953         {
 954           rtx cleanup_insns;
 955
 956           /* If this fixup jumped into this contour from before the beginning
 957              of this contour, report an error.   This code used to use
 958              the first non-label insn after f->target_rtl, but that's
 959              wrong since such can be added, by things like put_var_into_stack
 960              and have INSN_UIDs that are out of the range of the block.  */
 961           /* ??? Bug: this does not detect jumping in through intermediate
 962              blocks that have stack levels or cleanups.
 963              It detects only a problem with the innermost block
 964              around the label.  */
 965           if (f->target != 0
 966               && (dont_jump_in > 0 || (dont_jump_in == 0 && stack_level)
 967                   || cleanup_list)
 968               && INSN_UID (first_insn) < INSN_UID (f->target_rtl)
 969               && INSN_UID (first_insn) > INSN_UID (f->before_jump)
 970               && ! DECL_ERROR_ISSUED (f->target))
 971             {
 972               error ("%Jlabel '%D' used before containing binding contour",
 973                      f->target, f->target);
 974               /* Prevent multiple errors for one label.  */
 975               DECL_ERROR_ISSUED (f->target) = 1;
 976             }
 977
 978           /* We will expand the cleanups into a sequence of their own and
 979              then later on we will attach this new sequence to the insn
 980              stream just ahead of the actual jump insn.  */
 981
 982           start_sequence ();
 983
 984           /* Temporarily restore the lexical context where we will
 985              logically be inserting the fixup code.  We do this for the
 986              sake of getting the debugging information right.  */
 987
 988           lang_hooks.decls.pushlevel (0);
 989           lang_hooks.decls.set_block (f->context);
 990
 991           /* Expand the cleanups for blocks this jump exits.  */
 992           if (f->cleanup_list_list)
 993             {
 994               tree lists;
 995               for (lists = f->cleanup_list_list; lists; lists = TREE_CHAIN (lists))
 996                 /* Marked elements correspond to blocks that have been closed.
 997                    Do their cleanups.  */
 998                 if (TREE_ADDRESSABLE (lists)
 999                     && TREE_VALUE (lists) != 0)
1000                   {
1001                     expand_cleanups (TREE_VALUE (lists), 1, 1);
1002                     /* Pop any pushes done in the cleanups,
1003                        in case function is about to return.  */
1004                     do_pending_stack_adjust ();
1005                   }
1006             }
1007
1008           /* Restore stack level for the biggest contour that this
1009              jump jumps out of.  */
1010           if (f->stack_level
1011               && ! (f->target_rtl == return_label
1012                     && ((TREE_CODE (TREE_TYPE (current_function_decl))
1013                          == FUNCTION_TYPE)
1014                         && (TYPE_RETURNS_STACK_DEPRESSED
1015                             (TREE_TYPE (current_function_decl))))))
1016             emit_stack_restore (SAVE_BLOCK, f->stack_level, f->before_jump);
1017
1018           /* Finish up the sequence containing the insns which implement the
1019              necessary cleanups, and then attach that whole sequence to the
1020              insn stream just ahead of the actual jump insn.  Attaching it
1021              at that point insures that any cleanups which are in fact
1022              implicit C++ object destructions (which must be executed upon
1023              leaving the block) appear (to the debugger) to be taking place
1024              in an area of the generated code where the object(s) being
1025              destructed are still "in scope".  */
1026
1027           cleanup_insns = get_insns ();
1028           lang_hooks.decls.poplevel (1, 0, 0);
1029
1030           end_sequence ();
1031           emit_insn_after (cleanup_insns, f->before_jump);
1032
1033           f->before_jump = 0;
1034         }
1035     }
1036
1037   /* For any still-undefined labels, do the cleanups for this block now.
1038      We must do this now since items in the cleanup list may go out
1039      of scope when the block ends.  */
1040   for (prev = 0, f = goto_fixup_chain; f; prev = f, f = f->next)
1041     if (f->before_jump != 0
1042         && PREV_INSN (f->target_rtl) == 0
1043         /* Label has still not appeared.  If we are exiting a block with
1044            a stack level to restore, that started before the fixup,
1045            mark this stack level as needing restoration
1046            when the fixup is later finalized.  */
1047         && thisblock != 0
1048         /* Note: if THISBLOCK == 0 and we have a label that hasn't appeared, it
1049            means the label is undefined.  That's erroneous, but possible.  */
1050         && (thisblock->data.block.block_start_count
1051             <= f->block_start_count))
1052       {
1053         tree lists = f->cleanup_list_list;
1054         rtx cleanup_insns;
1055
1056         for (; lists; lists = TREE_CHAIN (lists))
1057           /* If the following elt. corresponds to our containing block
1058              then the elt. must be for this block.  */
1059           if (TREE_CHAIN (lists) == thisblock->data.block.outer_cleanups)
1060             {
1061               start_sequence ();
1062               lang_hooks.decls.pushlevel (0);
1063               lang_hooks.decls.set_block (f->context);
1064               expand_cleanups (TREE_VALUE (lists), 1, 1);
1065               do_pending_stack_adjust ();
1066               cleanup_insns = get_insns ();
1067               lang_hooks.decls.poplevel (1, 0, 0);
1068               end_sequence ();
1069               if (cleanup_insns != 0)
1070                 f->before_jump
1071                   = emit_insn_after (cleanup_insns, f->before_jump);
1072
1073               f->cleanup_list_list = TREE_CHAIN (lists);
1074             }
1075
1076         if (stack_level)
1077           f->stack_level = stack_level;
1078       }
1079 }
1080 \f
1081 /* Return the number of times character C occurs in string S.  */
1082 static int
1083 n_occurrences (int c, const char *s)
1084 {
1085   int n = 0;
1086   while (*s)
1087     n += (*s++ == c);
1088   return n;
1089 }
1090 \f
1091 /* Generate RTL for an asm statement (explicit assembler code).
1092    STRING is a STRING_CST node containing the assembler code text,
1093    or an ADDR_EXPR containing a STRING_CST.  VOL nonzero means the
1094    insn is volatile; don't optimize it.  */
1095
1096 void
1097 expand_asm (tree string, int vol)
1098 {
1099   rtx body;
1100
1101   if (TREE_CODE (string) == ADDR_EXPR)
1102     string = TREE_OPERAND (string, 0);
1103
1104   body = gen_rtx_ASM_INPUT (VOIDmode, TREE_STRING_POINTER (string));
1105
1106   MEM_VOLATILE_P (body) = vol;
1107
1108   emit_insn (body);
1109
1110   clear_last_expr ();
1111 }
1112
1113 /* Parse the output constraint pointed to by *CONSTRAINT_P.  It is the
1114    OPERAND_NUMth output operand, indexed from zero.  There are NINPUTS
1115    inputs and NOUTPUTS outputs to this extended-asm.  Upon return,
1116    *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
1117    memory operand.  Similarly, *ALLOWS_REG will be TRUE iff the
1118    constraint allows the use of a register operand.  And, *IS_INOUT
1119    will be true if the operand is read-write, i.e., if it is used as
1120    an input as well as an output.  If *CONSTRAINT_P is not in
1121    canonical form, it will be made canonical.  (Note that `+' will be
1122    replaced with `=' as part of this process.)
1123
1124    Returns TRUE if all went well; FALSE if an error occurred.  */
1125
1126 bool
1127 parse_output_constraint (const char **constraint_p, int operand_num,
1128                          int ninputs, int noutputs, bool *allows_mem,
1129                          bool *allows_reg, bool *is_inout)
1130 {
1131   const char *constraint = *constraint_p;
1132   const char *p;
1133
1134   /* Assume the constraint doesn't allow the use of either a register
1135      or memory.  */
1136   *allows_mem = false;
1137   *allows_reg = false;
1138
1139   /* Allow the `=' or `+' to not be at the beginning of the string,
1140      since it wasn't explicitly documented that way, and there is a
1141      large body of code that puts it last.  Swap the character to
1142      the front, so as not to uglify any place else.  */
1143   p = strchr (constraint, '=');
1144   if (!p)
1145     p = strchr (constraint, '+');
1146
1147   /* If the string doesn't contain an `=', issue an error
1148      message.  */
1149   if (!p)
1150     {
1151       error ("output operand constraint lacks `='");
1152       return false;
1153     }
1154
1155   /* If the constraint begins with `+', then the operand is both read
1156      from and written to.  */
1157   *is_inout = (*p == '+');
1158
1159   /* Canonicalize the output constraint so that it begins with `='.  */
1160   if (p != constraint || is_inout)
1161     {
1162       char *buf;
1163       size_t c_len = strlen (constraint);
1164
1165       if (p != constraint)
1166         warning ("output constraint `%c' for operand %d is not at the beginning",
1167                  *p, operand_num);
1168
1169       /* Make a copy of the constraint.  */
1170       buf = alloca (c_len + 1);
1171       strcpy (buf, constraint);
1172       /* Swap the first character and the `=' or `+'.  */
1173       buf[p - constraint] = buf[0];
1174       /* Make sure the first character is an `='.  (Until we do this,
1175          it might be a `+'.)  */
1176       buf[0] = '=';
1177       /* Replace the constraint with the canonicalized string.  */
1178       *constraint_p = ggc_alloc_string (buf, c_len);
1179       constraint = *constraint_p;
1180     }
1181
1182   /* Loop through the constraint string.  */
1183   for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
1184     switch (*p)
1185       {
1186       case '+':
1187       case '=':
1188         error ("operand constraint contains incorrectly positioned '+' or '='");
1189         return false;
1190
1191       case '%':
1192         if (operand_num + 1 == ninputs + noutputs)
1193           {
1194             error ("`%%' constraint used with last operand");
1195             return false;
1196           }
1197         break;
1198
1199       case 'V':  case 'm':  case 'o':
1200         *allows_mem = true;
1201         break;
1202
1203       case '?':  case '!':  case '*':  case '&':  case '#':
1204       case 'E':  case 'F':  case 'G':  case 'H':
1205       case 's':  case 'i':  case 'n':
1206       case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
1207       case 'N':  case 'O':  case 'P':  case ',':
1208         break;
1209
1210       case '0':  case '1':  case '2':  case '3':  case '4':
1211       case '5':  case '6':  case '7':  case '8':  case '9':
1212       case '[':
1213         error ("matching constraint not valid in output operand");
1214         return false;
1215
1216       case '<':  case '>':
1217         /* ??? Before flow, auto inc/dec insns are not supposed to exist,
1218            excepting those that expand_call created.  So match memory
1219            and hope.  */
1220         *allows_mem = true;
1221         break;
1222
1223       case 'g':  case 'X':
1224         *allows_reg = true;
1225         *allows_mem = true;
1226         break;
1227
1228       case 'p': case 'r':
1229         *allows_reg = true;
1230         break;
1231
1232       default:
1233         if (!ISALPHA (*p))
1234           break;
1235         if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
1236           *allows_reg = true;
1237 #ifdef EXTRA_CONSTRAINT_STR
1238         else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
1239           *allows_reg = true;
1240         else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
1241           *allows_mem = true;
1242         else
1243           {
1244             /* Otherwise we can't assume anything about the nature of
1245                the constraint except that it isn't purely registers.
1246                Treat it like "g" and hope for the best.  */
1247             *allows_reg = true;
1248             *allows_mem = true;
1249           }
1250 #endif
1251         break;
1252       }
1253
1254   if (*is_inout && !*allows_reg)
1255     warning ("read-write constraint does not allow a register");
1256
1257   return true;
1258 }
1259
1260 /* Similar, but for input constraints.  */
1261
1262 bool
1263 parse_input_constraint (const char **constraint_p, int input_num,
1264                         int ninputs, int noutputs, int ninout,
1265                         const char * const * constraints,
1266                         bool *allows_mem, bool *allows_reg)
1267 {
1268   const char *constraint = *constraint_p;
1269   const char *orig_constraint = constraint;
1270   size_t c_len = strlen (constraint);
1271   size_t j;
1272   bool saw_match = false;
1273
1274   /* Assume the constraint doesn't allow the use of either
1275      a register or memory.  */
1276   *allows_mem = false;
1277   *allows_reg = false;
1278
1279   /* Make sure constraint has neither `=', `+', nor '&'.  */
1280
1281   for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
1282     switch (constraint[j])
1283       {
1284       case '+':  case '=':  case '&':
1285         if (constraint == orig_constraint)
1286           {
1287             error ("input operand constraint contains `%c'", constraint[j]);
1288             return false;
1289           }
1290         break;
1291
1292       case '%':
1293         if (constraint == orig_constraint
1294             && input_num + 1 == ninputs - ninout)
1295           {
1296             error ("`%%' constraint used with last operand");
1297             return false;
1298           }
1299         break;
1300
1301       case 'V':  case 'm':  case 'o':
1302         *allows_mem = true;
1303         break;
1304
1305       case '<':  case '>':
1306       case '?':  case '!':  case '*':  case '#':
1307       case 'E':  case 'F':  case 'G':  case 'H':
1308       case 's':  case 'i':  case 'n':
1309       case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
1310       case 'N':  case 'O':  case 'P':  case ',':
1311         break;
1312
1313         /* Whether or not a numeric constraint allows a register is
1314            decided by the matching constraint, and so there is no need
1315            to do anything special with them.  We must handle them in
1316            the default case, so that we don't unnecessarily force
1317            operands to memory.  */
1318       case '0':  case '1':  case '2':  case '3':  case '4':
1319       case '5':  case '6':  case '7':  case '8':  case '9':
1320         {
1321           char *end;
1322           unsigned long match;
1323
1324           saw_match = true;
1325
1326           match = strtoul (constraint + j, &end, 10);
1327           if (match >= (unsigned long) noutputs)
1328             {
1329               error ("matching constraint references invalid operand number");
1330               return false;
1331             }
1332
1333           /* Try and find the real constraint for this dup.  Only do this
1334              if the matching constraint is the only alternative.  */
1335           if (*end == '\0'
1336               && (j == 0 || (j == 1 && constraint[0] == '%')))
1337             {
1338               constraint = constraints[match];
1339               *constraint_p = constraint;
1340               c_len = strlen (constraint);
1341               j = 0;
1342               /* ??? At the end of the loop, we will skip the first part of
1343                  the matched constraint.  This assumes not only that the
1344                  other constraint is an output constraint, but also that
1345                  the '=' or '+' come first.  */
1346               break;
1347             }
1348           else
1349             j = end - constraint;
1350           /* Anticipate increment at end of loop.  */
1351           j--;
1352         }
1353         /* Fall through.  */
1354
1355       case 'p':  case 'r':
1356         *allows_reg = true;
1357         break;
1358
1359       case 'g':  case 'X':
1360         *allows_reg = true;
1361         *allows_mem = true;
1362         break;
1363
1364       default:
1365         if (! ISALPHA (constraint[j]))
1366           {
1367             error ("invalid punctuation `%c' in constraint", constraint[j]);
1368             return false;
1369           }
1370         if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
1371             != NO_REGS)
1372           *allows_reg = true;
1373 #ifdef EXTRA_CONSTRAINT_STR
1374         else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
1375           *allows_reg = true;
1376         else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
1377           *allows_mem = true;
1378         else
1379           {
1380             /* Otherwise we can't assume anything about the nature of
1381                the constraint except that it isn't purely registers.
1382                Treat it like "g" and hope for the best.  */
1383             *allows_reg = true;
1384             *allows_mem = true;
1385           }
1386 #endif
1387         break;
1388       }
1389
1390   if (saw_match && !*allows_reg)
1391     warning ("matching constraint does not allow a register");
1392
1393   return true;
1394 }
1395
1396 /* Check for overlap between registers marked in CLOBBERED_REGS and
1397    anything inappropriate in DECL.  Emit error and return TRUE for error,
1398    FALSE for ok.  */
1399
1400 static bool
1401 decl_conflicts_with_clobbers_p (tree decl, const HARD_REG_SET clobbered_regs)
1402 {
1403   /* Conflicts between asm-declared register variables and the clobber
1404      list are not allowed.  */
1405   if ((TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == PARM_DECL)
1406       && DECL_REGISTER (decl)
1407       && REG_P (DECL_RTL (decl))
1408       && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
1409     {
1410       rtx reg = DECL_RTL (decl);
1411       unsigned int regno;
1412
1413       for (regno = REGNO (reg);
1414            regno < (REGNO (reg)
1415                     + hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]);
1416            regno++)
1417         if (TEST_HARD_REG_BIT (clobbered_regs, regno))
1418           {
1419             error ("asm-specifier for variable `%s' conflicts with asm clobber list",
1420                    IDENTIFIER_POINTER (DECL_NAME (decl)));
1421
1422             /* Reset registerness to stop multiple errors emitted for a
1423                single variable.  */
1424             DECL_REGISTER (decl) = 0;
1425             return true;
1426           }
1427     }
1428   return false;
1429 }
1430
1431 /* Generate RTL for an asm statement with arguments.
1432    STRING is the instruction template.
1433    OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
1434    Each output or input has an expression in the TREE_VALUE and
1435    and a tree list in TREE_PURPOSE which in turn contains a constraint
1436    name in TREE_VALUE (or NULL_TREE) and a constraint string
1437    in TREE_PURPOSE.
1438    CLOBBERS is a list of STRING_CST nodes each naming a hard register
1439    that is clobbered by this insn.
1440
1441    Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
1442    Some elements of OUTPUTS may be replaced with trees representing temporary
1443    values.  The caller should copy those temporary values to the originally
1444    specified lvalues.
1445
1446    VOL nonzero means the insn is volatile; don't optimize it.  */
1447
1448 void
1449 expand_asm_operands (tree string, tree outputs, tree inputs,
1450                      tree clobbers, int vol, location_t locus)
1451 {
1452   rtvec argvec, constraintvec;
1453   rtx body;
1454   int ninputs = list_length (inputs);
1455   int noutputs = list_length (outputs);
1456   int ninout;
1457   int nclobbers;
1458   HARD_REG_SET clobbered_regs;
1459   int clobber_conflict_found = 0;
1460   tree tail;
1461   tree t;
1462   int i;
1463   /* Vector of RTX's of evaluated output operands.  */
1464   rtx *output_rtx = alloca (noutputs * sizeof (rtx));
1465   int *inout_opnum = alloca (noutputs * sizeof (int));
1466   rtx *real_output_rtx = alloca (noutputs * sizeof (rtx));
1467   enum machine_mode *inout_mode
1468     = alloca (noutputs * sizeof (enum machine_mode));
1469   const char **constraints
1470     = alloca ((noutputs + ninputs) * sizeof (const char *));
1471   int old_generating_concat_p = generating_concat_p;
1472
1473   /* An ASM with no outputs needs to be treated as volatile, for now.  */
1474   if (noutputs == 0)
1475     vol = 1;
1476
1477   if (! check_operand_nalternatives (outputs, inputs))
1478     return;
1479
1480   string = resolve_asm_operand_names (string, outputs, inputs);
1481
1482   /* Collect constraints.  */
1483   i = 0;
1484   for (t = outputs; t ; t = TREE_CHAIN (t), i++)
1485     constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1486   for (t = inputs; t ; t = TREE_CHAIN (t), i++)
1487     constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1488
1489   /* Sometimes we wish to automatically clobber registers across an asm.
1490      Case in point is when the i386 backend moved from cc0 to a hard reg --
1491      maintaining source-level compatibility means automatically clobbering
1492      the flags register.  */
1493   clobbers = targetm.md_asm_clobbers (clobbers);
1494
1495   /* Count the number of meaningful clobbered registers, ignoring what
1496      we would ignore later.  */
1497   nclobbers = 0;
1498   CLEAR_HARD_REG_SET (clobbered_regs);
1499   for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1500     {
1501       const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1502
1503       i = decode_reg_name (regname);
1504       if (i >= 0 || i == -4)
1505         ++nclobbers;
1506       else if (i == -2)
1507         error ("unknown register name `%s' in `asm'", regname);
1508
1509       /* Mark clobbered registers.  */
1510       if (i >= 0)
1511         {
1512           /* Clobbering the PIC register is an error */
1513           if (i == (int) PIC_OFFSET_TABLE_REGNUM)
1514             {
1515               error ("PIC register `%s' clobbered in `asm'", regname);
1516               return;
1517             }
1518
1519           SET_HARD_REG_BIT (clobbered_regs, i);
1520         }
1521     }
1522
1523   clear_last_expr ();
1524
1525   /* First pass over inputs and outputs checks validity and sets
1526      mark_addressable if needed.  */
1527
1528   ninout = 0;
1529   for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1530     {
1531       tree val = TREE_VALUE (tail);
1532       tree type = TREE_TYPE (val);
1533       const char *constraint;
1534       bool is_inout;
1535       bool allows_reg;
1536       bool allows_mem;
1537
1538       /* If there's an erroneous arg, emit no insn.  */
1539       if (type == error_mark_node)
1540         return;
1541
1542       /* Try to parse the output constraint.  If that fails, there's
1543          no point in going further.  */
1544       constraint = constraints[i];
1545       if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
1546                                     &allows_mem, &allows_reg, &is_inout))
1547         return;
1548
1549       if (! allows_reg
1550           && (allows_mem
1551               || is_inout
1552               || (DECL_P (val)
1553                   && GET_CODE (DECL_RTL (val)) == REG
1554                   && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
1555         lang_hooks.mark_addressable (val);
1556
1557       if (is_inout)
1558         ninout++;
1559     }
1560
1561   ninputs += ninout;
1562   if (ninputs + noutputs > MAX_RECOG_OPERANDS)
1563     {
1564       error ("more than %d operands in `asm'", MAX_RECOG_OPERANDS);
1565       return;
1566     }
1567
1568   for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
1569     {
1570       bool allows_reg, allows_mem;
1571       const char *constraint;
1572
1573       /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
1574          would get VOIDmode and that could cause a crash in reload.  */
1575       if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
1576         return;
1577
1578       constraint = constraints[i + noutputs];
1579       if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
1580                                     constraints, &allows_mem, &allows_reg))
1581         return;
1582
1583       if (! allows_reg && allows_mem)
1584         lang_hooks.mark_addressable (TREE_VALUE (tail));
1585     }
1586
1587   /* Second pass evaluates arguments.  */
1588
1589   ninout = 0;
1590   for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1591     {
1592       tree val = TREE_VALUE (tail);
1593       tree type = TREE_TYPE (val);
1594       bool is_inout;
1595       bool allows_reg;
1596       bool allows_mem;
1597       rtx op;
1598
1599       if (!parse_output_constraint (&constraints[i], i, ninputs,
1600                                     noutputs, &allows_mem, &allows_reg,
1601                                     &is_inout))
1602         abort ();
1603
1604       /* If an output operand is not a decl or indirect ref and our constraint
1605          allows a register, make a temporary to act as an intermediate.
1606          Make the asm insn write into that, then our caller will copy it to
1607          the real output operand.  Likewise for promoted variables.  */
1608
1609       generating_concat_p = 0;
1610
1611       real_output_rtx[i] = NULL_RTX;
1612       if ((TREE_CODE (val) == INDIRECT_REF
1613            && allows_mem)
1614           || (DECL_P (val)
1615               && (allows_mem || GET_CODE (DECL_RTL (val)) == REG)
1616               && ! (GET_CODE (DECL_RTL (val)) == REG
1617                     && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
1618           || ! allows_reg
1619           || is_inout)
1620         {
1621           op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
1622           if (GET_CODE (op) == MEM)
1623             op = validize_mem (op);
1624
1625           if (! allows_reg && GET_CODE (op) != MEM)
1626             error ("output number %d not directly addressable", i);
1627           if ((! allows_mem && GET_CODE (op) == MEM)
1628               || GET_CODE (op) == CONCAT)
1629             {
1630               real_output_rtx[i] = protect_from_queue (op, 1);
1631               op = gen_reg_rtx (GET_MODE (op));
1632               if (is_inout)
1633                 emit_move_insn (op, real_output_rtx[i]);
1634             }
1635         }
1636       else
1637         {
1638           op = assign_temp (type, 0, 0, 1);
1639           op = validize_mem (op);
1640           TREE_VALUE (tail) = make_tree (type, op);
1641         }
1642       output_rtx[i] = op;
1643
1644       generating_concat_p = old_generating_concat_p;
1645
1646       if (is_inout)
1647         {
1648           inout_mode[ninout] = TYPE_MODE (type);
1649           inout_opnum[ninout++] = i;
1650         }
1651
1652       if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
1653         clobber_conflict_found = 1;
1654     }
1655
1656   /* Make vectors for the expression-rtx, constraint strings,
1657      and named operands.  */
1658
1659   argvec = rtvec_alloc (ninputs);
1660   constraintvec = rtvec_alloc (ninputs);
1661
1662   body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
1663                                 : GET_MODE (output_rtx[0])),
1664                                TREE_STRING_POINTER (string),
1665                                empty_string, 0, argvec, constraintvec,
1666                                locus.file, locus.line);
1667
1668   MEM_VOLATILE_P (body) = vol;
1669
1670   /* Eval the inputs and put them into ARGVEC.
1671      Put their constraints into ASM_INPUTs and store in CONSTRAINTS.  */
1672
1673   for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
1674     {
1675       bool allows_reg, allows_mem;
1676       const char *constraint;
1677       tree val, type;
1678       rtx op;
1679
1680       constraint = constraints[i + noutputs];
1681       if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
1682                                     constraints, &allows_mem, &allows_reg))
1683         abort ();
1684
1685       generating_concat_p = 0;
1686
1687       val = TREE_VALUE (tail);
1688       type = TREE_TYPE (val);
1689       op = expand_expr (val, NULL_RTX, VOIDmode,
1690                         (allows_mem && !allows_reg
1691                          ? EXPAND_MEMORY : EXPAND_NORMAL));
1692
1693       /* Never pass a CONCAT to an ASM.  */
1694       if (GET_CODE (op) == CONCAT)
1695         op = force_reg (GET_MODE (op), op);
1696       else if (GET_CODE (op) == MEM)
1697         op = validize_mem (op);
1698
1699       if (asm_operand_ok (op, constraint) <= 0)
1700         {
1701           if (allows_reg)
1702             op = force_reg (TYPE_MODE (type), op);
1703           else if (!allows_mem)
1704             warning ("asm operand %d probably doesn't match constraints",
1705                      i + noutputs);
1706           else if (GET_CODE (op) == MEM)
1707             {
1708               /* We won't recognize either volatile memory or memory
1709                  with a queued address as available a memory_operand
1710                  at this point.  Ignore it: clearly this *is* a memory.  */
1711             }
1712           else
1713             {
1714               warning ("use of memory input without lvalue in "
1715                        "asm operand %d is deprecated", i + noutputs);
1716
1717               if (CONSTANT_P (op))
1718                 {
1719                   rtx mem = force_const_mem (TYPE_MODE (type), op);
1720                   if (mem)
1721                     op = validize_mem (mem);
1722                   else
1723                     op = force_reg (TYPE_MODE (type), op);
1724                 }
1725               if (GET_CODE (op) == REG
1726                   || GET_CODE (op) == SUBREG
1727                   || GET_CODE (op) == ADDRESSOF
1728                   || GET_CODE (op) == CONCAT)
1729                 {
1730                   tree qual_type = build_qualified_type (type,
1731                                                          (TYPE_QUALS (type)
1732                                                           | TYPE_QUAL_CONST));
1733                   rtx memloc = assign_temp (qual_type, 1, 1, 1);
1734                   memloc = validize_mem (memloc);
1735                   emit_move_insn (memloc, op);
1736                   op = memloc;
1737                 }
1738             }
1739         }
1740
1741       generating_concat_p = old_generating_concat_p;
1742       ASM_OPERANDS_INPUT (body, i) = op;
1743
1744       ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
1745         = gen_rtx_ASM_INPUT (TYPE_MODE (type), constraints[i + noutputs]);
1746
1747       if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
1748         clobber_conflict_found = 1;
1749     }
1750
1751   /* Protect all the operands from the queue now that they have all been
1752      evaluated.  */
1753
1754   generating_concat_p = 0;
1755
1756   for (i = 0; i < ninputs - ninout; i++)
1757     ASM_OPERANDS_INPUT (body, i)
1758       = protect_from_queue (ASM_OPERANDS_INPUT (body, i), 0);
1759
1760   for (i = 0; i < noutputs; i++)
1761     output_rtx[i] = protect_from_queue (output_rtx[i], 1);
1762
1763   /* For in-out operands, copy output rtx to input rtx.  */
1764   for (i = 0; i < ninout; i++)
1765     {
1766       int j = inout_opnum[i];
1767       char buffer[16];
1768
1769       ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
1770         = output_rtx[j];
1771
1772       sprintf (buffer, "%d", j);
1773       ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
1774         = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
1775     }
1776
1777   generating_concat_p = old_generating_concat_p;
1778
1779   /* Now, for each output, construct an rtx
1780      (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
1781                                ARGVEC CONSTRAINTS OPNAMES))
1782      If there is more than one, put them inside a PARALLEL.  */
1783
1784   if (noutputs == 1 && nclobbers == 0)
1785     {
1786       ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = constraints[0];
1787       emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1788     }
1789
1790   else if (noutputs == 0 && nclobbers == 0)
1791     {
1792       /* No output operands: put in a raw ASM_OPERANDS rtx.  */
1793       emit_insn (body);
1794     }
1795
1796   else
1797     {
1798       rtx obody = body;
1799       int num = noutputs;
1800
1801       if (num == 0)
1802         num = 1;
1803
1804       body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1805
1806       /* For each output operand, store a SET.  */
1807       for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1808         {
1809           XVECEXP (body, 0, i)
1810             = gen_rtx_SET (VOIDmode,
1811                            output_rtx[i],
1812                            gen_rtx_ASM_OPERANDS
1813                            (GET_MODE (output_rtx[i]),
1814                             TREE_STRING_POINTER (string),
1815                             constraints[i], i, argvec, constraintvec,
1816                             locus.file, locus.line));
1817
1818           MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1819         }
1820
1821       /* If there are no outputs (but there are some clobbers)
1822          store the bare ASM_OPERANDS into the PARALLEL.  */
1823
1824       if (i == 0)
1825         XVECEXP (body, 0, i++) = obody;
1826
1827       /* Store (clobber REG) for each clobbered register specified.  */
1828
1829       for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1830         {
1831           const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1832           int j = decode_reg_name (regname);
1833           rtx clobbered_reg;
1834
1835           if (j < 0)
1836             {
1837               if (j == -3)      /* `cc', which is not a register */
1838                 continue;
1839
1840               if (j == -4)      /* `memory', don't cache memory across asm */
1841                 {
1842                   XVECEXP (body, 0, i++)
1843                     = gen_rtx_CLOBBER (VOIDmode,
1844                                        gen_rtx_MEM
1845                                        (BLKmode,
1846                                         gen_rtx_SCRATCH (VOIDmode)));
1847                   continue;
1848                 }
1849
1850               /* Ignore unknown register, error already signaled.  */
1851               continue;
1852             }
1853
1854           /* Use QImode since that's guaranteed to clobber just one reg.  */
1855           clobbered_reg = gen_rtx_REG (QImode, j);
1856
1857           /* Do sanity check for overlap between clobbers and respectively
1858              input and outputs that hasn't been handled.  Such overlap
1859              should have been detected and reported above.  */
1860           if (!clobber_conflict_found)
1861             {
1862               int opno;
1863
1864               /* We test the old body (obody) contents to avoid tripping
1865                  over the under-construction body.  */
1866               for (opno = 0; opno < noutputs; opno++)
1867                 if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno]))
1868                   internal_error ("asm clobber conflict with output operand");
1869
1870               for (opno = 0; opno < ninputs - ninout; opno++)
1871                 if (reg_overlap_mentioned_p (clobbered_reg,
1872                                              ASM_OPERANDS_INPUT (obody, opno)))
1873                   internal_error ("asm clobber conflict with input operand");
1874             }
1875
1876           XVECEXP (body, 0, i++)
1877             = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1878         }
1879
1880       emit_insn (body);
1881     }
1882
1883   /* For any outputs that needed reloading into registers, spill them
1884      back to where they belong.  */
1885   for (i = 0; i < noutputs; ++i)
1886     if (real_output_rtx[i])
1887       emit_move_insn (real_output_rtx[i], output_rtx[i]);
1888
1889   free_temp_slots ();
1890 }
1891
1892 /* A subroutine of expand_asm_operands.  Check that all operands have
1893    the same number of alternatives.  Return true if so.  */
1894
1895 static bool
1896 check_operand_nalternatives (tree outputs, tree inputs)
1897 {
1898   if (outputs || inputs)
1899     {
1900       tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1901       int nalternatives
1902         = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1903       tree next = inputs;
1904
1905       if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1906         {
1907           error ("too many alternatives in `asm'");
1908           return false;
1909         }
1910
1911       tmp = outputs;
1912       while (tmp)
1913         {
1914           const char *constraint
1915             = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1916
1917           if (n_occurrences (',', constraint) != nalternatives)
1918             {
1919               error ("operand constraints for `asm' differ in number of alternatives");
1920               return false;
1921             }
1922
1923           if (TREE_CHAIN (tmp))
1924             tmp = TREE_CHAIN (tmp);
1925           else
1926             tmp = next, next = 0;
1927         }
1928     }
1929
1930   return true;
1931 }
1932
1933 /* A subroutine of expand_asm_operands.  Check that all operand names
1934    are unique.  Return true if so.  We rely on the fact that these names
1935    are identifiers, and so have been canonicalized by get_identifier,
1936    so all we need are pointer comparisons.  */
1937
1938 static bool
1939 check_unique_operand_names (tree outputs, tree inputs)
1940 {
1941   tree i, j;
1942
1943   for (i = outputs; i ; i = TREE_CHAIN (i))
1944     {
1945       tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1946       if (! i_name)
1947         continue;
1948
1949       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1950         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1951           goto failure;
1952     }
1953
1954   for (i = inputs; i ; i = TREE_CHAIN (i))
1955     {
1956       tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1957       if (! i_name)
1958         continue;
1959
1960       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1961         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1962           goto failure;
1963       for (j = outputs; j ; j = TREE_CHAIN (j))
1964         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1965           goto failure;
1966     }
1967
1968   return true;
1969
1970  failure:
1971   error ("duplicate asm operand name '%s'",
1972          TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
1973   return false;
1974 }
1975
1976 /* A subroutine of expand_asm_operands.  Resolve the names of the operands
1977    in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1978    STRING and in the constraints to those numbers.  */
1979
1980 tree
1981 resolve_asm_operand_names (tree string, tree outputs, tree inputs)
1982 {
1983   char *buffer;
1984   char *p;
1985   const char *c;
1986   tree t;
1987
1988   check_unique_operand_names (outputs, inputs);
1989
1990   /* Substitute [<name>] in input constraint strings.  There should be no
1991      named operands in output constraints.  */
1992   for (t = inputs; t ; t = TREE_CHAIN (t))
1993     {
1994       c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1995       if (strchr (c, '[') != NULL)
1996         {
1997           p = buffer = xstrdup (c);
1998           while ((p = strchr (p, '[')) != NULL)
1999             p = resolve_operand_name_1 (p, outputs, inputs);
2000           TREE_VALUE (TREE_PURPOSE (t))
2001             = build_string (strlen (buffer), buffer);
2002           free (buffer);
2003         }
2004     }
2005
2006   /* Now check for any needed substitutions in the template.  */
2007   c = TREE_STRING_POINTER (string);
2008   while ((c = strchr (c, '%')) != NULL)
2009     {
2010       if (c[1] == '[')
2011         break;
2012       else if (ISALPHA (c[1]) && c[2] == '[')
2013         break;
2014       else
2015         {
2016           c += 1;
2017           continue;
2018         }
2019     }
2020
2021   if (c)
2022     {
2023       /* OK, we need to make a copy so we can perform the substitutions.
2024          Assume that we will not need extra space--we get to remove '['
2025          and ']', which means we cannot have a problem until we have more
2026          than 999 operands.  */
2027       buffer = xstrdup (TREE_STRING_POINTER (string));
2028       p = buffer + (c - TREE_STRING_POINTER (string));
2029
2030       while ((p = strchr (p, '%')) != NULL)
2031         {
2032           if (p[1] == '[')
2033             p += 1;
2034           else if (ISALPHA (p[1]) && p[2] == '[')
2035             p += 2;
2036           else
2037             {
2038               p += 1;
2039               continue;
2040             }
2041
2042           p = resolve_operand_name_1 (p, outputs, inputs);
2043         }
2044
2045       string = build_string (strlen (buffer), buffer);
2046       free (buffer);
2047     }
2048
2049   return string;
2050 }
2051
2052 /* A subroutine of resolve_operand_names.  P points to the '[' for a
2053    potential named operand of the form [<name>].  In place, replace
2054    the name and brackets with a number.  Return a pointer to the
2055    balance of the string after substitution.  */
2056
2057 static char *
2058 resolve_operand_name_1 (char *p, tree outputs, tree inputs)
2059 {
2060   char *q;
2061   int op;
2062   tree t;
2063   size_t len;
2064
2065   /* Collect the operand name.  */
2066   q = strchr (p, ']');
2067   if (!q)
2068     {
2069       error ("missing close brace for named operand");
2070       return strchr (p, '\0');
2071     }
2072   len = q - p - 1;
2073
2074   /* Resolve the name to a number.  */
2075   for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
2076     {
2077       tree name = TREE_PURPOSE (TREE_PURPOSE (t));
2078       if (name)
2079         {
2080           const char *c = TREE_STRING_POINTER (name);
2081           if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
2082             goto found;
2083         }
2084     }
2085   for (t = inputs; t ; t = TREE_CHAIN (t), op++)
2086     {
2087       tree name = TREE_PURPOSE (TREE_PURPOSE (t));
2088       if (name)
2089         {
2090           const char *c = TREE_STRING_POINTER (name);
2091           if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
2092             goto found;
2093         }
2094     }
2095
2096   *q = '\0';
2097   error ("undefined named operand '%s'", p + 1);
2098   op = 0;
2099  found:
2100
2101   /* Replace the name with the number.  Unfortunately, not all libraries
2102      get the return value of sprintf correct, so search for the end of the
2103      generated string by hand.  */
2104   sprintf (p, "%d", op);
2105   p = strchr (p, '\0');
2106
2107   /* Verify the no extra buffer space assumption.  */
2108   if (p > q)
2109     abort ();
2110
2111   /* Shift the rest of the buffer down to fill the gap.  */
2112   memmove (p, q + 1, strlen (q + 1) + 1);
2113
2114   return p;
2115 }
2116 \f
2117 /* Generate RTL to evaluate the expression EXP
2118    and remember it in case this is the VALUE in a ({... VALUE; }) constr.
2119    Provided just for backward-compatibility.  expand_expr_stmt_value()
2120    should be used for new code.  */
2121
2122 void
2123 expand_expr_stmt (tree exp)
2124 {
2125   expand_expr_stmt_value (exp, -1, 1);
2126 }
2127
2128 /* Generate RTL to evaluate the expression EXP.  WANT_VALUE tells
2129    whether to (1) save the value of the expression, (0) discard it or
2130    (-1) use expr_stmts_for_value to tell.  The use of -1 is
2131    deprecated, and retained only for backward compatibility.  */
2132
2133 void
2134 expand_expr_stmt_value (tree exp, int want_value, int maybe_last)
2135 {
2136   rtx value;
2137   tree type;
2138   rtx alt_rtl = NULL;
2139
2140   if (want_value == -1)
2141     want_value = expr_stmts_for_value != 0;
2142
2143   /* If -Wextra, warn about statements with no side effects,
2144      except for an explicit cast to void (e.g. for assert()), and
2145      except for last statement in ({...}) where they may be useful.  */
2146   if (! want_value
2147       && (expr_stmts_for_value == 0 || ! maybe_last)
2148       && exp != error_mark_node
2149       && warn_unused_value)
2150     {
2151       if (TREE_SIDE_EFFECTS (exp))
2152         warn_if_unused_value (exp);
2153       else if (!VOID_TYPE_P (TREE_TYPE (exp)))
2154         warning ("%Hstatement with no effect", &emit_locus);
2155     }
2156
2157   /* If EXP is of function type and we are expanding statements for
2158      value, convert it to pointer-to-function.  */
2159   if (want_value && TREE_CODE (TREE_TYPE (exp)) == FUNCTION_TYPE)
2160     exp = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
2161
2162   /* The call to `expand_expr' could cause last_expr_type and
2163      last_expr_value to get reset.  Therefore, we set last_expr_value
2164      and last_expr_type *after* calling expand_expr.  */
2165   value = expand_expr_real (exp, want_value ? NULL_RTX : const0_rtx,
2166                             VOIDmode, 0, &alt_rtl);
2167   type = TREE_TYPE (exp);
2168
2169   /* If all we do is reference a volatile value in memory,
2170      copy it to a register to be sure it is actually touched.  */
2171   if (value && GET_CODE (value) == MEM && TREE_THIS_VOLATILE (exp))
2172     {
2173       if (TYPE_MODE (type) == VOIDmode)
2174         ;
2175       else if (TYPE_MODE (type) != BLKmode)
2176         value = copy_to_reg (value);
2177       else
2178         {
2179           rtx lab = gen_label_rtx ();
2180
2181           /* Compare the value with itself to reference it.  */
2182           emit_cmp_and_jump_insns (value, value, EQ,
2183                                    expand_expr (TYPE_SIZE (type),
2184                                                 NULL_RTX, VOIDmode, 0),
2185                                    BLKmode, 0, lab);
2186           emit_label (lab);
2187         }
2188     }
2189
2190   /* If this expression is part of a ({...}) and is in memory, we may have
2191      to preserve temporaries.  */
2192   preserve_temp_slots (value);
2193
2194   /* Free any temporaries used to evaluate this expression.  Any temporary
2195      used as a result of this expression will already have been preserved
2196      above.  */
2197   free_temp_slots ();
2198
2199   if (want_value)
2200     {
2201       last_expr_value = value;
2202       last_expr_alt_rtl = alt_rtl;
2203       last_expr_type = type;
2204     }
2205
2206   emit_queue ();
2207 }
2208
2209 /* Warn if EXP contains any computations whose results are not used.
2210    Return 1 if a warning is printed; 0 otherwise.  */
2211
2212 int
2213 warn_if_unused_value (tree exp)
2214 {
2215   if (TREE_USED (exp))
2216     return 0;
2217
2218   /* Don't warn about void constructs.  This includes casting to void,
2219      void function calls, and statement expressions with a final cast
2220      to void.  */
2221   if (VOID_TYPE_P (TREE_TYPE (exp)))
2222     return 0;
2223
2224   switch (TREE_CODE (exp))
2225     {
2226     case PREINCREMENT_EXPR:
2227     case POSTINCREMENT_EXPR:
2228     case PREDECREMENT_EXPR:
2229     case POSTDECREMENT_EXPR:
2230     case MODIFY_EXPR:
2231     case INIT_EXPR:
2232     case TARGET_EXPR:
2233     case CALL_EXPR:
2234     case RTL_EXPR:
2235     case TRY_CATCH_EXPR:
2236     case WITH_CLEANUP_EXPR:
2237     case EXIT_EXPR:
2238       return 0;
2239
2240     case BIND_EXPR:
2241       /* For a binding, warn if no side effect within it.  */
2242       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2243
2244     case SAVE_EXPR:
2245       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2246
2247     case TRUTH_ORIF_EXPR:
2248     case TRUTH_ANDIF_EXPR:
2249       /* In && or ||, warn if 2nd operand has no side effect.  */
2250       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2251
2252     case COMPOUND_EXPR:
2253       if (TREE_NO_UNUSED_WARNING (exp))
2254         return 0;
2255       if (warn_if_unused_value (TREE_OPERAND (exp, 0)))
2256         return 1;
2257       /* Let people do `(foo (), 0)' without a warning.  */
2258       if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
2259         return 0;
2260       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2261
2262     case NOP_EXPR:
2263     case CONVERT_EXPR:
2264     case NON_LVALUE_EXPR:
2265       /* Don't warn about conversions not explicit in the user's program.  */
2266       if (TREE_NO_UNUSED_WARNING (exp))
2267         return 0;
2268       /* Assignment to a cast usually results in a cast of a modify.
2269          Don't complain about that.  There can be an arbitrary number of
2270          casts before the modify, so we must loop until we find the first
2271          non-cast expression and then test to see if that is a modify.  */
2272       {
2273         tree tem = TREE_OPERAND (exp, 0);
2274
2275         while (TREE_CODE (tem) == CONVERT_EXPR || TREE_CODE (tem) == NOP_EXPR)
2276           tem = TREE_OPERAND (tem, 0);
2277
2278         if (TREE_CODE (tem) == MODIFY_EXPR || TREE_CODE (tem) == INIT_EXPR
2279             || TREE_CODE (tem) == CALL_EXPR)
2280           return 0;
2281       }
2282       goto maybe_warn;
2283
2284     case INDIRECT_REF:
2285       /* Don't warn about automatic dereferencing of references, since
2286          the user cannot control it.  */
2287       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
2288         return warn_if_unused_value (TREE_OPERAND (exp, 0));
2289       /* Fall through.  */
2290
2291     default:
2292       /* Referencing a volatile value is a side effect, so don't warn.  */
2293       if ((DECL_P (exp)
2294            || TREE_CODE_CLASS (TREE_CODE (exp)) == 'r')
2295           && TREE_THIS_VOLATILE (exp))
2296         return 0;
2297
2298       /* If this is an expression which has no operands, there is no value
2299          to be unused.  There are no such language-independent codes,
2300          but front ends may define such.  */
2301       if (TREE_CODE_CLASS (TREE_CODE (exp)) == 'e'
2302           && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0)
2303         return 0;
2304
2305     maybe_warn:
2306       /* If this is an expression with side effects, don't warn.  */
2307       if (TREE_SIDE_EFFECTS (exp))
2308         return 0;
2309
2310       warning ("%Hvalue computed is not used", &emit_locus);
2311       return 1;
2312     }
2313 }
2314
2315 /* Clear out the memory of the last expression evaluated.  */
2316
2317 void
2318 clear_last_expr (void)
2319 {
2320   last_expr_type = NULL_TREE;
2321   last_expr_value = NULL_RTX;
2322   last_expr_alt_rtl = NULL_RTX;
2323 }
2324
2325 /* Begin a statement-expression, i.e., a series of statements which
2326    may return a value.  Return the RTL_EXPR for this statement expr.
2327    The caller must save that value and pass it to
2328    expand_end_stmt_expr.  If HAS_SCOPE is nonzero, temporaries created
2329    in the statement-expression are deallocated at the end of the
2330    expression.  */
2331
2332 tree
2333 expand_start_stmt_expr (int has_scope)
2334 {
2335   tree t;
2336
2337   /* Make the RTL_EXPR node temporary, not momentary,
2338      so that rtl_expr_chain doesn't become garbage.  */
2339   t = make_node (RTL_EXPR);
2340   do_pending_stack_adjust ();
2341   if (has_scope)
2342     start_sequence_for_rtl_expr (t);
2343   else
2344     start_sequence ();
2345   NO_DEFER_POP;
2346   expr_stmts_for_value++;
2347   return t;
2348 }
2349
2350 /* Restore the previous state at the end of a statement that returns a value.
2351    Returns a tree node representing the statement's value and the
2352    insns to compute the value.
2353
2354    The nodes of that expression have been freed by now, so we cannot use them.
2355    But we don't want to do that anyway; the expression has already been
2356    evaluated and now we just want to use the value.  So generate a RTL_EXPR
2357    with the proper type and RTL value.
2358
2359    If the last substatement was not an expression,
2360    return something with type `void'.  */
2361
2362 tree
2363 expand_end_stmt_expr (tree t)
2364 {
2365   OK_DEFER_POP;
2366
2367   if (! last_expr_value || ! last_expr_type)
2368     {
2369       last_expr_value = const0_rtx;
2370       last_expr_alt_rtl = NULL_RTX;
2371       last_expr_type = void_type_node;
2372     }
2373   else if (GET_CODE (last_expr_value) != REG && ! CONSTANT_P (last_expr_value))
2374     /* Remove any possible QUEUED.  */
2375     last_expr_value = protect_from_queue (last_expr_value, 0);
2376
2377   emit_queue ();
2378
2379   TREE_TYPE (t) = last_expr_type;
2380   RTL_EXPR_RTL (t) = last_expr_value;
2381   RTL_EXPR_ALT_RTL (t) = last_expr_alt_rtl;
2382   RTL_EXPR_SEQUENCE (t) = get_insns ();
2383
2384   rtl_expr_chain = tree_cons (NULL_TREE, t, rtl_expr_chain);
2385
2386   end_sequence ();
2387
2388   /* Don't consider deleting this expr or containing exprs at tree level.  */
2389   TREE_SIDE_EFFECTS (t) = 1;
2390   /* Propagate volatility of the actual RTL expr.  */
2391   TREE_THIS_VOLATILE (t) = volatile_refs_p (last_expr_value);
2392
2393   clear_last_expr ();
2394   expr_stmts_for_value--;
2395
2396   return t;
2397 }
2398 \f
2399 /* Generate RTL for the start of an if-then.  COND is the expression
2400    whose truth should be tested.
2401
2402    If EXITFLAG is nonzero, this conditional is visible to
2403    `exit_something'.  */
2404
2405 void
2406 expand_start_cond (tree cond, int exitflag)
2407 {
2408   struct nesting *thiscond = ALLOC_NESTING ();
2409
2410   /* Make an entry on cond_stack for the cond we are entering.  */
2411
2412   thiscond->desc = COND_NESTING;
2413   thiscond->next = cond_stack;
2414   thiscond->all = nesting_stack;
2415   thiscond->depth = ++nesting_depth;
2416   thiscond->data.cond.next_label = gen_label_rtx ();
2417   /* Before we encounter an `else', we don't need a separate exit label
2418      unless there are supposed to be exit statements
2419      to exit this conditional.  */
2420   thiscond->exit_label = exitflag ? gen_label_rtx () : 0;
2421   thiscond->data.cond.endif_label = thiscond->exit_label;
2422   cond_stack = thiscond;
2423   nesting_stack = thiscond;
2424
2425   do_jump (cond, thiscond->data.cond.next_label, NULL_RTX);
2426 }
2427
2428 /* Generate RTL between then-clause and the elseif-clause
2429    of an if-then-elseif-....  */
2430
2431 void
2432 expand_start_elseif (tree cond)
2433 {
2434   if (cond_stack->data.cond.endif_label == 0)
2435     cond_stack->data.cond.endif_label = gen_label_rtx ();
2436   emit_jump (cond_stack->data.cond.endif_label);
2437   emit_label (cond_stack->data.cond.next_label);
2438   cond_stack->data.cond.next_label = gen_label_rtx ();
2439   do_jump (cond, cond_stack->data.cond.next_label, NULL_RTX);
2440 }
2441
2442 /* Generate RTL between the then-clause and the else-clause
2443    of an if-then-else.  */
2444
2445 void
2446 expand_start_else (void)
2447 {
2448   if (cond_stack->data.cond.endif_label == 0)
2449     cond_stack->data.cond.endif_label = gen_label_rtx ();
2450
2451   emit_jump (cond_stack->data.cond.endif_label);
2452   emit_label (cond_stack->data.cond.next_label);
2453   cond_stack->data.cond.next_label = 0;  /* No more _else or _elseif calls.  */
2454 }
2455
2456 /* After calling expand_start_else, turn this "else" into an "else if"
2457    by providing another condition.  */
2458
2459 void
2460 expand_elseif (tree cond)
2461 {
2462   cond_stack->data.cond.next_label = gen_label_rtx ();
2463   do_jump (cond, cond_stack->data.cond.next_label, NULL_RTX);
2464 }
2465
2466 /* Generate RTL for the end of an if-then.
2467    Pop the record for it off of cond_stack.  */
2468
2469 void
2470 expand_end_cond (void)
2471 {
2472   struct nesting *thiscond = cond_stack;
2473
2474   do_pending_stack_adjust ();
2475   if (thiscond->data.cond.next_label)
2476     emit_label (thiscond->data.cond.next_label);
2477   if (thiscond->data.cond.endif_label)
2478     emit_label (thiscond->data.cond.endif_label);
2479
2480   POPSTACK (cond_stack);
2481   clear_last_expr ();
2482 }
2483 \f
2484 /* Generate RTL for the start of a loop.  EXIT_FLAG is nonzero if this
2485    loop should be exited by `exit_something'.  This is a loop for which
2486    `expand_continue' will jump to the top of the loop.
2487
2488    Make an entry on loop_stack to record the labels associated with
2489    this loop.  */
2490
2491 struct nesting *
2492 expand_start_loop (int exit_flag)
2493 {
2494   struct nesting *thisloop = ALLOC_NESTING ();
2495
2496   /* Make an entry on loop_stack for the loop we are entering.  */
2497
2498   thisloop->desc = LOOP_NESTING;
2499   thisloop->next = loop_stack;
2500   thisloop->all = nesting_stack;
2501   thisloop->depth = ++nesting_depth;
2502   thisloop->data.loop.start_label = gen_label_rtx ();
2503   thisloop->data.loop.end_label = gen_label_rtx ();
2504   thisloop->data.loop.continue_label = thisloop->data.loop.start_label;
2505   thisloop->exit_label = exit_flag ? thisloop->data.loop.end_label : 0;
2506   loop_stack = thisloop;
2507   nesting_stack = thisloop;
2508
2509   do_pending_stack_adjust ();
2510   emit_queue ();
2511   emit_note (NOTE_INSN_LOOP_BEG);
2512   emit_label (thisloop->data.loop.start_label);
2513
2514   return thisloop;
2515 }
2516
2517 /* Like expand_start_loop but for a loop where the continuation point
2518    (for expand_continue_loop) will be specified explicitly.  */
2519
2520 struct nesting *
2521 expand_start_loop_continue_elsewhere (int exit_flag)
2522 {
2523   struct nesting *thisloop = expand_start_loop (exit_flag);
2524   loop_stack->data.loop.continue_label = gen_label_rtx ();
2525   return thisloop;
2526 }
2527
2528 /* Begin a null, aka do { } while (0) "loop".  But since the contents
2529    of said loop can still contain a break, we must frob the loop nest.  */
2530
2531 struct nesting *
2532 expand_start_null_loop (void)
2533 {
2534   struct nesting *thisloop = ALLOC_NESTING ();
2535
2536   /* Make an entry on loop_stack for the loop we are entering.  */
2537
2538   thisloop->desc = LOOP_NESTING;
2539   thisloop->next = loop_stack;
2540   thisloop->all = nesting_stack;
2541   thisloop->depth = ++nesting_depth;
2542   thisloop->data.loop.start_label = emit_note (NOTE_INSN_DELETED);
2543   thisloop->data.loop.end_label = gen_label_rtx ();
2544   thisloop->data.loop.continue_label = thisloop->data.loop.end_label;
2545   thisloop->exit_label = thisloop->data.loop.end_label;
2546   loop_stack = thisloop;
2547   nesting_stack = thisloop;
2548
2549   return thisloop;
2550 }
2551
2552 /* Specify the continuation point for a loop started with
2553    expand_start_loop_continue_elsewhere.
2554    Use this at the point in the code to which a continue statement
2555    should jump.  */
2556
2557 void
2558 expand_loop_continue_here (void)
2559 {
2560   do_pending_stack_adjust ();
2561   emit_note (NOTE_INSN_LOOP_CONT);
2562   emit_label (loop_stack->data.loop.continue_label);
2563 }
2564
2565 /* Finish a loop.  Generate a jump back to the top and the loop-exit label.
2566    Pop the block off of loop_stack.  */
2567
2568 void
2569 expand_end_loop (void)
2570 {
2571   rtx start_label = loop_stack->data.loop.start_label;
2572   rtx etc_note;
2573   int eh_regions, debug_blocks;
2574   bool empty_test;
2575
2576   /* Mark the continue-point at the top of the loop if none elsewhere.  */
2577   if (start_label == loop_stack->data.loop.continue_label)
2578     emit_note_before (NOTE_INSN_LOOP_CONT, start_label);
2579
2580   do_pending_stack_adjust ();
2581
2582   /* If the loop starts with a loop exit, roll that to the end where
2583      it will optimize together with the jump back.
2584
2585      If the loop presently looks like this (in pseudo-C):
2586
2587         LOOP_BEG
2588         start_label:
2589           if (test) goto end_label;
2590         LOOP_END_TOP_COND
2591           body;
2592           goto start_label;
2593         end_label:
2594
2595      transform it to look like:
2596
2597         LOOP_BEG
2598           goto start_label;
2599         top_label:
2600           body;
2601         start_label:
2602           if (test) goto end_label;
2603           goto top_label;
2604         end_label:
2605
2606      We rely on the presence of NOTE_INSN_LOOP_END_TOP_COND to mark
2607      the end of the entry conditional.  Without this, our lexical scan
2608      can't tell the difference between an entry conditional and a
2609      body conditional that exits the loop.  Mistaking the two means
2610      that we can misplace the NOTE_INSN_LOOP_CONT note, which can
2611      screw up loop unrolling.
2612
2613      Things will be oh so much better when loop optimization is done
2614      off of a proper control flow graph...  */
2615
2616   /* Scan insns from the top of the loop looking for the END_TOP_COND note.  */
2617
2618   empty_test = true;
2619   eh_regions = debug_blocks = 0;
2620   for (etc_note = start_label; etc_note ; etc_note = NEXT_INSN (etc_note))
2621     if (GET_CODE (etc_note) == NOTE)
2622       {
2623         if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_LOOP_END_TOP_COND)
2624           break;
2625
2626         /* We must not walk into a nested loop.  */
2627         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_LOOP_BEG)
2628           {
2629             etc_note = NULL_RTX;
2630             break;
2631           }
2632
2633         /* At the same time, scan for EH region notes, as we don't want
2634            to scrog region nesting.  This shouldn't happen, but...  */
2635         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_EH_REGION_BEG)
2636           eh_regions++;
2637         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_EH_REGION_END)
2638           {
2639             if (--eh_regions < 0)
2640               /* We've come to the end of an EH region, but never saw the
2641                  beginning of that region.  That means that an EH region
2642                  begins before the top of the loop, and ends in the middle
2643                  of it.  The existence of such a situation violates a basic
2644                  assumption in this code, since that would imply that even
2645                  when EH_REGIONS is zero, we might move code out of an
2646                  exception region.  */
2647               abort ();
2648           }
2649
2650         /* Likewise for debug scopes.  In this case we'll either (1) move
2651            all of the notes if they are properly nested or (2) leave the
2652            notes alone and only rotate the loop at high optimization
2653            levels when we expect to scrog debug info.  */
2654         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_BLOCK_BEG)
2655           debug_blocks++;
2656         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_BLOCK_END)
2657           debug_blocks--;
2658       }
2659     else if (INSN_P (etc_note))
2660       empty_test = false;
2661
2662   if (etc_note
2663       && optimize
2664       && ! empty_test
2665       && eh_regions == 0
2666       && (debug_blocks == 0 || optimize >= 2)
2667       && NEXT_INSN (etc_note) != NULL_RTX
2668       && ! any_condjump_p (get_last_insn ()))
2669     {
2670       /* We found one.  Move everything from START to ETC to the end
2671          of the loop, and add a jump from the top of the loop.  */
2672       rtx top_label = gen_label_rtx ();
2673       rtx start_move = start_label;
2674
2675       /* If the start label is preceded by a NOTE_INSN_LOOP_CONT note,
2676          then we want to move this note also.  */
2677       if (GET_CODE (PREV_INSN (start_move)) == NOTE
2678           && NOTE_LINE_NUMBER (PREV_INSN (start_move)) == NOTE_INSN_LOOP_CONT)
2679         start_move = PREV_INSN (start_move);
2680
2681       emit_label_before (top_label, start_move);
2682
2683       /* Actually move the insns.  If the debug scopes are nested, we
2684          can move everything at once.  Otherwise we have to move them
2685          one by one and squeeze out the block notes.  */
2686       if (debug_blocks == 0)
2687         reorder_insns (start_move, etc_note, get_last_insn ());
2688       else
2689         {
2690           rtx insn, next_insn;
2691           for (insn = start_move; insn; insn = next_insn)
2692             {
2693               /* Figure out which insn comes after this one.  We have
2694                  to do this before we move INSN.  */
2695               next_insn = (insn == etc_note ? NULL : NEXT_INSN (insn));
2696
2697               if (GET_CODE (insn) == NOTE
2698                   && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2699                       || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
2700                 continue;
2701
2702               reorder_insns (insn, insn, get_last_insn ());
2703             }
2704         }
2705
2706       /* Add the jump from the top of the loop.  */
2707       emit_jump_insn_before (gen_jump (start_label), top_label);
2708       emit_barrier_before (top_label);
2709       start_label = top_label;
2710     }
2711
2712   emit_jump (start_label);
2713   emit_note (NOTE_INSN_LOOP_END);
2714   emit_label (loop_stack->data.loop.end_label);
2715
2716   POPSTACK (loop_stack);
2717
2718   clear_last_expr ();
2719 }
2720
2721 /* Finish a null loop, aka do { } while (0).  */
2722
2723 void
2724 expand_end_null_loop (void)
2725 {
2726   do_pending_stack_adjust ();
2727   emit_label (loop_stack->data.loop.end_label);
2728
2729   POPSTACK (loop_stack);
2730
2731   clear_last_expr ();
2732 }
2733
2734 /* Generate a jump to the current loop's continue-point.
2735    This is usually the top of the loop, but may be specified
2736    explicitly elsewhere.  If not currently inside a loop,
2737    return 0 and do nothing; caller will print an error message.  */
2738
2739 int
2740 expand_continue_loop (struct nesting *whichloop)
2741 {
2742   /* Emit information for branch prediction.  */
2743   rtx note;
2744
2745   if (flag_guess_branch_prob)
2746     {
2747       note = emit_note (NOTE_INSN_PREDICTION);
2748       NOTE_PREDICTION (note) = NOTE_PREDICT (PRED_CONTINUE, IS_TAKEN);
2749     }
2750   clear_last_expr ();
2751   if (whichloop == 0)
2752     whichloop = loop_stack;
2753   if (whichloop == 0)
2754     return 0;
2755   expand_goto_internal (NULL_TREE, whichloop->data.loop.continue_label,
2756                         NULL_RTX);
2757   return 1;
2758 }
2759
2760 /* Generate a jump to exit the current loop.  If not currently inside a loop,
2761    return 0 and do nothing; caller will print an error message.  */
2762
2763 int
2764 expand_exit_loop (struct nesting *whichloop)
2765 {
2766   clear_last_expr ();
2767   if (whichloop == 0)
2768     whichloop = loop_stack;
2769   if (whichloop == 0)
2770     return 0;
2771   expand_goto_internal (NULL_TREE, whichloop->data.loop.end_label, NULL_RTX);
2772   return 1;
2773 }
2774
2775 /* Generate a conditional jump to exit the current loop if COND
2776    evaluates to zero.  If not currently inside a loop,
2777    return 0 and do nothing; caller will print an error message.  */
2778
2779 int
2780 expand_exit_loop_if_false (struct nesting *whichloop, tree cond)
2781 {
2782   rtx label;
2783   clear_last_expr ();
2784
2785   if (whichloop == 0)
2786     whichloop = loop_stack;
2787   if (whichloop == 0)
2788     return 0;
2789
2790   if (integer_nonzerop (cond))
2791     return 1;
2792   if (integer_zerop (cond))
2793     return expand_exit_loop (whichloop);
2794
2795   /* Check if we definitely won't need a fixup.  */
2796   if (whichloop == nesting_stack)
2797     {
2798       jumpifnot (cond, whichloop->data.loop.end_label);
2799       return 1;
2800     }
2801
2802   /* In order to handle fixups, we actually create a conditional jump
2803      around an unconditional branch to exit the loop.  If fixups are
2804      necessary, they go before the unconditional branch.  */
2805
2806   label = gen_label_rtx ();
2807   jumpif (cond, label);
2808   expand_goto_internal (NULL_TREE, whichloop->data.loop.end_label,
2809                         NULL_RTX);
2810   emit_label (label);
2811
2812   return 1;
2813 }
2814
2815 /* Like expand_exit_loop_if_false except also emit a note marking
2816    the end of the conditional.  Should only be used immediately
2817    after expand_loop_start.  */
2818
2819 int
2820 expand_exit_loop_top_cond (struct nesting *whichloop, tree cond)
2821 {
2822   if (! expand_exit_loop_if_false (whichloop, cond))
2823     return 0;
2824
2825   emit_note (NOTE_INSN_LOOP_END_TOP_COND);
2826   return 1;
2827 }
2828
2829 /* Return nonzero if we should preserve sub-expressions as separate
2830    pseudos.  We never do so if we aren't optimizing.  We always do so
2831    if -fexpensive-optimizations.
2832
2833    Otherwise, we only do so if we are in the "early" part of a loop.  I.e.,
2834    the loop may still be a small one.  */
2835
2836 int
2837 preserve_subexpressions_p (void)
2838 {
2839   rtx insn;
2840
2841   if (flag_expensive_optimizations)
2842     return 1;
2843
2844   if (optimize == 0 || cfun == 0 || cfun->stmt == 0 || loop_stack == 0)
2845     return 0;
2846
2847   insn = get_last_insn_anywhere ();
2848
2849   return (insn
2850           && (INSN_UID (insn) - INSN_UID (loop_stack->data.loop.start_label)
2851               < n_non_fixed_regs * 3));
2852
2853 }
2854
2855 /* Generate a jump to exit the current loop, conditional, binding contour
2856    or case statement.  Not all such constructs are visible to this function,
2857    only those started with EXIT_FLAG nonzero.  Individual languages use
2858    the EXIT_FLAG parameter to control which kinds of constructs you can
2859    exit this way.
2860
2861    If not currently inside anything that can be exited,
2862    return 0 and do nothing; caller will print an error message.  */
2863
2864 int
2865 expand_exit_something (void)
2866 {
2867   struct nesting *n;
2868   clear_last_expr ();
2869   for (n = nesting_stack; n; n = n->all)
2870     if (n->exit_label != 0)
2871       {
2872         expand_goto_internal (NULL_TREE, n->exit_label, NULL_RTX);
2873         return 1;
2874       }
2875
2876   return 0;
2877 }
2878 \f
2879 /* Generate RTL to return from the current function, with no value.
2880    (That is, we do not do anything about returning any value.)  */
2881
2882 void
2883 expand_null_return (void)
2884 {
2885   rtx last_insn;
2886
2887   last_insn = get_last_insn ();
2888
2889   /* If this function was declared to return a value, but we
2890      didn't, clobber the return registers so that they are not
2891      propagated live to the rest of the function.  */
2892   clobber_return_register ();
2893
2894   expand_null_return_1 (last_insn);
2895 }
2896
2897 /* Generate RTL to return directly from the current function.
2898    (That is, we bypass any return value.)  */
2899
2900 void
2901 expand_naked_return (void)
2902 {
2903   rtx last_insn, end_label;
2904
2905   last_insn = get_last_insn ();
2906   end_label = naked_return_label;
2907
2908   clear_pending_stack_adjust ();
2909   do_pending_stack_adjust ();
2910   clear_last_expr ();
2911
2912   if (end_label == 0)
2913     end_label = naked_return_label = gen_label_rtx ();
2914   expand_goto_internal (NULL_TREE, end_label, last_insn);
2915 }
2916
2917 /* Try to guess whether the value of return means error code.  */
2918 static enum br_predictor
2919 return_prediction (rtx val)
2920 {
2921   /* Different heuristics for pointers and scalars.  */
2922   if (POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
2923     {
2924       /* NULL is usually not returned.  */
2925       if (val == const0_rtx)
2926         return PRED_NULL_RETURN;
2927     }
2928   else
2929     {
2930       /* Negative return values are often used to indicate
2931          errors.  */
2932       if (GET_CODE (val) == CONST_INT
2933           && INTVAL (val) < 0)
2934         return PRED_NEGATIVE_RETURN;
2935       /* Constant return values are also usually erors,
2936          zero/one often mean booleans so exclude them from the
2937          heuristics.  */
2938       if (CONSTANT_P (val)
2939           && (val != const0_rtx && val != const1_rtx))
2940         return PRED_CONST_RETURN;
2941     }
2942   return PRED_NO_PREDICTION;
2943 }
2944
2945
2946 /* If the current function returns values in the most significant part
2947    of a register, shift return value VAL appropriately.  The mode of
2948    the function's return type is known not to be BLKmode.  */
2949
2950 static rtx
2951 shift_return_value (rtx val)
2952 {
2953   tree type;
2954
2955   type = TREE_TYPE (DECL_RESULT (current_function_decl));
2956   if (targetm.calls.return_in_msb (type))
2957     {
2958       rtx target;
2959       HOST_WIDE_INT shift;
2960
2961       target = DECL_RTL (DECL_RESULT (current_function_decl));
2962       shift = (GET_MODE_BITSIZE (GET_MODE (target))
2963                - BITS_PER_UNIT * int_size_in_bytes (type));
2964       if (shift > 0)
2965         val = expand_binop (GET_MODE (target), ashl_optab,
2966                             gen_lowpart (GET_MODE (target), val),
2967                             GEN_INT (shift), target, 1, OPTAB_WIDEN);
2968     }
2969   return val;
2970 }
2971
2972
2973 /* Generate RTL to return from the current function, with value VAL.  */
2974
2975 static void
2976 expand_value_return (rtx val)
2977 {
2978   rtx last_insn;
2979   rtx return_reg;
2980   enum br_predictor pred;
2981
2982   if (flag_guess_branch_prob
2983       && (pred = return_prediction (val)) != PRED_NO_PREDICTION)
2984     {
2985       /* Emit information for branch prediction.  */
2986       rtx note;
2987
2988       note = emit_note (NOTE_INSN_PREDICTION);
2989
2990       NOTE_PREDICTION (note) = NOTE_PREDICT (pred, NOT_TAKEN);
2991
2992     }
2993
2994   last_insn = get_last_insn ();
2995   return_reg = DECL_RTL (DECL_RESULT (current_function_decl));
2996
2997   /* Copy the value to the return location
2998      unless it's already there.  */
2999
3000   if (return_reg != val)
3001     {
3002       tree type = TREE_TYPE (DECL_RESULT (current_function_decl));
3003       if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl)))
3004       {
3005         int unsignedp = TYPE_UNSIGNED (type);
3006         enum machine_mode old_mode
3007           = DECL_MODE (DECL_RESULT (current_function_decl));
3008         enum machine_mode mode
3009           = promote_mode (type, old_mode, &unsignedp, 1);
3010
3011         if (mode != old_mode)
3012           val = convert_modes (mode, old_mode, val, unsignedp);
3013       }
3014       if (GET_CODE (return_reg) == PARALLEL)
3015         emit_group_load (return_reg, val, type, int_size_in_bytes (type));
3016       else
3017         emit_move_insn (return_reg, val);
3018     }
3019
3020   expand_null_return_1 (last_insn);
3021 }
3022
3023 /* Output a return with no value.  If LAST_INSN is nonzero,
3024    pretend that the return takes place after LAST_INSN.  */
3025
3026 static void
3027 expand_null_return_1 (rtx last_insn)
3028 {
3029   rtx end_label = cleanup_label ? cleanup_label : return_label;
3030
3031   clear_pending_stack_adjust ();
3032   do_pending_stack_adjust ();
3033   clear_last_expr ();
3034
3035   if (end_label == 0)
3036      end_label = return_label = gen_label_rtx ();
3037   expand_goto_internal (NULL_TREE, end_label, last_insn);
3038 }
3039 \f
3040 /* Generate RTL to evaluate the expression RETVAL and return it
3041    from the current function.  */
3042
3043 void
3044 expand_return (tree retval)
3045 {
3046   /* If there are any cleanups to be performed, then they will
3047      be inserted following LAST_INSN.  It is desirable
3048      that the last_insn, for such purposes, should be the
3049      last insn before computing the return value.  Otherwise, cleanups
3050      which call functions can clobber the return value.  */
3051   /* ??? rms: I think that is erroneous, because in C++ it would
3052      run destructors on variables that might be used in the subsequent
3053      computation of the return value.  */
3054   rtx last_insn = 0;
3055   rtx result_rtl;
3056   rtx val = 0;
3057   tree retval_rhs;
3058
3059   /* If function wants no value, give it none.  */
3060   if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
3061     {
3062       expand_expr (retval, NULL_RTX, VOIDmode, 0);
3063       emit_queue ();
3064       expand_null_return ();
3065       return;
3066     }
3067
3068   if (retval == error_mark_node)
3069     {
3070       /* Treat this like a return of no value from a function that
3071          returns a value.  */
3072       expand_null_return ();
3073       return;
3074     }
3075   else if (TREE_CODE (retval) == RESULT_DECL)
3076     retval_rhs = retval;
3077   else if ((TREE_CODE (retval) == MODIFY_EXPR || TREE_CODE (retval) == INIT_EXPR)
3078            && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
3079     retval_rhs = TREE_OPERAND (retval, 1);
3080   else if (VOID_TYPE_P (TREE_TYPE (retval)))
3081     /* Recognize tail-recursive call to void function.  */
3082     retval_rhs = retval;
3083   else
3084     retval_rhs = NULL_TREE;
3085
3086   last_insn = get_last_insn ();
3087
3088   /* Distribute return down conditional expr if either of the sides
3089      may involve tail recursion (see test below).  This enhances the number
3090      of tail recursions we see.  Don't do this always since it can produce
3091      sub-optimal code in some cases and we distribute assignments into
3092      conditional expressions when it would help.  */
3093
3094   if (optimize && retval_rhs != 0
3095       && frame_offset == 0
3096       && TREE_CODE (retval_rhs) == COND_EXPR
3097       && (TREE_CODE (TREE_OPERAND (retval_rhs, 1)) == CALL_EXPR
3098           || TREE_CODE (TREE_OPERAND (retval_rhs, 2)) == CALL_EXPR))
3099     {
3100       rtx label = gen_label_rtx ();
3101       tree expr;
3102
3103       do_jump (TREE_OPERAND (retval_rhs, 0), label, NULL_RTX);
3104       start_cleanup_deferral ();
3105       expr = build (MODIFY_EXPR, TREE_TYPE (TREE_TYPE (current_function_decl)),
3106                     DECL_RESULT (current_function_decl),
3107                     TREE_OPERAND (retval_rhs, 1));
3108       TREE_SIDE_EFFECTS (expr) = 1;
3109       expand_return (expr);
3110       emit_label (label);
3111
3112       expr = build (MODIFY_EXPR, TREE_TYPE (TREE_TYPE (current_function_decl)),
3113                     DECL_RESULT (current_function_decl),
3114                     TREE_OPERAND (retval_rhs, 2));
3115       TREE_SIDE_EFFECTS (expr) = 1;
3116       expand_return (expr);
3117       end_cleanup_deferral ();
3118       return;
3119     }
3120
3121   result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
3122
3123   /* If the result is an aggregate that is being returned in one (or more)
3124      registers, load the registers here.  The compiler currently can't handle
3125      copying a BLKmode value into registers.  We could put this code in a
3126      more general area (for use by everyone instead of just function
3127      call/return), but until this feature is generally usable it is kept here
3128      (and in expand_call).  The value must go into a pseudo in case there
3129      are cleanups that will clobber the real return register.  */
3130
3131   if (retval_rhs != 0
3132       && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
3133       && GET_CODE (result_rtl) == REG)
3134     {
3135       int i;
3136       unsigned HOST_WIDE_INT bitpos, xbitpos;
3137       unsigned HOST_WIDE_INT padding_correction = 0;
3138       unsigned HOST_WIDE_INT bytes
3139         = int_size_in_bytes (TREE_TYPE (retval_rhs));
3140       int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
3141       unsigned int bitsize
3142         = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
3143       rtx *result_pseudos = alloca (sizeof (rtx) * n_regs);
3144       rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
3145       rtx result_val = expand_expr (retval_rhs, NULL_RTX, VOIDmode, 0);
3146       enum machine_mode tmpmode, result_reg_mode;
3147
3148       if (bytes == 0)
3149         {
3150           expand_null_return ();
3151           return;
3152         }
3153
3154       /* If the structure doesn't take up a whole number of words, see
3155          whether the register value should be padded on the left or on
3156          the right.  Set PADDING_CORRECTION to the number of padding
3157          bits needed on the left side.
3158
3159          In most ABIs, the structure will be returned at the least end of
3160          the register, which translates to right padding on little-endian
3161          targets and left padding on big-endian targets.  The opposite
3162          holds if the structure is returned at the most significant
3163          end of the register.  */
3164       if (bytes % UNITS_PER_WORD != 0
3165           && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
3166               ? !BYTES_BIG_ENDIAN
3167               : BYTES_BIG_ENDIAN))
3168         padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
3169                                                * BITS_PER_UNIT));
3170
3171       /* Copy the structure BITSIZE bits at a time.  */
3172       for (bitpos = 0, xbitpos = padding_correction;
3173            bitpos < bytes * BITS_PER_UNIT;
3174            bitpos += bitsize, xbitpos += bitsize)
3175         {
3176           /* We need a new destination pseudo each time xbitpos is
3177              on a word boundary and when xbitpos == padding_correction
3178              (the first time through).  */
3179           if (xbitpos % BITS_PER_WORD == 0
3180               || xbitpos == padding_correction)
3181             {
3182               /* Generate an appropriate register.  */
3183               dst = gen_reg_rtx (word_mode);
3184               result_pseudos[xbitpos / BITS_PER_WORD] = dst;
3185
3186               /* Clear the destination before we move anything into it.  */
3187               emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
3188             }
3189
3190           /* We need a new source operand each time bitpos is on a word
3191              boundary.  */
3192           if (bitpos % BITS_PER_WORD == 0)
3193             src = operand_subword_force (result_val,
3194                                          bitpos / BITS_PER_WORD,
3195                                          BLKmode);
3196
3197           /* Use bitpos for the source extraction (left justified) and
3198              xbitpos for the destination store (right justified).  */
3199           store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
3200                            extract_bit_field (src, bitsize,
3201                                               bitpos % BITS_PER_WORD, 1,
3202                                               NULL_RTX, word_mode, word_mode,
3203                                               BITS_PER_WORD),
3204                            BITS_PER_WORD);
3205         }
3206
3207       tmpmode = GET_MODE (result_rtl);
3208       if (tmpmode == BLKmode)
3209         {
3210           /* Find the smallest integer mode large enough to hold the
3211              entire structure and use that mode instead of BLKmode
3212              on the USE insn for the return register.  */
3213           for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
3214                tmpmode != VOIDmode;
3215                tmpmode = GET_MODE_WIDER_MODE (tmpmode))
3216             /* Have we found a large enough mode?  */
3217             if (GET_MODE_SIZE (tmpmode) >= bytes)
3218               break;
3219
3220           /* No suitable mode found.  */
3221           if (tmpmode == VOIDmode)
3222             abort ();
3223
3224           PUT_MODE (result_rtl, tmpmode);
3225         }
3226
3227       if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
3228         result_reg_mode = word_mode;
3229       else
3230         result_reg_mode = tmpmode;
3231       result_reg = gen_reg_rtx (result_reg_mode);
3232
3233       emit_queue ();
3234       for (i = 0; i < n_regs; i++)
3235         emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
3236                         result_pseudos[i]);
3237
3238       if (tmpmode != result_reg_mode)
3239         result_reg = gen_lowpart (tmpmode, result_reg);
3240
3241       expand_value_return (result_reg);
3242     }
3243   else if (retval_rhs != 0
3244            && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
3245            && (GET_CODE (result_rtl) == REG
3246                || (GET_CODE (result_rtl) == PARALLEL)))
3247     {
3248       /* Calculate the return value into a temporary (usually a pseudo
3249          reg).  */
3250       tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
3251       tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
3252
3253       val = assign_temp (nt, 0, 0, 1);
3254       val = expand_expr (retval_rhs, val, GET_MODE (val), 0);
3255       val = force_not_mem (val);
3256       emit_queue ();
3257       /* Return the calculated value, doing cleanups first.  */
3258       expand_value_return (shift_return_value (val));
3259     }
3260   else
3261     {
3262       /* No cleanups or no hard reg used;
3263          calculate value into hard return reg.  */
3264       expand_expr (retval, const0_rtx, VOIDmode, 0);
3265       emit_queue ();
3266       expand_value_return (result_rtl);
3267     }
3268 }
3269 \f
3270 /* Attempt to optimize a potential tail recursion call into a goto.
3271    ARGUMENTS are the arguments to a CALL_EXPR; LAST_INSN indicates
3272    where to place the jump to the tail recursion label.
3273
3274    Return TRUE if the call was optimized into a goto.  */
3275
3276 int
3277 optimize_tail_recursion (tree arguments, rtx last_insn)
3278 {
3279   /* Finish checking validity, and if valid emit code to set the
3280      argument variables for the new call.  */
3281   if (tail_recursion_args (arguments, DECL_ARGUMENTS (current_function_decl)))
3282     {
3283       if (tail_recursion_label == 0)
3284         {
3285           tail_recursion_label = gen_label_rtx ();
3286           emit_label_after (tail_recursion_label,
3287                             tail_recursion_reentry);
3288         }
3289       emit_queue ();
3290       expand_goto_internal (NULL_TREE, tail_recursion_label, last_insn);
3291       emit_barrier ();
3292       return 1;
3293     }
3294   return 0;
3295 }
3296
3297 /* Emit code to alter this function's formal parms for a tail-recursive call.
3298    ACTUALS is a list of actual parameter expressions (chain of TREE_LISTs).
3299    FORMALS is the chain of decls of formals.
3300    Return 1 if this can be done;
3301    otherwise return 0 and do not emit any code.  */
3302
3303 static int
3304 tail_recursion_args (tree actuals, tree formals)
3305 {
3306   tree a = actuals, f = formals;
3307   int i;
3308   rtx *argvec;
3309
3310   /* Check that number and types of actuals are compatible
3311      with the formals.  This is not always true in valid C code.
3312      Also check that no formal needs to be addressable
3313      and that all formals are scalars.  */
3314
3315   /* Also count the args.  */
3316
3317   for (a = actuals, f = formals, i = 0; a && f; a = TREE_CHAIN (a), f = TREE_CHAIN (f), i++)
3318     {
3319       if (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_VALUE (a)))
3320           != TYPE_MAIN_VARIANT (TREE_TYPE (f)))
3321         return 0;
3322       if (GET_CODE (DECL_RTL (f)) != REG || DECL_MODE (f) == BLKmode)
3323         return 0;
3324     }
3325   if (a != 0 || f != 0)
3326     return 0;
3327
3328   /* Compute all the actuals.  */
3329
3330   argvec = alloca (i * sizeof (rtx));
3331
3332   for (a = actuals, i = 0; a; a = TREE_CHAIN (a), i++)
3333     argvec[i] = expand_expr (TREE_VALUE (a), NULL_RTX, VOIDmode, 0);
3334
3335   /* Find which actual values refer to current values of previous formals.
3336      Copy each of them now, before any formal is changed.  */
3337
3338   for (a = actuals, i = 0; a; a = TREE_CHAIN (a), i++)
3339     {
3340       int copy = 0;
3341       int j;
3342       for (f = formals, j = 0; j < i; f = TREE_CHAIN (f), j++)
3343         if (reg_mentioned_p (DECL_RTL (f), argvec[i]))
3344           {
3345             copy = 1;
3346             break;
3347           }
3348       if (copy)
3349         argvec[i] = copy_to_reg (argvec[i]);
3350     }
3351
3352   /* Store the values of the actuals into the formals.  */
3353
3354   for (f = formals, a = actuals, i = 0; f;
3355        f = TREE_CHAIN (f), a = TREE_CHAIN (a), i++)
3356     {
3357       if (GET_MODE (DECL_RTL (f)) == GET_MODE (argvec[i]))
3358         emit_move_insn (DECL_RTL (f), argvec[i]);
3359       else
3360         {
3361           rtx tmp = argvec[i];
3362           int unsignedp = TYPE_UNSIGNED (TREE_TYPE (TREE_VALUE (a)));
3363           promote_mode(TREE_TYPE (TREE_VALUE (a)), GET_MODE (tmp),
3364                        &unsignedp, 0);
3365           if (DECL_MODE (f) != GET_MODE (DECL_RTL (f)))
3366             {
3367               tmp = gen_reg_rtx (DECL_MODE (f));
3368               convert_move (tmp, argvec[i], unsignedp);
3369             }
3370           convert_move (DECL_RTL (f), tmp, unsignedp);
3371         }
3372     }
3373
3374   free_temp_slots ();
3375   return 1;
3376 }
3377 \f
3378 /* Generate the RTL code for entering a binding contour.
3379    The variables are declared one by one, by calls to `expand_decl'.
3380
3381    FLAGS is a bitwise or of the following flags:
3382
3383      1 - Nonzero if this construct should be visible to
3384          `exit_something'.
3385
3386      2 - Nonzero if this contour does not require a
3387          NOTE_INSN_BLOCK_BEG note.  Virtually all calls from
3388          language-independent code should set this flag because they
3389          will not create corresponding BLOCK nodes.  (There should be
3390          a one-to-one correspondence between NOTE_INSN_BLOCK_BEG notes
3391          and BLOCKs.)  If this flag is set, MARK_ENDS should be zero
3392          when expand_end_bindings is called.
3393
3394     If we are creating a NOTE_INSN_BLOCK_BEG note, a BLOCK may
3395     optionally be supplied.  If so, it becomes the NOTE_BLOCK for the
3396     note.  */
3397
3398 void
3399 expand_start_bindings_and_block (int flags, tree block)
3400 {
3401   struct nesting *thisblock = ALLOC_NESTING ();
3402   rtx note;
3403   int exit_flag = ((flags & 1) != 0);
3404   int block_flag = ((flags & 2) == 0);
3405
3406   /* If a BLOCK is supplied, then the caller should be requesting a
3407      NOTE_INSN_BLOCK_BEG note.  */
3408   if (!block_flag && block)
3409     abort ();
3410
3411   /* Create a note to mark the beginning of the block.  */
3412   if (block_flag)
3413     {
3414       note = emit_note (NOTE_INSN_BLOCK_BEG);
3415       NOTE_BLOCK (note) = block;
3416     }
3417   else
3418     note = emit_note (NOTE_INSN_DELETED);
3419
3420   /* Make an entry on block_stack for the block we are entering.  */
3421
3422   thisblock->desc = BLOCK_NESTING;
3423   thisblock->next = block_stack;
3424   thisblock->all = nesting_stack;
3425   thisblock->depth = ++nesting_depth;
3426   thisblock->data.block.stack_level = 0;
3427   thisblock->data.block.cleanups = 0;
3428   thisblock->data.block.exception_region = 0;
3429   thisblock->data.block.block_target_temp_slot_level = target_temp_slot_level;
3430
3431   thisblock->data.block.conditional_code = 0;
3432   thisblock->data.block.last_unconditional_cleanup = note;
3433   /* When we insert instructions after the last unconditional cleanup,
3434      we don't adjust last_insn.  That means that a later add_insn will
3435      clobber the instructions we've just added.  The easiest way to
3436      fix this is to just insert another instruction here, so that the
3437      instructions inserted after the last unconditional cleanup are
3438      never the last instruction.  */
3439   emit_note (NOTE_INSN_DELETED);
3440
3441   if (block_stack
3442       && !(block_stack->data.block.cleanups == NULL_TREE
3443            && block_stack->data.block.outer_cleanups == NULL_TREE))
3444     thisblock->data.block.outer_cleanups
3445       = tree_cons (NULL_TREE, block_stack->data.block.cleanups,
3446                    block_stack->data.block.outer_cleanups);
3447   else
3448     thisblock->data.block.outer_cleanups = 0;
3449   thisblock->data.block.label_chain = 0;
3450   thisblock->data.block.innermost_stack_block = stack_block_stack;
3451   thisblock->data.block.first_insn = note;
3452   thisblock->data.block.block_start_count = ++current_block_start_count;
3453   thisblock->exit_label = exit_flag ? gen_label_rtx () : 0;
3454   block_stack = thisblock;
3455   nesting_stack = thisblock;
3456
3457   /* Make a new level for allocating stack slots.  */
3458   push_temp_slots ();
3459 }
3460
3461 /* Specify the scope of temporaries created by TARGET_EXPRs.  Similar
3462    to CLEANUP_POINT_EXPR, but handles cases when a series of calls to
3463    expand_expr are made.  After we end the region, we know that all
3464    space for all temporaries that were created by TARGET_EXPRs will be
3465    destroyed and their space freed for reuse.  */
3466
3467 void
3468 expand_start_target_temps (void)
3469 {
3470   /* This is so that even if the result is preserved, the space
3471      allocated will be freed, as we know that it is no longer in use.  */
3472   push_temp_slots ();
3473
3474   /* Start a new binding layer that will keep track of all cleanup
3475      actions to be performed.  */
3476   expand_start_bindings (2);
3477
3478   target_temp_slot_level = temp_slot_level;
3479 }
3480
3481 void
3482 expand_end_target_temps (void)
3483 {
3484   expand_end_bindings (NULL_TREE, 0, 0);
3485
3486   /* This is so that even if the result is preserved, the space
3487      allocated will be freed, as we know that it is no longer in use.  */
3488   pop_temp_slots ();
3489 }
3490
3491 /* Given a pointer to a BLOCK node return nonzero if (and only if) the node
3492    in question represents the outermost pair of curly braces (i.e. the "body
3493    block") of a function or method.
3494
3495    For any BLOCK node representing a "body block" of a function or method, the
3496    BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which
3497    represents the outermost (function) scope for the function or method (i.e.
3498    the one which includes the formal parameters).  The BLOCK_SUPERCONTEXT of
3499    *that* node in turn will point to the relevant FUNCTION_DECL node.  */
3500
3501 int
3502 is_body_block (tree stmt)
3503 {
3504   if (lang_hooks.no_body_blocks)
3505     return 0;
3506
3507   if (TREE_CODE (stmt) == BLOCK)
3508     {
3509       tree parent = BLOCK_SUPERCONTEXT (stmt);
3510
3511       if (parent && TREE_CODE (parent) == BLOCK)
3512         {
3513           tree grandparent = BLOCK_SUPERCONTEXT (parent);
3514
3515           if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL)
3516             return 1;
3517         }
3518     }
3519
3520   return 0;
3521 }
3522
3523 /* True if we are currently emitting insns in an area of output code
3524    that is controlled by a conditional expression.  This is used by
3525    the cleanup handling code to generate conditional cleanup actions.  */
3526
3527 int
3528 conditional_context (void)
3529 {
3530   return block_stack && block_stack->data.block.conditional_code;
3531 }
3532
3533 /* Return an opaque pointer to the current nesting level, so frontend code
3534    can check its own sanity.  */
3535
3536 struct nesting *
3537 current_nesting_level (void)
3538 {
3539   return cfun ? block_stack : 0;
3540 }
3541
3542 /* Emit a handler label for a nonlocal goto handler.
3543    Also emit code to store the handler label in SLOT before BEFORE_INSN.  */
3544
3545 static rtx
3546 expand_nl_handler_label (rtx slot, rtx before_insn)
3547 {
3548   rtx insns;
3549   rtx handler_label = gen_label_rtx ();
3550
3551   /* Don't let cleanup_cfg delete the handler.  */
3552   LABEL_PRESERVE_P (handler_label) = 1;
3553
3554   start_sequence ();
3555   emit_move_insn (slot, gen_rtx_LABEL_REF (Pmode, handler_label));
3556   insns = get_insns ();
3557   end_sequence ();
3558   emit_insn_before (insns, before_insn);
3559
3560   emit_label (handler_label);
3561
3562   return handler_label;
3563 }
3564
3565 /* Emit code to restore vital registers at the beginning of a nonlocal goto
3566    handler.  */
3567 static void
3568 expand_nl_goto_receiver (void)
3569 {
3570     /* Clobber the FP when we get here, so we have to make sure it's
3571      marked as used by this function.  */
3572   emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
3573
3574   /* Mark the static chain as clobbered here so life information
3575      doesn't get messed up for it.  */
3576   emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx));
3577
3578 #ifdef HAVE_nonlocal_goto
3579   if (! HAVE_nonlocal_goto)
3580 #endif
3581     /* First adjust our frame pointer to its actual value.  It was
3582        previously set to the start of the virtual area corresponding to
3583        the stacked variables when we branched here and now needs to be
3584        adjusted to the actual hardware fp value.
3585
3586        Assignments are to virtual registers are converted by
3587        instantiate_virtual_regs into the corresponding assignment
3588        to the underlying register (fp in this case) that makes
3589        the original assignment true.
3590        So the following insn will actually be
3591        decrementing fp by STARTING_FRAME_OFFSET.  */
3592     emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
3593
3594 #if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3595   if (fixed_regs[ARG_POINTER_REGNUM])
3596     {
3597 #ifdef ELIMINABLE_REGS
3598       /* If the argument pointer can be eliminated in favor of the
3599          frame pointer, we don't need to restore it.  We assume here
3600          that if such an elimination is present, it can always be used.
3601          This is the case on all known machines; if we don't make this
3602          assumption, we do unnecessary saving on many machines.  */
3603       static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
3604       size_t i;
3605
3606       for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
3607         if (elim_regs[i].from == ARG_POINTER_REGNUM
3608             && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
3609           break;
3610
3611       if (i == ARRAY_SIZE (elim_regs))
3612 #endif
3613         {
3614           /* Now restore our arg pointer from the address at which it
3615              was saved in our stack frame.  */
3616           emit_move_insn (virtual_incoming_args_rtx,
3617                           copy_to_reg (get_arg_pointer_save_area (cfun)));
3618         }
3619     }
3620 #endif
3621
3622 #ifdef HAVE_nonlocal_goto_receiver
3623   if (HAVE_nonlocal_goto_receiver)
3624     emit_insn (gen_nonlocal_goto_receiver ());
3625 #endif
3626
3627   /* @@@ This is a kludge.  Not all machine descriptions define a blockage
3628      insn, but we must not allow the code we just generated to be reordered
3629      by scheduling.  Specifically, the update of the frame pointer must
3630      happen immediately, not later.  So emit an ASM_INPUT to act as blockage
3631      insn.  */
3632   emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
3633 }
3634
3635 /* Make handlers for nonlocal gotos taking place in the function calls in
3636    block THISBLOCK.  */
3637
3638 static void
3639 expand_nl_goto_receivers (struct nesting *thisblock)
3640 {
3641   tree link;
3642   rtx afterward = gen_label_rtx ();
3643   rtx insns, slot;
3644   rtx label_list;
3645   int any_invalid;
3646
3647   /* Record the handler address in the stack slot for that purpose,
3648      during this block, saving and restoring the outer value.  */
3649   if (thisblock->next != 0)
3650     for (slot = nonlocal_goto_handler_slots; slot; slot = XEXP (slot, 1))
3651       {
3652         rtx save_receiver = gen_reg_rtx (Pmode);
3653         emit_move_insn (XEXP (slot, 0), save_receiver);
3654
3655         start_sequence ();
3656         emit_move_insn (save_receiver, XEXP (slot, 0));
3657         insns = get_insns ();
3658         end_sequence ();
3659         emit_insn_before (insns, thisblock->data.block.first_insn);
3660       }
3661
3662   /* Jump around the handlers; they run only when specially invoked.  */
3663   emit_jump (afterward);
3664
3665   /* Make a separate handler for each label.  */
3666   link = nonlocal_labels;
3667   slot = nonlocal_goto_handler_slots;
3668   label_list = NULL_RTX;
3669   for (; link; link = TREE_CHAIN (link), slot = XEXP (slot, 1))
3670     /* Skip any labels we shouldn't be able to jump to from here,
3671        we generate one special handler for all of them below which just calls
3672        abort.  */
3673     if (! DECL_TOO_LATE (TREE_VALUE (link)))
3674       {
3675         rtx lab;
3676         lab = expand_nl_handler_label (XEXP (slot, 0),
3677                                        thisblock->data.block.first_insn);
3678         label_list = gen_rtx_EXPR_LIST (VOIDmode, lab, label_list);
3679
3680         expand_nl_goto_receiver ();
3681
3682         /* Jump to the "real" nonlocal label.  */
3683         expand_goto (TREE_VALUE (link));
3684       }
3685
3686   /* A second pass over all nonlocal labels; this time we handle those
3687      we should not be able to jump to at this point.  */
3688   link = nonlocal_labels;
3689   slot = nonlocal_goto_handler_slots;
3690   any_invalid = 0;
3691   for (; link; link = TREE_CHAIN (link), slot = XEXP (slot, 1))
3692     if (DECL_TOO_LATE (TREE_VALUE (link)))
3693       {
3694         rtx lab;
3695         lab = expand_nl_handler_label (XEXP (slot, 0),
3696                                        thisblock->data.block.first_insn);
3697         label_list = gen_rtx_EXPR_LIST (VOIDmode, lab, label_list);
3698         any_invalid = 1;
3699       }
3700
3701   if (any_invalid)
3702     {
3703       expand_nl_goto_receiver ();
3704       expand_builtin_trap ();
3705     }
3706
3707   nonlocal_goto_handler_labels = label_list;
3708   emit_label (afterward);
3709 }
3710
3711 /* Warn about any unused VARS (which may contain nodes other than
3712    VAR_DECLs, but such nodes are ignored).  The nodes are connected
3713    via the TREE_CHAIN field.  */
3714
3715 void
3716 warn_about_unused_variables (tree vars)
3717 {
3718   tree decl;
3719
3720   if (warn_unused_variable)
3721     for (decl = vars; decl; decl = TREE_CHAIN (decl))
3722       if (TREE_CODE (decl) == VAR_DECL
3723           && ! TREE_USED (decl)
3724           && ! DECL_IN_SYSTEM_HEADER (decl)
3725           && DECL_NAME (decl) && ! DECL_ARTIFICIAL (decl))
3726         warning ("%Junused variable '%D'", decl, decl);
3727 }
3728
3729 /* Generate RTL code to terminate a binding contour.
3730
3731    VARS is the chain of VAR_DECL nodes for the variables bound in this
3732    contour.  There may actually be other nodes in this chain, but any
3733    nodes other than VAR_DECLS are ignored.
3734
3735    MARK_ENDS is nonzero if we should put a note at the beginning
3736    and end of this binding contour.
3737
3738    DONT_JUMP_IN is positive if it is not valid to jump into this contour,
3739    zero if we can jump into this contour only if it does not have a saved
3740    stack level, and negative if we are not to check for invalid use of
3741    labels (because the front end does that).  */
3742
3743 void
3744 expand_end_bindings (tree vars, int mark_ends, int dont_jump_in)
3745 {
3746   struct nesting *thisblock = block_stack;
3747
3748   /* If any of the variables in this scope were not used, warn the
3749      user.  */
3750   warn_about_unused_variables (vars);
3751
3752   if (thisblock->exit_label)
3753     {
3754       do_pending_stack_adjust ();
3755       emit_label (thisblock->exit_label);
3756     }
3757
3758   /* If necessary, make handlers for nonlocal gotos taking
3759      place in the function calls in this block.  */
3760   if (function_call_count != 0 && nonlocal_labels
3761       /* Make handler for outermost block
3762          if there were any nonlocal gotos to this function.  */
3763       && (thisblock->next == 0 ? current_function_has_nonlocal_label
3764           /* Make handler for inner block if it has something
3765              special to do when you jump out of it.  */
3766           : (thisblock->data.block.cleanups != 0
3767              || thisblock->data.block.stack_level != 0)))
3768     expand_nl_goto_receivers (thisblock);
3769
3770   /* Don't allow jumping into a block that has a stack level.
3771      Cleanups are allowed, though.  */
3772   if (dont_jump_in > 0
3773       || (dont_jump_in == 0 && thisblock->data.block.stack_level != 0))
3774     {
3775       struct label_chain *chain;
3776
3777       /* Any labels in this block are no longer valid to go to.
3778          Mark them to cause an error message.  */
3779       for (chain = thisblock->data.block.label_chain; chain; chain = chain->next)
3780         {
3781           DECL_TOO_LATE (chain->label) = 1;
3782           /* If any goto without a fixup came to this label,
3783              that must be an error, because gotos without fixups
3784              come from outside all saved stack-levels.  */
3785           if (TREE_ADDRESSABLE (chain->label))
3786             error ("%Jlabel '%D' used before containing binding contour",
3787                    chain->label, chain->label);
3788         }
3789     }
3790
3791   /* Restore stack level in effect before the block
3792      (only if variable-size objects allocated).  */
3793   /* Perform any cleanups associated with the block.  */
3794
3795   if (thisblock->data.block.stack_level != 0
3796       || thisblock->data.block.cleanups != 0)
3797     {
3798       int reachable;
3799       rtx insn;
3800
3801       /* Don't let cleanups affect ({...}) constructs.  */
3802       int old_expr_stmts_for_value = expr_stmts_for_value;
3803       rtx old_last_expr_value = last_expr_value;
3804       rtx old_last_expr_alt_rtl = last_expr_alt_rtl;
3805       tree old_last_expr_type = last_expr_type;
3806       expr_stmts_for_value = 0;
3807
3808       /* Only clean up here if this point can actually be reached.  */
3809       insn = get_last_insn ();
3810       if (GET_CODE (insn) == NOTE)
3811         insn = prev_nonnote_insn (insn);
3812       reachable = (! insn || GET_CODE (insn) != BARRIER);
3813
3814       /* Do the cleanups.  */
3815       expand_cleanups (thisblock->data.block.cleanups, 0, reachable);
3816       if (reachable)
3817         do_pending_stack_adjust ();
3818
3819       expr_stmts_for_value = old_expr_stmts_for_value;
3820       last_expr_value = old_last_expr_value;
3821       last_expr_alt_rtl = old_last_expr_alt_rtl;
3822       last_expr_type = old_last_expr_type;
3823
3824       /* Restore the stack level.  */
3825
3826       if (reachable && thisblock->data.block.stack_level != 0)
3827         {
3828           emit_stack_restore (thisblock->next ? SAVE_BLOCK : SAVE_FUNCTION,
3829                               thisblock->data.block.stack_level, NULL_RTX);
3830           if (nonlocal_goto_handler_slots != 0)
3831             emit_stack_save (SAVE_NONLOCAL, &nonlocal_goto_stack_level,
3832                              NULL_RTX);
3833         }
3834
3835       /* Any gotos out of this block must also do these things.
3836          Also report any gotos with fixups that came to labels in this
3837          level.  */
3838       fixup_gotos (thisblock,
3839                    thisblock->data.block.stack_level,
3840                    thisblock->data.block.cleanups,
3841                    thisblock->data.block.first_insn,
3842                    dont_jump_in);
3843     }
3844
3845   /* Mark the beginning and end of the scope if requested.
3846      We do this now, after running cleanups on the variables
3847      just going out of scope, so they are in scope for their cleanups.  */
3848
3849   if (mark_ends)
3850     {
3851       rtx note = emit_note (NOTE_INSN_BLOCK_END);
3852       NOTE_BLOCK (note) = NOTE_BLOCK (thisblock->data.block.first_insn);
3853     }
3854   else
3855     /* Get rid of the beginning-mark if we don't make an end-mark.  */
3856     NOTE_LINE_NUMBER (thisblock->data.block.first_insn) = NOTE_INSN_DELETED;
3857
3858   /* Restore the temporary level of TARGET_EXPRs.  */
3859   target_temp_slot_level = thisblock->data.block.block_target_temp_slot_level;
3860
3861   /* Restore block_stack level for containing block.  */
3862
3863   stack_block_stack = thisblock->data.block.innermost_stack_block;
3864   POPSTACK (block_stack);
3865
3866   /* Pop the stack slot nesting and free any slots at this level.  */
3867   pop_temp_slots ();
3868 }
3869 \f
3870 /* Generate code to save the stack pointer at the start of the current block
3871    and set up to restore it on exit.  */
3872
3873 void
3874 save_stack_pointer (void)
3875 {
3876   struct nesting *thisblock = block_stack;
3877
3878   if (thisblock->data.block.stack_level == 0)
3879     {
3880       emit_stack_save (thisblock->next ? SAVE_BLOCK : SAVE_FUNCTION,
3881                        &thisblock->data.block.stack_level,
3882                        thisblock->data.block.first_insn);
3883       stack_block_stack = thisblock;
3884     }
3885 }
3886 \f
3887 /* Generate RTL for the automatic variable declaration DECL.
3888    (Other kinds of declarations are simply ignored if seen here.)  */
3889
3890 void
3891 expand_decl (tree decl)
3892 {
3893   tree type;
3894
3895   type = TREE_TYPE (decl);
3896
3897   /* For a CONST_DECL, set mode, alignment, and sizes from those of the
3898      type in case this node is used in a reference.  */
3899   if (TREE_CODE (decl) == CONST_DECL)
3900     {
3901       DECL_MODE (decl) = TYPE_MODE (type);
3902       DECL_ALIGN (decl) = TYPE_ALIGN (type);
3903       DECL_SIZE (decl) = TYPE_SIZE (type);
3904       DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
3905       return;
3906     }
3907
3908   /* Otherwise, only automatic variables need any expansion done.  Static and
3909      external variables, and external functions, will be handled by
3910      `assemble_variable' (called from finish_decl).  TYPE_DECL requires
3911      nothing.  PARM_DECLs are handled in `assign_parms'.  */
3912   if (TREE_CODE (decl) != VAR_DECL)
3913     return;
3914
3915   if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
3916     return;
3917
3918   /* Create the RTL representation for the variable.  */
3919
3920   if (type == error_mark_node)
3921     SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
3922
3923   else if (DECL_SIZE (decl) == 0)
3924     /* Variable with incomplete type.  */
3925     {
3926       rtx x;
3927       if (DECL_INITIAL (decl) == 0)
3928         /* Error message was already done; now avoid a crash.  */
3929         x = gen_rtx_MEM (BLKmode, const0_rtx);
3930       else
3931         /* An initializer is going to decide the size of this array.
3932            Until we know the size, represent its address with a reg.  */
3933         x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
3934
3935       set_mem_attributes (x, decl, 1);
3936       SET_DECL_RTL (decl, x);
3937     }
3938   else if (DECL_MODE (decl) != BLKmode
3939            /* If -ffloat-store, don't put explicit float vars
3940               into regs.  */
3941            && !(flag_float_store
3942                 && TREE_CODE (type) == REAL_TYPE)
3943            && ! TREE_THIS_VOLATILE (decl)
3944            && ! DECL_NONLOCAL (decl)
3945            && (DECL_REGISTER (decl) || DECL_ARTIFICIAL (decl) || optimize))
3946     {
3947       /* Automatic variable that can go in a register.  */
3948       int unsignedp = TYPE_UNSIGNED (type);
3949       enum machine_mode reg_mode
3950         = promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
3951
3952       SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
3953
3954       if (!DECL_ARTIFICIAL (decl))
3955         mark_user_reg (DECL_RTL (decl));
3956
3957       if (POINTER_TYPE_P (type))
3958         mark_reg_pointer (DECL_RTL (decl),
3959                           TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
3960
3961       maybe_set_unchanging (DECL_RTL (decl), decl);
3962
3963       /* If something wants our address, try to use ADDRESSOF.  */
3964       if (TREE_ADDRESSABLE (decl))
3965         put_var_into_stack (decl, /*rescan=*/false);
3966     }
3967
3968   else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST
3969            && ! (flag_stack_check && ! STACK_CHECK_BUILTIN
3970                  && 0 < compare_tree_int (DECL_SIZE_UNIT (decl),
3971                                           STACK_CHECK_MAX_VAR_SIZE)))
3972     {
3973       /* Variable of fixed size that goes on the stack.  */
3974       rtx oldaddr = 0;
3975       rtx addr;
3976       rtx x;
3977
3978       /* If we previously made RTL for this decl, it must be an array
3979          whose size was determined by the initializer.
3980          The old address was a register; set that register now
3981          to the proper address.  */
3982       if (DECL_RTL_SET_P (decl))
3983         {
3984           if (GET_CODE (DECL_RTL (decl)) != MEM
3985               || GET_CODE (XEXP (DECL_RTL (decl), 0)) != REG)
3986             abort ();
3987           oldaddr = XEXP (DECL_RTL (decl), 0);
3988         }
3989
3990       /* Set alignment we actually gave this decl.  */
3991       DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
3992                            : GET_MODE_BITSIZE (DECL_MODE (decl)));
3993       DECL_USER_ALIGN (decl) = 0;
3994
3995       x = assign_temp (decl, 1, 1, 1);
3996       set_mem_attributes (x, decl, 1);
3997       SET_DECL_RTL (decl, x);
3998
3999       if (oldaddr)
4000         {
4001           addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
4002           if (addr != oldaddr)
4003             emit_move_insn (oldaddr, addr);
4004         }
4005     }
4006   else
4007     /* Dynamic-size object: must push space on the stack.  */
4008     {
4009       rtx address, size, x;
4010
4011       /* Record the stack pointer on entry to block, if have
4012          not already done so.  */
4013       do_pending_stack_adjust ();
4014       save_stack_pointer ();
4015
4016       /* In function-at-a-time mode, variable_size doesn't expand this,
4017          so do it now.  */
4018       if (TREE_CODE (type) == ARRAY_TYPE && TYPE_DOMAIN (type))
4019         expand_expr (TYPE_MAX_VALUE (TYPE_DOMAIN (type)),
4020                      const0_rtx, VOIDmode, 0);
4021
4022       /* Compute the variable's size, in bytes.  */
4023       size = expand_expr (DECL_SIZE_UNIT (decl), NULL_RTX, VOIDmode, 0);
4024       free_temp_slots ();
4025
4026       /* Allocate space on the stack for the variable.  Note that
4027          DECL_ALIGN says how the variable is to be aligned and we
4028          cannot use it to conclude anything about the alignment of
4029          the size.  */
4030       address = allocate_dynamic_stack_space (size, NULL_RTX,
4031                                               TYPE_ALIGN (TREE_TYPE (decl)));
4032
4033       /* Reference the variable indirect through that rtx.  */
4034       x = gen_rtx_MEM (DECL_MODE (decl), address);
4035       set_mem_attributes (x, decl, 1);
4036       SET_DECL_RTL (decl, x);
4037
4038
4039       /* Indicate the alignment we actually gave this variable.  */
4040 #ifdef STACK_BOUNDARY
4041       DECL_ALIGN (decl) = STACK_BOUNDARY;
4042 #else
4043       DECL_ALIGN (decl) = BIGGEST_ALIGNMENT;
4044 #endif
4045       DECL_USER_ALIGN (decl) = 0;
4046     }
4047 }
4048 \f
4049 /* Emit code to perform the initialization of a declaration DECL.  */
4050
4051 void
4052 expand_decl_init (tree decl)
4053 {
4054   int was_used = TREE_USED (decl);
4055
4056   /* If this is a CONST_DECL, we don't have to generate any code.  Likewise
4057      for static decls.  */
4058   if (TREE_CODE (decl) == CONST_DECL
4059       || TREE_STATIC (decl))
4060     return;
4061
4062   /* Compute and store the initial value now.  */
4063
4064   push_temp_slots ();
4065
4066   if (DECL_INITIAL (decl) == error_mark_node)
4067     {
4068       enum tree_code code = TREE_CODE (TREE_TYPE (decl));
4069
4070       if (code == INTEGER_TYPE || code == REAL_TYPE || code == ENUMERAL_TYPE
4071           || code == POINTER_TYPE || code == REFERENCE_TYPE)
4072         expand_assignment (decl, convert (TREE_TYPE (decl), integer_zero_node),
4073                            0);
4074       emit_queue ();
4075     }
4076   else if (DECL_INITIAL (decl) && TREE_CODE (DECL_INITIAL (decl)) != TREE_LIST)
4077     {
4078       emit_line_note (DECL_SOURCE_LOCATION (decl));
4079       expand_assignment (decl, DECL_INITIAL (decl), 0);
4080       emit_queue ();
4081     }
4082
4083   /* Don't let the initialization count as "using" the variable.  */
4084   TREE_USED (decl) = was_used;
4085
4086   /* Free any temporaries we made while initializing the decl.  */
4087   preserve_temp_slots (NULL_RTX);
4088   free_temp_slots ();
4089   pop_temp_slots ();
4090 }
4091
4092 /* CLEANUP is an expression to be executed at exit from this binding contour;
4093    for example, in C++, it might call the destructor for this variable.
4094
4095    We wrap CLEANUP in an UNSAVE_EXPR node, so that we can expand the
4096    CLEANUP multiple times, and have the correct semantics.  This
4097    happens in exception handling, for gotos, returns, breaks that
4098    leave the current scope.
4099
4100    If CLEANUP is nonzero and DECL is zero, we record a cleanup
4101    that is not associated with any particular variable.  */
4102
4103 int
4104 expand_decl_cleanup (tree decl, tree cleanup)
4105 {
4106   struct nesting *thisblock;
4107
4108   /* Error if we are not in any block.  */
4109   if (cfun == 0 || block_stack == 0)
4110     return 0;
4111
4112   thisblock = block_stack;
4113
4114   /* Record the cleanup if there is one.  */
4115
4116   if (cleanup != 0)
4117     {
4118       tree t;
4119       rtx seq;
4120       tree *cleanups = &thisblock->data.block.cleanups;
4121       int cond_context = conditional_context ();
4122
4123       if (cond_context)
4124         {
4125           rtx flag = gen_reg_rtx (word_mode);
4126           rtx set_flag_0;
4127           tree cond;
4128
4129           start_sequence ();
4130           emit_move_insn (flag, const0_rtx);
4131           set_flag_0 = get_insns ();
4132           end_sequence ();
4133
4134           thisblock->data.block.last_unconditional_cleanup
4135             = emit_insn_after (set_flag_0,
4136                                 thisblock->data.block.last_unconditional_cleanup);
4137
4138           emit_move_insn (flag, const1_rtx);
4139
4140           cond = build_decl (VAR_DECL, NULL_TREE,
4141                              lang_hooks.types.type_for_mode (word_mode, 1));
4142           SET_DECL_RTL (cond, flag);
4143
4144           /* Conditionalize the cleanup.  */
4145           cleanup = build (COND_EXPR, void_type_node,
4146                            lang_hooks.truthvalue_conversion (cond),
4147                            cleanup, integer_zero_node);
4148           cleanup = fold (cleanup);
4149
4150           cleanups = &thisblock->data.block.cleanups;
4151         }
4152
4153       cleanup = unsave_expr (cleanup);
4154
4155       t = *cleanups = tree_cons (decl, cleanup, *cleanups);
4156
4157       if (! cond_context)
4158         /* If this block has a cleanup, it belongs in stack_block_stack.  */
4159         stack_block_stack = thisblock;
4160
4161       if (cond_context)
4162         {
4163           start_sequence ();
4164         }
4165
4166       if (! using_eh_for_cleanups_p)
4167         TREE_ADDRESSABLE (t) = 1;
4168       else
4169         expand_eh_region_start ();
4170
4171       if (cond_context)
4172         {
4173           seq = get_insns ();
4174           end_sequence ();
4175           if (seq)
4176             thisblock->data.block.last_unconditional_cleanup
4177               = emit_insn_after (seq,
4178                                  thisblock->data.block.last_unconditional_cleanup);
4179         }
4180       else
4181         {
4182           thisblock->data.block.last_unconditional_cleanup
4183             = get_last_insn ();
4184           /* When we insert instructions after the last unconditional cleanup,
4185              we don't adjust last_insn.  That means that a later add_insn will
4186              clobber the instructions we've just added.  The easiest way to
4187              fix this is to just insert another instruction here, so that the
4188              instructions inserted after the last unconditional cleanup are
4189              never the last instruction.  */
4190           emit_note (NOTE_INSN_DELETED);
4191         }
4192     }
4193   return 1;
4194 }
4195
4196 /* Like expand_decl_cleanup, but maybe only run the cleanup if an exception
4197    is thrown.  */
4198
4199 int
4200 expand_decl_cleanup_eh (tree decl, tree cleanup, int eh_only)
4201 {
4202   int ret = expand_decl_cleanup (decl, cleanup);
4203   if (cleanup && ret)
4204     {
4205       tree node = block_stack->data.block.cleanups;
4206       CLEANUP_EH_ONLY (node) = eh_only;
4207     }
4208   return ret;
4209 }
4210 \f
4211 /* DECL is an anonymous union.  CLEANUP is a cleanup for DECL.
4212    DECL_ELTS is the list of elements that belong to DECL's type.
4213    In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup.  */
4214
4215 void
4216 expand_anon_union_decl (tree decl, tree cleanup, tree decl_elts)
4217 {
4218   struct nesting *thisblock = cfun == 0 ? 0 : block_stack;
4219   rtx x;
4220   tree t;
4221
4222   /* If any of the elements are addressable, so is the entire union.  */
4223   for (t = decl_elts; t; t = TREE_CHAIN (t))
4224     if (TREE_ADDRESSABLE (TREE_VALUE (t)))
4225       {
4226         TREE_ADDRESSABLE (decl) = 1;
4227         break;
4228       }
4229
4230   expand_decl (decl);
4231   expand_decl_cleanup (decl, cleanup);
4232   x = DECL_RTL (decl);
4233
4234   /* Go through the elements, assigning RTL to each.  */
4235   for (t = decl_elts; t; t = TREE_CHAIN (t))
4236     {
4237       tree decl_elt = TREE_VALUE (t);
4238       tree cleanup_elt = TREE_PURPOSE (t);
4239       enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt));
4240
4241       /* If any of the elements are addressable, so is the entire
4242          union.  */
4243       if (TREE_USED (decl_elt))
4244         TREE_USED (decl) = 1;
4245
4246       /* Propagate the union's alignment to the elements.  */
4247       DECL_ALIGN (decl_elt) = DECL_ALIGN (decl);
4248       DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl);
4249
4250       /* If the element has BLKmode and the union doesn't, the union is
4251          aligned such that the element doesn't need to have BLKmode, so
4252          change the element's mode to the appropriate one for its size.  */
4253       if (mode == BLKmode && DECL_MODE (decl) != BLKmode)
4254         DECL_MODE (decl_elt) = mode
4255           = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1);
4256
4257       /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we
4258          instead create a new MEM rtx with the proper mode.  */
4259       if (GET_CODE (x) == MEM)
4260         {
4261           if (mode == GET_MODE (x))
4262             SET_DECL_RTL (decl_elt, x);
4263           else
4264             SET_DECL_RTL (decl_elt, adjust_address_nv (x, mode, 0));
4265         }
4266       else if (GET_CODE (x) == REG)
4267         {
4268           if (mode == GET_MODE (x))
4269             SET_DECL_RTL (decl_elt, x);
4270           else
4271             SET_DECL_RTL (decl_elt, gen_lowpart_SUBREG (mode, x));
4272         }
4273       else
4274         abort ();
4275
4276       /* Record the cleanup if there is one.  */
4277
4278       if (cleanup != 0)
4279         thisblock->data.block.cleanups
4280           = tree_cons (decl_elt, cleanup_elt,
4281                        thisblock->data.block.cleanups);
4282     }
4283 }
4284 \f
4285 /* Expand a list of cleanups LIST.
4286    Elements may be expressions or may be nested lists.
4287
4288    If IN_FIXUP is nonzero, we are generating this cleanup for a fixup
4289    goto and handle protection regions specially in that case.
4290
4291    If REACHABLE, we emit code, otherwise just inform the exception handling
4292    code about this finalization.  */
4293
4294 static void
4295 expand_cleanups (tree list, int in_fixup, int reachable)
4296 {
4297   tree tail;
4298   for (tail = list; tail; tail = TREE_CHAIN (tail))
4299     if (TREE_CODE (TREE_VALUE (tail)) == TREE_LIST)
4300       expand_cleanups (TREE_VALUE (tail), in_fixup, reachable);
4301     else
4302       {
4303         if (! in_fixup && using_eh_for_cleanups_p)
4304           expand_eh_region_end_cleanup (TREE_VALUE (tail));
4305
4306         if (reachable && !CLEANUP_EH_ONLY (tail))
4307           {
4308             /* Cleanups may be run multiple times.  For example,
4309                when exiting a binding contour, we expand the
4310                cleanups associated with that contour.  When a goto
4311                within that binding contour has a target outside that
4312                contour, it will expand all cleanups from its scope to
4313                the target.  Though the cleanups are expanded multiple
4314                times, the control paths are non-overlapping so the
4315                cleanups will not be executed twice.  */
4316
4317             /* We may need to protect from outer cleanups.  */
4318             if (in_fixup && using_eh_for_cleanups_p)
4319               {
4320                 expand_eh_region_start ();
4321
4322                 expand_expr (TREE_VALUE (tail), const0_rtx, VOIDmode, 0);
4323
4324                 expand_eh_region_end_fixup (TREE_VALUE (tail));
4325               }
4326             else
4327               expand_expr (TREE_VALUE (tail), const0_rtx, VOIDmode, 0);
4328
4329             free_temp_slots ();
4330           }
4331       }
4332 }
4333
4334 /* Mark when the context we are emitting RTL for as a conditional
4335    context, so that any cleanup actions we register with
4336    expand_decl_init will be properly conditionalized when those
4337    cleanup actions are later performed.  Must be called before any
4338    expression (tree) is expanded that is within a conditional context.  */
4339
4340 void
4341 start_cleanup_deferral (void)
4342 {
4343   /* block_stack can be NULL if we are inside the parameter list.  It is
4344      OK to do nothing, because cleanups aren't possible here.  */
4345   if (block_stack)
4346     ++block_stack->data.block.conditional_code;
4347 }
4348
4349 /* Mark the end of a conditional region of code.  Because cleanup
4350    deferrals may be nested, we may still be in a conditional region
4351    after we end the currently deferred cleanups, only after we end all
4352    deferred cleanups, are we back in unconditional code.  */
4353
4354 void
4355 end_cleanup_deferral (void)
4356 {
4357   /* block_stack can be NULL if we are inside the parameter list.  It is
4358      OK to do nothing, because cleanups aren't possible here.  */
4359   if (block_stack)
4360     --block_stack->data.block.conditional_code;
4361 }
4362
4363 tree
4364 last_cleanup_this_contour (void)
4365 {
4366   if (block_stack == 0)
4367     return 0;
4368
4369   return block_stack->data.block.cleanups;
4370 }
4371
4372 /* Return 1 if there are any pending cleanups at this point.
4373    Check the current contour as well as contours that enclose
4374    the current contour.  */
4375
4376 int
4377 any_pending_cleanups (void)
4378 {
4379   struct nesting *block;
4380
4381   if (cfun == NULL || cfun->stmt == NULL || block_stack == 0)
4382     return 0;
4383
4384   if (block_stack->data.block.cleanups != NULL)
4385     return 1;
4386
4387   if (block_stack->data.block.outer_cleanups == 0)
4388     return 0;
4389
4390   for (block = block_stack->next; block; block = block->next)
4391     if (block->data.block.cleanups != 0)
4392       return 1;
4393
4394   return 0;
4395 }
4396 \f
4397 /* Enter a case (Pascal) or switch (C) statement.
4398    Push a block onto case_stack and nesting_stack
4399    to accumulate the case-labels that are seen
4400    and to record the labels generated for the statement.
4401
4402    EXIT_FLAG is nonzero if `exit_something' should exit this case stmt.
4403    Otherwise, this construct is transparent for `exit_something'.
4404
4405    EXPR is the index-expression to be dispatched on.
4406    TYPE is its nominal type.  We could simply convert EXPR to this type,
4407    but instead we take short cuts.  */
4408
4409 void
4410 expand_start_case (int exit_flag, tree expr, tree type,
4411                    const char *printname)
4412 {
4413   struct nesting *thiscase = ALLOC_NESTING ();
4414
4415   /* Make an entry on case_stack for the case we are entering.  */
4416
4417   thiscase->desc = CASE_NESTING;
4418   thiscase->next = case_stack;
4419   thiscase->all = nesting_stack;
4420   thiscase->depth = ++nesting_depth;
4421   thiscase->exit_label = exit_flag ? gen_label_rtx () : 0;
4422   thiscase->data.case_stmt.case_list = 0;
4423   thiscase->data.case_stmt.index_expr = expr;
4424   thiscase->data.case_stmt.nominal_type = type;
4425   thiscase->data.case_stmt.default_label = 0;
4426   thiscase->data.case_stmt.printname = printname;
4427   thiscase->data.case_stmt.line_number_status = force_line_numbers ();
4428   case_stack = thiscase;
4429   nesting_stack = thiscase;
4430
4431   do_pending_stack_adjust ();
4432   emit_queue ();
4433
4434   /* Make sure case_stmt.start points to something that won't
4435      need any transformation before expand_end_case.  */
4436   if (GET_CODE (get_last_insn ()) != NOTE)
4437     emit_note (NOTE_INSN_DELETED);
4438
4439   thiscase->data.case_stmt.start = get_last_insn ();
4440
4441   start_cleanup_deferral ();
4442 }
4443 \f
4444 static void
4445 check_seenlabel (void)
4446 {
4447   /* If this is the first label, warn if any insns have been emitted.  */
4448   if (case_stack->data.case_stmt.line_number_status >= 0)
4449     {
4450       rtx insn;
4451
4452       restore_line_number_status
4453         (case_stack->data.case_stmt.line_number_status);
4454       case_stack->data.case_stmt.line_number_status = -1;
4455
4456       for (insn = case_stack->data.case_stmt.start;
4457            insn;
4458            insn = NEXT_INSN (insn))
4459         {
4460           if (GET_CODE (insn) == CODE_LABEL)
4461             break;
4462           if (GET_CODE (insn) != NOTE
4463               && (GET_CODE (insn) != INSN || GET_CODE (PATTERN (insn)) != USE))
4464             {
4465               do
4466                 insn = PREV_INSN (insn);
4467               while (insn && (GET_CODE (insn) != NOTE || NOTE_LINE_NUMBER (insn) < 0));
4468
4469               /* If insn is zero, then there must have been a syntax error.  */
4470               if (insn)
4471                 {
4472                   location_t locus;
4473                   locus.file = NOTE_SOURCE_FILE (insn);
4474                   locus.line = NOTE_LINE_NUMBER (insn);
4475                   warning ("%Hunreachable code at beginning of %s", &locus,
4476                            case_stack->data.case_stmt.printname);
4477                 }
4478               break;
4479             }
4480         }
4481     }
4482 }
4483
4484 /* Accumulate one case or default label inside a case or switch statement.
4485    VALUE is the value of the case (a null pointer, for a default label).
4486    The function CONVERTER, when applied to arguments T and V,
4487    converts the value V to the type T.
4488
4489    If not currently inside a case or switch statement, return 1 and do
4490    nothing.  The caller will print a language-specific error message.
4491    If VALUE is a duplicate or overlaps, return 2 and do nothing
4492    except store the (first) duplicate node in *DUPLICATE.
4493    If VALUE is out of range, return 3 and do nothing.
4494    If we are jumping into the scope of a cleanup or var-sized array, return 5.
4495    Return 0 on success.
4496
4497    Extended to handle range statements.  */
4498
4499 int
4500 pushcase (tree value, tree (*converter) (tree, tree), tree label,
4501           tree *duplicate)
4502 {
4503   tree index_type;
4504   tree nominal_type;
4505
4506   /* Fail if not inside a real case statement.  */
4507   if (! (case_stack && case_stack->data.case_stmt.start))
4508     return 1;
4509
4510   if (stack_block_stack
4511       && stack_block_stack->depth > case_stack->depth)
4512     return 5;
4513
4514   index_type = TREE_TYPE (case_stack->data.case_stmt.index_expr);
4515   nominal_type = case_stack->data.case_stmt.nominal_type;
4516
4517   /* If the index is erroneous, avoid more problems: pretend to succeed.  */
4518   if (index_type == error_mark_node)
4519     return 0;
4520
4521   /* Convert VALUE to the type in which the comparisons are nominally done.  */
4522   if (value != 0)
4523     value = (*converter) (nominal_type, value);
4524
4525   check_seenlabel ();
4526
4527   /* Fail if this value is out of range for the actual type of the index
4528      (which may be narrower than NOMINAL_TYPE).  */
4529   if (value != 0
4530       && (TREE_CONSTANT_OVERFLOW (value)
4531           || ! int_fits_type_p (value, index_type)))
4532     return 3;
4533
4534   return add_case_node (value, value, label, duplicate);
4535 }
4536
4537 /* Like pushcase but this case applies to all values between VALUE1 and
4538    VALUE2 (inclusive).  If VALUE1 is NULL, the range starts at the lowest
4539    value of the index type and ends at VALUE2.  If VALUE2 is NULL, the range
4540    starts at VALUE1 and ends at the highest value of the index type.
4541    If both are NULL, this case applies to all values.
4542
4543    The return value is the same as that of pushcase but there is one
4544    additional error code: 4 means the specified range was empty.  */
4545
4546 int
4547 pushcase_range (tree value1, tree value2, tree (*converter) (tree, tree),
4548                 tree label, tree *duplicate)
4549 {
4550   tree index_type;
4551   tree nominal_type;
4552
4553   /* Fail if not inside a real case statement.  */
4554   if (! (case_stack && case_stack->data.case_stmt.start))
4555     return 1;
4556
4557   if (stack_block_stack
4558       && stack_block_stack->depth > case_stack->depth)
4559     return 5;
4560
4561   index_type = TREE_TYPE (case_stack->data.case_stmt.index_expr);
4562   nominal_type = case_stack->data.case_stmt.nominal_type;
4563
4564   /* If the index is erroneous, avoid more problems: pretend to succeed.  */
4565   if (index_type == error_mark_node)
4566     return 0;
4567
4568   check_seenlabel ();
4569
4570   /* Convert VALUEs to type in which the comparisons are nominally done
4571      and replace any unspecified value with the corresponding bound.  */
4572   if (value1 == 0)
4573     value1 = TYPE_MIN_VALUE (index_type);
4574   if (value2 == 0)
4575     value2 = TYPE_MAX_VALUE (index_type);
4576
4577   /* Fail if the range is empty.  Do this before any conversion since
4578      we want to allow out-of-range empty ranges.  */
4579   if (value2 != 0 && tree_int_cst_lt (value2, value1))
4580     return 4;
4581
4582   /* If the max was unbounded, use the max of the nominal_type we are
4583      converting to.  Do this after the < check above to suppress false
4584      positives.  */
4585   if (value2 == 0)
4586     value2 = TYPE_MAX_VALUE (nominal_type);
4587
4588   value1 = (*converter) (nominal_type, value1);
4589   value2 = (*converter) (nominal_type, value2);
4590
4591   /* Fail if these values are out of range.  */
4592   if (TREE_CONSTANT_OVERFLOW (value1)
4593       || ! int_fits_type_p (value1, index_type))
4594     return 3;
4595
4596   if (TREE_CONSTANT_OVERFLOW (value2)
4597       || ! int_fits_type_p (value2, index_type))
4598     return 3;
4599
4600   return add_case_node (value1, value2, label, duplicate);
4601 }
4602
4603 /* Do the actual insertion of a case label for pushcase and pushcase_range
4604    into case_stack->data.case_stmt.case_list.  Use an AVL tree to avoid
4605    slowdown for large switch statements.  */
4606
4607 int
4608 add_case_node (tree low, tree high, tree label, tree *duplicate)
4609 {
4610   struct case_node *p, **q, *r;
4611
4612   /* If there's no HIGH value, then this is not a case range; it's
4613      just a simple case label.  But that's just a degenerate case
4614      range.  */
4615   if (!high)
4616     high = low;
4617
4618   /* Handle default labels specially.  */
4619   if (!high && !low)
4620     {
4621       if (case_stack->data.case_stmt.default_label != 0)
4622         {
4623           *duplicate = case_stack->data.case_stmt.default_label;
4624           return 2;
4625         }
4626       case_stack->data.case_stmt.default_label = label;
4627       expand_label (label);
4628       return 0;
4629     }
4630
4631   q = &case_stack->data.case_stmt.case_list;
4632   p = *q;
4633
4634   while ((r = *q))
4635     {
4636       p = r;
4637
4638       /* Keep going past elements distinctly greater than HIGH.  */
4639       if (tree_int_cst_lt (high, p->low))
4640         q = &p->left;
4641
4642       /* or distinctly less than LOW.  */
4643       else if (tree_int_cst_lt (p->high, low))
4644         q = &p->right;
4645
4646       else
4647         {
4648           /* We have an overlap; this is an error.  */
4649           *duplicate = p->code_label;
4650           return 2;
4651         }
4652     }
4653
4654   /* Add this label to the chain, and succeed.  */
4655
4656   r = ggc_alloc (sizeof (struct case_node));
4657   r->low = low;
4658
4659   /* If the bounds are equal, turn this into the one-value case.  */
4660   if (tree_int_cst_equal (low, high))
4661     r->high = r->low;
4662   else
4663     r->high = high;
4664
4665   r->code_label = label;
4666   expand_label (label);
4667
4668   *q = r;
4669   r->parent = p;
4670   r->left = 0;
4671   r->right = 0;
4672   r->balance = 0;
4673
4674   while (p)
4675     {
4676       struct case_node *s;
4677
4678       if (r == p->left)
4679         {
4680           int b;
4681
4682           if (! (b = p->balance))
4683             /* Growth propagation from left side.  */
4684             p->balance = -1;
4685           else if (b < 0)
4686             {
4687               if (r->balance < 0)
4688                 {
4689                   /* R-Rotation */
4690                   if ((p->left = s = r->right))
4691                     s->parent = p;
4692
4693                   r->right = p;
4694                   p->balance = 0;
4695                   r->balance = 0;
4696                   s = p->parent;
4697                   p->parent = r;
4698
4699                   if ((r->parent = s))
4700                     {
4701                       if (s->left == p)
4702                         s->left = r;
4703                       else
4704                         s->right = r;
4705                     }
4706                   else
4707                     case_stack->data.case_stmt.case_list = r;
4708                 }
4709               else
4710                 /* r->balance == +1 */
4711                 {
4712                   /* LR-Rotation */
4713
4714                   int b2;
4715                   struct case_node *t = r->right;
4716
4717                   if ((p->left = s = t->right))
4718                     s->parent = p;
4719
4720                   t->right = p;
4721                   if ((r->right = s = t->left))
4722                     s->parent = r;
4723
4724                   t->left = r;
4725                   b = t->balance;
4726                   b2 = b < 0;
4727                   p->balance = b2;
4728                   b2 = -b2 - b;
4729                   r->balance = b2;
4730                   t->balance = 0;
4731                   s = p->parent;
4732                   p->parent = t;
4733                   r->parent = t;
4734
4735                   if ((t->parent = s))
4736                     {
4737                       if (s->left == p)
4738                         s->left = t;
4739                       else
4740                         s->right = t;
4741                     }
4742                   else
4743                     case_stack->data.case_stmt.case_list = t;
4744                 }
4745               break;
4746             }
4747
4748           else
4749             {
4750               /* p->balance == +1; growth of left side balances the node.  */
4751               p->balance = 0;
4752               break;
4753             }
4754         }
4755       else
4756         /* r == p->right */
4757         {
4758           int b;
4759
4760           if (! (b = p->balance))
4761             /* Growth propagation from right side.  */
4762             p->balance++;
4763           else if (b > 0)
4764             {
4765               if (r->balance > 0)
4766                 {
4767                   /* L-Rotation */
4768
4769                   if ((p->right = s = r->left))
4770                     s->parent = p;
4771
4772                   r->left = p;
4773                   p->balance = 0;
4774                   r->balance = 0;
4775                   s = p->parent;
4776                   p->parent = r;
4777                   if ((r->parent = s))
4778                     {
4779                       if (s->left == p)
4780                         s->left = r;
4781                       else
4782                         s->right = r;
4783                     }
4784
4785                   else
4786                     case_stack->data.case_stmt.case_list = r;
4787                 }
4788
4789               else
4790                 /* r->balance == -1 */
4791                 {
4792                   /* RL-Rotation */
4793                   int b2;
4794                   struct case_node *t = r->left;
4795
4796                   if ((p->right = s = t->left))
4797                     s->parent = p;
4798
4799                   t->left = p;
4800
4801                   if ((r->left = s = t->right))
4802                     s->parent = r;
4803
4804                   t->right = r;
4805                   b = t->balance;
4806                   b2 = b < 0;
4807                   r->balance = b2;
4808                   b2 = -b2 - b;
4809                   p->balance = b2;
4810                   t->balance = 0;
4811                   s = p->parent;
4812                   p->parent = t;
4813                   r->parent = t;
4814
4815                   if ((t->parent = s))
4816                     {
4817                       if (s->left == p)
4818                         s->left = t;
4819                       else
4820                         s->right = t;
4821                     }
4822
4823                   else
4824                     case_stack->data.case_stmt.case_list = t;
4825                 }
4826               break;
4827             }
4828           else
4829             {
4830               /* p->balance == -1; growth of right side balances the node.  */
4831               p->balance = 0;
4832               break;
4833             }
4834         }
4835
4836       r = p;
4837       p = p->parent;
4838     }
4839
4840   return 0;
4841 }
4842 \f
4843 /* Returns the number of possible values of TYPE.
4844    Returns -1 if the number is unknown, variable, or if the number does not
4845    fit in a HOST_WIDE_INT.
4846    Sets *SPARSENESS to 2 if TYPE is an ENUMERAL_TYPE whose values
4847    do not increase monotonically (there may be duplicates);
4848    to 1 if the values increase monotonically, but not always by 1;
4849    otherwise sets it to 0.  */
4850
4851 HOST_WIDE_INT
4852 all_cases_count (tree type, int *sparseness)
4853 {
4854   tree t;
4855   HOST_WIDE_INT count, minval, lastval;
4856
4857   *sparseness = 0;
4858
4859   switch (TREE_CODE (type))
4860     {
4861     case BOOLEAN_TYPE:
4862       count = 2;
4863       break;
4864
4865     case CHAR_TYPE:
4866       count = 1 << BITS_PER_UNIT;
4867       break;
4868
4869     default:
4870     case INTEGER_TYPE:
4871       if (TYPE_MAX_VALUE (type) != 0
4872           && 0 != (t = fold (build (MINUS_EXPR, type, TYPE_MAX_VALUE (type),
4873                                     TYPE_MIN_VALUE (type))))
4874           && 0 != (t = fold (build (PLUS_EXPR, type, t,
4875                                     convert (type, integer_zero_node))))
4876           && host_integerp (t, 1))
4877         count = tree_low_cst (t, 1);
4878       else
4879         return -1;
4880       break;
4881
4882     case ENUMERAL_TYPE:
4883       /* Don't waste time with enumeral types with huge values.  */
4884       if (! host_integerp (TYPE_MIN_VALUE (type), 0)
4885           || TYPE_MAX_VALUE (type) == 0
4886           || ! host_integerp (TYPE_MAX_VALUE (type), 0))
4887         return -1;
4888
4889       lastval = minval = tree_low_cst (TYPE_MIN_VALUE (type), 0);
4890       count = 0;
4891
4892       for (t = TYPE_VALUES (type); t != NULL_TREE; t = TREE_CHAIN (t))
4893         {
4894           HOST_WIDE_INT thisval = tree_low_cst (TREE_VALUE (t), 0);
4895
4896           if (*sparseness == 2 || thisval <= lastval)
4897             *sparseness = 2;
4898           else if (thisval != minval + count)
4899             *sparseness = 1;
4900
4901           lastval = thisval;
4902           count++;
4903         }
4904     }
4905
4906   return count;
4907 }
4908
4909 #define BITARRAY_TEST(ARRAY, INDEX) \
4910   ((ARRAY)[(unsigned) (INDEX) / HOST_BITS_PER_CHAR]\
4911                           & (1 << ((unsigned) (INDEX) % HOST_BITS_PER_CHAR)))
4912 #define BITARRAY_SET(ARRAY, INDEX) \
4913   ((ARRAY)[(unsigned) (INDEX) / HOST_BITS_PER_CHAR]\
4914                           |= 1 << ((unsigned) (INDEX) % HOST_BITS_PER_CHAR))
4915
4916 /* Set the elements of the bitstring CASES_SEEN (which has length COUNT),
4917    with the case values we have seen, assuming the case expression
4918    has the given TYPE.
4919    SPARSENESS is as determined by all_cases_count.
4920
4921    The time needed is proportional to COUNT, unless
4922    SPARSENESS is 2, in which case quadratic time is needed.  */
4923
4924 void
4925 mark_seen_cases (tree type, unsigned char *cases_seen, HOST_WIDE_INT count,
4926                  int sparseness)
4927 {
4928   tree next_node_to_try = NULL_TREE;
4929   HOST_WIDE_INT next_node_offset = 0;
4930
4931   struct case_node *n, *root = case_stack->data.case_stmt.case_list;
4932   tree val = make_node (INTEGER_CST);
4933
4934   TREE_TYPE (val) = type;
4935   if (! root)
4936     /* Do nothing.  */
4937     ;
4938   else if (sparseness == 2)
4939     {
4940       tree t;
4941       unsigned HOST_WIDE_INT xlo;
4942
4943       /* This less efficient loop is only needed to handle
4944          duplicate case values (multiple enum constants
4945          with the same value).  */
4946       TREE_TYPE (val) = TREE_TYPE (root->low);
4947       for (t = TYPE_VALUES (type), xlo = 0; t != NULL_TREE;
4948            t = TREE_CHAIN (t), xlo++)
4949         {
4950           TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (TREE_VALUE (t));
4951           TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (TREE_VALUE (t));
4952           n = root;
4953           do
4954             {
4955               /* Keep going past elements distinctly greater than VAL.  */
4956               if (tree_int_cst_lt (val, n->low))
4957                 n = n->left;
4958
4959               /* or distinctly less than VAL.  */
4960               else if (tree_int_cst_lt (n->high, val))
4961                 n = n->right;
4962
4963               else
4964                 {
4965                   /* We have found a matching range.  */
4966                   BITARRAY_SET (cases_seen, xlo);
4967                   break;
4968                 }
4969             }
4970           while (n);
4971         }
4972     }
4973   else
4974     {
4975       if (root->left)
4976         case_stack->data.case_stmt.case_list = root = case_tree2list (root, 0);
4977
4978       for (n = root; n; n = n->right)
4979         {
4980           TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (n->low);
4981           TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (n->low);
4982           while (! tree_int_cst_lt (n->high, val))
4983             {
4984               /* Calculate (into xlo) the "offset" of the integer (val).
4985                  The element with lowest value has offset 0, the next smallest
4986                  element has offset 1, etc.  */
4987
4988               unsigned HOST_WIDE_INT xlo;
4989               HOST_WIDE_INT xhi;
4990               tree t;
4991
4992               if (sparseness && TYPE_VALUES (type) != NULL_TREE)
4993                 {
4994                   /* The TYPE_VALUES will be in increasing order, so
4995                      starting searching where we last ended.  */
4996                   t = next_node_to_try;
4997                   xlo = next_node_offset;
4998                   xhi = 0;
4999                   for (;;)
5000                     {
5001                       if (t == NULL_TREE)
5002                         {
5003                           t = TYPE_VALUES (type);
5004                           xlo = 0;
5005                         }
5006                       if (tree_int_cst_equal (val, TREE_VALUE (t)))
5007                         {
5008                           next_node_to_try = TREE_CHAIN (t);
5009                           next_node_offset = xlo + 1;
5010                           break;
5011                         }
5012                       xlo++;
5013                       t = TREE_CHAIN (t);
5014                       if (t == next_node_to_try)
5015                         {
5016                           xlo = -1;
5017                           break;
5018                         }
5019                     }
5020                 }
5021               else
5022                 {
5023                   t = TYPE_MIN_VALUE (type);
5024                   if (t)
5025                     neg_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t),
5026                                 &xlo, &xhi);
5027                   else
5028                     xlo = xhi = 0;
5029                   add_double (xlo, xhi,
5030                               TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
5031                               &xlo, &xhi);
5032                 }
5033
5034               if (xhi == 0 && xlo < (unsigned HOST_WIDE_INT) count)
5035                 BITARRAY_SET (cases_seen, xlo);
5036
5037               add_double (TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
5038                           1, 0,
5039                           &TREE_INT_CST_LOW (val), &TREE_INT_CST_HIGH (val));
5040             }
5041         }
5042     }
5043 }
5044
5045 /* Given a switch statement with an expression that is an enumeration
5046    type, warn if any of the enumeration type's literals are not
5047    covered by the case expressions of the switch.  Also, warn if there
5048    are any extra switch cases that are *not* elements of the
5049    enumerated type.
5050
5051    Historical note:
5052
5053    At one stage this function would: ``If all enumeration literals
5054    were covered by the case expressions, turn one of the expressions
5055    into the default expression since it should not be possible to fall
5056    through such a switch.''
5057
5058    That code has since been removed as: ``This optimization is
5059    disabled because it causes valid programs to fail.  ANSI C does not
5060    guarantee that an expression with enum type will have a value that
5061    is the same as one of the enumeration literals.''  */
5062
5063 void
5064 check_for_full_enumeration_handling (tree type)
5065 {
5066   struct case_node *n;
5067   tree chain;
5068
5069   /* True iff the selector type is a numbered set mode.  */
5070   int sparseness = 0;
5071
5072   /* The number of possible selector values.  */
5073   HOST_WIDE_INT size;
5074
5075   /* For each possible selector value. a one iff it has been matched
5076      by a case value alternative.  */
5077   unsigned char *cases_seen;
5078
5079   /* The allocated size of cases_seen, in chars.  */
5080   HOST_WIDE_INT bytes_needed;
5081
5082   size = all_cases_count (type, &sparseness);
5083   bytes_needed = (size + HOST_BITS_PER_CHAR) / HOST_BITS_PER_CHAR;
5084
5085   if (size > 0 && size < 600000
5086       /* We deliberately use calloc here, not cmalloc, so that we can suppress
5087          this optimization if we don't have enough memory rather than
5088          aborting, as xmalloc would do.  */
5089       && (cases_seen = really_call_calloc (bytes_needed, 1)) != NULL)
5090     {
5091       HOST_WIDE_INT i;
5092       tree v = TYPE_VALUES (type);
5093
5094       /* The time complexity of this code is normally O(N), where
5095          N being the number of members in the enumerated type.
5096          However, if type is an ENUMERAL_TYPE whose values do not
5097          increase monotonically, O(N*log(N)) time may be needed.  */
5098
5099       mark_seen_cases (type, cases_seen, size, sparseness);
5100
5101       for (i = 0; v != NULL_TREE && i < size; i++, v = TREE_CHAIN (v))
5102         if (BITARRAY_TEST (cases_seen, i) == 0)
5103           warning ("enumeration value `%s' not handled in switch",
5104                    IDENTIFIER_POINTER (TREE_PURPOSE (v)));
5105
5106       free (cases_seen);
5107     }
5108
5109   /* Now we go the other way around; we warn if there are case
5110      expressions that don't correspond to enumerators.  This can
5111      occur since C and C++ don't enforce type-checking of
5112      assignments to enumeration variables.  */
5113
5114   if (case_stack->data.case_stmt.case_list
5115       && case_stack->data.case_stmt.case_list->left)
5116     case_stack->data.case_stmt.case_list
5117       = case_tree2list (case_stack->data.case_stmt.case_list, 0);
5118   for (n = case_stack->data.case_stmt.case_list; n; n = n->right)
5119     {
5120       for (chain = TYPE_VALUES (type);
5121            chain && !tree_int_cst_equal (n->low, TREE_VALUE (chain));
5122            chain = TREE_CHAIN (chain))
5123         ;
5124
5125       if (!chain)
5126         {
5127           if (TYPE_NAME (type) == 0)
5128             warning ("case value `%ld' not in enumerated type",
5129                      (long) TREE_INT_CST_LOW (n->low));
5130           else
5131             warning ("case value `%ld' not in enumerated type `%s'",
5132                      (long) TREE_INT_CST_LOW (n->low),
5133                      IDENTIFIER_POINTER ((TREE_CODE (TYPE_NAME (type))
5134                                           == IDENTIFIER_NODE)
5135                                          ? TYPE_NAME (type)
5136                                          : DECL_NAME (TYPE_NAME (type))));
5137         }
5138       if (!tree_int_cst_equal (n->low, n->high))
5139         {
5140           for (chain = TYPE_VALUES (type);
5141                chain && !tree_int_cst_equal (n->high, TREE_VALUE (chain));
5142                chain = TREE_CHAIN (chain))
5143             ;
5144
5145           if (!chain)
5146             {
5147               if (TYPE_NAME (type) == 0)
5148                 warning ("case value `%ld' not in enumerated type",
5149                          (long) TREE_INT_CST_LOW (n->high));
5150               else
5151                 warning ("case value `%ld' not in enumerated type `%s'",
5152                          (long) TREE_INT_CST_LOW (n->high),
5153                          IDENTIFIER_POINTER ((TREE_CODE (TYPE_NAME (type))
5154                                               == IDENTIFIER_NODE)
5155                                              ? TYPE_NAME (type)
5156                                              : DECL_NAME (TYPE_NAME (type))));
5157             }
5158         }
5159     }
5160 }
5161
5162 \f
5163 /* Maximum number of case bit tests.  */
5164 #define MAX_CASE_BIT_TESTS  3
5165
5166 /* By default, enable case bit tests on targets with ashlsi3.  */
5167 #ifndef CASE_USE_BIT_TESTS
5168 #define CASE_USE_BIT_TESTS  (ashl_optab->handlers[word_mode].insn_code \
5169                              != CODE_FOR_nothing)
5170 #endif
5171
5172
5173 /* A case_bit_test represents a set of case nodes that may be
5174    selected from using a bit-wise comparison.  HI and LO hold
5175    the integer to be tested against, LABEL contains the label
5176    to jump to upon success and BITS counts the number of case
5177    nodes handled by this test, typically the number of bits
5178    set in HI:LO.  */
5179
5180 struct case_bit_test
5181 {
5182   HOST_WIDE_INT hi;
5183   HOST_WIDE_INT lo;
5184   rtx label;
5185   int bits;
5186 };
5187
5188 /* Determine whether "1 << x" is relatively cheap in word_mode.  */
5189
5190 static
5191 bool lshift_cheap_p (void)
5192 {
5193   static bool init = false;
5194   static bool cheap = true;
5195
5196   if (!init)
5197     {
5198       rtx reg = gen_rtx_REG (word_mode, 10000);
5199       int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET);
5200       cheap = cost < COSTS_N_INSNS (3);
5201       init = true;
5202     }
5203
5204   return cheap;
5205 }
5206
5207 /* Comparison function for qsort to order bit tests by decreasing
5208    number of case nodes, i.e. the node with the most cases gets
5209    tested first.  */
5210
5211 static
5212 int case_bit_test_cmp (const void *p1, const void *p2)
5213 {
5214   const struct case_bit_test *d1 = p1;
5215   const struct case_bit_test *d2 = p2;
5216
5217   return d2->bits - d1->bits;
5218 }
5219
5220 /*  Expand a switch statement by a short sequence of bit-wise
5221     comparisons.  "switch(x)" is effectively converted into
5222     "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
5223     integer constants.
5224
5225     INDEX_EXPR is the value being switched on, which is of
5226     type INDEX_TYPE.  MINVAL is the lowest case value of in
5227     the case nodes, of INDEX_TYPE type, and RANGE is highest
5228     value minus MINVAL, also of type INDEX_TYPE.  NODES is
5229     the set of case nodes, and DEFAULT_LABEL is the label to
5230     branch to should none of the cases match.
5231
5232     There *MUST* be MAX_CASE_BIT_TESTS or less unique case
5233     node targets.  */
5234
5235 static void
5236 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
5237                      tree range, case_node_ptr nodes, rtx default_label)
5238 {
5239   struct case_bit_test test[MAX_CASE_BIT_TESTS];
5240   enum machine_mode mode;
5241   rtx expr, index, label;
5242   unsigned int i,j,lo,hi;
5243   struct case_node *n;
5244   unsigned int count;
5245
5246   count = 0;
5247   for (n = nodes; n; n = n->right)
5248     {
5249       label = label_rtx (n->code_label);
5250       for (i = 0; i < count; i++)
5251         if (same_case_target_p (label, test[i].label))
5252           break;
5253
5254       if (i == count)
5255         {
5256           if (count >= MAX_CASE_BIT_TESTS)
5257             abort ();
5258           test[i].hi = 0;
5259           test[i].lo = 0;
5260           test[i].label = label;
5261           test[i].bits = 1;
5262           count++;
5263         }
5264       else
5265         test[i].bits++;
5266
5267       lo = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5268                                       n->low, minval)), 1);
5269       hi = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5270                                       n->high, minval)), 1);
5271       for (j = lo; j <= hi; j++)
5272         if (j >= HOST_BITS_PER_WIDE_INT)
5273           test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
5274         else
5275           test[i].lo |= (HOST_WIDE_INT) 1 << j;
5276     }
5277
5278   qsort (test, count, sizeof(*test), case_bit_test_cmp);
5279
5280   index_expr = fold (build (MINUS_EXPR, index_type,
5281                             convert (index_type, index_expr),
5282                             convert (index_type, minval)));
5283   index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
5284   emit_queue ();
5285   index = protect_from_queue (index, 0);
5286   do_pending_stack_adjust ();
5287
5288   mode = TYPE_MODE (index_type);
5289   expr = expand_expr (range, NULL_RTX, VOIDmode, 0);
5290   emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
5291                            default_label);
5292
5293   index = convert_to_mode (word_mode, index, 0);
5294   index = expand_binop (word_mode, ashl_optab, const1_rtx,
5295                         index, NULL_RTX, 1, OPTAB_WIDEN);
5296
5297   for (i = 0; i < count; i++)
5298     {
5299       expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
5300       expr = expand_binop (word_mode, and_optab, index, expr,
5301                            NULL_RTX, 1, OPTAB_WIDEN);
5302       emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
5303                                word_mode, 1, test[i].label);
5304     }
5305
5306   emit_jump (default_label);
5307 }
5308
5309 #ifndef HAVE_casesi
5310 #define HAVE_casesi 0
5311 #endif
5312
5313 #ifndef HAVE_tablejump
5314 #define HAVE_tablejump 0
5315 #endif
5316
5317 /* Terminate a case (Pascal) or switch (C) statement
5318    in which ORIG_INDEX is the expression to be tested.
5319    If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
5320    type as given in the source before any compiler conversions.
5321    Generate the code to test it and jump to the right place.  */
5322
5323 void
5324 expand_end_case_type (tree orig_index, tree orig_type)
5325 {
5326   tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
5327   rtx default_label = 0;
5328   struct case_node *n, *m;
5329   unsigned int count, uniq;
5330   rtx index;
5331   rtx table_label;
5332   int ncases;
5333   rtx *labelvec;
5334   int i;
5335   rtx before_case, end, lab;
5336   struct nesting *thiscase = case_stack;
5337   tree index_expr, index_type;
5338   bool exit_done = false;
5339   int unsignedp;
5340
5341   /* Don't crash due to previous errors.  */
5342   if (thiscase == NULL)
5343     return;
5344
5345   index_expr = thiscase->data.case_stmt.index_expr;
5346   index_type = TREE_TYPE (index_expr);
5347   unsignedp = TYPE_UNSIGNED (index_type);
5348   if (orig_type == NULL)
5349     orig_type = TREE_TYPE (orig_index);
5350
5351   do_pending_stack_adjust ();
5352
5353   /* This might get a spurious warning in the presence of a syntax error;
5354      it could be fixed by moving the call to check_seenlabel after the
5355      check for error_mark_node, and copying the code of check_seenlabel that
5356      deals with case_stack->data.case_stmt.line_number_status /
5357      restore_line_number_status in front of the call to end_cleanup_deferral;
5358      However, this might miss some useful warnings in the presence of
5359      non-syntax errors.  */
5360   check_seenlabel ();
5361
5362   /* An ERROR_MARK occurs for various reasons including invalid data type.  */
5363   if (index_type != error_mark_node)
5364     {
5365       /* If the switch expression was an enumerated type, check that
5366          exactly all enumeration literals are covered by the cases.
5367          The check is made when -Wswitch was specified and there is no
5368          default case, or when -Wswitch-enum was specified.  */
5369       if (((warn_switch && !thiscase->data.case_stmt.default_label)
5370            || warn_switch_enum)
5371           && TREE_CODE (orig_type) == ENUMERAL_TYPE
5372           && TREE_CODE (index_expr) != INTEGER_CST)
5373         check_for_full_enumeration_handling (orig_type);
5374
5375       if (warn_switch_default && !thiscase->data.case_stmt.default_label)
5376         warning ("switch missing default case");
5377
5378       /* If we don't have a default-label, create one here,
5379          after the body of the switch.  */
5380       if (thiscase->data.case_stmt.default_label == 0)
5381         {
5382           thiscase->data.case_stmt.default_label
5383             = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
5384           /* Share the exit label if possible.  */
5385           if (thiscase->exit_label)
5386             {
5387               SET_DECL_RTL (thiscase->data.case_stmt.default_label,
5388                             thiscase->exit_label);
5389               exit_done = true;
5390             }
5391           expand_label (thiscase->data.case_stmt.default_label);
5392         }
5393       default_label = label_rtx (thiscase->data.case_stmt.default_label);
5394
5395       before_case = get_last_insn ();
5396
5397       if (thiscase->data.case_stmt.case_list
5398           && thiscase->data.case_stmt.case_list->left)
5399         thiscase->data.case_stmt.case_list
5400           = case_tree2list (thiscase->data.case_stmt.case_list, 0);
5401
5402       /* Simplify the case-list before we count it.  */
5403       group_case_nodes (thiscase->data.case_stmt.case_list);
5404       strip_default_case_nodes (&thiscase->data.case_stmt.case_list,
5405                                 default_label);
5406
5407       /* Get upper and lower bounds of case values.
5408          Also convert all the case values to the index expr's data type.  */
5409
5410       uniq = 0;
5411       count = 0;
5412       for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5413         {
5414           /* Check low and high label values are integers.  */
5415           if (TREE_CODE (n->low) != INTEGER_CST)
5416             abort ();
5417           if (TREE_CODE (n->high) != INTEGER_CST)
5418             abort ();
5419
5420           n->low = convert (index_type, n->low);
5421           n->high = convert (index_type, n->high);
5422
5423           /* Count the elements and track the largest and smallest
5424              of them (treating them as signed even if they are not).  */
5425           if (count++ == 0)
5426             {
5427               minval = n->low;
5428               maxval = n->high;
5429             }
5430           else
5431             {
5432               if (INT_CST_LT (n->low, minval))
5433                 minval = n->low;
5434               if (INT_CST_LT (maxval, n->high))
5435                 maxval = n->high;
5436             }
5437           /* A range counts double, since it requires two compares.  */
5438           if (! tree_int_cst_equal (n->low, n->high))
5439             count++;
5440
5441           /* Count the number of unique case node targets.  */
5442           uniq++;
5443           lab = label_rtx (n->code_label);
5444           for (m = thiscase->data.case_stmt.case_list; m != n; m = m->right)
5445             if (same_case_target_p (label_rtx (m->code_label), lab))
5446               {
5447                 uniq--;
5448                 break;
5449               }
5450         }
5451
5452       /* Compute span of values.  */
5453       if (count != 0)
5454         range = fold (build (MINUS_EXPR, index_type, maxval, minval));
5455
5456       end_cleanup_deferral ();
5457
5458       if (count == 0)
5459         {
5460           expand_expr (index_expr, const0_rtx, VOIDmode, 0);
5461           emit_queue ();
5462           emit_jump (default_label);
5463         }
5464
5465       /* Try implementing this switch statement by a short sequence of
5466          bit-wise comparisons.  However, we let the binary-tree case
5467          below handle constant index expressions.  */
5468       else if (CASE_USE_BIT_TESTS
5469                && ! TREE_CONSTANT (index_expr)
5470                && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
5471                && compare_tree_int (range, 0) > 0
5472                && lshift_cheap_p ()
5473                && ((uniq == 1 && count >= 3)
5474                    || (uniq == 2 && count >= 5)
5475                    || (uniq == 3 && count >= 6)))
5476         {
5477           /* Optimize the case where all the case values fit in a
5478              word without having to subtract MINVAL.  In this case,
5479              we can optimize away the subtraction.  */
5480           if (compare_tree_int (minval, 0) > 0
5481               && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
5482             {
5483               minval = integer_zero_node;
5484               range = maxval;
5485             }
5486           emit_case_bit_tests (index_type, index_expr, minval, range,
5487                                thiscase->data.case_stmt.case_list,
5488                                default_label);
5489         }
5490
5491       /* If range of values is much bigger than number of values,
5492          make a sequence of conditional branches instead of a dispatch.
5493          If the switch-index is a constant, do it this way
5494          because we can optimize it.  */
5495
5496       else if (count < case_values_threshold ()
5497                || compare_tree_int (range,
5498                                     (optimize_size ? 3 : 10) * count) > 0
5499                /* RANGE may be signed, and really large ranges will show up
5500                   as negative numbers.  */
5501                || compare_tree_int (range, 0) < 0
5502 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
5503                || flag_pic
5504 #endif
5505                || TREE_CONSTANT (index_expr)
5506                /* If neither casesi or tablejump is available, we can
5507                   only go this way.  */
5508                || (!HAVE_casesi && !HAVE_tablejump))
5509         {
5510           index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
5511
5512           /* If the index is a short or char that we do not have
5513              an insn to handle comparisons directly, convert it to
5514              a full integer now, rather than letting each comparison
5515              generate the conversion.  */
5516
5517           if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
5518               && ! have_insn_for (COMPARE, GET_MODE (index)))
5519             {
5520               enum machine_mode wider_mode;
5521               for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
5522                    wider_mode = GET_MODE_WIDER_MODE (wider_mode))
5523                 if (have_insn_for (COMPARE, wider_mode))
5524                   {
5525                     index = convert_to_mode (wider_mode, index, unsignedp);
5526                     break;
5527                   }
5528             }
5529
5530           emit_queue ();
5531           do_pending_stack_adjust ();
5532
5533           index = protect_from_queue (index, 0);
5534           if (GET_CODE (index) == MEM)
5535             index = copy_to_reg (index);
5536           if (GET_CODE (index) == CONST_INT
5537               || TREE_CODE (index_expr) == INTEGER_CST)
5538             {
5539               /* Make a tree node with the proper constant value
5540                  if we don't already have one.  */
5541               if (TREE_CODE (index_expr) != INTEGER_CST)
5542                 {
5543                   index_expr
5544                     = build_int_2 (INTVAL (index),
5545                                    unsignedp || INTVAL (index) >= 0 ? 0 : -1);
5546                   index_expr = convert (index_type, index_expr);
5547                 }
5548
5549               /* For constant index expressions we need only
5550                  issue an unconditional branch to the appropriate
5551                  target code.  The job of removing any unreachable
5552                  code is left to the optimization phase if the
5553                  "-O" option is specified.  */
5554               for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5555                 if (! tree_int_cst_lt (index_expr, n->low)
5556                     && ! tree_int_cst_lt (n->high, index_expr))
5557                   break;
5558
5559               if (n)
5560                 emit_jump (label_rtx (n->code_label));
5561               else
5562                 emit_jump (default_label);
5563             }
5564           else
5565             {
5566               /* If the index expression is not constant we generate
5567                  a binary decision tree to select the appropriate
5568                  target code.  This is done as follows:
5569
5570                  The list of cases is rearranged into a binary tree,
5571                  nearly optimal assuming equal probability for each case.
5572
5573                  The tree is transformed into RTL, eliminating
5574                  redundant test conditions at the same time.
5575
5576                  If program flow could reach the end of the
5577                  decision tree an unconditional jump to the
5578                  default code is emitted.  */
5579
5580               use_cost_table
5581                 = (TREE_CODE (orig_type) != ENUMERAL_TYPE
5582                    && estimate_case_costs (thiscase->data.case_stmt.case_list));
5583               balance_case_nodes (&thiscase->data.case_stmt.case_list, NULL);
5584               emit_case_nodes (index, thiscase->data.case_stmt.case_list,
5585                                default_label, index_type);
5586               emit_jump_if_reachable (default_label);
5587             }
5588         }
5589       else
5590         {
5591           table_label = gen_label_rtx ();
5592           if (! try_casesi (index_type, index_expr, minval, range,
5593                             table_label, default_label))
5594             {
5595               index_type = thiscase->data.case_stmt.nominal_type;
5596
5597               /* Index jumptables from zero for suitable values of
5598                  minval to avoid a subtraction.  */
5599               if (! optimize_size
5600                   && compare_tree_int (minval, 0) > 0
5601                   && compare_tree_int (minval, 3) < 0)
5602                 {
5603                   minval = integer_zero_node;
5604                   range = maxval;
5605                 }
5606
5607               if (! try_tablejump (index_type, index_expr, minval, range,
5608                                    table_label, default_label))
5609                 abort ();
5610             }
5611
5612           /* Get table of labels to jump to, in order of case index.  */
5613
5614           ncases = tree_low_cst (range, 0) + 1;
5615           labelvec = alloca (ncases * sizeof (rtx));
5616           memset (labelvec, 0, ncases * sizeof (rtx));
5617
5618           for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5619             {
5620               /* Compute the low and high bounds relative to the minimum
5621                  value since that should fit in a HOST_WIDE_INT while the
5622                  actual values may not.  */
5623               HOST_WIDE_INT i_low
5624                 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5625                                              n->low, minval)), 1);
5626               HOST_WIDE_INT i_high
5627                 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5628                                              n->high, minval)), 1);
5629               HOST_WIDE_INT i;
5630
5631               for (i = i_low; i <= i_high; i ++)
5632                 labelvec[i]
5633                   = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
5634             }
5635
5636           /* Fill in the gaps with the default.  */
5637           for (i = 0; i < ncases; i++)
5638             if (labelvec[i] == 0)
5639               labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
5640
5641           /* Output the table.  */
5642           emit_label (table_label);
5643
5644           if (CASE_VECTOR_PC_RELATIVE || flag_pic)
5645             emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
5646                                                    gen_rtx_LABEL_REF (Pmode, table_label),
5647                                                    gen_rtvec_v (ncases, labelvec),
5648                                                    const0_rtx, const0_rtx));
5649           else
5650             emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
5651                                               gen_rtvec_v (ncases, labelvec)));
5652
5653           /* If the case insn drops through the table,
5654              after the table we must jump to the default-label.
5655              Otherwise record no drop-through after the table.  */
5656 #ifdef CASE_DROPS_THROUGH
5657           emit_jump (default_label);
5658 #else
5659           emit_barrier ();
5660 #endif
5661         }
5662
5663       before_case = NEXT_INSN (before_case);
5664       end = get_last_insn ();
5665       if (squeeze_notes (&before_case, &end))
5666         abort ();
5667       reorder_insns (before_case, end,
5668                      thiscase->data.case_stmt.start);
5669     }
5670   else
5671     end_cleanup_deferral ();
5672
5673   if (thiscase->exit_label && !exit_done)
5674     emit_label (thiscase->exit_label);
5675
5676   POPSTACK (case_stack);
5677
5678   free_temp_slots ();
5679 }
5680
5681 /* Convert the tree NODE into a list linked by the right field, with the left
5682    field zeroed.  RIGHT is used for recursion; it is a list to be placed
5683    rightmost in the resulting list.  */
5684
5685 static struct case_node *
5686 case_tree2list (struct case_node *node, struct case_node *right)
5687 {
5688   struct case_node *left;
5689
5690   if (node->right)
5691     right = case_tree2list (node->right, right);
5692
5693   node->right = right;
5694   if ((left = node->left))
5695     {
5696       node->left = 0;
5697       return case_tree2list (left, node);
5698     }
5699
5700   return node;
5701 }
5702
5703 /* Generate code to jump to LABEL if OP1 and OP2 are equal.  */
5704
5705 static void
5706 do_jump_if_equal (rtx op1, rtx op2, rtx label, int unsignedp)
5707 {
5708   if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
5709     {
5710       if (op1 == op2)
5711         emit_jump (label);
5712     }
5713   else
5714     emit_cmp_and_jump_insns (op1, op2, EQ, NULL_RTX,
5715                              (GET_MODE (op1) == VOIDmode
5716                              ? GET_MODE (op2) : GET_MODE (op1)),
5717                              unsignedp, label);
5718 }
5719 \f
5720 /* Not all case values are encountered equally.  This function
5721    uses a heuristic to weight case labels, in cases where that
5722    looks like a reasonable thing to do.
5723
5724    Right now, all we try to guess is text, and we establish the
5725    following weights:
5726
5727         chars above space:      16
5728         digits:                 16
5729         default:                12
5730         space, punct:           8
5731         tab:                    4
5732         newline:                2
5733         other "\" chars:        1
5734         remaining chars:        0
5735
5736    If we find any cases in the switch that are not either -1 or in the range
5737    of valid ASCII characters, or are control characters other than those
5738    commonly used with "\", don't treat this switch scanning text.
5739
5740    Return 1 if these nodes are suitable for cost estimation, otherwise
5741    return 0.  */
5742
5743 static int
5744 estimate_case_costs (case_node_ptr node)
5745 {
5746   tree min_ascii = integer_minus_one_node;
5747   tree max_ascii = convert (TREE_TYPE (node->high), build_int_2 (127, 0));
5748   case_node_ptr n;
5749   int i;
5750
5751   /* If we haven't already made the cost table, make it now.  Note that the
5752      lower bound of the table is -1, not zero.  */
5753
5754   if (! cost_table_initialized)
5755     {
5756       cost_table_initialized = 1;
5757
5758       for (i = 0; i < 128; i++)
5759         {
5760           if (ISALNUM (i))
5761             COST_TABLE (i) = 16;
5762           else if (ISPUNCT (i))
5763             COST_TABLE (i) = 8;
5764           else if (ISCNTRL (i))
5765             COST_TABLE (i) = -1;
5766         }
5767
5768       COST_TABLE (' ') = 8;
5769       COST_TABLE ('\t') = 4;
5770       COST_TABLE ('\0') = 4;
5771       COST_TABLE ('\n') = 2;
5772       COST_TABLE ('\f') = 1;
5773       COST_TABLE ('\v') = 1;
5774       COST_TABLE ('\b') = 1;
5775     }
5776
5777   /* See if all the case expressions look like text.  It is text if the
5778      constant is >= -1 and the highest constant is <= 127.  Do all comparisons
5779      as signed arithmetic since we don't want to ever access cost_table with a
5780      value less than -1.  Also check that none of the constants in a range
5781      are strange control characters.  */
5782
5783   for (n = node; n; n = n->right)
5784     {
5785       if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high))
5786         return 0;
5787
5788       for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
5789            i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
5790         if (COST_TABLE (i) < 0)
5791           return 0;
5792     }
5793
5794   /* All interesting values are within the range of interesting
5795      ASCII characters.  */
5796   return 1;
5797 }
5798
5799 /* Determine whether two case labels branch to the same target.  */
5800
5801 static bool
5802 same_case_target_p (rtx l1, rtx l2)
5803 {
5804   rtx i1, i2;
5805
5806   if (l1 == l2)
5807     return true;
5808
5809   i1 = next_real_insn (l1);
5810   i2 = next_real_insn (l2);
5811   if (i1 == i2)
5812     return true;
5813
5814   if (i1 && simplejump_p (i1))
5815     {
5816       l1 = XEXP (SET_SRC (PATTERN (i1)), 0);
5817     }
5818
5819   if (i2 && simplejump_p (i2))
5820     {
5821       l2 = XEXP (SET_SRC (PATTERN (i2)), 0);
5822     }
5823   return l1 == l2;
5824 }
5825
5826 /* Delete nodes that branch to the default label from a list of
5827    case nodes.  Eg. case 5: default: becomes just default:  */
5828
5829 static void
5830 strip_default_case_nodes (case_node_ptr *prev, rtx deflab)
5831 {
5832   case_node_ptr ptr;
5833
5834   while (*prev)
5835     {
5836       ptr = *prev;
5837       if (same_case_target_p (label_rtx (ptr->code_label), deflab))
5838         *prev = ptr->right;
5839       else
5840         prev = &ptr->right;
5841     }
5842 }
5843
5844 /* Scan an ordered list of case nodes
5845    combining those with consecutive values or ranges.
5846
5847    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
5848
5849 static void
5850 group_case_nodes (case_node_ptr head)
5851 {
5852   case_node_ptr node = head;
5853
5854   while (node)
5855     {
5856       rtx lab = label_rtx (node->code_label);
5857       case_node_ptr np = node;
5858
5859       /* Try to group the successors of NODE with NODE.  */
5860       while (((np = np->right) != 0)
5861              /* Do they jump to the same place?  */
5862              && same_case_target_p (label_rtx (np->code_label), lab)
5863              /* Are their ranges consecutive?  */
5864              && tree_int_cst_equal (np->low,
5865                                     fold (build (PLUS_EXPR,
5866                                                  TREE_TYPE (node->high),
5867                                                  node->high,
5868                                                  integer_one_node)))
5869              /* An overflow is not consecutive.  */
5870              && tree_int_cst_lt (node->high,
5871                                  fold (build (PLUS_EXPR,
5872                                               TREE_TYPE (node->high),
5873                                               node->high,
5874                                               integer_one_node))))
5875         {
5876           node->high = np->high;
5877         }
5878       /* NP is the first node after NODE which can't be grouped with it.
5879          Delete the nodes in between, and move on to that node.  */
5880       node->right = np;
5881       node = np;
5882     }
5883 }
5884
5885 /* Take an ordered list of case nodes
5886    and transform them into a near optimal binary tree,
5887    on the assumption that any target code selection value is as
5888    likely as any other.
5889
5890    The transformation is performed by splitting the ordered
5891    list into two equal sections plus a pivot.  The parts are
5892    then attached to the pivot as left and right branches.  Each
5893    branch is then transformed recursively.  */
5894
5895 static void
5896 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
5897 {
5898   case_node_ptr np;
5899
5900   np = *head;
5901   if (np)
5902     {
5903       int cost = 0;
5904       int i = 0;
5905       int ranges = 0;
5906       case_node_ptr *npp;
5907       case_node_ptr left;
5908
5909       /* Count the number of entries on branch.  Also count the ranges.  */
5910
5911       while (np)
5912         {
5913           if (!tree_int_cst_equal (np->low, np->high))
5914             {
5915               ranges++;
5916               if (use_cost_table)
5917                 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
5918             }
5919
5920           if (use_cost_table)
5921             cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
5922
5923           i++;
5924           np = np->right;
5925         }
5926
5927       if (i > 2)
5928         {
5929           /* Split this list if it is long enough for that to help.  */
5930           npp = head;
5931           left = *npp;
5932           if (use_cost_table)
5933             {
5934               /* Find the place in the list that bisects the list's total cost,
5935                  Here I gets half the total cost.  */
5936               int n_moved = 0;
5937               i = (cost + 1) / 2;
5938               while (1)
5939                 {
5940                   /* Skip nodes while their cost does not reach that amount.  */
5941                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
5942                     i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
5943                   i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
5944                   if (i <= 0)
5945                     break;
5946                   npp = &(*npp)->right;
5947                   n_moved += 1;
5948                 }
5949               if (n_moved == 0)
5950                 {
5951                   /* Leave this branch lopsided, but optimize left-hand
5952                      side and fill in `parent' fields for right-hand side.  */
5953                   np = *head;
5954                   np->parent = parent;
5955                   balance_case_nodes (&np->left, np);
5956                   for (; np->right; np = np->right)
5957                     np->right->parent = np;
5958                   return;
5959                 }
5960             }
5961           /* If there are just three nodes, split at the middle one.  */
5962           else if (i == 3)
5963             npp = &(*npp)->right;
5964           else
5965             {
5966               /* Find the place in the list that bisects the list's total cost,
5967                  where ranges count as 2.
5968                  Here I gets half the total cost.  */
5969               i = (i + ranges + 1) / 2;
5970               while (1)
5971                 {
5972                   /* Skip nodes while their cost does not reach that amount.  */
5973                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
5974                     i--;
5975                   i--;
5976                   if (i <= 0)
5977                     break;
5978                   npp = &(*npp)->right;
5979                 }
5980             }
5981           *head = np = *npp;
5982           *npp = 0;
5983           np->parent = parent;
5984           np->left = left;
5985
5986           /* Optimize each of the two split parts.  */
5987           balance_case_nodes (&np->left, np);
5988           balance_case_nodes (&np->right, np);
5989         }
5990       else
5991         {
5992           /* Else leave this branch as one level,
5993              but fill in `parent' fields.  */
5994           np = *head;
5995           np->parent = parent;
5996           for (; np->right; np = np->right)
5997             np->right->parent = np;
5998         }
5999     }
6000 }
6001 \f
6002 /* Search the parent sections of the case node tree
6003    to see if a test for the lower bound of NODE would be redundant.
6004    INDEX_TYPE is the type of the index expression.
6005
6006    The instructions to generate the case decision tree are
6007    output in the same order as nodes are processed so it is
6008    known that if a parent node checks the range of the current
6009    node minus one that the current node is bounded at its lower
6010    span.  Thus the test would be redundant.  */
6011
6012 static int
6013 node_has_low_bound (case_node_ptr node, tree index_type)
6014 {
6015   tree low_minus_one;
6016   case_node_ptr pnode;
6017
6018   /* If the lower bound of this node is the lowest value in the index type,
6019      we need not test it.  */
6020
6021   if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
6022     return 1;
6023
6024   /* If this node has a left branch, the value at the left must be less
6025      than that at this node, so it cannot be bounded at the bottom and
6026      we need not bother testing any further.  */
6027
6028   if (node->left)
6029     return 0;
6030
6031   low_minus_one = fold (build (MINUS_EXPR, TREE_TYPE (node->low),
6032                                node->low, integer_one_node));
6033
6034   /* If the subtraction above overflowed, we can't verify anything.
6035      Otherwise, look for a parent that tests our value - 1.  */
6036
6037   if (! tree_int_cst_lt (low_minus_one, node->low))
6038     return 0;
6039
6040   for (pnode = node->parent; pnode; pnode = pnode->parent)
6041     if (tree_int_cst_equal (low_minus_one, pnode->high))
6042       return 1;
6043
6044   return 0;
6045 }
6046
6047 /* Search the parent sections of the case node tree
6048    to see if a test for the upper bound of NODE would be redundant.
6049    INDEX_TYPE is the type of the index expression.
6050
6051    The instructions to generate the case decision tree are
6052    output in the same order as nodes are processed so it is
6053    known that if a parent node checks the range of the current
6054    node plus one that the current node is bounded at its upper
6055    span.  Thus the test would be redundant.  */
6056
6057 static int
6058 node_has_high_bound (case_node_ptr node, tree index_type)
6059 {
6060   tree high_plus_one;
6061   case_node_ptr pnode;
6062
6063   /* If there is no upper bound, obviously no test is needed.  */
6064
6065   if (TYPE_MAX_VALUE (index_type) == NULL)
6066     return 1;
6067
6068   /* If the upper bound of this node is the highest value in the type
6069      of the index expression, we need not test against it.  */
6070
6071   if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
6072     return 1;
6073
6074   /* If this node has a right branch, the value at the right must be greater
6075      than that at this node, so it cannot be bounded at the top and
6076      we need not bother testing any further.  */
6077
6078   if (node->right)
6079     return 0;
6080
6081   high_plus_one = fold (build (PLUS_EXPR, TREE_TYPE (node->high),
6082                                node->high, integer_one_node));
6083
6084   /* If the addition above overflowed, we can't verify anything.
6085      Otherwise, look for a parent that tests our value + 1.  */
6086
6087   if (! tree_int_cst_lt (node->high, high_plus_one))
6088     return 0;
6089
6090   for (pnode = node->parent; pnode; pnode = pnode->parent)
6091     if (tree_int_cst_equal (high_plus_one, pnode->low))
6092       return 1;
6093
6094   return 0;
6095 }
6096
6097 /* Search the parent sections of the
6098    case node tree to see if both tests for the upper and lower
6099    bounds of NODE would be redundant.  */
6100
6101 static int
6102 node_is_bounded (case_node_ptr node, tree index_type)
6103 {
6104   return (node_has_low_bound (node, index_type)
6105           && node_has_high_bound (node, index_type));
6106 }
6107
6108 /*  Emit an unconditional jump to LABEL unless it would be dead code.  */
6109
6110 static void
6111 emit_jump_if_reachable (rtx label)
6112 {
6113   if (GET_CODE (get_last_insn ()) != BARRIER)
6114     emit_jump (label);
6115 }
6116 \f
6117 /* Emit step-by-step code to select a case for the value of INDEX.
6118    The thus generated decision tree follows the form of the
6119    case-node binary tree NODE, whose nodes represent test conditions.
6120    INDEX_TYPE is the type of the index of the switch.
6121
6122    Care is taken to prune redundant tests from the decision tree
6123    by detecting any boundary conditions already checked by
6124    emitted rtx.  (See node_has_high_bound, node_has_low_bound
6125    and node_is_bounded, above.)
6126
6127    Where the test conditions can be shown to be redundant we emit
6128    an unconditional jump to the target code.  As a further
6129    optimization, the subordinates of a tree node are examined to
6130    check for bounded nodes.  In this case conditional and/or
6131    unconditional jumps as a result of the boundary check for the
6132    current node are arranged to target the subordinates associated
6133    code for out of bound conditions on the current node.
6134
6135    We can assume that when control reaches the code generated here,
6136    the index value has already been compared with the parents
6137    of this node, and determined to be on the same side of each parent
6138    as this node is.  Thus, if this node tests for the value 51,
6139    and a parent tested for 52, we don't need to consider
6140    the possibility of a value greater than 51.  If another parent
6141    tests for the value 50, then this node need not test anything.  */
6142
6143 static void
6144 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
6145                  tree index_type)
6146 {
6147   /* If INDEX has an unsigned type, we must make unsigned branches.  */
6148   int unsignedp = TYPE_UNSIGNED (index_type);
6149   enum machine_mode mode = GET_MODE (index);
6150   enum machine_mode imode = TYPE_MODE (index_type);
6151
6152   /* See if our parents have already tested everything for us.
6153      If they have, emit an unconditional jump for this node.  */
6154   if (node_is_bounded (node, index_type))
6155     emit_jump (label_rtx (node->code_label));
6156
6157   else if (tree_int_cst_equal (node->low, node->high))
6158     {
6159       /* Node is single valued.  First see if the index expression matches
6160          this node and then check our children, if any.  */
6161
6162       do_jump_if_equal (index,
6163                         convert_modes (mode, imode,
6164                                        expand_expr (node->low, NULL_RTX,
6165                                                     VOIDmode, 0),
6166                                        unsignedp),
6167                         label_rtx (node->code_label), unsignedp);
6168
6169       if (node->right != 0 && node->left != 0)
6170         {
6171           /* This node has children on both sides.
6172              Dispatch to one side or the other
6173              by comparing the index value with this node's value.
6174              If one subtree is bounded, check that one first,
6175              so we can avoid real branches in the tree.  */
6176
6177           if (node_is_bounded (node->right, index_type))
6178             {
6179               emit_cmp_and_jump_insns (index,
6180                                        convert_modes
6181                                        (mode, imode,
6182                                         expand_expr (node->high, NULL_RTX,
6183                                                      VOIDmode, 0),
6184                                         unsignedp),
6185                                        GT, NULL_RTX, mode, unsignedp,
6186                                        label_rtx (node->right->code_label));
6187               emit_case_nodes (index, node->left, default_label, index_type);
6188             }
6189
6190           else if (node_is_bounded (node->left, index_type))
6191             {
6192               emit_cmp_and_jump_insns (index,
6193                                        convert_modes
6194                                        (mode, imode,
6195                                         expand_expr (node->high, NULL_RTX,
6196                                                      VOIDmode, 0),
6197                                         unsignedp),
6198                                        LT, NULL_RTX, mode, unsignedp,
6199                                        label_rtx (node->left->code_label));
6200               emit_case_nodes (index, node->right, default_label, index_type);
6201             }
6202
6203           /* If both children are single-valued cases with no
6204              children, finish up all the work.  This way, we can save
6205              one ordered comparison.  */
6206           else if (tree_int_cst_equal (node->right->low, node->right->high)
6207                    && node->right->left == 0
6208                    && node->right->right == 0
6209                    && tree_int_cst_equal (node->left->low, node->left->high)
6210                    && node->left->left == 0
6211                    && node->left->right == 0)
6212             {
6213               /* Neither node is bounded.  First distinguish the two sides;
6214                  then emit the code for one side at a time.  */
6215
6216               /* See if the value matches what the right hand side
6217                  wants.  */
6218               do_jump_if_equal (index,
6219                                 convert_modes (mode, imode,
6220                                                expand_expr (node->right->low,
6221                                                             NULL_RTX,
6222                                                             VOIDmode, 0),
6223                                                unsignedp),
6224                                 label_rtx (node->right->code_label),
6225                                 unsignedp);
6226
6227               /* See if the value matches what the left hand side
6228                  wants.  */
6229               do_jump_if_equal (index,
6230                                 convert_modes (mode, imode,
6231                                                expand_expr (node->left->low,
6232                                                             NULL_RTX,
6233                                                             VOIDmode, 0),
6234                                                unsignedp),
6235                                 label_rtx (node->left->code_label),
6236                                 unsignedp);
6237             }
6238
6239           else
6240             {
6241               /* Neither node is bounded.  First distinguish the two sides;
6242                  then emit the code for one side at a time.  */
6243
6244               tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
6245
6246               /* See if the value is on the right.  */
6247               emit_cmp_and_jump_insns (index,
6248                                        convert_modes
6249                                        (mode, imode,
6250                                         expand_expr (node->high, NULL_RTX,
6251                                                      VOIDmode, 0),
6252                                         unsignedp),
6253                                        GT, NULL_RTX, mode, unsignedp,
6254                                        label_rtx (test_label));
6255
6256               /* Value must be on the left.
6257                  Handle the left-hand subtree.  */
6258               emit_case_nodes (index, node->left, default_label, index_type);
6259               /* If left-hand subtree does nothing,
6260                  go to default.  */
6261               emit_jump_if_reachable (default_label);
6262
6263               /* Code branches here for the right-hand subtree.  */
6264               expand_label (test_label);
6265               emit_case_nodes (index, node->right, default_label, index_type);
6266             }
6267         }
6268
6269       else if (node->right != 0 && node->left == 0)
6270         {
6271           /* Here we have a right child but no left so we issue conditional
6272              branch to default and process the right child.
6273
6274              Omit the conditional branch to default if we it avoid only one
6275              right child; it costs too much space to save so little time.  */
6276
6277           if (node->right->right || node->right->left
6278               || !tree_int_cst_equal (node->right->low, node->right->high))
6279             {
6280               if (!node_has_low_bound (node, index_type))
6281                 {
6282                   emit_cmp_and_jump_insns (index,
6283                                            convert_modes
6284                                            (mode, imode,
6285                                             expand_expr (node->high, NULL_RTX,
6286                                                          VOIDmode, 0),
6287                                             unsignedp),
6288                                            LT, NULL_RTX, mode, unsignedp,
6289                                            default_label);
6290                 }
6291
6292               emit_case_nodes (index, node->right, default_label, index_type);
6293             }
6294           else
6295             /* We cannot process node->right normally
6296                since we haven't ruled out the numbers less than
6297                this node's value.  So handle node->right explicitly.  */
6298             do_jump_if_equal (index,
6299                               convert_modes
6300                               (mode, imode,
6301                                expand_expr (node->right->low, NULL_RTX,
6302                                             VOIDmode, 0),
6303                                unsignedp),
6304                               label_rtx (node->right->code_label), unsignedp);
6305         }
6306
6307       else if (node->right == 0 && node->left != 0)
6308         {
6309           /* Just one subtree, on the left.  */
6310           if (node->left->left || node->left->right
6311               || !tree_int_cst_equal (node->left->low, node->left->high))
6312             {
6313               if (!node_has_high_bound (node, index_type))
6314                 {
6315                   emit_cmp_and_jump_insns (index,
6316                                            convert_modes
6317                                            (mode, imode,
6318                                             expand_expr (node->high, NULL_RTX,
6319                                                          VOIDmode, 0),
6320                                             unsignedp),
6321                                            GT, NULL_RTX, mode, unsignedp,
6322                                            default_label);
6323                 }
6324
6325               emit_case_nodes (index, node->left, default_label, index_type);
6326             }
6327           else
6328             /* We cannot process node->left normally
6329                since we haven't ruled out the numbers less than
6330                this node's value.  So handle node->left explicitly.  */
6331             do_jump_if_equal (index,
6332                               convert_modes
6333                               (mode, imode,
6334                                expand_expr (node->left->low, NULL_RTX,
6335                                             VOIDmode, 0),
6336                                unsignedp),
6337                               label_rtx (node->left->code_label), unsignedp);
6338         }
6339     }
6340   else
6341     {
6342       /* Node is a range.  These cases are very similar to those for a single
6343          value, except that we do not start by testing whether this node
6344          is the one to branch to.  */
6345
6346       if (node->right != 0 && node->left != 0)
6347         {
6348           /* Node has subtrees on both sides.
6349              If the right-hand subtree is bounded,
6350              test for it first, since we can go straight there.
6351              Otherwise, we need to make a branch in the control structure,
6352              then handle the two subtrees.  */
6353           tree test_label = 0;
6354
6355           if (node_is_bounded (node->right, index_type))
6356             /* Right hand node is fully bounded so we can eliminate any
6357                testing and branch directly to the target code.  */
6358             emit_cmp_and_jump_insns (index,
6359                                      convert_modes
6360                                      (mode, imode,
6361                                       expand_expr (node->high, NULL_RTX,
6362                                                    VOIDmode, 0),
6363                                       unsignedp),
6364                                      GT, NULL_RTX, mode, unsignedp,
6365                                      label_rtx (node->right->code_label));
6366           else
6367             {
6368               /* Right hand node requires testing.
6369                  Branch to a label where we will handle it later.  */
6370
6371               test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
6372               emit_cmp_and_jump_insns (index,
6373                                        convert_modes
6374                                        (mode, imode,
6375                                         expand_expr (node->high, NULL_RTX,
6376                                                      VOIDmode, 0),
6377                                         unsignedp),
6378                                        GT, NULL_RTX, mode, unsignedp,
6379                                        label_rtx (test_label));
6380             }
6381
6382           /* Value belongs to this node or to the left-hand subtree.  */
6383
6384           emit_cmp_and_jump_insns (index,
6385                                    convert_modes
6386                                    (mode, imode,
6387                                     expand_expr (node->low, NULL_RTX,
6388                                                  VOIDmode, 0),
6389                                     unsignedp),
6390                                    GE, NULL_RTX, mode, unsignedp,
6391                                    label_rtx (node->code_label));
6392
6393           /* Handle the left-hand subtree.  */
6394           emit_case_nodes (index, node->left, default_label, index_type);
6395
6396           /* If right node had to be handled later, do that now.  */
6397
6398           if (test_label)
6399             {
6400               /* If the left-hand subtree fell through,
6401                  don't let it fall into the right-hand subtree.  */
6402               emit_jump_if_reachable (default_label);
6403
6404               expand_label (test_label);
6405               emit_case_nodes (index, node->right, default_label, index_type);
6406             }
6407         }
6408
6409       else if (node->right != 0 && node->left == 0)
6410         {
6411           /* Deal with values to the left of this node,
6412              if they are possible.  */
6413           if (!node_has_low_bound (node, index_type))
6414             {
6415               emit_cmp_and_jump_insns (index,
6416                                        convert_modes
6417                                        (mode, imode,
6418                                         expand_expr (node->low, NULL_RTX,
6419                                                      VOIDmode, 0),
6420                                         unsignedp),
6421                                        LT, NULL_RTX, mode, unsignedp,
6422                                        default_label);
6423             }
6424
6425           /* Value belongs to this node or to the right-hand subtree.  */
6426
6427           emit_cmp_and_jump_insns (index,
6428                                    convert_modes
6429                                    (mode, imode,
6430                                     expand_expr (node->high, NULL_RTX,
6431                                                  VOIDmode, 0),
6432                                     unsignedp),
6433                                    LE, NULL_RTX, mode, unsignedp,
6434                                    label_rtx (node->code_label));
6435
6436           emit_case_nodes (index, node->right, default_label, index_type);
6437         }
6438
6439       else if (node->right == 0 && node->left != 0)
6440         {
6441           /* Deal with values to the right of this node,
6442              if they are possible.  */
6443           if (!node_has_high_bound (node, index_type))
6444             {
6445               emit_cmp_and_jump_insns (index,
6446                                        convert_modes
6447                                        (mode, imode,
6448                                         expand_expr (node->high, NULL_RTX,
6449                                                      VOIDmode, 0),
6450                                         unsignedp),
6451                                        GT, NULL_RTX, mode, unsignedp,
6452                                        default_label);
6453             }
6454
6455           /* Value belongs to this node or to the left-hand subtree.  */
6456
6457           emit_cmp_and_jump_insns (index,
6458                                    convert_modes
6459                                    (mode, imode,
6460                                     expand_expr (node->low, NULL_RTX,
6461                                                  VOIDmode, 0),
6462                                     unsignedp),
6463                                    GE, NULL_RTX, mode, unsignedp,
6464                                    label_rtx (node->code_label));
6465
6466           emit_case_nodes (index, node->left, default_label, index_type);
6467         }
6468
6469       else
6470         {
6471           /* Node has no children so we check low and high bounds to remove
6472              redundant tests.  Only one of the bounds can exist,
6473              since otherwise this node is bounded--a case tested already.  */
6474           int high_bound = node_has_high_bound (node, index_type);
6475           int low_bound = node_has_low_bound (node, index_type);
6476
6477           if (!high_bound && low_bound)
6478             {
6479               emit_cmp_and_jump_insns (index,
6480                                        convert_modes
6481                                        (mode, imode,
6482                                         expand_expr (node->high, NULL_RTX,
6483                                                      VOIDmode, 0),
6484                                         unsignedp),
6485                                        GT, NULL_RTX, mode, unsignedp,
6486                                        default_label);
6487             }
6488
6489           else if (!low_bound && high_bound)
6490             {
6491               emit_cmp_and_jump_insns (index,
6492                                        convert_modes
6493                                        (mode, imode,
6494                                         expand_expr (node->low, NULL_RTX,
6495                                                      VOIDmode, 0),
6496                                         unsignedp),
6497                                        LT, NULL_RTX, mode, unsignedp,
6498                                        default_label);
6499             }
6500           else if (!low_bound && !high_bound)
6501             {
6502               /* Widen LOW and HIGH to the same width as INDEX.  */
6503               tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
6504               tree low = build1 (CONVERT_EXPR, type, node->low);
6505               tree high = build1 (CONVERT_EXPR, type, node->high);
6506               rtx low_rtx, new_index, new_bound;
6507
6508               /* Instead of doing two branches, emit one unsigned branch for
6509                  (index-low) > (high-low).  */
6510               low_rtx = expand_expr (low, NULL_RTX, mode, 0);
6511               new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
6512                                                NULL_RTX, unsignedp,
6513                                                OPTAB_WIDEN);
6514               new_bound = expand_expr (fold (build (MINUS_EXPR, type,
6515                                                     high, low)),
6516                                        NULL_RTX, mode, 0);
6517
6518               emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
6519                                        mode, 1, default_label);
6520             }
6521
6522           emit_jump (label_rtx (node->code_label));
6523         }
6524     }
6525 }
6526
6527 #include "gt-stmt.h"