gcc/stmt.c

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