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