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