gcc/stmt.c

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