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