gcc/stmt.c

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