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