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