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