gcc/stmt.c

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