gcc/stmt.c

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