gcc/stmt.c

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