gcc/stmt.c

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