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