gcc/flow.c

   1 /* Data flow analysis for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* This file contains the data flow analysis pass of the compiler.  It
  23    computes data flow information which tells combine_instructions
  24    which insns to consider combining and controls register allocation.
  25
  26    Additional data flow information that is too bulky to record is
  27    generated during the analysis, and is used at that time to create
  28    autoincrement and autodecrement addressing.
  29
  30    The first step is dividing the function into basic blocks.
  31    find_basic_blocks does this.  Then life_analysis determines
  32    where each register is live and where it is dead.
  33
  34    ** find_basic_blocks **
  35
  36    find_basic_blocks divides the current function's rtl into basic
  37    blocks and constructs the CFG.  The blocks are recorded in the
  38    basic_block_info array; the CFG exists in the edge structures
  39    referenced by the blocks.
  40
  41    find_basic_blocks also finds any unreachable loops and deletes them.
  42
  43    ** life_analysis **
  44
  45    life_analysis is called immediately after find_basic_blocks.
  46    It uses the basic block information to determine where each
  47    hard or pseudo register is live.
  48
  49    ** live-register info **
  50
  51    The information about where each register is live is in two parts:
  52    the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
  53
  54    basic_block->global_live_at_start has an element for each basic
  55    block, and the element is a bit-vector with a bit for each hard or
  56    pseudo register.  The bit is 1 if the register is live at the
  57    beginning of the basic block.
  58
  59    Two types of elements can be added to an insn's REG_NOTES.
  60    A REG_DEAD note is added to an insn's REG_NOTES for any register
  61    that meets both of two conditions:  The value in the register is not
  62    needed in subsequent insns and the insn does not replace the value in
  63    the register (in the case of multi-word hard registers, the value in
  64    each register must be replaced by the insn to avoid a REG_DEAD note).
  65
  66    In the vast majority of cases, an object in a REG_DEAD note will be
  67    used somewhere in the insn.  The (rare) exception to this is if an
  68    insn uses a multi-word hard register and only some of the registers are
  69    needed in subsequent insns.  In that case, REG_DEAD notes will be
  70    provided for those hard registers that are not subsequently needed.
  71    Partial REG_DEAD notes of this type do not occur when an insn sets
  72    only some of the hard registers used in such a multi-word operand;
  73    omitting REG_DEAD notes for objects stored in an insn is optional and
  74    the desire to do so does not justify the complexity of the partial
  75    REG_DEAD notes.
  76
  77    REG_UNUSED notes are added for each register that is set by the insn
  78    but is unused subsequently (if every register set by the insn is unused
  79    and the insn does not reference memory or have some other side-effect,
  80    the insn is deleted instead).  If only part of a multi-word hard
  81    register is used in a subsequent insn, REG_UNUSED notes are made for
  82    the parts that will not be used.
  83
  84    To determine which registers are live after any insn, one can
  85    start from the beginning of the basic block and scan insns, noting
  86    which registers are set by each insn and which die there.
  87
  88    ** Other actions of life_analysis **
  89
  90    life_analysis sets up the LOG_LINKS fields of insns because the
  91    information needed to do so is readily available.
  92
  93    life_analysis deletes insns whose only effect is to store a value
  94    that is never used.
  95
  96    life_analysis notices cases where a reference to a register as
  97    a memory address can be combined with a preceding or following
  98    incrementation or decrementation of the register.  The separate
  99    instruction to increment or decrement is deleted and the address
 100    is changed to a POST_INC or similar rtx.
 101
 102    Each time an incrementing or decrementing address is created,
 103    a REG_INC element is added to the insn's REG_NOTES list.
 104
 105    life_analysis fills in certain vectors containing information about
 106    register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
 107    REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
 108
 109    life_analysis sets current_function_sp_is_unchanging if the function
 110    doesn't modify the stack pointer.  */
 111
 112 /* TODO:
 113
 114    Split out from life_analysis:
 115         - local property discovery (bb->local_live, bb->local_set)
 116         - global property computation
 117         - log links creation
 118         - pre/post modify transformation
 119 */
 120 \f
 121 #include "config.h"
 122 #include "system.h"
 123 #include "tree.h"
 124 #include "rtl.h"
 125 #include "tm_p.h"
 126 #include "hard-reg-set.h"
 127 #include "basic-block.h"
 128 #include "insn-config.h"
 129 #include "regs.h"
 130 #include "flags.h"
 131 #include "output.h"
 132 #include "function.h"
 133 #include "except.h"
 134 #include "toplev.h"
 135 #include "recog.h"
 136 #include "expr.h"
 137 #include "ssa.h"
 138
 139 #include "obstack.h"
 140 #include "splay-tree.h"
 141
 142 #define obstack_chunk_alloc xmalloc
 143 #define obstack_chunk_free free
 144
 145 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
 146    the stack pointer does not matter.  The value is tested only in
 147    functions that have frame pointers.
 148    No definition is equivalent to always zero.  */
 149 #ifndef EXIT_IGNORE_STACK
 150 #define EXIT_IGNORE_STACK 0
 151 #endif
 152
 153 #ifndef HAVE_epilogue
 154 #define HAVE_epilogue 0
 155 #endif
 156 #ifndef HAVE_prologue
 157 #define HAVE_prologue 0
 158 #endif
 159 #ifndef HAVE_sibcall_epilogue
 160 #define HAVE_sibcall_epilogue 0
 161 #endif
 162
 163 #ifndef LOCAL_REGNO
 164 #define LOCAL_REGNO(REGNO)  0
 165 #endif
 166 #ifndef EPILOGUE_USES
 167 #define EPILOGUE_USES(REGNO)  0
 168 #endif
 169
 170 #ifdef HAVE_conditional_execution
 171 #ifndef REVERSE_CONDEXEC_PREDICATES_P
 172 #define REVERSE_CONDEXEC_PREDICATES_P(x, y) ((x) == reverse_condition (y))
 173 #endif
 174 #endif
 175
 176 /* The obstack on which the flow graph components are allocated.  */
 177
 178 struct obstack flow_obstack;
 179 static char *flow_firstobj;
 180
 181 /* Number of basic blocks in the current function.  */
 182
 183 int n_basic_blocks;
 184
 185 /* Number of edges in the current function.  */
 186
 187 int n_edges;
 188
 189 /* The basic block array.  */
 190
 191 varray_type basic_block_info;
 192
 193 /* The special entry and exit blocks.  */
 194
 195 struct basic_block_def entry_exit_blocks[2]
 196 = {{NULL,                       /* head */
 197     NULL,                       /* end */
 198     NULL,                       /* pred */
 199     NULL,                       /* succ */
 200     NULL,                       /* local_set */
 201     NULL,                       /* cond_local_set */
 202     NULL,                       /* global_live_at_start */
 203     NULL,                       /* global_live_at_end */
 204     NULL,                       /* aux */
 205     ENTRY_BLOCK,                /* index */
 206     0,                          /* loop_depth */
 207     0,                          /* count */
 208     0                           /* frequency */
 209   },
 210   {
 211     NULL,                       /* head */
 212     NULL,                       /* end */
 213     NULL,                       /* pred */
 214     NULL,                       /* succ */
 215     NULL,                       /* local_set */
 216     NULL,                       /* cond_local_set */
 217     NULL,                       /* global_live_at_start */
 218     NULL,                       /* global_live_at_end */
 219     NULL,                       /* aux */
 220     EXIT_BLOCK,                 /* index */
 221     0,                          /* loop_depth */
 222     0,                          /* count */
 223     0                           /* frequency */
 224   }
 225 };
 226
 227 /* Nonzero if the second flow pass has completed.  */
 228 int flow2_completed;
 229
 230 /* Maximum register number used in this function, plus one.  */
 231
 232 int max_regno;
 233
 234 /* Indexed by n, giving various register information */
 235
 236 varray_type reg_n_info;
 237
 238 /* Size of a regset for the current function,
 239    in (1) bytes and (2) elements.  */
 240
 241 int regset_bytes;
 242 int regset_size;
 243
 244 /* Regset of regs live when calls to `setjmp'-like functions happen.  */
 245 /* ??? Does this exist only for the setjmp-clobbered warning message?  */
 246
 247 regset regs_live_at_setjmp;
 248
 249 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
 250    that have to go in the same hard reg.
 251    The first two regs in the list are a pair, and the next two
 252    are another pair, etc.  */
 253 rtx regs_may_share;
 254
 255 /* Callback that determines if it's ok for a function to have no
 256    noreturn attribute.  */
 257 int (*lang_missing_noreturn_ok_p) PARAMS ((tree));
 258
 259 /* Set of registers that may be eliminable.  These are handled specially
 260    in updating regs_ever_live.  */
 261
 262 static HARD_REG_SET elim_reg_set;
 263
 264 /* The basic block structure for every insn, indexed by uid.  */
 265
 266 varray_type basic_block_for_insn;
 267
 268 /* The labels mentioned in non-jump rtl.  Valid during find_basic_blocks.  */
 269 /* ??? Should probably be using LABEL_NUSES instead.  It would take a
 270    bit of surgery to be able to use or co-opt the routines in jump.  */
 271
 272 static rtx label_value_list;
 273 static rtx tail_recursion_label_list;
 274
 275 /* Holds information for tracking conditional register life information.  */
 276 struct reg_cond_life_info
 277 {
 278   /* A boolean expression of conditions under which a register is dead.  */
 279   rtx condition;
 280   /* Conditions under which a register is dead at the basic block end.  */
 281   rtx orig_condition;
 282
 283   /* A boolean expression of conditions under which a register has been
 284      stored into.  */
 285   rtx stores;
 286
 287   /* ??? Could store mask of bytes that are dead, so that we could finally
 288      track lifetimes of multi-word registers accessed via subregs.  */
 289 };
 290
 291 /* For use in communicating between propagate_block and its subroutines.
 292    Holds all information needed to compute life and def-use information.  */
 293
 294 struct propagate_block_info
 295 {
 296   /* The basic block we're considering.  */
 297   basic_block bb;
 298
 299   /* Bit N is set if register N is conditionally or unconditionally live.  */
 300   regset reg_live;
 301
 302   /* Bit N is set if register N is set this insn.  */
 303   regset new_set;
 304
 305   /* Element N is the next insn that uses (hard or pseudo) register N
 306      within the current basic block; or zero, if there is no such insn.  */
 307   rtx *reg_next_use;
 308
 309   /* Contains a list of all the MEMs we are tracking for dead store
 310      elimination.  */
 311   rtx mem_set_list;
 312
 313   /* If non-null, record the set of registers set unconditionally in the
 314      basic block.  */
 315   regset local_set;
 316
 317   /* If non-null, record the set of registers set conditionally in the
 318      basic block.  */
 319   regset cond_local_set;
 320
 321 #ifdef HAVE_conditional_execution
 322   /* Indexed by register number, holds a reg_cond_life_info for each
 323      register that is not unconditionally live or dead.  */
 324   splay_tree reg_cond_dead;
 325
 326   /* Bit N is set if register N is in an expression in reg_cond_dead.  */
 327   regset reg_cond_reg;
 328 #endif
 329
 330   /* The length of mem_set_list.  */
 331   int mem_set_list_len;
 332
 333   /* Non-zero if the value of CC0 is live.  */
 334   int cc0_live;
 335
 336   /* Flags controling the set of information propagate_block collects.  */
 337   int flags;
 338 };
 339
 340 /* Maximum length of pbi->mem_set_list before we start dropping
 341    new elements on the floor.  */
 342 #define MAX_MEM_SET_LIST_LEN    100
 343
 344 /* Store the data structures necessary for depth-first search.  */
 345 struct depth_first_search_dsS {
 346   /* stack for backtracking during the algorithm */
 347   basic_block *stack;
 348
 349   /* number of edges in the stack.  That is, positions 0, ..., sp-1
 350      have edges.  */
 351   unsigned int sp;
 352
 353   /* record of basic blocks already seen by depth-first search */
 354   sbitmap visited_blocks;
 355 };
 356 typedef struct depth_first_search_dsS *depth_first_search_ds;
 357
 358 /* Have print_rtl_and_abort give the same information that fancy_abort
 359    does.  */
 360 #define print_rtl_and_abort() \
 361   print_rtl_and_abort_fcn (__FILE__, __LINE__, __FUNCTION__)
 362
 363 /* Forward declarations */
 364 static int count_basic_blocks           PARAMS ((rtx));
 365 static void find_basic_blocks_1         PARAMS ((rtx));
 366 static rtx find_label_refs              PARAMS ((rtx, rtx));
 367 static void make_edges                  PARAMS ((rtx));
 368 static void make_label_edge             PARAMS ((sbitmap *, basic_block,
 369                                                  rtx, int));
 370 static void make_eh_edge                PARAMS ((sbitmap *, basic_block, rtx));
 371
 372 static void commit_one_edge_insertion   PARAMS ((edge));
 373
 374 static void delete_unreachable_blocks   PARAMS ((void));
 375 static int can_delete_note_p            PARAMS ((rtx));
 376 static void expunge_block               PARAMS ((basic_block));
 377 static int can_delete_label_p           PARAMS ((rtx));
 378 static int tail_recursion_label_p       PARAMS ((rtx));
 379 static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
 380                                                           basic_block));
 381 static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
 382                                                         basic_block));
 383 static int merge_blocks                 PARAMS ((edge,basic_block,basic_block));
 384 static bool try_optimize_cfg            PARAMS ((void));
 385 static bool forwarder_block_p           PARAMS ((basic_block));
 386 static bool can_fallthru                PARAMS ((basic_block, basic_block));
 387 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
 388 static bool try_simplify_condjump       PARAMS ((basic_block));
 389 static bool try_forward_edges           PARAMS ((basic_block));
 390 static void tidy_fallthru_edges         PARAMS ((void));
 391 static int verify_wide_reg_1            PARAMS ((rtx *, void *));
 392 static void verify_wide_reg             PARAMS ((int, rtx, rtx));
 393 static void verify_local_live_at_start  PARAMS ((regset, basic_block));
 394 static int noop_move_p                  PARAMS ((rtx));
 395 static void delete_noop_moves           PARAMS ((rtx));
 396 static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
 397 static void notice_stack_pointer_modification PARAMS ((rtx));
 398 static void mark_reg                    PARAMS ((rtx, void *));
 399 static void mark_regs_live_at_end       PARAMS ((regset));
 400 static int set_phi_alternative_reg      PARAMS ((rtx, int, int, void *));
 401 static void calculate_global_regs_live  PARAMS ((sbitmap, sbitmap, int));
 402 static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
 403 static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
 404 static int insn_dead_p                  PARAMS ((struct propagate_block_info *,
 405                                                  rtx, int, rtx));
 406 static int libcall_dead_p               PARAMS ((struct propagate_block_info *,
 407                                                  rtx, rtx));
 408 static void mark_set_regs               PARAMS ((struct propagate_block_info *,
 409                                                  rtx, rtx));
 410 static void mark_set_1                  PARAMS ((struct propagate_block_info *,
 411                                                  enum rtx_code, rtx, rtx,
 412                                                  rtx, int));
 413 #ifdef HAVE_conditional_execution
 414 static int mark_regno_cond_dead         PARAMS ((struct propagate_block_info *,
 415                                                  int, rtx));
 416 static void free_reg_cond_life_info     PARAMS ((splay_tree_value));
 417 static int flush_reg_cond_reg_1         PARAMS ((splay_tree_node, void *));
 418 static void flush_reg_cond_reg          PARAMS ((struct propagate_block_info *,
 419                                                  int));
 420 static rtx elim_reg_cond                PARAMS ((rtx, unsigned int));
 421 static rtx ior_reg_cond                 PARAMS ((rtx, rtx, int));
 422 static rtx not_reg_cond                 PARAMS ((rtx));
 423 static rtx and_reg_cond                 PARAMS ((rtx, rtx, int));
 424 #endif
 425 #ifdef AUTO_INC_DEC
 426 static void attempt_auto_inc            PARAMS ((struct propagate_block_info *,
 427                                                  rtx, rtx, rtx, rtx, rtx));
 428 static void find_auto_inc               PARAMS ((struct propagate_block_info *,
 429                                                  rtx, rtx));
 430 static int try_pre_increment_1          PARAMS ((struct propagate_block_info *,
 431                                                  rtx));
 432 static int try_pre_increment            PARAMS ((rtx, rtx, HOST_WIDE_INT));
 433 #endif
 434 static void mark_used_reg               PARAMS ((struct propagate_block_info *,
 435                                                  rtx, rtx, rtx));
 436 static void mark_used_regs              PARAMS ((struct propagate_block_info *,
 437                                                  rtx, rtx, rtx));
 438 void dump_flow_info                     PARAMS ((FILE *));
 439 void debug_flow_info                    PARAMS ((void));
 440 static void print_rtl_and_abort_fcn     PARAMS ((const char *, int,
 441                                                  const char *))
 442                                         ATTRIBUTE_NORETURN;
 443
 444 static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
 445                                                   rtx));
 446 static void invalidate_mems_from_set    PARAMS ((struct propagate_block_info *,
 447                                                  rtx));
 448 static void remove_fake_successors      PARAMS ((basic_block));
 449 static void flow_nodes_print            PARAMS ((const char *, const sbitmap,
 450                                                  FILE *));
 451 static void flow_edge_list_print        PARAMS ((const char *, const edge *,
 452                                                  int, FILE *));
 453 static void flow_loops_cfg_dump         PARAMS ((const struct loops *,
 454                                                  FILE *));
 455 static int flow_loop_nested_p           PARAMS ((struct loop *,
 456                                                  struct loop *));
 457 static int flow_loop_entry_edges_find   PARAMS ((basic_block, const sbitmap,
 458                                                  edge **));
 459 static int flow_loop_exit_edges_find    PARAMS ((const sbitmap, edge **));
 460 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
 461 static void flow_dfs_compute_reverse_init
 462   PARAMS ((depth_first_search_ds));
 463 static void flow_dfs_compute_reverse_add_bb
 464   PARAMS ((depth_first_search_ds, basic_block));
 465 static basic_block flow_dfs_compute_reverse_execute
 466   PARAMS ((depth_first_search_ds));
 467 static void flow_dfs_compute_reverse_finish
 468   PARAMS ((depth_first_search_ds));
 469 static void flow_loop_pre_header_scan PARAMS ((struct loop *));
 470 static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
 471                                                       const sbitmap *));
 472 static void flow_loop_tree_node_add     PARAMS ((struct loop *, struct loop *));
 473 static void flow_loops_tree_build       PARAMS ((struct loops *));
 474 static int flow_loop_level_compute      PARAMS ((struct loop *, int));
 475 static int flow_loops_level_compute     PARAMS ((struct loops *));
 476 static void allocate_bb_life_data       PARAMS ((void));
 477 static void find_sub_basic_blocks       PARAMS ((basic_block));
 478 static bool redirect_edge_and_branch    PARAMS ((edge, basic_block));
 479 static rtx block_label                  PARAMS ((basic_block));
 480 \f
 481 /* Find basic blocks of the current function.
 482    F is the first insn of the function and NREGS the number of register
 483    numbers in use.  */
 484
 485 void
 486 find_basic_blocks (f, nregs, file)
 487      rtx f;
 488      int nregs ATTRIBUTE_UNUSED;
 489      FILE *file ATTRIBUTE_UNUSED;
 490 {
 491   int max_uid;
 492
 493   /* Flush out existing data.  */
 494   if (basic_block_info != NULL)
 495     {
 496       int i;
 497
 498       clear_edges ();
 499
 500       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 501          tag for reuse during create_basic_block, just in case some pass
 502          copies around basic block notes improperly.  */
 503       for (i = 0; i < n_basic_blocks; ++i)
 504         BASIC_BLOCK (i)->aux = NULL;
 505
 506       VARRAY_FREE (basic_block_info);
 507     }
 508
 509   n_basic_blocks = count_basic_blocks (f);
 510
 511   /* Size the basic block table.  The actual structures will be allocated
 512      by find_basic_blocks_1, since we want to keep the structure pointers
 513      stable across calls to find_basic_blocks.  */
 514   /* ??? This whole issue would be much simpler if we called find_basic_blocks
 515      exactly once, and thereafter we don't have a single long chain of
 516      instructions at all until close to the end of compilation when we
 517      actually lay them out.  */
 518
 519   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 520
 521   find_basic_blocks_1 (f);
 522
 523   /* Record the block to which an insn belongs.  */
 524   /* ??? This should be done another way, by which (perhaps) a label is
 525      tagged directly with the basic block that it starts.  It is used for
 526      more than that currently, but IMO that is the only valid use.  */
 527
 528   max_uid = get_max_uid ();
 529 #ifdef AUTO_INC_DEC
 530   /* Leave space for insns life_analysis makes in some cases for auto-inc.
 531      These cases are rare, so we don't need too much space.  */
 532   max_uid += max_uid / 10;
 533 #endif
 534
 535   compute_bb_for_insn (max_uid);
 536
 537   /* Discover the edges of our cfg.  */
 538   make_edges (label_value_list);
 539
 540   /* Do very simple cleanup now, for the benefit of code that runs between
 541      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 542   tidy_fallthru_edges ();
 543
 544   mark_critical_edges ();
 545
 546 #ifdef ENABLE_CHECKING
 547   verify_flow_info ();
 548 #endif
 549 }
 550
 551 void
 552 check_function_return_warnings ()
 553 {
 554   if (warn_missing_noreturn
 555       && !TREE_THIS_VOLATILE (cfun->decl)
 556       && EXIT_BLOCK_PTR->pred == NULL
 557       && (lang_missing_noreturn_ok_p
 558           && !lang_missing_noreturn_ok_p (cfun->decl)))
 559     warning ("function might be possible candidate for attribute `noreturn'");
 560
 561   /* If we have a path to EXIT, then we do return.  */
 562   if (TREE_THIS_VOLATILE (cfun->decl)
 563       && EXIT_BLOCK_PTR->pred != NULL)
 564     warning ("`noreturn' function does return");
 565
 566   /* If the clobber_return_insn appears in some basic block, then we
 567      do reach the end without returning a value.  */
 568   else if (warn_return_type
 569            && cfun->x_clobber_return_insn != NULL
 570            && EXIT_BLOCK_PTR->pred != NULL)
 571     {
 572       int max_uid = get_max_uid ();
 573
 574       /* If clobber_return_insn was excised by jump1, then renumber_insns
 575          can make max_uid smaller than the number still recorded in our rtx.
 576          That's fine, since this is a quick way of verifying that the insn
 577          is no longer in the chain.  */
 578       if (INSN_UID (cfun->x_clobber_return_insn) < max_uid)
 579         {
 580           /* Recompute insn->block mapping, since the initial mapping is
 581              set before we delete unreachable blocks.  */
 582           compute_bb_for_insn (max_uid);
 583
 584           if (BLOCK_FOR_INSN (cfun->x_clobber_return_insn) != NULL)
 585             warning ("control reaches end of non-void function");
 586         }
 587     }
 588 }
 589
 590 /* Count the basic blocks of the function.  */
 591
 592 static int
 593 count_basic_blocks (f)
 594      rtx f;
 595 {
 596   register rtx insn;
 597   register RTX_CODE prev_code;
 598   register int count = 0;
 599   int saw_abnormal_edge = 0;
 600
 601   prev_code = JUMP_INSN;
 602   for (insn = f; insn; insn = NEXT_INSN (insn))
 603     {
 604       enum rtx_code code = GET_CODE (insn);
 605
 606       if (code == CODE_LABEL
 607           || (GET_RTX_CLASS (code) == 'i'
 608               && (prev_code == JUMP_INSN
 609                   || prev_code == BARRIER
 610                   || saw_abnormal_edge)))
 611         {
 612           saw_abnormal_edge = 0;
 613           count++;
 614         }
 615
 616       /* Record whether this insn created an edge.  */
 617       if (code == CALL_INSN)
 618         {
 619           rtx note;
 620
 621           /* If there is a nonlocal goto label and the specified
 622              region number isn't -1, we have an edge.  */
 623           if (nonlocal_goto_handler_labels
 624               && ((note = find_reg_note (insn, REG_EH_REGION, NULL_RTX)) == 0
 625                   || INTVAL (XEXP (note, 0)) >= 0))
 626             saw_abnormal_edge = 1;
 627
 628           else if (can_throw_internal (insn))
 629             saw_abnormal_edge = 1;
 630         }
 631       else if (flag_non_call_exceptions
 632                && code == INSN
 633                && can_throw_internal (insn))
 634         saw_abnormal_edge = 1;
 635
 636       if (code != NOTE)
 637         prev_code = code;
 638     }
 639
 640   /* The rest of the compiler works a bit smoother when we don't have to
 641      check for the edge case of do-nothing functions with no basic blocks.  */
 642   if (count == 0)
 643     {
 644       emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
 645       count = 1;
 646     }
 647
 648   return count;
 649 }
 650
 651 /* Scan a list of insns for labels referred to other than by jumps.
 652    This is used to scan the alternatives of a call placeholder.  */
 653 static rtx
 654 find_label_refs (f, lvl)
 655      rtx f;
 656      rtx lvl;
 657 {
 658   rtx insn;
 659
 660   for (insn = f; insn; insn = NEXT_INSN (insn))
 661     if (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN)
 662       {
 663         rtx note;
 664
 665         /* Make a list of all labels referred to other than by jumps
 666            (which just don't have the REG_LABEL notes).
 667
 668            Make a special exception for labels followed by an ADDR*VEC,
 669            as this would be a part of the tablejump setup code.
 670
 671            Make a special exception to registers loaded with label
 672            values just before jump insns that use them.  */
 673
 674         for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 675           if (REG_NOTE_KIND (note) == REG_LABEL)
 676             {
 677               rtx lab = XEXP (note, 0), next;
 678
 679               if ((next = next_nonnote_insn (lab)) != NULL
 680                        && GET_CODE (next) == JUMP_INSN
 681                        && (GET_CODE (PATTERN (next)) == ADDR_VEC
 682                            || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
 683                 ;
 684               else if (GET_CODE (lab) == NOTE)
 685                 ;
 686               else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 687                        && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
 688                 ;
 689               else
 690                 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
 691             }
 692       }
 693
 694   return lvl;
 695 }
 696
 697 /* Assume that someone emitted code with control flow instructions to the
 698    basic block.  Update the data structure.  */
 699 static void
 700 find_sub_basic_blocks (bb)
 701      basic_block bb;
 702 {
 703   rtx first_insn = bb->head, insn;
 704   rtx end = bb->end;
 705   edge succ_list = bb->succ;
 706   rtx jump_insn = NULL_RTX;
 707   int created = 0;
 708   int barrier = 0;
 709   edge falltru = 0;
 710   basic_block first_bb = bb, last_bb;
 711   int i;
 712
 713   if (GET_CODE (first_insn) == LABEL_REF)
 714     first_insn = NEXT_INSN (first_insn);
 715   first_insn = NEXT_INSN (first_insn);
 716   bb->succ = NULL;
 717
 718   insn = first_insn;
 719   /* Scan insn chain and try to find new basic block boundaries.  */
 720   while (insn != end)
 721     {
 722       enum rtx_code code = GET_CODE (insn);
 723       switch (code)
 724         {
 725         case JUMP_INSN:
 726           /* We need some special care for those expressions.  */
 727           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 728               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 729             abort();
 730           jump_insn = insn;
 731           break;
 732         case BARRIER:
 733           if (!jump_insn)
 734             abort ();
 735           barrier = 1;
 736           break;
 737         /* On code label, split current basic block.  */
 738         case CODE_LABEL:
 739           falltru = split_block (bb, PREV_INSN (insn));
 740           if (jump_insn)
 741             bb->end = jump_insn;
 742           bb = falltru->dest;
 743           if (barrier)
 744             remove_edge (falltru);
 745           barrier = 0;
 746           jump_insn = 0;
 747           created = 1;
 748           if (LABEL_ALTERNATE_NAME (insn))
 749             make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
 750           break;
 751         case INSN:
 752           /* In case we've previously split insn on the JUMP_INSN, move the
 753              block header to proper place.  */
 754           if (jump_insn)
 755             {
 756               falltru = split_block (bb, PREV_INSN (insn));
 757               bb->end = jump_insn;
 758               bb = falltru->dest;
 759               if (barrier)
 760                 abort ();
 761               jump_insn = 0;
 762             }
 763         default:
 764           break;
 765         }
 766       insn = NEXT_INSN (insn);
 767     }
 768   /* Last basic block must end in the original BB end.  */
 769   if (jump_insn)
 770     abort ();
 771
 772   /* Wire in the original edges for last basic block.  */
 773   if (created)
 774     {
 775       bb->succ = succ_list;
 776       while (succ_list)
 777         succ_list->src = bb, succ_list = succ_list->succ_next;
 778     }
 779   else
 780     bb->succ = succ_list;
 781
 782   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 783      jumps at the end of each new basic blocks.  */
 784   last_bb = bb;
 785   for (i = first_bb->index; i < last_bb->index; i++)
 786     {
 787       bb = BASIC_BLOCK (i);
 788       if (GET_CODE (bb->end) == JUMP_INSN)
 789         {
 790           mark_jump_label (PATTERN (bb->end), bb->end, 0, 0);
 791           make_label_edge (NULL, bb, JUMP_LABEL (bb->end), 0);
 792         }
 793       insn = NEXT_INSN (insn);
 794     }
 795 }
 796
 797 /* Find all basic blocks of the function whose first insn is F.
 798
 799    Collect and return a list of labels whose addresses are taken.  This
 800    will be used in make_edges for use with computed gotos.  */
 801
 802 static void
 803 find_basic_blocks_1 (f)
 804      rtx f;
 805 {
 806   register rtx insn, next;
 807   int i = 0;
 808   rtx bb_note = NULL_RTX;
 809   rtx lvl = NULL_RTX;
 810   rtx trll = NULL_RTX;
 811   rtx head = NULL_RTX;
 812   rtx end = NULL_RTX;
 813
 814   /* We process the instructions in a slightly different way than we did
 815      previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
 816      closed out the previous block, so that it gets attached at the proper
 817      place.  Since this form should be equivalent to the previous,
 818      count_basic_blocks continues to use the old form as a check.  */
 819
 820   for (insn = f; insn; insn = next)
 821     {
 822       enum rtx_code code = GET_CODE (insn);
 823
 824       next = NEXT_INSN (insn);
 825
 826       switch (code)
 827         {
 828         case NOTE:
 829           {
 830             int kind = NOTE_LINE_NUMBER (insn);
 831
 832             /* Look for basic block notes with which to keep the
 833                basic_block_info pointers stable.  Unthread the note now;
 834                we'll put it back at the right place in create_basic_block.
 835                Or not at all if we've already found a note in this block.  */
 836             if (kind == NOTE_INSN_BASIC_BLOCK)
 837               {
 838                 if (bb_note == NULL_RTX)
 839                   bb_note = insn;
 840                 else
 841                   next = flow_delete_insn (insn);
 842               }
 843             break;
 844           }
 845
 846         case CODE_LABEL:
 847           /* A basic block starts at a label.  If we've closed one off due
 848              to a barrier or some such, no need to do it again.  */
 849           if (head != NULL_RTX)
 850             {
 851               /* While we now have edge lists with which other portions of
 852                  the compiler might determine a call ending a basic block
 853                  does not imply an abnormal edge, it will be a bit before
 854                  everything can be updated.  So continue to emit a noop at
 855                  the end of such a block.  */
 856               if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
 857                 {
 858                   rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
 859                   end = emit_insn_after (nop, end);
 860                 }
 861
 862               create_basic_block (i++, head, end, bb_note);
 863               bb_note = NULL_RTX;
 864             }
 865
 866           head = end = insn;
 867           break;
 868
 869         case JUMP_INSN:
 870           /* A basic block ends at a jump.  */
 871           if (head == NULL_RTX)
 872             head = insn;
 873           else
 874             {
 875               /* ??? Make a special check for table jumps.  The way this
 876                  happens is truly and amazingly gross.  We are about to
 877                  create a basic block that contains just a code label and
 878                  an addr*vec jump insn.  Worse, an addr_diff_vec creates
 879                  its own natural loop.
 880
 881                  Prevent this bit of brain damage, pasting things together
 882                  correctly in make_edges.
 883
 884                  The correct solution involves emitting the table directly
 885                  on the tablejump instruction as a note, or JUMP_LABEL.  */
 886
 887               if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 888                   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 889                 {
 890                   head = end = NULL;
 891                   n_basic_blocks--;
 892                   break;
 893                 }
 894             }
 895           end = insn;
 896           goto new_bb_inclusive;
 897
 898         case BARRIER:
 899           /* A basic block ends at a barrier.  It may be that an unconditional
 900              jump already closed the basic block -- no need to do it again.  */
 901           if (head == NULL_RTX)
 902             break;
 903
 904           /* While we now have edge lists with which other portions of the
 905              compiler might determine a call ending a basic block does not
 906              imply an abnormal edge, it will be a bit before everything can
 907              be updated.  So continue to emit a noop at the end of such a
 908              block.  */
 909           if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
 910             {
 911               rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
 912               end = emit_insn_after (nop, end);
 913             }
 914           goto new_bb_exclusive;
 915
 916         case CALL_INSN:
 917           {
 918             /* Record whether this call created an edge.  */
 919             rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
 920             int region = (note ? INTVAL (XEXP (note, 0)) : 0);
 921
 922             if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 923               {
 924                 /* Scan each of the alternatives for label refs.  */
 925                 lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
 926                 lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
 927                 lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
 928                 /* Record its tail recursion label, if any.  */
 929                 if (XEXP (PATTERN (insn), 3) != NULL_RTX)
 930                   trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
 931               }
 932
 933             /* A basic block ends at a call that can either throw or
 934                do a non-local goto.  */
 935             if ((nonlocal_goto_handler_labels && region >= 0)
 936                 || can_throw_internal (insn))
 937               {
 938               new_bb_inclusive:
 939                 if (head == NULL_RTX)
 940                   head = insn;
 941                 end = insn;
 942
 943               new_bb_exclusive:
 944                 create_basic_block (i++, head, end, bb_note);
 945                 head = end = NULL_RTX;
 946                 bb_note = NULL_RTX;
 947                 break;
 948               }
 949           }
 950           /* Fall through.  */
 951
 952         case INSN:
 953           /* Non-call exceptions generate new blocks just like calls.  */
 954           if (flag_non_call_exceptions && can_throw_internal (insn))
 955             goto new_bb_inclusive;
 956
 957           if (head == NULL_RTX)
 958             head = insn;
 959           end = insn;
 960           break;
 961
 962         default:
 963           abort ();
 964         }
 965
 966       if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
 967         {
 968           rtx note;
 969
 970           /* Make a list of all labels referred to other than by jumps.
 971
 972              Make a special exception for labels followed by an ADDR*VEC,
 973              as this would be a part of the tablejump setup code.
 974
 975              Make a special exception to registers loaded with label
 976              values just before jump insns that use them.  */
 977
 978           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 979             if (REG_NOTE_KIND (note) == REG_LABEL)
 980               {
 981                 rtx lab = XEXP (note, 0), next;
 982
 983                 if ((next = next_nonnote_insn (lab)) != NULL
 984                          && GET_CODE (next) == JUMP_INSN
 985                          && (GET_CODE (PATTERN (next)) == ADDR_VEC
 986                              || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
 987                   ;
 988                 else if (GET_CODE (lab) == NOTE)
 989                   ;
 990                 else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 991                          && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
 992                   ;
 993                 else
 994                   lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
 995               }
 996         }
 997     }
 998
 999   if (head != NULL_RTX)
1000     create_basic_block (i++, head, end, bb_note);
1001   else if (bb_note)
1002     flow_delete_insn (bb_note);
1003
1004   if (i != n_basic_blocks)
1005     abort ();
1006
1007   label_value_list = lvl;
1008   tail_recursion_label_list = trll;
1009 }
1010
1011 /* Tidy the CFG by deleting unreachable code and whatnot.  */
1012
1013 void
1014 cleanup_cfg ()
1015 {
1016   delete_unreachable_blocks ();
1017   if (try_optimize_cfg ())
1018     delete_unreachable_blocks ();
1019   mark_critical_edges ();
1020
1021   /* Kill the data we won't maintain.  */
1022   free_EXPR_LIST_list (&label_value_list);
1023   free_EXPR_LIST_list (&tail_recursion_label_list);
1024 }
1025
1026 /* Create a new basic block consisting of the instructions between
1027    HEAD and END inclusive.  Reuses the note and basic block struct
1028    in BB_NOTE, if any.  */
1029
1030 void
1031 create_basic_block (index, head, end, bb_note)
1032      int index;
1033      rtx head, end, bb_note;
1034 {
1035   basic_block bb;
1036
1037   if (bb_note
1038       && ! RTX_INTEGRATED_P (bb_note)
1039       && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
1040       && bb->aux == NULL)
1041     {
1042       /* If we found an existing note, thread it back onto the chain.  */
1043
1044       rtx after;
1045
1046       if (GET_CODE (head) == CODE_LABEL)
1047         after = head;
1048       else
1049         {
1050           after = PREV_INSN (head);
1051           head = bb_note;
1052         }
1053
1054       if (after != bb_note && NEXT_INSN (after) != bb_note)
1055         reorder_insns (bb_note, bb_note, after);
1056     }
1057   else
1058     {
1059       /* Otherwise we must create a note and a basic block structure.
1060          Since we allow basic block structs in rtl, give the struct
1061          the same lifetime by allocating it off the function obstack
1062          rather than using malloc.  */
1063
1064       bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
1065       memset (bb, 0, sizeof (*bb));
1066
1067       if (GET_CODE (head) == CODE_LABEL)
1068         bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
1069       else
1070         {
1071           bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
1072           head = bb_note;
1073         }
1074       NOTE_BASIC_BLOCK (bb_note) = bb;
1075     }
1076
1077   /* Always include the bb note in the block.  */
1078   if (NEXT_INSN (end) == bb_note)
1079     end = bb_note;
1080
1081   bb->head = head;
1082   bb->end = end;
1083   bb->index = index;
1084   BASIC_BLOCK (index) = bb;
1085
1086   /* Tag the block so that we know it has been used when considering
1087      other basic block notes.  */
1088   bb->aux = bb;
1089 }
1090 \f
1091 /* Records the basic block struct in BB_FOR_INSN, for every instruction
1092    indexed by INSN_UID.  MAX is the size of the array.  */
1093
1094 void
1095 compute_bb_for_insn (max)
1096      int max;
1097 {
1098   int i;
1099
1100   if (basic_block_for_insn)
1101     VARRAY_FREE (basic_block_for_insn);
1102   VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
1103
1104   for (i = 0; i < n_basic_blocks; ++i)
1105     {
1106       basic_block bb = BASIC_BLOCK (i);
1107       rtx insn, end;
1108
1109       end = bb->end;
1110       insn = bb->head;
1111       while (1)
1112         {
1113           int uid = INSN_UID (insn);
1114           if (uid < max)
1115             VARRAY_BB (basic_block_for_insn, uid) = bb;
1116           if (insn == end)
1117             break;
1118           insn = NEXT_INSN (insn);
1119         }
1120     }
1121 }
1122
1123 /* Free the memory associated with the edge structures.  */
1124
1125 void
1126 clear_edges ()
1127 {
1128   int i;
1129   edge n, e;
1130
1131   for (i = 0; i < n_basic_blocks; ++i)
1132     {
1133       basic_block bb = BASIC_BLOCK (i);
1134
1135       for (e = bb->succ; e; e = n)
1136         {
1137           n = e->succ_next;
1138           free (e);
1139         }
1140
1141       bb->succ = 0;
1142       bb->pred = 0;
1143     }
1144
1145   for (e = ENTRY_BLOCK_PTR->succ; e; e = n)
1146     {
1147       n = e->succ_next;
1148       free (e);
1149     }
1150
1151   ENTRY_BLOCK_PTR->succ = 0;
1152   EXIT_BLOCK_PTR->pred = 0;
1153
1154   n_edges = 0;
1155 }
1156
1157 /* Identify the edges between basic blocks.
1158
1159    NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
1160    that are otherwise unreachable may be reachable with a non-local goto.
1161
1162    BB_EH_END is an array indexed by basic block number in which we record
1163    the list of exception regions active at the end of the basic block.  */
1164
1165 static void
1166 make_edges (label_value_list)
1167      rtx label_value_list;
1168 {
1169   int i;
1170   sbitmap *edge_cache = NULL;
1171
1172   /* Assume no computed jump; revise as we create edges.  */
1173   current_function_has_computed_jump = 0;
1174
1175   /* Heavy use of computed goto in machine-generated code can lead to
1176      nearly fully-connected CFGs.  In that case we spend a significant
1177      amount of time searching the edge lists for duplicates.  */
1178   if (forced_labels || label_value_list)
1179     {
1180       edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
1181       sbitmap_vector_zero (edge_cache, n_basic_blocks);
1182     }
1183
1184   /* By nature of the way these get numbered, block 0 is always the entry.  */
1185   make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
1186
1187   for (i = 0; i < n_basic_blocks; ++i)
1188     {
1189       basic_block bb = BASIC_BLOCK (i);
1190       rtx insn, x;
1191       enum rtx_code code;
1192       int force_fallthru = 0;
1193
1194       if (GET_CODE (bb->head) == CODE_LABEL
1195           && LABEL_ALTERNATE_NAME (bb->head))
1196         make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
1197
1198       /* Examine the last instruction of the block, and discover the
1199          ways we can leave the block.  */
1200
1201       insn = bb->end;
1202       code = GET_CODE (insn);
1203
1204       /* A branch.  */
1205       if (code == JUMP_INSN)
1206         {
1207           rtx tmp;
1208
1209           /* Recognize exception handling placeholders.  */
1210           if (GET_CODE (PATTERN (insn)) == RESX)
1211             make_eh_edge (edge_cache, bb, insn);
1212
1213           /* Recognize a non-local goto as a branch outside the
1214              current function.  */
1215           else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
1216             ;
1217
1218           /* ??? Recognize a tablejump and do the right thing.  */
1219           else if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1220                    && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1221                    && GET_CODE (tmp) == JUMP_INSN
1222                    && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1223                        || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1224             {
1225               rtvec vec;
1226               int j;
1227
1228               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1229                 vec = XVEC (PATTERN (tmp), 0);
1230               else
1231                 vec = XVEC (PATTERN (tmp), 1);
1232
1233               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1234                 make_label_edge (edge_cache, bb,
1235                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
1236
1237               /* Some targets (eg, ARM) emit a conditional jump that also
1238                  contains the out-of-range target.  Scan for these and
1239                  add an edge if necessary.  */
1240               if ((tmp = single_set (insn)) != NULL
1241                   && SET_DEST (tmp) == pc_rtx
1242                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1243                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
1244                 make_label_edge (edge_cache, bb,
1245                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
1246
1247 #ifdef CASE_DROPS_THROUGH
1248               /* Silly VAXen.  The ADDR_VEC is going to be in the way of
1249                  us naturally detecting fallthru into the next block.  */
1250               force_fallthru = 1;
1251 #endif
1252             }
1253
1254           /* If this is a computed jump, then mark it as reaching
1255              everything on the label_value_list and forced_labels list.  */
1256           else if (computed_jump_p (insn))
1257             {
1258               current_function_has_computed_jump = 1;
1259
1260               for (x = label_value_list; x; x = XEXP (x, 1))
1261                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1262
1263               for (x = forced_labels; x; x = XEXP (x, 1))
1264                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1265             }
1266
1267           /* Returns create an exit out.  */
1268           else if (returnjump_p (insn))
1269             make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
1270
1271           /* Otherwise, we have a plain conditional or unconditional jump.  */
1272           else
1273             {
1274               if (! JUMP_LABEL (insn))
1275                 abort ();
1276               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
1277             }
1278         }
1279
1280       /* If this is a sibling call insn, then this is in effect a
1281          combined call and return, and so we need an edge to the
1282          exit block.  No need to worry about EH edges, since we
1283          wouldn't have created the sibling call in the first place.  */
1284
1285       if (code == CALL_INSN && SIBLING_CALL_P (insn))
1286         make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
1287                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1288
1289       /* If this is a CALL_INSN, then mark it as reaching the active EH
1290          handler for this CALL_INSN.  If we're handling non-call
1291          exceptions then any insn can reach any of the active handlers.
1292
1293          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
1294
1295       else if (code == CALL_INSN || flag_non_call_exceptions)
1296         {
1297           /* Add any appropriate EH edges.  */
1298           make_eh_edge (edge_cache, bb, insn);
1299
1300           if (code == CALL_INSN && nonlocal_goto_handler_labels)
1301             {
1302               /* ??? This could be made smarter: in some cases it's possible
1303                  to tell that certain calls will not do a nonlocal goto.
1304
1305                  For example, if the nested functions that do the nonlocal
1306                  gotos do not have their addresses taken, then only calls to
1307                  those functions or to other nested functions that use them
1308                  could possibly do nonlocal gotos.  */
1309               /* We do know that a REG_EH_REGION note with a value less
1310                  than 0 is guaranteed not to perform a non-local goto.  */
1311               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1312               if (!note || INTVAL (XEXP (note, 0)) >=  0)
1313                 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
1314                   make_label_edge (edge_cache, bb, XEXP (x, 0),
1315                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1316             }
1317         }
1318
1319       /* Find out if we can drop through to the next block.  */
1320       insn = next_nonnote_insn (insn);
1321       if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
1322         make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1323       else if (i + 1 < n_basic_blocks)
1324         {
1325           rtx tmp = BLOCK_HEAD (i + 1);
1326           if (GET_CODE (tmp) == NOTE)
1327             tmp = next_nonnote_insn (tmp);
1328           if (force_fallthru || insn == tmp)
1329             make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
1330         }
1331     }
1332
1333   if (edge_cache)
1334     sbitmap_vector_free (edge_cache);
1335 }
1336
1337 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
1338    about the edge that is accumulated between calls.  */
1339
1340 void
1341 make_edge (edge_cache, src, dst, flags)
1342      sbitmap *edge_cache;
1343      basic_block src, dst;
1344      int flags;
1345 {
1346   int use_edge_cache;
1347   edge e;
1348
1349   /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1350      many edges to them, and we didn't allocate memory for it.  */
1351   use_edge_cache = (edge_cache
1352                     && src != ENTRY_BLOCK_PTR
1353                     && dst != EXIT_BLOCK_PTR);
1354
1355   /* Make sure we don't add duplicate edges.  */
1356   switch (use_edge_cache)
1357     {
1358     default:
1359       /* Quick test for non-existance of the edge.  */
1360       if (! TEST_BIT (edge_cache[src->index], dst->index))
1361         break;
1362
1363       /* The edge exists; early exit if no work to do.  */
1364       if (flags == 0)
1365         return;
1366
1367       /* FALLTHRU */
1368     case 0:
1369       for (e = src->succ; e; e = e->succ_next)
1370         if (e->dest == dst)
1371           {
1372             e->flags |= flags;
1373             return;
1374           }
1375       break;
1376     }
1377
1378   e = (edge) xcalloc (1, sizeof (*e));
1379   n_edges++;
1380
1381   e->succ_next = src->succ;
1382   e->pred_next = dst->pred;
1383   e->src = src;
1384   e->dest = dst;
1385   e->flags = flags;
1386
1387   src->succ = e;
1388   dst->pred = e;
1389
1390   if (use_edge_cache)
1391     SET_BIT (edge_cache[src->index], dst->index);
1392 }
1393
1394 /* Create an edge from a basic block to a label.  */
1395
1396 static void
1397 make_label_edge (edge_cache, src, label, flags)
1398      sbitmap *edge_cache;
1399      basic_block src;
1400      rtx label;
1401      int flags;
1402 {
1403   if (GET_CODE (label) != CODE_LABEL)
1404     abort ();
1405
1406   /* If the label was never emitted, this insn is junk, but avoid a
1407      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
1408      as a result of a syntax error and a diagnostic has already been
1409      printed.  */
1410
1411   if (INSN_UID (label) == 0)
1412     return;
1413
1414   make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
1415 }
1416
1417 /* Create the edges generated by INSN in REGION.  */
1418
1419 static void
1420 make_eh_edge (edge_cache, src, insn)
1421      sbitmap *edge_cache;
1422      basic_block src;
1423      rtx insn;
1424 {
1425   int is_call = (GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
1426   rtx handlers, i;
1427
1428   handlers = reachable_handlers (insn);
1429
1430   for (i = handlers; i; i = XEXP (i, 1))
1431     make_label_edge (edge_cache, src, XEXP (i, 0),
1432                      EDGE_ABNORMAL | EDGE_EH | is_call);
1433
1434   free_INSN_LIST_list (&handlers);
1435 }
1436
1437 /* Identify critical edges and set the bits appropriately.  */
1438
1439 void
1440 mark_critical_edges ()
1441 {
1442   int i, n = n_basic_blocks;
1443   basic_block bb;
1444
1445   /* We begin with the entry block.  This is not terribly important now,
1446      but could be if a front end (Fortran) implemented alternate entry
1447      points.  */
1448   bb = ENTRY_BLOCK_PTR;
1449   i = -1;
1450
1451   while (1)
1452     {
1453       edge e;
1454
1455       /* (1) Critical edges must have a source with multiple successors.  */
1456       if (bb->succ && bb->succ->succ_next)
1457         {
1458           for (e = bb->succ; e; e = e->succ_next)
1459             {
1460               /* (2) Critical edges must have a destination with multiple
1461                  predecessors.  Note that we know there is at least one
1462                  predecessor -- the edge we followed to get here.  */
1463               if (e->dest->pred->pred_next)
1464                 e->flags |= EDGE_CRITICAL;
1465               else
1466                 e->flags &= ~EDGE_CRITICAL;
1467             }
1468         }
1469       else
1470         {
1471           for (e = bb->succ; e; e = e->succ_next)
1472             e->flags &= ~EDGE_CRITICAL;
1473         }
1474
1475       if (++i >= n)
1476         break;
1477       bb = BASIC_BLOCK (i);
1478     }
1479 }
1480 \f
1481 /* Split a block BB after insn INSN creating a new fallthru edge.
1482    Return the new edge.  Note that to keep other parts of the compiler happy,
1483    this function renumbers all the basic blocks so that the new
1484    one has a number one greater than the block split.  */
1485
1486 edge
1487 split_block (bb, insn)
1488      basic_block bb;
1489      rtx insn;
1490 {
1491   basic_block new_bb;
1492   edge new_edge;
1493   edge e;
1494   rtx bb_note;
1495   int i, j;
1496
1497   /* There is no point splitting the block after its end.  */
1498   if (bb->end == insn)
1499     return 0;
1500
1501   /* Create the new structures.  */
1502   new_bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*new_bb));
1503   new_edge = (edge) xcalloc (1, sizeof (*new_edge));
1504   n_edges++;
1505
1506   memset (new_bb, 0, sizeof (*new_bb));
1507
1508   new_bb->head = NEXT_INSN (insn);
1509   new_bb->end = bb->end;
1510   bb->end = insn;
1511
1512   new_bb->succ = bb->succ;
1513   bb->succ = new_edge;
1514   new_bb->pred = new_edge;
1515   new_bb->count = bb->count;
1516   new_bb->frequency = bb->frequency;
1517   new_bb->loop_depth = bb->loop_depth;
1518
1519   new_edge->src = bb;
1520   new_edge->dest = new_bb;
1521   new_edge->flags = EDGE_FALLTHRU;
1522   new_edge->probability = REG_BR_PROB_BASE;
1523   new_edge->count = bb->count;
1524
1525   /* Redirect the src of the successor edges of bb to point to new_bb.  */
1526   for (e = new_bb->succ; e; e = e->succ_next)
1527     e->src = new_bb;
1528
1529   /* Place the new block just after the block being split.  */
1530   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1531
1532   /* Some parts of the compiler expect blocks to be number in
1533      sequential order so insert the new block immediately after the
1534      block being split..  */
1535   j = bb->index;
1536   for (i = n_basic_blocks - 1; i > j + 1; --i)
1537     {
1538       basic_block tmp = BASIC_BLOCK (i - 1);
1539       BASIC_BLOCK (i) = tmp;
1540       tmp->index = i;
1541     }
1542
1543   BASIC_BLOCK (i) = new_bb;
1544   new_bb->index = i;
1545
1546   if (GET_CODE (new_bb->head) == CODE_LABEL)
1547     {
1548       /* Create the basic block note.  */
1549       bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK,
1550                                  new_bb->head);
1551       NOTE_BASIC_BLOCK (bb_note) = new_bb;
1552     }
1553   else
1554     {
1555       /* Create the basic block note.  */
1556       bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1557                                   new_bb->head);
1558       NOTE_BASIC_BLOCK (bb_note) = new_bb;
1559       new_bb->head = bb_note;
1560     }
1561
1562   update_bb_for_insn (new_bb);
1563
1564   if (bb->global_live_at_start)
1565     {
1566       new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1567       new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1568       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
1569
1570       /* We now have to calculate which registers are live at the end
1571          of the split basic block and at the start of the new basic
1572          block.  Start with those registers that are known to be live
1573          at the end of the original basic block and get
1574          propagate_block to determine which registers are live.  */
1575       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
1576       propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
1577       COPY_REG_SET (bb->global_live_at_end,
1578                     new_bb->global_live_at_start);
1579     }
1580
1581   return new_edge;
1582 }
1583
1584 /* Return label in the head of basic block.  Create one if it doesn't exist.  */
1585 static rtx
1586 block_label (block)
1587      basic_block block;
1588 {
1589   if (GET_CODE (block->head) != CODE_LABEL)
1590     block->head = emit_label_before (gen_label_rtx (), block->head);
1591   return block->head;
1592 }
1593
1594 /* Return true if the block has no effect and only forwards control flow to
1595    its single destination.  */
1596 static bool
1597 forwarder_block_p (bb)
1598      basic_block bb;
1599 {
1600   rtx insn = bb->head;
1601   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
1602       || !bb->succ || bb->succ->succ_next)
1603     return false;
1604
1605   while (insn != bb->end)
1606     {
1607       if (active_insn_p (insn))
1608         return false;
1609       insn = NEXT_INSN (insn);
1610     }
1611   return (!active_insn_p (insn)
1612           || (GET_CODE (insn) == JUMP_INSN && onlyjump_p (insn)));
1613 }
1614
1615 /* Return nonzero if we can reach target from src by falling trought.  */
1616 static bool
1617 can_fallthru (src, target)
1618      basic_block src, target;
1619 {
1620   rtx insn = src->end;
1621   rtx insn2 = target->head;
1622
1623   if (!active_insn_p (insn2))
1624     insn2 = next_active_insn (insn2);
1625   /* ??? Later we may add code to move jump tables offline.  */
1626   return next_active_insn (insn) == insn2;
1627 }
1628
1629 /* Attempt to perform edge redirection by replacing possibly complex jump
1630    instruction by unconditional jump or removing jump completely.
1631    This can apply only if all edges now point to the same block.
1632
1633    The parameters and return values are equivalent to redirect_edge_and_branch.
1634  */
1635 static bool
1636 try_redirect_by_replacing_jump (e, target)
1637      edge e;
1638      basic_block target;
1639 {
1640   basic_block src = e->src;
1641   rtx insn = src->end;
1642   edge tmp;
1643   rtx set;
1644   int fallthru = 0;
1645   rtx barrier;
1646
1647   /* Verify that all targets will be TARGET.  */
1648   for (tmp = src->succ; tmp; tmp = tmp->succ_next)
1649     if (tmp->dest != target && tmp != e)
1650       break;
1651   if (tmp || GET_CODE (insn) != JUMP_INSN)
1652     return false;
1653
1654   /* Avoid removing branch with side effects.  */
1655   set = single_set (insn);
1656   if (!set || side_effects_p (set))
1657     return false;
1658
1659   /* See if we can create the fallthru edge.  */
1660   if (can_fallthru (src, target))
1661     {
1662       src->end = PREV_INSN (insn);
1663       if (rtl_dump_file)
1664         fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
1665       flow_delete_insn (insn);
1666       fallthru = 1;
1667       insn = src->end;
1668     }
1669   /* If this already is simplejump, redirect it.  */
1670   else if (simplejump_p (insn))
1671     {
1672       if (e->dest == target)
1673         return false;
1674       if (rtl_dump_file)
1675         fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
1676                  INSN_UID (insn), e->dest->index, target->index);
1677       redirect_jump (insn, block_label (target), 0);
1678     }
1679   /* Or replace possibly complicated jump insn by simple jump insn.  */
1680   else
1681     {
1682       rtx target_label = block_label (target);
1683
1684       src->end = PREV_INSN (insn);
1685       src->end = emit_jump_insn_after (gen_jump (target_label), src->end);
1686       JUMP_LABEL (src->end) = target_label;
1687       LABEL_NUSES (target_label)++;
1688       if (rtl_dump_file)
1689         fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
1690                  INSN_UID (insn), INSN_UID (src->end));
1691       flow_delete_insn (insn);
1692       insn = src->end;
1693     }
1694
1695   /* Keep only one edge out and set proper flags.  */
1696   while (src->succ->succ_next)
1697     remove_edge (src->succ);
1698   e = src->succ;
1699   if (fallthru)
1700     e->flags = EDGE_FALLTHRU;
1701   else
1702     e->flags = 0;
1703   e->probability = REG_BR_PROB_BASE;
1704   e->count = src->count;
1705
1706   /* Fixup barriers.  */
1707   barrier = next_nonnote_insn (insn);
1708   if (fallthru && GET_CODE (barrier) == BARRIER)
1709     flow_delete_insn (barrier);
1710   else if (!fallthru && GET_CODE (barrier) != BARRIER)
1711     emit_barrier_after (insn);
1712
1713   /* In case we've zapped an conditional jump, we need to kill the cc0
1714      setter too if available.  */
1715 #ifdef HAVE_cc0
1716   insn = src->end;
1717   if (GET_CODE (insn) == JUMP_INSN)
1718     insn = prev_nonnote_insn (insn);
1719   if (sets_cc0_p (insn))
1720     {
1721       if (insn == src->end)
1722         src->end = PREV_INSN (insn);
1723       flow_delete_insn (insn);
1724     }
1725 #endif
1726
1727   if (e->dest != target)
1728     redirect_edge_succ (e, target);
1729   return true;
1730 }
1731
1732 /* Attempt to change code to redirect edge E to TARGET.
1733    Don't do that on expense of adding new instructions or reordering
1734    basic blocks.
1735
1736    Function can be also called with edge destionation equivalent to the
1737    TARGET.  Then it should try the simplifications and do nothing if
1738    none is possible.
1739
1740    Return true if transformation suceeded.  We still return flase in case
1741    E already destinated TARGET and we didn't managed to simplify instruction
1742    stream.  */
1743 static bool
1744 redirect_edge_and_branch (e, target)
1745      edge e;
1746      basic_block target;
1747 {
1748   rtx tmp;
1749   rtx old_label = e->dest->head;
1750   basic_block src = e->src;
1751   rtx insn = src->end;
1752
1753   if (try_redirect_by_replacing_jump (e, target))
1754     return true;
1755   /* Do this fast path late, as we want above code to simplify for cases
1756      where called on single edge leaving basic block containing nontrivial
1757      jump insn.  */
1758   else if (e->dest == target)
1759     return false;
1760
1761   /* We can only redirect non-fallthru edges of jump insn.  */
1762   if (e->flags & EDGE_FALLTHRU)
1763     return false;
1764   if (GET_CODE (insn) != JUMP_INSN)
1765     return false;
1766
1767   /* Recognize a tablejump and adjust all matching cases.  */
1768   if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1769       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1770       && GET_CODE (tmp) == JUMP_INSN
1771       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1772           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1773     {
1774       rtvec vec;
1775       int j;
1776       rtx new_label = block_label (target);
1777
1778       if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1779         vec = XVEC (PATTERN (tmp), 0);
1780       else
1781         vec = XVEC (PATTERN (tmp), 1);
1782
1783       for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1784         if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1785           {
1786             RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1787             --LABEL_NUSES (old_label);
1788             ++LABEL_NUSES (new_label);
1789           }
1790
1791       /* Handle casesi dispatch insns */
1792       if ((tmp = single_set (insn)) != NULL
1793           && SET_DEST (tmp) == pc_rtx
1794           && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1795           && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1796           && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1797         {
1798           XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
1799                                                        new_label);
1800           --LABEL_NUSES (old_label);
1801           ++LABEL_NUSES (new_label);
1802         }
1803     }
1804   else
1805     {
1806       /* ?? We may play the games with moving the named labels from
1807          one basic block to the other in case only one computed_jump is
1808          available.  */
1809       if (computed_jump_p (insn))
1810         return false;
1811
1812       /* A return instruction can't be redirected.  */
1813       if (returnjump_p (insn))
1814         return false;
1815
1816       /* If the insn doesn't go where we think, we're confused.  */
1817       if (JUMP_LABEL (insn) != old_label)
1818         abort ();
1819       redirect_jump (insn, block_label (target), 0);
1820     }
1821
1822   if (rtl_dump_file)
1823     fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
1824              e->src->index, e->dest->index, target->index);
1825   if (e->dest != target)
1826     {
1827       edge s;
1828       /* Check whether the edge is already present.  */
1829       for (s = src->succ; s; s=s->succ_next)
1830         if (s->dest == target)
1831           break;
1832       if (s)
1833         {
1834           s->flags |= e->flags;
1835           s->probability += e->probability;
1836           s->count += e->count;
1837           remove_edge (e);
1838         }
1839       else
1840         redirect_edge_succ (e, target);
1841     }
1842   return true;
1843 }
1844
1845 /* Split a (typically critical) edge.  Return the new block.
1846    Abort on abnormal edges.
1847
1848    ??? The code generally expects to be called on critical edges.
1849    The case of a block ending in an unconditional jump to a
1850    block with multiple predecessors is not handled optimally.  */
1851
1852 basic_block
1853 split_edge (edge_in)
1854      edge edge_in;
1855 {
1856   basic_block old_pred, bb, old_succ;
1857   edge edge_out;
1858   rtx bb_note;
1859   int i, j;
1860
1861   /* Abnormal edges cannot be split.  */
1862   if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1863     abort ();
1864
1865   old_pred = edge_in->src;
1866   old_succ = edge_in->dest;
1867
1868   /* Create the new structures.  */
1869   bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
1870   edge_out = (edge) xcalloc (1, sizeof (*edge_out));
1871   n_edges++;
1872
1873   memset (bb, 0, sizeof (*bb));
1874
1875   /* ??? This info is likely going to be out of date very soon.  */
1876   if (old_succ->global_live_at_start)
1877     {
1878       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1879       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1880       COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
1881       COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
1882     }
1883
1884   /* Wire them up.  */
1885   bb->succ = edge_out;
1886   bb->count = edge_in->count;
1887   bb->frequency = (edge_in->probability * edge_in->src->frequency
1888                    / REG_BR_PROB_BASE);
1889
1890   edge_in->flags &= ~EDGE_CRITICAL;
1891
1892   edge_out->pred_next = old_succ->pred;
1893   edge_out->succ_next = NULL;
1894   edge_out->src = bb;
1895   edge_out->dest = old_succ;
1896   edge_out->flags = EDGE_FALLTHRU;
1897   edge_out->probability = REG_BR_PROB_BASE;
1898   edge_out->count = edge_in->count;
1899
1900   old_succ->pred = edge_out;
1901
1902   /* Tricky case -- if there existed a fallthru into the successor
1903      (and we're not it) we must add a new unconditional jump around
1904      the new block we're actually interested in.
1905
1906      Further, if that edge is critical, this means a second new basic
1907      block must be created to hold it.  In order to simplify correct
1908      insn placement, do this before we touch the existing basic block
1909      ordering for the block we were really wanting.  */
1910   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1911     {
1912       edge e;
1913       for (e = edge_out->pred_next; e; e = e->pred_next)
1914         if (e->flags & EDGE_FALLTHRU)
1915           break;
1916
1917       if (e)
1918         {
1919           basic_block jump_block;
1920           rtx pos;
1921
1922           if ((e->flags & EDGE_CRITICAL) == 0
1923               && e->src != ENTRY_BLOCK_PTR)
1924             {
1925               /* Non critical -- we can simply add a jump to the end
1926                  of the existing predecessor.  */
1927               jump_block = e->src;
1928             }
1929           else
1930             {
1931               /* We need a new block to hold the jump.  The simplest
1932                  way to do the bulk of the work here is to recursively
1933                  call ourselves.  */
1934               jump_block = split_edge (e);
1935               e = jump_block->succ;
1936             }
1937
1938           /* Now add the jump insn ...  */
1939           pos = emit_jump_insn_after (gen_jump (old_succ->head),
1940                                       jump_block->end);
1941           jump_block->end = pos;
1942           if (basic_block_for_insn)
1943             set_block_for_insn (pos, jump_block);
1944           emit_barrier_after (pos);
1945
1946           /* ... let jump know that label is in use, ...  */
1947           JUMP_LABEL (pos) = old_succ->head;
1948           ++LABEL_NUSES (old_succ->head);
1949
1950           /* ... and clear fallthru on the outgoing edge.  */
1951           e->flags &= ~EDGE_FALLTHRU;
1952
1953           /* Continue splitting the interesting edge.  */
1954         }
1955     }
1956
1957   /* Place the new block just in front of the successor.  */
1958   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1959   if (old_succ == EXIT_BLOCK_PTR)
1960     j = n_basic_blocks - 1;
1961   else
1962     j = old_succ->index;
1963   for (i = n_basic_blocks - 1; i > j; --i)
1964     {
1965       basic_block tmp = BASIC_BLOCK (i - 1);
1966       BASIC_BLOCK (i) = tmp;
1967       tmp->index = i;
1968     }
1969   BASIC_BLOCK (i) = bb;
1970   bb->index = i;
1971
1972   /* Create the basic block note.
1973
1974      Where we place the note can have a noticable impact on the generated
1975      code.  Consider this cfg:
1976
1977                         E
1978                         |
1979                         0
1980                        / \
1981                    +->1-->2--->E
1982                    |  |
1983                    +--+
1984
1985       If we need to insert an insn on the edge from block 0 to block 1,
1986       we want to ensure the instructions we insert are outside of any
1987       loop notes that physically sit between block 0 and block 1.  Otherwise
1988       we confuse the loop optimizer into thinking the loop is a phony.  */
1989   if (old_succ != EXIT_BLOCK_PTR
1990       && PREV_INSN (old_succ->head)
1991       && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
1992       && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
1993     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1994                                 PREV_INSN (old_succ->head));
1995   else if (old_succ != EXIT_BLOCK_PTR)
1996     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
1997   else
1998     bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
1999   NOTE_BASIC_BLOCK (bb_note) = bb;
2000   bb->head = bb->end = bb_note;
2001
2002   /* For non-fallthry edges, we must adjust the predecessor's
2003      jump instruction to target our new block.  */
2004   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
2005     {
2006       if (!redirect_edge_and_branch (edge_in, bb))
2007         abort ();
2008     }
2009   else
2010     redirect_edge_succ (edge_in, bb);
2011
2012   return bb;
2013 }
2014
2015 /* Queue instructions for insertion on an edge between two basic blocks.
2016    The new instructions and basic blocks (if any) will not appear in the
2017    CFG until commit_edge_insertions is called.  */
2018
2019 void
2020 insert_insn_on_edge (pattern, e)
2021      rtx pattern;
2022      edge e;
2023 {
2024   /* We cannot insert instructions on an abnormal critical edge.
2025      It will be easier to find the culprit if we die now.  */
2026   if ((e->flags & (EDGE_ABNORMAL|EDGE_CRITICAL))
2027       == (EDGE_ABNORMAL|EDGE_CRITICAL))
2028     abort ();
2029
2030   if (e->insns == NULL_RTX)
2031     start_sequence ();
2032   else
2033     push_to_sequence (e->insns);
2034
2035   emit_insn (pattern);
2036
2037   e->insns = get_insns ();
2038   end_sequence ();
2039 }
2040
2041 /* Update the CFG for the instructions queued on edge E.  */
2042
2043 static void
2044 commit_one_edge_insertion (e)
2045      edge e;
2046 {
2047   rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
2048   basic_block bb;
2049
2050   /* Pull the insns off the edge now since the edge might go away.  */
2051   insns = e->insns;
2052   e->insns = NULL_RTX;
2053
2054   /* Figure out where to put these things.  If the destination has
2055      one predecessor, insert there.  Except for the exit block.  */
2056   if (e->dest->pred->pred_next == NULL
2057       && e->dest != EXIT_BLOCK_PTR)
2058     {
2059       bb = e->dest;
2060
2061       /* Get the location correct wrt a code label, and "nice" wrt
2062          a basic block note, and before everything else.  */
2063       tmp = bb->head;
2064       if (GET_CODE (tmp) == CODE_LABEL)
2065         tmp = NEXT_INSN (tmp);
2066       if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2067         tmp = NEXT_INSN (tmp);
2068       if (tmp == bb->head)
2069         before = tmp;
2070       else
2071         after = PREV_INSN (tmp);
2072     }
2073
2074   /* If the source has one successor and the edge is not abnormal,
2075      insert there.  Except for the entry block.  */
2076   else if ((e->flags & EDGE_ABNORMAL) == 0
2077            && e->src->succ->succ_next == NULL
2078            && e->src != ENTRY_BLOCK_PTR)
2079     {
2080       bb = e->src;
2081       /* It is possible to have a non-simple jump here.  Consider a target
2082          where some forms of unconditional jumps clobber a register.  This
2083          happens on the fr30 for example.
2084
2085          We know this block has a single successor, so we can just emit
2086          the queued insns before the jump.  */
2087       if (GET_CODE (bb->end) == JUMP_INSN)
2088         {
2089           before = bb->end;
2090         }
2091       else
2092         {
2093           /* We'd better be fallthru, or we've lost track of what's what.  */
2094           if ((e->flags & EDGE_FALLTHRU) == 0)
2095             abort ();
2096
2097           after = bb->end;
2098         }
2099     }
2100
2101   /* Otherwise we must split the edge.  */
2102   else
2103     {
2104       bb = split_edge (e);
2105       after = bb->end;
2106     }
2107
2108   /* Now that we've found the spot, do the insertion.  */
2109
2110   /* Set the new block number for these insns, if structure is allocated.  */
2111   if (basic_block_for_insn)
2112     {
2113       rtx i;
2114       for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
2115         set_block_for_insn (i, bb);
2116     }
2117
2118   if (before)
2119     {
2120       emit_insns_before (insns, before);
2121       if (before == bb->head)
2122         bb->head = insns;
2123
2124       last = prev_nonnote_insn (before);
2125     }
2126   else
2127     {
2128       last = emit_insns_after (insns, after);
2129       if (after == bb->end)
2130         bb->end = last;
2131     }
2132
2133   if (returnjump_p (last))
2134     {
2135       /* ??? Remove all outgoing edges from BB and add one for EXIT.
2136          This is not currently a problem because this only happens
2137          for the (single) epilogue, which already has a fallthru edge
2138          to EXIT.  */
2139
2140       e = bb->succ;
2141       if (e->dest != EXIT_BLOCK_PTR
2142           || e->succ_next != NULL
2143           || (e->flags & EDGE_FALLTHRU) == 0)
2144         abort ();
2145       e->flags &= ~EDGE_FALLTHRU;
2146
2147       emit_barrier_after (last);
2148       bb->end = last;
2149
2150       if (before)
2151         flow_delete_insn (before);
2152     }
2153   else if (GET_CODE (last) == JUMP_INSN)
2154     abort ();
2155   find_sub_basic_blocks (bb);
2156 }
2157
2158 /* Update the CFG for all queued instructions.  */
2159
2160 void
2161 commit_edge_insertions ()
2162 {
2163   int i;
2164   basic_block bb;
2165
2166 #ifdef ENABLE_CHECKING
2167   verify_flow_info ();
2168 #endif
2169
2170   i = -1;
2171   bb = ENTRY_BLOCK_PTR;
2172   while (1)
2173     {
2174       edge e, next;
2175
2176       for (e = bb->succ; e; e = next)
2177         {
2178           next = e->succ_next;
2179           if (e->insns)
2180             commit_one_edge_insertion (e);
2181         }
2182
2183       if (++i >= n_basic_blocks)
2184         break;
2185       bb = BASIC_BLOCK (i);
2186     }
2187 }
2188
2189 /* Add fake edges to the function exit for any non constant calls in
2190    the bitmap of blocks specified by BLOCKS or to the whole CFG if
2191    BLOCKS is zero.  Return the nuber of blocks that were split.  */
2192
2193 int
2194 flow_call_edges_add (blocks)
2195      sbitmap blocks;
2196 {
2197   int i;
2198   int blocks_split = 0;
2199   int bb_num = 0;
2200   basic_block *bbs;
2201
2202   /* Map bb indicies into basic block pointers since split_block
2203      will renumber the basic blocks.  */
2204
2205   bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
2206
2207   if (! blocks)
2208     {
2209       for (i = 0; i < n_basic_blocks; i++)
2210         bbs[bb_num++] = BASIC_BLOCK (i);
2211     }
2212   else
2213     {
2214       EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
2215       {
2216         bbs[bb_num++] = BASIC_BLOCK (i);
2217       });
2218     }
2219
2220
2221   /* Now add fake edges to the function exit for any non constant
2222      calls since there is no way that we can determine if they will
2223      return or not...  */
2224
2225   for (i = 0; i < bb_num; i++)
2226     {
2227       basic_block bb = bbs[i];
2228       rtx insn;
2229       rtx prev_insn;
2230
2231       for (insn = bb->end; ; insn = prev_insn)
2232         {
2233           prev_insn = PREV_INSN (insn);
2234           if (GET_CODE (insn) == CALL_INSN && ! CONST_CALL_P (insn))
2235             {
2236               edge e;
2237
2238               /* Note that the following may create a new basic block
2239                  and renumber the existing basic blocks.  */
2240               e = split_block (bb, insn);
2241               if (e)
2242                 blocks_split++;
2243
2244               make_edge (NULL, bb, EXIT_BLOCK_PTR, EDGE_FAKE);
2245             }
2246           if (insn == bb->head)
2247             break;
2248         }
2249     }
2250
2251   if (blocks_split)
2252     verify_flow_info ();
2253
2254   free (bbs);
2255   return blocks_split;
2256 }
2257 \f
2258 /* Find unreachable blocks.  An unreachable block will have NULL in
2259    block->aux, a non-NULL value indicates the block is reachable.  */
2260
2261 void
2262 find_unreachable_blocks ()
2263 {
2264   edge e;
2265   int i, n;
2266   basic_block *tos, *worklist;
2267
2268   n = n_basic_blocks;
2269   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
2270
2271   /* Use basic_block->aux as a marker.  Clear them all.  */
2272
2273   for (i = 0; i < n; ++i)
2274     BASIC_BLOCK (i)->aux = NULL;
2275
2276   /* Add our starting points to the worklist.  Almost always there will
2277      be only one.  It isn't inconcievable that we might one day directly
2278      support Fortran alternate entry points.  */
2279
2280   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
2281     {
2282       *tos++ = e->dest;
2283
2284       /* Mark the block with a handy non-null value.  */
2285       e->dest->aux = e;
2286     }
2287
2288   /* Iterate: find everything reachable from what we've already seen.  */
2289
2290   while (tos != worklist)
2291     {
2292       basic_block b = *--tos;
2293
2294       for (e = b->succ; e; e = e->succ_next)
2295         if (!e->dest->aux)
2296           {
2297             *tos++ = e->dest;
2298             e->dest->aux = e;
2299           }
2300     }
2301
2302   free (worklist);
2303 }
2304
2305 /* Delete all unreachable basic blocks.   */
2306 static void
2307 delete_unreachable_blocks ()
2308 {
2309   int i;
2310
2311   find_unreachable_blocks ();
2312
2313   /* Delete all unreachable basic blocks.  Count down so that we
2314      don't interfere with the block renumbering that happens in
2315      flow_delete_block.  */
2316
2317   for (i = n_basic_blocks - 1; i >= 0; --i)
2318     {
2319       basic_block b = BASIC_BLOCK (i);
2320
2321       if (b->aux != NULL)
2322         /* This block was found.  Tidy up the mark.  */
2323         b->aux = NULL;
2324       else
2325         flow_delete_block (b);
2326     }
2327
2328   tidy_fallthru_edges ();
2329 }
2330
2331 /* Return true if NOTE is not one of the ones that must be kept paired,
2332    so that we may simply delete them.  */
2333
2334 static int
2335 can_delete_note_p (note)
2336      rtx note;
2337 {
2338   return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
2339           || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
2340 }
2341
2342 /* Unlink a chain of insns between START and FINISH, leaving notes
2343    that must be paired.  */
2344
2345 void
2346 flow_delete_insn_chain (start, finish)
2347      rtx start, finish;
2348 {
2349   /* Unchain the insns one by one.  It would be quicker to delete all
2350      of these with a single unchaining, rather than one at a time, but
2351      we need to keep the NOTE's.  */
2352
2353   rtx next;
2354
2355   while (1)
2356     {
2357       next = NEXT_INSN (start);
2358       if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
2359         ;
2360       else if (GET_CODE (start) == CODE_LABEL
2361                && ! can_delete_label_p (start))
2362         {
2363           const char *name = LABEL_NAME (start);
2364           PUT_CODE (start, NOTE);
2365           NOTE_LINE_NUMBER (start) = NOTE_INSN_DELETED_LABEL;
2366           NOTE_SOURCE_FILE (start) = name;
2367         }
2368       else
2369         next = flow_delete_insn (start);
2370
2371       if (start == finish)
2372         break;
2373       start = next;
2374     }
2375 }
2376
2377 /* Delete the insns in a (non-live) block.  We physically delete every
2378    non-deleted-note insn, and update the flow graph appropriately.
2379
2380    Return nonzero if we deleted an exception handler.  */
2381
2382 /* ??? Preserving all such notes strikes me as wrong.  It would be nice
2383    to post-process the stream to remove empty blocks, loops, ranges, etc.  */
2384
2385 int
2386 flow_delete_block (b)
2387      basic_block b;
2388 {
2389   int deleted_handler = 0;
2390   rtx insn, end, tmp;
2391
2392   /* If the head of this block is a CODE_LABEL, then it might be the
2393      label for an exception handler which can't be reached.
2394
2395      We need to remove the label from the exception_handler_label list
2396      and remove the associated NOTE_INSN_EH_REGION_BEG and
2397      NOTE_INSN_EH_REGION_END notes.  */
2398
2399   insn = b->head;
2400
2401   never_reached_warning (insn);
2402
2403   if (GET_CODE (insn) == CODE_LABEL)
2404     maybe_remove_eh_handler (insn);
2405
2406   /* Include any jump table following the basic block.  */
2407   end = b->end;
2408   if (GET_CODE (end) == JUMP_INSN
2409       && (tmp = JUMP_LABEL (end)) != NULL_RTX
2410       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
2411       && GET_CODE (tmp) == JUMP_INSN
2412       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
2413           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
2414     end = tmp;
2415
2416   /* Include any barrier that may follow the basic block.  */
2417   tmp = next_nonnote_insn (end);
2418   if (tmp && GET_CODE (tmp) == BARRIER)
2419     end = tmp;
2420
2421   /* Selectively delete the entire chain.  */
2422   flow_delete_insn_chain (insn, end);
2423
2424   /* Remove the edges into and out of this block.  Note that there may
2425      indeed be edges in, if we are removing an unreachable loop.  */
2426   {
2427     edge e, next, *q;
2428
2429     for (e = b->pred; e; e = next)
2430       {
2431         for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
2432           continue;
2433         *q = e->succ_next;
2434         next = e->pred_next;
2435         n_edges--;
2436         free (e);
2437       }
2438     for (e = b->succ; e; e = next)
2439       {
2440         for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
2441           continue;
2442         *q = e->pred_next;
2443         next = e->succ_next;
2444         n_edges--;
2445         free (e);
2446       }
2447
2448     b->pred = NULL;
2449     b->succ = NULL;
2450   }
2451
2452   /* Remove the basic block from the array, and compact behind it.  */
2453   expunge_block (b);
2454
2455   return deleted_handler;
2456 }
2457
2458 /* Remove block B from the basic block array and compact behind it.  */
2459
2460 static void
2461 expunge_block (b)
2462      basic_block b;
2463 {
2464   int i, n = n_basic_blocks;
2465
2466   for (i = b->index; i + 1 < n; ++i)
2467     {
2468       basic_block x = BASIC_BLOCK (i + 1);
2469       BASIC_BLOCK (i) = x;
2470       x->index = i;
2471     }
2472
2473   basic_block_info->num_elements--;
2474   n_basic_blocks--;
2475 }
2476
2477 /* Delete INSN by patching it out.  Return the next insn.  */
2478
2479 rtx
2480 flow_delete_insn (insn)
2481      rtx insn;
2482 {
2483   rtx prev = PREV_INSN (insn);
2484   rtx next = NEXT_INSN (insn);
2485   rtx note;
2486
2487   PREV_INSN (insn) = NULL_RTX;
2488   NEXT_INSN (insn) = NULL_RTX;
2489   INSN_DELETED_P (insn) = 1;
2490
2491   if (prev)
2492     NEXT_INSN (prev) = next;
2493   if (next)
2494     PREV_INSN (next) = prev;
2495   else
2496     set_last_insn (prev);
2497
2498   if (GET_CODE (insn) == CODE_LABEL)
2499     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2500
2501   /* If deleting a jump, decrement the use count of the label.  Deleting
2502      the label itself should happen in the normal course of block merging.  */
2503   if (GET_CODE (insn) == JUMP_INSN
2504       && JUMP_LABEL (insn)
2505       && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
2506     LABEL_NUSES (JUMP_LABEL (insn))--;
2507
2508   /* Also if deleting an insn that references a label.  */
2509   else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
2510            && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2511     LABEL_NUSES (XEXP (note, 0))--;
2512
2513   if (GET_CODE (insn) == JUMP_INSN
2514       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
2515           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
2516     {
2517       rtx pat = PATTERN (insn);
2518       int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
2519       int len = XVECLEN (pat, diff_vec_p);
2520       int i;
2521
2522       for (i = 0; i < len; i++)
2523         LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
2524     }
2525
2526   return next;
2527 }
2528
2529 /* True if a given label can be deleted.  */
2530
2531 static int
2532 can_delete_label_p (label)
2533      rtx label;
2534 {
2535   rtx x;
2536
2537   if (LABEL_PRESERVE_P (label))
2538     return 0;
2539
2540   for (x = forced_labels; x; x = XEXP (x, 1))
2541     if (label == XEXP (x, 0))
2542       return 0;
2543   for (x = label_value_list; x; x = XEXP (x, 1))
2544     if (label == XEXP (x, 0))
2545       return 0;
2546   for (x = exception_handler_labels; x; x = XEXP (x, 1))
2547     if (label == XEXP (x, 0))
2548       return 0;
2549
2550   /* User declared labels must be preserved.  */
2551   if (LABEL_NAME (label) != 0)
2552     return 0;
2553
2554   return 1;
2555 }
2556
2557 static int
2558 tail_recursion_label_p (label)
2559      rtx label;
2560 {
2561   rtx x;
2562
2563   for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
2564     if (label == XEXP (x, 0))
2565       return 1;
2566
2567   return 0;
2568 }
2569
2570 /* Blocks A and B are to be merged into a single block A.  The insns
2571    are already contiguous, hence `nomove'.  */
2572
2573 void
2574 merge_blocks_nomove (a, b)
2575      basic_block a, b;
2576 {
2577   edge e;
2578   rtx b_head, b_end, a_end;
2579   rtx del_first = NULL_RTX, del_last = NULL_RTX;
2580   int b_empty = 0;
2581
2582   /* If there was a CODE_LABEL beginning B, delete it.  */
2583   b_head = b->head;
2584   b_end = b->end;
2585   if (GET_CODE (b_head) == CODE_LABEL)
2586     {
2587       /* Detect basic blocks with nothing but a label.  This can happen
2588          in particular at the end of a function.  */
2589       if (b_head == b_end)
2590         b_empty = 1;
2591       del_first = del_last = b_head;
2592       b_head = NEXT_INSN (b_head);
2593     }
2594
2595   /* Delete the basic block note.  */
2596   if (NOTE_INSN_BASIC_BLOCK_P (b_head))
2597     {
2598       if (b_head == b_end)
2599         b_empty = 1;
2600       if (! del_last)
2601         del_first = b_head;
2602       del_last = b_head;
2603       b_head = NEXT_INSN (b_head);
2604     }
2605
2606   /* If there was a jump out of A, delete it.  */
2607   a_end = a->end;
2608   if (GET_CODE (a_end) == JUMP_INSN)
2609     {
2610       rtx prev;
2611
2612       for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
2613         if (GET_CODE (prev) != NOTE
2614             || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
2615             || prev == a->head)
2616           break;
2617
2618       del_first = a_end;
2619
2620 #ifdef HAVE_cc0
2621       /* If this was a conditional jump, we need to also delete
2622          the insn that set cc0.  */
2623       if (prev && sets_cc0_p (prev))
2624         {
2625           rtx tmp = prev;
2626           prev = prev_nonnote_insn (prev);
2627           if (!prev)
2628             prev = a->head;
2629           del_first = tmp;
2630         }
2631 #endif
2632
2633       a_end = prev;
2634     }
2635   else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
2636     del_first = NEXT_INSN (a_end);
2637
2638   /* Delete everything marked above as well as crap that might be
2639      hanging out between the two blocks.  */
2640   flow_delete_insn_chain (del_first, del_last);
2641
2642   /* Normally there should only be one successor of A and that is B, but
2643      partway though the merge of blocks for conditional_execution we'll
2644      be merging a TEST block with THEN and ELSE successors.  Free the
2645      whole lot of them and hope the caller knows what they're doing.  */
2646   while (a->succ)
2647     remove_edge (a->succ);
2648
2649   /* Adjust the edges out of B for the new owner.  */
2650   for (e = b->succ; e; e = e->succ_next)
2651     e->src = a;
2652   a->succ = b->succ;
2653
2654   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
2655   b->pred = b->succ = NULL;
2656
2657   /* Reassociate the insns of B with A.  */
2658   if (!b_empty)
2659     {
2660       if (basic_block_for_insn)
2661         {
2662           BLOCK_FOR_INSN (b_head) = a;
2663           while (b_head != b_end)
2664             {
2665               b_head = NEXT_INSN (b_head);
2666               BLOCK_FOR_INSN (b_head) = a;
2667             }
2668         }
2669       a_end = b_end;
2670     }
2671   a->end = a_end;
2672
2673   expunge_block (b);
2674 }
2675
2676 /* Blocks A and B are to be merged into a single block.  A has no incoming
2677    fallthru edge, so it can be moved before B without adding or modifying
2678    any jumps (aside from the jump from A to B).  */
2679
2680 static int
2681 merge_blocks_move_predecessor_nojumps (a, b)
2682      basic_block a, b;
2683 {
2684   rtx start, end, barrier;
2685   int index;
2686
2687   start = a->head;
2688   end = a->end;
2689
2690   barrier = next_nonnote_insn (end);
2691   if (GET_CODE (barrier) != BARRIER)
2692     abort ();
2693   flow_delete_insn (barrier);
2694
2695   /* Move block and loop notes out of the chain so that we do not
2696      disturb their order.
2697
2698      ??? A better solution would be to squeeze out all the non-nested notes
2699      and adjust the block trees appropriately.   Even better would be to have
2700      a tighter connection between block trees and rtl so that this is not
2701      necessary.  */
2702   start = squeeze_notes (start, end);
2703
2704   /* Scramble the insn chain.  */
2705   if (end != PREV_INSN (b->head))
2706     reorder_insns (start, end, PREV_INSN (b->head));
2707
2708   if (rtl_dump_file)
2709     {
2710       fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
2711                a->index, b->index);
2712     }
2713
2714   /* Swap the records for the two blocks around.  Although we are deleting B,
2715      A is now where B was and we want to compact the BB array from where
2716      A used to be.  */
2717   BASIC_BLOCK (a->index) = b;
2718   BASIC_BLOCK (b->index) = a;
2719   index = a->index;
2720   a->index = b->index;
2721   b->index = index;
2722
2723   /* Now blocks A and B are contiguous.  Merge them.  */
2724   merge_blocks_nomove (a, b);
2725
2726   return 1;
2727 }
2728
2729 /* Blocks A and B are to be merged into a single block.  B has no outgoing
2730    fallthru edge, so it can be moved after A without adding or modifying
2731    any jumps (aside from the jump from A to B).  */
2732
2733 static int
2734 merge_blocks_move_successor_nojumps (a, b)
2735      basic_block a, b;
2736 {
2737   rtx start, end, barrier;
2738
2739   start = b->head;
2740   end = b->end;
2741   barrier = NEXT_INSN (end);
2742
2743   /* Recognize a jump table following block B.  */
2744   if (GET_CODE (barrier) == CODE_LABEL
2745       && NEXT_INSN (barrier)
2746       && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
2747       && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
2748           || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
2749     {
2750       end = NEXT_INSN (barrier);
2751       barrier = NEXT_INSN (end);
2752     }
2753
2754   /* There had better have been a barrier there.  Delete it.  */
2755   if (GET_CODE (barrier) != BARRIER)
2756     abort ();
2757   flow_delete_insn (barrier);
2758
2759   /* Move block and loop notes out of the chain so that we do not
2760      disturb their order.
2761
2762      ??? A better solution would be to squeeze out all the non-nested notes
2763      and adjust the block trees appropriately.   Even better would be to have
2764      a tighter connection between block trees and rtl so that this is not
2765      necessary.  */
2766   start = squeeze_notes (start, end);
2767
2768   /* Scramble the insn chain.  */
2769   reorder_insns (start, end, a->end);
2770
2771   /* Now blocks A and B are contiguous.  Merge them.  */
2772   merge_blocks_nomove (a, b);
2773
2774   if (rtl_dump_file)
2775     {
2776       fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
2777                b->index, a->index);
2778     }
2779
2780   return 1;
2781 }
2782
2783 /* Attempt to merge basic blocks that are potentially non-adjacent.
2784    Return true iff the attempt succeeded.  */
2785
2786 static int
2787 merge_blocks (e, b, c)
2788      edge e;
2789      basic_block b, c;
2790 {
2791   /* If C has a tail recursion label, do not merge.  There is no
2792      edge recorded from the call_placeholder back to this label, as
2793      that would make optimize_sibling_and_tail_recursive_calls more
2794      complex for no gain.  */
2795   if (GET_CODE (c->head) == CODE_LABEL
2796       && tail_recursion_label_p (c->head))
2797     return 0;
2798
2799   /* If B has a fallthru edge to C, no need to move anything.  */
2800   if (e->flags & EDGE_FALLTHRU)
2801     {
2802       merge_blocks_nomove (b, c);
2803
2804       if (rtl_dump_file)
2805         {
2806           fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
2807                    b->index, c->index);
2808         }
2809
2810       return 1;
2811     }
2812   else
2813     {
2814       edge tmp_edge;
2815       int c_has_outgoing_fallthru;
2816       int b_has_incoming_fallthru;
2817
2818       /* We must make sure to not munge nesting of exception regions,
2819          lexical blocks, and loop notes.
2820
2821          The first is taken care of by requiring that the active eh
2822          region at the end of one block always matches the active eh
2823          region at the beginning of the next block.
2824
2825          The later two are taken care of by squeezing out all the notes.  */
2826
2827       /* ???  A throw/catch edge (or any abnormal edge) should be rarely
2828          executed and we may want to treat blocks which have two out
2829          edges, one normal, one abnormal as only having one edge for
2830          block merging purposes.  */
2831
2832       for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
2833         if (tmp_edge->flags & EDGE_FALLTHRU)
2834           break;
2835       c_has_outgoing_fallthru = (tmp_edge != NULL);
2836
2837       for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
2838         if (tmp_edge->flags & EDGE_FALLTHRU)
2839           break;
2840       b_has_incoming_fallthru = (tmp_edge != NULL);
2841
2842       /* If B does not have an incoming fallthru, then it can be moved
2843          immediately before C without introducing or modifying jumps.
2844          C cannot be the first block, so we do not have to worry about
2845          accessing a non-existent block.  */
2846       if (! b_has_incoming_fallthru)
2847         return merge_blocks_move_predecessor_nojumps (b, c);
2848
2849       /* Otherwise, we're going to try to move C after B.  If C does
2850          not have an outgoing fallthru, then it can be moved
2851          immediately after B without introducing or modifying jumps.  */
2852       if (! c_has_outgoing_fallthru)
2853         return merge_blocks_move_successor_nojumps (b, c);
2854
2855       /* Otherwise, we'll need to insert an extra jump, and possibly
2856          a new block to contain it.  */
2857       /* ??? Not implemented yet.  */
2858
2859       return 0;
2860     }
2861 }
2862
2863 /* Simplify conditional jump around an jump.
2864    Return nonzero in case optimization matched.  */
2865
2866 static bool
2867 try_simplify_condjump (src)
2868      basic_block src;
2869 {
2870   basic_block final_block, next_block;
2871   rtx insn = src->end;
2872   edge branch, fallthru;
2873
2874   if (!any_condjump_p (insn))
2875     return false;
2876
2877   fallthru = FALLTHRU_EDGE (src);
2878
2879   /* Following block must be simple forwarder block with single
2880      entry and must not be last in the stream.  */
2881   next_block = fallthru->dest;
2882   if (!forwarder_block_p (next_block)
2883       || next_block->pred->pred_next
2884       || next_block->index == n_basic_blocks - 1)
2885     return false;
2886
2887   /* The branch must target to block afterwards.  */
2888   final_block = BASIC_BLOCK (next_block->index + 1);
2889
2890   branch = BRANCH_EDGE (src);
2891
2892   if (branch->dest != final_block)
2893     return false;
2894
2895   /* Avoid jump.c from being overactive on removin ureachable insns.  */
2896   LABEL_NUSES (JUMP_LABEL (insn))++;
2897   if (!invert_jump (insn, block_label (next_block->succ->dest), 1))
2898     {
2899       LABEL_NUSES (JUMP_LABEL (insn))--;
2900       return false;
2901     }
2902   if (rtl_dump_file)
2903     fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
2904              INSN_UID (insn), INSN_UID (next_block->end));
2905
2906   redirect_edge_succ (branch, final_block);
2907   redirect_edge_succ (fallthru, next_block->succ->dest);
2908
2909   branch->flags |= EDGE_FALLTHRU;
2910   fallthru->flags &= ~EDGE_FALLTHRU;
2911
2912   flow_delete_block (next_block);
2913   return true;
2914 }
2915
2916 /* Attempt to forward edges leaving basic block B.
2917    Return nonzero if sucessfull.  */
2918
2919 static bool
2920 try_forward_edges (b)
2921      basic_block b;
2922 {
2923   bool changed = 0;
2924   edge e;
2925   for (e = b->succ; e; e = e->succ_next)
2926     {
2927       basic_block target = e->dest, first = e->dest;
2928       int counter = 0;
2929
2930       /* Look for the real destination of jump.
2931          Avoid inifinite loop in the infinite empty loop by counting
2932          up to n_basic_blocks.  */
2933       while (forwarder_block_p (target)
2934              && target->succ->dest != EXIT_BLOCK_PTR
2935              && counter < n_basic_blocks)
2936         {
2937           /* Bypass trivial infinite loops.  */
2938           if (target == target->succ->dest)
2939             counter = n_basic_blocks;
2940           target = target->succ->dest, counter++;
2941         }
2942
2943       if (target != first && counter < n_basic_blocks
2944           && redirect_edge_and_branch (e, target))
2945         {
2946           while (first != target)
2947             {
2948               first->count -= e->count;
2949               first->succ->count -= e->count;
2950               first->frequency -= ((e->probability * b->frequency
2951                                     + REG_BR_PROB_BASE / 2)
2952                                    / REG_BR_PROB_BASE);
2953               first = first->succ->dest;
2954             }
2955           /* We've possibly removed the edge.  */
2956           changed = 1;
2957           e = b->succ;
2958         }
2959       else if (rtl_dump_file && counter == n_basic_blocks)
2960         fprintf (rtl_dump_file, "Infinite loop in BB %i.\n", target->index);
2961       else if (rtl_dump_file && first != target)
2962         fprintf (rtl_dump_file,
2963                  "Forwarding edge %i->%i to %i failed.\n", b->index,
2964                  e->dest->index, target->index);
2965     }
2966   return changed;
2967 }
2968
2969 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2970    instructions etc.
2971
2972    Return nonzero in case some optimizations matched.  */
2973
2974 static bool
2975 try_optimize_cfg ()
2976 {
2977   int i;
2978   bool changed_overall = 0;
2979   bool changed;
2980
2981   /* Attempt to merge blocks as made possible by edge removal.  If a block
2982      has only one successor, and the successor has only one predecessor,
2983      they may be combined.  */
2984
2985   do
2986     {
2987       changed = 0;
2988       for (i = 0; i < n_basic_blocks;)
2989         {
2990           basic_block c, b = BASIC_BLOCK (i);
2991           edge s;
2992           int changed_here = 0;
2993
2994           /* Delete trivially dead basic block.  */
2995           if (b->pred == NULL)
2996             {
2997               c = BASIC_BLOCK (i - 1);
2998               if (rtl_dump_file)
2999                 fprintf (rtl_dump_file, "Deleting block %i.\n", b->index);
3000               flow_delete_block (b);
3001               changed = 1;
3002               b = c;
3003             }
3004           /* The fallthru forwarder block can be deleted.  */
3005           if (b->pred->pred_next == NULL
3006               && forwarder_block_p (b)
3007               && (b->pred->flags & EDGE_FALLTHRU)
3008               && (b->succ->flags & EDGE_FALLTHRU))
3009             {
3010               if (rtl_dump_file)
3011                 fprintf (rtl_dump_file, "Deleting fallthru block %i.\n",
3012                          b->index);
3013               c = BASIC_BLOCK (i ? i - 1 : i + 1);
3014               redirect_edge_succ (b->pred, b->succ->dest);
3015               flow_delete_block (b);
3016               changed = 1;
3017               b = c;
3018             }
3019
3020           /* A loop because chains of blocks might be combineable.  */
3021           while ((s = b->succ) != NULL
3022                  && s->succ_next == NULL
3023                  && (s->flags & EDGE_EH) == 0
3024                  && (c = s->dest) != EXIT_BLOCK_PTR
3025                  && c->pred->pred_next == NULL
3026                  /* If the jump insn has side effects, we can't kill the edge.  */
3027                  && (GET_CODE (b->end) != JUMP_INSN
3028                      || onlyjump_p (b->end)) && merge_blocks (s, b, c))
3029             changed_here = 1;
3030
3031           if (try_simplify_condjump (b))
3032             changed_here = 1;
3033
3034           /* In the case basic blocks has single outgoing edge, but over by the
3035              non-trivial jump instruction, we can replace it by unconditional
3036              jump, or delete the jump completely.  Use logic of
3037              redirect_edge_and_branch to do the dirty job for us.
3038
3039              We match cases as conditional jumps jumping to the next block or
3040              dispatch tables.  */
3041
3042           if (b->succ
3043               && b->succ->succ_next == NULL
3044               && GET_CODE (b->end) == JUMP_INSN
3045               && b->succ->dest != EXIT_BLOCK_PTR
3046               && redirect_edge_and_branch (b->succ, b->succ->dest))
3047             changed_here = 1;
3048
3049           if (try_forward_edges (b))
3050             changed_here = 1;
3051
3052           /* Don't get confused by the index shift caused by deleting
3053              blocks.  */
3054           if (!changed_here)
3055             i = b->index + 1;
3056           else
3057             changed = 1;
3058         }
3059       changed_overall |= changed;
3060       changed = 0;
3061     }
3062   while (changed);
3063 #ifdef ENABLE_CHECKING
3064   if (changed)
3065     verify_flow_info ();
3066 #endif
3067   return changed_overall;
3068 }
3069
3070 /* The given edge should potentially be a fallthru edge.  If that is in
3071    fact true, delete the jump and barriers that are in the way.  */
3072
3073 void
3074 tidy_fallthru_edge (e, b, c)
3075      edge e;
3076      basic_block b, c;
3077 {
3078   rtx q;
3079
3080   /* ??? In a late-running flow pass, other folks may have deleted basic
3081      blocks by nopping out blocks, leaving multiple BARRIERs between here
3082      and the target label. They ought to be chastized and fixed.
3083
3084      We can also wind up with a sequence of undeletable labels between
3085      one block and the next.
3086
3087      So search through a sequence of barriers, labels, and notes for
3088      the head of block C and assert that we really do fall through.  */
3089
3090   if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
3091     return;
3092
3093   /* Remove what will soon cease being the jump insn from the source block.
3094      If block B consisted only of this single jump, turn it into a deleted
3095      note.  */
3096   q = b->end;
3097   if (GET_CODE (q) == JUMP_INSN
3098       && onlyjump_p (q)
3099       && (any_uncondjump_p (q)
3100           || (b->succ == e && e->succ_next == NULL)))
3101     {
3102 #ifdef HAVE_cc0
3103       /* If this was a conditional jump, we need to also delete
3104          the insn that set cc0.  */
3105       if (any_condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
3106         q = PREV_INSN (q);
3107 #endif
3108
3109       if (b->head == q)
3110         {
3111           PUT_CODE (q, NOTE);
3112           NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
3113           NOTE_SOURCE_FILE (q) = 0;
3114         }
3115       else
3116         {
3117           q = PREV_INSN (q);
3118
3119           /* We don't want a block to end on a line-number note since that has
3120              the potential of changing the code between -g and not -g.  */
3121           while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
3122             q = PREV_INSN (q);
3123         }
3124
3125       b->end = q;
3126     }
3127
3128   /* Selectively unlink the sequence.  */
3129   if (q != PREV_INSN (c->head))
3130     flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
3131
3132   e->flags |= EDGE_FALLTHRU;
3133 }
3134
3135 /* Fix up edges that now fall through, or rather should now fall through
3136    but previously required a jump around now deleted blocks.  Simplify
3137    the search by only examining blocks numerically adjacent, since this
3138    is how find_basic_blocks created them.  */
3139
3140 static void
3141 tidy_fallthru_edges ()
3142 {
3143   int i;
3144
3145   for (i = 1; i < n_basic_blocks; ++i)
3146     {
3147       basic_block b = BASIC_BLOCK (i - 1);
3148       basic_block c = BASIC_BLOCK (i);
3149       edge s;
3150
3151       /* We care about simple conditional or unconditional jumps with
3152          a single successor.
3153
3154          If we had a conditional branch to the next instruction when
3155          find_basic_blocks was called, then there will only be one
3156          out edge for the block which ended with the conditional
3157          branch (since we do not create duplicate edges).
3158
3159          Furthermore, the edge will be marked as a fallthru because we
3160          merge the flags for the duplicate edges.  So we do not want to
3161          check that the edge is not a FALLTHRU edge.  */
3162       if ((s = b->succ) != NULL
3163           && ! (s->flags & EDGE_COMPLEX)
3164           && s->succ_next == NULL
3165           && s->dest == c
3166           /* If the jump insn has side effects, we can't tidy the edge.  */
3167           && (GET_CODE (b->end) != JUMP_INSN
3168               || onlyjump_p (b->end)))
3169         tidy_fallthru_edge (s, b, c);
3170     }
3171 }
3172 \f
3173 /* Perform data flow analysis.
3174    F is the first insn of the function; FLAGS is a set of PROP_* flags
3175    to be used in accumulating flow info.  */
3176
3177 void
3178 life_analysis (f, file, flags)
3179      rtx f;
3180      FILE *file;
3181      int flags;
3182 {
3183 #ifdef ELIMINABLE_REGS
3184   register int i;
3185   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
3186 #endif
3187
3188   /* Record which registers will be eliminated.  We use this in
3189      mark_used_regs.  */
3190
3191   CLEAR_HARD_REG_SET (elim_reg_set);
3192
3193 #ifdef ELIMINABLE_REGS
3194   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3195     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3196 #else
3197   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
3198 #endif
3199
3200   if (! optimize)
3201     flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC);
3202
3203   /* The post-reload life analysis have (on a global basis) the same
3204      registers live as was computed by reload itself.  elimination
3205      Otherwise offsets and such may be incorrect.
3206
3207      Reload will make some registers as live even though they do not
3208      appear in the rtl.
3209
3210      We don't want to create new auto-incs after reload, since they
3211      are unlikely to be useful and can cause problems with shared
3212      stack slots.  */
3213   if (reload_completed)
3214     flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
3215
3216   /* We want alias analysis information for local dead store elimination.  */
3217   if (optimize && (flags & PROP_SCAN_DEAD_CODE))
3218     init_alias_analysis ();
3219
3220   /* Always remove no-op moves.  Do this before other processing so
3221      that we don't have to keep re-scanning them.  */
3222   delete_noop_moves (f);
3223
3224   /* Some targets can emit simpler epilogues if they know that sp was
3225      not ever modified during the function.  After reload, of course,
3226      we've already emitted the epilogue so there's no sense searching.  */
3227   if (! reload_completed)
3228     notice_stack_pointer_modification (f);
3229
3230   /* Allocate and zero out data structures that will record the
3231      data from lifetime analysis.  */
3232   allocate_reg_life_data ();
3233   allocate_bb_life_data ();
3234
3235   /* Find the set of registers live on function exit.  */
3236   mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
3237
3238   /* "Update" life info from zero.  It'd be nice to begin the
3239      relaxation with just the exit and noreturn blocks, but that set
3240      is not immediately handy.  */
3241
3242   if (flags & PROP_REG_INFO)
3243     memset (regs_ever_live, 0, sizeof (regs_ever_live));
3244   update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
3245
3246   /* Clean up.  */
3247   if (optimize && (flags & PROP_SCAN_DEAD_CODE))
3248     end_alias_analysis ();
3249
3250   if (file)
3251     dump_flow_info (file);
3252
3253   free_basic_block_vars (1);
3254
3255 #ifdef ENABLE_CHECKING
3256   {
3257     rtx insn;
3258
3259     /* Search for any REG_LABEL notes which reference deleted labels.  */
3260     for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3261       {
3262         rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
3263
3264         if (inote && GET_CODE (inote) == NOTE_INSN_DELETED_LABEL)
3265           abort ();
3266       }
3267   }
3268 #endif
3269 }
3270
3271 /* A subroutine of verify_wide_reg, called through for_each_rtx.
3272    Search for REGNO.  If found, abort if it is not wider than word_mode.  */
3273
3274 static int
3275 verify_wide_reg_1 (px, pregno)
3276      rtx *px;
3277      void *pregno;
3278 {
3279   rtx x = *px;
3280   unsigned int regno = *(int *) pregno;
3281
3282   if (GET_CODE (x) == REG && REGNO (x) == regno)
3283     {
3284       if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
3285         abort ();
3286       return 1;
3287     }
3288   return 0;
3289 }
3290
3291 /* A subroutine of verify_local_live_at_start.  Search through insns
3292    between HEAD and END looking for register REGNO.  */
3293
3294 static void
3295 verify_wide_reg (regno, head, end)
3296      int regno;
3297      rtx head, end;
3298 {
3299   while (1)
3300     {
3301       if (INSN_P (head)
3302           && for_each_rtx (&PATTERN (head), verify_wide_reg_1, &regno))
3303         return;
3304       if (head == end)
3305         break;
3306       head = NEXT_INSN (head);
3307     }
3308
3309   /* We didn't find the register at all.  Something's way screwy.  */
3310   if (rtl_dump_file)
3311     fprintf (rtl_dump_file, "Aborting in verify_wide_reg; reg %d\n", regno);
3312   print_rtl_and_abort ();
3313 }
3314
3315 /* A subroutine of update_life_info.  Verify that there are no untoward
3316    changes in live_at_start during a local update.  */
3317
3318 static void
3319 verify_local_live_at_start (new_live_at_start, bb)
3320      regset new_live_at_start;
3321      basic_block bb;
3322 {
3323   if (reload_completed)
3324     {
3325       /* After reload, there are no pseudos, nor subregs of multi-word
3326          registers.  The regsets should exactly match.  */
3327       if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
3328         {
3329           if (rtl_dump_file)
3330             {
3331               fprintf (rtl_dump_file,
3332                        "live_at_start mismatch in bb %d, aborting\n",
3333                        bb->index);
3334               debug_bitmap_file (rtl_dump_file, bb->global_live_at_start);
3335               debug_bitmap_file (rtl_dump_file, new_live_at_start);
3336             }
3337           print_rtl_and_abort ();
3338         }
3339     }
3340   else
3341     {
3342       int i;
3343
3344       /* Find the set of changed registers.  */
3345       XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
3346
3347       EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i,
3348         {
3349           /* No registers should die.  */
3350           if (REGNO_REG_SET_P (bb->global_live_at_start, i))
3351             {
3352               if (rtl_dump_file)
3353                 fprintf (rtl_dump_file,
3354                          "Register %d died unexpectedly in block %d\n", i,
3355                          bb->index);
3356               print_rtl_and_abort ();
3357             }
3358
3359           /* Verify that the now-live register is wider than word_mode.  */
3360           verify_wide_reg (i, bb->head, bb->end);
3361         });
3362     }
3363 }
3364
3365 /* Updates life information starting with the basic blocks set in BLOCKS.
3366    If BLOCKS is null, consider it to be the universal set.
3367
3368    If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
3369    we are only expecting local modifications to basic blocks.  If we find
3370    extra registers live at the beginning of a block, then we either killed
3371    useful data, or we have a broken split that wants data not provided.
3372    If we find registers removed from live_at_start, that means we have
3373    a broken peephole that is killing a register it shouldn't.
3374
3375    ??? This is not true in one situation -- when a pre-reload splitter
3376    generates subregs of a multi-word pseudo, current life analysis will
3377    lose the kill.  So we _can_ have a pseudo go live.  How irritating.
3378
3379    Including PROP_REG_INFO does not properly refresh regs_ever_live
3380    unless the caller resets it to zero.  */
3381
3382 void
3383 update_life_info (blocks, extent, prop_flags)
3384      sbitmap blocks;
3385      enum update_life_extent extent;
3386      int prop_flags;
3387 {
3388   regset tmp;
3389   regset_head tmp_head;
3390   int i;
3391
3392   tmp = INITIALIZE_REG_SET (tmp_head);
3393
3394   /* For a global update, we go through the relaxation process again.  */
3395   if (extent != UPDATE_LIFE_LOCAL)
3396     {
3397       calculate_global_regs_live (blocks, blocks,
3398                                   prop_flags & PROP_SCAN_DEAD_CODE);
3399
3400       /* If asked, remove notes from the blocks we'll update.  */
3401       if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
3402         count_or_remove_death_notes (blocks, 1);
3403     }
3404
3405   if (blocks)
3406     {
3407       EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
3408         {
3409           basic_block bb = BASIC_BLOCK (i);
3410
3411           COPY_REG_SET (tmp, bb->global_live_at_end);
3412           propagate_block (bb, tmp, NULL, NULL, prop_flags);
3413
3414           if (extent == UPDATE_LIFE_LOCAL)
3415             verify_local_live_at_start (tmp, bb);
3416         });
3417     }
3418   else
3419     {
3420       for (i = n_basic_blocks - 1; i >= 0; --i)
3421         {
3422           basic_block bb = BASIC_BLOCK (i);
3423
3424           COPY_REG_SET (tmp, bb->global_live_at_end);
3425           propagate_block (bb, tmp, NULL, NULL, prop_flags);
3426
3427           if (extent == UPDATE_LIFE_LOCAL)
3428             verify_local_live_at_start (tmp, bb);
3429         }
3430     }
3431
3432   FREE_REG_SET (tmp);
3433
3434   if (prop_flags & PROP_REG_INFO)
3435     {
3436       /* The only pseudos that are live at the beginning of the function
3437          are those that were not set anywhere in the function.  local-alloc
3438          doesn't know how to handle these correctly, so mark them as not
3439          local to any one basic block.  */
3440       EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
3441                                  FIRST_PSEUDO_REGISTER, i,
3442                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
3443
3444       /* We have a problem with any pseudoreg that lives across the setjmp.
3445          ANSI says that if a user variable does not change in value between
3446          the setjmp and the longjmp, then the longjmp preserves it.  This
3447          includes longjmp from a place where the pseudo appears dead.
3448          (In principle, the value still exists if it is in scope.)
3449          If the pseudo goes in a hard reg, some other value may occupy
3450          that hard reg where this pseudo is dead, thus clobbering the pseudo.
3451          Conclusion: such a pseudo must not go in a hard reg.  */
3452       EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
3453                                  FIRST_PSEUDO_REGISTER, i,
3454                                  {
3455                                    if (regno_reg_rtx[i] != 0)
3456                                      {
3457                                        REG_LIVE_LENGTH (i) = -1;
3458                                        REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
3459                                      }
3460                                  });
3461     }
3462 }
3463
3464 /* Free the variables allocated by find_basic_blocks.
3465
3466    KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed.  */
3467
3468 void
3469 free_basic_block_vars (keep_head_end_p)
3470      int keep_head_end_p;
3471 {
3472   if (basic_block_for_insn)
3473     {
3474       VARRAY_FREE (basic_block_for_insn);
3475       basic_block_for_insn = NULL;
3476     }
3477
3478   if (! keep_head_end_p)
3479     {
3480       if (basic_block_info)
3481         {
3482           clear_edges ();
3483           VARRAY_FREE (basic_block_info);
3484         }
3485       n_basic_blocks = 0;
3486
3487       ENTRY_BLOCK_PTR->aux = NULL;
3488       ENTRY_BLOCK_PTR->global_live_at_end = NULL;
3489       EXIT_BLOCK_PTR->aux = NULL;
3490       EXIT_BLOCK_PTR->global_live_at_start = NULL;
3491     }
3492 }
3493
3494 /* Return nonzero if an insn consists only of SETs, each of which only sets a
3495    value to itself.  */
3496
3497 static int
3498 noop_move_p (insn)
3499      rtx insn;
3500 {
3501   rtx pat = PATTERN (insn);
3502
3503   /* Insns carrying these notes are useful later on.  */
3504   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
3505     return 0;
3506
3507   if (GET_CODE (pat) == SET && set_noop_p (pat))
3508     return 1;
3509
3510   if (GET_CODE (pat) == PARALLEL)
3511     {
3512       int i;
3513       /* If nothing but SETs of registers to themselves,
3514          this insn can also be deleted.  */
3515       for (i = 0; i < XVECLEN (pat, 0); i++)
3516         {
3517           rtx tem = XVECEXP (pat, 0, i);
3518
3519           if (GET_CODE (tem) == USE
3520               || GET_CODE (tem) == CLOBBER)
3521             continue;
3522
3523           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
3524             return 0;
3525         }
3526
3527       return 1;
3528     }
3529   return 0;
3530 }
3531
3532 /* Delete any insns that copy a register to itself.  */
3533
3534 static void
3535 delete_noop_moves (f)
3536      rtx f;
3537 {
3538   rtx insn;
3539   for (insn = f; insn; insn = NEXT_INSN (insn))
3540     {
3541       if (GET_CODE (insn) == INSN && noop_move_p (insn))
3542         {
3543           PUT_CODE (insn, NOTE);
3544           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
3545           NOTE_SOURCE_FILE (insn) = 0;
3546         }
3547     }
3548 }
3549
3550 /* Determine if the stack pointer is constant over the life of the function.
3551    Only useful before prologues have been emitted.  */
3552
3553 static void
3554 notice_stack_pointer_modification_1 (x, pat, data)
3555      rtx x;
3556      rtx pat ATTRIBUTE_UNUSED;
3557      void *data ATTRIBUTE_UNUSED;
3558 {
3559   if (x == stack_pointer_rtx
3560       /* The stack pointer is only modified indirectly as the result
3561          of a push until later in flow.  See the comments in rtl.texi
3562          regarding Embedded Side-Effects on Addresses.  */
3563       || (GET_CODE (x) == MEM
3564           && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == 'a'
3565           && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
3566     current_function_sp_is_unchanging = 0;
3567 }
3568
3569 static void
3570 notice_stack_pointer_modification (f)
3571      rtx f;
3572 {
3573   rtx insn;
3574
3575   /* Assume that the stack pointer is unchanging if alloca hasn't
3576      been used.  */
3577   current_function_sp_is_unchanging = !current_function_calls_alloca;
3578   if (! current_function_sp_is_unchanging)
3579     return;
3580
3581   for (insn = f; insn; insn = NEXT_INSN (insn))
3582     {
3583       if (INSN_P (insn))
3584         {
3585           /* Check if insn modifies the stack pointer.  */
3586           note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
3587                        NULL);
3588           if (! current_function_sp_is_unchanging)
3589             return;
3590         }
3591     }
3592 }
3593
3594 /* Mark a register in SET.  Hard registers in large modes get all
3595    of their component registers set as well.  */
3596
3597 static void
3598 mark_reg (reg, xset)
3599      rtx reg;
3600      void *xset;
3601 {
3602   regset set = (regset) xset;
3603   int regno = REGNO (reg);
3604
3605   if (GET_MODE (reg) == BLKmode)
3606     abort ();
3607
3608   SET_REGNO_REG_SET (set, regno);
3609   if (regno < FIRST_PSEUDO_REGISTER)
3610     {
3611       int n = HARD_REGNO_NREGS (regno, G