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