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