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