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   /* If this is an expression with side effects, don't warn.  */
2307   if (TREE_SIDE_EFFECTS (exp))
2308     return 0;
2309
2310   switch (TREE_CODE (exp))
2311     {
2312     case PREINCREMENT_EXPR:
2313     case POSTINCREMENT_EXPR:
2314     case PREDECREMENT_EXPR:
2315     case POSTDECREMENT_EXPR:
2316     case MODIFY_EXPR:
2317     case INIT_EXPR:
2318     case TARGET_EXPR:
2319     case CALL_EXPR:
2320     case METHOD_CALL_EXPR:
2321     case RTL_EXPR:
2322     case TRY_CATCH_EXPR:
2323     case WITH_CLEANUP_EXPR:
2324     case EXIT_EXPR:
2325       return 0;
2326
2327     case BIND_EXPR:
2328       /* For a binding, warn if no side effect within it.  */
2329       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2330
2331     case SAVE_EXPR:
2332       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2333
2334     case TRUTH_ORIF_EXPR:
2335     case TRUTH_ANDIF_EXPR:
2336       /* In && or ||, warn if 2nd operand has no side effect.  */
2337       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2338
2339     case COMPOUND_EXPR:
2340       if (TREE_NO_UNUSED_WARNING (exp))
2341         return 0;
2342       if (warn_if_unused_value (TREE_OPERAND (exp, 0)))
2343         return 1;
2344       /* Let people do `(foo (), 0)' without a warning.  */
2345       if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
2346         return 0;
2347       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2348
2349     case NOP_EXPR:
2350     case CONVERT_EXPR:
2351     case NON_LVALUE_EXPR:
2352       /* Don't warn about conversions not explicit in the user's program.  */
2353       if (TREE_NO_UNUSED_WARNING (exp))
2354         return 0;
2355       /* Assignment to a cast usually results in a cast of a modify.
2356          Don't complain about that.  There can be an arbitrary number of
2357          casts before the modify, so we must loop until we find the first
2358          non-cast expression and then test to see if that is a modify.  */
2359       {
2360         tree tem = TREE_OPERAND (exp, 0);
2361
2362         while (TREE_CODE (tem) == CONVERT_EXPR || TREE_CODE (tem) == NOP_EXPR)
2363           tem = TREE_OPERAND (tem, 0);
2364
2365         if (TREE_CODE (tem) == MODIFY_EXPR || TREE_CODE (tem) == INIT_EXPR
2366             || TREE_CODE (tem) == CALL_EXPR)
2367           return 0;
2368       }
2369       goto warn;
2370
2371     case INDIRECT_REF:
2372       /* Don't warn about automatic dereferencing of references, since
2373          the user cannot control it.  */
2374       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
2375         return warn_if_unused_value (TREE_OPERAND (exp, 0));
2376       /* Fall through.  */
2377
2378     default:
2379       /* Referencing a volatile value is a side effect, so don't warn.  */
2380       if ((DECL_P (exp)
2381            || TREE_CODE_CLASS (TREE_CODE (exp)) == 'r')
2382           && TREE_THIS_VOLATILE (exp))
2383         return 0;
2384
2385       /* If this is an expression which has no operands, there is no value
2386          to be unused.  There are no such language-independent codes,
2387          but front ends may define such.  */
2388       if (TREE_CODE_CLASS (TREE_CODE (exp)) == 'e'
2389           && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0)
2390         return 0;
2391
2392     warn:
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 which will return a value.
2408    Return the RTL_EXPR for this statement expr.
2409    The caller must save that value and pass it to expand_end_stmt_expr.  */
2410
2411 tree
2412 expand_start_stmt_expr ()
2413 {
2414   tree t;
2415
2416   /* Make the RTL_EXPR node temporary, not momentary,
2417      so that rtl_expr_chain doesn't become garbage.  */
2418   t = make_node (RTL_EXPR);
2419   do_pending_stack_adjust ();
2420   start_sequence_for_rtl_expr (t);
2421   NO_DEFER_POP;
2422   expr_stmts_for_value++;
2423   last_expr_value = NULL_RTX;
2424   return t;
2425 }
2426
2427 /* Restore the previous state at the end of a statement that returns a value.
2428    Returns a tree node representing the statement's value and the
2429    insns to compute the value.
2430
2431    The nodes of that expression have been freed by now, so we cannot use them.
2432    But we don't want to do that anyway; the expression has already been
2433    evaluated and now we just want to use the value.  So generate a RTL_EXPR
2434    with the proper type and RTL value.
2435
2436    If the last substatement was not an expression,
2437    return something with type `void'.  */
2438
2439 tree
2440 expand_end_stmt_expr (t)
2441      tree t;
2442 {
2443   OK_DEFER_POP;
2444
2445   if (! last_expr_value || ! last_expr_type)
2446     {
2447       last_expr_value = const0_rtx;
2448       last_expr_type = void_type_node;
2449     }
2450   else if (GET_CODE (last_expr_value) != REG && ! CONSTANT_P (last_expr_value))
2451     /* Remove any possible QUEUED.  */
2452     last_expr_value = protect_from_queue (last_expr_value, 0);
2453
2454   emit_queue ();
2455
2456   TREE_TYPE (t) = last_expr_type;
2457   RTL_EXPR_RTL (t) = last_expr_value;
2458   RTL_EXPR_SEQUENCE (t) = get_insns ();
2459
2460   rtl_expr_chain = tree_cons (NULL_TREE, t, rtl_expr_chain);
2461
2462   end_sequence ();
2463
2464   /* Don't consider deleting this expr or containing exprs at tree level.  */
2465   TREE_SIDE_EFFECTS (t) = 1;
2466   /* Propagate volatility of the actual RTL expr.  */
2467   TREE_THIS_VOLATILE (t) = volatile_refs_p (last_expr_value);
2468
2469   last_expr_type = 0;
2470   expr_stmts_for_value--;
2471
2472   return t;
2473 }
2474 \f
2475 /* Generate RTL for the start of an if-then.  COND is the expression
2476    whose truth should be tested.
2477
2478    If EXITFLAG is nonzero, this conditional is visible to
2479    `exit_something'.  */
2480
2481 void
2482 expand_start_cond (cond, exitflag)
2483      tree cond;
2484      int exitflag;
2485 {
2486   struct nesting *thiscond = ALLOC_NESTING ();
2487
2488   /* Make an entry on cond_stack for the cond we are entering.  */
2489
2490   thiscond->next = cond_stack;
2491   thiscond->all = nesting_stack;
2492   thiscond->depth = ++nesting_depth;
2493   thiscond->data.cond.next_label = gen_label_rtx ();
2494   /* Before we encounter an `else', we don't need a separate exit label
2495      unless there are supposed to be exit statements
2496      to exit this conditional.  */
2497   thiscond->exit_label = exitflag ? gen_label_rtx () : 0;
2498   thiscond->data.cond.endif_label = thiscond->exit_label;
2499   cond_stack = thiscond;
2500   nesting_stack = thiscond;
2501
2502   do_jump (cond, thiscond->data.cond.next_label, NULL_RTX);
2503 }
2504
2505 /* Generate RTL between then-clause and the elseif-clause
2506    of an if-then-elseif-....  */
2507
2508 void
2509 expand_start_elseif (cond)
2510      tree cond;
2511 {
2512   if (cond_stack->data.cond.endif_label == 0)
2513     cond_stack->data.cond.endif_label = gen_label_rtx ();
2514   emit_jump (cond_stack->data.cond.endif_label);
2515   emit_label (cond_stack->data.cond.next_label);
2516   cond_stack->data.cond.next_label = gen_label_rtx ();
2517   do_jump (cond, cond_stack->data.cond.next_label, NULL_RTX);
2518 }
2519
2520 /* Generate RTL between the then-clause and the else-clause
2521    of an if-then-else.  */
2522
2523 void
2524 expand_start_else ()
2525 {
2526   if (cond_stack->data.cond.endif_label == 0)
2527     cond_stack->data.cond.endif_label = gen_label_rtx ();
2528
2529   emit_jump (cond_stack->data.cond.endif_label);
2530   emit_label (cond_stack->data.cond.next_label);
2531   cond_stack->data.cond.next_label = 0;  /* No more _else or _elseif calls.  */
2532 }
2533
2534 /* After calling expand_start_else, turn this "else" into an "else if"
2535    by providing another condition.  */
2536
2537 void
2538 expand_elseif (cond)
2539      tree cond;
2540 {
2541   cond_stack->data.cond.next_label = gen_label_rtx ();
2542   do_jump (cond, cond_stack->data.cond.next_label, NULL_RTX);
2543 }
2544
2545 /* Generate RTL for the end of an if-then.
2546    Pop the record for it off of cond_stack.  */
2547
2548 void
2549 expand_end_cond ()
2550 {
2551   struct nesting *thiscond = cond_stack;
2552
2553   do_pending_stack_adjust ();
2554   if (thiscond->data.cond.next_label)
2555     emit_label (thiscond->data.cond.next_label);
2556   if (thiscond->data.cond.endif_label)
2557     emit_label (thiscond->data.cond.endif_label);
2558
2559   POPSTACK (cond_stack);
2560   last_expr_type = 0;
2561 }
2562 \f
2563 /* Generate RTL for the start of a loop.  EXIT_FLAG is nonzero if this
2564    loop should be exited by `exit_something'.  This is a loop for which
2565    `expand_continue' will jump to the top of the loop.
2566
2567    Make an entry on loop_stack to record the labels associated with
2568    this loop.  */
2569
2570 struct nesting *
2571 expand_start_loop (exit_flag)
2572      int exit_flag;
2573 {
2574   struct nesting *thisloop = ALLOC_NESTING ();
2575
2576   /* Make an entry on loop_stack for the loop we are entering.  */
2577
2578   thisloop->next = loop_stack;
2579   thisloop->all = nesting_stack;
2580   thisloop->depth = ++nesting_depth;
2581   thisloop->data.loop.start_label = gen_label_rtx ();
2582   thisloop->data.loop.end_label = gen_label_rtx ();
2583   thisloop->data.loop.alt_end_label = 0;
2584   thisloop->data.loop.continue_label = thisloop->data.loop.start_label;
2585   thisloop->exit_label = exit_flag ? thisloop->data.loop.end_label : 0;
2586   loop_stack = thisloop;
2587   nesting_stack = thisloop;
2588
2589   do_pending_stack_adjust ();
2590   emit_queue ();
2591   emit_note (NULL, NOTE_INSN_LOOP_BEG);
2592   emit_label (thisloop->data.loop.start_label);
2593
2594   return thisloop;
2595 }
2596
2597 /* Like expand_start_loop but for a loop where the continuation point
2598    (for expand_continue_loop) will be specified explicitly.  */
2599
2600 struct nesting *
2601 expand_start_loop_continue_elsewhere (exit_flag)
2602      int exit_flag;
2603 {
2604   struct nesting *thisloop = expand_start_loop (exit_flag);
2605   loop_stack->data.loop.continue_label = gen_label_rtx ();
2606   return thisloop;
2607 }
2608
2609 /* Begin a null, aka do { } while (0) "loop".  But since the contents
2610    of said loop can still contain a break, we must frob the loop nest.  */
2611
2612 struct nesting *
2613 expand_start_null_loop ()
2614 {
2615   struct nesting *thisloop = ALLOC_NESTING ();
2616
2617   /* Make an entry on loop_stack for the loop we are entering.  */
2618
2619   thisloop->next = loop_stack;
2620   thisloop->all = nesting_stack;
2621   thisloop->depth = ++nesting_depth;
2622   thisloop->data.loop.start_label = emit_note (NULL, NOTE_INSN_DELETED);
2623   thisloop->data.loop.end_label = gen_label_rtx ();
2624   thisloop->data.loop.alt_end_label = NULL_RTX;
2625   thisloop->data.loop.continue_label = thisloop->data.loop.end_label;
2626   thisloop->exit_label = thisloop->data.loop.end_label;
2627   loop_stack = thisloop;
2628   nesting_stack = thisloop;
2629
2630   return thisloop;
2631 }
2632
2633 /* Specify the continuation point for a loop started with
2634    expand_start_loop_continue_elsewhere.
2635    Use this at the point in the code to which a continue statement
2636    should jump.  */
2637
2638 void
2639 expand_loop_continue_here ()
2640 {
2641   do_pending_stack_adjust ();
2642   emit_note (NULL, NOTE_INSN_LOOP_CONT);
2643   emit_label (loop_stack->data.loop.continue_label);
2644 }
2645
2646 /* Finish a loop.  Generate a jump back to the top and the loop-exit label.
2647    Pop the block off of loop_stack.  */
2648
2649 void
2650 expand_end_loop ()
2651 {
2652   rtx start_label = loop_stack->data.loop.start_label;
2653   rtx etc_note;
2654   int eh_regions, debug_blocks;
2655
2656   /* Mark the continue-point at the top of the loop if none elsewhere.  */
2657   if (start_label == loop_stack->data.loop.continue_label)
2658     emit_note_before (NOTE_INSN_LOOP_CONT, start_label);
2659
2660   do_pending_stack_adjust ();
2661
2662   /* If the loop starts with a loop exit, roll that to the end where
2663      it will optimize together with the jump back.
2664
2665      If the loop presently looks like this (in pseudo-C):
2666
2667         LOOP_BEG
2668         start_label:
2669           if (test) goto end_label;
2670         LOOP_END_TOP_COND
2671           body;
2672           goto start_label;
2673         end_label:
2674
2675      transform it to look like:
2676
2677         LOOP_BEG
2678           goto start_label;
2679         top_label:
2680           body;
2681         start_label:
2682           if (test) goto end_label;
2683           goto top_label;
2684         end_label:
2685
2686      We rely on the presence of NOTE_INSN_LOOP_END_TOP_COND to mark
2687      the end of the entry condtional.  Without this, our lexical scan
2688      can't tell the difference between an entry conditional and a
2689      body conditional that exits the loop.  Mistaking the two means
2690      that we can misplace the NOTE_INSN_LOOP_CONT note, which can
2691      screw up loop unrolling.
2692
2693      Things will be oh so much better when loop optimization is done
2694      off of a proper control flow graph...  */
2695
2696   /* Scan insns from the top of the loop looking for the END_TOP_COND note.  */
2697
2698   eh_regions = debug_blocks = 0;
2699   for (etc_note = start_label; etc_note ; etc_note = NEXT_INSN (etc_note))
2700     if (GET_CODE (etc_note) == NOTE)
2701       {
2702         if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_LOOP_END_TOP_COND)
2703           break;
2704
2705         /* We must not walk into a nested loop.  */
2706         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_LOOP_BEG)
2707           {
2708             etc_note = NULL_RTX;
2709             break;
2710           }
2711
2712         /* At the same time, scan for EH region notes, as we don't want
2713            to scrog region nesting.  This shouldn't happen, but...  */
2714         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_EH_REGION_BEG)
2715           eh_regions++;
2716         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_EH_REGION_END)
2717           {
2718             if (--eh_regions < 0)
2719               /* We've come to the end of an EH region, but never saw the
2720                  beginning of that region.  That means that an EH region
2721                  begins before the top of the loop, and ends in the middle
2722                  of it.  The existence of such a situation violates a basic
2723                  assumption in this code, since that would imply that even
2724                  when EH_REGIONS is zero, we might move code out of an
2725                  exception region.  */
2726               abort ();
2727           }
2728
2729         /* Likewise for debug scopes.  In this case we'll either (1) move
2730            all of the notes if they are properly nested or (2) leave the
2731            notes alone and only rotate the loop at high optimization
2732            levels when we expect to scrog debug info.  */
2733         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_BLOCK_BEG)
2734           debug_blocks++;
2735         else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_BLOCK_END)
2736           debug_blocks--;
2737       }
2738
2739   if (etc_note
2740       && optimize
2741       && eh_regions == 0
2742       && (debug_blocks == 0 || optimize >= 2)
2743       && NEXT_INSN (etc_note) != NULL_RTX
2744       && ! any_condjump_p (get_last_insn ()))
2745     {
2746       /* We found one.  Move everything from START to ETC to the end
2747          of the loop, and add a jump from the top of the loop.  */
2748       rtx top_label = gen_label_rtx ();
2749       rtx start_move = start_label;
2750
2751       /* If the start label is preceded by a NOTE_INSN_LOOP_CONT note,
2752          then we want to move this note also.  */
2753       if (GET_CODE (PREV_INSN (start_move)) == NOTE
2754           && NOTE_LINE_NUMBER (PREV_INSN (start_move)) == NOTE_INSN_LOOP_CONT)
2755         start_move = PREV_INSN (start_move);
2756
2757       emit_label_before (top_label, start_move);
2758
2759       /* Actually move the insns.  If the debug scopes are nested, we
2760          can move everything at once.  Otherwise we have to move them
2761          one by one and squeeze out the block notes.  */
2762       if (debug_blocks == 0)
2763         reorder_insns (start_move, etc_note, get_last_insn ());
2764       else
2765         {
2766           rtx insn, next_insn;
2767           for (insn = start_move; insn; insn = next_insn)
2768             {
2769               /* Figure out which insn comes after this one.  We have
2770                  to do this before we move INSN.  */
2771               next_insn = (insn == etc_note ? NULL : NEXT_INSN (insn));
2772
2773               if (GET_CODE (insn) == NOTE
2774                   && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2775                       || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
2776                 continue;
2777
2778               reorder_insns (insn, insn, get_last_insn ());
2779             }
2780         }
2781
2782       /* Add the jump from the top of the loop.  */
2783       emit_jump_insn_before (gen_jump (start_label), top_label);
2784       emit_barrier_before (top_label);
2785       start_label = top_label;
2786     }
2787
2788   emit_jump (start_label);
2789   emit_note (NULL, NOTE_INSN_LOOP_END);
2790   emit_label (loop_stack->data.loop.end_label);
2791
2792   POPSTACK (loop_stack);
2793
2794   last_expr_type = 0;
2795 }
2796
2797 /* Finish a null loop, aka do { } while (0).  */
2798
2799 void
2800 expand_end_null_loop ()
2801 {
2802   do_pending_stack_adjust ();
2803   emit_label (loop_stack->data.loop.end_label);
2804
2805   POPSTACK (loop_stack);
2806
2807   last_expr_type = 0;
2808 }
2809
2810 /* Generate a jump to the current loop's continue-point.
2811    This is usually the top of the loop, but may be specified
2812    explicitly elsewhere.  If not currently inside a loop,
2813    return 0 and do nothing; caller will print an error message.  */
2814
2815 int
2816 expand_continue_loop (whichloop)
2817      struct nesting *whichloop;
2818 {
2819   last_expr_type = 0;
2820   if (whichloop == 0)
2821     whichloop = loop_stack;
2822   if (whichloop == 0)
2823     return 0;
2824   expand_goto_internal (NULL_TREE, whichloop->data.loop.continue_label,
2825                         NULL_RTX);
2826   return 1;
2827 }
2828
2829 /* Generate a jump to exit the current loop.  If not currently inside a loop,
2830    return 0 and do nothing; caller will print an error message.  */
2831
2832 int
2833 expand_exit_loop (whichloop)
2834      struct nesting *whichloop;
2835 {
2836   last_expr_type = 0;
2837   if (whichloop == 0)
2838     whichloop = loop_stack;
2839   if (whichloop == 0)
2840     return 0;
2841   expand_goto_internal (NULL_TREE, whichloop->data.loop.end_label, NULL_RTX);
2842   return 1;
2843 }
2844
2845 /* Generate a conditional jump to exit the current loop if COND
2846    evaluates to zero.  If not currently inside a loop,
2847    return 0 and do nothing; caller will print an error message.  */
2848
2849 int
2850 expand_exit_loop_if_false (whichloop, cond)
2851      struct nesting *whichloop;
2852      tree cond;
2853 {
2854   rtx label = gen_label_rtx ();
2855   rtx last_insn;
2856   last_expr_type = 0;
2857
2858   if (whichloop == 0)
2859     whichloop = loop_stack;
2860   if (whichloop == 0)
2861     return 0;
2862   /* In order to handle fixups, we actually create a conditional jump
2863      around an unconditional branch to exit the loop.  If fixups are
2864      necessary, they go before the unconditional branch.  */
2865
2866   do_jump (cond, NULL_RTX, label);
2867   last_insn = get_last_insn ();
2868   if (GET_CODE (last_insn) == CODE_LABEL)
2869     whichloop->data.loop.alt_end_label = last_insn;
2870   expand_goto_internal (NULL_TREE, whichloop->data.loop.end_label,
2871                         NULL_RTX);
2872   emit_label (label);
2873
2874   return 1;
2875 }
2876
2877 /* Like expand_exit_loop_if_false except also emit a note marking
2878    the end of the conditional.  Should only be used immediately
2879    after expand_loop_start.  */
2880
2881 int
2882 expand_exit_loop_top_cond (whichloop, cond)
2883      struct nesting *whichloop;
2884      tree cond;
2885 {
2886   if (! expand_exit_loop_if_false (whichloop, cond))
2887     return 0;
2888
2889   emit_note (NULL, NOTE_INSN_LOOP_END_TOP_COND);
2890   return 1;
2891 }
2892
2893 /* Return nonzero if the loop nest is empty.  Else return zero.  */
2894
2895 int
2896 stmt_loop_nest_empty ()
2897 {
2898   /* cfun->stmt can be NULL if we are building a call to get the
2899      EH context for a setjmp/longjmp EH target and the current
2900      function was a deferred inline function.  */
2901   return (cfun->stmt == NULL || loop_stack == NULL);
2902 }
2903
2904 /* Return non-zero if we should preserve sub-expressions as separate
2905    pseudos.  We never do so if we aren't optimizing.  We always do so
2906    if -fexpensive-optimizations.
2907
2908    Otherwise, we only do so if we are in the "early" part of a loop.  I.e.,
2909    the loop may still be a small one.  */
2910
2911 int
2912 preserve_subexpressions_p ()
2913 {
2914   rtx insn;
2915
2916   if (flag_expensive_optimizations)
2917     return 1;
2918
2919   if (optimize == 0 || cfun == 0 || cfun->stmt == 0 || loop_stack == 0)
2920     return 0;
2921
2922   insn = get_last_insn_anywhere ();
2923
2924   return (insn
2925           && (INSN_UID (insn) - INSN_UID (loop_stack->data.loop.start_label)
2926               < n_non_fixed_regs * 3));
2927
2928 }
2929
2930 /* Generate a jump to exit the current loop, conditional, binding contour
2931    or case statement.  Not all such constructs are visible to this function,
2932    only those started with EXIT_FLAG nonzero.  Individual languages use
2933    the EXIT_FLAG parameter to control which kinds of constructs you can
2934    exit this way.
2935
2936    If not currently inside anything that can be exited,
2937    return 0 and do nothing; caller will print an error message.  */
2938
2939 int
2940 expand_exit_something ()
2941 {
2942   struct nesting *n;
2943   last_expr_type = 0;
2944   for (n = nesting_stack; n; n = n->all)
2945     if (n->exit_label != 0)
2946       {
2947         expand_goto_internal (NULL_TREE, n->exit_label, NULL_RTX);
2948         return 1;
2949       }
2950
2951   return 0;
2952 }
2953 \f
2954 /* Generate RTL to return from the current function, with no value.
2955    (That is, we do not do anything about returning any value.)  */
2956
2957 void
2958 expand_null_return ()
2959 {
2960   rtx last_insn = get_last_insn ();
2961
2962   /* If this function was declared to return a value, but we
2963      didn't, clobber the return registers so that they are not
2964      propagated live to the rest of the function.  */
2965   clobber_return_register ();
2966
2967   expand_null_return_1 (last_insn);
2968 }
2969
2970 /* Generate RTL to return from the current function, with value VAL.  */
2971
2972 static void
2973 expand_value_return (val)
2974      rtx val;
2975 {
2976   rtx last_insn = get_last_insn ();
2977   rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl));
2978
2979   /* Copy the value to the return location
2980      unless it's already there.  */
2981
2982   if (return_reg != val)
2983     {
2984       tree type = TREE_TYPE (DECL_RESULT (current_function_decl));
2985 #ifdef PROMOTE_FUNCTION_RETURN
2986       int unsignedp = TREE_UNSIGNED (type);
2987       enum machine_mode old_mode
2988         = DECL_MODE (DECL_RESULT (current_function_decl));
2989       enum machine_mode mode
2990         = promote_mode (type, old_mode, &unsignedp, 1);
2991
2992       if (mode != old_mode)
2993         val = convert_modes (mode, old_mode, val, unsignedp);
2994 #endif
2995       if (GET_CODE (return_reg) == PARALLEL)
2996         emit_group_load (return_reg, val, int_size_in_bytes (type));
2997       else
2998         emit_move_insn (return_reg, val);
2999     }
3000
3001   expand_null_return_1 (last_insn);
3002 }
3003
3004 /* Output a return with no value.  If LAST_INSN is nonzero,
3005    pretend that the return takes place after LAST_INSN.  */
3006
3007 static void
3008 expand_null_return_1 (last_insn)
3009      rtx last_insn;
3010 {
3011   rtx end_label = cleanup_label ? cleanup_label : return_label;
3012
3013   clear_pending_stack_adjust ();
3014   do_pending_stack_adjust ();
3015   last_expr_type = 0;
3016
3017   if (end_label == 0)
3018      end_label = return_label = gen_label_rtx ();
3019   expand_goto_internal (NULL_TREE, end_label, last_insn);
3020 }
3021 \f
3022 /* Generate RTL to evaluate the expression RETVAL and return it
3023    from the current function.  */
3024
3025 void
3026 expand_return (retval)
3027      tree retval;
3028 {
3029   /* If there are any cleanups to be performed, then they will
3030      be inserted following LAST_INSN.  It is desirable
3031      that the last_insn, for such purposes, should be the
3032      last insn before computing the return value.  Otherwise, cleanups
3033      which call functions can clobber the return value.  */
3034   /* ??? rms: I think that is erroneous, because in C++ it would
3035      run destructors on variables that might be used in the subsequent
3036      computation of the return value.  */
3037   rtx last_insn = 0;
3038   rtx result_rtl;
3039   rtx val = 0;
3040   tree retval_rhs;
3041
3042   /* If function wants no value, give it none.  */
3043   if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
3044     {
3045       expand_expr (retval, NULL_RTX, VOIDmode, 0);
3046       emit_queue ();
3047       expand_null_return ();
3048       return;
3049     }
3050
3051   if (retval == error_mark_node)
3052     {
3053       /* Treat this like a return of no value from a function that
3054          returns a value.  */
3055       expand_null_return ();
3056       return;
3057     }
3058   else if (TREE_CODE (retval) == RESULT_DECL)
3059     retval_rhs = retval;
3060   else if ((TREE_CODE (retval) == MODIFY_EXPR || TREE_CODE (retval) == INIT_EXPR)
3061            && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
3062     retval_rhs = TREE_OPERAND (retval, 1);
3063   else if (VOID_TYPE_P (TREE_TYPE (retval)))
3064     /* Recognize tail-recursive call to void function.  */
3065     retval_rhs = retval;
3066   else
3067     retval_rhs = NULL_TREE;
3068
3069   last_insn = get_last_insn ();
3070
3071   /* Distribute return down conditional expr if either of the sides
3072      may involve tail recursion (see test below).  This enhances the number
3073      of tail recursions we see.  Don't do this always since it can produce
3074      sub-optimal code in some cases and we distribute assignments into
3075      conditional expressions when it would help.  */
3076
3077   if (optimize && retval_rhs != 0
3078       && frame_offset == 0
3079       && TREE_CODE (retval_rhs) == COND_EXPR
3080       && (TREE_CODE (TREE_OPERAND (retval_rhs, 1)) == CALL_EXPR
3081           || TREE_CODE (TREE_OPERAND (retval_rhs, 2)) == CALL_EXPR))
3082     {
3083       rtx label = gen_label_rtx ();
3084       tree expr;
3085
3086       do_jump (TREE_OPERAND (retval_rhs, 0), label, NULL_RTX);
3087       start_cleanup_deferral ();
3088       expr = build (MODIFY_EXPR, TREE_TYPE (TREE_TYPE (current_function_decl)),
3089                     DECL_RESULT (current_function_decl),
3090                     TREE_OPERAND (retval_rhs, 1));
3091       TREE_SIDE_EFFECTS (expr) = 1;
3092       expand_return (expr);
3093       emit_label (label);
3094
3095       expr = build (MODIFY_EXPR, TREE_TYPE (TREE_TYPE (current_function_decl)),
3096                     DECL_RESULT (current_function_decl),
3097                     TREE_OPERAND (retval_rhs, 2));
3098       TREE_SIDE_EFFECTS (expr) = 1;
3099       expand_return (expr);
3100       end_cleanup_deferral ();
3101       return;
3102     }
3103
3104   result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
3105
3106   /* If the result is an aggregate that is being returned in one (or more)
3107      registers, load the registers here.  The compiler currently can't handle
3108      copying a BLKmode value into registers.  We could put this code in a
3109      more general area (for use by everyone instead of just function
3110      call/return), but until this feature is generally usable it is kept here
3111      (and in expand_call).  The value must go into a pseudo in case there
3112      are cleanups that will clobber the real return register.  */
3113
3114   if (retval_rhs != 0
3115       && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
3116       && GET_CODE (result_rtl) == REG)
3117     {
3118       int i;
3119       unsigned HOST_WIDE_INT bitpos, xbitpos;
3120       unsigned HOST_WIDE_INT big_endian_correction = 0;
3121       unsigned HOST_WIDE_INT bytes
3122         = int_size_in_bytes (TREE_TYPE (retval_rhs));
3123       int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
3124       unsigned int bitsize
3125         = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
3126       rtx *result_pseudos = (rtx *) alloca (sizeof (rtx) * n_regs);
3127       rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
3128       rtx result_val = expand_expr (retval_rhs, NULL_RTX, VOIDmode, 0);
3129       enum machine_mode tmpmode, result_reg_mode;
3130
3131       if (bytes == 0)
3132         {
3133           expand_null_return ();
3134           return;
3135         }
3136
3137       /* Structures whose size is not a multiple of a word are aligned
3138          to the least significant byte (to the right).  On a BYTES_BIG_ENDIAN
3139          machine, this means we must skip the empty high order bytes when
3140          calculating the bit offset.  */
3141       if (BYTES_BIG_ENDIAN
3142           && !FUNCTION_ARG_REG_LITTLE_ENDIAN
3143           && bytes % UNITS_PER_WORD)
3144         big_endian_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
3145                                                   * BITS_PER_UNIT));
3146
3147       /* Copy the structure BITSIZE bits at a time.  */
3148       for (bitpos = 0, xbitpos = big_endian_correction;
3149            bitpos < bytes * BITS_PER_UNIT;
3150            bitpos += bitsize, xbitpos += bitsize)
3151         {
3152           /* We need a new destination pseudo each time xbitpos is
3153              on a word boundary and when xbitpos == big_endian_correction
3154              (the first time through).  */
3155           if (xbitpos % BITS_PER_WORD == 0
3156               || xbitpos == big_endian_correction)
3157             {
3158               /* Generate an appropriate register.  */
3159               dst = gen_reg_rtx (word_mode);
3160               result_pseudos[xbitpos / BITS_PER_WORD] = dst;
3161
3162               /* Clear the destination before we move anything into it.  */
3163               emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
3164             }
3165
3166           /* We need a new source operand each time bitpos is on a word
3167              boundary.  */
3168           if (bitpos % BITS_PER_WORD == 0)
3169             src = operand_subword_force (result_val,
3170                                          bitpos / BITS_PER_WORD,
3171                                          BLKmode);
3172
3173           /* Use bitpos for the source extraction (left justified) and
3174              xbitpos for the destination store (right justified).  */
3175           store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
3176                            extract_bit_field (src, bitsize,
3177                                               bitpos % BITS_PER_WORD, 1,
3178                                               NULL_RTX, word_mode, word_mode,
3179                                               BITS_PER_WORD),
3180                            BITS_PER_WORD);
3181         }
3182
3183       /* Find the smallest integer mode large enough to hold the
3184          entire structure and use that mode instead of BLKmode
3185          on the USE insn for the return register.  */
3186       for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
3187            tmpmode != VOIDmode;
3188            tmpmode = GET_MODE_WIDER_MODE (tmpmode))
3189         /* Have we found a large enough mode?  */
3190         if (GET_MODE_SIZE (tmpmode) >= bytes)
3191           break;
3192
3193       /* No suitable mode found.  */
3194       if (tmpmode == VOIDmode)
3195         abort ();
3196
3197       PUT_MODE (result_rtl, tmpmode);
3198
3199       if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
3200         result_reg_mode = word_mode;
3201       else
3202         result_reg_mode = tmpmode;
3203       result_reg = gen_reg_rtx (result_reg_mode);
3204
3205       emit_queue ();
3206       for (i = 0; i < n_regs; i++)
3207         emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
3208                         result_pseudos[i]);
3209
3210       if (tmpmode != result_reg_mode)
3211         result_reg = gen_lowpart (tmpmode, result_reg);
3212
3213       expand_value_return (result_reg);
3214     }
3215   else if (retval_rhs != 0
3216            && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
3217            && (GET_CODE (result_rtl) == REG
3218                || (GET_CODE (result_rtl) == PARALLEL)))
3219     {
3220       /* Calculate the return value into a temporary (usually a pseudo
3221          reg).  */
3222       tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
3223       tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
3224
3225       val = assign_temp (nt, 0, 0, 1);
3226       val = expand_expr (retval_rhs, val, GET_MODE (val), 0);
3227       val = force_not_mem (val);
3228       emit_queue ();
3229       /* Return the calculated value, doing cleanups first.  */
3230       expand_value_return (val);
3231     }
3232   else
3233     {
3234       /* No cleanups or no hard reg used;
3235          calculate value into hard return reg.  */
3236       expand_expr (retval, const0_rtx, VOIDmode, 0);
3237       emit_queue ();
3238       expand_value_return (result_rtl);
3239     }
3240 }
3241
3242 /* Return 1 if the end of the generated RTX is not a barrier.
3243    This means code already compiled can drop through.  */
3244
3245 int
3246 drop_through_at_end_p ()
3247 {
3248   rtx insn = get_last_insn ();
3249   while (insn && GET_CODE (insn) == NOTE)
3250     insn = PREV_INSN (insn);
3251   return insn && GET_CODE (insn) != BARRIER;
3252 }
3253 \f
3254 /* Attempt to optimize a potential tail recursion call into a goto.
3255    ARGUMENTS are the arguments to a CALL_EXPR; LAST_INSN indicates
3256    where to place the jump to the tail recursion label.
3257
3258    Return TRUE if the call was optimized into a goto.  */
3259
3260 int
3261 optimize_tail_recursion (arguments, last_insn)
3262      tree arguments;
3263      rtx last_insn;
3264 {
3265   /* Finish checking validity, and if valid emit code to set the
3266      argument variables for the new call.  */
3267   if (tail_recursion_args (arguments, DECL_ARGUMENTS (current_function_decl)))
3268     {
3269       if (tail_recursion_label == 0)
3270         {
3271           tail_recursion_label = gen_label_rtx ();
3272           emit_label_after (tail_recursion_label,
3273                             tail_recursion_reentry);
3274         }
3275       emit_queue ();
3276       expand_goto_internal (NULL_TREE, tail_recursion_label, last_insn);
3277       emit_barrier ();
3278       return 1;
3279     }
3280   return 0;
3281 }
3282
3283 /* Emit code to alter this function's formal parms for a tail-recursive call.
3284    ACTUALS is a list of actual parameter expressions (chain of TREE_LISTs).
3285    FORMALS is the chain of decls of formals.
3286    Return 1 if this can be done;
3287    otherwise return 0 and do not emit any code.  */
3288
3289 static int
3290 tail_recursion_args (actuals, formals)
3291      tree actuals, formals;
3292 {
3293   tree a = actuals, f = formals;
3294   int i;
3295   rtx *argvec;
3296
3297   /* Check that number and types of actuals are compatible
3298      with the formals.  This is not always true in valid C code.
3299      Also check that no formal needs to be addressable
3300      and that all formals are scalars.  */
3301
3302   /* Also count the args.  */
3303
3304   for (a = actuals, f = formals, i = 0; a && f; a = TREE_CHAIN (a), f = TREE_CHAIN (f), i++)
3305     {
3306       if (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_VALUE (a)))
3307           != TYPE_MAIN_VARIANT (TREE_TYPE (f)))
3308         return 0;
3309       if (GET_CODE (DECL_RTL (f)) != REG || DECL_MODE (f) == BLKmode)
3310         return 0;
3311     }
3312   if (a != 0 || f != 0)
3313     return 0;
3314
3315   /* Compute all the actuals.  */
3316
3317   argvec = (rtx *) alloca (i * sizeof (rtx));
3318
3319   for (a = actuals, i = 0; a; a = TREE_CHAIN (a), i++)
3320     argvec[i] = expand_expr (TREE_VALUE (a), NULL_RTX, VOIDmode, 0);
3321
3322   /* Find which actual values refer to current values of previous formals.
3323      Copy each of them now, before any formal is changed.  */
3324
3325   for (a = actuals, i = 0; a; a = TREE_CHAIN (a), i++)
3326     {
3327       int copy = 0;
3328       int j;
3329       for (f = formals, j = 0; j < i; f = TREE_CHAIN (f), j++)
3330         if (reg_mentioned_p (DECL_RTL (f), argvec[i]))
3331           {
3332             copy = 1;
3333             break;
3334           }
3335       if (copy)
3336         argvec[i] = copy_to_reg (argvec[i]);
3337     }
3338
3339   /* Store the values of the actuals into the formals.  */
3340
3341   for (f = formals, a = actuals, i = 0; f;
3342        f = TREE_CHAIN (f), a = TREE_CHAIN (a), i++)
3343     {
3344       if (GET_MODE (DECL_RTL (f)) == GET_MODE (argvec[i]))
3345         emit_move_insn (DECL_RTL (f), argvec[i]);
3346       else
3347         convert_move (DECL_RTL (f), argvec[i],
3348                       TREE_UNSIGNED (TREE_TYPE (TREE_VALUE (a))));
3349     }
3350
3351   free_temp_slots ();
3352   return 1;
3353 }
3354 \f
3355 /* Generate the RTL code for entering a binding contour.
3356    The variables are declared one by one, by calls to `expand_decl'.
3357
3358    FLAGS is a bitwise or of the following flags:
3359
3360      1 - Nonzero if this construct should be visible to
3361          `exit_something'.
3362
3363      2 - Nonzero if this contour does not require a
3364          NOTE_INSN_BLOCK_BEG note.  Virtually all calls from
3365          language-independent code should set this flag because they
3366          will not create corresponding BLOCK nodes.  (There should be
3367          a one-to-one correspondence between NOTE_INSN_BLOCK_BEG notes
3368          and BLOCKs.)  If this flag is set, MARK_ENDS should be zero
3369          when expand_end_bindings is called.
3370
3371     If we are creating a NOTE_INSN_BLOCK_BEG note, a BLOCK may
3372     optionally be supplied.  If so, it becomes the NOTE_BLOCK for the
3373     note.  */
3374
3375 void
3376 expand_start_bindings_and_block (flags, block)
3377      int flags;
3378      tree block;
3379 {
3380   struct nesting *thisblock = ALLOC_NESTING ();
3381   rtx note;
3382   int exit_flag = ((flags & 1) != 0);
3383   int block_flag = ((flags & 2) == 0);
3384
3385   /* If a BLOCK is supplied, then the caller should be requesting a
3386      NOTE_INSN_BLOCK_BEG note.  */
3387   if (!block_flag && block)
3388     abort ();
3389
3390   /* Create a note to mark the beginning of the block.  */
3391   if (block_flag)
3392     {
3393       note = emit_note (NULL, NOTE_INSN_BLOCK_BEG);
3394       NOTE_BLOCK (note) = block;
3395     }
3396   else
3397     note = emit_note (NULL, NOTE_INSN_DELETED);
3398
3399   /* Make an entry on block_stack for the block we are entering.  */
3400
3401   thisblock->next = block_stack;
3402   thisblock->all = nesting_stack;
3403   thisblock->depth = ++nesting_depth;
3404   thisblock->data.block.stack_level = 0;
3405   thisblock->data.block.cleanups = 0;
3406   thisblock->data.block.n_function_calls = 0;
3407   thisblock->data.block.exception_region = 0;
3408   thisblock->data.block.block_target_temp_slot_level = target_temp_slot_level;
3409
3410   thisblock->data.block.conditional_code = 0;
3411   thisblock->data.block.last_unconditional_cleanup = note;
3412   /* When we insert instructions after the last unconditional cleanup,
3413      we don't adjust last_insn.  That means that a later add_insn will
3414      clobber the instructions we've just added.  The easiest way to
3415      fix this is to just insert another instruction here, so that the
3416      instructions inserted after the last unconditional cleanup are
3417      never the last instruction.  */
3418   emit_note (NULL, NOTE_INSN_DELETED);
3419   thisblock->data.block.cleanup_ptr = &thisblock->data.block.cleanups;
3420
3421   if (block_stack
3422       && !(block_stack->data.block.cleanups == NULL_TREE
3423            && block_stack->data.block.outer_cleanups == NULL_TREE))
3424     thisblock->data.block.outer_cleanups
3425       = tree_cons (NULL_TREE, block_stack->data.block.cleanups,
3426                    block_stack->data.block.outer_cleanups);
3427   else
3428     thisblock->data.block.outer_cleanups = 0;
3429   thisblock->data.block.label_chain = 0;
3430   thisblock->data.block.innermost_stack_block = stack_block_stack;
3431   thisblock->data.block.first_insn = note;
3432   thisblock->data.block.block_start_count = ++current_block_start_count;
3433   thisblock->exit_label = exit_flag ? gen_label_rtx () : 0;
3434   block_stack = thisblock;
3435   nesting_stack = thisblock;
3436
3437   /* Make a new level for allocating stack slots.  */
3438   push_temp_slots ();
3439 }
3440
3441 /* Specify the scope of temporaries created by TARGET_EXPRs.  Similar
3442    to CLEANUP_POINT_EXPR, but handles cases when a series of calls to
3443    expand_expr are made.  After we end the region, we know that all
3444    space for all temporaries that were created by TARGET_EXPRs will be
3445    destroyed and their space freed for reuse.  */
3446
3447 void
3448 expand_start_target_temps ()
3449 {
3450   /* This is so that even if the result is preserved, the space
3451      allocated will be freed, as we know that it is no longer in use.  */
3452   push_temp_slots ();
3453
3454   /* Start a new binding layer that will keep track of all cleanup
3455      actions to be performed.  */
3456   expand_start_bindings (2);
3457
3458   target_temp_slot_level = temp_slot_level;
3459 }
3460
3461 void
3462 expand_end_target_temps ()
3463 {
3464   expand_end_bindings (NULL_TREE, 0, 0);
3465
3466   /* This is so that even if the result is preserved, the space
3467      allocated will be freed, as we know that it is no longer in use.  */
3468   pop_temp_slots ();
3469 }
3470
3471 /* Given a pointer to a BLOCK node return non-zero if (and only if) the node
3472    in question represents the outermost pair of curly braces (i.e. the "body
3473    block") of a function or method.
3474
3475    For any BLOCK node representing a "body block" of a function or method, the
3476    BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which
3477    represents the outermost (function) scope for the function or method (i.e.
3478    the one which includes the formal parameters).  The BLOCK_SUPERCONTEXT of
3479    *that* node in turn will point to the relevant FUNCTION_DECL node.  */
3480
3481 int
3482 is_body_block (stmt)
3483      tree stmt;
3484 {
3485   if (TREE_CODE (stmt) == BLOCK)
3486     {
3487       tree parent = BLOCK_SUPERCONTEXT (stmt);
3488
3489       if (parent && TREE_CODE (parent) == BLOCK)
3490         {
3491           tree grandparent = BLOCK_SUPERCONTEXT (parent);
3492
3493           if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL)
3494             return 1;
3495         }
3496     }
3497
3498   return 0;
3499 }
3500
3501 /* True if we are currently emitting insns in an area of output code
3502    that is controlled by a conditional expression.  This is used by
3503    the cleanup handling code to generate conditional cleanup actions.  */
3504
3505 int
3506 conditional_context ()
3507 {
3508   return block_stack && block_stack->data.block.conditional_code;
3509 }
3510
3511 /* Return an opaque pointer to the current nesting level, so frontend code
3512    can check its own sanity.  */
3513
3514 struct nesting *
3515 current_nesting_level ()
3516 {
3517   return cfun ? block_stack : 0;
3518 }
3519
3520 /* Emit a handler label for a nonlocal goto handler.
3521    Also emit code to store the handler label in SLOT before BEFORE_INSN.  */
3522
3523 static rtx
3524 expand_nl_handler_label (slot, before_insn)
3525      rtx slot, before_insn;
3526 {
3527   rtx insns;
3528   rtx handler_label = gen_label_rtx ();
3529
3530   /* Don't let cleanup_cfg delete the handler.  */
3531   LABEL_PRESERVE_P (handler_label) = 1;
3532
3533   start_sequence ();
3534   emit_move_insn (slot, gen_rtx_LABEL_REF (Pmode, handler_label));
3535   insns = get_insns ();
3536   end_sequence ();
3537   emit_insns_before (insns, before_insn);
3538
3539   emit_label (handler_label);
3540
3541   return handler_label;
3542 }
3543
3544 /* Emit code to restore vital registers at the beginning of a nonlocal goto
3545    handler.  */
3546 static void
3547 expand_nl_goto_receiver ()
3548 {
3549 #ifdef HAVE_nonlocal_goto
3550   if (! HAVE_nonlocal_goto)
3551 #endif
3552     /* First adjust our frame pointer to its actual value.  It was
3553        previously set to the start of the virtual area corresponding to
3554        the stacked variables when we branched here and now needs to be
3555        adjusted to the actual hardware fp value.
3556
3557        Assignments are to virtual registers are converted by
3558        instantiate_virtual_regs into the corresponding assignment
3559        to the underlying register (fp in this case) that makes
3560        the original assignment true.
3561        So the following insn will actually be
3562        decrementing fp by STARTING_FRAME_OFFSET.  */
3563     emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
3564
3565 #if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3566   if (fixed_regs[ARG_POINTER_REGNUM])
3567     {
3568 #ifdef ELIMINABLE_REGS
3569       /* If the argument pointer can be eliminated in favor of the
3570          frame pointer, we don't need to restore it.  We assume here
3571          that if such an elimination is present, it can always be used.
3572          This is the case on all known machines; if we don't make this
3573          assumption, we do unnecessary saving on many machines.  */
3574       static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
3575       size_t i;
3576
3577       for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
3578         if (elim_regs[i].from == ARG_POINTER_REGNUM
3579             && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
3580           break;
3581
3582       if (i == ARRAY_SIZE (elim_regs))
3583 #endif
3584         {
3585           /* Now restore our arg pointer from the address at which it
3586              was saved in our stack frame.  */
3587           emit_move_insn (virtual_incoming_args_rtx,
3588                           copy_to_reg (get_arg_pointer_save_area (cfun)));
3589         }
3590     }
3591 #endif
3592
3593 #ifdef HAVE_nonlocal_goto_receiver
3594   if (HAVE_nonlocal_goto_receiver)
3595     emit_insn (gen_nonlocal_goto_receiver ());
3596 #endif
3597 }
3598
3599 /* Make handlers for nonlocal gotos taking place in the function calls in
3600    block THISBLOCK.  */
3601
3602 static void
3603 expand_nl_goto_receivers (thisblock)
3604      struct nesting *thisblock;
3605 {
3606   tree link;
3607   rtx afterward = gen_label_rtx ();
3608   rtx insns, slot;
3609   rtx label_list;
3610   int any_invalid;
3611
3612   /* Record the handler address in the stack slot for that purpose,
3613      during this block, saving and restoring the outer value.  */
3614   if (thisblock->next != 0)
3615     for (slot = nonlocal_goto_handler_slots; slot; slot = XEXP (slot, 1))
3616       {
3617         rtx save_receiver = gen_reg_rtx (Pmode);
3618         emit_move_insn (XEXP (slot, 0), save_receiver);
3619
3620         start_sequence ();
3621         emit_move_insn (save_receiver, XEXP (slot, 0));
3622         insns = get_insns ();
3623         end_sequence ();
3624         emit_insns_before (insns, thisblock->data.block.first_insn);
3625       }
3626
3627   /* Jump around the handlers; they run only when specially invoked.  */
3628   emit_jump (afterward);
3629
3630   /* Make a separate handler for each label.  */
3631   link = nonlocal_labels;
3632   slot = nonlocal_goto_handler_slots;
3633   label_list = NULL_RTX;
3634   for (; link; link = TREE_CHAIN (link), slot = XEXP (slot, 1))
3635     /* Skip any labels we shouldn't be able to jump to from here,
3636        we generate one special handler for all of them below which just calls
3637        abort.  */
3638     if (! DECL_TOO_LATE (TREE_VALUE (link)))
3639       {
3640         rtx lab;
3641         lab = expand_nl_handler_label (XEXP (slot, 0),
3642                                        thisblock->data.block.first_insn);
3643         label_list = gen_rtx_EXPR_LIST (VOIDmode, lab, label_list);
3644
3645         expand_nl_goto_receiver ();
3646
3647         /* Jump to the "real" nonlocal label.  */
3648         expand_goto (TREE_VALUE (link));
3649       }
3650
3651   /* A second pass over all nonlocal labels; this time we handle those
3652      we should not be able to jump to at this point.  */
3653   link = nonlocal_labels;
3654   slot = nonlocal_goto_handler_slots;
3655   any_invalid = 0;
3656   for (; link; link = TREE_CHAIN (link), slot = XEXP (slot, 1))
3657     if (DECL_TOO_LATE (TREE_VALUE (link)))
3658       {
3659         rtx lab;
3660         lab = expand_nl_handler_label (XEXP (slot, 0),
3661                                        thisblock->data.block.first_insn);
3662         label_list = gen_rtx_EXPR_LIST (VOIDmode, lab, label_list);
3663         any_invalid = 1;
3664       }
3665
3666   if (any_invalid)
3667     {
3668       expand_nl_goto_receiver ();
3669       emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "abort"), LCT_NORETURN,
3670                          VOIDmode, 0);
3671       emit_barrier ();
3672     }
3673
3674   nonlocal_goto_handler_labels = label_list;
3675   emit_label (afterward);
3676 }
3677
3678 /* Warn about any unused VARS (which may contain nodes other than
3679    VAR_DECLs, but such nodes are ignored).  The nodes are connected
3680    via the TREE_CHAIN field.  */
3681
3682 void
3683 warn_about_unused_variables (vars)
3684      tree vars;
3685 {
3686   tree decl;
3687
3688   if (warn_unused_variable)
3689     for (decl = vars; decl; decl = TREE_CHAIN (decl))
3690       if (TREE_CODE (decl) == VAR_DECL
3691           && ! TREE_USED (decl)
3692           && ! DECL_IN_SYSTEM_HEADER (decl)
3693           && DECL_NAME (decl) && ! DECL_ARTIFICIAL (decl))
3694         warning_with_decl (decl, "unused variable `%s'");
3695 }
3696
3697 /* Generate RTL code to terminate a binding contour.
3698
3699    VARS is the chain of VAR_DECL nodes for the variables bound in this
3700    contour.  There may actually be other nodes in this chain, but any
3701    nodes other than VAR_DECLS are ignored.
3702
3703    MARK_ENDS is nonzero if we should put a note at the beginning
3704    and end of this binding contour.
3705
3706    DONT_JUMP_IN is nonzero if it is not valid to jump into this contour.
3707    (That is true automatically if the contour has a saved stack level.)  */
3708
3709 void
3710 expand_end_bindings (vars, mark_ends, dont_jump_in)
3711      tree vars;
3712      int mark_ends;
3713      int dont_jump_in;
3714 {
3715   struct nesting *thisblock = block_stack;
3716
3717   /* If any of the variables in this scope were not used, warn the
3718      user.  */
3719   warn_about_unused_variables (vars);
3720
3721   if (thisblock->exit_label)
3722     {
3723       do_pending_stack_adjust ();
3724       emit_label (thisblock->exit_label);
3725     }
3726
3727   /* If necessary, make handlers for nonlocal gotos taking
3728      place in the function calls in this block.  */
3729   if (function_call_count != thisblock->data.block.n_function_calls
3730       && nonlocal_labels
3731       /* Make handler for outermost block
3732          if there were any nonlocal gotos to this function.  */
3733       && (thisblock->next == 0 ? current_function_has_nonlocal_label
3734           /* Make handler for inner block if it has something
3735              special to do when you jump out of it.  */
3736           : (thisblock->data.block.cleanups != 0
3737              || thisblock->data.block.stack_level != 0)))
3738     expand_nl_goto_receivers (thisblock);
3739
3740   /* Don't allow jumping into a block that has a stack level.
3741      Cleanups are allowed, though.  */
3742   if (dont_jump_in
3743       || thisblock->data.block.stack_level != 0)
3744     {
3745       struct label_chain *chain;
3746
3747       /* Any labels in this block are no longer valid to go to.
3748          Mark them to cause an error message.  */
3749       for (chain = thisblock->data.block.label_chain; chain; chain = chain->next)
3750         {
3751           DECL_TOO_LATE (chain->label) = 1;
3752           /* If any goto without a fixup came to this label,
3753              that must be an error, because gotos without fixups
3754              come from outside all saved stack-levels.  */
3755           if (TREE_ADDRESSABLE (chain->label))
3756             error_with_decl (chain->label,
3757                              "label `%s' used before containing binding contour");
3758         }
3759     }
3760
3761   /* Restore stack level in effect before the block
3762      (only if variable-size objects allocated).  */
3763   /* Perform any cleanups associated with the block.  */
3764
3765   if (thisblock->data.block.stack_level != 0
3766       || thisblock->data.block.cleanups != 0)
3767     {
3768       int reachable;
3769       rtx insn;
3770
3771       /* Don't let cleanups affect ({...}) constructs.  */
3772       int old_expr_stmts_for_value = expr_stmts_for_value;
3773       rtx old_last_expr_value = last_expr_value;
3774       tree old_last_expr_type = last_expr_type;
3775       expr_stmts_for_value = 0;
3776
3777       /* Only clean up here if this point can actually be reached.  */
3778       insn = get_last_insn ();
3779       if (GET_CODE (insn) == NOTE)
3780         insn = prev_nonnote_insn (insn);
3781       reachable = (! insn || GET_CODE (insn) != BARRIER);
3782
3783       /* Do the cleanups.  */
3784       expand_cleanups (thisblock->data.block.cleanups, NULL_TREE, 0, reachable);
3785       if (reachable)
3786         do_pending_stack_adjust ();
3787
3788       expr_stmts_for_value = old_expr_stmts_for_value;
3789       last_expr_value = old_last_expr_value;
3790       last_expr_type = old_last_expr_type;
3791
3792       /* Restore the stack level.  */
3793
3794       if (reachable && thisblock->data.block.stack_level != 0)
3795         {
3796           emit_stack_restore (thisblock->next ? SAVE_BLOCK : SAVE_FUNCTION,
3797                               thisblock->data.block.stack_level, NULL_RTX);
3798           if (nonlocal_goto_handler_slots != 0)
3799             emit_stack_save (SAVE_NONLOCAL, &nonlocal_goto_stack_level,
3800                              NULL_RTX);
3801         }
3802
3803       /* Any gotos out of this block must also do these things.
3804          Also report any gotos with fixups that came to labels in this
3805          level.  */
3806       fixup_gotos (thisblock,
3807                    thisblock->data.block.stack_level,
3808                    thisblock->data.block.cleanups,
3809                    thisblock->data.block.first_insn,
3810                    dont_jump_in);
3811     }
3812
3813   /* Mark the beginning and end of the scope if requested.
3814      We do this now, after running cleanups on the variables
3815      just going out of scope, so they are in scope for their cleanups.  */
3816
3817   if (mark_ends)
3818     {
3819       rtx note = emit_note (NULL, NOTE_INSN_BLOCK_END);
3820       NOTE_BLOCK (note) = NOTE_BLOCK (thisblock->data.block.first_insn);
3821     }
3822   else
3823     /* Get rid of the beginning-mark if we don't make an end-mark.  */
3824     NOTE_LINE_NUMBER (thisblock->data.block.first_insn) = NOTE_INSN_DELETED;
3825
3826   /* Restore the temporary level of TARGET_EXPRs.  */
3827   target_temp_slot_level = thisblock->data.block.block_target_temp_slot_level;
3828
3829   /* Restore block_stack level for containing block.  */
3830
3831   stack_block_stack = thisblock->data.block.innermost_stack_block;
3832   POPSTACK (block_stack);
3833
3834   /* Pop the stack slot nesting and free any slots at this level.  */
3835   pop_temp_slots ();
3836 }
3837 \f
3838 /* Generate code to save the stack pointer at the start of the current block
3839    and set up to restore it on exit.  */
3840
3841 void
3842 save_stack_pointer ()
3843 {
3844   struct nesting *thisblock = block_stack;
3845
3846   if (thisblock->data.block.stack_level == 0)
3847     {
3848       emit_stack_save (thisblock->next ? SAVE_BLOCK : SAVE_FUNCTION,
3849                        &thisblock->data.block.stack_level,
3850                        thisblock->data.block.first_insn);
3851       stack_block_stack = thisblock;
3852     }
3853 }
3854 \f
3855 /* Generate RTL for the automatic variable declaration DECL.
3856    (Other kinds of declarations are simply ignored if seen here.)  */
3857
3858 void
3859 expand_decl (decl)
3860      tree decl;
3861 {
3862   struct nesting *thisblock;
3863   tree type;
3864
3865   type = TREE_TYPE (decl);
3866
3867   /* For a CONST_DECL, set mode, alignment, and sizes from those of the
3868      type in case this node is used in a reference.  */
3869   if (TREE_CODE (decl) == CONST_DECL)
3870     {
3871       DECL_MODE (decl) = TYPE_MODE (type);
3872       DECL_ALIGN (decl) = TYPE_ALIGN (type);
3873       DECL_SIZE (decl) = TYPE_SIZE (type);
3874       DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
3875       return;
3876     }
3877
3878   /* Otherwise, only automatic variables need any expansion done.  Static and
3879      external variables, and external functions, will be handled by
3880      `assemble_variable' (called from finish_decl).  TYPE_DECL requires
3881      nothing.  PARM_DECLs are handled in `assign_parms'.  */
3882   if (TREE_CODE (decl) != VAR_DECL)
3883     return;
3884
3885   if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
3886     return;
3887
3888   thisblock = block_stack;
3889
3890   /* Create the RTL representation for the variable.  */
3891
3892   if (type == error_mark_node)
3893     SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
3894
3895   else if (DECL_SIZE (decl) == 0)
3896     /* Variable with incomplete type.  */
3897     {
3898       rtx x;
3899       if (DECL_INITIAL (decl) == 0)
3900         /* Error message was already done; now avoid a crash.  */
3901         x = gen_rtx_MEM (BLKmode, const0_rtx);
3902       else
3903         /* An initializer is going to decide the size of this array.
3904            Until we know the size, represent its address with a reg.  */
3905         x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
3906
3907       set_mem_attributes (x, decl, 1);
3908       SET_DECL_RTL (decl, x);
3909     }
3910   else if (DECL_MODE (decl) != BLKmode
3911            /* If -ffloat-store, don't put explicit float vars
3912               into regs.  */
3913            && !(flag_float_store
3914                 && TREE_CODE (type) == REAL_TYPE)
3915            && ! TREE_THIS_VOLATILE (decl)
3916            && (DECL_REGISTER (decl) || optimize))
3917     {
3918       /* Automatic variable that can go in a register.  */
3919       int unsignedp = TREE_UNSIGNED (type);
3920       enum machine_mode reg_mode
3921         = promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
3922
3923       SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
3924
3925       if (GET_CODE (DECL_RTL (decl)) == REG)
3926         REGNO_DECL (REGNO (DECL_RTL (decl))) = decl;
3927       else if (GET_CODE (DECL_RTL (decl)) == CONCAT)
3928         {
3929           REGNO_DECL (REGNO (XEXP (DECL_RTL (decl), 0))) = decl;
3930           REGNO_DECL (REGNO (XEXP (DECL_RTL (decl), 1))) = decl;
3931         }
3932
3933       mark_user_reg (DECL_RTL (decl));
3934
3935       if (POINTER_TYPE_P (type))
3936         mark_reg_pointer (DECL_RTL (decl),
3937                           TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
3938
3939       maybe_set_unchanging (DECL_RTL (decl), decl);
3940
3941       /* If something wants our address, try to use ADDRESSOF.  */
3942       if (TREE_ADDRESSABLE (decl))
3943         put_var_into_stack (decl);
3944     }
3945
3946   else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST
3947            && ! (flag_stack_check && ! STACK_CHECK_BUILTIN
3948                  && 0 < compare_tree_int (DECL_SIZE_UNIT (decl),
3949                                           STACK_CHECK_MAX_VAR_SIZE)))
3950     {
3951       /* Variable of fixed size that goes on the stack.  */
3952       rtx oldaddr = 0;
3953       rtx addr;
3954       rtx x;
3955
3956       /* If we previously made RTL for this decl, it must be an array
3957          whose size was determined by the initializer.
3958          The old address was a register; set that register now
3959          to the proper address.  */
3960       if (DECL_RTL_SET_P (decl))
3961         {
3962           if (GET_CODE (DECL_RTL (decl)) != MEM
3963               || GET_CODE (XEXP (DECL_RTL (decl), 0)) != REG)
3964             abort ();
3965           oldaddr = XEXP (DECL_RTL (decl), 0);
3966         }
3967
3968       /* Set alignment we actually gave this decl.  */
3969       DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
3970                            : GET_MODE_BITSIZE (DECL_MODE (decl)));
3971       DECL_USER_ALIGN (decl) = 0;
3972
3973       x = assign_temp (TREE_TYPE (decl), 1, 1, 1);
3974       set_mem_attributes (x, decl, 1);
3975       SET_DECL_RTL (decl, x);
3976
3977       if (oldaddr)
3978         {
3979           addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
3980           if (addr != oldaddr)
3981             emit_move_insn (oldaddr, addr);
3982         }
3983     }
3984   else
3985     /* Dynamic-size object: must push space on the stack.  */
3986     {
3987       rtx address, size, x;
3988
3989       /* Record the stack pointer on entry to block, if have
3990          not already done so.  */
3991       do_pending_stack_adjust ();
3992       save_stack_pointer ();
3993
3994       /* In function-at-a-time mode, variable_size doesn't expand this,
3995          so do it now.  */
3996       if (TREE_CODE (type) == ARRAY_TYPE && TYPE_DOMAIN (type))
3997         expand_expr (TYPE_MAX_VALUE (TYPE_DOMAIN (type)),
3998                      const0_rtx, VOIDmode, 0);
3999
4000       /* Compute the variable's size, in bytes.  */
4001       size = expand_expr (DECL_SIZE_UNIT (decl), NULL_RTX, VOIDmode, 0);
4002       free_temp_slots ();
4003
4004       /* Allocate space on the stack for the variable.  Note that
4005          DECL_ALIGN says how the variable is to be aligned and we
4006          cannot use it to conclude anything about the alignment of
4007          the size.  */
4008       address = allocate_dynamic_stack_space (size, NULL_RTX,
4009                                               TYPE_ALIGN (TREE_TYPE (decl)));
4010
4011       /* Reference the variable indirect through that rtx.  */
4012       x = gen_rtx_MEM (DECL_MODE (decl), address);
4013       set_mem_attributes (x, decl, 1);
4014       SET_DECL_RTL (decl, x);
4015
4016
4017       /* Indicate the alignment we actually gave this variable.  */
4018 #ifdef STACK_BOUNDARY
4019       DECL_ALIGN (decl) = STACK_BOUNDARY;
4020 #else
4021       DECL_ALIGN (decl) = BIGGEST_ALIGNMENT;
4022 #endif
4023       DECL_USER_ALIGN (decl) = 0;
4024     }
4025 }
4026 \f
4027 /* Emit code to perform the initialization of a declaration DECL.  */
4028
4029 void
4030 expand_decl_init (decl)
4031      tree decl;
4032 {
4033   int was_used = TREE_USED (decl);
4034
4035   /* If this is a CONST_DECL, we don't have to generate any code.  Likewise
4036      for static decls.  */
4037   if (TREE_CODE (decl) == CONST_DECL
4038       || TREE_STATIC (decl))
4039     return;
4040
4041   /* Compute and store the initial value now.  */
4042
4043   if (DECL_INITIAL (decl) == error_mark_node)
4044     {
4045       enum tree_code code = TREE_CODE (TREE_TYPE (decl));
4046
4047       if (code == INTEGER_TYPE || code == REAL_TYPE || code == ENUMERAL_TYPE
4048           || code == POINTER_TYPE || code == REFERENCE_TYPE)
4049         expand_assignment (decl, convert (TREE_TYPE (decl), integer_zero_node),
4050                            0, 0);
4051       emit_queue ();
4052     }
4053   else if (DECL_INITIAL (decl) && TREE_CODE (DECL_INITIAL (decl)) != TREE_LIST)
4054     {
4055       emit_line_note (DECL_SOURCE_FILE (decl), DECL_SOURCE_LINE (decl));
4056       expand_assignment (decl, DECL_INITIAL (decl), 0, 0);
4057       emit_queue ();
4058     }
4059
4060   /* Don't let the initialization count as "using" the variable.  */
4061   TREE_USED (decl) = was_used;
4062
4063   /* Free any temporaries we made while initializing the decl.  */
4064   preserve_temp_slots (NULL_RTX);
4065   free_temp_slots ();
4066 }
4067
4068 /* CLEANUP is an expression to be executed at exit from this binding contour;
4069    for example, in C++, it might call the destructor for this variable.
4070
4071    We wrap CLEANUP in an UNSAVE_EXPR node, so that we can expand the
4072    CLEANUP multiple times, and have the correct semantics.  This
4073    happens in exception handling, for gotos, returns, breaks that
4074    leave the current scope.
4075
4076    If CLEANUP is nonzero and DECL is zero, we record a cleanup
4077    that is not associated with any particular variable.  */
4078
4079 int
4080 expand_decl_cleanup (decl, cleanup)
4081      tree decl, cleanup;
4082 {
4083   struct nesting *thisblock;
4084
4085   /* Error if we are not in any block.  */
4086   if (cfun == 0 || block_stack == 0)
4087     return 0;
4088
4089   thisblock = block_stack;
4090
4091   /* Record the cleanup if there is one.  */
4092
4093   if (cleanup != 0)
4094     {
4095       tree t;
4096       rtx seq;
4097       tree *cleanups = &thisblock->data.block.cleanups;
4098       int cond_context = conditional_context ();
4099
4100       if (cond_context)
4101         {
4102           rtx flag = gen_reg_rtx (word_mode);
4103           rtx set_flag_0;
4104           tree cond;
4105
4106           start_sequence ();
4107           emit_move_insn (flag, const0_rtx);
4108           set_flag_0 = get_insns ();
4109           end_sequence ();
4110
4111           thisblock->data.block.last_unconditional_cleanup
4112             = emit_insns_after (set_flag_0,
4113                                 thisblock->data.block.last_unconditional_cleanup);
4114
4115           emit_move_insn (flag, const1_rtx);
4116
4117           cond = build_decl (VAR_DECL, NULL_TREE, type_for_mode (word_mode, 1));
4118           SET_DECL_RTL (cond, flag);
4119
4120           /* Conditionalize the cleanup.  */
4121           cleanup = build (COND_EXPR, void_type_node,
4122                            truthvalue_conversion (cond),
4123                            cleanup, integer_zero_node);
4124           cleanup = fold (cleanup);
4125
4126           cleanups = thisblock->data.block.cleanup_ptr;
4127         }
4128
4129       cleanup = unsave_expr (cleanup);
4130
4131       t = *cleanups = tree_cons (decl, cleanup, *cleanups);
4132
4133       if (! cond_context)
4134         /* If this block has a cleanup, it belongs in stack_block_stack.  */
4135         stack_block_stack = thisblock;
4136
4137       if (cond_context)
4138         {
4139           start_sequence ();
4140         }
4141
4142       if (! using_eh_for_cleanups_p)
4143         TREE_ADDRESSABLE (t) = 1;
4144       else
4145         expand_eh_region_start ();
4146
4147       if (cond_context)
4148         {
4149           seq = get_insns ();
4150           end_sequence ();
4151           if (seq)
4152             thisblock->data.block.last_unconditional_cleanup
4153               = emit_insns_after (seq,
4154                                   thisblock->data.block.last_unconditional_cleanup);
4155         }
4156       else
4157         {
4158           thisblock->data.block.last_unconditional_cleanup
4159             = get_last_insn ();
4160           /* When we insert instructions after the last unconditional cleanup,
4161              we don't adjust last_insn.  That means that a later add_insn will
4162              clobber the instructions we've just added.  The easiest way to
4163              fix this is to just insert another instruction here, so that the
4164              instructions inserted after the last unconditional cleanup are
4165              never the last instruction.  */
4166           emit_note (NULL, NOTE_INSN_DELETED);
4167           thisblock->data.block.cleanup_ptr = &thisblock->data.block.cleanups;
4168         }
4169     }
4170   return 1;
4171 }
4172 \f
4173 /* DECL is an anonymous union.  CLEANUP is a cleanup for DECL.
4174    DECL_ELTS is the list of elements that belong to DECL's type.
4175    In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup.  */
4176
4177 void
4178 expand_anon_union_decl (decl, cleanup, decl_elts)
4179      tree decl, cleanup, decl_elts;
4180 {
4181   struct nesting *thisblock = cfun == 0 ? 0 : block_stack;
4182   rtx x;
4183   tree t;
4184
4185   /* If any of the elements are addressable, so is the entire union.  */
4186   for (t = decl_elts; t; t = TREE_CHAIN (t))
4187     if (TREE_ADDRESSABLE (TREE_VALUE (t)))
4188       {
4189         TREE_ADDRESSABLE (decl) = 1;
4190         break;
4191       }
4192
4193   expand_decl (decl);
4194   expand_decl_cleanup (decl, cleanup);
4195   x = DECL_RTL (decl);
4196
4197   /* Go through the elements, assigning RTL to each.  */
4198   for (t = decl_elts; t; t = TREE_CHAIN (t))
4199     {
4200       tree decl_elt = TREE_VALUE (t);
4201       tree cleanup_elt = TREE_PURPOSE (t);
4202       enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt));
4203
4204       /* Propagate the union's alignment to the elements.  */
4205       DECL_ALIGN (decl_elt) = DECL_ALIGN (decl);
4206       DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl);
4207
4208       /* If the element has BLKmode and the union doesn't, the union is
4209          aligned such that the element doesn't need to have BLKmode, so
4210          change the element's mode to the appropriate one for its size.  */
4211       if (mode == BLKmode && DECL_MODE (decl) != BLKmode)
4212         DECL_MODE (decl_elt) = mode
4213           = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1);
4214
4215       /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we
4216          instead create a new MEM rtx with the proper mode.  */
4217       if (GET_CODE (x) == MEM)
4218         {
4219           if (mode == GET_MODE (x))
4220             SET_DECL_RTL (decl_elt, x);
4221           else
4222             SET_DECL_RTL (decl_elt, adjust_address_nv (x, mode, 0));
4223         }
4224       else if (GET_CODE (x) == REG)
4225         {
4226           if (mode == GET_MODE (x))
4227             SET_DECL_RTL (decl_elt, x);
4228           else
4229             SET_DECL_RTL (decl_elt, gen_lowpart_SUBREG (mode, x));
4230         }
4231       else
4232         abort ();
4233
4234       /* Record the cleanup if there is one.  */
4235
4236       if (cleanup != 0)
4237         thisblock->data.block.cleanups
4238           = tree_cons (decl_elt, cleanup_elt,
4239                        thisblock->data.block.cleanups);
4240     }
4241 }
4242 \f
4243 /* Expand a list of cleanups LIST.
4244    Elements may be expressions or may be nested lists.
4245
4246    If DONT_DO is nonnull, then any list-element
4247    whose TREE_PURPOSE matches DONT_DO is omitted.
4248    This is sometimes used to avoid a cleanup associated with
4249    a value that is being returned out of the scope.
4250
4251    If IN_FIXUP is non-zero, we are generating this cleanup for a fixup
4252    goto and handle protection regions specially in that case.
4253
4254    If REACHABLE, we emit code, otherwise just inform the exception handling
4255    code about this finalization.  */
4256
4257 static void
4258 expand_cleanups (list, dont_do, in_fixup, reachable)
4259      tree list;
4260      tree dont_do;
4261      int in_fixup;
4262      int reachable;
4263 {
4264   tree tail;
4265   for (tail = list; tail; tail = TREE_CHAIN (tail))
4266     if (dont_do == 0 || TREE_PURPOSE (tail) != dont_do)
4267       {
4268         if (TREE_CODE (TREE_VALUE (tail)) == TREE_LIST)
4269           expand_cleanups (TREE_VALUE (tail), dont_do, in_fixup, reachable);
4270         else
4271           {
4272             if (! in_fixup && using_eh_for_cleanups_p)
4273               expand_eh_region_end_cleanup (TREE_VALUE (tail));
4274
4275             if (reachable)
4276               {
4277                 /* Cleanups may be run multiple times.  For example,
4278                    when exiting a binding contour, we expand the
4279                    cleanups associated with that contour.  When a goto
4280                    within that binding contour has a target outside that
4281                    contour, it will expand all cleanups from its scope to
4282                    the target.  Though the cleanups are expanded multiple
4283                    times, the control paths are non-overlapping so the
4284                    cleanups will not be executed twice.  */
4285
4286                 /* We may need to protect from outer cleanups.  */
4287                 if (in_fixup && using_eh_for_cleanups_p)
4288                   {
4289                     expand_eh_region_start ();
4290
4291                     expand_expr (TREE_VALUE (tail), const0_rtx, VOIDmode, 0);
4292
4293                     expand_eh_region_end_fixup (TREE_VALUE (tail));
4294                   }
4295                 else
4296                   expand_expr (TREE_VALUE (tail), const0_rtx, VOIDmode, 0);
4297
4298                 free_temp_slots ();
4299               }
4300           }
4301       }
4302 }
4303
4304 /* Mark when the context we are emitting RTL for as a conditional
4305    context, so that any cleanup actions we register with
4306    expand_decl_init will be properly conditionalized when those
4307    cleanup actions are later performed.  Must be called before any
4308    expression (tree) is expanded that is within a conditional context.  */
4309
4310 void
4311 start_cleanup_deferral ()
4312 {
4313   /* block_stack can be NULL if we are inside the parameter list.  It is
4314      OK to do nothing, because cleanups aren't possible here.  */
4315   if (block_stack)
4316     ++block_stack->data.block.conditional_code;
4317 }
4318
4319 /* Mark the end of a conditional region of code.  Because cleanup
4320    deferrals may be nested, we may still be in a conditional region
4321    after we end the currently deferred cleanups, only after we end all
4322    deferred cleanups, are we back in unconditional code.  */
4323
4324 void
4325 end_cleanup_deferral ()
4326 {
4327   /* block_stack can be NULL if we are inside the parameter list.  It is
4328      OK to do nothing, because cleanups aren't possible here.  */
4329   if (block_stack)
4330     --block_stack->data.block.conditional_code;
4331 }
4332
4333 /* Move all cleanups from the current block_stack
4334    to the containing block_stack, where they are assumed to
4335    have been created.  If anything can cause a temporary to
4336    be created, but not expanded for more than one level of
4337    block_stacks, then this code will have to change.  */
4338
4339 void
4340 move_cleanups_up ()
4341 {
4342   struct nesting *block = block_stack;
4343   struct nesting *outer = block->next;
4344
4345   outer->data.block.cleanups
4346     = chainon (block->data.block.cleanups,
4347                outer->data.block.cleanups);
4348   block->data.block.cleanups = 0;
4349 }
4350
4351 tree
4352 last_cleanup_this_contour ()
4353 {
4354   if (block_stack == 0)
4355     return 0;
4356
4357   return block_stack->data.block.cleanups;
4358 }
4359
4360 /* Return 1 if there are any pending cleanups at this point.
4361    If THIS_CONTOUR is nonzero, check the current contour as well.
4362    Otherwise, look only at the contours that enclose this one.  */
4363
4364 int
4365 any_pending_cleanups (this_contour)
4366      int this_contour;
4367 {
4368   struct nesting *block;
4369
4370   if (cfun == NULL || cfun->stmt == NULL || block_stack == 0)
4371     return 0;
4372
4373   if (this_contour && block_stack->data.block.cleanups != NULL)
4374     return 1;
4375   if (block_stack->data.block.cleanups == 0
4376       && block_stack->data.block.outer_cleanups == 0)
4377     return 0;
4378
4379   for (block = block_stack->next; block; block = block->next)
4380     if (block->data.block.cleanups != 0)
4381       return 1;
4382
4383   return 0;
4384 }
4385 \f
4386 /* Enter a case (Pascal) or switch (C) statement.
4387    Push a block onto case_stack and nesting_stack
4388    to accumulate the case-labels that are seen
4389    and to record the labels generated for the statement.
4390
4391    EXIT_FLAG is nonzero if `exit_something' should exit this case stmt.
4392    Otherwise, this construct is transparent for `exit_something'.
4393
4394    EXPR is the index-expression to be dispatched on.
4395    TYPE is its nominal type.  We could simply convert EXPR to this type,
4396    but instead we take short cuts.  */
4397
4398 void
4399 expand_start_case (exit_flag, expr, type, printname)
4400      int exit_flag;
4401      tree expr;
4402      tree type;
4403      const char *printname;
4404 {
4405   struct nesting *thiscase = ALLOC_NESTING ();
4406
4407   /* Make an entry on case_stack for the case we are entering.  */
4408
4409   thiscase->next = case_stack;
4410   thiscase->all = nesting_stack;
4411   thiscase->depth = ++nesting_depth;
4412   thiscase->exit_label = exit_flag ? gen_label_rtx () : 0;
4413   thiscase->data.case_stmt.case_list = 0;
4414   thiscase->data.case_stmt.index_expr = expr;
4415   thiscase->data.case_stmt.nominal_type = type;
4416   thiscase->data.case_stmt.default_label = 0;
4417   thiscase->data.case_stmt.printname = printname;
4418   thiscase->data.case_stmt.line_number_status = force_line_numbers ();
4419   case_stack = thiscase;
4420   nesting_stack = thiscase;
4421
4422   do_pending_stack_adjust ();
4423
4424   /* Make sure case_stmt.start points to something that won't
4425      need any transformation before expand_end_case.  */
4426   if (GET_CODE (get_last_insn ()) != NOTE)
4427     emit_note (NULL, NOTE_INSN_DELETED);
4428
4429   thiscase->data.case_stmt.start = get_last_insn ();
4430
4431   start_cleanup_deferral ();
4432 }
4433
4434 /* Start a "dummy case statement" within which case labels are invalid
4435    and are not connected to any larger real case statement.
4436    This can be used if you don't want to let a case statement jump
4437    into the middle of certain kinds of constructs.  */
4438
4439 void
4440 expand_start_case_dummy ()
4441 {
4442   struct nesting *thiscase = ALLOC_NESTING ();
4443
4444   /* Make an entry on case_stack for the dummy.  */
4445
4446   thiscase->next = case_stack;
4447   thiscase->all = nesting_stack;
4448   thiscase->depth = ++nesting_depth;
4449   thiscase->exit_label = 0;
4450   thiscase->data.case_stmt.case_list = 0;
4451   thiscase->data.case_stmt.start = 0;
4452   thiscase->data.case_stmt.nominal_type = 0;
4453   thiscase->data.case_stmt.default_label = 0;
4454   case_stack = thiscase;
4455   nesting_stack = thiscase;
4456   start_cleanup_deferral ();
4457 }
4458
4459 /* End a dummy case statement.  */
4460
4461 void
4462 expand_end_case_dummy ()
4463 {
4464   end_cleanup_deferral ();
4465   POPSTACK (case_stack);
4466 }
4467
4468 /* Return the data type of the index-expression
4469    of the innermost case statement, or null if none.  */
4470
4471 tree
4472 case_index_expr_type ()
4473 {
4474   if (case_stack)
4475     return TREE_TYPE (case_stack->data.case_stmt.index_expr);
4476   return 0;
4477 }
4478 \f
4479 static void
4480 check_seenlabel ()
4481 {
4482   /* If this is the first label, warn if any insns have been emitted.  */
4483   if (case_stack->data.case_stmt.line_number_status >= 0)
4484     {
4485       rtx insn;
4486
4487       restore_line_number_status
4488         (case_stack->data.case_stmt.line_number_status);
4489       case_stack->data.case_stmt.line_number_status = -1;
4490
4491       for (insn = case_stack->data.case_stmt.start;
4492            insn;
4493            insn = NEXT_INSN (insn))
4494         {
4495           if (GET_CODE (insn) == CODE_LABEL)
4496             break;
4497           if (GET_CODE (insn) != NOTE
4498               && (GET_CODE (insn) != INSN || GET_CODE (PATTERN (insn)) != USE))
4499             {
4500               do
4501                 insn = PREV_INSN (insn);
4502               while (insn && (GET_CODE (insn) != NOTE || NOTE_LINE_NUMBER (insn) < 0));
4503
4504               /* If insn is zero, then there must have been a syntax error.  */
4505               if (insn)
4506                 warning_with_file_and_line (NOTE_SOURCE_FILE (insn),
4507                                             NOTE_LINE_NUMBER (insn),
4508                                             "unreachable code at beginning of %s",
4509                                             case_stack->data.case_stmt.printname);
4510               break;
4511             }
4512         }
4513     }
4514 }
4515
4516 /* Accumulate one case or default label inside a case or switch statement.
4517    VALUE is the value of the case (a null pointer, for a default label).
4518    The function CONVERTER, when applied to arguments T and V,
4519    converts the value V to the type T.
4520
4521    If not currently inside a case or switch statement, return 1 and do
4522    nothing.  The caller will print a language-specific error message.
4523    If VALUE is a duplicate or overlaps, return 2 and do nothing
4524    except store the (first) duplicate node in *DUPLICATE.
4525    If VALUE is out of range, return 3 and do nothing.
4526    If we are jumping into the scope of a cleanup or var-sized array, return 5.
4527    Return 0 on success.
4528
4529    Extended to handle range statements.  */
4530
4531 int
4532 pushcase (value, converter, label, duplicate)
4533      tree value;
4534      tree (*converter) PARAMS ((tree, tree));
4535      tree label;
4536      tree *duplicate;
4537 {
4538   tree index_type;
4539   tree nominal_type;
4540
4541   /* Fail if not inside a real case statement.  */
4542   if (! (case_stack && case_stack->data.case_stmt.start))
4543     return 1;
4544
4545   if (stack_block_stack
4546       && stack_block_stack->depth > case_stack->depth)
4547     return 5;
4548
4549   index_type = TREE_TYPE (case_stack->data.case_stmt.index_expr);
4550   nominal_type = case_stack->data.case_stmt.nominal_type;
4551
4552   /* If the index is erroneous, avoid more problems: pretend to succeed.  */
4553   if (index_type == error_mark_node)
4554     return 0;
4555
4556   /* Convert VALUE to the type in which the comparisons are nominally done.  */
4557   if (value != 0)
4558     value = (*converter) (nominal_type, value);
4559
4560   check_seenlabel ();
4561
4562   /* Fail if this value is out of range for the actual type of the index
4563      (which may be narrower than NOMINAL_TYPE).  */
4564   if (value != 0
4565       && (TREE_CONSTANT_OVERFLOW (value)
4566           || ! int_fits_type_p (value, index_type)))
4567     return 3;
4568
4569   return add_case_node (value, value, label, duplicate);
4570 }
4571
4572 /* Like pushcase but this case applies to all values between VALUE1 and
4573    VALUE2 (inclusive).  If VALUE1 is NULL, the range starts at the lowest
4574    value of the index type and ends at VALUE2.  If VALUE2 is NULL, the range
4575    starts at VALUE1 and ends at the highest value of the index type.
4576    If both are NULL, this case applies to all values.
4577
4578    The return value is the same as that of pushcase but there is one
4579    additional error code: 4 means the specified range was empty.  */
4580
4581 int
4582 pushcase_range (value1, value2, converter, label, duplicate)
4583      tree value1, value2;
4584      tree (*converter) PARAMS ((tree, tree));
4585      tree label;
4586      tree *duplicate;
4587 {
4588   tree index_type;
4589   tree nominal_type;
4590
4591   /* Fail if not inside a real case statement.  */
4592   if (! (case_stack && case_stack->data.case_stmt.start))
4593     return 1;
4594
4595   if (stack_block_stack
4596       && stack_block_stack->depth > case_stack->depth)
4597     return 5;
4598
4599   index_type = TREE_TYPE (case_stack->data.case_stmt.index_expr);
4600   nominal_type = case_stack->data.case_stmt.nominal_type;
4601
4602   /* If the index is erroneous, avoid more problems: pretend to succeed.  */
4603   if (index_type == error_mark_node)
4604     return 0;
4605
4606   check_seenlabel ();
4607
4608   /* Convert VALUEs to type in which the comparisons are nominally done
4609      and replace any unspecified value with the corresponding bound.  */
4610   if (value1 == 0)
4611     value1 = TYPE_MIN_VALUE (index_type);
4612   if (value2 == 0)
4613     value2 = TYPE_MAX_VALUE (index_type);
4614
4615   /* Fail if the range is empty.  Do this before any conversion since
4616      we want to allow out-of-range empty ranges.  */
4617   if (value2 != 0 && tree_int_cst_lt (value2, value1))
4618     return 4;
4619
4620   /* If the max was unbounded, use the max of the nominal_type we are
4621      converting to.  Do this after the < check above to suppress false
4622      positives.  */
4623   if (value2 == 0)
4624     value2 = TYPE_MAX_VALUE (nominal_type);
4625
4626   value1 = (*converter) (nominal_type, value1);
4627   value2 = (*converter) (nominal_type, value2);
4628
4629   /* Fail if these values are out of range.  */
4630   if (TREE_CONSTANT_OVERFLOW (value1)
4631       || ! int_fits_type_p (value1, index_type))
4632     return 3;
4633
4634   if (TREE_CONSTANT_OVERFLOW (value2)
4635       || ! int_fits_type_p (value2, index_type))
4636     return 3;
4637
4638   return add_case_node (value1, value2, label, duplicate);
4639 }
4640
4641 /* Do the actual insertion of a case label for pushcase and pushcase_range
4642    into case_stack->data.case_stmt.case_list.  Use an AVL tree to avoid
4643    slowdown for large switch statements.  */
4644
4645 int
4646 add_case_node (low, high, label, duplicate)
4647      tree low, high;
4648      tree label;
4649      tree *duplicate;
4650 {
4651   struct case_node *p, **q, *r;
4652
4653   /* If there's no HIGH value, then this is not a case range; it's
4654      just a simple case label.  But that's just a degenerate case
4655      range.  */
4656   if (!high)
4657     high = low;
4658
4659   /* Handle default labels specially.  */
4660   if (!high && !low)
4661     {
4662       if (case_stack->data.case_stmt.default_label != 0)
4663         {
4664           *duplicate = case_stack->data.case_stmt.default_label;
4665           return 2;
4666         }
4667       case_stack->data.case_stmt.default_label = label;
4668       expand_label (label);
4669       return 0;
4670     }
4671
4672   q = &case_stack->data.case_stmt.case_list;
4673   p = *q;
4674
4675   while ((r = *q))
4676     {
4677       p = r;
4678
4679       /* Keep going past elements distinctly greater than HIGH.  */
4680       if (tree_int_cst_lt (high, p->low))
4681         q = &p->left;
4682
4683       /* or distinctly less than LOW.  */
4684       else if (tree_int_cst_lt (p->high, low))
4685         q = &p->right;
4686
4687       else
4688         {
4689           /* We have an overlap; this is an error.  */
4690           *duplicate = p->code_label;
4691           return 2;
4692         }
4693     }
4694
4695   /* Add this label to the chain, and succeed.  */
4696
4697   r = (struct case_node *) xmalloc (sizeof (struct case_node));
4698   r->low = low;
4699
4700   /* If the bounds are equal, turn this into the one-value case.  */
4701   if (tree_int_cst_equal (low, high))
4702     r->high = r->low;
4703   else
4704     r->high = high;
4705
4706   r->code_label = label;
4707   expand_label (label);
4708
4709   *q = r;
4710   r->parent = p;
4711   r->left = 0;
4712   r->right = 0;
4713   r->balance = 0;
4714
4715   while (p)
4716     {
4717       struct case_node *s;
4718
4719       if (r == p->left)
4720         {
4721           int b;
4722
4723           if (! (b = p->balance))
4724             /* Growth propagation from left side.  */
4725             p->balance = -1;
4726           else if (b < 0)
4727             {
4728               if (r->balance < 0)
4729                 {
4730                   /* R-Rotation */
4731                   if ((p->left = s = r->right))
4732                     s->parent = p;
4733
4734                   r->right = p;
4735                   p->balance = 0;
4736                   r->balance = 0;
4737                   s = p->parent;
4738                   p->parent = r;
4739
4740                   if ((r->parent = s))
4741                     {
4742                       if (s->left == p)
4743                         s->left = r;
4744                       else
4745                         s->right = r;
4746                     }
4747                   else
4748                     case_stack->data.case_stmt.case_list = r;
4749                 }
4750               else
4751                 /* r->balance == +1 */
4752                 {
4753                   /* LR-Rotation */
4754
4755                   int b2;
4756                   struct case_node *t = r->right;
4757
4758                   if ((p->left = s = t->right))
4759                     s->parent = p;
4760
4761                   t->right = p;
4762                   if ((r->right = s = t->left))
4763                     s->parent = r;
4764
4765                   t->left = r;
4766                   b = t->balance;
4767                   b2 = b < 0;
4768                   p->balance = b2;
4769                   b2 = -b2 - b;
4770                   r->balance = b2;
4771                   t->balance = 0;
4772                   s = p->parent;
4773                   p->parent = t;
4774                   r->parent = t;
4775
4776                   if ((t->parent = s))
4777                     {
4778                       if (s->left == p)
4779                         s->left = t;
4780                       else
4781                         s->right = t;
4782                     }
4783                   else
4784                     case_stack->data.case_stmt.case_list = t;
4785                 }
4786               break;
4787             }
4788
4789           else
4790             {
4791               /* p->balance == +1; growth of left side balances the node.  */
4792               p->balance = 0;
4793               break;
4794             }
4795         }
4796       else
4797         /* r == p->right */
4798         {
4799           int b;
4800
4801           if (! (b = p->balance))
4802             /* Growth propagation from right side.  */
4803             p->balance++;
4804           else if (b > 0)
4805             {
4806               if (r->balance > 0)
4807                 {
4808                   /* L-Rotation */
4809
4810                   if ((p->right = s = r->left))
4811                     s->parent = p;
4812
4813                   r->left = p;
4814                   p->balance = 0;
4815                   r->balance = 0;
4816                   s = p->parent;
4817                   p->parent = r;
4818                   if ((r->parent = s))
4819                     {
4820                       if (s->left == p)
4821                         s->left = r;
4822                       else
4823                         s->right = r;
4824                     }
4825
4826                   else
4827                     case_stack->data.case_stmt.case_list = r;
4828                 }
4829
4830               else
4831                 /* r->balance == -1 */
4832                 {
4833                   /* RL-Rotation */
4834                   int b2;
4835                   struct case_node *t = r->left;
4836
4837                   if ((p->right = s = t->left))
4838                     s->parent = p;
4839
4840                   t->left = p;
4841
4842                   if ((r->left = s = t->right))
4843                     s->parent = r;
4844
4845                   t->right = r;
4846                   b = t->balance;
4847                   b2 = b < 0;
4848                   r->balance = b2;
4849                   b2 = -b2 - b;
4850                   p->balance = b2;
4851                   t->balance = 0;
4852                   s = p->parent;
4853                   p->parent = t;
4854                   r->parent = t;
4855
4856                   if ((t->parent = s))
4857                     {
4858                       if (s->left == p)
4859                         s->left = t;
4860                       else
4861                         s->right = t;
4862                     }
4863
4864                   else
4865                     case_stack->data.case_stmt.case_list = t;
4866                 }
4867               break;
4868             }
4869           else
4870             {
4871               /* p->balance == -1; growth of right side balances the node.  */
4872               p->balance = 0;
4873               break;
4874             }
4875         }
4876
4877       r = p;
4878       p = p->parent;
4879     }
4880
4881   return 0;
4882 }
4883 \f
4884 /* Returns the number of possible values of TYPE.
4885    Returns -1 if the number is unknown, variable, or if the number does not
4886    fit in a HOST_WIDE_INT.
4887    Sets *SPARSENESS to 2 if TYPE is an ENUMERAL_TYPE whose values
4888    do not increase monotonically (there may be duplicates);
4889    to 1 if the values increase monotonically, but not always by 1;
4890    otherwise sets it to 0.  */
4891
4892 HOST_WIDE_INT
4893 all_cases_count (type, sparseness)
4894      tree type;
4895      int *sparseness;
4896 {
4897   tree t;
4898   HOST_WIDE_INT count, minval, lastval;
4899
4900   *sparseness = 0;
4901
4902   switch (TREE_CODE (type))
4903     {
4904     case BOOLEAN_TYPE:
4905       count = 2;
4906       break;
4907
4908     case CHAR_TYPE:
4909       count = 1 << BITS_PER_UNIT;
4910       break;
4911
4912     default:
4913     case INTEGER_TYPE:
4914       if (TYPE_MAX_VALUE (type) != 0
4915           && 0 != (t = fold (build (MINUS_EXPR, type, TYPE_MAX_VALUE (type),
4916                                     TYPE_MIN_VALUE (type))))
4917           && 0 != (t = fold (build (PLUS_EXPR, type, t,
4918                                     convert (type, integer_zero_node))))
4919           && host_integerp (t, 1))
4920         count = tree_low_cst (t, 1);
4921       else
4922         return -1;
4923       break;
4924
4925     case ENUMERAL_TYPE:
4926       /* Don't waste time with enumeral types with huge values.  */
4927       if (! host_integerp (TYPE_MIN_VALUE (type), 0)
4928           || TYPE_MAX_VALUE (type) == 0
4929           || ! host_integerp (TYPE_MAX_VALUE (type), 0))
4930         return -1;
4931
4932       lastval = minval = tree_low_cst (TYPE_MIN_VALUE (type), 0);
4933       count = 0;
4934
4935       for (t = TYPE_VALUES (type); t != NULL_TREE; t = TREE_CHAIN (t))
4936         {
4937           HOST_WIDE_INT thisval = tree_low_cst (TREE_VALUE (t), 0);
4938
4939           if (*sparseness == 2 || thisval <= lastval)
4940             *sparseness = 2;
4941           else if (thisval != minval + count)
4942             *sparseness = 1;
4943
4944           lastval = thisval;
4945           count++;
4946         }
4947     }
4948
4949   return count;
4950 }
4951
4952 #define BITARRAY_TEST(ARRAY, INDEX) \
4953   ((ARRAY)[(unsigned) (INDEX) / HOST_BITS_PER_CHAR]\
4954                           & (1 << ((unsigned) (INDEX) % HOST_BITS_PER_CHAR)))
4955 #define BITARRAY_SET(ARRAY, INDEX) \
4956   ((ARRAY)[(unsigned) (INDEX) / HOST_BITS_PER_CHAR]\
4957                           |= 1 << ((unsigned) (INDEX) % HOST_BITS_PER_CHAR))
4958
4959 /* Set the elements of the bitstring CASES_SEEN (which has length COUNT),
4960    with the case values we have seen, assuming the case expression
4961    has the given TYPE.
4962    SPARSENESS is as determined by all_cases_count.
4963
4964    The time needed is proportional to COUNT, unless
4965    SPARSENESS is 2, in which case quadratic time is needed.  */
4966
4967 void
4968 mark_seen_cases (type, cases_seen, count, sparseness)
4969      tree type;
4970      unsigned char *cases_seen;
4971      HOST_WIDE_INT count;
4972      int sparseness;
4973 {
4974   tree next_node_to_try = NULL_TREE;
4975   HOST_WIDE_INT next_node_offset = 0;
4976
4977   struct case_node *n, *root = case_stack->data.case_stmt.case_list;
4978   tree val = make_node (INTEGER_CST);
4979
4980   TREE_TYPE (val) = type;
4981   if (! root)
4982     /* Do nothing.  */
4983     ;
4984   else if (sparseness == 2)
4985     {
4986       tree t;
4987       unsigned HOST_WIDE_INT xlo;
4988
4989       /* This less efficient loop is only needed to handle
4990          duplicate case values (multiple enum constants
4991          with the same value).  */
4992       TREE_TYPE (val) = TREE_TYPE (root->low);
4993       for (t = TYPE_VALUES (type), xlo = 0; t != NULL_TREE;
4994            t = TREE_CHAIN (t), xlo++)
4995         {
4996           TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (TREE_VALUE (t));
4997           TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (TREE_VALUE (t));
4998           n = root;
4999           do
5000             {
5001               /* Keep going past elements distinctly greater than VAL.  */
5002               if (tree_int_cst_lt (val, n->low))
5003                 n = n->left;
5004
5005               /* or distinctly less than VAL.  */
5006               else if (tree_int_cst_lt (n->high, val))
5007                 n = n->right;
5008
5009               else
5010                 {
5011                   /* We have found a matching range.  */
5012                   BITARRAY_SET (cases_seen, xlo);
5013                   break;
5014                 }
5015             }
5016           while (n);
5017         }
5018     }
5019   else
5020     {
5021       if (root->left)
5022         case_stack->data.case_stmt.case_list = root = case_tree2list (root, 0);
5023
5024       for (n = root; n; n = n->right)
5025         {
5026           TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (n->low);
5027           TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (n->low);
5028           while (! tree_int_cst_lt (n->high, val))
5029             {
5030               /* Calculate (into xlo) the "offset" of the integer (val).
5031                  The element with lowest value has offset 0, the next smallest
5032                  element has offset 1, etc.  */
5033
5034               unsigned HOST_WIDE_INT xlo;
5035               HOST_WIDE_INT xhi;
5036               tree t;
5037
5038               if (sparseness && TYPE_VALUES (type) != NULL_TREE)
5039                 {
5040                   /* The TYPE_VALUES will be in increasing order, so
5041                      starting searching where we last ended.  */
5042                   t = next_node_to_try;
5043                   xlo = next_node_offset;
5044                   xhi = 0;
5045                   for (;;)
5046                     {
5047                       if (t == NULL_TREE)
5048                         {
5049                           t = TYPE_VALUES (type);
5050                           xlo = 0;
5051                         }
5052                       if (tree_int_cst_equal (val, TREE_VALUE (t)))
5053                         {
5054                           next_node_to_try = TREE_CHAIN (t);
5055                           next_node_offset = xlo + 1;
5056                           break;
5057                         }
5058                       xlo++;
5059                       t = TREE_CHAIN (t);
5060                       if (t == next_node_to_try)
5061                         {
5062                           xlo = -1;
5063                           break;
5064                         }
5065                     }
5066                 }
5067               else
5068                 {
5069                   t = TYPE_MIN_VALUE (type);
5070                   if (t)
5071                     neg_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t),
5072                                 &xlo, &xhi);
5073                   else
5074                     xlo = xhi = 0;
5075                   add_double (xlo, xhi,
5076                               TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
5077                               &xlo, &xhi);
5078                 }
5079
5080               if (xhi == 0 && xlo < (unsigned HOST_WIDE_INT) count)
5081                 BITARRAY_SET (cases_seen, xlo);
5082
5083               add_double (TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
5084                           1, 0,
5085                           &TREE_INT_CST_LOW (val), &TREE_INT_CST_HIGH (val));
5086             }
5087         }
5088     }
5089 }
5090
5091 /* Called when the index of a switch statement is an enumerated type
5092    and there is no default label.
5093
5094    Checks that all enumeration literals are covered by the case
5095    expressions of a switch.  Also, warn if there are any extra
5096    switch cases that are *not* elements of the enumerated type.
5097
5098    If all enumeration literals were covered by the case expressions,
5099    turn one of the expressions into the default expression since it should
5100    not be possible to fall through such a switch.  */
5101
5102 void
5103 check_for_full_enumeration_handling (type)
5104      tree type;
5105 {
5106   struct case_node *n;
5107   tree chain;
5108
5109   /* True iff the selector type is a numbered set mode.  */
5110   int sparseness = 0;
5111
5112   /* The number of possible selector values.  */
5113   HOST_WIDE_INT size;
5114
5115   /* For each possible selector value. a one iff it has been matched
5116      by a case value alternative.  */
5117   unsigned char *cases_seen;
5118
5119   /* The allocated size of cases_seen, in chars.  */
5120   HOST_WIDE_INT bytes_needed;
5121
5122   if (! warn_switch)
5123     return;
5124
5125   size = all_cases_count (type, &sparseness);
5126   bytes_needed = (size + HOST_BITS_PER_CHAR) / HOST_BITS_PER_CHAR;
5127
5128   if (size > 0 && size < 600000
5129       /* We deliberately use calloc here, not cmalloc, so that we can suppress
5130          this optimization if we don't have enough memory rather than
5131          aborting, as xmalloc would do.  */
5132       && (cases_seen =
5133           (unsigned char *) really_call_calloc (bytes_needed, 1)) != NULL)
5134     {
5135       HOST_WIDE_INT i;
5136       tree v = TYPE_VALUES (type);
5137
5138       /* The time complexity of this code is normally O(N), where
5139          N being the number of members in the enumerated type.
5140          However, if type is a ENUMERAL_TYPE whose values do not
5141          increase monotonically, O(N*log(N)) time may be needed.  */
5142
5143       mark_seen_cases (type, cases_seen, size, sparseness);
5144
5145       for (i = 0; v != NULL_TREE && i < size; i++, v = TREE_CHAIN (v))
5146         if (BITARRAY_TEST (cases_seen, i) == 0)
5147           warning ("enumeration value `%s' not handled in switch",
5148                    IDENTIFIER_POINTER (TREE_PURPOSE (v)));
5149
5150       free (cases_seen);
5151     }
5152
5153   /* Now we go the other way around; we warn if there are case
5154      expressions that don't correspond to enumerators.  This can
5155      occur since C and C++ don't enforce type-checking of
5156      assignments to enumeration variables.  */
5157
5158   if (case_stack->data.case_stmt.case_list
5159       && case_stack->data.case_stmt.case_list->left)
5160     case_stack->data.case_stmt.case_list
5161       = case_tree2list (case_stack->data.case_stmt.case_list, 0);
5162   if (warn_switch)
5163     for (n = case_stack->data.case_stmt.case_list; n; n = n->right)
5164       {
5165         for (chain = TYPE_VALUES (type);
5166              chain && !tree_int_cst_equal (n->low, TREE_VALUE (chain));
5167              chain = TREE_CHAIN (chain))
5168           ;
5169
5170         if (!chain)
5171           {
5172             if (TYPE_NAME (type) == 0)
5173               warning ("case value `%ld' not in enumerated type",
5174                        (long) TREE_INT_CST_LOW (n->low));
5175             else
5176               warning ("case value `%ld' not in enumerated type `%s'",
5177                        (long) TREE_INT_CST_LOW (n->low),
5178                        IDENTIFIER_POINTER ((TREE_CODE (TYPE_NAME (type))
5179                                             == IDENTIFIER_NODE)
5180                                            ? TYPE_NAME (type)
5181                                            : DECL_NAME (TYPE_NAME (type))));
5182           }
5183         if (!tree_int_cst_equal (n->low, n->high))
5184           {
5185             for (chain = TYPE_VALUES (type);
5186                  chain && !tree_int_cst_equal (n->high, TREE_VALUE (chain));
5187                  chain = TREE_CHAIN (chain))
5188               ;
5189
5190             if (!chain)
5191               {
5192                 if (TYPE_NAME (type) == 0)
5193                   warning ("case value `%ld' not in enumerated type",
5194                            (long) TREE_INT_CST_LOW (n->high));
5195                 else
5196                   warning ("case value `%ld' not in enumerated type `%s'",
5197                            (long) TREE_INT_CST_LOW (n->high),
5198                            IDENTIFIER_POINTER ((TREE_CODE (TYPE_NAME (type))
5199                                                 == IDENTIFIER_NODE)
5200                                                ? TYPE_NAME (type)
5201                                                : DECL_NAME (TYPE_NAME (type))));
5202               }
5203           }
5204       }
5205 }
5206
5207 /* Free CN, and its children.  */
5208
5209 static void
5210 free_case_nodes (cn)
5211      case_node_ptr cn;
5212 {
5213   if (cn)
5214     {
5215       free_case_nodes (cn->left);
5216       free_case_nodes (cn->right);
5217       free (cn);
5218     }
5219 }
5220
5221 \f
5222
5223 /* Terminate a case (Pascal) or switch (C) statement
5224    in which ORIG_INDEX is the expression to be tested.
5225    If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
5226    type as given in the source before any compiler conversions.
5227    Generate the code to test it and jump to the right place.  */
5228
5229 void
5230 expand_end_case_type (orig_index, orig_type)
5231      tree orig_index, orig_type;
5232 {
5233   tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
5234   rtx default_label = 0;
5235   struct case_node *n;
5236   unsigned int count;
5237   rtx index;
5238   rtx table_label;
5239   int ncases;
5240   rtx *labelvec;
5241   int i;
5242   rtx before_case, end;
5243   struct nesting *thiscase = case_stack;
5244   tree index_expr, index_type;
5245   int unsignedp;
5246
5247   /* Don't crash due to previous errors.  */
5248   if (thiscase == NULL)
5249     return;
5250
5251   table_label = gen_label_rtx ();
5252   index_expr = thiscase->data.case_stmt.index_expr;
5253   index_type = TREE_TYPE (index_expr);
5254   unsignedp = TREE_UNSIGNED (index_type);
5255   if (orig_type == NULL)
5256     orig_type = TREE_TYPE (orig_index);
5257
5258   do_pending_stack_adjust ();
5259
5260   /* This might get an spurious warning in the presence of a syntax error;
5261      it could be fixed by moving the call to check_seenlabel after the
5262      check for error_mark_node, and copying the code of check_seenlabel that
5263      deals with case_stack->data.case_stmt.line_number_status /
5264      restore_line_number_status in front of the call to end_cleanup_deferral;
5265      However, this might miss some useful warnings in the presence of
5266      non-syntax errors.  */
5267   check_seenlabel ();
5268
5269   /* An ERROR_MARK occurs for various reasons including invalid data type.  */
5270   if (index_type != error_mark_node)
5271     {
5272       /* If switch expression was an enumerated type, check that all
5273          enumeration literals are covered by the cases.
5274          No sense trying this if there's a default case, however.  */
5275
5276       if (!thiscase->data.case_stmt.default_label
5277           && TREE_CODE (orig_type) == ENUMERAL_TYPE
5278           && TREE_CODE (index_expr) != INTEGER_CST)
5279         check_for_full_enumeration_handling (orig_type);
5280
5281       /* If we don't have a default-label, create one here,
5282          after the body of the switch.  */
5283       if (thiscase->data.case_stmt.default_label == 0)
5284         {
5285           thiscase->data.case_stmt.default_label
5286             = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
5287           expand_label (thiscase->data.case_stmt.default_label);
5288         }
5289       default_label = label_rtx (thiscase->data.case_stmt.default_label);
5290
5291       before_case = get_last_insn ();
5292
5293       if (thiscase->data.case_stmt.case_list
5294           && thiscase->data.case_stmt.case_list->left)
5295         thiscase->data.case_stmt.case_list
5296           = case_tree2list (thiscase->data.case_stmt.case_list, 0);
5297
5298       /* Simplify the case-list before we count it.  */
5299       group_case_nodes (thiscase->data.case_stmt.case_list);
5300
5301       /* Get upper and lower bounds of case values.
5302          Also convert all the case values to the index expr's data type.  */
5303
5304       count = 0;
5305       for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5306         {
5307           /* Check low and high label values are integers.  */
5308           if (TREE_CODE (n->low) != INTEGER_CST)
5309             abort ();
5310           if (TREE_CODE (n->high) != INTEGER_CST)
5311             abort ();
5312
5313           n->low = convert (index_type, n->low);
5314           n->high = convert (index_type, n->high);
5315
5316           /* Count the elements and track the largest and smallest
5317              of them (treating them as signed even if they are not).  */
5318           if (count++ == 0)
5319             {
5320               minval = n->low;
5321               maxval = n->high;
5322             }
5323           else
5324             {
5325               if (INT_CST_LT (n->low, minval))
5326                 minval = n->low;
5327               if (INT_CST_LT (maxval, n->high))
5328                 maxval = n->high;
5329             }
5330           /* A range counts double, since it requires two compares.  */
5331           if (! tree_int_cst_equal (n->low, n->high))
5332             count++;
5333         }
5334
5335       /* Compute span of values.  */
5336       if (count != 0)
5337         range = fold (build (MINUS_EXPR, index_type, maxval, minval));
5338
5339       end_cleanup_deferral ();
5340
5341       if (count == 0)
5342         {
5343           expand_expr (index_expr, const0_rtx, VOIDmode, 0);
5344           emit_queue ();
5345           emit_jump (default_label);
5346         }
5347
5348       /* If range of values is much bigger than number of values,
5349          make a sequence of conditional branches instead of a dispatch.
5350          If the switch-index is a constant, do it this way
5351          because we can optimize it.  */
5352
5353       else if (count < case_values_threshold ()
5354                || compare_tree_int (range, 10 * count) > 0
5355                /* RANGE may be signed, and really large ranges will show up
5356                   as negative numbers.  */
5357                || compare_tree_int (range, 0) < 0
5358 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
5359                || flag_pic
5360 #endif
5361                || TREE_CODE (index_expr) == INTEGER_CST
5362                || (TREE_CODE (index_expr) == COMPOUND_EXPR
5363                    && TREE_CODE (TREE_OPERAND (index_expr, 1)) == INTEGER_CST))
5364         {
5365           index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
5366
5367           /* If the index is a short or char that we do not have
5368              an insn to handle comparisons directly, convert it to
5369              a full integer now, rather than letting each comparison
5370              generate the conversion.  */
5371
5372           if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
5373               && ! have_insn_for (COMPARE, GET_MODE (index)))
5374             {
5375               enum machine_mode wider_mode;
5376               for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
5377                    wider_mode = GET_MODE_WIDER_MODE (wider_mode))
5378                 if (have_insn_for (COMPARE, wider_mode))
5379                   {
5380                     index = convert_to_mode (wider_mode, index, unsignedp);
5381                     break;
5382                   }
5383             }
5384
5385           emit_queue ();
5386           do_pending_stack_adjust ();
5387
5388           index = protect_from_queue (index, 0);
5389           if (GET_CODE (index) == MEM)
5390             index = copy_to_reg (index);
5391           if (GET_CODE (index) == CONST_INT
5392               || TREE_CODE (index_expr) == INTEGER_CST)
5393             {
5394               /* Make a tree node with the proper constant value
5395                  if we don't already have one.  */
5396               if (TREE_CODE (index_expr) != INTEGER_CST)
5397                 {
5398                   index_expr
5399                     = build_int_2 (INTVAL (index),
5400                                    unsignedp || INTVAL (index) >= 0 ? 0 : -1);
5401                   index_expr = convert (index_type, index_expr);
5402                 }
5403
5404               /* For constant index expressions we need only
5405                  issue an unconditional branch to the appropriate
5406                  target code.  The job of removing any unreachable
5407                  code is left to the optimisation phase if the
5408                  "-O" option is specified.  */
5409               for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5410                 if (! tree_int_cst_lt (index_expr, n->low)
5411                     && ! tree_int_cst_lt (n->high, index_expr))
5412                   break;
5413
5414               if (n)
5415                 emit_jump (label_rtx (n->code_label));
5416               else
5417                 emit_jump (default_label);
5418             }
5419           else
5420             {
5421               /* If the index expression is not constant we generate
5422                  a binary decision tree to select the appropriate
5423                  target code.  This is done as follows:
5424
5425                  The list of cases is rearranged into a binary tree,
5426                  nearly optimal assuming equal probability for each case.
5427
5428                  The tree is transformed into RTL, eliminating
5429                  redundant test conditions at the same time.
5430
5431                  If program flow could reach the end of the
5432                  decision tree an unconditional jump to the
5433                  default code is emitted.  */
5434
5435               use_cost_table
5436                 = (TREE_CODE (orig_type) != ENUMERAL_TYPE
5437                    && estimate_case_costs (thiscase->data.case_stmt.case_list));
5438               balance_case_nodes (&thiscase->data.case_stmt.case_list, NULL);
5439               emit_case_nodes (index, thiscase->data.case_stmt.case_list,
5440                                default_label, index_type);
5441               emit_jump_if_reachable (default_label);
5442             }
5443         }
5444       else
5445         {
5446           if (! try_casesi (index_type, index_expr, minval, range,
5447                             table_label, default_label))
5448             {
5449               index_type = thiscase->data.case_stmt.nominal_type;
5450
5451               /* Index jumptables from zero for suitable values of
5452                  minval to avoid a subtraction.  */
5453               if (! optimize_size
5454                   && compare_tree_int (minval, 0) > 0
5455                   && compare_tree_int (minval, 3) < 0)
5456                 {
5457                   minval = integer_zero_node;
5458                   range = maxval;
5459                 }
5460
5461               if (! try_tablejump (index_type, index_expr, minval, range,
5462                                    table_label, default_label))
5463                 abort ();
5464             }
5465
5466           /* Get table of labels to jump to, in order of case index.  */
5467
5468           ncases = tree_low_cst (range, 0) + 1;
5469           labelvec = (rtx *) alloca (ncases * sizeof (rtx));
5470           memset ((char *) labelvec, 0, ncases * sizeof (rtx));
5471
5472           for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5473             {
5474               /* Compute the low and high bounds relative to the minimum
5475                  value since that should fit in a HOST_WIDE_INT while the
5476                  actual values may not.  */
5477               HOST_WIDE_INT i_low
5478                 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5479                                              n->low, minval)), 1);
5480               HOST_WIDE_INT i_high
5481                 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5482                                              n->high, minval)), 1);
5483               HOST_WIDE_INT i;
5484
5485               for (i = i_low; i <= i_high; i ++)
5486                 labelvec[i]
5487                   = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
5488             }
5489
5490           /* Fill in the gaps with the default.  */
5491           for (i = 0; i < ncases; i++)
5492             if (labelvec[i] == 0)
5493               labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
5494
5495           /* Output the table */
5496           emit_label (table_label);
5497
5498           if (CASE_VECTOR_PC_RELATIVE || flag_pic)
5499             emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
5500                                                    gen_rtx_LABEL_REF (Pmode, table_label),
5501                                                    gen_rtvec_v (ncases, labelvec),
5502                                                    const0_rtx, const0_rtx));
5503           else
5504             emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
5505                                               gen_rtvec_v (ncases, labelvec)));
5506
5507           /* If the case insn drops through the table,
5508              after the table we must jump to the default-label.
5509              Otherwise record no drop-through after the table.  */
5510 #ifdef CASE_DROPS_THROUGH
5511           emit_jump (default_label);
5512 #else
5513           emit_barrier ();
5514 #endif
5515         }
5516
5517       before_case = NEXT_INSN (before_case);
5518       end = get_last_insn ();
5519       if (squeeze_notes (&before_case, &end))
5520         abort ();
5521       reorder_insns (before_case, end,
5522                      thiscase->data.case_stmt.start);
5523     }
5524   else
5525     end_cleanup_deferral ();
5526
5527   if (thiscase->exit_label)
5528     emit_label (thiscase->exit_label);
5529
5530   free_case_nodes (case_stack->data.case_stmt.case_list);
5531   POPSTACK (case_stack);
5532
5533   free_temp_slots ();
5534 }
5535
5536 /* Convert the tree NODE into a list linked by the right field, with the left
5537    field zeroed.  RIGHT is used for recursion; it is a list to be placed
5538    rightmost in the resulting list.  */
5539
5540 static struct case_node *
5541 case_tree2list (node, right)
5542      struct case_node *node, *right;
5543 {
5544   struct case_node *left;
5545
5546   if (node->right)
5547     right = case_tree2list (node->right, right);
5548
5549   node->right = right;
5550   if ((left = node->left))
5551     {
5552       node->left = 0;
5553       return case_tree2list (left, node);
5554     }
5555
5556   return node;
5557 }
5558
5559 /* Generate code to jump to LABEL if OP1 and OP2 are equal.  */
5560
5561 static void
5562 do_jump_if_equal (op1, op2, label, unsignedp)
5563      rtx op1, op2, label;
5564      int unsignedp;
5565 {
5566   if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
5567     {
5568       if (INTVAL (op1) == INTVAL (op2))
5569         emit_jump (label);
5570     }
5571   else
5572     emit_cmp_and_jump_insns (op1, op2, EQ, NULL_RTX,
5573                              (GET_MODE (op1) == VOIDmode
5574                              ? GET_MODE (op2) : GET_MODE (op1)),
5575                              unsignedp, label);
5576 }
5577 \f
5578 /* Not all case values are encountered equally.  This function
5579    uses a heuristic to weight case labels, in cases where that
5580    looks like a reasonable thing to do.
5581
5582    Right now, all we try to guess is text, and we establish the
5583    following weights:
5584
5585         chars above space:      16
5586         digits:                 16
5587         default:                12
5588         space, punct:           8
5589         tab:                    4
5590         newline:                2
5591         other "\" chars:        1
5592         remaining chars:        0
5593
5594    If we find any cases in the switch that are not either -1 or in the range
5595    of valid ASCII characters, or are control characters other than those
5596    commonly used with "\", don't treat this switch scanning text.
5597
5598    Return 1 if these nodes are suitable for cost estimation, otherwise
5599    return 0.  */
5600
5601 static int
5602 estimate_case_costs (node)
5603      case_node_ptr node;
5604 {
5605   tree min_ascii = integer_minus_one_node;
5606   tree max_ascii = convert (TREE_TYPE (node->high), build_int_2 (127, 0));
5607   case_node_ptr n;
5608   int i;
5609
5610   /* If we haven't already made the cost table, make it now.  Note that the
5611      lower bound of the table is -1, not zero.  */
5612
5613   if (! cost_table_initialized)
5614     {
5615       cost_table_initialized = 1;
5616
5617       for (i = 0; i < 128; i++)
5618         {
5619           if (ISALNUM (i))
5620             COST_TABLE (i) = 16;
5621           else if (ISPUNCT (i))
5622             COST_TABLE (i) = 8;
5623           else if (ISCNTRL (i))
5624             COST_TABLE (i) = -1;
5625         }
5626
5627       COST_TABLE (' ') = 8;
5628       COST_TABLE ('\t') = 4;
5629       COST_TABLE ('\0') = 4;
5630       COST_TABLE ('\n') = 2;
5631       COST_TABLE ('\f') = 1;
5632       COST_TABLE ('\v') = 1;
5633       COST_TABLE ('\b') = 1;
5634     }
5635
5636   /* See if all the case expressions look like text.  It is text if the
5637      constant is >= -1 and the highest constant is <= 127.  Do all comparisons
5638      as signed arithmetic since we don't want to ever access cost_table with a
5639      value less than -1.  Also check that none of the constants in a range
5640      are strange control characters.  */
5641
5642   for (n = node; n; n = n->right)
5643     {
5644       if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high))
5645         return 0;
5646
5647       for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
5648            i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
5649         if (COST_TABLE (i) < 0)
5650           return 0;
5651     }
5652
5653   /* All interesting values are within the range of interesting
5654      ASCII characters.  */
5655   return 1;
5656 }
5657
5658 /* Scan an ordered list of case nodes
5659    combining those with consecutive values or ranges.
5660
5661    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
5662
5663 static void
5664 group_case_nodes (head)
5665      case_node_ptr head;
5666 {
5667   case_node_ptr node = head;
5668
5669   while (node)
5670     {
5671       rtx lb = next_real_insn (label_rtx (node->code_label));
5672       rtx lb2;
5673       case_node_ptr np = node;
5674
5675       /* Try to group the successors of NODE with NODE.  */
5676       while (((np = np->right) != 0)
5677              /* Do they jump to the same place?  */
5678              && ((lb2 = next_real_insn (label_rtx (np->code_label))) == lb
5679                  || (lb != 0 && lb2 != 0
5680                      && simplejump_p (lb)
5681                      && simplejump_p (lb2)
5682                      && rtx_equal_p (SET_SRC (PATTERN (lb)),
5683                                      SET_SRC (PATTERN (lb2)))))
5684              /* Are their ranges consecutive?  */
5685              && tree_int_cst_equal (np->low,
5686                                     fold (build (PLUS_EXPR,
5687                                                  TREE_TYPE (node->high),
5688                                                  node->high,
5689                                                  integer_one_node)))
5690              /* An overflow is not consecutive.  */
5691              && tree_int_cst_lt (node->high,
5692                                  fold (build (PLUS_EXPR,
5693                                               TREE_TYPE (node->high),
5694                                               node->high,
5695                                               integer_one_node))))
5696         {
5697           node->high = np->high;
5698         }
5699       /* NP is the first node after NODE which can't be grouped with it.
5700          Delete the nodes in between, and move on to that node.  */
5701       node->right = np;
5702       node = np;
5703     }
5704 }
5705
5706 /* Take an ordered list of case nodes
5707    and transform them into a near optimal binary tree,
5708    on the assumption that any target code selection value is as
5709    likely as any other.
5710
5711    The transformation is performed by splitting the ordered
5712    list into two equal sections plus a pivot.  The parts are
5713    then attached to the pivot as left and right branches.  Each
5714    branch is then transformed recursively.  */
5715
5716 static void
5717 balance_case_nodes (head, parent)
5718      case_node_ptr *head;
5719      case_node_ptr parent;
5720 {
5721   case_node_ptr np;
5722
5723   np = *head;
5724   if (np)
5725     {
5726       int cost = 0;
5727       int i = 0;
5728       int ranges = 0;
5729       case_node_ptr *npp;
5730       case_node_ptr left;
5731
5732       /* Count the number of entries on branch.  Also count the ranges.  */
5733
5734       while (np)
5735         {
5736           if (!tree_int_cst_equal (np->low, np->high))
5737             {
5738               ranges++;
5739               if (use_cost_table)
5740                 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
5741             }
5742
5743           if (use_cost_table)
5744             cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
5745
5746           i++;
5747           np = np->right;
5748         }
5749
5750       if (i > 2)
5751         {
5752           /* Split this list if it is long enough for that to help.  */
5753           npp = head;
5754           left = *npp;
5755           if (use_cost_table)
5756             {
5757               /* Find the place in the list that bisects the list's total cost,
5758                  Here I gets half the total cost.  */
5759               int n_moved = 0;
5760               i = (cost + 1) / 2;
5761               while (1)
5762                 {
5763                   /* Skip nodes while their cost does not reach that amount.  */
5764                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
5765                     i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
5766                   i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
5767                   if (i <= 0)
5768                     break;
5769                   npp = &(*npp)->right;
5770                   n_moved += 1;
5771                 }
5772               if (n_moved == 0)
5773                 {
5774                   /* Leave this branch lopsided, but optimize left-hand
5775                      side and fill in `parent' fields for right-hand side.  */
5776                   np = *head;
5777                   np->parent = parent;
5778                   balance_case_nodes (&np->left, np);
5779                   for (; np->right; np = np->right)
5780                     np->right->parent = np;
5781                   return;
5782                 }
5783             }
5784           /* If there are just three nodes, split at the middle one.  */
5785           else if (i == 3)
5786             npp = &(*npp)->right;
5787           else
5788             {
5789               /* Find the place in the list that bisects the list's total cost,
5790                  where ranges count as 2.
5791                  Here I gets half the total cost.  */
5792               i = (i + ranges + 1) / 2;
5793               while (1)
5794                 {
5795                   /* Skip nodes while their cost does not reach that amount.  */
5796                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
5797                     i--;
5798                   i--;
5799                   if (i <= 0)
5800                     break;
5801                   npp = &(*npp)->right;
5802                 }
5803             }
5804           *head = np = *npp;
5805           *npp = 0;
5806           np->parent = parent;
5807           np->left = left;
5808
5809           /* Optimize each of the two split parts.  */
5810           balance_case_nodes (&np->left, np);
5811           balance_case_nodes (&np->right, np);
5812         }
5813       else
5814         {
5815           /* Else leave this branch as one level,
5816              but fill in `parent' fields.  */
5817           np = *head;
5818           np->parent = parent;
5819           for (; np->right; np = np->right)
5820             np->right->parent = np;
5821         }
5822     }
5823 }
5824 \f
5825 /* Search the parent sections of the case node tree
5826    to see if a test for the lower bound of NODE would be redundant.
5827    INDEX_TYPE is the type of the index expression.
5828
5829    The instructions to generate the case decision tree are
5830    output in the same order as nodes are processed so it is
5831    known that if a parent node checks the range of the current
5832    node minus one that the current node is bounded at its lower
5833    span.  Thus the test would be redundant.  */
5834
5835 static int
5836 node_has_low_bound (node, index_type)
5837      case_node_ptr node;
5838      tree index_type;
5839 {
5840   tree low_minus_one;
5841   case_node_ptr pnode;
5842
5843   /* If the lower bound of this node is the lowest value in the index type,
5844      we need not test it.  */
5845
5846   if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
5847     return 1;
5848
5849   /* If this node has a left branch, the value at the left must be less
5850      than that at this node, so it cannot be bounded at the bottom and
5851      we need not bother testing any further.  */
5852
5853   if (node->left)
5854     return 0;
5855
5856   low_minus_one = fold (build (MINUS_EXPR, TREE_TYPE (node->low),
5857                                node->low, integer_one_node));
5858
5859   /* If the subtraction above overflowed, we can't verify anything.
5860      Otherwise, look for a parent that tests our value - 1.  */
5861
5862   if (! tree_int_cst_lt (low_minus_one, node->low))
5863     return 0;
5864
5865   for (pnode = node->parent; pnode; pnode = pnode->parent)
5866     if (tree_int_cst_equal (low_minus_one, pnode->high))
5867       return 1;
5868
5869   return 0;
5870 }
5871
5872 /* Search the parent sections of the case node tree
5873    to see if a test for the upper bound of NODE would be redundant.
5874    INDEX_TYPE is the type of the index expression.
5875
5876    The instructions to generate the case decision tree are
5877    output in the same order as nodes are processed so it is
5878    known that if a parent node checks the range of the current
5879    node plus one that the current node is bounded at its upper
5880    span.  Thus the test would be redundant.  */
5881
5882 static int
5883 node_has_high_bound (node, index_type)
5884      case_node_ptr node;
5885      tree index_type;
5886 {
5887   tree high_plus_one;
5888   case_node_ptr pnode;
5889
5890   /* If there is no upper bound, obviously no test is needed.  */
5891
5892   if (TYPE_MAX_VALUE (index_type) == NULL)
5893     return 1;
5894
5895   /* If the upper bound of this node is the highest value in the type
5896      of the index expression, we need not test against it.  */
5897
5898   if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
5899     return 1;
5900
5901   /* If this node has a right branch, the value at the right must be greater
5902      than that at this node, so it cannot be bounded at the top and
5903      we need not bother testing any further.  */
5904
5905   if (node->right)
5906     return 0;
5907
5908   high_plus_one = fold (build (PLUS_EXPR, TREE_TYPE (node->high),
5909                                node->high, integer_one_node));
5910
5911   /* If the addition above overflowed, we can't verify anything.
5912      Otherwise, look for a parent that tests our value + 1.  */
5913
5914   if (! tree_int_cst_lt (node->high, high_plus_one))
5915     return 0;
5916
5917   for (pnode = node->parent; pnode; pnode = pnode->parent)
5918     if (tree_int_cst_equal (high_plus_one, pnode->low))
5919       return 1;
5920
5921   return 0;
5922 }
5923
5924 /* Search the parent sections of the
5925    case node tree to see if both tests for the upper and lower
5926    bounds of NODE would be redundant.  */
5927
5928 static int
5929 node_is_bounded (node, index_type)
5930      case_node_ptr node;
5931      tree index_type;
5932 {
5933   return (node_has_low_bound (node, index_type)
5934           && node_has_high_bound (node, index_type));
5935 }
5936
5937 /*  Emit an unconditional jump to LABEL unless it would be dead code.  */
5938
5939 static void
5940 emit_jump_if_reachable (label)
5941      rtx label;
5942 {
5943   if (GET_CODE (get_last_insn ()) != BARRIER)
5944     emit_jump (label);
5945 }
5946 \f
5947 /* Emit step-by-step code to select a case for the value of INDEX.
5948    The thus generated decision tree follows the form of the
5949    case-node binary tree NODE, whose nodes represent test conditions.
5950    INDEX_TYPE is the type of the index of the switch.
5951
5952    Care is taken to prune redundant tests from the decision tree
5953    by detecting any boundary conditions already checked by
5954    emitted rtx.  (See node_has_high_bound, node_has_low_bound
5955    and node_is_bounded, above.)
5956
5957    Where the test conditions can be shown to be redundant we emit
5958    an unconditional jump to the target code.  As a further
5959    optimization, the subordinates of a tree node are examined to
5960    check for bounded nodes.  In this case conditional and/or
5961    unconditional jumps as a result of the boundary check for the
5962    current node are arranged to target the subordinates associated
5963    code for out of bound conditions on the current node.
5964
5965    We can assume that when control reaches the code generated here,
5966    the index value has already been compared with the parents
5967    of this node, and determined to be on the same side of each parent
5968    as this node is.  Thus, if this node tests for the value 51,
5969    and a parent tested for 52, we don't need to consider
5970    the possibility of a value greater than 51.  If another parent
5971    tests for the value 50, then this node need not test anything.  */
5972
5973 static void
5974 emit_case_nodes (index, node, default_label, index_type)
5975      rtx index;
5976      case_node_ptr node;
5977      rtx default_label;
5978      tree index_type;
5979 {
5980   /* If INDEX has an unsigned type, we must make unsigned branches.  */
5981   int unsignedp = TREE_UNSIGNED (index_type);
5982   enum machine_mode mode = GET_MODE (index);
5983   enum machine_mode imode = TYPE_MODE (index_type);
5984
5985   /* See if our parents have already tested everything for us.
5986      If they have, emit an unconditional jump for this node.  */
5987   if (node_is_bounded (node, index_type))
5988     emit_jump (label_rtx (node->code_label));
5989
5990   else if (tree_int_cst_equal (node->low, node->high))
5991     {
5992       /* Node is single valued.  First see if the index expression matches
5993          this node and then check our children, if any.  */
5994
5995       do_jump_if_equal (index,
5996                         convert_modes (mode, imode,
5997                                        expand_expr (node->low, NULL_RTX,
5998                                                     VOIDmode, 0),
5999                                        unsignedp),
6000                         label_rtx (node->code_label), unsignedp);
6001
6002       if (node->right != 0 && node->left != 0)
6003         {
6004           /* This node has children on both sides.
6005              Dispatch to one side or the other
6006              by comparing the index value with this node's value.
6007              If one subtree is bounded, check that one first,
6008              so we can avoid real branches in the tree.  */
6009
6010           if (node_is_bounded (node->right, index_type))
6011             {
6012               emit_cmp_and_jump_insns (index,
6013                                        convert_modes
6014                                        (mode, imode,
6015                                         expand_expr (node->high, NULL_RTX,
6016                                                      VOIDmode, 0),
6017                                         unsignedp),
6018                                        GT, NULL_RTX, mode, unsignedp,
6019                                        label_rtx (node->right->code_label));
6020               emit_case_nodes (index, node->left, default_label, index_type);
6021             }
6022
6023           else if (node_is_bounded (node->left, index_type))
6024             {
6025               emit_cmp_and_jump_insns (index,
6026                                        convert_modes
6027                                        (mode, imode,
6028                                         expand_expr (node->high, NULL_RTX,
6029                                                      VOIDmode, 0),
6030                                         unsignedp),
6031                                        LT, NULL_RTX, mode, unsignedp,
6032                                        label_rtx (node->left->code_label));
6033               emit_case_nodes (index, node->right, default_label, index_type);
6034             }
6035
6036           else
6037             {
6038               /* Neither node is bounded.  First distinguish the two sides;
6039                  then emit the code for one side at a time.  */
6040
6041               tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
6042
6043               /* See if the value is on the right.  */
6044               emit_cmp_and_jump_insns (index,
6045                                        convert_modes
6046                                        (mode, imode,
6047                                         expand_expr (node->high, NULL_RTX,
6048                                                      VOIDmode, 0),
6049                                         unsignedp),
6050                                        GT, NULL_RTX, mode, unsignedp,
6051                                        label_rtx (test_label));
6052
6053               /* Value must be on the left.
6054                  Handle the left-hand subtree.  */
6055               emit_case_nodes (index, node->left, default_label, index_type);
6056               /* If left-hand subtree does nothing,
6057                  go to default.  */
6058               emit_jump_if_reachable (default_label);
6059
6060               /* Code branches here for the right-hand subtree.  */
6061               expand_label (test_label);
6062               emit_case_nodes (index, node->right, default_label, index_type);
6063             }
6064         }
6065
6066       else if (node->right != 0 && node->left == 0)
6067         {
6068           /* Here we have a right child but no left so we issue conditional
6069              branch to default and process the right child.
6070
6071              Omit the conditional branch to default if we it avoid only one
6072              right child; it costs too much space to save so little time.  */
6073
6074           if (node->right->right || node->right->left
6075               || !tree_int_cst_equal (node->right->low, node->right->high))
6076             {
6077               if (!node_has_low_bound (node, index_type))
6078                 {
6079                   emit_cmp_and_jump_insns (index,
6080                                            convert_modes
6081                                            (mode, imode,
6082                                             expand_expr (node->high, NULL_RTX,
6083                                                          VOIDmode, 0),
6084                                             unsignedp),
6085                                            LT, NULL_RTX, mode, unsignedp,
6086                                            default_label);
6087                 }
6088
6089               emit_case_nodes (index, node->right, default_label, index_type);
6090             }
6091           else
6092             /* We cannot process node->right normally
6093                since we haven't ruled out the numbers less than
6094                this node's value.  So handle node->right explicitly.  */
6095             do_jump_if_equal (index,
6096                               convert_modes
6097                               (mode, imode,
6098                                expand_expr (node->right->low, NULL_RTX,
6099                                             VOIDmode, 0),
6100                                unsignedp),
6101                               label_rtx (node->right->code_label), unsignedp);
6102         }
6103
6104       else if (node->right == 0 && node->left != 0)
6105         {
6106           /* Just one subtree, on the left.  */
6107           if (node->left->left || node->left->right
6108               || !tree_int_cst_equal (node->left->low, node->left->high))
6109             {
6110               if (!node_has_high_bound (node, index_type))
6111                 {
6112                   emit_cmp_and_jump_insns (index,
6113                                            convert_modes
6114                                            (mode, imode,
6115                                             expand_expr (node->high, NULL_RTX,
6116                                                          VOIDmode, 0),
6117                                             unsignedp),
6118                                            GT, NULL_RTX, mode, unsignedp,
6119                                            default_label);
6120                 }
6121
6122               emit_case_nodes (index, node->left, default_label, index_type);
6123             }
6124           else
6125             /* We cannot process node->left normally
6126                since we haven't ruled out the numbers less than
6127                this node's value.  So handle node->left explicitly.  */
6128             do_jump_if_equal (index,
6129                               convert_modes
6130                               (mode, imode,
6131                                expand_expr (node->left->low, NULL_RTX,
6132                                             VOIDmode, 0),
6133                                unsignedp),
6134                               label_rtx (node->left->code_label), unsignedp);
6135         }
6136     }
6137   else
6138     {
6139       /* Node is a range.  These cases are very similar to those for a single
6140          value, except that we do not start by testing whether this node
6141          is the one to branch to.  */
6142
6143       if (node->right != 0 && node->left != 0)
6144         {
6145           /* Node has subtrees on both sides.
6146              If the right-hand subtree is bounded,
6147              test for it first, since we can go straight there.
6148              Otherwise, we need to make a branch in the control structure,
6149              then handle the two subtrees.  */
6150           tree test_label = 0;
6151
6152           if (node_is_bounded (node->right, index_type))
6153             /* Right hand node is fully bounded so we can eliminate any
6154                testing and branch directly to the target code.  */
6155             emit_cmp_and_jump_insns (index,
6156                                      convert_modes
6157                                      (mode, imode,
6158                                       expand_expr (node->high, NULL_RTX,
6159                                                    VOIDmode, 0),
6160                                       unsignedp),
6161                                      GT, NULL_RTX, mode, unsignedp,
6162                                      label_rtx (node->right->code_label));
6163           else
6164             {
6165               /* Right hand node requires testing.
6166                  Branch to a label where we will handle it later.  */
6167
6168               test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
6169               emit_cmp_and_jump_insns (index,
6170                                        convert_modes
6171                                        (mode, imode,
6172                                         expand_expr (node->high, NULL_RTX,
6173                                                      VOIDmode, 0),
6174                                         unsignedp),
6175                                        GT, NULL_RTX, mode, unsignedp,
6176                                        label_rtx (test_label));
6177             }
6178
6179           /* Value belongs to this node or to the left-hand subtree.  */
6180
6181           emit_cmp_and_jump_insns (index,
6182                                    convert_modes
6183                                    (mode, imode,
6184                                     expand_expr (node->low, NULL_RTX,
6185                                                  VOIDmode, 0),
6186                                     unsignedp),
6187                                    GE, NULL_RTX, mode, unsignedp,
6188                                    label_rtx (node->code_label));
6189
6190           /* Handle the left-hand subtree.  */
6191           emit_case_nodes (index, node->left, default_label, index_type);
6192
6193           /* If right node had to be handled later, do that now.  */
6194
6195           if (test_label)
6196             {
6197               /* If the left-hand subtree fell through,
6198                  don't let it fall into the right-hand subtree.  */
6199               emit_jump_if_reachable (default_label);
6200
6201               expand_label (test_label);
6202               emit_case_nodes (index, node->right, default_label, index_type);
6203             }
6204         }
6205
6206       else if (node->right != 0 && node->left == 0)
6207         {
6208           /* Deal with values to the left of this node,
6209              if they are possible.  */
6210           if (!node_has_low_bound (node, index_type))
6211             {
6212               emit_cmp_and_jump_insns (index,
6213                                        convert_modes
6214                                        (mode, imode,
6215                                         expand_expr (node->low, NULL_RTX,
6216                                                      VOIDmode, 0),
6217                                         unsignedp),
6218                                        LT, NULL_RTX, mode, unsignedp,
6219                                        default_label);
6220             }
6221
6222           /* Value belongs to this node or to the right-hand subtree.  */
6223
6224           emit_cmp_and_jump_insns (index,
6225                                    convert_modes
6226                                    (mode, imode,
6227                                     expand_expr (node->high, NULL_RTX,
6228                                                  VOIDmode, 0),
6229                                     unsignedp),
6230                                    LE, NULL_RTX, mode, unsignedp,
6231                                    label_rtx (node->code_label));
6232
6233           emit_case_nodes (index, node->right, default_label, index_type);
6234         }
6235
6236       else if (node->right == 0 && node->left != 0)
6237         {
6238           /* Deal with values to the right of this node,
6239              if they are possible.  */
6240           if (!node_has_high_bound (node, index_type))
6241             {
6242               emit_cmp_and_jump_insns (index,
6243                                        convert_modes
6244                                        (mode, imode,
6245                                         expand_expr (node->high, NULL_RTX,
6246                                                      VOIDmode, 0),
6247                                         unsignedp),
6248                                        GT, NULL_RTX, mode, unsignedp,
6249                                        default_label);
6250             }
6251
6252           /* Value belongs to this node or to the left-hand subtree.  */
6253
6254           emit_cmp_and_jump_insns (index,
6255                                    convert_modes
6256                                    (mode, imode,
6257                                     expand_expr (node->low, NULL_RTX,
6258                                                  VOIDmode, 0),
6259                                     unsignedp),
6260                                    GE, NULL_RTX, mode, unsignedp,
6261                                    label_rtx (node->code_label));
6262
6263           emit_case_nodes (index, node->left, default_label, index_type);
6264         }
6265
6266       else
6267         {
6268           /* Node has no children so we check low and high bounds to remove
6269              redundant tests.  Only one of the bounds can exist,
6270              since otherwise this node is bounded--a case tested already.  */
6271           int high_bound = node_has_high_bound (node, index_type);
6272           int low_bound = node_has_low_bound (node, index_type);
6273
6274           if (!high_bound && low_bound)
6275             {
6276               emit_cmp_and_jump_insns (index,
6277                                        convert_modes
6278                                        (mode, imode,
6279                                         expand_expr (node->high, NULL_RTX,
6280                                                      VOIDmode, 0),
6281                                         unsignedp),
6282                                        GT, NULL_RTX, mode, unsignedp,
6283                                        default_label);
6284             }
6285
6286           else if (!low_bound && high_bound)
6287             {
6288               emit_cmp_and_jump_insns (index,
6289                                        convert_modes
6290                                        (mode, imode,
6291                                         expand_expr (node->low, NULL_RTX,
6292                                                      VOIDmode, 0),
6293                                         unsignedp),
6294                                        LT, NULL_RTX, mode, unsignedp,
6295                                        default_label);
6296             }
6297           else if (!low_bound && !high_bound)
6298             {
6299               /* Widen LOW and HIGH to the same width as INDEX.  */
6300               tree type = type_for_mode (mode, unsignedp);
6301               tree low = build1 (CONVERT_EXPR, type, node->low);
6302               tree high = build1 (CONVERT_EXPR, type, node->high);
6303               rtx low_rtx, new_index, new_bound;
6304
6305               /* Instead of doing two branches, emit one unsigned branch for
6306                  (index-low) > (high-low).  */
6307               low_rtx = expand_expr (low, NULL_RTX, mode, 0);
6308               new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
6309                                                NULL_RTX, unsignedp,
6310                                                OPTAB_WIDEN);
6311               new_bound = expand_expr (fold (build (MINUS_EXPR, type,
6312                                                     high, low)),
6313                                        NULL_RTX, mode, 0);
6314
6315               emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
6316                                        mode, 1, default_label);
6317             }
6318
6319           emit_jump (label_rtx (node->code_label));
6320         }
6321     }
6322 }