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