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