gcc/stmt.c

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