gcc/stmt.c

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