gcc/stmt.c

   1 /* Expands front end tree to back end RTL for GNU C-Compiler
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
   3    1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file handles the generation of rtl code from tree structure
  23    above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
  24    It also creates the rtl expressions for parameters and auto variables
  25    and has full responsibility for allocating stack slots.
  26
  27    The functions whose names start with `expand_' are called by the
  28    parser to generate RTL instructions for various kinds of constructs.
  29
  30    Some control and binding constructs require calling several such
  31    functions at different times.  For example, a simple if-then
  32    is expanded by calling `expand_start_cond' (with the condition-expression
  33    as argument) before parsing the then-clause and calling `expand_end_cond'
  34    after parsing the then-clause.  */
  35
  36 #include "config.h"
  37 #include "system.h"
  38
  39 #include "rtl.h"
  40 #include "tree.h"
  41 #include "tm_p.h"
  42 #include "flags.h"
  43 #include "except.h"
  44 #include "function.h"
  45 #include "insn-config.h"
  46 #include "expr.h"
  47 #include "libfuncs.h"
  48 #include "hard-reg-set.h"
  49 #include "obstack.h"
  50 #include "loop.h"
  51 #include "recog.h"
  52 #include "machmode.h"
  53 #include "toplev.h"
  54 #include "output.h"
  55 #include "ggc.h"
  56
  57 #define obstack_chunk_alloc xmalloc
  58 #define obstack_chunk_free free
  59 struct obstack stmt_obstack;
  60
  61 /* Assume that case vectors are not pc-relative.  */
  62 #ifndef CASE_VECTOR_PC_RELATIVE
  63 #define CASE_VECTOR_PC_RELATIVE 0
  64 #endif
  65 \f
  66 /* Functions and data structures for expanding case statements.  */
  67
  68 /* Case label structure, used to hold info on labels within case
  69    statements.  We handle "range" labels; for a single-value label
  70    as in C, the high and low limits are the same.
  71
  72    An AVL tree of case nodes is initially created, and later transformed
  73    to a list linked via the RIGHT fields in the nodes.  Nodes with
  74    higher case values are later in the list.
  75
  76    Switch statements can be output in one of two forms.  A branch table
  77    is used if there are more than a few labels and the labels are dense
  78    within the range between the smallest and largest case value.  If a
  79    branch table is used, no further manipulations are done with the case
  80    node chain.
  81
  82    The alternative to the use of a branch table is to generate a series
  83    of compare and jump insns.  When that is done, we use the LEFT, RIGHT,
  84    and PARENT fields to hold a binary tree.  Initially the tree is
  85    totally unbalanced, with everything on the right.  We balance the tree
  86    with nodes on the left having lower case values than the parent
  87    and nodes on the right having higher values.  We then output the tree
  88    in order.  */
  89
  90 struct case_node
  91 {
  92   struct case_node      *left;  /* Left son in binary tree */
  93   struct case_node      *right; /* Right son in binary tree; also node chain */
  94   struct case_node      *parent; /* Parent of node in binary tree */
  95   tree                  low;    /* Lowest index value for this label */
  96   tree                  high;   /* Highest index value for this label */
  97   tree                  code_label; /* Label to jump to when node matches */
  98   int                   balance;
  99 };
 100
 101 typedef struct case_node case_node;
 102 typedef struct case_node *case_node_ptr;
 103
 104 /* These are used by estimate_case_costs and balance_case_nodes.  */
 105
 106 /* This must be a signed type, and non-ANSI compilers lack signed char.  */
 107 static short cost_table_[129];
 108 static int use_cost_table;
 109 static int cost_table_initialized;
 110
 111 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
 112    is unsigned.  */
 113 #define COST_TABLE(I)  cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
 114 \f
 115 /* Stack of control and binding constructs we are currently inside.
 116
 117    These constructs begin when you call `expand_start_WHATEVER'
 118    and end when you call `expand_end_WHATEVER'.  This stack records
 119    info about how the construct began that tells the end-function
 120    what to do.  It also may provide information about the construct
 121    to alter the behavior of other constructs within the body.
 122    For example, they may affect the behavior of C `break' and `continue'.
 123
 124    Each construct gets one `struct nesting' object.
 125    All of these objects are chained through the `all' field.
 126    `nesting_stack' points to the first object (innermost construct).
 127    The position of an entry on `nesting_stack' is in its `depth' field.
 128
 129    Each type of construct has its own individual stack.
 130    For example, loops have `loop_stack'.  Each object points to the
 131    next object of the same type through the `next' field.
 132
 133    Some constructs are visible to `break' exit-statements and others
 134    are not.  Which constructs are visible depends on the language.
 135    Therefore, the data structure allows each construct to be visible
 136    or not, according to the args given when the construct is started.
 137    The construct is visible if the `exit_label' field is non-null.
 138    In that case, the value should be a CODE_LABEL rtx.  */
 139
 140 struct nesting
 141 {
 142   struct nesting *all;
 143   struct nesting *next;
 144   int depth;
 145   rtx exit_label;
 146   union
 147     {
 148       /* For conds (if-then and if-then-else statements).  */
 149       struct
 150         {
 151           /* Label for the end of the if construct.
 152              There is none if EXITFLAG was not set
 153              and no `else' has been seen yet.  */
 154           rtx endif_label;
 155           /* Label for the end of this alternative.
 156              This may be the end of the if or the next else/elseif.  */
 157           rtx next_label;
 158         } cond;
 159       /* For loops.  */
 160       struct
 161         {
 162           /* Label at the top of the loop; place to loop back to.  */
 163           rtx start_label;
 164           /* Label at the end of the whole construct.  */
 165           rtx end_label;
 166           /* Label before a jump that branches to the end of the whole
 167              construct.  This is where destructors go if any.  */
 168           rtx alt_end_label;
 169           /* Label for `continue' statement to jump to;
 170              this is in front of the stepper of the loop.  */
 171           rtx continue_label;
 172         } loop;
 173       /* For variable binding contours.  */
 174       struct
 175         {
 176           /* Sequence number of this binding contour within the function,
 177              in order of entry.  */
 178           int block_start_count;
 179           /* Nonzero => value to restore stack to on exit.  */
 180           rtx stack_level;
 181           /* The NOTE that starts this contour.
 182              Used by expand_goto to check whether the destination
 183              is within each contour or not.  */
 184           rtx first_insn;
 185           /* Innermost containing binding contour that has a stack level.  */
 186           struct nesting *innermost_stack_block;
 187           /* List of cleanups to be run on exit from this contour.
 188              This is a list of expressions to be evaluated.
 189              The TREE_PURPOSE of each link is the ..._DECL node
 190              which the cleanup pertains to.  */
 191           tree cleanups;
 192           /* List of cleanup-lists of blocks containing this block,
 193              as they were at the locus where this block appears.
 194              There is an element for each containing block,
 195              ordered innermost containing block first.
 196              The tail of this list can be 0,
 197              if all remaining elements would be empty lists.
 198              The element's TREE_VALUE is the cleanup-list of that block,
 199              which may be null.  */
 200           tree outer_cleanups;
 201           /* Chain of labels defined inside this binding contour.
 202              For contours that have stack levels or cleanups.  */
 203           struct label_chain *label_chain;
 204           /* Number of function calls seen, as of start of this block.  */
 205           int n_function_calls;
 206           /* Nonzero if this is associated with a EH region.  */
 207           int exception_region;
 208           /* The saved target_temp_slot_level from our outer block.
 209              We may reset target_temp_slot_level to be the level of
 210              this block, if that is done, target_temp_slot_level
 211              reverts to the saved target_temp_slot_level at the very
 212              end of the block.  */
 213           int block_target_temp_slot_level;
 214           /* True if we are currently emitting insns in an area of
 215              output code that is controlled by a conditional
 216              expression.  This is used by the cleanup handling code to
 217              generate conditional cleanup actions.  */
 218           int conditional_code;
 219           /* A place to move the start of the exception region for any
 220              of the conditional cleanups, must be at the end or after
 221              the start of the last unconditional cleanup, and before any
 222              conditional branch points.  */
 223           rtx last_unconditional_cleanup;
 224           /* When in a conditional context, this is the specific
 225              cleanup list associated with last_unconditional_cleanup,
 226              where we place the conditionalized cleanups.  */
 227           tree *cleanup_ptr;
 228         } block;
 229       /* For switch (C) or case (Pascal) statements,
 230          and also for dummies (see `expand_start_case_dummy').  */
 231       struct
 232         {
 233           /* The insn after which the case dispatch should finally
 234              be emitted.  Zero for a dummy.  */
 235           rtx start;
 236           /* A list of case labels; it is first built as an AVL tree.
 237              During expand_end_case, this is converted to a list, and may be
 238              rearranged into a nearly balanced binary tree.  */
 239           struct case_node *case_list;
 240           /* Label to jump to if no case matches.  */
 241           tree default_label;
 242           /* The expression to be dispatched on.  */
 243           tree index_expr;
 244           /* Type that INDEX_EXPR should be converted to.  */
 245           tree nominal_type;
 246           /* Name of this kind of statement, for warnings.  */
 247           const char *printname;
 248           /* Used to save no_line_numbers till we see the first case label.
 249              We set this to -1 when we see the first case label in this
 250              case statement.  */
 251           int line_number_status;
 252         } case_stmt;
 253     } data;
 254 };
 255
 256 /* Allocate and return a new `struct nesting'.  */
 257
 258 #define ALLOC_NESTING() \
 259  (struct nesting *) obstack_alloc (&stmt_obstack, sizeof (struct nesting))
 260
 261 /* Pop the nesting stack element by element until we pop off
 262    the element which is at the top of STACK.
 263    Update all the other stacks, popping off elements from them
 264    as we pop them from nesting_stack.  */
 265
 266 #define POPSTACK(STACK)                                 \
 267 do { struct nesting *target = STACK;                    \
 268      struct nesting *this;                              \
 269      do { this = nesting_stack;                         \
 270           if (loop_stack == this)                       \
 271             loop_stack = loop_stack->next;              \
 272           if (cond_stack == this)                       \
 273             cond_stack = cond_stack->next;              \
 274           if (block_stack == this)                      \
 275             block_stack = block_stack->next;            \
 276           if (stack_block_stack == this)                \
 277             stack_block_stack = stack_block_stack->next; \
 278           if (case_stack == this)                       \
 279             case_stack = case_stack->next;              \
 280           nesting_depth = nesting_stack->depth - 1;     \
 281           nesting_stack = this->all;                    \
 282           obstack_free (&stmt_obstack, this); }         \
 283      while (this != target); } while (0)
 284 \f
 285 /* In some cases it is impossible to generate code for a forward goto
 286    until the label definition is seen.  This happens when it may be necessary
 287    for the goto to reset the stack pointer: we don't yet know how to do that.
 288    So expand_goto puts an entry on this fixup list.
 289    Each time a binding contour that resets the stack is exited,
 290    we check each fixup.
 291    If the target label has now been defined, we can insert the proper code.  */
 292
 293 struct goto_fixup
 294 {
 295   /* Points to following fixup.  */
 296   struct goto_fixup *next;
 297   /* Points to the insn before the jump insn.
 298      If more code must be inserted, it goes after this insn.  */
 299   rtx before_jump;
 300   /* The LABEL_DECL that this jump is jumping to, or 0
 301      for break, continue or return.  */
 302   tree target;
 303   /* The BLOCK for the place where this goto was found.  */
 304   tree context;
 305   /* The CODE_LABEL rtx that this is jumping to.  */
 306   rtx target_rtl;
 307   /* Number of binding contours started in current function
 308      before the label reference.  */
 309   int block_start_count;
 310   /* The outermost stack level that should be restored for this jump.
 311      Each time a binding contour that resets the stack is exited,
 312      if the target label is *not* yet defined, this slot is updated.  */
 313   rtx stack_level;
 314   /* List of lists of cleanup expressions to be run by this goto.
 315      There is one element for each block that this goto is within.
 316      The tail of this list can be 0,
 317      if all remaining elements would be empty.
 318      The TREE_VALUE contains the cleanup list of that block as of the
 319      time this goto was seen.
 320      The TREE_ADDRESSABLE flag is 1 for a block that has been exited.  */
 321   tree cleanup_list_list;
 322 };
 323
 324 /* Within any binding contour that must restore a stack level,
 325    all labels are recorded with a chain of these structures.  */
 326
 327 struct label_chain
 328 {
 329   /* Points to following fixup.  */
 330   struct label_chain *next;
 331   tree label;
 332 };
 333
 334 struct stmt_status
 335 {
 336   /* Chain of all pending binding contours.  */
 337   struct nesting *x_block_stack;
 338
 339   /* If any new stacks are added here, add them to POPSTACKS too.  */
 340
 341   /* Chain of all pending binding contours that restore stack levels
 342      or have cleanups.  */
 343   struct nesting *x_stack_block_stack;
 344
 345   /* Chain of all pending conditional statements.  */
 346   struct nesting *x_cond_stack;
 347
 348   /* Chain of all pending loops.  */
 349   struct nesting *x_loop_stack;
 350
 351   /* Chain of all pending case or switch statements.  */
 352   struct nesting *x_case_stack;
 353
 354   /* Separate chain including all of the above,
 355      chained through the `all' field.  */
 356   struct nesting *x_nesting_stack;
 357
 358   /* Number of entries on nesting_stack now.  */
 359   int x_nesting_depth;
 360
 361   /* Number of binding contours started so far in this function.  */
 362   int x_block_start_count;
 363
 364   /* Each time we expand an expression-statement,
 365      record the expr's type and its RTL value here.  */
 366   tree x_last_expr_type;
 367   rtx x_last_expr_value;
 368
 369   /* Nonzero if within a ({...}) grouping, in which case we must
 370      always compute a value for each expr-stmt in case it is the last one.  */
 371   int x_expr_stmts_for_value;
 372
 373   /* Filename and line number of last line-number note,
 374      whether we actually emitted it or not.  */
 375   const char *x_emit_filename;
 376   int x_emit_lineno;
 377
 378   struct goto_fixup *x_goto_fixup_chain;
 379 };
 380
 381 #define block_stack (cfun->stmt->x_block_stack)
 382 #define stack_block_stack (cfun->stmt->x_stack_block_stack)
 383 #define cond_stack (cfun->stmt->x_cond_stack)
 384 #define loop_stack (cfun->stmt->x_loop_stack)
 385 #define case_stack (cfun->stmt->x_case_stack)
 386 #define nesting_stack (cfun->stmt->x_nesting_stack)
 387 #define nesting_depth (cfun->stmt->x_nesting_depth)
 388 #define current_block_start_count (cfun->stmt->x_block_start_count)
 389 #define last_expr_type (cfun->stmt->x_last_expr_type)
 390 #define last_expr_value (cfun->stmt->x_last_expr_value)
 391 #define expr_stmts_for_value (cfun->stmt->x_expr_stmts_for_value)
 392 #define emit_filename (cfun->stmt->x_emit_filename)
 393 #define emit_lineno (cfun->stmt->x_emit_lineno)
 394 #define goto_fixup_chain (cfun->stmt->x_goto_fixup_chain)
 395
 396 /* Non-zero if we are using EH to handle cleanus.  */
 397 static int using_eh_for_cleanups_p = 0;
 398
 399 static int n_occurrences                PARAMS ((int, const char *));
 400 static bool parse_input_constraint      PARAMS ((const char **, int, int, int,
 401                                                  int, const char * const *,
 402                                                  bool *, bool *));
 403 static void expand_goto_internal        PARAMS ((tree, rtx, rtx));
 404 static int expand_fixup                 PARAMS ((tree, rtx, rtx));
 405 static rtx expand_nl_handler_label      PARAMS ((rtx, rtx));
 406 static void expand_nl_goto_receiver     PARAMS ((void));
 407 static void expand_nl_goto_receivers    PARAMS ((struct nesting *));
 408 static void fixup_gotos                 PARAMS ((struct nesting *, rtx, tree,
 409                                                rtx, int));
 410 static bool check_operand_nalternatives PARAMS ((tree, tree));
 411 static bool check_unique_operand_names  PARAMS ((tree, tree));
 412 static tree resolve_operand_names       PARAMS ((tree, tree, tree,
 413                                                  const char **));
 414 static char *resolve_operand_name_1     PARAMS ((char *, tree, tree));
 415 static void expand_null_return_1        PARAMS ((rtx));
 416 static void expand_value_return         PARAMS ((rtx));
 417 static int tail_recursion_args          PARAMS ((tree, tree));
 418 static void expand_cleanups             PARAMS ((tree, tree, int, int));
 419 static void check_seenlabel             PARAMS ((void));
 420 static void do_jump_if_equal            PARAMS ((rtx, rtx, rtx, int));
 421 static int estimate_case_costs          PARAMS ((case_node_ptr));
 422 static void group_case_nodes            PARAMS ((case_node_ptr));
 423 static void balance_case_nodes          PARAMS ((case_node_ptr *,
 424                                                case_node_ptr));
 425 static int node_has_low_bound           PARAMS ((case_node_ptr, tree));
 426 static int node_has_high_bound          PARAMS ((case_node_ptr, tree));
 427 static int node_is_bounded              PARAMS ((case_node_ptr, tree));
 428 static void emit_jump_if_reachable      PARAMS ((rtx));
 429 static void emit_case_nodes             PARAMS ((rtx, case_node_ptr, rtx, tree));
 430 static struct case_node *case_tree2list PARAMS ((case_node *, case_node *));
 431 static void mark_cond_nesting           PARAMS ((struct nesting *));
 432 static void mark_loop_nesting           PARAMS ((struct nesting *));
 433 static void mark_block_nesting          PARAMS ((struct nesting *));
 434 static void mark_case_nesting           PARAMS ((struct nesting *));
 435 static void mark_case_node              PARAMS ((struct case_node *));
 436 static void mark_goto_fixup             PARAMS ((struct goto_fixup *));
 437 static void free_case_nodes             PARAMS ((case_node_ptr));
 438 \f
 439 void
 440 using_eh_for_cleanups ()
 441 {
 442   using_eh_for_cleanups_p = 1;
 443 }
 444
 445 /* Mark N (known to be a cond-nesting) for GC.  */
 446
 447 static void
 448 mark_cond_nesting (n)
 449      struct nesting *n;
 450 {
 451   while (n)
 452     {
 453       ggc_mark_rtx (n->exit_label);
 454       ggc_mark_rtx (n->data.cond.endif_label);
 455       ggc_mark_rtx (n->data.cond.next_label);
 456
 457       n = n->next;
 458     }
 459 }
 460
 461 /* Mark N (known to be a loop-nesting) for GC.  */
 462
 463 static void
 464 mark_loop_nesting (n)
 465      struct nesting *n;
 466 {
 467
 468   while (n)
 469     {
 470       ggc_mark_rtx (n->exit_label);
 471       ggc_mark_rtx (n->data.loop.start_label);
 472       ggc_mark_rtx (n->data.loop.end_label);
 473       ggc_mark_rtx (n->data.loop.alt_end_label);
 474       ggc_mark_rtx (n->data.loop.continue_label);
 475
 476       n = n->next;
 477     }
 478 }
 479
 480 /* Mark N (known to be a block-nesting) for GC.  */
 481
 482 static void
 483 mark_block_nesting (n)
 484      struct nesting *n;
 485 {
 486   while (n)
 487     {
 488       struct label_chain *l;
 489
 490       ggc_mark_rtx (n->exit_label);
 491       ggc_mark_rtx (n->data.block.stack_level);
 492       ggc_mark_rtx (n->data.block.first_insn);
 493       ggc_mark_tree (n->data.block.cleanups);
 494       ggc_mark_tree (n->data.block.outer_cleanups);
 495
 496       for (l = n->data.block.label_chain; l != NULL; l = l->next)
 497         {
 498           ggc_mark (l);
 499           ggc_mark_tree (l->label);
 500         }
 501
 502       ggc_mark_rtx (n->data.block.last_unconditional_cleanup);
 503
 504       /* ??? cleanup_ptr never points outside the stack, does it?  */
 505
 506       n = n->next;
 507     }
 508 }
 509
 510 /* Mark N (known to be a case-nesting) for GC.  */
 511
 512 static void
 513 mark_case_nesting (n)
 514      struct nesting *n;
 515 {
 516   while (n)
 517     {
 518       ggc_mark_rtx (n->exit_label);
 519       ggc_mark_rtx (n->data.case_stmt.start);
 520
 521       ggc_mark_tree (n->data.case_stmt.default_label);
 522       ggc_mark_tree (n->data.case_stmt.index_expr);
 523       ggc_mark_tree (n->data.case_stmt.nominal_type);
 524
 525       mark_case_node (n->data.case_stmt.case_list);
 526       n = n->next;
 527     }
 528 }
 529
 530 /* Mark C for GC.  */
 531
 532 static void
 533 mark_case_node (c)
 534      struct case_node *c;
 535 {
 536   if (c != 0)
 537     {
 538       ggc_mark_tree (c->low);
 539       ggc_mark_tree (c->high);
 540       ggc_mark_tree (c->code_label);
 541
 542       mark_case_node (c->right);
 543       mark_case_node (c->left);
 544     }
 545 }
 546
 547 /* Mark G for GC.  */
 548
 549 static void
 550 mark_goto_fixup (g)
 551      struct goto_fixup *g;
 552 {
 553   while (g)
 554     {
 555       ggc_mark (g);
 556       ggc_mark_rtx (g->before_jump);
 557       ggc_mark_tree (g->target);
 558       ggc_mark_tree (g->context);
 559       ggc_mark_rtx (g->target_rtl);
 560       ggc_mark_rtx (g->stack_level);
 561       ggc_mark_tree (g->cleanup_list_list);
 562
 563       g = g->next;
 564     }
 565 }
 566
 567 /* Clear out all parts of the state in F that can safely be discarded
 568    after the function has been compiled, to let garbage collection
 569    reclaim the memory.  */
 570
 571 void
 572 free_stmt_status (f)
 573      struct function *f;
 574 {
 575   /* We're about to free the function obstack.  If we hold pointers to
 576      things allocated there, then we'll try to mark them when we do
 577      GC.  So, we clear them out here explicitly.  */
 578   if (f->stmt)
 579     free (f->stmt);
 580   f->stmt = NULL;
 581 }
 582
 583 /* Mark P for GC.  */
 584
 585 void
 586 mark_stmt_status (p)
 587      struct stmt_status *p;
 588 {
 589   if (p == 0)
 590     return;
 591
 592   mark_block_nesting (p->x_block_stack);
 593   mark_cond_nesting (p->x_cond_stack);
 594   mark_loop_nesting (p->x_loop_stack);
 595   mark_case_nesting (p->x_case_stack);
 596
 597   ggc_mark_tree (p->x_last_expr_type);
 598   /* last_epxr_value is only valid if last_expr_type is nonzero.  */
 599   if (p->x_last_expr_type)
 600     ggc_mark_rtx (p->x_last_expr_value);
 601
 602   mark_goto_fixup (p->x_goto_fixup_chain);
 603 }
 604
 605 void
 606 init_stmt ()
 607 {
 608   gcc_obstack_init (&stmt_obstack);
 609 }
 610
 611 void
 612 init_stmt_for_function ()
 613 {
 614   cfun->stmt = (struct stmt_status *) xmalloc (sizeof (struct stmt_status));
 615
 616   /* We are not currently within any block, conditional, loop or case.  */
 617   block_stack = 0;
 618   stack_block_stack = 0;
 619   loop_stack = 0;
 620   case_stack = 0;
 621   cond_stack = 0;
 622   nesting_stack = 0;
 623   nesting_depth = 0;
 624
 625   current_block_start_count = 0;
 626
 627   /* No gotos have been expanded yet.  */
 628   goto_fixup_chain = 0;
 629
 630   /* We are not processing a ({...}) grouping.  */
 631   expr_stmts_for_value = 0;
 632   last_expr_type = 0;
 633   last_expr_value = NULL_RTX;
 634 }
 635 \f
 636 /* Return nonzero if anything is pushed on the loop, condition, or case
 637    stack.  */
 638 int
 639 in_control_zone_p ()
 640 {
 641   return cond_stack || loop_stack || case_stack;
 642 }
 643
 644 /* Record the current file and line.  Called from emit_line_note.  */
 645 void
 646 set_file_and_line_for_stmt (file, line)
 647      const char *file;
 648      int line;
 649 {
 650   /* If we're outputting an inline function, and we add a line note,
 651      there may be no CFUN->STMT information.  So, there's no need to
 652      update it.  */
 653   if (cfun->stmt)
 654     {
 655       emit_filename = file;
 656       emit_lineno = line;
 657     }
 658 }
 659
 660 /* Emit a no-op instruction.  */
 661
 662 void
 663 emit_nop ()
 664 {
 665   rtx last_insn;
 666
 667   last_insn = get_last_insn ();
 668   if (!optimize
 669       && (GET_CODE (last_insn) == CODE_LABEL
 670           || (GET_CODE (last_insn) == NOTE
 671               && prev_real_insn (last_insn) == 0)))
 672     emit_insn (gen_nop ());
 673 }
 674 \f
 675 /* Return the rtx-label that corresponds to a LABEL_DECL,
 676    creating it if necessary.  */
 677
 678 rtx
 679 label_rtx (label)
 680      tree label;
 681 {
 682   if (TREE_CODE (label) != LABEL_DECL)
 683     abort ();
 684
 685   if (!DECL_RTL_SET_P (label))
 686     SET_DECL_RTL (label, gen_label_rtx ());
 687
 688   return DECL_RTL (label);
 689 }
 690
 691
 692 /* Add an unconditional jump to LABEL as the next sequential instruction.  */
 693
 694 void
 695 emit_jump (label)
 696      rtx label;
 697 {
 698   do_pending_stack_adjust ();
 699   emit_jump_insn (gen_jump (label));
 700   emit_barrier ();
 701 }
 702
 703 /* Emit code to jump to the address
 704    specified by the pointer expression EXP.  */
 705
 706 void
 707 expand_computed_goto (exp)
 708      tree exp;
 709 {
 710   rtx x = expand_expr (exp, NULL_RTX, VOIDmode, 0);
 711
 712 #ifdef POINTERS_EXTEND_UNSIGNED
 713   if (GET_MODE (x) != Pmode)
 714     x = convert_memory_address (Pmode, x);
 715 #endif
 716
 717   emit_queue ();
 718   do_pending_stack_adjust ();
 719   emit_indirect_jump (x);
 720
 721   current_function_has_computed_jump = 1;
 722 }
 723 \f
 724 /* Handle goto statements and the labels that they can go to.  */
 725
 726 /* Specify the location in the RTL code of a label LABEL,
 727    which is a LABEL_DECL tree node.
 728
 729    This is used for the kind of label that the user can jump to with a
 730    goto statement, and for alternatives of a switch or case statement.
 731    RTL labels generated for loops and conditionals don't go through here;
 732    they are generated directly at the RTL level, by other functions below.
 733
 734    Note that this has nothing to do with defining label *names*.
 735    Languages vary in how they do that and what that even means.  */
 736
 737 void
 738 expand_label (label)
 739      tree label;
 740 {
 741   struct label_chain *p;
 742
 743   do_pending_stack_adjust ();
 744   emit_label (label_rtx (label));
 745   if (DECL_NAME (label))
 746     LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
 747
 748   if (stack_block_stack != 0)
 749     {
 750       p = (struct label_chain *) ggc_alloc (sizeof (struct label_chain));
 751       p->next = stack_block_stack->data.block.label_chain;
 752       stack_block_stack->data.block.label_chain = p;
 753       p->label = label;
 754     }
 755 }
 756
 757 /* Declare that LABEL (a LABEL_DECL) may be used for nonlocal gotos
 758    from nested functions.  */
 759
 760 void
 761 declare_nonlocal_label (label)
 762      tree label;
 763 {
 764   rtx slot = assign_stack_local (Pmode, GET_MODE_SIZE (Pmode), 0);
 765
 766   nonlocal_labels = tree_cons (NULL_TREE, label, nonlocal_labels);
 767   LABEL_PRESERVE_P (label_rtx (label)) = 1;
 768   if (nonlocal_goto_handler_slots == 0)
 769     {
 770       emit_stack_save (SAVE_NONLOCAL,
 771                        &nonlocal_goto_stack_level,
 772                        PREV_INSN (tail_recursion_reentry));
 773     }
 774   nonlocal_goto_handler_slots
 775     = gen_rtx_EXPR_LIST (VOIDmode, slot, nonlocal_goto_handler_slots);
 776 }
 777
 778 /* Generate RTL code for a `goto' statement with target label LABEL.
 779    LABEL should be a LABEL_DECL tree node that was or will later be
 780    defined with `expand_label'.  */
 781
 782 void
 783 expand_goto (label)
 784      tree label;
 785 {
 786   tree context;
 787
 788   /* Check for a nonlocal goto to a containing function.  */
 789   context = decl_function_context (label);
 790   if (context != 0 && context != current_function_decl)
 791     {
 792       struct function *p = find_function_data (context);
 793       rtx label_ref = gen_rtx_LABEL_REF (Pmode, label_rtx (label));
 794       rtx handler_slot, static_chain, save_area, insn;
 795       tree link;
 796
 797       /* Find the corresponding handler slot for this label.  */
 798       handler_slot = p->x_nonlocal_goto_handler_slots;
 799       for (link = p->x_nonlocal_labels; TREE_VALUE (link) != label;
 800            link = TREE_CHAIN (link))
 801         handler_slot = XEXP (handler_slot, 1);
 802       handler_slot = XEXP (handler_slot, 0);
 803
 804       p->has_nonlocal_label = 1;
 805       current_function_has_nonlocal_goto = 1;
 806       LABEL_REF_NONLOCAL_P (label_ref) = 1;
 807
 808       /* Copy the rtl for the slots so that they won't be shared in
 809          case the virtual stack vars register gets instantiated differently
 810          in the parent than in the child.  */
 811
 812       static_chain = copy_to_reg (lookup_static_chain (label));
 813
 814       /* Get addr of containing function's current nonlocal goto handler,
 815          which will do any cleanups and then jump to the label.  */
 816       handler_slot = copy_to_reg (replace_rtx (copy_rtx (handler_slot),
 817                                                virtual_stack_vars_rtx,
 818                                                static_chain));
 819
 820       /* Get addr of containing function's nonlocal save area.  */
 821       save_area = p->x_nonlocal_goto_stack_level;
 822       if (save_area)
 823         save_area = replace_rtx (copy_rtx (save_area),
 824                                  virtual_stack_vars_rtx, static_chain);
 825
 826 #if HAVE_nonlocal_goto
 827       if (HAVE_nonlocal_goto)
 828         emit_insn (gen_nonlocal_goto (static_chain, handler_slot,
 829                                       save_area, label_ref));
 830       else
 831 #endif
 832         {
 833           /* Restore frame pointer for containing function.
 834              This sets the actual hard register used for the frame pointer
 835              to the location of the function's incoming static chain info.
 836              The non-local goto handler will then adjust it to contain the
 837              proper value and reload the argument pointer, if needed.  */
 838           emit_move_insn (hard_frame_pointer_rtx, static_chain);
 839           emit_stack_restore (SAVE_NONLOCAL, save_area, NULL_RTX);
 840
 841           /* USE of hard_frame_pointer_rtx added for consistency;
 842              not clear if really needed.  */
 843           emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
 844           emit_insn (gen_rtx_USE (VOIDmode, stack_pointer_rtx));
 845           emit_indirect_jump (handler_slot);
 846         }
 847
 848       /* Search backwards to the jump insn and mark it as a
 849          non-local goto.  */
 850       for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 851         {
 852           if (GET_CODE (insn) == JUMP_INSN)
 853             {
 854               REG_NOTES (insn) = alloc_EXPR_LIST (REG_NON_LOCAL_GOTO,
 855                                                   const0_rtx, REG_NOTES (insn));
 856               break;
 857             }
 858           else if (GET_CODE (insn) == CALL_INSN)
 859               break;
 860         }
 861     }
 862   else
 863     expand_goto_internal (label, label_rtx (label), NULL_RTX);
 864 }
 865
 866 /* Generate RTL code for a `goto' statement with target label BODY.
 867    LABEL should be a LABEL_REF.
 868    LAST_INSN, if non-0, is the rtx we should consider as the last
 869    insn emitted (for the purposes of cleaning up a return).  */
 870
 871 static void
 872 expand_goto_internal (body, label, last_insn)
 873      tree body;
 874      rtx label;
 875      rtx last_insn;
 876 {
 877   struct nesting *block;
 878   rtx stack_level = 0;
 879
 880   if (GET_CODE (label) != CODE_LABEL)
 881     abort ();
 882
 883   /* If label has already been defined, we can tell now
 884      whether and how we must alter the stack level.  */
 885
 886   if (PREV_INSN (label) != 0)
 887     {
 888       /* Find the innermost pending block that contains the label.
 889          (Check containment by comparing insn-uids.)
 890          Then restore the outermost stack level within that block,
 891          and do cleanups of all blocks contained in it.  */
 892       for (block = block_stack; block; block = block->next)
 893         {
 894           if (INSN_UID (block->data.block.first_insn) < INSN_UID (label))
 895             break;
 896           if (block->data.block.stack_level != 0)
 897             stack_level = block->data.block.stack_level;
 898           /* Execute the cleanups for blocks we are exiting.  */
 899           if (block->data.block.cleanups != 0)
 900             {
 901               expand_cleanups (block->data.block.cleanups, NULL_TREE, 1, 1);
 902               do_pending_stack_adjust ();
 903             }
 904         }
 905
 906       if (stack_level)
 907         {
 908           /* Ensure stack adjust isn't done by emit_jump, as this
 909              would clobber the stack pointer.  This one should be
 910              deleted as dead by flow.  */
 911           clear_pending_stack_adjust ();
 912           do_pending_stack_adjust ();
 913
 914           /* Don't do this adjust if it's to the end label and this function
 915              is to return with a depressed stack pointer.  */
 916           if (label == return_label
 917               && (((TREE_CODE (TREE_TYPE (current_function_decl))
 918                    == FUNCTION_TYPE)
 919                    && (TYPE_RETURNS_STACK_DEPRESSED
 920                        (TREE_TYPE (current_function_decl))))))
 921             ;
 922           else
 923             emit_stack_restore (SAVE_BLOCK, stack_level, NULL_RTX);
 924         }
 925
 926       if (body != 0 && DECL_TOO_LATE (body))
 927         error ("jump to `%s' invalidly jumps into binding contour",
 928                IDENTIFIER_POINTER (DECL_NAME (body)));
 929     }
 930   /* Label not yet defined: may need to put this goto
 931      on the fixup list.  */
 932   else if (! expand_fixup (body, label, last_insn))
 933     {
 934       /* No fixup needed.  Record that the label is the target
 935          of at least one goto that has no fixup.  */
 936       if (body != 0)
 937         TREE_ADDRESSABLE (body) = 1;
 938     }
 939
 940   emit_jump (label);
 941 }
 942 \f
 943 /* Generate if necessary a fixup for a goto
 944    whose target label in tree structure (if any) is TREE_LABEL
 945    and whose target in rtl is RTL_LABEL.
 946
 947    If LAST_INSN is nonzero, we pretend that the jump appears
 948    after insn LAST_INSN instead of at the current point in the insn stream.
 949
 950    The fixup will be used later to insert insns just before the goto.
 951    Those insns will restore the stack level as appropriate for the
 952    target label, and will (in the case of C++) also invoke any object
 953    destructors which have to be invoked when we exit the scopes which
 954    are exited by the goto.
 955
 956    Value is nonzero if a fixup is made.  */
 957
 958 static int
 959 expand_fixup (tree_label, rtl_label, last_insn)
 960      tree tree_label;
 961      rtx rtl_label;
 962      rtx last_insn;
 963 {
 964   struct nesting *block, *end_block;
 965
 966   /* See if we can recognize which block the label will be output in.
 967      This is possible in some very common cases.
 968      If we succeed, set END_BLOCK to that block.
 969      Otherwise, set it to 0.  */
 970
 971   if (cond_stack
 972       && (rtl_label == cond_stack->data.cond.endif_label
 973           || rtl_label == cond_stack->data.cond.next_label))
 974     end_block = cond_stack;
 975   /* If we are in a loop, recognize certain labels which
 976      are likely targets.  This reduces the number of fixups
 977      we need to create.  */
 978   else if (loop_stack
 979       && (rtl_label == loop_stack->data.loop.start_label
 980           || rtl_label == loop_stack->data.loop.end_label
 981           || rtl_label == loop_stack->data.loop.continue_label))
 982     end_block = loop_stack;
 983   else
 984     end_block = 0;
 985
 986   /* Now set END_BLOCK to the binding level to which we will return.  */
 987
 988   if (end_block)
 989     {
 990       struct nesting *next_block = end_block->all;
 991       block = block_stack;
 992
 993       /* First see if the END_BLOCK is inside the innermost binding level.
 994          If so, then no cleanups or stack levels are relevant.  */
 995       while (next_block && next_block != block)
 996         next_block = next_block->all;
 997
 998       if (next_block)
 999         return 0;
1000
1001       /* Otherwise, set END_BLOCK to the innermost binding level
1002          which is outside the relevant control-structure nesting.  */
1003       next_block = block_stack->next;
1004       for (block = block_stack; block != end_block; block = block->all)
1005         if (block == next_block)
1006           next_block = next_block->next;
1007       end_block = next_block;
1008     }
1009
1010   /* Does any containing block have a stack level or cleanups?
1011      If not, no fixup is needed, and that is the normal case
1012      (the only case, for standard C).  */
1013   for (block = block_stack; block != end_block; block = block->next)
1014     if (block->data.block.stack_level != 0
1015         || block->data.block.cleanups != 0)
1016       break;
1017
1018   if (block != end_block)
1019     {
1020       /* Ok, a fixup is needed.  Add a fixup to the list of such.  */
1021       struct goto_fixup *fixup
1022         = (struct goto_fixup *) ggc_alloc (sizeof (struct goto_fixup));
1023       /* In case an old stack level is restored, make sure that comes
1024          after any pending stack adjust.  */
1025       /* ?? If the fixup isn't to come at the present position,
1026          doing the stack adjust here isn't useful.  Doing it with our
1027          settings at that location isn't useful either.  Let's hope
1028          someone does it!  */
1029       if (last_insn == 0)
1030         do_pending_stack_adjust ();
1031       fixup->target = tree_label;
1032       fixup->target_rtl = rtl_label;
1033
1034       /* Create a BLOCK node and a corresponding matched set of
1035          NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes at
1036          this point.  The notes will encapsulate any and all fixup
1037          code which we might later insert at this point in the insn
1038          stream.  Also, the BLOCK node will be the parent (i.e. the
1039          `SUPERBLOCK') of any other BLOCK nodes which we might create
1040          later on when we are expanding the fixup code.
1041
1042          Note that optimization passes (including expand_end_loop)
1043          might move the *_BLOCK notes away, so we use a NOTE_INSN_DELETED
1044          as a placeholder.  */
1045
1046       {
1047         rtx original_before_jump
1048           = last_insn ? last_insn : get_last_insn ();
1049         rtx start;
1050         rtx end;
1051         tree block;
1052
1053         block = make_node (BLOCK);
1054         TREE_USED (block) = 1;
1055
1056         if (!cfun->x_whole_function_mode_p)
1057           insert_block (block);
1058         else
1059           {
1060             BLOCK_CHAIN (block)
1061               = BLOCK_CHAIN (DECL_INITIAL (current_function_decl));
1062             BLOCK_CHAIN (DECL_INITIAL (current_function_decl))
1063               = block;
1064           }
1065
1066         start_sequence ();
1067         start = emit_note (NULL, NOTE_INSN_BLOCK_BEG);
1068         if (cfun->x_whole_function_mode_p)
1069           NOTE_BLOCK (start) = block;
1070         fixup->before_jump = emit_note (NULL, NOTE_INSN_DELETED);
1071         end = emit_note (NULL, NOTE_INSN_BLOCK_END);
1072         if (cfun->x_whole_function_mode_p)
1073           NOTE_BLOCK (end) = block;
1074         fixup->context = block;
1075         end_sequence ();
1076         emit_insns_after (start, original_before_jump);
1077       }
1078
1079       fixup->block_start_count = current_block_start_count;
1080       fixup->stack_level = 0;
1081       fixup->cleanup_list_list
1082         = ((block->data.block.outer_cleanups
1083             || block->data.block.cleanups)
1084            ? tree_cons (NULL_TREE, block->data.block.cleanups,
1085                         block->data.block.outer_cleanups)
1086            : 0);
1087       fixup->next = goto_fixup_chain;
1088       goto_fixup_chain = fixup;
1089     }
1090
1091   return block != 0;
1092 }
1093 \f
1094 /* Expand any needed fixups in the outputmost binding level of the
1095    function.  FIRST_INSN is the first insn in the function.  */
1096
1097 void
1098 expand_fixups (first_insn)
1099      rtx first_insn;
1100 {
1101   fixup_gotos (NULL, NULL_RTX, NULL_TREE, first_insn, 0);
1102 }
1103
1104 /* When exiting a binding contour, process all pending gotos requiring fixups.
1105    THISBLOCK is the structure that describes the block being exited.
1106    STACK_LEVEL is the rtx for the stack level to restore exiting this contour.
1107    CLEANUP_LIST is a list of expressions to evaluate on exiting this contour.
1108    FIRST_INSN is the insn that began this contour.
1109
1110    Gotos that jump out of this contour must restore the
1111    stack level and do the cleanups before actually jumping.
1112
1113    DONT_JUMP_IN nonzero means report error there is a jump into this
1114    contour from before the beginning of the contour.
1115    This is also done if STACK_LEVEL is nonzero.  */
1116
1117 static void
1118 fixup_gotos (thisblock, stack_level, cleanup_list, first_insn, dont_jump_in)
1119      struct nesting *thisblock;
1120      rtx stack_level;
1121      tree cleanup_list;
1122      rtx first_insn;
1123      int dont_jump_in;
1124 {
1125   struct goto_fixup *f, *prev;
1126
1127   /* F is the fixup we are considering; PREV is the previous one.  */
1128   /* We run this loop in two passes so that cleanups of exited blocks
1129      are run first, and blocks that are exited are marked so
1130      afterwards.  */
1131
1132   for (prev = 0, f = goto_fixup_chain; f; prev = f, f = f->next)
1133     {
1134       /* Test for a fixup that is inactive because it is already handled.  */
1135       if (f->before_jump == 0)
1136         {
1137           /* Delete inactive fixup from the chain, if that is easy to do.  */
1138           if (prev != 0)
1139             prev->next = f->next;
1140         }
1141       /* Has this fixup's target label been defined?
1142          If so, we can finalize it.  */
1143       else if (PREV_INSN (f->target_rtl) != 0)
1144         {
1145           rtx cleanup_insns;
1146
1147           /* If this fixup jumped into this contour from before the beginning
1148              of this contour, report an error.   This code used to use
1149              the first non-label insn after f->target_rtl, but that's
1150              wrong since such can be added, by things like put_var_into_stack
1151              and have INSN_UIDs that are out of the range of the block.  */
1152           /* ??? Bug: this does not detect jumping in through intermediate
1153              blocks that have stack levels or cleanups.
1154              It detects only a problem with the innermost block
1155              around the label.  */
1156           if (f->target != 0
1157               && (dont_jump_in || stack_level || cleanup_list)
1158               && INSN_UID (first_insn) < INSN_UID (f->target_rtl)
1159               && INSN_UID (first_insn) > INSN_UID (f->before_jump)
1160               && ! DECL_ERROR_ISSUED (f->target))
1161             {
1162               error_with_decl (f->target,
1163                                "label `%s' used before containing binding contour");
1164               /* Prevent multiple errors for one label.  */
1165               DECL_ERROR_ISSUED (f->target) = 1;
1166             }
1167
1168           /* We will expand the cleanups into a sequence of their own and
1169              then later on we will attach this new sequence to the insn
1170              stream just ahead of the actual jump insn.  */
1171
1172           start_sequence ();
1173
1174           /* Temporarily restore the lexical context where we will
1175              logically be inserting the fixup code.  We do this for the
1176              sake of getting the debugging information right.  */
1177
1178           pushlevel (0);
1179           set_block (f->context);
1180
1181           /* Expand the cleanups for blocks this jump exits.  */
1182           if (f->cleanup_list_list)
1183             {
1184               tree lists;
1185               for (lists = f->cleanup_list_list; lists; lists = TREE_CHAIN (lists))
1186                 /* Marked elements correspond to blocks that have been closed.
1187                    Do their cleanups.  */
1188                 if (TREE_ADDRESSABLE (lists)
1189                     && TREE_VALUE (lists) != 0)
1190                   {
1191                     expand_cleanups (TREE_VALUE (lists), NULL_TREE, 1, 1);
1192                     /* Pop any pushes done in the cleanups,
1193                        in case function is about to return.  */
1194                     do_pending_stack_adjust ();
1195                   }
1196             }
1197
1198           /* Restore stack level for the biggest contour that this
1199              jump jumps out of.  */
1200           if (f->stack_level
1201               && ! (f->target_rtl == return_label
1202                     && ((TREE_CODE (TREE_TYPE (current_function_decl))
1203                          == FUNCTION_TYPE)
1204                         && (TYPE_RETURNS_STACK_DEPRESSED
1205                             (TREE_TYPE (current_function_decl))))))
1206             emit_stack_restore (SAVE_BLOCK, f->stack_level, f->before_jump);
1207
1208           /* Finish up the sequence containing the insns which implement the
1209              necessary cleanups, and then attach that whole sequence to the
1210              insn stream just ahead of the actual jump insn.  Attaching it
1211              at that point insures that any cleanups which are in fact
1212              implicit C++ object destructions (which must be executed upon
1213              leaving the block) appear (to the debugger) to be taking place
1214              in an area of the generated code where the object(s) being
1215              destructed are still "in scope".  */
1216
1217           cleanup_insns = get_insns ();
1218           poplevel (1, 0, 0);
1219
1220           end_sequence ();
1221           emit_insns_after (cleanup_insns, f->before_jump);
1222
1223           f->before_jump = 0;
1224         }
1225     }
1226
1227   /* For any still-undefined labels, do the cleanups for this block now.
1228      We must do this now since items in the cleanup list may go out
1229      of scope when the block ends.  */
1230   for (prev = 0, f = goto_fixup_chain; f; prev = f, f = f->next)
1231     if (f->before_jump != 0
1232         && PREV_INSN (f->target_rtl) == 0
1233         /* Label has still not appeared.  If we are exiting a block with
1234            a stack level to restore, that started before the fixup,
1235            mark this stack level as needing restoration
1236            when the fixup is later finalized.  */
1237         && thisblock != 0
1238         /* Note: if THISBLOCK == 0 and we have a label that hasn't appeared, it
1239            means the label is undefined.  That's erroneous, but possible.  */
1240         && (thisblock->data.block.block_start_count
1241             <= f->block_start_count))
1242       {
1243         tree lists = f->cleanup_list_list;
1244         rtx cleanup_insns;
1245
1246         for (; lists; lists = TREE_CHAIN (lists))
1247           /* If the following elt. corresponds to our containing block
1248              then the elt. must be for this block.  */
1249           if (TREE_CHAIN (lists) == thisblock->data.block.outer_cleanups)
1250             {
1251               start_sequence ();
1252               pushlevel (0);
1253               set_block (f->context);
1254               expand_cleanups (TREE_VALUE (lists), NULL_TREE, 1, 1);
1255               do_pending_stack_adjust ();
1256               cleanup_insns = get_insns ();
1257               poplevel (1, 0, 0);
1258               end_sequence ();
1259               if (cleanup_insns != 0)
1260                 f->before_jump
1261                   = emit_insns_after (cleanup_insns, f->before_jump);
1262
1263               f->cleanup_list_list = TREE_CHAIN (lists);
1264             }
1265
1266         if (stack_level)
1267           f->stack_level = stack_level;
1268       }
1269 }
1270 \f
1271 /* Return the number of times character C occurs in string S.  */
1272 static int
1273 n_occurrences (c, s)
1274      int c;
1275      const char *s;
1276 {
1277   int n = 0;
1278   while (*s)
1279     n += (*s++ == c);
1280   return n;
1281 }
1282 \f
1283 /* Generate RTL for an asm statement (explicit assembler code).
1284    BODY is a STRING_CST node containing the assembler code text,
1285    or an ADDR_EXPR containing a STRING_CST.  */
1286
1287 void
1288 expand_asm (body)
1289      tree body;
1290 {
1291   if (TREE_CODE (body) == ADDR_EXPR)
1292     body = TREE_OPERAND (body, 0);
1293
1294   emit_insn (gen_rtx_ASM_INPUT (VOIDmode,
1295                                 TREE_STRING_POINTER (body)));
1296   last_expr_type = 0;
1297 }
1298
1299 /* Parse the output constraint pointed to by *CONSTRAINT_P.  It is the
1300    OPERAND_NUMth output operand, indexed from zero.  There are NINPUTS
1301    inputs and NOUTPUTS outputs to this extended-asm.  Upon return,
1302    *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
1303    memory operand.  Similarly, *ALLOWS_REG will be TRUE iff the
1304    constraint allows the use of a register operand.  And, *IS_INOUT
1305    will be true if the operand is read-write, i.e., if it is used as
1306    an input as well as an output.  If *CONSTRAINT_P is not in
1307    canonical form, it will be made canonical.  (Note that `+' will be
1308    rpelaced with `=' as part of this process.)
1309
1310    Returns TRUE if all went well; FALSE if an error occurred.  */
1311
1312 bool
1313 parse_output_constraint (constraint_p, operand_num, ninputs, noutputs,
1314                          allows_mem, allows_reg, is_inout)
1315      const char **constraint_p;
1316      int operand_num;
1317      int ninputs;
1318      int noutputs;
1319      bool *allows_mem;
1320      bool *allows_reg;
1321      bool *is_inout;
1322 {
1323   const char *constraint = *constraint_p;
1324   const char *p;
1325
1326   /* Assume the constraint doesn't allow the use of either a register
1327      or memory.  */
1328   *allows_mem = false;
1329   *allows_reg = false;
1330
1331   /* Allow the `=' or `+' to not be at the beginning of the string,
1332      since it wasn't explicitly documented that way, and there is a
1333      large body of code that puts it last.  Swap the character to
1334      the front, so as not to uglify any place else.  */
1335   p = strchr (constraint, '=');
1336   if (!p)
1337     p = strchr (constraint, '+');
1338
1339   /* If the string doesn't contain an `=', issue an error
1340      message.  */
1341   if (!p)
1342     {
1343       error ("output operand constraint lacks `='");
1344       return false;
1345     }
1346
1347   /* If the constraint begins with `+', then the operand is both read
1348      from and written to.  */
1349   *is_inout = (*p == '+');
1350
1351   /* Canonicalize the output constraint so that it begins with `='.  */
1352   if (p != constraint || is_inout)
1353     {
1354       char *buf;
1355       size_t c_len = strlen (constraint);
1356
1357       if (p != constraint)
1358         warning ("output constraint `%c' for operand %d is not at the beginning",
1359                  *p, operand_num);
1360
1361       /* Make a copy of the constraint.  */
1362       buf = alloca (c_len + 1);
1363       strcpy (buf, constraint);
1364       /* Swap the first character and the `=' or `+'.  */
1365       buf[p - constraint] = buf[0];
1366       /* Make sure the first character is an `='.  (Until we do this,
1367          it might be a `+'.)  */
1368       buf[0] = '=';
1369       /* Replace the constraint with the canonicalized string.  */
1370       *constraint_p = ggc_alloc_string (buf, c_len);
1371       constraint = *constraint_p;
1372     }
1373
1374   /* Loop through the constraint string.  */
1375   for (p = constraint + 1; *p; ++p)
1376     switch (*p)
1377       {
1378       case '+':
1379       case '=':
1380         error ("operand constraint contains incorrectly positioned '+' or '='");
1381         return false;
1382
1383       case '%':
1384         if (operand_num + 1 == ninputs + noutputs)
1385           {
1386             error ("`%%' constraint used with last operand");
1387             return false;
1388           }
1389         break;
1390
1391       case 'V':  case 'm':  case 'o':
1392         *allows_mem = true;
1393         break;
1394
1395       case '?':  case '!':  case '*':  case '&':  case '#':
1396       case 'E':  case 'F':  case 'G':  case 'H':
1397       case 's':  case 'i':  case 'n':
1398       case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
1399       case 'N':  case 'O':  case 'P':  case ',':
1400         break;
1401
1402       case '0':  case '1':  case '2':  case '3':  case '4':
1403       case '5':  case '6':  case '7':  case '8':  case '9':
1404       case '[':
1405         error ("matching constraint not valid in output operand");
1406         return false;
1407
1408       case '<':  case '>':
1409         /* ??? Before flow, auto inc/dec insns are not supposed to exist,
1410            excepting those that expand_call created.  So match memory
1411            and hope.  */
1412         *allows_mem = true;
1413         break;
1414
1415       case 'g':  case 'X':
1416         *allows_reg = true;
1417         *allows_mem = true;
1418         break;
1419
1420       case 'p': case 'r':
1421         *allows_reg = true;
1422         break;
1423
1424       default:
1425         if (!ISALPHA (*p))
1426           break;
1427         if (REG_CLASS_FROM_LETTER (*p) != NO_REGS)
1428           *allows_reg = true;
1429 #ifdef EXTRA_CONSTRAINT
1430         else
1431           {
1432             /* Otherwise we can't assume anything about the nature of
1433                the constraint except that it isn't purely registers.
1434                Treat it like "g" and hope for the best.  */
1435             *allows_reg = true;
1436             *allows_mem = true;
1437           }
1438 #endif
1439         break;
1440       }
1441
1442   return true;
1443 }
1444
1445 /* Similar, but for input constraints.  */
1446
1447 static bool
1448 parse_input_constraint (constraint_p, input_num, ninputs, noutputs, ninout,
1449                         constraints, allows_mem, allows_reg)
1450      const char **constraint_p;
1451      int input_num;
1452      int ninputs;
1453      int noutputs;
1454      int ninout;
1455      const char * const * constraints;
1456      bool *allows_mem;
1457      bool *allows_reg;
1458 {
1459   const char *constraint = *constraint_p;
1460   const char *orig_constraint = constraint;
1461   size_t c_len = strlen (constraint);
1462   size_t j;
1463
1464   /* Assume the constraint doesn't allow the use of either
1465      a register or memory.  */
1466   *allows_mem = false;
1467   *allows_reg = false;
1468
1469   /* Make sure constraint has neither `=', `+', nor '&'.  */
1470
1471   for (j = 0; j < c_len; j++)
1472     switch (constraint[j])
1473       {
1474       case '+':  case '=':  case '&':
1475         if (constraint == orig_constraint)
1476           {
1477             error ("input operand constraint contains `%c'", constraint[j]);
1478             return false;
1479           }
1480         break;
1481
1482       case '%':
1483         if (constraint == orig_constraint
1484             && input_num + 1 == ninputs - ninout)
1485           {
1486             error ("`%%' constraint used with last operand");
1487             return false;
1488           }
1489         break;
1490
1491       case 'V':  case 'm':  case 'o':
1492         *allows_mem = true;
1493         break;
1494
1495       case '<':  case '>':
1496       case '?':  case '!':  case '*':  case '#':
1497       case 'E':  case 'F':  case 'G':  case 'H':
1498       case 's':  case 'i':  case 'n':
1499       case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
1500       case 'N':  case 'O':  case 'P':  case ',':
1501         break;
1502
1503         /* Whether or not a numeric constraint allows a register is
1504            decided by the matching constraint, and so there is no need
1505            to do anything special with them.  We must handle them in
1506            the default case, so that we don't unnecessarily force
1507            operands to memory.  */
1508       case '0':  case '1':  case '2':  case '3':  case '4':
1509       case '5':  case '6':  case '7':  case '8':  case '9':
1510         {
1511           char *end;
1512           unsigned long match;
1513
1514           match = strtoul (constraint + j, &end, 10);
1515           if (match >= (unsigned long) noutputs)
1516             {
1517               error ("matching constraint references invalid operand number");
1518               return false;
1519             }
1520
1521           /* Try and find the real constraint for this dup.  Only do this
1522              if the matching constraint is the only alternative.  */
1523           if (*end == '\0'
1524               && (j == 0 || (j == 1 && constraint[0] == '%')))
1525             {
1526               constraint = constraints[match];
1527               *constraint_p = constraint;
1528               c_len = strlen (constraint);
1529               j = 0;
1530               break;
1531             }
1532           else
1533             j = end - constraint;
1534         }
1535         /* Fall through.  */
1536
1537       case 'p':  case 'r':
1538         *allows_reg = true;
1539         break;
1540
1541       case 'g':  case 'X':
1542         *allows_reg = true;
1543         *allows_mem = true;
1544         break;
1545
1546       default:
1547         if (! ISALPHA (constraint[j]))
1548           {
1549             error ("invalid punctuation `%c' in constraint", constraint[j]);
1550             return false;
1551           }
1552         if (REG_CLASS_FROM_LETTER (constraint[j]) != NO_REGS)
1553           *allows_reg = true;
1554 #ifdef EXTRA_CONSTRAINT
1555         else
1556           {
1557             /* Otherwise we can't assume anything about the nature of
1558                the constraint except that it isn't purely registers.
1559                Treat it like "g" and hope for the best.  */
1560             *allows_reg = true;
1561             *allows_mem = true;
1562           }
1563 #endif
1564         break;
1565       }
1566
1567   return true;
1568 }
1569
1570 /* Generate RTL for an asm statement with arguments.
1571    STRING is the instruction template.
1572    OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
1573    Each output or input has an expression in the TREE_VALUE and
1574    and a tree list in TREE_PURPOSE which in turn contains a constraint
1575    name in TREE_VALUE (or NULL_TREE) and a constraint string
1576    in TREE_PURPOSE.
1577    CLOBBERS is a list of STRING_CST nodes each naming a hard register
1578    that is clobbered by this insn.
1579
1580    Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
1581    Some elements of OUTPUTS may be replaced with trees representing temporary
1582    values.  The caller should copy those temporary values to the originally
1583    specified lvalues.
1584
1585    VOL nonzero means the insn is volatile; don't optimize it.  */
1586
1587 void
1588 expand_asm_operands (string, outputs, inputs, clobbers, vol, filename, line)
1589      tree string, outputs, inputs, clobbers;
1590      int vol;
1591      const char *filename;
1592      int line;
1593 {
1594   rtvec argvec, constraintvec;
1595   rtx body;
1596   int ninputs = list_length (inputs);
1597   int noutputs = list_length (outputs);
1598   int ninout;
1599   int nclobbers;
1600   tree tail;
1601   int i;
1602   /* Vector of RTX's of evaluated output operands.  */
1603   rtx *output_rtx = (rtx *) alloca (noutputs * sizeof (rtx));
1604   int *inout_opnum = (int *) alloca (noutputs * sizeof (int));
1605   rtx *real_output_rtx = (rtx *) alloca (noutputs * sizeof (rtx));
1606   enum machine_mode *inout_mode
1607     = (enum machine_mode *) alloca (noutputs * sizeof (enum machine_mode));
1608   const char **constraints
1609     = (const char **) alloca ((noutputs + ninputs) * sizeof (const char *));
1610   /* The insn we have emitted.  */
1611   rtx insn;
1612   int old_generating_concat_p = generating_concat_p;
1613
1614   /* An ASM with no outputs needs to be treated as volatile, for now.  */
1615   if (noutputs == 0)
1616     vol = 1;
1617
1618   if (! check_operand_nalternatives (outputs, inputs))
1619     return;
1620
1621   if (! check_unique_operand_names (outputs, inputs))
1622     return;
1623
1624   string = resolve_operand_names (string, outputs, inputs, constraints);
1625
1626 #ifdef MD_ASM_CLOBBERS
1627   /* Sometimes we wish to automatically clobber registers across an asm.
1628      Case in point is when the i386 backend moved from cc0 to a hard reg --
1629      maintaining source-level compatibility means automatically clobbering
1630      the flags register.  */
1631   MD_ASM_CLOBBERS (clobbers);
1632 #endif
1633
1634   /* Count the number of meaningful clobbered registers, ignoring what
1635      we would ignore later.  */
1636   nclobbers = 0;
1637   for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1638     {
1639       const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1640
1641       i = decode_reg_name (regname);
1642       if (i >= 0 || i == -4)
1643         ++nclobbers;
1644       else if (i == -2)
1645         error ("unknown register name `%s' in `asm'", regname);
1646     }
1647
1648   last_expr_type = 0;
1649
1650   /* First pass over inputs and outputs checks validity and sets
1651      mark_addressable if needed.  */
1652
1653   ninout = 0;
1654   for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1655     {
1656       tree val = TREE_VALUE (tail);
1657       tree type = TREE_TYPE (val);
1658       const char *constraint;
1659       bool is_inout;
1660       bool allows_reg;
1661       bool allows_mem;
1662
1663       /* If there's an erroneous arg, emit no insn.  */
1664       if (type == error_mark_node)
1665         return;
1666
1667       /* Try to parse the output constraint.  If that fails, there's
1668          no point in going further.  */
1669       constraint = constraints[i];
1670       if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
1671                                     &allows_mem, &allows_reg, &is_inout))
1672         return;
1673
1674       if (! allows_reg
1675           && (allows_mem
1676               || is_inout
1677               || (DECL_P (val)
1678                   && GET_CODE (DECL_RTL (val)) == REG
1679                   && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
1680         mark_addressable (val);
1681
1682       if (is_inout)
1683         ninout++;
1684     }
1685
1686   ninputs += ninout;
1687   if (ninputs + noutputs > MAX_RECOG_OPERANDS)
1688     {
1689       error ("more than %d operands in `asm'", MAX_RECOG_OPERANDS);
1690       return;
1691     }
1692
1693   for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
1694     {
1695       bool allows_reg, allows_mem;
1696       const char *constraint;
1697
1698       /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
1699          would get VOIDmode and that could cause a crash in reload.  */
1700       if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
1701         return;
1702
1703       constraint = constraints[i + noutputs];
1704       if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
1705                                     constraints, &allows_mem, &allows_reg))
1706         return;
1707
1708       if (! allows_reg && allows_mem)
1709         mark_addressable (TREE_VALUE (tail));
1710     }
1711
1712   /* Second pass evaluates arguments.  */
1713
1714   ninout = 0;
1715   for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1716     {
1717       tree val = TREE_VALUE (tail);
1718       tree type = TREE_TYPE (val);
1719       bool is_inout;
1720       bool allows_reg;
1721       bool allows_mem;
1722
1723       if (!parse_output_constraint (&constraints[i], i, ninputs,
1724                                     noutputs, &allows_mem, &allows_reg,
1725                                     &is_inout))
1726         abort ();
1727
1728       /* If an output operand is not a decl or indirect ref and our constraint
1729          allows a register, make a temporary to act as an intermediate.
1730          Make the asm insn write into that, then our caller will copy it to
1731          the real output operand.  Likewise for promoted variables.  */
1732
1733       generating_concat_p = 0;
1734
1735       real_output_rtx[i] = NULL_RTX;
1736       if ((TREE_CODE (val) == INDIRECT_REF
1737            && allows_mem)
1738           || (DECL_P (val)
1739               && (allows_mem || GET_CODE (DECL_RTL (val)) == REG)
1740               && ! (GET_CODE (DECL_RTL (val)) == REG
1741                     && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
1742           || ! allows_reg
1743           || is_inout)
1744         {
1745           output_rtx[i] = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
1746
1747           if (! allows_reg && GET_CODE (output_rtx[i]) != MEM)
1748             error ("output number %d not directly addressable", i);
1749           if ((! allows_mem && GET_CODE (output_rtx[i]) == MEM)
1750               || GET_CODE (output_rtx[i]) == CONCAT)
1751             {
1752               real_output_rtx[i] = protect_from_queue (output_rtx[i], 1);
1753               output_rtx[i] = gen_reg_rtx (GET_MODE (output_rtx[i]));
1754               if (is_inout)
1755                 emit_move_insn (output_rtx[i], real_output_rtx[i]);
1756             }
1757         }
1758       else
1759         {
1760           output_rtx[i] = assign_temp (type, 0, 0, 1);
1761           TREE_VALUE (tail) = make_tree (type, output_rtx[i]);
1762         }
1763
1764       generating_concat_p = old_generating_concat_p;
1765
1766       if (is_inout)
1767         {
1768           inout_mode[ninout] = TYPE_MODE (type);
1769           inout_opnum[ninout++] = i;
1770         }
1771     }
1772
1773   /* Make vectors for the expression-rtx, constraint strings,
1774      and named operands.  */
1775
1776   argvec = rtvec_alloc (ninputs);
1777   constraintvec = rtvec_alloc (ninputs);
1778
1779   body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
1780                                 : GET_MODE (output_rtx[0])),
1781                                TREE_STRING_POINTER (string),
1782                                empty_string, 0, argvec, constraintvec,
1783                                filename, line);
1784
1785   MEM_VOLATILE_P (body) = vol;
1786
1787   /* Eval the inputs and put them into ARGVEC.
1788      Put their constraints into ASM_INPUTs and store in CONSTRAINTS.  */
1789
1790   for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
1791     {
1792       bool allows_reg, allows_mem;
1793       const char *constraint;
1794       tree val, type;
1795       rtx op;
1796
1797       constraint = constraints[i + noutputs];
1798       if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
1799                                     constraints, &allows_mem, &allows_reg))
1800         abort ();
1801
1802       generating_concat_p = 0;
1803
1804       val = TREE_VALUE (tail);
1805       type = TREE_TYPE (val);
1806       op = expand_expr (val, NULL_RTX, VOIDmode, 0);
1807
1808       /* Never pass a CONCAT to an ASM.  */
1809       if (GET_CODE (op) == CONCAT)
1810         op = force_reg (GET_MODE (op), op);
1811
1812       if (asm_operand_ok (op, constraint) <= 0)
1813         {
1814           if (allows_reg)
1815             op = force_reg (TYPE_MODE (type), op);
1816           else if (!allows_mem)
1817             warning ("asm operand %d probably doesn't match constraints",
1818                      i + noutputs);
1819           else if (CONSTANT_P (op))
1820             op = force_const_mem (TYPE_MODE (type), op);
1821           else if (GET_CODE (op) == REG
1822                    || GET_CODE (op) == SUBREG
1823                    || GET_CODE (op) == ADDRESSOF
1824                    || GET_CODE (op) == CONCAT)
1825             {
1826               tree qual_type = build_qualified_type (type,
1827                                                      (TYPE_QUALS (type)
1828                                                       | TYPE_QUAL_CONST));
1829               rtx memloc = assign_temp (qual_type, 1, 1, 1);
1830
1831               emit_move_insn (memloc, op);
1832               op = memloc;
1833             }
1834
1835           else if (GET_CODE (op) == MEM && MEM_VOLATILE_P (op))
1836             {
1837               /* We won't recognize volatile memory as available a
1838                  memory_operand at this point.  Ignore it.  */
1839             }
1840           else if (queued_subexp_p (op))
1841             ;
1842           else
1843             /* ??? Leave this only until we have experience with what
1844                happens in combine and elsewhere when constraints are
1845                not satisfied.  */
1846             warning ("asm operand %d probably doesn't match constraints",
1847                      i + noutputs);
1848         }
1849
1850       generating_concat_p = old_generating_concat_p;
1851       ASM_OPERANDS_INPUT (body, i) = op;
1852
1853       ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
1854         = gen_rtx_ASM_INPUT (TYPE_MODE (type), constraints[i + noutputs]);
1855     }
1856
1857   /* Protect all the operands from the queue now that they have all been
1858      evaluated.  */
1859
1860   generating_concat_p = 0;
1861
1862   for (i = 0; i < ninputs - ninout; i++)
1863     ASM_OPERANDS_INPUT (body, i)
1864       = protect_from_queue (ASM_OPERANDS_INPUT (body, i), 0);
1865
1866   for (i = 0; i < noutputs; i++)
1867     output_rtx[i] = protect_from_queue (output_rtx[i], 1);
1868
1869   /* For in-out operands, copy output rtx to input rtx.  */
1870   for (i = 0; i < ninout; i++)
1871     {
1872       int j = inout_opnum[i];
1873       char buffer[16];
1874
1875       ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
1876         = output_rtx[j];
1877
1878       sprintf (buffer, "%d", j);
1879       ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
1880         = gen_rtx_ASM_INPUT (inout_mode[i], ggc_alloc_string (buffer, -1));
1881     }
1882
1883   generating_concat_p = old_generating_concat_p;
1884
1885   /* Now, for each output, construct an rtx
1886      (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
1887                                ARGVEC CONSTRAINTS OPNAMES))
1888      If there is more than one, put them inside a PARALLEL.  */
1889
1890   if (noutputs == 1 && nclobbers == 0)
1891     {
1892       ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = constraints[0];
1893       insn = emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1894     }
1895
1896   else if (noutputs == 0 && nclobbers == 0)
1897     {
1898       /* No output operands: put in a raw ASM_OPERANDS rtx.  */
1899       insn = emit_insn (body);
1900     }
1901
1902   else
1903     {
1904       rtx obody = body;
1905       int num = noutputs;
1906
1907       if (num == 0)
1908         num = 1;
1909
1910       body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1911
1912       /* For each output operand, store a SET.  */
1913       for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1914         {
1915           XVECEXP (body, 0, i)
1916             = gen_rtx_SET (VOIDmode,
1917                            output_rtx[i],
1918                            gen_rtx_ASM_OPERANDS
1919                            (GET_MODE (output_rtx[i]),
1920                             TREE_STRING_POINTER (string),
1921                             constraints[i], i, argvec, constraintvec,
1922                             filename, line));
1923
1924           MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1925         }
1926
1927       /* If there are no outputs (but there are some clobbers)
1928          store the bare ASM_OPERANDS into the PARALLEL.  */
1929
1930       if (i == 0)
1931         XVECEXP (body, 0, i++) = obody;
1932
1933       /* Store (clobber REG) for each clobbered register specified.  */
1934
1935       for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1936         {
1937           const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1938           int j = decode_reg_name (regname);
1939
1940           if (j < 0)
1941             {
1942               if (j == -3)      /* `cc', which is not a register */
1943                 continue;
1944
1945               if (j == -4)      /* `memory', don't cache memory across asm */
1946                 {
1947                   XVECEXP (body, 0, i++)
1948                     = gen_rtx_CLOBBER (VOIDmode,
1949                                        gen_rtx_MEM
1950                                        (BLKmode,
1951                                         gen_rtx_SCRATCH (VOIDmode)));
1952                   continue;
1953                 }
1954
1955               /* Ignore unknown register, error already signaled.  */
1956               continue;
1957             }
1958
1959           /* Use QImode since that's guaranteed to clobber just one reg.  */
1960           XVECEXP (body, 0, i++)
1961             = gen_rtx_CLOBBER (VOIDmode, gen_rtx_REG (QImode, j));
1962         }
1963
1964       insn = emit_insn (body);
1965     }
1966
1967   /* For any outputs that needed reloading into registers, spill them
1968      back to where they belong.  */
1969   for (i = 0; i < noutputs; ++i)
1970     if (real_output_rtx[i])
1971       emit_move_insn (real_output_rtx[i], output_rtx[i]);
1972
1973   free_temp_slots ();
1974 }
1975
1976 /* A subroutine of expand_asm_operands.  Check that all operands have
1977    the same number of alternatives.  Return true if so.  */
1978
1979 static bool
1980 check_operand_nalternatives (outputs, inputs)
1981      tree outputs, inputs;
1982 {
1983   if (outputs || inputs)
1984     {
1985       tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1986       int nalternatives
1987         = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1988       tree next = inputs;
1989
1990       if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1991         {
1992           error ("too many alternatives in `asm'");
1993           return false;
1994         }
1995
1996       tmp = outputs;
1997       while (tmp)
1998         {
1999           const char *constraint
2000             = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
2001
2002           if (n_occurrences (',', constraint) != nalternatives)
2003             {
2004               error ("operand constraints for `asm' differ in number of alternatives");
2005               return false;
2006             }
2007
2008           if (TREE_CHAIN (tmp))
2009             tmp = TREE_CHAIN (tmp);
2010           else
2011             tmp = next, next = 0;
2012         }
2013     }
2014
2015   return true;
2016 }
2017
2018 /* A subroutine of expand_asm_operands.  Check that all operand names
2019    are unique.  Return true if so.  We rely on the fact that these names
2020    are identifiers, and so have been canonicalized by get_identifier,
2021    so all we need are pointer comparisons.  */
2022
2023 static bool
2024 check_unique_operand_names (outputs, inputs)
2025      tree outputs, inputs;
2026 {
2027   tree i, j;
2028
2029   for (i = outputs; i ; i = TREE_CHAIN (i))
2030     {
2031       tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
2032       if (! i_name)
2033         continue;
2034
2035       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
2036         if (i_name == TREE_PURPOSE (TREE_PURPOSE (j)))
2037           goto failure;
2038     }
2039
2040   for (i = inputs; i ; i = TREE_CHAIN (i))
2041     {
2042       tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
2043       if (! i_name)
2044         continue;
2045
2046       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
2047         if (i_name == TREE_PURPOSE (TREE_PURPOSE (j)))
2048           goto failure;
2049       for (j = outputs; j ; j = TREE_CHAIN (j))
2050         if (i_name == TREE_PURPOSE (TREE_PURPOSE (j)))
2051           goto failure;
2052     }
2053
2054   return true;
2055
2056  failure:
2057   error ("duplicate asm operand name '%s'",
2058          IDENTIFIER_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
2059   return false;
2060 }
2061
2062 /* A subroutine of expand_asm_operands.  Resolve the names of the operands
2063    in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
2064    STRING and in the constraints to those numbers.  */
2065
2066 static tree
2067 resolve_operand_names (string, outputs, inputs, pconstraints)
2068      tree string;
2069      tree outputs, inputs;
2070      const char **pconstraints;
2071 {
2072   char *buffer = xstrdup (TREE_STRING_POINTER (string));
2073   char *p;
2074   tree t;
2075
2076   /* Assume that we will not need extra space to perform the substitution.
2077      This because we get to remove '[' and ']', which means we cannot have
2078      a problem until we have more than 999 operands.  */
2079
2080   p = buffer;
2081   while ((p = strchr (p, '%')) != NULL)
2082     {
2083       if (p[1] == '[')
2084         p += 1;
2085       else if (ISALPHA (p[1]) && p[2] == '[')
2086         p += 2;
2087       else
2088         {
2089           p += 1;
2090           continue;
2091         }
2092
2093       p = resolve_operand_name_1 (p, outputs, inputs);
2094     }
2095
2096   string = build_string (strlen (buffer), buffer);
2097   free (buffer);
2098
2099   /* Collect output constraints here because it's convenient.
2100      There should be no named operands here; this is verified
2101      in expand_asm_operand.  */
2102   for (t = outputs; t ; t = TREE_CHAIN (t), pconstraints++)
2103     *pconstraints = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
2104
2105   /* Substitute [<name>] in input constraint strings.  */
2106   for (t = inputs; t ; t = TREE_CHAIN (t), pconstraints++)
2107     {
2108       const char *c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
2109       if (strchr (c, '[') == NULL)
2110         *pconstraints = c;
2111       else
2112         {
2113           p = buffer = xstrdup (c);
2114           while ((p = strchr (p, '[')) != NULL)
2115             p = resolve_operand_name_1 (p, outputs, inputs);
2116
2117           *pconstraints = ggc_alloc_string (buffer, -1);
2118           free (buffer);
2119         }
2120     }
2121
2122   return string;
2123 }
2124
2125 /* A subroutine of resolve_operand_names.  P points to the '[' for a
2126    potential named operand of the form [<name>].  In place, replace
2127    the name and brackets with a number.  Return a pointer to the
2128    balance of the string after substitution.  */
2129
2130 static char *
2131 resolve_operand_name_1 (p, outputs, inputs)
2132      char *p;
2133      tree outputs, inputs;
2134 {
2135   char *q;
2136   int op;
2137   tree t;
2138   size_t len;
2139
2140   /* Collect the operand name.  */
2141   q = strchr (p, ']');
2142   if (!q)
2143     {
2144       error ("missing close brace for named operand");
2145       return strchr (p, '\0');
2146     }
2147   len = q - p - 1;
2148
2149   /* Resolve the name to a number.  */
2150   for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
2151     {
2152       tree id = TREE_PURPOSE (TREE_PURPOSE (t));
2153       if (id)
2154         {
2155           const char *c = IDENTIFIER_POINTER (id);
2156           if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
2157             goto found;
2158         }
2159     }
2160   for (t = inputs; t ; t = TREE_CHAIN (t), op++)
2161     {
2162       tree id = TREE_PURPOSE (TREE_PURPOSE (t));
2163       if (id)
2164         {
2165           const char *c = IDENTIFIER_POINTER (id);
2166           if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
2167             goto found;
2168         }
2169     }
2170
2171   *q = '\0';
2172   error ("undefined named operand '%s'", p + 1);
2173   op = 0;
2174  found:
2175
2176   /* Replace the name with the number.  Unfortunately, not all libraries
2177      get the return value of sprintf correct, so search for the end of the
2178      generated string by hand.  */
2179   sprintf (p, "%d", op);
2180   p = strchr (p, '\0');
2181
2182   /* Verify the no extra buffer space assumption.  */
2183   if (p > q)
2184     abort ();
2185
2186   /* Shift the rest of the buffer down to fill the gap.  */
2187   memmove (p, q + 1, strlen (q + 1) + 1);
2188
2189   return p;
2190 }
2191 \f
2192 /* Generate RTL to evaluate the expression EXP
2193    and remember it in case this is the VALUE in a ({... VALUE; }) constr.
2194    Provided just for backward-compatibility.  expand_expr_stmt_value()
2195    should be used for new code.  */
2196
2197 void
2198 expand_expr_stmt (exp)
2199      tree exp;
2200 {
2201   expand_expr_stmt_value (exp, -1, 1);
2202 }
2203
2204 /* Generate RTL to evaluate the expression EXP.  WANT_VALUE tells
2205    whether to (1) save the value of the expression, (0) discard it or
2206    (-1) use expr_stmts_for_value to tell.  The use of -1 is
2207    deprecated, and retained only for backward compatibility.  */
2208
2209 void
2210 expand_expr_stmt_value (exp, want_value, maybe_last)
2211      tree exp;
2212      int want_value, maybe_last;
2213 {
2214   rtx value;
2215   tree type;
2216
2217   if (want_value == -1)
2218     want_value = expr_stmts_for_value != 0;
2219
2220   /* If -W, warn about statements with no side effects,
2221      except for an explicit cast to void (e.g. for assert()), and
2222      except for last statement in ({...}) where they may be useful.  */
2223   if (! want_value
2224       && (expr_stmts_for_value == 0 || ! maybe_last)
2225       && exp != error_mark_node)
2226     {
2227       if (! TREE_SIDE_EFFECTS (exp))
2228         {
2229           if ((extra_warnings || warn_unused_value)
2230               && !(TREE_CODE (exp) == CONVERT_EXPR
2231                    && VOID_TYPE_P (TREE_TYPE (exp))))
2232             warning_with_file_and_line (emit_filename, emit_lineno,
2233                                         "statement with no effect");
2234         }
2235       else if (warn_unused_value)
2236         warn_if_unused_value (exp);
2237     }
2238
2239   /* If EXP is of function type and we are expanding statements for
2240      value, convert it to pointer-to-function.  */
2241   if (want_value && TREE_CODE (TREE_TYPE (exp)) == FUNCTION_TYPE)
2242     exp = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
2243
2244   /* The call to `expand_expr' could cause last_expr_type and
2245      last_expr_value to get reset.  Therefore, we set last_expr_value
2246      and last_expr_type *after* calling expand_expr.  */
2247   value = expand_expr (exp, want_value ? NULL_RTX : const0_rtx,
2248                        VOIDmode, 0);
2249   type = TREE_TYPE (exp);
2250
2251   /* If all we do is reference a volatile value in memory,
2252      copy it to a register to be sure it is actually touched.  */
2253   if (value && GET_CODE (value) == MEM && TREE_THIS_VOLATILE (exp))
2254     {
2255       if (TYPE_MODE (type) == VOIDmode)
2256         ;
2257       else if (TYPE_MODE (type) != BLKmode)
2258         value = copy_to_reg (value);
2259       else
2260         {
2261           rtx lab = gen_label_rtx ();
2262
2263           /* Compare the value with itself to reference it.  */
2264           emit_cmp_and_jump_insns (value, value, EQ,
2265                                    expand_expr (TYPE_SIZE (type),
2266                                                 NULL_RTX, VOIDmode, 0),
2267                                    BLKmode, 0, lab);
2268           emit_label (lab);
2269         }
2270     }
2271
2272   /* If this expression is part of a ({...}) and is in memory, we may have
2273      to preserve temporaries.  */
2274   preserve_temp_slots (value);
2275
2276   /* Free any temporaries used to evaluate this expression.  Any temporary
2277      used as a result of this expression will already have been preserved
2278      above.  */
2279   free_temp_slots ();
2280
2281   if (want_value)
2282     {
2283       last_expr_value = value;
2284       last_expr_type = type;
2285     }
2286
2287   emit_queue ();
2288 }
2289
2290 /* Warn if EXP contains any computations whose results are not used.
2291    Return 1 if a warning is printed; 0 otherwise.  */
2292
2293 int
2294 warn_if_unused_value (exp)
2295      tree exp;
2296 {
2297   if (TREE_USED (exp))
2298     return 0;
2299
2300   /* Don't warn about void constructs.  This includes casting to void,
2301      void function calls, and statement expressions with a final cast
2302      to void.  */
2303   if (VOID_TYPE_P (TREE_TYPE (exp)))
2304     return 0;
2305
2306   switch (TREE_CODE (exp))
2307     {
2308     case PREINCREMENT_EXPR:
2309     case POSTINCREMENT_EXPR:
2310     case PREDECREMENT_EXPR:
2311     case POSTDECREMENT_EXPR:
2312     case MODIFY_EXPR:
2313     case INIT_EXPR:
2314     case TARGET_EXPR:
2315     case CALL_EXPR:
2316     case METHOD_CALL_EXPR:
2317     case RTL_EXPR:
2318     case TRY_CATCH_EXPR:
2319     case WITH_CLEANUP_EXPR:
2320     case EXIT_EXPR:
2321       return 0;
2322
2323     case BIND_EXPR:
2324       /* For a binding, warn if no side effect within it.  */
2325       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2326
2327     case SAVE_EXPR:
2328       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2329
2330     case TRUTH_ORIF_EXPR:
2331     case TRUTH_ANDIF_EXPR:
2332       /* In && or ||, warn if 2nd operand has no side effect.  */
2333       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2334
2335     case COMPOUND_EXPR:
2336       if (TREE_NO_UNUSED_WARNING (exp))
2337         return 0;
2338       if (warn_if_unused_value (TREE_OPERAND (exp, 0)))
2339         return 1;
2340       /* Let people do `(foo (), 0)' without a warning.  */
2341       if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
2342         return 0;
2343       return warn_if_unused_value (TREE_OPERAND (exp, 1));
2344
2345     case NOP_EXPR:
2346     case CONVERT_EXPR:
2347     case NON_LVALUE_EXPR:
2348       /* Don't warn about conversions not explicit in the user's program.  */
2349       if (TREE_NO_UNUSED_WARNING (exp))
2350         return 0;
2351       /* Assignment to a cast usually results in a cast of a modify.
2352          Don't complain about that.  There can be an arbitrary number of
2353          casts before the modify, so we must loop until we find the first
2354          non-cast expression and then test to see if that is a modify.  */
2355       {
2356         tree tem = TREE_OPERAND (exp, 0);
2357
2358         while (TREE_CODE (tem) == CONVERT_EXPR || TREE_CODE (tem) == NOP_EXPR)
2359           tem = TREE_OPERAND (tem, 0);
2360
2361         if (TREE_CODE (tem) == MODIFY_EXPR || TREE_CODE (tem) == INIT_EXPR
2362             || TREE_CODE (tem) == CALL_EXPR)
2363           return 0;
2364       }
2365       goto maybe_warn;
2366
2367     case INDIRECT_REF:
2368       /* Don't warn about automatic dereferencing of references, since
2369          the user cannot control it.  */
2370       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
2371         return warn_if_unused_value (TREE_OPERAND (exp, 0));
2372       /* Fall through.  */
2373
2374     default:
2375       /* Referencing a volatile value is a side effect, so don't warn.  */
2376       if ((DECL_P (exp)
2377            || TREE_CODE_CLASS (TREE_CODE (exp)) == 'r')
2378           && TREE_THIS_VOLATILE (exp))
2379         return 0;
2380
2381       /* If this is an expression which has no operands, there is no value
2382          to be unused.  There are no such language-independent codes,
2383          but front ends may define such.  */
2384       if (TREE_CODE_CLASS (TREE_CODE (exp)) == 'e'
2385           && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0)
2386         return 0;
2387
2388     maybe_warn:
2389       /* If this is an expression with side effects, don't warn.  */
2390       if (TREE_SIDE_EFFECTS (exp))
2391         return 0;
2392
2393       warning_with_file_and_line (emit_filename, emit_lineno,
2394                                   "value computed is not used");
2395       return 1;
2396     }
2397 }
2398
2399 /* Clear out the memory of the last expression evaluated.  */
2400
2401 void
2402 clear_last_expr ()
2403 {
2404   last_expr_type = 0;
2405 }
2406
2407 /* Begin a statement 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       /* If any of the elements are addressable, so is the entire
4205          union.  */
4206       if (TREE_USED (decl_elt))
4207         TREE_USED (decl) = 1;
4208
4209       /* Propagate the union's alignment to the elements.  */
4210       DECL_ALIGN (decl_elt) = DECL_ALIGN (decl);
4211       DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl);
4212
4213       /* If the element has BLKmode and the union doesn't, the union is
4214          aligned such that the element doesn't need to have BLKmode, so
4215          change the element's mode to the appropriate one for its size.  */
4216       if (mode == BLKmode && DECL_MODE (decl) != BLKmode)
4217         DECL_MODE (decl_elt) = mode
4218           = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1);
4219
4220       /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we
4221          instead create a new MEM rtx with the proper mode.  */
4222       if (GET_CODE (x) == MEM)
4223         {
4224           if (mode == GET_MODE (x))
4225             SET_DECL_RTL (decl_elt, x);
4226           else
4227             SET_DECL_RTL (decl_elt, adjust_address_nv (x, mode, 0));
4228         }
4229       else if (GET_CODE (x) == REG)
4230         {
4231           if (mode == GET_MODE (x))
4232             SET_DECL_RTL (decl_elt, x);
4233           else
4234             SET_DECL_RTL (decl_elt, gen_lowpart_SUBREG (mode, x));
4235         }
4236       else
4237         abort ();
4238
4239       /* Record the cleanup if there is one.  */
4240
4241       if (cleanup != 0)
4242         thisblock->data.block.cleanups
4243           = tree_cons (decl_elt, cleanup_elt,
4244                        thisblock->data.block.cleanups);
4245     }
4246 }
4247 \f
4248 /* Expand a list of cleanups LIST.
4249    Elements may be expressions or may be nested lists.
4250
4251    If DONT_DO is nonnull, then any list-element
4252    whose TREE_PURPOSE matches DONT_DO is omitted.
4253    This is sometimes used to avoid a cleanup associated with
4254    a value that is being returned out of the scope.
4255
4256    If IN_FIXUP is non-zero, we are generating this cleanup for a fixup
4257    goto and handle protection regions specially in that case.
4258
4259    If REACHABLE, we emit code, otherwise just inform the exception handling
4260    code about this finalization.  */
4261
4262 static void
4263 expand_cleanups (list, dont_do, in_fixup, reachable)
4264      tree list;
4265      tree dont_do;
4266      int in_fixup;
4267      int reachable;
4268 {
4269   tree tail;
4270   for (tail = list; tail; tail = TREE_CHAIN (tail))
4271     if (dont_do == 0 || TREE_PURPOSE (tail) != dont_do)
4272       {
4273         if (TREE_CODE (TREE_VALUE (tail)) == TREE_LIST)
4274           expand_cleanups (TREE_VALUE (tail), dont_do, in_fixup, reachable);
4275         else
4276           {
4277             if (! in_fixup && using_eh_for_cleanups_p)
4278               expand_eh_region_end_cleanup (TREE_VALUE (tail));
4279
4280             if (reachable)
4281               {
4282                 /* Cleanups may be run multiple times.  For example,
4283                    when exiting a binding contour, we expand the
4284                    cleanups associated with that contour.  When a goto
4285                    within that binding contour has a target outside that
4286                    contour, it will expand all cleanups from its scope to
4287                    the target.  Though the cleanups are expanded multiple
4288                    times, the control paths are non-overlapping so the
4289                    cleanups will not be executed twice.  */
4290
4291                 /* We may need to protect from outer cleanups.  */
4292                 if (in_fixup && using_eh_for_cleanups_p)
4293                   {
4294                     expand_eh_region_start ();
4295
4296                     expand_expr (TREE_VALUE (tail), const0_rtx, VOIDmode, 0);
4297
4298                     expand_eh_region_end_fixup (TREE_VALUE (tail));
4299                   }
4300                 else
4301                   expand_expr (TREE_VALUE (tail), const0_rtx, VOIDmode, 0);
4302
4303                 free_temp_slots ();
4304               }
4305           }
4306       }
4307 }
4308
4309 /* Mark when the context we are emitting RTL for as a conditional
4310    context, so that any cleanup actions we register with
4311    expand_decl_init will be properly conditionalized when those
4312    cleanup actions are later performed.  Must be called before any
4313    expression (tree) is expanded that is within a conditional context.  */
4314
4315 void
4316 start_cleanup_deferral ()
4317 {
4318   /* block_stack can be NULL if we are inside the parameter list.  It is
4319      OK to do nothing, because cleanups aren't possible here.  */
4320   if (block_stack)
4321     ++block_stack->data.block.conditional_code;
4322 }
4323
4324 /* Mark the end of a conditional region of code.  Because cleanup
4325    deferrals may be nested, we may still be in a conditional region
4326    after we end the currently deferred cleanups, only after we end all
4327    deferred cleanups, are we back in unconditional code.  */
4328
4329 void
4330 end_cleanup_deferral ()
4331 {
4332   /* block_stack can be NULL if we are inside the parameter list.  It is
4333      OK to do nothing, because cleanups aren't possible here.  */
4334   if (block_stack)
4335     --block_stack->data.block.conditional_code;
4336 }
4337
4338 /* Move all cleanups from the current block_stack
4339    to the containing block_stack, where they are assumed to
4340    have been created.  If anything can cause a temporary to
4341    be created, but not expanded for more than one level of
4342    block_stacks, then this code will have to change.  */
4343
4344 void
4345 move_cleanups_up ()
4346 {
4347   struct nesting *block = block_stack;
4348   struct nesting *outer = block->next;
4349
4350   outer->data.block.cleanups
4351     = chainon (block->data.block.cleanups,
4352                outer->data.block.cleanups);
4353   block->data.block.cleanups = 0;
4354 }
4355
4356 tree
4357 last_cleanup_this_contour ()
4358 {
4359   if (block_stack == 0)
4360     return 0;
4361
4362   return block_stack->data.block.cleanups;
4363 }
4364
4365 /* Return 1 if there are any pending cleanups at this point.
4366    If THIS_CONTOUR is nonzero, check the current contour as well.
4367    Otherwise, look only at the contours that enclose this one.  */
4368
4369 int
4370 any_pending_cleanups (this_contour)
4371      int this_contour;
4372 {
4373   struct nesting *block;
4374
4375   if (cfun == NULL || cfun->stmt == NULL || block_stack == 0)
4376     return 0;
4377
4378   if (this_contour && block_stack->data.block.cleanups != NULL)
4379     return 1;
4380   if (block_stack->data.block.cleanups == 0
4381       && block_stack->data.block.outer_cleanups == 0)
4382     return 0;
4383
4384   for (block = block_stack->next; block; block = block->next)
4385     if (block->data.block.cleanups != 0)
4386       return 1;
4387
4388   return 0;
4389 }
4390 \f
4391 /* Enter a case (Pascal) or switch (C) statement.
4392    Push a block onto case_stack and nesting_stack
4393    to accumulate the case-labels that are seen
4394    and to record the labels generated for the statement.
4395
4396    EXIT_FLAG is nonzero if `exit_something' should exit this case stmt.
4397    Otherwise, this construct is transparent for `exit_something'.
4398
4399    EXPR is the index-expression to be dispatched on.
4400    TYPE is its nominal type.  We could simply convert EXPR to this type,
4401    but instead we take short cuts.  */
4402
4403 void
4404 expand_start_case (exit_flag, expr, type, printname)
4405      int exit_flag;
4406      tree expr;
4407      tree type;
4408      const char *printname;
4409 {
4410   struct nesting *thiscase = ALLOC_NESTING ();
4411
4412   /* Make an entry on case_stack for the case we are entering.  */
4413
4414   thiscase->next = case_stack;
4415   thiscase->all = nesting_stack;
4416   thiscase->depth = ++nesting_depth;
4417   thiscase->exit_label = exit_flag ? gen_label_rtx () : 0;
4418   thiscase->data.case_stmt.case_list = 0;
4419   thiscase->data.case_stmt.index_expr = expr;
4420   thiscase->data.case_stmt.nominal_type = type;
4421   thiscase->data.case_stmt.default_label = 0;
4422   thiscase->data.case_stmt.printname = printname;
4423   thiscase->data.case_stmt.line_number_status = force_line_numbers ();
4424   case_stack = thiscase;
4425   nesting_stack = thiscase;
4426
4427   do_pending_stack_adjust ();
4428
4429   /* Make sure case_stmt.start points to something that won't
4430      need any transformation before expand_end_case.  */
4431   if (GET_CODE (get_last_insn ()) != NOTE)
4432     emit_note (NULL, NOTE_INSN_DELETED);
4433
4434   thiscase->data.case_stmt.start = get_last_insn ();
4435
4436   start_cleanup_deferral ();
4437 }
4438
4439 /* Start a "dummy case statement" within which case labels are invalid
4440    and are not connected to any larger real case statement.
4441    This can be used if you don't want to let a case statement jump
4442    into the middle of certain kinds of constructs.  */
4443
4444 void
4445 expand_start_case_dummy ()
4446 {
4447   struct nesting *thiscase = ALLOC_NESTING ();
4448
4449   /* Make an entry on case_stack for the dummy.  */
4450
4451   thiscase->next = case_stack;
4452   thiscase->all = nesting_stack;
4453   thiscase->depth = ++nesting_depth;
4454   thiscase->exit_label = 0;
4455   thiscase->data.case_stmt.case_list = 0;
4456   thiscase->data.case_stmt.start = 0;
4457   thiscase->data.case_stmt.nominal_type = 0;
4458   thiscase->data.case_stmt.default_label = 0;
4459   case_stack = thiscase;
4460   nesting_stack = thiscase;
4461   start_cleanup_deferral ();
4462 }
4463
4464 /* End a dummy case statement.  */
4465
4466 void
4467 expand_end_case_dummy ()
4468 {
4469   end_cleanup_deferral ();
4470   POPSTACK (case_stack);
4471 }
4472
4473 /* Return the data type of the index-expression
4474    of the innermost case statement, or null if none.  */
4475
4476 tree
4477 case_index_expr_type ()
4478 {
4479   if (case_stack)
4480     return TREE_TYPE (case_stack->data.case_stmt.index_expr);
4481   return 0;
4482 }
4483 \f
4484 static void
4485 check_seenlabel ()
4486 {
4487   /* If this is the first label, warn if any insns have been emitted.  */
4488   if (case_stack->data.case_stmt.line_number_status >= 0)
4489     {
4490       rtx insn;
4491
4492       restore_line_number_status
4493         (case_stack->data.case_stmt.line_number_status);
4494       case_stack->data.case_stmt.line_number_status = -1;
4495
4496       for (insn = case_stack->data.case_stmt.start;
4497            insn;
4498            insn = NEXT_INSN (insn))
4499         {
4500           if (GET_CODE (insn) == CODE_LABEL)
4501             break;
4502           if (GET_CODE (insn) != NOTE
4503               && (GET_CODE (insn) != INSN || GET_CODE (PATTERN (insn)) != USE))
4504             {
4505               do
4506                 insn = PREV_INSN (insn);
4507               while (insn && (GET_CODE (insn) != NOTE || NOTE_LINE_NUMBER (insn) < 0));
4508
4509               /* If insn is zero, then there must have been a syntax error.  */
4510               if (insn)
4511                 warning_with_file_and_line (NOTE_SOURCE_FILE (insn),
4512                                             NOTE_LINE_NUMBER (insn),
4513                                             "unreachable code at beginning of %s",
4514                                             case_stack->data.case_stmt.printname);
4515               break;
4516             }
4517         }
4518     }
4519 }
4520
4521 /* Accumulate one case or default label inside a case or switch statement.
4522    VALUE is the value of the case (a null pointer, for a default label).
4523    The function CONVERTER, when applied to arguments T and V,
4524    converts the value V to the type T.
4525
4526    If not currently inside a case or switch statement, return 1 and do
4527    nothing.  The caller will print a language-specific error message.
4528    If VALUE is a duplicate or overlaps, return 2 and do nothing
4529    except store the (first) duplicate node in *DUPLICATE.
4530    If VALUE is out of range, return 3 and do nothing.
4531    If we are jumping into the scope of a cleanup or var-sized array, return 5.
4532    Return 0 on success.
4533
4534    Extended to handle range statements.  */
4535
4536 int
4537 pushcase (value, converter, label, duplicate)
4538      tree value;
4539      tree (*converter) PARAMS ((tree, tree));
4540      tree label;
4541      tree *duplicate;
4542 {
4543   tree index_type;
4544   tree nominal_type;
4545
4546   /* Fail if not inside a real case statement.  */
4547   if (! (case_stack && case_stack->data.case_stmt.start))
4548     return 1;
4549
4550   if (stack_block_stack
4551       && stack_block_stack->depth > case_stack->depth)
4552     return 5;
4553
4554   index_type = TREE_TYPE (case_stack->data.case_stmt.index_expr);
4555   nominal_type = case_stack->data.case_stmt.nominal_type;
4556
4557   /* If the index is erroneous, avoid more problems: pretend to succeed.  */
4558   if (index_type == error_mark_node)
4559     return 0;
4560
4561   /* Convert VALUE to the type in which the comparisons are nominally done.  */
4562   if (value != 0)
4563     value = (*converter) (nominal_type, value);
4564
4565   check_seenlabel ();
4566
4567   /* Fail if this value is out of range for the actual type of the index
4568      (which may be narrower than NOMINAL_TYPE).  */
4569   if (value != 0
4570       && (TREE_CONSTANT_OVERFLOW (value)
4571           || ! int_fits_type_p (value, index_type)))
4572     return 3;
4573
4574   return add_case_node (value, value, label, duplicate);
4575 }
4576
4577 /* Like pushcase but this case applies to all values between VALUE1 and
4578    VALUE2 (inclusive).  If VALUE1 is NULL, the range starts at the lowest
4579    value of the index type and ends at VALUE2.  If VALUE2 is NULL, the range
4580    starts at VALUE1 and ends at the highest value of the index type.
4581    If both are NULL, this case applies to all values.
4582
4583    The return value is the same as that of pushcase but there is one
4584    additional error code: 4 means the specified range was empty.  */
4585
4586 int
4587 pushcase_range (value1, value2, converter, label, duplicate)
4588      tree value1, value2;
4589      tree (*converter) PARAMS ((tree, tree));
4590      tree label;
4591      tree *duplicate;
4592 {
4593   tree index_type;
4594   tree nominal_type;
4595
4596   /* Fail if not inside a real case statement.  */
4597   if (! (case_stack && case_stack->data.case_stmt.start))
4598     return 1;
4599
4600   if (stack_block_stack
4601       && stack_block_stack->depth > case_stack->depth)
4602     return 5;
4603
4604   index_type = TREE_TYPE (case_stack->data.case_stmt.index_expr);
4605   nominal_type = case_stack->data.case_stmt.nominal_type;
4606
4607   /* If the index is erroneous, avoid more problems: pretend to succeed.  */
4608   if (index_type == error_mark_node)
4609     return 0;
4610
4611   check_seenlabel ();
4612
4613   /* Convert VALUEs to type in which the comparisons are nominally done
4614      and replace any unspecified value with the corresponding bound.  */
4615   if (value1 == 0)
4616     value1 = TYPE_MIN_VALUE (index_type);
4617   if (value2 == 0)
4618     value2 = TYPE_MAX_VALUE (index_type);
4619
4620   /* Fail if the range is empty.  Do this before any conversion since
4621      we want to allow out-of-range empty ranges.  */
4622   if (value2 != 0 && tree_int_cst_lt (value2, value1))
4623     return 4;
4624
4625   /* If the max was unbounded, use the max of the nominal_type we are
4626      converting to.  Do this after the < check above to suppress false
4627      positives.  */
4628   if (value2 == 0)
4629     value2 = TYPE_MAX_VALUE (nominal_type);
4630
4631   value1 = (*converter) (nominal_type, value1);
4632   value2 = (*converter) (nominal_type, value2);
4633
4634   /* Fail if these values are out of range.  */
4635   if (TREE_CONSTANT_OVERFLOW (value1)
4636       || ! int_fits_type_p (value1, index_type))
4637     return 3;
4638
4639   if (TREE_CONSTANT_OVERFLOW (value2)
4640       || ! int_fits_type_p (value2, index_type))
4641     return 3;
4642
4643   return add_case_node (value1, value2, label, duplicate);
4644 }
4645
4646 /* Do the actual insertion of a case label for pushcase and pushcase_range
4647    into case_stack->data.case_stmt.case_list.  Use an AVL tree to avoid
4648    slowdown for large switch statements.  */
4649
4650 int
4651 add_case_node (low, high, label, duplicate)
4652      tree low, high;
4653      tree label;
4654      tree *duplicate;
4655 {
4656   struct case_node *p, **q, *r;
4657
4658   /* If there's no HIGH value, then this is not a case range; it's
4659      just a simple case label.  But that's just a degenerate case
4660      range.  */
4661   if (!high)
4662     high = low;
4663
4664   /* Handle default labels specially.  */
4665   if (!high && !low)
4666     {
4667       if (case_stack->data.case_stmt.default_label != 0)
4668         {
4669           *duplicate = case_stack->data.case_stmt.default_label;
4670           return 2;
4671         }
4672       case_stack->data.case_stmt.default_label = label;
4673       expand_label (label);
4674       return 0;
4675     }
4676
4677   q = &case_stack->data.case_stmt.case_list;
4678   p = *q;
4679
4680   while ((r = *q))
4681     {
4682       p = r;
4683
4684       /* Keep going past elements distinctly greater than HIGH.  */
4685       if (tree_int_cst_lt (high, p->low))
4686         q = &p->left;
4687
4688       /* or distinctly less than LOW.  */
4689       else if (tree_int_cst_lt (p->high, low))
4690         q = &p->right;
4691
4692       else
4693         {
4694           /* We have an overlap; this is an error.  */
4695           *duplicate = p->code_label;
4696           return 2;
4697         }
4698     }
4699
4700   /* Add this label to the chain, and succeed.  */
4701
4702   r = (struct case_node *) xmalloc (sizeof (struct case_node));
4703   r->low = low;
4704
4705   /* If the bounds are equal, turn this into the one-value case.  */
4706   if (tree_int_cst_equal (low, high))
4707     r->high = r->low;
4708   else
4709     r->high = high;
4710
4711   r->code_label = label;
4712   expand_label (label);
4713
4714   *q = r;
4715   r->parent = p;
4716   r->left = 0;
4717   r->right = 0;
4718   r->balance = 0;
4719
4720   while (p)
4721     {
4722       struct case_node *s;
4723
4724       if (r == p->left)
4725         {
4726           int b;
4727
4728           if (! (b = p->balance))
4729             /* Growth propagation from left side.  */
4730             p->balance = -1;
4731           else if (b < 0)
4732             {
4733               if (r->balance < 0)
4734                 {
4735                   /* R-Rotation */
4736                   if ((p->left = s = r->right))
4737                     s->parent = p;
4738
4739                   r->right = p;
4740                   p->balance = 0;
4741                   r->balance = 0;
4742                   s = p->parent;
4743                   p->parent = r;
4744
4745                   if ((r->parent = s))
4746                     {
4747                       if (s->left == p)
4748                         s->left = r;
4749                       else
4750                         s->right = r;
4751                     }
4752                   else
4753                     case_stack->data.case_stmt.case_list = r;
4754                 }
4755               else
4756                 /* r->balance == +1 */
4757                 {
4758                   /* LR-Rotation */
4759
4760                   int b2;
4761                   struct case_node *t = r->right;
4762
4763                   if ((p->left = s = t->right))
4764                     s->parent = p;
4765
4766                   t->right = p;
4767                   if ((r->right = s = t->left))
4768                     s->parent = r;
4769
4770                   t->left = r;
4771                   b = t->balance;
4772                   b2 = b < 0;
4773                   p->balance = b2;
4774                   b2 = -b2 - b;
4775                   r->balance = b2;
4776                   t->balance = 0;
4777                   s = p->parent;
4778                   p->parent = t;
4779                   r->parent = t;
4780
4781                   if ((t->parent = s))
4782                     {
4783                       if (s->left == p)
4784                         s->left = t;
4785                       else
4786                         s->right = t;
4787                     }
4788                   else
4789                     case_stack->data.case_stmt.case_list = t;
4790                 }
4791               break;
4792             }
4793
4794           else
4795             {
4796               /* p->balance == +1; growth of left side balances the node.  */
4797               p->balance = 0;
4798               break;
4799             }
4800         }
4801       else
4802         /* r == p->right */
4803         {
4804           int b;
4805
4806           if (! (b = p->balance))
4807             /* Growth propagation from right side.  */
4808             p->balance++;
4809           else if (b > 0)
4810             {
4811               if (r->balance > 0)
4812                 {
4813                   /* L-Rotation */
4814
4815                   if ((p->right = s = r->left))
4816                     s->parent = p;
4817
4818                   r->left = p;
4819                   p->balance = 0;
4820                   r->balance = 0;
4821                   s = p->parent;
4822                   p->parent = r;
4823                   if ((r->parent = s))
4824                     {
4825                       if (s->left == p)
4826                         s->left = r;
4827                       else
4828                         s->right = r;
4829                     }
4830
4831                   else
4832                     case_stack->data.case_stmt.case_list = r;
4833                 }
4834
4835               else
4836                 /* r->balance == -1 */
4837                 {
4838                   /* RL-Rotation */
4839                   int b2;
4840                   struct case_node *t = r->left;
4841
4842                   if ((p->right = s = t->left))
4843                     s->parent = p;
4844
4845                   t->left = p;
4846
4847                   if ((r->left = s = t->right))
4848                     s->parent = r;
4849
4850                   t->right = r;
4851                   b = t->balance;
4852                   b2 = b < 0;
4853                   r->balance = b2;
4854                   b2 = -b2 - b;
4855                   p->balance = b2;
4856                   t->balance = 0;
4857                   s = p->parent;
4858                   p->parent = t;
4859                   r->parent = t;
4860
4861                   if ((t->parent = s))
4862                     {
4863                       if (s->left == p)
4864                         s->left = t;
4865                       else
4866                         s->right = t;
4867                     }
4868
4869                   else
4870                     case_stack->data.case_stmt.case_list = t;
4871                 }
4872               break;
4873             }
4874           else
4875             {
4876               /* p->balance == -1; growth of right side balances the node.  */
4877               p->balance = 0;
4878               break;
4879             }
4880         }
4881
4882       r = p;
4883       p = p->parent;
4884     }
4885
4886   return 0;
4887 }
4888 \f
4889 /* Returns the number of possible values of TYPE.
4890    Returns -1 if the number is unknown, variable, or if the number does not
4891    fit in a HOST_WIDE_INT.
4892    Sets *SPARSENESS to 2 if TYPE is an ENUMERAL_TYPE whose values
4893    do not increase monotonically (there may be duplicates);
4894    to 1 if the values increase monotonically, but not always by 1;
4895    otherwise sets it to 0.  */
4896
4897 HOST_WIDE_INT
4898 all_cases_count (type, sparseness)
4899      tree type;
4900      int *sparseness;
4901 {
4902   tree t;
4903   HOST_WIDE_INT count, minval, lastval;
4904
4905   *sparseness = 0;
4906
4907   switch (TREE_CODE (type))
4908     {
4909     case BOOLEAN_TYPE:
4910       count = 2;
4911       break;
4912
4913     case CHAR_TYPE:
4914       count = 1 << BITS_PER_UNIT;
4915       break;
4916
4917     default:
4918     case INTEGER_TYPE:
4919       if (TYPE_MAX_VALUE (type) != 0
4920           && 0 != (t = fold (build (MINUS_EXPR, type, TYPE_MAX_VALUE (type),
4921                                     TYPE_MIN_VALUE (type))))
4922           && 0 != (t = fold (build (PLUS_EXPR, type, t,
4923                                     convert (type, integer_zero_node))))
4924           && host_integerp (t, 1))
4925         count = tree_low_cst (t, 1);
4926       else
4927         return -1;
4928       break;
4929
4930     case ENUMERAL_TYPE:
4931       /* Don't waste time with enumeral types with huge values.  */
4932       if (! host_integerp (TYPE_MIN_VALUE (type), 0)
4933           || TYPE_MAX_VALUE (type) == 0
4934           || ! host_integerp (TYPE_MAX_VALUE (type), 0))
4935         return -1;
4936
4937       lastval = minval = tree_low_cst (TYPE_MIN_VALUE (type), 0);
4938       count = 0;
4939
4940       for (t = TYPE_VALUES (type); t != NULL_TREE; t = TREE_CHAIN (t))
4941         {
4942           HOST_WIDE_INT thisval = tree_low_cst (TREE_VALUE (t), 0);
4943
4944           if (*sparseness == 2 || thisval <= lastval)
4945             *sparseness = 2;
4946           else if (thisval != minval + count)
4947             *sparseness = 1;
4948
4949           lastval = thisval;
4950           count++;
4951         }
4952     }
4953
4954   return count;
4955 }
4956
4957 #define BITARRAY_TEST(ARRAY, INDEX) \
4958   ((ARRAY)[(unsigned) (INDEX) / HOST_BITS_PER_CHAR]\
4959                           & (1 << ((unsigned) (INDEX) % HOST_BITS_PER_CHAR)))
4960 #define BITARRAY_SET(ARRAY, INDEX) \
4961   ((ARRAY)[(unsigned) (INDEX) / HOST_BITS_PER_CHAR]\
4962                           |= 1 << ((unsigned) (INDEX) % HOST_BITS_PER_CHAR))
4963
4964 /* Set the elements of the bitstring CASES_SEEN (which has length COUNT),
4965    with the case values we have seen, assuming the case expression
4966    has the given TYPE.
4967    SPARSENESS is as determined by all_cases_count.
4968
4969    The time needed is proportional to COUNT, unless
4970    SPARSENESS is 2, in which case quadratic time is needed.  */
4971
4972 void
4973 mark_seen_cases (type, cases_seen, count, sparseness)
4974      tree type;
4975      unsigned char *cases_seen;
4976      HOST_WIDE_INT count;
4977      int sparseness;
4978 {
4979   tree next_node_to_try = NULL_TREE;
4980   HOST_WIDE_INT next_node_offset = 0;
4981
4982   struct case_node *n, *root = case_stack->data.case_stmt.case_list;
4983   tree val = make_node (INTEGER_CST);
4984
4985   TREE_TYPE (val) = type;
4986   if (! root)
4987     /* Do nothing.  */
4988     ;
4989   else if (sparseness == 2)
4990     {
4991       tree t;
4992       unsigned HOST_WIDE_INT xlo;
4993
4994       /* This less efficient loop is only needed to handle
4995          duplicate case values (multiple enum constants
4996          with the same value).  */
4997       TREE_TYPE (val) = TREE_TYPE (root->low);
4998       for (t = TYPE_VALUES (type), xlo = 0; t != NULL_TREE;
4999            t = TREE_CHAIN (t), xlo++)
5000         {
5001           TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (TREE_VALUE (t));
5002           TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (TREE_VALUE (t));
5003           n = root;
5004           do
5005             {
5006               /* Keep going past elements distinctly greater than VAL.  */
5007               if (tree_int_cst_lt (val, n->low))
5008                 n = n->left;
5009
5010               /* or distinctly less than VAL.  */
5011               else if (tree_int_cst_lt (n->high, val))
5012                 n = n->right;
5013
5014               else
5015                 {
5016                   /* We have found a matching range.  */
5017                   BITARRAY_SET (cases_seen, xlo);
5018                   break;
5019                 }
5020             }
5021           while (n);
5022         }
5023     }
5024   else
5025     {
5026       if (root->left)
5027         case_stack->data.case_stmt.case_list = root = case_tree2list (root, 0);
5028
5029       for (n = root; n; n = n->right)
5030         {
5031           TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (n->low);
5032           TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (n->low);
5033           while (! tree_int_cst_lt (n->high, val))
5034             {
5035               /* Calculate (into xlo) the "offset" of the integer (val).
5036                  The element with lowest value has offset 0, the next smallest
5037                  element has offset 1, etc.  */
5038
5039               unsigned HOST_WIDE_INT xlo;
5040               HOST_WIDE_INT xhi;
5041               tree t;
5042
5043               if (sparseness && TYPE_VALUES (type) != NULL_TREE)
5044                 {
5045                   /* The TYPE_VALUES will be in increasing order, so
5046                      starting searching where we last ended.  */
5047                   t = next_node_to_try;
5048                   xlo = next_node_offset;
5049                   xhi = 0;
5050                   for (;;)
5051                     {
5052                       if (t == NULL_TREE)
5053                         {
5054                           t = TYPE_VALUES (type);
5055                           xlo = 0;
5056                         }
5057                       if (tree_int_cst_equal (val, TREE_VALUE (t)))
5058                         {
5059                           next_node_to_try = TREE_CHAIN (t);
5060                           next_node_offset = xlo + 1;
5061                           break;
5062                         }
5063                       xlo++;
5064                       t = TREE_CHAIN (t);
5065                       if (t == next_node_to_try)
5066                         {
5067                           xlo = -1;
5068                           break;
5069                         }
5070                     }
5071                 }
5072               else
5073                 {
5074                   t = TYPE_MIN_VALUE (type);
5075                   if (t)
5076                     neg_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t),
5077                                 &xlo, &xhi);
5078                   else
5079                     xlo = xhi = 0;
5080                   add_double (xlo, xhi,
5081                               TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
5082                               &xlo, &xhi);
5083                 }
5084
5085               if (xhi == 0 && xlo < (unsigned HOST_WIDE_INT) count)
5086                 BITARRAY_SET (cases_seen, xlo);
5087
5088               add_double (TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
5089                           1, 0,
5090                           &TREE_INT_CST_LOW (val), &TREE_INT_CST_HIGH (val));
5091             }
5092         }
5093     }
5094 }
5095
5096 /* Called when the index of a switch statement is an enumerated type
5097    and there is no default label.
5098
5099    Checks that all enumeration literals are covered by the case
5100    expressions of a switch.  Also, warn if there are any extra
5101    switch cases that are *not* elements of the enumerated type.
5102
5103    If all enumeration literals were covered by the case expressions,
5104    turn one of the expressions into the default expression since it should
5105    not be possible to fall through such a switch.  */
5106
5107 void
5108 check_for_full_enumeration_handling (type)
5109      tree type;
5110 {
5111   struct case_node *n;
5112   tree chain;
5113
5114   /* True iff the selector type is a numbered set mode.  */
5115   int sparseness = 0;
5116
5117   /* The number of possible selector values.  */
5118   HOST_WIDE_INT size;
5119
5120   /* For each possible selector value. a one iff it has been matched
5121      by a case value alternative.  */
5122   unsigned char *cases_seen;
5123
5124   /* The allocated size of cases_seen, in chars.  */
5125   HOST_WIDE_INT bytes_needed;
5126
5127   if (! warn_switch)
5128     return;
5129
5130   size = all_cases_count (type, &sparseness);
5131   bytes_needed = (size + HOST_BITS_PER_CHAR) / HOST_BITS_PER_CHAR;
5132
5133   if (size > 0 && size < 600000
5134       /* We deliberately use calloc here, not cmalloc, so that we can suppress
5135          this optimization if we don't have enough memory rather than
5136          aborting, as xmalloc would do.  */
5137       && (cases_seen =
5138           (unsigned char *) really_call_calloc (bytes_needed, 1)) != NULL)
5139     {
5140       HOST_WIDE_INT i;
5141       tree v = TYPE_VALUES (type);
5142
5143       /* The time complexity of this code is normally O(N), where
5144          N being the number of members in the enumerated type.
5145          However, if type is a ENUMERAL_TYPE whose values do not
5146          increase monotonically, O(N*log(N)) time may be needed.  */
5147
5148       mark_seen_cases (type, cases_seen, size, sparseness);
5149
5150       for (i = 0; v != NULL_TREE && i < size; i++, v = TREE_CHAIN (v))
5151         if (BITARRAY_TEST (cases_seen, i) == 0)
5152           warning ("enumeration value `%s' not handled in switch",
5153                    IDENTIFIER_POINTER (TREE_PURPOSE (v)));
5154
5155       free (cases_seen);
5156     }
5157
5158   /* Now we go the other way around; we warn if there are case
5159      expressions that don't correspond to enumerators.  This can
5160      occur since C and C++ don't enforce type-checking of
5161      assignments to enumeration variables.  */
5162
5163   if (case_stack->data.case_stmt.case_list
5164       && case_stack->data.case_stmt.case_list->left)
5165     case_stack->data.case_stmt.case_list
5166       = case_tree2list (case_stack->data.case_stmt.case_list, 0);
5167   if (warn_switch)
5168     for (n = case_stack->data.case_stmt.case_list; n; n = n->right)
5169       {
5170         for (chain = TYPE_VALUES (type);
5171              chain && !tree_int_cst_equal (n->low, TREE_VALUE (chain));
5172              chain = TREE_CHAIN (chain))
5173           ;
5174
5175         if (!chain)
5176           {
5177             if (TYPE_NAME (type) == 0)
5178               warning ("case value `%ld' not in enumerated type",
5179                        (long) TREE_INT_CST_LOW (n->low));
5180             else
5181               warning ("case value `%ld' not in enumerated type `%s'",
5182                        (long) TREE_INT_CST_LOW (n->low),
5183                        IDENTIFIER_POINTER ((TREE_CODE (TYPE_NAME (type))
5184                                             == IDENTIFIER_NODE)
5185                                            ? TYPE_NAME (type)
5186                                            : DECL_NAME (TYPE_NAME (type))));
5187           }
5188         if (!tree_int_cst_equal (n->low, n->high))
5189           {
5190             for (chain = TYPE_VALUES (type);
5191                  chain && !tree_int_cst_equal (n->high, TREE_VALUE (chain));
5192                  chain = TREE_CHAIN (chain))
5193               ;
5194
5195             if (!chain)
5196               {
5197                 if (TYPE_NAME (type) == 0)
5198                   warning ("case value `%ld' not in enumerated type",
5199                            (long) TREE_INT_CST_LOW (n->high));
5200                 else
5201                   warning ("case value `%ld' not in enumerated type `%s'",
5202                            (long) TREE_INT_CST_LOW (n->high),
5203                            IDENTIFIER_POINTER ((TREE_CODE (TYPE_NAME (type))
5204                                                 == IDENTIFIER_NODE)
5205                                                ? TYPE_NAME (type)
5206                                                : DECL_NAME (TYPE_NAME (type))));
5207               }
5208           }
5209       }
5210 }
5211
5212 /* Free CN, and its children.  */
5213
5214 static void
5215 free_case_nodes (cn)
5216      case_node_ptr cn;
5217 {
5218   if (cn)
5219     {
5220       free_case_nodes (cn->left);
5221       free_case_nodes (cn->right);
5222       free (cn);
5223     }
5224 }
5225
5226 \f
5227
5228 /* Terminate a case (Pascal) or switch (C) statement
5229    in which ORIG_INDEX is the expression to be tested.
5230    If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
5231    type as given in the source before any compiler conversions.
5232    Generate the code to test it and jump to the right place.  */
5233
5234 void
5235 expand_end_case_type (orig_index, orig_type)
5236      tree orig_index, orig_type;
5237 {
5238   tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
5239   rtx default_label = 0;
5240   struct case_node *n;
5241   unsigned int count;
5242   rtx index;
5243   rtx table_label;
5244   int ncases;
5245   rtx *labelvec;
5246   int i;
5247   rtx before_case, end;
5248   struct nesting *thiscase = case_stack;
5249   tree index_expr, index_type;
5250   int unsignedp;
5251
5252   /* Don't crash due to previous errors.  */
5253   if (thiscase == NULL)
5254     return;
5255
5256   table_label = gen_label_rtx ();
5257   index_expr = thiscase->data.case_stmt.index_expr;
5258   index_type = TREE_TYPE (index_expr);
5259   unsignedp = TREE_UNSIGNED (index_type);
5260   if (orig_type == NULL)
5261     orig_type = TREE_TYPE (orig_index);
5262
5263   do_pending_stack_adjust ();
5264
5265   /* This might get an spurious warning in the presence of a syntax error;
5266      it could be fixed by moving the call to check_seenlabel after the
5267      check for error_mark_node, and copying the code of check_seenlabel that
5268      deals with case_stack->data.case_stmt.line_number_status /
5269      restore_line_number_status in front of the call to end_cleanup_deferral;
5270      However, this might miss some useful warnings in the presence of
5271      non-syntax errors.  */
5272   check_seenlabel ();
5273
5274   /* An ERROR_MARK occurs for various reasons including invalid data type.  */
5275   if (index_type != error_mark_node)
5276     {
5277       /* If switch expression was an enumerated type, check that all
5278          enumeration literals are covered by the cases.
5279          No sense trying this if there's a default case, however.  */
5280
5281       if (!thiscase->data.case_stmt.default_label
5282           && TREE_CODE (orig_type) == ENUMERAL_TYPE
5283           && TREE_CODE (index_expr) != INTEGER_CST)
5284         check_for_full_enumeration_handling (orig_type);
5285
5286       /* If we don't have a default-label, create one here,
5287          after the body of the switch.  */
5288       if (thiscase->data.case_stmt.default_label == 0)
5289         {
5290           thiscase->data.case_stmt.default_label
5291             = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
5292           expand_label (thiscase->data.case_stmt.default_label);
5293         }
5294       default_label = label_rtx (thiscase->data.case_stmt.default_label);
5295
5296       before_case = get_last_insn ();
5297
5298       if (thiscase->data.case_stmt.case_list
5299           && thiscase->data.case_stmt.case_list->left)
5300         thiscase->data.case_stmt.case_list
5301           = case_tree2list (thiscase->data.case_stmt.case_list, 0);
5302
5303       /* Simplify the case-list before we count it.  */
5304       group_case_nodes (thiscase->data.case_stmt.case_list);
5305
5306       /* Get upper and lower bounds of case values.
5307          Also convert all the case values to the index expr's data type.  */
5308
5309       count = 0;
5310       for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5311         {
5312           /* Check low and high label values are integers.  */
5313           if (TREE_CODE (n->low) != INTEGER_CST)
5314             abort ();
5315           if (TREE_CODE (n->high) != INTEGER_CST)
5316             abort ();
5317
5318           n->low = convert (index_type, n->low);
5319           n->high = convert (index_type, n->high);
5320
5321           /* Count the elements and track the largest and smallest
5322              of them (treating them as signed even if they are not).  */
5323           if (count++ == 0)
5324             {
5325               minval = n->low;
5326               maxval = n->high;
5327             }
5328           else
5329             {
5330               if (INT_CST_LT (n->low, minval))
5331                 minval = n->low;
5332               if (INT_CST_LT (maxval, n->high))
5333                 maxval = n->high;
5334             }
5335           /* A range counts double, since it requires two compares.  */
5336           if (! tree_int_cst_equal (n->low, n->high))
5337             count++;
5338         }
5339
5340       /* Compute span of values.  */
5341       if (count != 0)
5342         range = fold (build (MINUS_EXPR, index_type, maxval, minval));
5343
5344       end_cleanup_deferral ();
5345
5346       if (count == 0)
5347         {
5348           expand_expr (index_expr, const0_rtx, VOIDmode, 0);
5349           emit_queue ();
5350           emit_jump (default_label);
5351         }
5352
5353       /* If range of values is much bigger than number of values,
5354          make a sequence of conditional branches instead of a dispatch.
5355          If the switch-index is a constant, do it this way
5356          because we can optimize it.  */
5357
5358       else if (count < case_values_threshold ()
5359                || compare_tree_int (range, 10 * count) > 0
5360                /* RANGE may be signed, and really large ranges will show up
5361                   as negative numbers.  */
5362                || compare_tree_int (range, 0) < 0
5363 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
5364                || flag_pic
5365 #endif
5366                || TREE_CODE (index_expr) == INTEGER_CST
5367                || (TREE_CODE (index_expr) == COMPOUND_EXPR
5368                    && TREE_CODE (TREE_OPERAND (index_expr, 1)) == INTEGER_CST))
5369         {
5370           index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
5371
5372           /* If the index is a short or char that we do not have
5373              an insn to handle comparisons directly, convert it to
5374              a full integer now, rather than letting each comparison
5375              generate the conversion.  */
5376
5377           if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
5378               && ! have_insn_for (COMPARE, GET_MODE (index)))
5379             {
5380               enum machine_mode wider_mode;
5381               for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
5382                    wider_mode = GET_MODE_WIDER_MODE (wider_mode))
5383                 if (have_insn_for (COMPARE, wider_mode))
5384                   {
5385                     index = convert_to_mode (wider_mode, index, unsignedp);
5386                     break;
5387                   }
5388             }
5389
5390           emit_queue ();
5391           do_pending_stack_adjust ();
5392
5393           index = protect_from_queue (index, 0);
5394           if (GET_CODE (index) == MEM)
5395             index = copy_to_reg (index);
5396           if (GET_CODE (index) == CONST_INT
5397               || TREE_CODE (index_expr) == INTEGER_CST)
5398             {
5399               /* Make a tree node with the proper constant value
5400                  if we don't already have one.  */
5401               if (TREE_CODE (index_expr) != INTEGER_CST)
5402                 {
5403                   index_expr
5404                     = build_int_2 (INTVAL (index),
5405                                    unsignedp || INTVAL (index) >= 0 ? 0 : -1);
5406                   index_expr = convert (index_type, index_expr);
5407                 }
5408
5409               /* For constant index expressions we need only
5410                  issue an unconditional branch to the appropriate
5411                  target code.  The job of removing any unreachable
5412                  code is left to the optimisation phase if the
5413                  "-O" option is specified.  */
5414               for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5415                 if (! tree_int_cst_lt (index_expr, n->low)
5416                     && ! tree_int_cst_lt (n->high, index_expr))
5417                   break;
5418
5419               if (n)
5420                 emit_jump (label_rtx (n->code_label));
5421               else
5422                 emit_jump (default_label);
5423             }
5424           else
5425             {
5426               /* If the index expression is not constant we generate
5427                  a binary decision tree to select the appropriate
5428                  target code.  This is done as follows:
5429
5430                  The list of cases is rearranged into a binary tree,
5431                  nearly optimal assuming equal probability for each case.
5432
5433                  The tree is transformed into RTL, eliminating
5434                  redundant test conditions at the same time.
5435
5436                  If program flow could reach the end of the
5437                  decision tree an unconditional jump to the
5438                  default code is emitted.  */
5439
5440               use_cost_table
5441                 = (TREE_CODE (orig_type) != ENUMERAL_TYPE
5442                    && estimate_case_costs (thiscase->data.case_stmt.case_list));
5443               balance_case_nodes (&thiscase->data.case_stmt.case_list, NULL);
5444               emit_case_nodes (index, thiscase->data.case_stmt.case_list,
5445                                default_label, index_type);
5446               emit_jump_if_reachable (default_label);
5447             }
5448         }
5449       else
5450         {
5451           if (! try_casesi (index_type, index_expr, minval, range,
5452                             table_label, default_label))
5453             {
5454               index_type = thiscase->data.case_stmt.nominal_type;
5455
5456               /* Index jumptables from zero for suitable values of
5457                  minval to avoid a subtraction.  */
5458               if (! optimize_size
5459                   && compare_tree_int (minval, 0) > 0
5460                   && compare_tree_int (minval, 3) < 0)
5461                 {
5462                   minval = integer_zero_node;
5463                   range = maxval;
5464                 }
5465
5466               if (! try_tablejump (index_type, index_expr, minval, range,
5467                                    table_label, default_label))
5468                 abort ();
5469             }
5470
5471           /* Get table of labels to jump to, in order of case index.  */
5472
5473           ncases = tree_low_cst (range, 0) + 1;
5474           labelvec = (rtx *) alloca (ncases * sizeof (rtx));
5475           memset ((char *) labelvec, 0, ncases * sizeof (rtx));
5476
5477           for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
5478             {
5479               /* Compute the low and high bounds relative to the minimum
5480                  value since that should fit in a HOST_WIDE_INT while the
5481                  actual values may not.  */
5482               HOST_WIDE_INT i_low
5483                 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5484                                              n->low, minval)), 1);
5485               HOST_WIDE_INT i_high
5486                 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
5487                                              n->high, minval)), 1);
5488               HOST_WIDE_INT i;
5489
5490               for (i = i_low; i <= i_high; i ++)
5491                 labelvec[i]
5492                   = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
5493             }
5494
5495           /* Fill in the gaps with the default.  */
5496           for (i = 0; i < ncases; i++)
5497             if (labelvec[i] == 0)
5498               labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
5499
5500           /* Output the table */
5501           emit_label (table_label);
5502
5503           if (CASE_VECTOR_PC_RELATIVE || flag_pic)
5504             emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
5505                                                    gen_rtx_LABEL_REF (Pmode, table_label),
5506                                                    gen_rtvec_v (ncases, labelvec),
5507                                                    const0_rtx, const0_rtx));
5508           else
5509             emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
5510                                               gen_rtvec_v (ncases, labelvec)));
5511
5512           /* If the case insn drops through the table,
5513              after the table we must jump to the default-label.
5514              Otherwise record no drop-through after the table.  */
5515 #ifdef CASE_DROPS_THROUGH
5516           emit_jump (default_label);
5517 #else
5518           emit_barrier ();
5519 #endif
5520         }
5521
5522       before_case = NEXT_INSN (before_case);
5523       end = get_last_insn ();
5524       if (squeeze_notes (&before_case, &end))
5525         abort ();
5526       reorder_insns (before_case, end,
5527                      thiscase->data.case_stmt.start);
5528     }
5529   else
5530     end_cleanup_deferral ();
5531
5532   if (thiscase->exit_label)
5533     emit_label (thiscase->exit_label);
5534
5535   free_case_nodes (case_stack->data.case_stmt.case_list);
5536   POPSTACK (case_stack);
5537
5538   free_temp_slots ();
5539 }
5540
5541 /* Convert the tree NODE into a list linked by the right field, with the left
5542    field zeroed.  RIGHT is used for recursion; it is a list to be placed
5543    rightmost in the resulting list.  */
5544
5545 static struct case_node *
5546 case_tree2list (node, right)
5547      struct case_node *node, *right;
5548 {
5549   struct case_node *left;
5550
5551   if (node->right)
5552     right = case_tree2list (node->right, right);
5553
5554   node->right = right;
5555   if ((left = node->left))
5556     {
5557       node->left = 0;
5558       return case_tree2list (left, node);
5559     }
5560
5561   return node;
5562 }
5563
5564 /* Generate code to jump to LABEL if OP1 and OP2 are equal.  */
5565
5566 static void
5567 do_jump_if_equal (op1, op2, label, unsignedp)
5568      rtx op1, op2, label;
5569      int unsignedp;
5570 {
5571   if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
5572     {
5573       if (INTVAL (op1) == INTVAL (op2))
5574         emit_jump (label);
5575     }
5576   else
5577     emit_cmp_and_jump_insns (op1, op2, EQ, NULL_RTX,
5578                              (GET_MODE (op1) == VOIDmode
5579                              ? GET_MODE (op2) : GET_MODE (op1)),
5580                              unsignedp, label);
5581 }
5582 \f
5583 /* Not all case values are encountered equally.  This function
5584    uses a heuristic to weight case labels, in cases where that
5585    looks like a reasonable thing to do.
5586
5587    Right now, all we try to guess is text, and we establish the
5588    following weights:
5589
5590         chars above space:      16
5591         digits:                 16
5592         default:                12
5593         space, punct:           8
5594         tab:                    4
5595         newline:                2
5596         other "\" chars:        1
5597         remaining chars:        0
5598
5599    If we find any cases in the switch that are not either -1 or in the range
5600    of valid ASCII characters, or are control characters other than those
5601    commonly used with "\", don't treat this switch scanning text.
5602
5603    Return 1 if these nodes are suitable for cost estimation, otherwise
5604    return 0.  */
5605
5606 static int
5607 estimate_case_costs (node)
5608      case_node_ptr node;
5609 {
5610   tree min_ascii = integer_minus_one_node;
5611   tree max_ascii = convert (TREE_TYPE (node->high), build_int_2 (127, 0));
5612   case_node_ptr n;
5613   int i;
5614
5615   /* If we haven't already made the cost table, make it now.  Note that the
5616      lower bound of the table is -1, not zero.  */
5617
5618   if (! cost_table_initialized)
5619     {
5620       cost_table_initialized = 1;
5621
5622       for (i = 0; i < 128; i++)
5623         {
5624           if (ISALNUM (i))
5625             COST_TABLE (i) = 16;
5626           else if (ISPUNCT (i))
5627             COST_TABLE (i) = 8;
5628           else if (ISCNTRL (i))
5629             COST_TABLE (i) = -1;
5630         }
5631
5632       COST_TABLE (' ') = 8;
5633       COST_TABLE ('\t') = 4;
5634       COST_TABLE ('\0') = 4;
5635       COST_TABLE ('\n') = 2;
5636       COST_TABLE ('\f') = 1;
5637       COST_TABLE ('\v') = 1;
5638       COST_TABLE ('\b') = 1;
5639     }
5640
5641   /* See if all the case expressions look like text.  It is text if the
5642      constant is >= -1 and the highest constant is <= 127.  Do all comparisons
5643      as signed arithmetic since we don't want to ever access cost_table with a
5644      value less than -1.  Also check that none of the constants in a range
5645      are strange control characters.  */
5646
5647   for (n = node; n; n = n->right)
5648     {
5649       if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high))
5650         return 0;
5651
5652       for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
5653            i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
5654         if (COST_TABLE (i) < 0)
5655           return 0;
5656     }
5657
5658   /* All interesting values are within the range of interesting
5659      ASCII characters.  */
5660   return 1;
5661 }
5662
5663 /* Scan an ordered list of case nodes
5664    combining those with consecutive values or ranges.
5665
5666    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
5667
5668 static void
5669 group_case_nodes (head)
5670      case_node_ptr head;
5671 {
5672   case_node_ptr node = head;
5673
5674   while (node)
5675     {
5676       rtx lb = next_real_insn (label_rtx (node->code_label));
5677       rtx lb2;
5678       case_node_ptr np = node;
5679
5680       /* Try to group the successors of NODE with NODE.  */
5681       while (((np = np->right) != 0)
5682              /* Do they jump to the same place?  */
5683              && ((lb2 = next_real_insn (label_rtx (np->code_label))) == lb
5684                  || (lb != 0 && lb2 != 0
5685                      && simplejump_p (lb)
5686                      && simplejump_p (lb2)
5687                      && rtx_equal_p (SET_SRC (PATTERN (lb)),
5688                                      SET_SRC (PATTERN (lb2)))))
5689              /* Are their ranges consecutive?  */
5690              && tree_int_cst_equal (np->low,
5691                                     fold (build (PLUS_EXPR,
5692                                                  TREE_TYPE (node->high),
5693                                                  node->high,
5694                                                  integer_one_node)))
5695              /* An overflow is not consecutive.  */
5696              && tree_int_cst_lt (node->high,
5697                                  fold (build (PLUS_EXPR,
5698                                               TREE_TYPE (node->high),
5699                                               node->high,
5700                                               integer_one_node))))
5701         {
5702           node->high = np->high;
5703         }
5704       /* NP is the first node after NODE which can't be grouped with it.
5705          Delete the nodes in between, and move on to that node.  */
5706       node->right = np;
5707       node = np;
5708     }
5709 }
5710
5711 /* Take an ordered list of case nodes
5712    and transform them into a near optimal binary tree,
5713    on the assumption that any target code selection value is as
5714    likely as any other.
5715
5716    The transformation is performed by splitting the ordered
5717    list into two equal sections plus a pivot.  The parts are
5718    then attached to the pivot as left and right branches.  Each
5719    branch is then transformed recursively.  */
5720
5721 static void
5722 balance_case_nodes (head, parent)
5723      case_node_ptr *head;
5724      case_node_ptr parent;
5725 {
5726   case_node_ptr np;
5727
5728   np = *head;
5729   if (np)
5730     {
5731       int cost = 0;
5732       int i = 0;
5733       int ranges = 0;
5734       case_node_ptr *npp;
5735       case_node_ptr left;
5736
5737       /* Count the number of entries on branch.  Also count the ranges.  */
5738
5739       while (np)
5740         {
5741           if (!tree_int_cst_equal (np->low, np->high))
5742             {
5743               ranges++;
5744               if (use_cost_table)
5745                 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
5746             }
5747
5748           if (use_cost_table)
5749             cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
5750
5751           i++;
5752           np = np->right;
5753         }
5754
5755       if (i > 2)
5756         {
5757           /* Split this list if it is long enough for that to help.  */
5758           npp = head;
5759           left = *npp;
5760           if (use_cost_table)
5761             {
5762               /* Find the place in the list that bisects the list's total cost,
5763                  Here I gets half the total cost.  */
5764               int n_moved = 0;
5765               i = (cost + 1) / 2;
5766               while (1)
5767                 {
5768                   /* Skip nodes while their cost does not reach that amount.  */
5769                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
5770                     i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
5771                   i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
5772                   if (i <= 0)
5773                     break;
5774                   npp = &(*npp)->right;
5775                   n_moved += 1;
5776                 }
5777               if (n_moved == 0)
5778                 {
5779                   /* Leave this branch lopsided, but optimize left-hand
5780                      side and fill in `parent' fields for right-hand side.  */
5781                   np = *head;
5782                   np->parent = parent;
5783                   balance_case_nodes (&np->left, np);
5784                   for (; np->right; np = np->right)
5785                     np->right->parent = np;
5786                   return;
5787                 }
5788             }
5789           /* If there are just three nodes, split at the middle one.  */
5790           else if (i == 3)
5791             npp = &(*npp)->right;
5792           else
5793             {
5794               /* Find the place in the list that bisects the list's total cost,
5795                  where ranges count as 2.
5796                  Here I gets half the total cost.  */
5797               i = (i + ranges + 1) / 2;
5798               while (1)
5799                 {
5800                   /* Skip nodes while their cost does not reach that amount.  */
5801                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
5802                     i--;
5803                   i--;
5804                   if (i <= 0)
5805                     break;
5806                   npp = &(*npp)->right;
5807                 }
5808             }
5809           *head = np = *npp;
5810           *npp = 0;
5811           np->parent = parent;
5812           np->left = left;
5813
5814           /* Optimize each of the two split parts.  */
5815           balance_case_nodes (&np->left, np);
5816           balance_case_nodes (&np->right, np);
5817         }
5818       else
5819         {
5820           /* Else leave this branch as one level,
5821              but fill in `parent' fields.  */
5822           np = *head;
5823           np->parent = parent;
5824           for (; np->right; np = np->right)
5825             np->right->parent = np;
5826         }
5827     }
5828 }
5829 \f
5830 /* Search the parent sections of the case node tree
5831    to see if a test for the lower bound of NODE would be redundant.
5832    INDEX_TYPE is the type of the index expression.
5833
5834    The instructions to generate the case decision tree are
5835    output in the same order as nodes are processed so it is
5836    known that if a parent node checks the range of the current
5837    node minus one that the current node is bounded at its lower
5838    span.  Thus the test would be redundant.  */
5839
5840 static int
5841 node_has_low_bound (node, index_type)
5842      case_node_ptr node;
5843      tree index_type;
5844 {
5845   tree low_minus_one;
5846   case_node_ptr pnode;
5847
5848   /* If the lower bound of this node is the lowest value in the index type,
5849      we need not test it.  */
5850
5851   if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
5852     return 1;
5853
5854   /* If this node has a left branch, the value at the left must be less
5855      than that at this node, so it cannot be bounded at the bottom and
5856      we need not bother testing any further.  */
5857
5858   if (node->left)
5859     return 0;
5860
5861   low_minus_one = fold (build (MINUS_EXPR, TREE_TYPE (node->low),
5862                                node->low, integer_one_node));
5863
5864   /* If the subtraction above overflowed, we can't verify anything.
5865      Otherwise, look for a parent that tests our value - 1.  */
5866
5867   if (! tree_int_cst_lt (low_minus_one, node->low))
5868     return 0;
5869
5870   for (pnode = node->parent; pnode; pnode = pnode->parent)
5871     if (tree_int_cst_equal (low_minus_one, pnode->high))
5872       return 1;
5873
5874   return 0;
5875 }
5876
5877 /* Search the parent sections of the case node tree
5878    to see if a test for the upper bound of NODE would be redundant.
5879    INDEX_TYPE is the type of the index expression.
5880
5881    The instructions to generate the case decision tree are
5882    output in the same order as nodes are processed so it is
5883    known that if a parent node checks the range of the current
5884    node plus one that the current node is bounded at its upper
5885    span.  Thus the test would be redundant.  */
5886
5887 static int
5888 node_has_high_bound (node, index_type)
5889      case_node_ptr node;
5890      tree index_type;
5891 {
5892   tree high_plus_one;
5893   case_node_ptr pnode;
5894
5895   /* If there is no upper bound, obviously no test is needed.  */
5896
5897   if (TYPE_MAX_VALUE (index_type) == NULL)
5898     return 1;
5899
5900   /* If the upper bound of this node is the highest value in the type
5901      of the index expression, we need not test against it.  */
5902
5903   if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
5904     return 1;
5905
5906   /* If this node has a right branch, the value at the right must be greater
5907      than that at this node, so it cannot be bounded at the top and
5908      we need not bother testing any further.  */
5909
5910   if (node->right)
5911     return 0;
5912
5913   high_plus_one = fold (build (PLUS_EXPR, TREE_TYPE (node->high),
5914                                node->high, integer_one_node));
5915
5916   /* If the addition above overflowed, we can't verify anything.
5917      Otherwise, look for a parent that tests our value + 1.  */
5918
5919   if (! tree_int_cst_lt (node->high, high_plus_one))
5920     return 0;
5921
5922   for (pnode = node->parent; pnode; pnode = pnode->parent)
5923     if (tree_int_cst_equal (high_plus_one, pnode->low))
5924       return 1;
5925
5926   return 0;
5927 }
5928
5929 /* Search the parent sections of the
5930    case node tree to see if both tests for the upper and lower
5931    bounds of NODE would be redundant.  */
5932
5933 static int
5934 node_is_bounded (node, index_type)
5935      case_node_ptr node;
5936      tree index_type;
5937 {
5938   return (node_has_low_bound (node, index_type)
5939           && node_has_high_bound (node, index_type));
5940 }
5941
5942 /*  Emit an unconditional jump to LABEL unless it would be dead code.  */
5943
5944 static void
5945 emit_jump_if_reachable (label)
5946      rtx label;
5947 {
5948   if (GET_CODE (get_last_insn ()) != BARRIER)
5949     emit_jump (label);
5950 }
5951 \f
5952 /* Emit step-by-step code to select a case for the value of INDEX.
5953    The thus generated decision tree follows the form of the
5954    case-node binary tree NODE, whose nodes represent test conditions.
5955    INDEX_TYPE is the type of the index of the switch.
5956
5957    Care is taken to prune redundant tests from the decision tree
5958    by detecting any boundary conditions already checked by
5959    emitted rtx.  (See node_has_high_bound, node_has_low_bound
5960    and node_is_bounded, above.)
5961
5962    Where the test conditions can be shown to be redundant we emit
5963    an unconditional jump to the target code.  As a further
5964    optimization, the subordinates of a tree node are examined to
5965    check for bounded nodes.  In this case conditional and/or
5966    unconditional jumps as a result of the boundary check for the
5967    current node are arranged to target the subordinates associated
5968    code for out of bound conditions on the current node.
5969
5970    We can assume that when control reaches the code generated here,
5971    the index value has already been compared with the parents
5972    of this node, and determined to be on the same side of each parent
5973    as this node is.  Thus, if this node tests for the value 51,
5974    and a parent tested for 52, we don't need to consider
5975    the possibility of a value greater than 51.  If another parent
5976    tests for the value 50, then this node need not test anything.  */
5977
5978 static void
5979 emit_case_nodes (index, node, default_label, index_type)
5980      rtx index;
5981      case_node_ptr node;
5982      rtx default_label;
5983      tree index_type;
5984 {
5985   /* If INDEX has an unsigned type, we must make unsigned branches.  */
5986   int unsignedp = TREE_UNSIGNED (index_type);
5987   enum machine_mode mode = GET_MODE (index);
5988   enum machine_mode imode = TYPE_MODE (index_type);
5989
5990   /* See if our parents have already tested everything for us.
5991      If they have, emit an unconditional jump for this node.  */
5992   if (node_is_bounded (node, index_type))
5993     emit_jump (label_rtx (node->code_label));
5994
5995   else if (tree_int_cst_equal (node->low, node->high))
5996     {
5997       /* Node is single valued.  First see if the index expression matches
5998          this node and then check our children, if any.  */
5999
6000       do_jump_if_equal (index,
6001                         convert_modes (mode, imode,
6002                                        expand_expr (node->low, NULL_RTX,
6003                                                     VOIDmode, 0),
6004                                        unsignedp),
6005                         label_rtx (node->code_label), unsignedp);
6006
6007       if (node->right != 0 && node->left != 0)
6008         {
6009           /* This node has children on both sides.
6010              Dispatch to one side or the other
6011              by comparing the index value with this node's value.
6012              If one subtree is bounded, check that one first,
6013              so we can avoid real branches in the tree.  */
6014
6015           if (node_is_bounded (node->right, index_type))
6016             {
6017               emit_cmp_and_jump_insns (index,
6018                                        convert_modes
6019                                        (mode, imode,
6020                                         expand_expr (node->high, NULL_RTX,
6021                                                      VOIDmode, 0),
6022                                         unsignedp),
6023                                        GT, NULL_RTX, mode, unsignedp,
6024                                        label_rtx (node->right->code_label));
6025               emit_case_nodes (index, node->left, default_label, index_type);
6026             }
6027
6028           else if (node_is_bounded (node->left, index_type))
6029             {
6030               emit_cmp_and_jump_insns (index,
6031                                        convert_modes
6032                                        (mode, imode,
6033                                         expand_expr (node->high, NULL_RTX,
6034                                                      VOIDmode, 0),
6035                                         unsignedp),
6036                                        LT, NULL_RTX, mode, unsignedp,
6037                                        label_rtx (node->left->code_label));
6038               emit_case_nodes (index, node->right, default_label, index_type);
6039             }
6040
6041           else
6042             {
6043               /* Neither node is bounded.  First distinguish the two sides;
6044                  then emit the code for one side at a time.  */
6045
6046               tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
6047
6048               /* See if the value is on the right.  */
6049               emit_cmp_and_jump_insns (index,
6050                                        convert_modes
6051                                        (mode, imode,
6052                                         expand_expr (node->high, NULL_RTX,
6053                                                      VOIDmode, 0),
6054                                         unsignedp),
6055                                        GT, NULL_RTX, mode, unsignedp,
6056                                        label_rtx (test_label));
6057
6058               /* Value must be on the left.
6059                  Handle the left-hand subtree.  */
6060               emit_case_nodes (index, node->left, default_label, index_type);
6061               /* If left-hand subtree does nothing,
6062                  go to default.  */
6063               emit_jump_if_reachable (default_label);
6064
6065               /* Code branches here for the right-hand subtree.  */
6066               expand_label (test_label);
6067               emit_case_nodes (index, node->right, default_label, index_type);
6068             }
6069         }
6070
6071       else if (node->right != 0 && node->left == 0)
6072         {
6073           /* Here we have a right child but no left so we issue conditional
6074              branch to default and process the right child.
6075
6076              Omit the conditional branch to default if we it avoid only one
6077              right child; it costs too much space to save so little time.  */
6078
6079           if (node->right->right || node->right->left
6080               || !tree_int_cst_equal (node->right->low, node->right->high))
6081             {
6082               if (!node_has_low_bound (node, index_type))
6083                 {
6084                   emit_cmp_and_jump_insns (index,
6085                                            convert_modes
6086                                            (mode, imode,
6087                                             expand_expr (node->high, NULL_RTX,
6088                                                          VOIDmode, 0),
6089                                             unsignedp),
6090                                            LT, NULL_RTX, mode, unsignedp,
6091                                            default_label);
6092                 }
6093
6094               emit_case_nodes (index, node->right, default_label, index_type);
6095             }
6096           else
6097             /* We cannot process node->right normally
6098                since we haven't ruled out the numbers less than
6099                this node's value.  So handle node->right explicitly.  */
6100             do_jump_if_equal (index,
6101                               convert_modes
6102                               (mode, imode,
6103                                expand_expr (node->right->low, NULL_RTX,
6104                                             VOIDmode, 0),
6105                                unsignedp),
6106                               label_rtx (node->right->code_label), unsignedp);
6107         }
6108
6109       else if (node->right == 0 && node->left != 0)
6110         {
6111           /* Just one subtree, on the left.  */
6112           if (node->left->left || node->left->right
6113               || !tree_int_cst_equal (node->left->low, node->left->high))
6114             {
6115               if (!node_has_high_bound (node, index_type))
6116                 {
6117                   emit_cmp_and_jump_insns (index,
6118                                            convert_modes
6119                                            (mode, imode,
6120                                             expand_expr (node->high, NULL_RTX,
6121                                                          VOIDmode, 0),
6122                                             unsignedp),
6123                                            GT, NULL_RTX, mode, unsignedp,
6124                                            default_label);
6125                 }
6126
6127               emit_case_nodes (index, node->left, default_label, index_type);
6128             }
6129           else
6130             /* We cannot process node->left normally
6131                since we haven't ruled out the numbers less than
6132                this node's value.  So handle node->left explicitly.  */
6133             do_jump_if_equal (index,
6134                               convert_modes
6135                               (mode, imode,
6136                                expand_expr (node->left->low, NULL_RTX,
6137                                             VOIDmode, 0),
6138                                unsignedp),
6139                               label_rtx (node->left->code_label), unsignedp);
6140         }
6141     }
6142   else
6143     {
6144       /* Node is a range.  These cases are very similar to those for a single
6145          value, except that we do not start by testing whether this node
6146          is the one to branch to.  */
6147
6148       if (node->right != 0 && node->left != 0)
6149         {
6150           /* Node has subtrees on both sides.
6151              If the right-hand subtree is bounded,
6152              test for it first, since we can go straight there.
6153              Otherwise, we need to make a branch in the control structure,
6154              then handle the two subtrees.  */
6155           tree test_label = 0;
6156
6157           if (node_is_bounded (node->right, index_type))
6158             /* Right hand node is fully bounded so we can eliminate any
6159                testing and branch directly to the target code.  */
6160             emit_cmp_and_jump_insns (index,
6161                                      convert_modes
6162                                      (mode, imode,
6163                                       expand_expr (node->high, NULL_RTX,
6164                                                    VOIDmode, 0),
6165                                       unsignedp),
6166                                      GT, NULL_RTX, mode, unsignedp,
6167                                      label_rtx (node->right->code_label));
6168           else
6169             {
6170               /* Right hand node requires testing.
6171                  Branch to a label where we will handle it later.  */
6172
6173               test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
6174               emit_cmp_and_jump_insns (index,
6175                                        convert_modes
6176                                        (mode, imode,
6177                                         expand_expr (node->high, NULL_RTX,
6178                                                      VOIDmode, 0),
6179                                         unsignedp),
6180                                        GT, NULL_RTX, mode, unsignedp,
6181                                        label_rtx (test_label));
6182             }
6183
6184           /* Value belongs to this node or to the left-hand subtree.  */
6185
6186           emit_cmp_and_jump_insns (index,
6187                                    convert_modes
6188                                    (mode, imode,
6189                                     expand_expr (node->low, NULL_RTX,
6190                                                  VOIDmode, 0),
6191                                     unsignedp),
6192                                    GE, NULL_RTX, mode, unsignedp,
6193                                    label_rtx (node->code_label));
6194
6195           /* Handle the left-hand subtree.  */
6196           emit_case_nodes (index, node->left, default_label, index_type);
6197
6198           /* If right node had to be handled later, do that now.  */
6199
6200           if (test_label)
6201             {
6202               /* If the left-hand subtree fell through,
6203                  don't let it fall into the right-hand subtree.  */
6204               emit_jump_if_reachable (default_label);
6205
6206               expand_label (test_label);
6207               emit_case_nodes (index, node->right, default_label, index_type);
6208             }
6209         }
6210
6211       else if (node->right != 0 && node->left == 0)
6212         {
6213           /* Deal with values to the left of this node,
6214              if they are possible.  */
6215           if (!node_has_low_bound (node, index_type))
6216             {
6217               emit_cmp_and_jump_insns (index,
6218                                        convert_modes
6219                                        (mode, imode,
6220                                         expand_expr (node->low, NULL_RTX,
6221                                                      VOIDmode, 0),
6222                                         unsignedp),
6223                                        LT, NULL_RTX, mode, unsignedp,
6224                                        default_label);
6225             }
6226
6227           /* Value belongs to this node or to the right-hand subtree.  */
6228
6229           emit_cmp_and_jump_insns (index,
6230                                    convert_modes
6231                                    (mode, imode,
6232                                     expand_expr (node->high, NULL_RTX,
6233                                                  VOIDmode, 0),
6234                                     unsignedp),
6235                                    LE, NULL_RTX, mode, unsignedp,
6236                                    label_rtx (node->code_label));
6237
6238           emit_case_nodes (index, node->right, default_label, index_type);
6239         }
6240
6241       else if (node->right == 0 && node->left != 0)
6242         {
6243           /* Deal with values to the right of this node,
6244              if they are possible.  */
6245           if (!node_has_high_bound (node, index_type))
6246             {
6247               emit_cmp_and_jump_insns (index,
6248                                        convert_modes
6249                                        (mode, imode,
6250                                         expand_expr (node->high, NULL_RTX,
6251                                                      VOIDmode, 0),
6252                                         unsignedp),
6253                                        GT, NULL_RTX, mode, unsignedp,
6254                                        default_label);
6255             }
6256
6257           /* Value belongs to this node or to the left-hand subtree.  */
6258
6259           emit_cmp_and_jump_insns (index,
6260                                    convert_modes
6261                                    (mode, imode,
6262                                     expand_expr (node->low, NULL_RTX,
6263                                                  VOIDmode, 0),
6264                                     unsignedp),
6265                                    GE, NULL_RTX, mode, unsignedp,
6266                                    label_rtx (node->code_label));
6267
6268           emit_case_nodes (index, node->left, default_label, index_type);
6269         }
6270
6271       else
6272         {
6273           /* Node has no children so we check low and high bounds to remove
6274              redundant tests.  Only one of the bounds can exist,
6275              since otherwise this node is bounded--a case tested already.  */
6276           int high_bound = node_has_high_bound (node, index_type);
6277           int low_bound = node_has_low_bound (node, index_type);
6278
6279           if (!high_bound && low_bound)
6280             {
6281               emit_cmp_and_jump_insns (index,
6282                                        convert_modes
6283                                        (mode, imode,
6284                                         expand_expr (node->high, NULL_RTX,
6285                                                      VOIDmode, 0),
6286                                         unsignedp),
6287                                        GT, NULL_RTX, mode, unsignedp,
6288                                        default_label);
6289             }
6290
6291           else if (!low_bound && high_bound)
6292             {
6293               emit_cmp_and_jump_insns (index,
6294                                        convert_modes
6295                                        (mode, imode,
6296                                         expand_expr (node->low, NULL_RTX,
6297                                                      VOIDmode, 0),
6298                                         unsignedp),
6299                                        LT, NULL_RTX, mode, unsignedp,
6300                                        default_label);
6301             }
6302           else if (!low_bound && !high_bound)
6303             {
6304               /* Widen LOW and HIGH to the same width as INDEX.  */
6305               tree type = type_for_mode (mode, unsignedp);
6306               tree low = build1 (CONVERT_EXPR, type, node->low);
6307               tree high = build1 (CONVERT_EXPR, type, node->high);
6308               rtx low_rtx, new_index, new_bound;
6309
6310               /* Instead of doing two branches, emit one unsigned branch for
6311                  (index-low) > (high-low).  */
6312               low_rtx = expand_expr (low, NULL_RTX, mode, 0);
6313               new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
6314                                                NULL_RTX, unsignedp,
6315                                                OPTAB_WIDEN);
6316               new_bound = expand_expr (fold (build (MINUS_EXPR, type,
6317                                                     high, low)),
6318                                        NULL_RTX, mode, 0);
6319
6320               emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
6321                                        mode, 1, default_label);
6322             }
6323
6324           emit_jump (label_rtx (node->code_label));
6325         }
6326     }
6327 }