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