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