gcc/stmt.c

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