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 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
  23 /* This file contains the data flow analysis pass of the compiler.  It
  24    computes data flow information which tells combine_instructions
  25    which insns to consider combining and controls register allocation.
  26
  27    Additional data flow information that is too bulky to record is
  28    generated during the analysis, and is used at that time to create
  29    autoincrement and autodecrement addressing.
  30
  31    The first step is dividing the function into basic blocks.
  32    find_basic_blocks does this.  Then life_analysis determines
  33    where each register is live and where it is dead.
  34
  35    ** find_basic_blocks **
  36
  37    find_basic_blocks divides the current function's rtl into basic
  38    blocks and constructs the CFG.  The blocks are recorded in the
  39    basic_block_info array; the CFG exists in the edge structures
  40    referenced by the blocks.
  41
  42    find_basic_blocks also finds any unreachable loops and deletes them.
  43
  44    ** life_analysis **
  45
  46    life_analysis is called immediately after find_basic_blocks.
  47    It uses the basic block information to determine where each
  48    hard or pseudo register is live.
  49
  50    ** live-register info **
  51
  52    The information about where each register is live is in two parts:
  53    the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
  54
  55    basic_block->global_live_at_start has an element for each basic
  56    block, and the element is a bit-vector with a bit for each hard or
  57    pseudo register.  The bit is 1 if the register is live at the
  58    beginning of the basic block.
  59
  60    Two types of elements can be added to an insn's REG_NOTES.
  61    A REG_DEAD note is added to an insn's REG_NOTES for any register
  62    that meets both of two conditions:  The value in the register is not
  63    needed in subsequent insns and the insn does not replace the value in
  64    the register (in the case of multi-word hard registers, the value in
  65    each register must be replaced by the insn to avoid a REG_DEAD note).
  66
  67    In the vast majority of cases, an object in a REG_DEAD note will be
  68    used somewhere in the insn.  The (rare) exception to this is if an
  69    insn uses a multi-word hard register and only some of the registers are
  70    needed in subsequent insns.  In that case, REG_DEAD notes will be
  71    provided for those hard registers that are not subsequently needed.
  72    Partial REG_DEAD notes of this type do not occur when an insn sets
  73    only some of the hard registers used in such a multi-word operand;
  74    omitting REG_DEAD notes for objects stored in an insn is optional and
  75    the desire to do so does not justify the complexity of the partial
  76    REG_DEAD notes.
  77
  78    REG_UNUSED notes are added for each register that is set by the insn
  79    but is unused subsequently (if every register set by the insn is unused
  80    and the insn does not reference memory or have some other side-effect,
  81    the insn is deleted instead).  If only part of a multi-word hard
  82    register is used in a subsequent insn, REG_UNUSED notes are made for
  83    the parts that will not be used.
  84
  85    To determine which registers are live after any insn, one can
  86    start from the beginning of the basic block and scan insns, noting
  87    which registers are set by each insn and which die there.
  88
  89    ** Other actions of life_analysis **
  90
  91    life_analysis sets up the LOG_LINKS fields of insns because the
  92    information needed to do so is readily available.
  93
  94    life_analysis deletes insns whose only effect is to store a value
  95    that is never used.
  96
  97    life_analysis notices cases where a reference to a register as
  98    a memory address can be combined with a preceding or following
  99    incrementation or decrementation of the register.  The separate
 100    instruction to increment or decrement is deleted and the address
 101    is changed to a POST_INC or similar rtx.
 102
 103    Each time an incrementing or decrementing address is created,
 104    a REG_INC element is added to the insn's REG_NOTES list.
 105
 106    life_analysis fills in certain vectors containing information about
 107    register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
 108    REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
 109
 110    life_analysis sets current_function_sp_is_unchanging if the function
 111    doesn't modify the stack pointer.  */
 112
 113 /* TODO:
 114
 115    Split out from life_analysis:
 116         - local property discovery (bb->local_live, bb->local_set)
 117         - global property computation
 118         - log links creation
 119         - pre/post modify transformation
 120 */
 121 \f
 122 #include "config.h"
 123 #include "system.h"
 124 #include "tree.h"
 125 #include "rtl.h"
 126 #include "tm_p.h"
 127 #include "hard-reg-set.h"
 128 #include "basic-block.h"
 129 #include "insn-config.h"
 130 #include "regs.h"
 131 #include "flags.h"
 132 #include "output.h"
 133 #include "function.h"
 134 #include "except.h"
 135 #include "toplev.h"
 136 #include "recog.h"
 137 #include "insn-flags.h"
 138 #include "expr.h"
 139
 140 #include "obstack.h"
 141 #include "splay-tree.h"
 142
 143 #define obstack_chunk_alloc xmalloc
 144 #define obstack_chunk_free free
 145
 146
 147 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
 148    the stack pointer does not matter.  The value is tested only in
 149    functions that have frame pointers.
 150    No definition is equivalent to always zero.  */
 151 #ifndef EXIT_IGNORE_STACK
 152 #define EXIT_IGNORE_STACK 0
 153 #endif
 154
 155 #ifndef HAVE_epilogue
 156 #define HAVE_epilogue 0
 157 #endif
 158 #ifndef HAVE_prologue
 159 #define HAVE_prologue 0
 160 #endif
 161 #ifndef HAVE_sibcall_epilogue
 162 #define HAVE_sibcall_epilogue 0
 163 #endif
 164
 165 /* The contents of the current function definition are allocated
 166    in this obstack, and all are freed at the end of the function.
 167    For top-level functions, this is temporary_obstack.
 168    Separate obstacks are made for nested functions.  */
 169
 170 extern struct obstack *function_obstack;
 171
 172 /* Number of basic blocks in the current function.  */
 173
 174 int n_basic_blocks;
 175
 176 /* Number of edges in the current function.  */
 177
 178 int n_edges;
 179
 180 /* The basic block array.  */
 181
 182 varray_type basic_block_info;
 183
 184 /* The special entry and exit blocks.  */
 185
 186 struct basic_block_def entry_exit_blocks[2]
 187 = {{NULL,                       /* head */
 188     NULL,                       /* end */
 189     NULL,                       /* pred */
 190     NULL,                       /* succ */
 191     NULL,                       /* local_set */
 192     NULL,                       /* global_live_at_start */
 193     NULL,                       /* global_live_at_end */
 194     NULL,                       /* aux */
 195     ENTRY_BLOCK,                /* index */
 196     0,                          /* loop_depth */
 197     -1, -1,                     /* eh_beg, eh_end */
 198     0                           /* count */
 199   },
 200   {
 201     NULL,                       /* head */
 202     NULL,                       /* end */
 203     NULL,                       /* pred */
 204     NULL,                       /* succ */
 205     NULL,                       /* local_set */
 206     NULL,                       /* global_live_at_start */
 207     NULL,                       /* global_live_at_end */
 208     NULL,                       /* aux */
 209     EXIT_BLOCK,                 /* index */
 210     0,                          /* loop_depth */
 211     -1, -1,                     /* eh_beg, eh_end */
 212     0                           /* count */
 213   }
 214 };
 215
 216 /* Nonzero if the second flow pass has completed.  */
 217 int flow2_completed;
 218
 219 /* Maximum register number used in this function, plus one.  */
 220
 221 int max_regno;
 222
 223 /* Indexed by n, giving various register information */
 224
 225 varray_type reg_n_info;
 226
 227 /* Size of a regset for the current function,
 228    in (1) bytes and (2) elements.  */
 229
 230 int regset_bytes;
 231 int regset_size;
 232
 233 /* Regset of regs live when calls to `setjmp'-like functions happen.  */
 234 /* ??? Does this exist only for the setjmp-clobbered warning message?  */
 235
 236 regset regs_live_at_setjmp;
 237
 238 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
 239    that have to go in the same hard reg.
 240    The first two regs in the list are a pair, and the next two
 241    are another pair, etc.  */
 242 rtx regs_may_share;
 243
 244 /* Set of registers that may be eliminable.  These are handled specially
 245    in updating regs_ever_live.  */
 246
 247 static HARD_REG_SET elim_reg_set;
 248
 249 /* The basic block structure for every insn, indexed by uid.  */
 250
 251 varray_type basic_block_for_insn;
 252
 253 /* The labels mentioned in non-jump rtl.  Valid during find_basic_blocks.  */
 254 /* ??? Should probably be using LABEL_NUSES instead.  It would take a
 255    bit of surgery to be able to use or co-opt the routines in jump.  */
 256
 257 static rtx label_value_list;
 258 static rtx tail_recursion_label_list;
 259
 260 /* Holds information for tracking conditional register life information.  */
 261 struct reg_cond_life_info
 262 {
 263   /* An EXPR_LIST of conditions under which a register is dead.  */
 264   rtx condition;
 265
 266   /* ??? Could store mask of bytes that are dead, so that we could finally
 267      track lifetimes of multi-word registers accessed via subregs.  */
 268 };
 269
 270 /* For use in communicating between propagate_block and its subroutines.
 271    Holds all information needed to compute life and def-use information.  */
 272
 273 struct propagate_block_info
 274 {
 275   /* The basic block we're considering.  */
 276   basic_block bb;
 277
 278   /* Bit N is set if register N is conditionally or unconditionally live.  */
 279   regset reg_live;
 280
 281   /* Bit N is set if register N is set this insn.  */
 282   regset new_set;
 283
 284   /* Element N is the next insn that uses (hard or pseudo) register N
 285      within the current basic block; or zero, if there is no such insn.  */
 286   rtx *reg_next_use;
 287
 288   /* Contains a list of all the MEMs we are tracking for dead store
 289      elimination.  */
 290   rtx mem_set_list;
 291
 292   /* If non-null, record the set of registers set in the basic block.  */
 293   regset local_set;
 294
 295 #ifdef HAVE_conditional_execution
 296   /* Indexed by register number, holds a reg_cond_life_info for each
 297      register that is not unconditionally live or dead.  */
 298   splay_tree reg_cond_dead;
 299
 300   /* Bit N is set if register N is in an expression in reg_cond_dead.  */
 301   regset reg_cond_reg;
 302 #endif
 303
 304   /* Non-zero if the value of CC0 is live.  */
 305   int cc0_live;
 306
 307   /* Flags controling the set of information propagate_block collects.  */
 308   int flags;
 309 };
 310
 311 /* Forward declarations */
 312 static int count_basic_blocks           PARAMS ((rtx));
 313 static void find_basic_blocks_1         PARAMS ((rtx));
 314 static rtx find_label_refs              PARAMS ((rtx, rtx));
 315 static void clear_edges                 PARAMS ((void));
 316 static void make_edges                  PARAMS ((rtx));
 317 static void make_label_edge             PARAMS ((sbitmap *, basic_block,
 318                                                  rtx, int));
 319 static void make_eh_edge                PARAMS ((sbitmap *, eh_nesting_info *,
 320                                                  basic_block, rtx, int));
 321 static void mark_critical_edges         PARAMS ((void));
 322 static void move_stray_eh_region_notes  PARAMS ((void));
 323 static void record_active_eh_regions    PARAMS ((rtx));
 324
 325 static void commit_one_edge_insertion   PARAMS ((edge));
 326
 327 static void delete_unreachable_blocks   PARAMS ((void));
 328 static void delete_eh_regions           PARAMS ((void));
 329 static int can_delete_note_p            PARAMS ((rtx));
 330 static void expunge_block               PARAMS ((basic_block));
 331 static int can_delete_label_p           PARAMS ((rtx));
 332 static int tail_recursion_label_p       PARAMS ((rtx));
 333 static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
 334                                                           basic_block));
 335 static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
 336                                                         basic_block));
 337 static int merge_blocks                 PARAMS ((edge,basic_block,basic_block));
 338 static void try_merge_blocks            PARAMS ((void));
 339 static void tidy_fallthru_edges         PARAMS ((void));
 340 static int verify_wide_reg_1            PARAMS ((rtx *, void *));
 341 static void verify_wide_reg             PARAMS ((int, rtx, rtx));
 342 static void verify_local_live_at_start  PARAMS ((regset, basic_block));
 343 static int set_noop_p                   PARAMS ((rtx));
 344 static int noop_move_p                  PARAMS ((rtx));
 345 static void delete_noop_moves           PARAMS ((rtx));
 346 static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
 347 static void notice_stack_pointer_modification PARAMS ((rtx));
 348 static void mark_reg                    PARAMS ((rtx, void *));
 349 static void mark_regs_live_at_end       PARAMS ((regset));
 350 static int set_phi_alternative_reg      PARAMS ((rtx, int, int, void *));
 351 static void calculate_global_regs_live  PARAMS ((sbitmap, sbitmap, int));
 352 static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
 353 static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
 354 static int insn_dead_p                  PARAMS ((struct propagate_block_info *,
 355                                                  rtx, int, rtx));
 356 static int libcall_dead_p               PARAMS ((struct propagate_block_info *,
 357                                                  rtx, rtx, rtx));
 358 static void mark_set_regs               PARAMS ((struct propagate_block_info *,
 359                                                  rtx, rtx));
 360 static void mark_set_1                  PARAMS ((struct propagate_block_info *,
 361                                                  enum rtx_code, rtx, rtx,
 362                                                  rtx, int));
 363 #ifdef HAVE_conditional_execution
 364 static int mark_regno_cond_dead         PARAMS ((struct propagate_block_info *,
 365                                                  int, rtx));
 366 static void free_reg_cond_life_info     PARAMS ((splay_tree_value));
 367 static int flush_reg_cond_reg_1         PARAMS ((splay_tree_node, void *));
 368 static void flush_reg_cond_reg          PARAMS ((struct propagate_block_info *,
 369                                                  int));
 370 static rtx ior_reg_cond                 PARAMS ((rtx, rtx));
 371 static rtx not_reg_cond                 PARAMS ((rtx));
 372 static rtx nand_reg_cond                PARAMS ((rtx, rtx));
 373 #endif
 374 #ifdef AUTO_INC_DEC
 375 static void find_auto_inc               PARAMS ((struct propagate_block_info *,
 376                                                  rtx, rtx));
 377 static int try_pre_increment_1          PARAMS ((struct propagate_block_info *,
 378                                                  rtx));
 379 static int try_pre_increment            PARAMS ((rtx, rtx, HOST_WIDE_INT));
 380 #endif
 381 static void mark_used_reg               PARAMS ((struct propagate_block_info *,
 382                                                  rtx, rtx, rtx));
 383 static void mark_used_regs              PARAMS ((struct propagate_block_info *,
 384                                                  rtx, rtx, rtx));
 385 void dump_flow_info                     PARAMS ((FILE *));
 386 void debug_flow_info                    PARAMS ((void));
 387 static void dump_edge_info              PARAMS ((FILE *, edge, int));
 388
 389 static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
 390                                                   rtx));
 391 static void remove_fake_successors      PARAMS ((basic_block));
 392 static void flow_nodes_print    PARAMS ((const char *, const sbitmap, FILE *));
 393 static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
 394 static void flow_loops_cfg_dump         PARAMS ((const struct loops *, FILE *));
 395 static int flow_loop_nested_p           PARAMS ((struct loop *, struct loop *));
 396 static int flow_loop_exits_find         PARAMS ((const sbitmap, edge **));
 397 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
 398 static int flow_depth_first_order_compute PARAMS ((int *));
 399 static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
 400 static void flow_loop_tree_node_add     PARAMS ((struct loop *, struct loop *));
 401 static void flow_loops_tree_build       PARAMS ((struct loops *));
 402 static int flow_loop_level_compute      PARAMS ((struct loop *, int));
 403 static int flow_loops_level_compute     PARAMS ((struct loops *));
 404 \f
 405 /* Find basic blocks of the current function.
 406    F is the first insn of the function and NREGS the number of register
 407    numbers in use.  */
 408
 409 void
 410 find_basic_blocks (f, nregs, file)
 411      rtx f;
 412      int nregs ATTRIBUTE_UNUSED;
 413      FILE *file ATTRIBUTE_UNUSED;
 414 {
 415   int max_uid;
 416
 417   /* Flush out existing data.  */
 418   if (basic_block_info != NULL)
 419     {
 420       int i;
 421
 422       clear_edges ();
 423
 424       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 425          tag for reuse during create_basic_block, just in case some pass
 426          copies around basic block notes improperly.  */
 427       for (i = 0; i < n_basic_blocks; ++i)
 428         BASIC_BLOCK (i)->aux = NULL;
 429
 430       VARRAY_FREE (basic_block_info);
 431     }
 432
 433   n_basic_blocks = count_basic_blocks (f);
 434
 435   /* Size the basic block table.  The actual structures will be allocated
 436      by find_basic_blocks_1, since we want to keep the structure pointers
 437      stable across calls to find_basic_blocks.  */
 438   /* ??? This whole issue would be much simpler if we called find_basic_blocks
 439      exactly once, and thereafter we don't have a single long chain of
 440      instructions at all until close to the end of compilation when we
 441      actually lay them out.  */
 442
 443   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 444
 445   find_basic_blocks_1 (f);
 446
 447   /* Record the block to which an insn belongs.  */
 448   /* ??? This should be done another way, by which (perhaps) a label is
 449      tagged directly with the basic block that it starts.  It is used for
 450      more than that currently, but IMO that is the only valid use.  */
 451
 452   max_uid = get_max_uid ();
 453 #ifdef AUTO_INC_DEC
 454   /* Leave space for insns life_analysis makes in some cases for auto-inc.
 455      These cases are rare, so we don't need too much space.  */
 456   max_uid += max_uid / 10;
 457 #endif
 458
 459   compute_bb_for_insn (max_uid);
 460
 461   /* Discover the edges of our cfg.  */
 462   record_active_eh_regions (f);
 463   make_edges (label_value_list);
 464
 465   /* Do very simple cleanup now, for the benefit of code that runs between
 466      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 467   tidy_fallthru_edges ();
 468
 469   mark_critical_edges ();
 470
 471 #ifdef ENABLE_CHECKING
 472   verify_flow_info ();
 473 #endif
 474 }
 475
 476 /* Count the basic blocks of the function.  */
 477
 478 static int
 479 count_basic_blocks (f)
 480      rtx f;
 481 {
 482   register rtx insn;
 483   register RTX_CODE prev_code;
 484   register int count = 0;
 485   int eh_region = 0;
 486   int call_had_abnormal_edge = 0;
 487
 488   prev_code = JUMP_INSN;
 489   for (insn = f; insn; insn = NEXT_INSN (insn))
 490     {
 491       register RTX_CODE code = GET_CODE (insn);
 492
 493       if (code == CODE_LABEL
 494           || (GET_RTX_CLASS (code) == 'i'
 495               && (prev_code == JUMP_INSN
 496                   || prev_code == BARRIER
 497                   || (prev_code == CALL_INSN && call_had_abnormal_edge))))
 498         count++;
 499
 500       /* Record whether this call created an edge.  */
 501       if (code == CALL_INSN)
 502         {
 503           rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
 504           int region = (note ? INTVAL (XEXP (note, 0)) : 1);
 505
 506           call_had_abnormal_edge = 0;
 507
 508           /* If there is an EH region or rethrow, we have an edge.  */
 509           if ((eh_region && region > 0)
 510               || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
 511             call_had_abnormal_edge = 1;
 512           else if (nonlocal_goto_handler_labels && region >= 0)
 513             /* If there is a nonlocal goto label and the specified
 514                region number isn't -1, we have an edge. (0 means
 515                no throw, but might have a nonlocal goto).  */
 516             call_had_abnormal_edge = 1;
 517         }
 518
 519       if (code != NOTE)
 520         prev_code = code;
 521       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
 522         ++eh_region;
 523       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
 524         --eh_region;
 525     }
 526
 527   /* The rest of the compiler works a bit smoother when we don't have to
 528      check for the edge case of do-nothing functions with no basic blocks.  */
 529   if (count == 0)
 530     {
 531       emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
 532       count = 1;
 533     }
 534
 535   return count;
 536 }
 537
 538 /* Scan a list of insns for labels referrred to other than by jumps.
 539    This is used to scan the alternatives of a call placeholder.  */
 540 static rtx find_label_refs (f, lvl)
 541      rtx f;
 542      rtx lvl;
 543 {
 544   rtx insn;
 545
 546   for (insn = f; insn; insn = NEXT_INSN (insn))
 547     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 548       {
 549         rtx note;
 550
 551         /* Make a list of all labels referred to other than by jumps
 552            (which just don't have the REG_LABEL notes).
 553
 554            Make a special exception for labels followed by an ADDR*VEC,
 555            as this would be a part of the tablejump setup code.
 556
 557            Make a special exception for the eh_return_stub_label, which
 558            we know isn't part of any otherwise visible control flow.  */
 559
 560         for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 561           if (REG_NOTE_KIND (note) == REG_LABEL)
 562             {
 563               rtx lab = XEXP (note, 0), next;
 564
 565               if (lab == eh_return_stub_label)
 566                 ;
 567               else if ((next = next_nonnote_insn (lab)) != NULL
 568                        && GET_CODE (next) == JUMP_INSN
 569                        && (GET_CODE (PATTERN (next)) == ADDR_VEC
 570                            || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
 571                 ;
 572               else if (GET_CODE (lab) == NOTE)
 573                 ;
 574               else
 575                 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
 576             }
 577       }
 578
 579   return lvl;
 580 }
 581
 582 /* Find all basic blocks of the function whose first insn is F.
 583
 584    Collect and return a list of labels whose addresses are taken.  This
 585    will be used in make_edges for use with computed gotos.  */
 586
 587 static void
 588 find_basic_blocks_1 (f)
 589      rtx f;
 590 {
 591   register rtx insn, next;
 592   int i = 0;
 593   rtx bb_note = NULL_RTX;
 594   rtx eh_list = NULL_RTX;
 595   rtx lvl = NULL_RTX;
 596   rtx trll = NULL_RTX;
 597   rtx head = NULL_RTX;
 598   rtx end = NULL_RTX;
 599
 600   /* We process the instructions in a slightly different way than we did
 601      previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
 602      closed out the previous block, so that it gets attached at the proper
 603      place.  Since this form should be equivalent to the previous,
 604      count_basic_blocks continues to use the old form as a check.  */
 605
 606   for (insn = f; insn; insn = next)
 607     {
 608       enum rtx_code code = GET_CODE (insn);
 609
 610       next = NEXT_INSN (insn);
 611
 612       switch (code)
 613         {
 614         case NOTE:
 615           {
 616             int kind = NOTE_LINE_NUMBER (insn);
 617
 618             /* Keep a LIFO list of the currently active exception notes.  */
 619             if (kind == NOTE_INSN_EH_REGION_BEG)
 620               eh_list = alloc_INSN_LIST (insn, eh_list);
 621             else if (kind == NOTE_INSN_EH_REGION_END)
 622               {
 623                 rtx t = eh_list;
 624
 625                 eh_list = XEXP (eh_list, 1);
 626                 free_INSN_LIST_node (t);
 627               }
 628
 629             /* Look for basic block notes with which to keep the
 630                basic_block_info pointers stable.  Unthread the note now;
 631                we'll put it back at the right place in create_basic_block.
 632                Or not at all if we've already found a note in this block.  */
 633             else if (kind == NOTE_INSN_BASIC_BLOCK)
 634               {
 635                 if (bb_note == NULL_RTX)
 636                   bb_note = insn;
 637                 else
 638                   next = flow_delete_insn (insn);
 639               }
 640             break;
 641           }
 642
 643         case CODE_LABEL:
 644           /* A basic block starts at a label.  If we've closed one off due
 645              to a barrier or some such, no need to do it again.  */
 646           if (head != NULL_RTX)
 647             {
 648               /* While we now have edge lists with which other portions of
 649                  the compiler might determine a call ending a basic block
 650                  does not imply an abnormal edge, it will be a bit before
 651                  everything can be updated.  So continue to emit a noop at
 652                  the end of such a block.  */
 653               if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
 654                 {
 655                   rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
 656                   end = emit_insn_after (nop, end);
 657                 }
 658
 659               create_basic_block (i++, head, end, bb_note);
 660               bb_note = NULL_RTX;
 661             }
 662
 663           head = end = insn;
 664           break;
 665
 666         case JUMP_INSN:
 667           /* A basic block ends at a jump.  */
 668           if (head == NULL_RTX)
 669             head = insn;
 670           else
 671             {
 672               /* ??? Make a special check for table jumps.  The way this
 673                  happens is truly and amazingly gross.  We are about to
 674                  create a basic block that contains just a code label and
 675                  an addr*vec jump insn.  Worse, an addr_diff_vec creates
 676                  its own natural loop.
 677
 678                  Prevent this bit of brain damage, pasting things together
 679                  correctly in make_edges.
 680
 681                  The correct solution involves emitting the table directly
 682                  on the tablejump instruction as a note, or JUMP_LABEL.  */
 683
 684               if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 685                   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 686                 {
 687                   head = end = NULL;
 688                   n_basic_blocks--;
 689                   break;
 690                 }
 691             }
 692           end = insn;
 693           goto new_bb_inclusive;
 694
 695         case BARRIER:
 696           /* A basic block ends at a barrier.  It may be that an unconditional
 697              jump already closed the basic block -- no need to do it again.  */
 698           if (head == NULL_RTX)
 699             break;
 700
 701           /* While we now have edge lists with which other portions of the
 702              compiler might determine a call ending a basic block does not
 703              imply an abnormal edge, it will be a bit before everything can
 704              be updated.  So continue to emit a noop at the end of such a
 705              block.  */
 706           if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
 707             {
 708               rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
 709               end = emit_insn_after (nop, end);
 710             }
 711           goto new_bb_exclusive;
 712
 713         case CALL_INSN:
 714           {
 715             /* Record whether this call created an edge.  */
 716             rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
 717             int region = (note ? INTVAL (XEXP (note, 0)) : 1);
 718             int call_has_abnormal_edge = 0;
 719
 720             if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 721               {
 722                 /* Scan each of the alternatives for label refs.  */
 723                 lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
 724                 lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
 725                 lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
 726                 /* Record its tail recursion label, if any.  */
 727                 if (XEXP (PATTERN (insn), 3) != NULL_RTX)
 728                   trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
 729               }
 730
 731             /* If there is an EH region or rethrow, we have an edge.  */
 732             if ((eh_list && region > 0)
 733                 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
 734               call_has_abnormal_edge = 1;
 735             else if (nonlocal_goto_handler_labels && region >= 0)
 736               /* If there is a nonlocal goto label and the specified
 737                  region number isn't -1, we have an edge. (0 means
 738                  no throw, but might have a nonlocal goto).  */
 739               call_has_abnormal_edge = 1;
 740
 741             /* A basic block ends at a call that can either throw or
 742                do a non-local goto.  */
 743             if (call_has_abnormal_edge)
 744               {
 745               new_bb_inclusive:
 746                 if (head == NULL_RTX)
 747                   head = insn;
 748                 end = insn;
 749
 750               new_bb_exclusive:
 751                 create_basic_block (i++, head, end, bb_note);
 752                 head = end = NULL_RTX;
 753                 bb_note = NULL_RTX;
 754                 break;
 755               }
 756             }
 757           /* FALLTHRU */
 758
 759         default:
 760           if (GET_RTX_CLASS (code) == 'i')
 761             {
 762               if (head == NULL_RTX)
 763                 head = insn;
 764               end = insn;
 765             }
 766           break;
 767         }
 768
 769       if (GET_RTX_CLASS (code) == 'i')
 770         {
 771           rtx note;
 772
 773           /* Make a list of all labels referred to other than by jumps
 774              (which just don't have the REG_LABEL notes).
 775
 776              Make a special exception for labels followed by an ADDR*VEC,
 777              as this would be a part of the tablejump setup code.
 778
 779              Make a special exception for the eh_return_stub_label, which
 780              we know isn't part of any otherwise visible control flow.  */
 781
 782           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 783             if (REG_NOTE_KIND (note) == REG_LABEL)
 784               {
 785                 rtx lab = XEXP (note, 0), next;
 786
 787                 if (lab == eh_return_stub_label)
 788                   ;
 789                 else if ((next = next_nonnote_insn (lab)) != NULL
 790                          && GET_CODE (next) == JUMP_INSN
 791                          && (GET_CODE (PATTERN (next)) == ADDR_VEC
 792                              || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
 793                   ;
 794                 else if (GET_CODE (lab) == NOTE)
 795                   ;
 796                 else
 797                   lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
 798               }
 799         }
 800     }
 801
 802   if (head != NULL_RTX)
 803     create_basic_block (i++, head, end, bb_note);
 804   else if (bb_note)
 805     flow_delete_insn (bb_note);
 806
 807   if (i != n_basic_blocks)
 808     abort ();
 809
 810   label_value_list = lvl;
 811   tail_recursion_label_list = trll;
 812 }
 813
 814 /* Tidy the CFG by deleting unreachable code and whatnot.  */
 815
 816 void
 817 cleanup_cfg (f)
 818      rtx f;
 819 {
 820   delete_unreachable_blocks ();
 821   move_stray_eh_region_notes ();
 822   record_active_eh_regions (f);
 823   try_merge_blocks ();
 824   mark_critical_edges ();
 825
 826   /* Kill the data we won't maintain.  */
 827   free_EXPR_LIST_list (&label_value_list);
 828   free_EXPR_LIST_list (&tail_recursion_label_list);
 829 }
 830
 831 /* Create a new basic block consisting of the instructions between
 832    HEAD and END inclusive.  Reuses the note and basic block struct
 833    in BB_NOTE, if any.  */
 834
 835 void
 836 create_basic_block (index, head, end, bb_note)
 837      int index;
 838      rtx head, end, bb_note;
 839 {
 840   basic_block bb;
 841
 842   if (bb_note
 843       && ! RTX_INTEGRATED_P (bb_note)
 844       && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
 845       && bb->aux == NULL)
 846     {
 847       /* If we found an existing note, thread it back onto the chain.  */
 848
 849       rtx after;
 850
 851       if (GET_CODE (head) == CODE_LABEL)
 852         after = head;
 853       else
 854         {
 855           after = PREV_INSN (head);
 856           head = bb_note;
 857         }
 858
 859       if (after != bb_note && NEXT_INSN (after) != bb_note)
 860         reorder_insns (bb_note, bb_note, after);
 861     }
 862   else
 863     {
 864       /* Otherwise we must create a note and a basic block structure.
 865          Since we allow basic block structs in rtl, give the struct
 866          the same lifetime by allocating it off the function obstack
 867          rather than using malloc.  */
 868
 869       bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
 870       memset (bb, 0, sizeof (*bb));
 871
 872       if (GET_CODE (head) == CODE_LABEL)
 873         bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
 874       else
 875         {
 876           bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
 877           head = bb_note;
 878         }
 879       NOTE_BASIC_BLOCK (bb_note) = bb;
 880     }
 881
 882   /* Always include the bb note in the block.  */
 883   if (NEXT_INSN (end) == bb_note)
 884     end = bb_note;
 885
 886   bb->head = head;
 887   bb->end = end;
 888   bb->index = index;
 889   BASIC_BLOCK (index) = bb;
 890
 891   /* Tag the block so that we know it has been used when considering
 892      other basic block notes.  */
 893   bb->aux = bb;
 894 }
 895 \f
 896 /* Records the basic block struct in BB_FOR_INSN, for every instruction
 897    indexed by INSN_UID.  MAX is the size of the array.  */
 898
 899 void
 900 compute_bb_for_insn (max)
 901      int max;
 902 {
 903   int i;
 904
 905   if (basic_block_for_insn)
 906     VARRAY_FREE (basic_block_for_insn);
 907   VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
 908
 909   for (i = 0; i < n_basic_blocks; ++i)
 910     {
 911       basic_block bb = BASIC_BLOCK (i);
 912       rtx insn, end;
 913
 914       end = bb->end;
 915       insn = bb->head;
 916       while (1)
 917         {
 918           int uid = INSN_UID (insn);
 919           if (uid < max)
 920             VARRAY_BB (basic_block_for_insn, uid) = bb;
 921           if (insn == end)
 922             break;
 923           insn = NEXT_INSN (insn);
 924         }
 925     }
 926 }
 927
 928 /* Free the memory associated with the edge structures.  */
 929
 930 static void
 931 clear_edges ()
 932 {
 933   int i;
 934   edge n, e;
 935
 936   for (i = 0; i < n_basic_blocks; ++i)
 937     {
 938       basic_block bb = BASIC_BLOCK (i);
 939
 940       for (e = bb->succ; e ; e = n)
 941         {
 942           n = e->succ_next;
 943           free (e);
 944         }
 945
 946       bb->succ = 0;
 947       bb->pred = 0;
 948     }
 949
 950   for (e = ENTRY_BLOCK_PTR->succ; e ; e = n)
 951     {
 952       n = e->succ_next;
 953       free (e);
 954     }
 955
 956   ENTRY_BLOCK_PTR->succ = 0;
 957   EXIT_BLOCK_PTR->pred = 0;
 958
 959   n_edges = 0;
 960 }
 961
 962 /* Identify the edges between basic blocks.
 963
 964    NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
 965    that are otherwise unreachable may be reachable with a non-local goto.
 966
 967    BB_EH_END is an array indexed by basic block number in which we record
 968    the list of exception regions active at the end of the basic block.  */
 969
 970 static void
 971 make_edges (label_value_list)
 972      rtx label_value_list;
 973 {
 974   int i;
 975   eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
 976   sbitmap *edge_cache = NULL;
 977
 978   /* Assume no computed jump; revise as we create edges.  */
 979   current_function_has_computed_jump = 0;
 980
 981   /* Heavy use of computed goto in machine-generated code can lead to
 982      nearly fully-connected CFGs.  In that case we spend a significant
 983      amount of time searching the edge lists for duplicates.  */
 984   if (forced_labels || label_value_list)
 985     {
 986       edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 987       sbitmap_vector_zero (edge_cache, n_basic_blocks);
 988     }
 989
 990   /* By nature of the way these get numbered, block 0 is always the entry.  */
 991   make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
 992
 993   for (i = 0; i < n_basic_blocks; ++i)
 994     {
 995       basic_block bb = BASIC_BLOCK (i);
 996       rtx insn, x;
 997       enum rtx_code code;
 998       int force_fallthru = 0;
 999
1000       /* Examine the last instruction of the block, and discover the
1001          ways we can leave the block.  */
1002
1003       insn = bb->end;
1004       code = GET_CODE (insn);
1005
1006       /* A branch.  */
1007       if (code == JUMP_INSN)
1008         {
1009           rtx tmp;
1010
1011           /* ??? Recognize a tablejump and do the right thing.  */
1012           if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1013               && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1014               && GET_CODE (tmp) == JUMP_INSN
1015               && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1016                   || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1017             {
1018               rtvec vec;
1019               int j;
1020
1021               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1022                 vec = XVEC (PATTERN (tmp), 0);
1023               else
1024                 vec = XVEC (PATTERN (tmp), 1);
1025
1026               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1027                 make_label_edge (edge_cache, bb,
1028                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
1029
1030               /* Some targets (eg, ARM) emit a conditional jump that also
1031                  contains the out-of-range target.  Scan for these and
1032                  add an edge if necessary.  */
1033               if ((tmp = single_set (insn)) != NULL
1034                   && SET_DEST (tmp) == pc_rtx
1035                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1036                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
1037                 make_label_edge (edge_cache, bb,
1038                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
1039
1040 #ifdef CASE_DROPS_THROUGH
1041               /* Silly VAXen.  The ADDR_VEC is going to be in the way of
1042                  us naturally detecting fallthru into the next block.  */
1043               force_fallthru = 1;
1044 #endif
1045             }
1046
1047           /* If this is a computed jump, then mark it as reaching
1048              everything on the label_value_list and forced_labels list.  */
1049           else if (computed_jump_p (insn))
1050             {
1051               current_function_has_computed_jump = 1;
1052
1053               for (x = label_value_list; x; x = XEXP (x, 1))
1054                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1055
1056               for (x = forced_labels; x; x = XEXP (x, 1))
1057                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1058             }
1059
1060           /* Returns create an exit out.  */
1061           else if (returnjump_p (insn))
1062             make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
1063
1064           /* Otherwise, we have a plain conditional or unconditional jump.  */
1065           else
1066             {
1067               if (! JUMP_LABEL (insn))
1068                 abort ();
1069               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
1070             }
1071         }
1072
1073       /* If this is a sibling call insn, then this is in effect a
1074          combined call and return, and so we need an edge to the
1075          exit block.  No need to worry about EH edges, since we
1076          wouldn't have created the sibling call in the first place.  */
1077
1078       if (code == CALL_INSN && SIBLING_CALL_P (insn))
1079         make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
1080                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1081       else
1082
1083       /* If this is a CALL_INSN, then mark it as reaching the active EH
1084          handler for this CALL_INSN.  If we're handling asynchronous
1085          exceptions then any insn can reach any of the active handlers.
1086
1087          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
1088
1089       if (code == CALL_INSN || asynchronous_exceptions)
1090         {
1091           /* Add any appropriate EH edges.  We do this unconditionally
1092              since there may be a REG_EH_REGION or REG_EH_RETHROW note
1093              on the call, and this needn't be within an EH region.  */
1094           make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
1095
1096           /* If we have asynchronous exceptions, do the same for *all*
1097              exception regions active in the block.  */
1098           if (asynchronous_exceptions
1099               && bb->eh_beg != bb->eh_end)
1100             {
1101               if (bb->eh_beg >= 0)
1102                 make_eh_edge (edge_cache, eh_nest_info, bb,
1103                               NULL_RTX, bb->eh_beg);
1104
1105               for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
1106                 if (GET_CODE (x) == NOTE
1107                     && (NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_BEG
1108                         || NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
1109                   {
1110                     int region = NOTE_EH_HANDLER (x);
1111                     make_eh_edge (edge_cache, eh_nest_info, bb,
1112                                   NULL_RTX, region);
1113                   }
1114             }
1115
1116           if (code == CALL_INSN && nonlocal_goto_handler_labels)
1117             {
1118               /* ??? This could be made smarter: in some cases it's possible
1119                  to tell that certain calls will not do a nonlocal goto.
1120
1121                  For example, if the nested functions that do the nonlocal
1122                  gotos do not have their addresses taken, then only calls to
1123                  those functions or to other nested functions that use them
1124                  could possibly do nonlocal gotos.  */
1125               /* We do know that a REG_EH_REGION note with a value less
1126                  than 0 is guaranteed not to perform a non-local goto.  */
1127               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1128               if (!note || INTVAL (XEXP (note, 0)) >=  0)
1129                 for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
1130                   make_label_edge (edge_cache, bb, XEXP (x, 0),
1131                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1132             }
1133         }
1134
1135       /* We know something about the structure of the function __throw in
1136          libgcc2.c.  It is the only function that ever contains eh_stub
1137          labels.  It modifies its return address so that the last block
1138          returns to one of the eh_stub labels within it.  So we have to
1139          make additional edges in the flow graph.  */
1140       if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
1141         make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH);
1142
1143       /* Find out if we can drop through to the next block.  */
1144       insn = next_nonnote_insn (insn);
1145       if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
1146         make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1147       else if (i + 1 < n_basic_blocks)
1148         {
1149           rtx tmp = BLOCK_HEAD (i + 1);
1150           if (GET_CODE (tmp) == NOTE)
1151             tmp = next_nonnote_insn (tmp);
1152           if (force_fallthru || insn == tmp)
1153             make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
1154         }
1155     }
1156
1157   free_eh_nesting_info (eh_nest_info);
1158   if (edge_cache)
1159     sbitmap_vector_free (edge_cache);
1160 }
1161
1162 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
1163    about the edge that is accumulated between calls.  */
1164
1165 void
1166 make_edge (edge_cache, src, dst, flags)
1167      sbitmap *edge_cache;
1168      basic_block src, dst;
1169      int flags;
1170 {
1171   int use_edge_cache;
1172   edge e;
1173
1174   /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1175      many edges to them, and we didn't allocate memory for it.  */
1176   use_edge_cache = (edge_cache
1177                     && src != ENTRY_BLOCK_PTR
1178                     && dst != EXIT_BLOCK_PTR);
1179
1180   /* Make sure we don't add duplicate edges.  */
1181   if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
1182     for (e = src->succ; e ; e = e->succ_next)
1183       if (e->dest == dst)
1184         {
1185           e->flags |= flags;
1186           return;
1187         }
1188
1189   e = (edge) xcalloc (1, sizeof (*e));
1190   n_edges++;
1191
1192   e->succ_next = src->succ;
1193   e->pred_next = dst->pred;
1194   e->src = src;
1195   e->dest = dst;
1196   e->flags = flags;
1197
1198   src->succ = e;
1199   dst->pred = e;
1200
1201   if (use_edge_cache)
1202     SET_BIT (edge_cache[src->index], dst->index);
1203 }
1204
1205 /* Create an edge from a basic block to a label.  */
1206
1207 static void
1208 make_label_edge (edge_cache, src, label, flags)
1209      sbitmap *edge_cache;
1210      basic_block src;
1211      rtx label;
1212      int flags;
1213 {
1214   if (GET_CODE (label) != CODE_LABEL)
1215     abort ();
1216
1217   /* If the label was never emitted, this insn is junk, but avoid a
1218      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
1219      as a result of a syntax error and a diagnostic has already been
1220      printed.  */
1221
1222   if (INSN_UID (label) == 0)
1223     return;
1224
1225   make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
1226 }
1227
1228 /* Create the edges generated by INSN in REGION.  */
1229
1230 static void
1231 make_eh_edge (edge_cache, eh_nest_info, src, insn, region)
1232      sbitmap *edge_cache;
1233      eh_nesting_info *eh_nest_info;
1234      basic_block src;
1235      rtx insn;
1236      int region;
1237 {
1238   handler_info **handler_list;
1239   int num, is_call;
1240
1241   is_call = (insn && GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
1242   num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
1243   while (--num >= 0)
1244     {
1245       make_label_edge (edge_cache, src, handler_list[num]->handler_label,
1246                        EDGE_ABNORMAL | EDGE_EH | is_call);
1247     }
1248 }
1249
1250 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1251    dangerous if we intend to move basic blocks around.  Move such notes
1252    into the following block.  */
1253
1254 static void
1255 move_stray_eh_region_notes ()
1256 {
1257   int i;
1258   basic_block b1, b2;
1259
1260   if (n_basic_blocks < 2)
1261     return;
1262
1263   b2 = BASIC_BLOCK (n_basic_blocks - 1);
1264   for (i = n_basic_blocks - 2; i >= 0; --i, b2 = b1)
1265     {
1266       rtx insn, next, list = NULL_RTX;
1267
1268       b1 = BASIC_BLOCK (i);
1269       for (insn = NEXT_INSN (b1->end); insn != b2->head; insn = next)
1270         {
1271           next = NEXT_INSN (insn);
1272           if (GET_CODE (insn) == NOTE
1273               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1274                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1275             {
1276               /* Unlink from the insn chain.  */
1277               NEXT_INSN (PREV_INSN (insn)) = next;
1278               PREV_INSN (next) = PREV_INSN (insn);
1279
1280               /* Queue it.  */
1281               NEXT_INSN (insn) = list;
1282               list = insn;
1283             }
1284         }
1285
1286       if (list == NULL_RTX)
1287         continue;
1288
1289       /* Find where to insert these things.  */
1290       insn = b2->head;
1291       if (GET_CODE (insn) == CODE_LABEL)
1292         insn = NEXT_INSN (insn);
1293
1294       while (list)
1295         {
1296           next = NEXT_INSN (list);
1297           add_insn_after (list, insn);
1298           list = next;
1299         }
1300     }
1301 }
1302
1303 /* Recompute eh_beg/eh_end for each basic block.  */
1304
1305 static void
1306 record_active_eh_regions (f)
1307      rtx f;
1308 {
1309   rtx insn, eh_list = NULL_RTX;
1310   int i = 0;
1311   basic_block bb = BASIC_BLOCK (0);
1312
1313   for (insn = f; insn ; insn = NEXT_INSN (insn))
1314     {
1315       if (bb->head == insn)
1316         bb->eh_beg = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1317
1318       if (GET_CODE (insn) == NOTE)
1319         {
1320           int kind = NOTE_LINE_NUMBER (insn);
1321           if (kind == NOTE_INSN_EH_REGION_BEG)
1322             eh_list = alloc_INSN_LIST (insn, eh_list);
1323           else if (kind == NOTE_INSN_EH_REGION_END)
1324             {
1325               rtx t = XEXP (eh_list, 1);
1326               free_INSN_LIST_node (eh_list);
1327               eh_list = t;
1328             }
1329         }
1330
1331       if (bb->end == insn)
1332         {
1333           bb->eh_end = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1334           i += 1;
1335           if (i == n_basic_blocks)
1336             break;
1337           bb = BASIC_BLOCK (i);
1338         }
1339     }
1340 }
1341
1342 /* Identify critical edges and set the bits appropriately.  */
1343
1344 static void
1345 mark_critical_edges ()
1346 {
1347   int i, n = n_basic_blocks;
1348   basic_block bb;
1349
1350   /* We begin with the entry block.  This is not terribly important now,
1351      but could be if a front end (Fortran) implemented alternate entry
1352      points.  */
1353   bb = ENTRY_BLOCK_PTR;
1354   i = -1;
1355
1356   while (1)
1357     {
1358       edge e;
1359
1360       /* (1) Critical edges must have a source with multiple successors.  */
1361       if (bb->succ && bb->succ->succ_next)
1362         {
1363           for (e = bb->succ; e ; e = e->succ_next)
1364             {
1365               /* (2) Critical edges must have a destination with multiple
1366                  predecessors.  Note that we know there is at least one
1367                  predecessor -- the edge we followed to get here.  */
1368               if (e->dest->pred->pred_next)
1369                 e->flags |= EDGE_CRITICAL;
1370               else
1371                 e->flags &= ~EDGE_CRITICAL;
1372             }
1373         }
1374       else
1375         {
1376           for (e = bb->succ; e ; e = e->succ_next)
1377             e->flags &= ~EDGE_CRITICAL;
1378         }
1379
1380       if (++i >= n)
1381         break;
1382       bb = BASIC_BLOCK (i);
1383     }
1384 }
1385 \f
1386 /* Split a (typically critical) edge.  Return the new block.
1387    Abort on abnormal edges.
1388
1389    ??? The code generally expects to be called on critical edges.
1390    The case of a block ending in an unconditional jump to a
1391    block with multiple predecessors is not handled optimally.  */
1392
1393 basic_block
1394 split_edge (edge_in)
1395      edge edge_in;
1396 {
1397   basic_block old_pred, bb, old_succ;
1398   edge edge_out;
1399   rtx bb_note;
1400   int i, j;
1401
1402   /* Abnormal edges cannot be split.  */
1403   if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1404     abort ();
1405
1406   old_pred = edge_in->src;
1407   old_succ = edge_in->dest;
1408
1409   /* Remove the existing edge from the destination's pred list.  */
1410   {
1411     edge *pp;
1412     for (pp = &old_succ->pred; *pp != edge_in; pp = &(*pp)->pred_next)
1413       continue;
1414     *pp = edge_in->pred_next;
1415     edge_in->pred_next = NULL;
1416   }
1417
1418   /* Create the new structures.  */
1419   bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
1420   edge_out = (edge) xcalloc (1, sizeof (*edge_out));
1421   n_edges++;
1422
1423   memset (bb, 0, sizeof (*bb));
1424
1425   /* ??? This info is likely going to be out of date very soon.  */
1426   if (old_succ->global_live_at_start)
1427     {
1428       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
1429       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
1430       COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
1431       COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
1432     }
1433
1434   /* Wire them up.  */
1435   bb->pred = edge_in;
1436   bb->succ = edge_out;
1437   bb->count = edge_in->count;
1438
1439   edge_in->dest = bb;
1440   edge_in->flags &= ~EDGE_CRITICAL;
1441
1442   edge_out->pred_next = old_succ->pred;
1443   edge_out->succ_next = NULL;
1444   edge_out->src = bb;
1445   edge_out->dest = old_succ;
1446   edge_out->flags = EDGE_FALLTHRU;
1447   edge_out->probability = REG_BR_PROB_BASE;
1448   edge_out->count = edge_in->count;
1449
1450   old_succ->pred = edge_out;
1451
1452   /* Tricky case -- if there existed a fallthru into the successor
1453      (and we're not it) we must add a new unconditional jump around
1454      the new block we're actually interested in.
1455
1456      Further, if that edge is critical, this means a second new basic
1457      block must be created to hold it.  In order to simplify correct
1458      insn placement, do this before we touch the existing basic block
1459      ordering for the block we were really wanting.  */
1460   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1461     {
1462       edge e;
1463       for (e = edge_out->pred_next; e ; e = e->pred_next)
1464         if (e->flags & EDGE_FALLTHRU)
1465           break;
1466
1467       if (e)
1468         {
1469           basic_block jump_block;
1470           rtx pos;
1471
1472           if ((e->flags & EDGE_CRITICAL) == 0
1473               && e->src != ENTRY_BLOCK_PTR)
1474             {
1475               /* Non critical -- we can simply add a jump to the end
1476                  of the existing predecessor.  */
1477               jump_block = e->src;
1478             }
1479           else
1480             {
1481               /* We need a new block to hold the jump.  The simplest
1482                  way to do the bulk of the work here is to recursively
1483                  call ourselves.  */
1484               jump_block = split_edge (e);
1485               e = jump_block->succ;
1486             }
1487
1488           /* Now add the jump insn ...  */
1489           pos = emit_jump_insn_after (gen_jump (old_succ->head),
1490                                       jump_block->end);
1491           jump_block->end = pos;
1492           if (basic_block_for_insn)
1493             set_block_for_insn (pos, jump_block);
1494           emit_barrier_after (pos);
1495
1496           /* ... let jump know that label is in use, ...  */
1497           JUMP_LABEL (pos) = old_succ->head;
1498           ++LABEL_NUSES (old_succ->head);
1499
1500           /* ... and clear fallthru on the outgoing edge.  */
1501           e->flags &= ~EDGE_FALLTHRU;
1502
1503           /* Continue splitting the interesting edge.  */
1504         }
1505     }
1506
1507   /* Place the new block just in front of the successor.  */
1508   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1509   if (old_succ == EXIT_BLOCK_PTR)
1510     j = n_basic_blocks - 1;
1511   else
1512     j = old_succ->index;
1513   for (i = n_basic_blocks - 1; i > j; --i)
1514     {
1515       basic_block tmp = BASIC_BLOCK (i - 1);
1516       BASIC_BLOCK (i) = tmp;
1517       tmp->index = i;
1518     }
1519   BASIC_BLOCK (i) = bb;
1520   bb->index = i;
1521
1522   /* Create the basic block note.
1523
1524      Where we place the note can have a noticable impact on the generated
1525      code.  Consider this cfg:
1526
1527
1528                         E
1529                         |
1530                         0
1531                        / \
1532                    +->1-->2--->E
1533                    |  |
1534                    +--+
1535
1536       If we need to insert an insn on the edge from block 0 to block 1,
1537       we want to ensure the instructions we insert are outside of any
1538       loop notes that physically sit between block 0 and block 1.  Otherwise
1539       we confuse the loop optimizer into thinking the loop is a phony.  */
1540   if (old_succ != EXIT_BLOCK_PTR
1541       && PREV_INSN (old_succ->head)
1542       && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
1543       && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
1544     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1545                                 PREV_INSN (old_succ->head));
1546   else if (old_succ != EXIT_BLOCK_PTR)
1547     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
1548   else
1549     bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
1550   NOTE_BASIC_BLOCK (bb_note) = bb;
1551   bb->head = bb->end = bb_note;
1552
1553   /* Not quite simple -- for non-fallthru edges, we must adjust the
1554      predecessor's jump instruction to target our new block.  */
1555   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1556     {
1557       rtx tmp, insn = old_pred->end;
1558       rtx old_label = old_succ->head;
1559       rtx new_label = gen_label_rtx ();
1560
1561       if (GET_CODE (insn) != JUMP_INSN)
1562         abort ();
1563
1564       /* ??? Recognize a tablejump and adjust all matching cases.  */
1565       if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1566           && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1567           && GET_CODE (tmp) == JUMP_INSN
1568           && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1569               || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1570         {
1571           rtvec vec;
1572           int j;
1573
1574           if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1575             vec = XVEC (PATTERN (tmp), 0);
1576           else
1577             vec = XVEC (PATTERN (tmp), 1);
1578
1579           for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1580             if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1581               {
1582                 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (VOIDmode, new_label);
1583                 --LABEL_NUSES (old_label);
1584                 ++LABEL_NUSES (new_label);
1585               }
1586
1587           /* Handle casesi dispatch insns */
1588           if ((tmp = single_set (insn)) != NULL
1589               && SET_DEST (tmp) == pc_rtx
1590               && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1591               && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1592               && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1593             {
1594               XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
1595                                                            new_label);
1596               --LABEL_NUSES (old_label);
1597               ++LABEL_NUSES (new_label);
1598             }
1599         }
1600       else
1601         {
1602           /* This would have indicated an abnormal edge.  */
1603           if (computed_jump_p (insn))
1604             abort ();
1605
1606           /* A return instruction can't be redirected.  */
1607           if (returnjump_p (insn))
1608             abort ();
1609
1610           /* If the insn doesn't go where we think, we're confused.  */
1611           if (JUMP_LABEL (insn) != old_label)
1612             abort ();
1613
1614           redirect_jump (insn, new_label, 0);
1615         }
1616
1617       emit_label_before (new_label, bb_note);
1618       bb->head = new_label;
1619     }
1620
1621   return bb;
1622 }
1623
1624 /* Queue instructions for insertion on an edge between two basic blocks.
1625    The new instructions and basic blocks (if any) will not appear in the
1626    CFG until commit_edge_insertions is called.  */
1627
1628 void
1629 insert_insn_on_edge (pattern, e)
1630      rtx pattern;
1631      edge e;
1632 {
1633   /* We cannot insert instructions on an abnormal critical edge.
1634      It will be easier to find the culprit if we die now.  */
1635   if ((e->flags & (EDGE_ABNORMAL|EDGE_CRITICAL))
1636       == (EDGE_ABNORMAL|EDGE_CRITICAL))
1637     abort ();
1638
1639   if (e->insns == NULL_RTX)
1640     start_sequence ();
1641   else
1642     push_to_sequence (e->insns);
1643
1644   emit_insn (pattern);
1645
1646   e->insns = get_insns ();
1647   end_sequence();
1648 }
1649
1650 /* Update the CFG for the instructions queued on edge E.  */
1651
1652 static void
1653 commit_one_edge_insertion (e)
1654      edge e;
1655 {
1656   rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1657   basic_block bb;
1658
1659   /* Pull the insns off the edge now since the edge might go away.  */
1660   insns = e->insns;
1661   e->insns = NULL_RTX;
1662
1663   /* Figure out where to put these things.  If the destination has
1664      one predecessor, insert there.  Except for the exit block.  */
1665   if (e->dest->pred->pred_next == NULL
1666       && e->dest != EXIT_BLOCK_PTR)
1667     {
1668       bb = e->dest;
1669
1670       /* Get the location correct wrt a code label, and "nice" wrt
1671          a basic block note, and before everything else.  */
1672       tmp = bb->head;
1673       if (GET_CODE (tmp) == CODE_LABEL)
1674         tmp = NEXT_INSN (tmp);
1675       if (GET_CODE (tmp) == NOTE
1676           && NOTE_LINE_NUMBER (tmp) == NOTE_INSN_BASIC_BLOCK)
1677         tmp = NEXT_INSN (tmp);
1678       if (tmp == bb->head)
1679         before = tmp;
1680       else
1681         after = PREV_INSN (tmp);
1682     }
1683
1684   /* If the source has one successor and the edge is not abnormal,
1685      insert there.  Except for the entry block.  */
1686   else if ((e->flags & EDGE_ABNORMAL) == 0
1687            && e->src->succ->succ_next == NULL
1688            && e->src != ENTRY_BLOCK_PTR)
1689     {
1690       bb = e->src;
1691       /* It is possible to have a non-simple jump here.  Consider a target
1692          where some forms of unconditional jumps clobber a register.  This
1693          happens on the fr30 for example.
1694
1695          We know this block has a single successor, so we can just emit
1696          the queued insns before the jump.  */
1697       if (GET_CODE (bb->end) == JUMP_INSN)
1698         {
1699           before = bb->end;
1700         }
1701       else
1702         {
1703           /* We'd better be fallthru, or we've lost track of what's what.  */
1704           if ((e->flags & EDGE_FALLTHRU) == 0)
1705             abort ();
1706
1707           after = bb->end;
1708         }
1709     }
1710
1711   /* Otherwise we must split the edge.  */
1712   else
1713     {
1714       bb = split_edge (e);
1715       after = bb->end;
1716     }
1717
1718   /* Now that we've found the spot, do the insertion.  */
1719
1720   /* Set the new block number for these insns, if structure is allocated.  */
1721   if (basic_block_for_insn)
1722     {
1723       rtx i;
1724       for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
1725         set_block_for_insn (i, bb);
1726     }
1727
1728   if (before)
1729     {
1730       emit_insns_before (insns, before);
1731       if (before == bb->head)
1732         bb->head = insns;
1733
1734       last = prev_nonnote_insn (before);
1735     }
1736   else
1737     {
1738       last = emit_insns_after (insns, after);
1739       if (after == bb->end)
1740         bb->end = last;
1741     }
1742
1743   if (returnjump_p (last))
1744     {
1745       /* ??? Remove all outgoing edges from BB and add one for EXIT.
1746          This is not currently a problem because this only happens
1747          for the (single) epilogue, which already has a fallthru edge
1748          to EXIT.  */
1749
1750       e = bb->succ;
1751       if (e->dest != EXIT_BLOCK_PTR
1752           || e->succ_next != NULL
1753           || (e->flags & EDGE_FALLTHRU) == 0)
1754         abort ();
1755       e->flags &= ~EDGE_FALLTHRU;
1756
1757       emit_barrier_after (last);
1758       bb->end = last;
1759
1760       if (before)
1761         flow_delete_insn (before);
1762     }
1763   else if (GET_CODE (last) == JUMP_INSN)
1764     abort ();
1765 }
1766
1767 /* Update the CFG for all queued instructions.  */
1768
1769 void
1770 commit_edge_insertions ()
1771 {
1772   int i;
1773   basic_block bb;
1774
1775 #ifdef ENABLE_CHECKING
1776   verify_flow_info ();
1777 #endif
1778
1779   i = -1;
1780   bb = ENTRY_BLOCK_PTR;
1781   while (1)
1782     {
1783       edge e, next;
1784
1785       for (e = bb->succ; e ; e = next)
1786         {
1787           next = e->succ_next;
1788           if (e->insns)
1789             commit_one_edge_insertion (e);
1790         }
1791
1792       if (++i >= n_basic_blocks)
1793         break;
1794       bb = BASIC_BLOCK (i);
1795     }
1796 }
1797 \f
1798 /* Delete all unreachable basic blocks.   */
1799
1800 static void
1801 delete_unreachable_blocks ()
1802 {
1803   basic_block *worklist, *tos;
1804   int deleted_handler;
1805   edge e;
1806   int i, n;
1807
1808   n = n_basic_blocks;
1809   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
1810
1811   /* Use basic_block->aux as a marker.  Clear them all.  */
1812
1813   for (i = 0; i < n; ++i)
1814     BASIC_BLOCK (i)->aux = NULL;
1815
1816   /* Add our starting points to the worklist.  Almost always there will
1817      be only one.  It isn't inconcievable that we might one day directly
1818      support Fortran alternate entry points.  */
1819
1820   for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1821     {
1822       *tos++ = e->dest;
1823
1824       /* Mark the block with a handy non-null value.  */
1825       e->dest->aux = e;
1826     }
1827
1828   /* Iterate: find everything reachable from what we've already seen.  */
1829
1830   while (tos != worklist)
1831     {
1832       basic_block b = *--tos;
1833
1834       for (e = b->succ; e ; e = e->succ_next)
1835         if (!e->dest->aux)
1836           {
1837             *tos++ = e->dest;
1838             e->dest->aux = e;
1839           }
1840     }
1841
1842   /* Delete all unreachable basic blocks.  Count down so that we don't
1843      interfere with the block renumbering that happens in flow_delete_block. */
1844
1845   deleted_handler = 0;
1846
1847   for (i = n - 1; i >= 0; --i)
1848     {
1849       basic_block b = BASIC_BLOCK (i);
1850
1851       if (b->aux != NULL)
1852         /* This block was found.  Tidy up the mark.  */
1853         b->aux = NULL;
1854       else
1855         deleted_handler |= flow_delete_block (b);
1856     }
1857
1858   tidy_fallthru_edges ();
1859
1860   /* If we deleted an exception handler, we may have EH region begin/end
1861      blocks to remove as well. */
1862   if (deleted_handler)
1863     delete_eh_regions ();
1864
1865   free (worklist);
1866 }
1867
1868 /* Find EH regions for which there is no longer a handler, and delete them.  */
1869
1870 static void
1871 delete_eh_regions ()
1872 {
1873   rtx insn;
1874
1875   update_rethrow_references ();
1876
1877   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1878     if (GET_CODE (insn) == NOTE)
1879       {
1880         if ((NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG) ||
1881             (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1882           {
1883             int num = NOTE_EH_HANDLER (insn);
1884             /* A NULL handler indicates a region is no longer needed,
1885                as long as its rethrow label isn't used.  */
1886             if (get_first_handler (num) == NULL && ! rethrow_used (num))
1887               {
1888                 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1889                 NOTE_SOURCE_FILE (insn) = 0;
1890               }
1891           }
1892       }
1893 }
1894
1895 /* Return true if NOTE is not one of the ones that must be kept paired,
1896    so that we may simply delete them.  */
1897
1898 static int
1899 can_delete_note_p (note)
1900      rtx note;
1901 {
1902   return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
1903           || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
1904 }
1905
1906 /* Unlink a chain of insns between START and FINISH, leaving notes
1907    that must be paired.  */
1908
1909 void
1910 flow_delete_insn_chain (start, finish)
1911      rtx start, finish;
1912 {
1913   /* Unchain the insns one by one.  It would be quicker to delete all
1914      of these with a single unchaining, rather than one at a time, but
1915      we need to keep the NOTE's.  */
1916
1917   rtx next;
1918
1919   while (1)
1920     {
1921       next = NEXT_INSN (start);
1922       if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
1923         ;
1924       else if (GET_CODE (start) == CODE_LABEL
1925                && ! can_delete_label_p (start))
1926         {
1927           const char *name = LABEL_NAME (start);
1928           PUT_CODE (start, NOTE);
1929           NOTE_LINE_NUMBER (start) = NOTE_INSN_DELETED_LABEL;
1930           NOTE_SOURCE_FILE (start) = name;
1931         }
1932       else
1933         next = flow_delete_insn (start);
1934
1935       if (start == finish)
1936         break;
1937       start = next;
1938     }
1939 }
1940
1941 /* Delete the insns in a (non-live) block.  We physically delete every
1942    non-deleted-note insn, and update the flow graph appropriately.
1943
1944    Return nonzero if we deleted an exception handler.  */
1945
1946 /* ??? Preserving all such notes strikes me as wrong.  It would be nice
1947    to post-process the stream to remove empty blocks, loops, ranges, etc.  */
1948
1949 int
1950 flow_delete_block (b)
1951      basic_block b;
1952 {
1953   int deleted_handler = 0;
1954   rtx insn, end, tmp;
1955
1956   /* If the head of this block is a CODE_LABEL, then it might be the
1957      label for an exception handler which can't be reached.
1958
1959      We need to remove the label from the exception_handler_label list
1960      and remove the associated NOTE_INSN_EH_REGION_BEG and
1961      NOTE_INSN_EH_REGION_END notes.  */
1962
1963   insn = b->head;
1964
1965   never_reached_warning (insn);
1966
1967   if (GET_CODE (insn) == CODE_LABEL)
1968     {
1969       rtx x, *prev = &exception_handler_labels;
1970
1971       for (x = exception_handler_labels; x; x = XEXP (x, 1))
1972         {
1973           if (XEXP (x, 0) == insn)
1974             {
1975               /* Found a match, splice this label out of the EH label list.  */
1976               *prev = XEXP (x, 1);
1977               XEXP (x, 1) = NULL_RTX;
1978               XEXP (x, 0) = NULL_RTX;
1979
1980               /* Remove the handler from all regions */
1981               remove_handler (insn);
1982               deleted_handler = 1;
1983               break;
1984             }
1985           prev = &XEXP (x, 1);
1986         }
1987     }
1988
1989   /* Include any jump table following the basic block.  */
1990   end = b->end;
1991   if (GET_CODE (end) == JUMP_INSN
1992       && (tmp = JUMP_LABEL (end)) != NULL_RTX
1993       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1994       && GET_CODE (tmp) == JUMP_INSN
1995       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1996           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1997     end = tmp;
1998
1999   /* Include any barrier that may follow the basic block.  */
2000   tmp = next_nonnote_insn (end);
2001   if (tmp && GET_CODE (tmp) == BARRIER)
2002     end = tmp;
2003
2004   /* Selectively delete the entire chain.  */
2005   flow_delete_insn_chain (insn, end);
2006
2007   /* Remove the edges into and out of this block.  Note that there may
2008      indeed be edges in, if we are removing an unreachable loop.  */
2009   {
2010     edge e, next, *q;
2011
2012     for (e = b->pred; e ; e = next)
2013       {
2014         for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
2015           continue;
2016         *q = e->succ_next;
2017         next = e->pred_next;
2018         n_edges--;
2019         free (e);
2020       }
2021     for (e = b->succ; e ; e = next)
2022       {
2023         for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
2024           continue;
2025         *q = e->pred_next;
2026         next = e->succ_next;
2027         n_edges--;
2028         free (e);
2029       }
2030
2031     b->pred = NULL;
2032     b->succ = NULL;
2033   }
2034
2035   /* Remove the basic block from the array, and compact behind it.  */
2036   expunge_block (b);
2037
2038   return deleted_handler;
2039 }
2040
2041 /* Remove block B from the basic block array and compact behind it.  */
2042
2043 static void
2044 expunge_block (b)
2045      basic_block b;
2046 {
2047   int i, n = n_basic_blocks;
2048
2049   for (i = b->index; i + 1 < n; ++i)
2050     {
2051       basic_block x = BASIC_BLOCK (i + 1);
2052       BASIC_BLOCK (i) = x;
2053       x->index = i;
2054     }
2055
2056   basic_block_info->num_elements--;
2057   n_basic_blocks--;
2058 }
2059
2060 /* Delete INSN by patching it out.  Return the next insn.  */
2061
2062 rtx
2063 flow_delete_insn (insn)
2064      rtx insn;
2065 {
2066   rtx prev = PREV_INSN (insn);
2067   rtx next = NEXT_INSN (insn);
2068   rtx note;
2069
2070   PREV_INSN (insn) = NULL_RTX;
2071   NEXT_INSN (insn) = NULL_RTX;
2072   INSN_DELETED_P (insn) = 1;
2073
2074   if (prev)
2075     NEXT_INSN (prev) = next;
2076   if (next)
2077     PREV_INSN (next) = prev;
2078   else
2079     set_last_insn (prev);
2080
2081   if (GET_CODE (insn) == CODE_LABEL)
2082     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2083
2084   /* If deleting a jump, decrement the use count of the label.  Deleting
2085      the label itself should happen in the normal course of block merging.  */
2086   if (GET_CODE (insn) == JUMP_INSN
2087       && JUMP_LABEL (insn)
2088       && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
2089     LABEL_NUSES (JUMP_LABEL (insn))--;
2090
2091   /* Also if deleting an insn that references a label.  */
2092   else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
2093            && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2094     LABEL_NUSES (XEXP (note, 0))--;
2095
2096   return next;
2097 }
2098
2099 /* True if a given label can be deleted.  */
2100
2101 static int
2102 can_delete_label_p (label)
2103      rtx label;
2104 {
2105   rtx x;
2106
2107   if (LABEL_PRESERVE_P (label))
2108     return 0;
2109
2110   for (x = forced_labels; x ; x = XEXP (x, 1))
2111     if (label == XEXP (x, 0))
2112       return 0;
2113   for (x = label_value_list; x ; x = XEXP (x, 1))
2114     if (label == XEXP (x, 0))
2115       return 0;
2116   for (x = exception_handler_labels; x ; x = XEXP (x, 1))
2117     if (label == XEXP (x, 0))
2118       return 0;
2119
2120   /* User declared labels must be preserved.  */
2121   if (LABEL_NAME (label) != 0)
2122     return 0;
2123
2124   return 1;
2125 }
2126
2127 static int
2128 tail_recursion_label_p (label)
2129      rtx label;
2130 {
2131   rtx x;
2132
2133   for (x = tail_recursion_label_list; x ; x = XEXP (x, 1))
2134     if (label == XEXP (x, 0))
2135       return 1;
2136
2137   return 0;
2138 }
2139
2140 /* Blocks A and B are to be merged into a single block A.  The insns
2141    are already contiguous, hence `nomove'.  */
2142
2143 void
2144 merge_blocks_nomove (a, b)
2145      basic_block a, b;
2146 {
2147   edge e;
2148   rtx b_head, b_end, a_end;
2149   rtx del_first = NULL_RTX, del_last = NULL_RTX;
2150   int b_empty = 0;
2151
2152   /* If there was a CODE_LABEL beginning B, delete it.  */
2153   b_head = b->head;
2154   b_end = b->end;
2155   if (GET_CODE (b_head) == CODE_LABEL)
2156     {
2157       /* Detect basic blocks with nothing but a label.  This can happen
2158          in particular at the end of a function.  */
2159       if (b_head == b_end)
2160         b_empty = 1;
2161       del_first = del_last = b_head;
2162       b_head = NEXT_INSN (b_head);
2163     }
2164
2165   /* Delete the basic block note.  */
2166   if (GET_CODE (b_head) == NOTE
2167       && NOTE_LINE_NUMBER (b_head) == NOTE_INSN_BASIC_BLOCK)
2168     {
2169       if (b_head == b_end)
2170         b_empty = 1;
2171       if (! del_last)
2172         del_first = b_head;
2173       del_last = b_head;
2174       b_head = NEXT_INSN (b_head);
2175     }
2176
2177   /* If there was a jump out of A, delete it.  */
2178   a_end = a->end;
2179   if (GET_CODE (a_end) == JUMP_INSN)
2180     {
2181       rtx prev;
2182
2183       prev = prev_nonnote_insn (a_end);
2184       if (!prev)
2185         prev = a->head;
2186
2187       del_first = a_end;
2188
2189 #ifdef HAVE_cc0
2190       /* If this was a conditional jump, we need to also delete
2191          the insn that set cc0.  */
2192       if (prev && sets_cc0_p (prev))
2193         {
2194           rtx tmp = prev;
2195           prev = prev_nonnote_insn (prev);
2196           if (!prev)
2197             prev = a->head;
2198           del_first = tmp;
2199         }
2200 #endif
2201
2202       a_end = prev;
2203     }
2204   else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
2205     del_first = NEXT_INSN (a_end);
2206
2207   /* Delete everything marked above as well as crap that might be
2208      hanging out between the two blocks.  */
2209   flow_delete_insn_chain (del_first, del_last);
2210
2211   /* Normally there should only be one successor of A and that is B, but
2212      partway though the merge of blocks for conditional_execution we'll
2213      be merging a TEST block with THEN and ELSE successors.  Free the
2214      whole lot of them and hope the caller knows what they're doing.  */
2215   while (a->succ)
2216     remove_edge (a->succ);
2217
2218   /* Adjust the edges out of B for the new owner.  */
2219   for (e = b->succ; e ; e = e->succ_next)
2220     e->src = a;
2221   a->succ = b->succ;
2222
2223   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
2224   b->pred = b->succ = NULL;
2225
2226   /* Reassociate the insns of B with A.  */
2227   if (!b_empty)
2228     {
2229       if (basic_block_for_insn)
2230         {
2231           BLOCK_FOR_INSN (b_head) = a;
2232           while (b_head != b_end)
2233             {
2234               b_head = NEXT_INSN (b_head);
2235               BLOCK_FOR_INSN (b_head) = a;
2236             }
2237         }
2238       a_end = b_end;
2239     }
2240   a->end = a_end;
2241
2242   expunge_block (b);
2243 }
2244
2245 /* Blocks A and B are to be merged into a single block.  A has no incoming
2246    fallthru edge, so it can be moved before B without adding or modifying
2247    any jumps (aside from the jump from A to B).  */
2248
2249 static int
2250 merge_blocks_move_predecessor_nojumps (a, b)
2251      basic_block a, b;
2252 {
2253   rtx start, end, barrier;
2254   int index;
2255
2256   start = a->head;
2257   end = a->end;
2258
2259   barrier = next_nonnote_insn (end);
2260   if (GET_CODE (barrier) != BARRIER)
2261     abort ();
2262   flow_delete_insn (barrier);
2263
2264   /* Move block and loop notes out of the chain so that we do not
2265      disturb their order.
2266
2267      ??? A better solution would be to squeeze out all the non-nested notes
2268      and adjust the block trees appropriately.   Even better would be to have
2269      a tighter connection between block trees and rtl so that this is not
2270      necessary.  */
2271   start = squeeze_notes (start, end);
2272
2273   /* Scramble the insn chain.  */
2274   if (end != PREV_INSN (b->head))
2275     reorder_insns (start, end, PREV_INSN (b->head));
2276
2277   if (rtl_dump_file)
2278     {
2279       fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
2280                a->index, b->index);
2281     }
2282
2283   /* Swap the records for the two blocks around.  Although we are deleting B,
2284      A is now where B was and we want to compact the BB array from where
2285      A used to be.  */
2286   BASIC_BLOCK(a->index) = b;
2287   BASIC_BLOCK(b->index) = a;
2288   index = a->index;
2289   a->index = b->index;
2290   b->index = index;
2291
2292   /* Now blocks A and B are contiguous.  Merge them.  */
2293   merge_blocks_nomove (a, b);
2294
2295   return 1;
2296 }
2297
2298 /* Blocks A and B are to be merged into a single block.  B has no outgoing
2299    fallthru edge, so it can be moved after A without adding or modifying
2300    any jumps (aside from the jump from A to B).  */
2301
2302 static int
2303 merge_blocks_move_successor_nojumps (a, b)
2304      basic_block a, b;
2305 {
2306   rtx start, end, barrier;
2307
2308   start = b->head;
2309   end = b->end;
2310   barrier = NEXT_INSN (end);
2311
2312   /* Recognize a jump table following block B.  */
2313   if (GET_CODE (barrier) == CODE_LABEL
2314       && NEXT_INSN (barrier)
2315       && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
2316       && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
2317           || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
2318     {
2319       end = NEXT_INSN (barrier);
2320       barrier = NEXT_INSN (end);
2321     }
2322
2323   /* There had better have been a barrier there.  Delete it.  */
2324   if (GET_CODE (barrier) != BARRIER)
2325     abort ();
2326   flow_delete_insn (barrier);
2327
2328   /* Move block and loop notes out of the chain so that we do not
2329      disturb their order.
2330
2331      ??? A better solution would be to squeeze out all the non-nested notes
2332      and adjust the block trees appropriately.   Even better would be to have
2333      a tighter connection between block trees and rtl so that this is not
2334      necessary.  */
2335   start = squeeze_notes (start, end);
2336
2337   /* Scramble the insn chain.  */
2338   reorder_insns (start, end, a->end);
2339
2340   /* Now blocks A and B are contiguous.  Merge them.  */
2341   merge_blocks_nomove (a, b);
2342
2343   if (rtl_dump_file)
2344     {
2345       fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
2346                b->index, a->index);
2347     }
2348
2349   return 1;
2350 }
2351
2352 /* Attempt to merge basic blocks that are potentially non-adjacent.
2353    Return true iff the attempt succeeded.  */
2354
2355 static int
2356 merge_blocks (e, b, c)
2357      edge e;
2358      basic_block b, c;
2359 {
2360   /* If C has a tail recursion label, do not merge.  There is no
2361      edge recorded from the call_placeholder back to this label, as
2362      that would make optimize_sibling_and_tail_recursive_calls more
2363      complex for no gain.  */
2364   if (GET_CODE (c->head) == CODE_LABEL
2365       && tail_recursion_label_p (c->head))
2366     return 0;
2367
2368   /* If B has a fallthru edge to C, no need to move anything.  */
2369   if (e->flags & EDGE_FALLTHRU)
2370     {
2371       merge_blocks_nomove (b, c);
2372
2373       if (rtl_dump_file)
2374         {
2375           fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
2376                    b->index, c->index);
2377         }
2378
2379       return 1;
2380     }
2381   else
2382     {
2383       edge tmp_edge;
2384       basic_block d;
2385       int c_has_outgoing_fallthru;
2386       int b_has_incoming_fallthru;
2387
2388       /* We must make sure to not munge nesting of exception regions,
2389          lexical blocks, and loop notes.
2390
2391          The first is taken care of by requiring that the active eh
2392          region at the end of one block always matches the active eh
2393          region at the beginning of the next block.
2394
2395          The later two are taken care of by squeezing out all the notes.  */
2396
2397       /* ???  A throw/catch edge (or any abnormal edge) should be rarely
2398          executed and we may want to treat blocks which have two out
2399          edges, one normal, one abnormal as only having one edge for
2400          block merging purposes.  */
2401
2402       for (tmp_edge = c->succ; tmp_edge ; tmp_edge = tmp_edge->succ_next)
2403         if (tmp_edge->flags & EDGE_FALLTHRU)
2404           break;
2405       c_has_outgoing_fallthru = (tmp_edge != NULL);
2406
2407       for (tmp_edge = b->pred; tmp_edge ; tmp_edge = tmp_edge->pred_next)
2408         if (tmp_edge->flags & EDGE_FALLTHRU)
2409           break;
2410       b_has_incoming_fallthru = (tmp_edge != NULL);
2411
2412       /* If B does not have an incoming fallthru, and the exception regions
2413          match, then it can be moved immediately before C without introducing
2414          or modifying jumps.
2415
2416          C can not be the first block, so we do not have to worry about
2417          accessing a non-existent block.  */
2418       d = BASIC_BLOCK (c->index - 1);
2419       if (! b_has_incoming_fallthru
2420           && d->eh_end == b->eh_beg
2421           && b->eh_end == c->eh_beg)
2422         return merge_blocks_move_predecessor_nojumps (b, c);
2423
2424       /* Otherwise, we're going to try to move C after B.  Make sure the
2425          exception regions match.
2426
2427          If B is the last basic block, then we must not try to access the
2428          block structure for block B + 1.  Luckily in that case we do not
2429          need to worry about matching exception regions.  */
2430       d = (b->index + 1 < n_basic_blocks ? BASIC_BLOCK (b->index + 1) : NULL);
2431       if (b->eh_end == c->eh_beg
2432           && (d == NULL || c->eh_end == d->eh_beg))
2433         {
2434           /* If C does not have an outgoing fallthru, then it can be moved
2435              immediately after B without introducing or modifying jumps.  */
2436           if (! c_has_outgoing_fallthru)
2437             return merge_blocks_move_successor_nojumps (b, c);
2438
2439           /* Otherwise, we'll need to insert an extra jump, and possibly
2440              a new block to contain it.  */
2441           /* ??? Not implemented yet.  */
2442         }
2443
2444       return 0;
2445     }
2446 }
2447
2448 /* Top level driver for merge_blocks.  */
2449
2450 static void
2451 try_merge_blocks ()
2452 {
2453   int i;
2454
2455   /* Attempt to merge blocks as made possible by edge removal.  If a block
2456      has only one successor, and the successor has only one predecessor,
2457      they may be combined.  */
2458
2459   for (i = 0; i < n_basic_blocks; )
2460     {
2461       basic_block c, b = BASIC_BLOCK (i);
2462       edge s;
2463
2464       /* A loop because chains of blocks might be combineable.  */
2465       while ((s = b->succ) != NULL
2466              && s->succ_next == NULL
2467              && (s->flags & EDGE_EH) == 0
2468              && (c = s->dest) != EXIT_BLOCK_PTR
2469              && c->pred->pred_next == NULL
2470              /* If the jump insn has side effects, we can't kill the edge.  */
2471              && (GET_CODE (b->end) != JUMP_INSN
2472                  || onlyjump_p (b->end))
2473              && merge_blocks (s, b, c))
2474         continue;
2475
2476       /* Don't get confused by the index shift caused by deleting blocks.  */
2477       i = b->index + 1;
2478     }
2479 }
2480
2481 /* The given edge should potentially be a fallthru edge.  If that is in
2482    fact true, delete the jump and barriers that are in the way.  */
2483
2484 void
2485 tidy_fallthru_edge (e, b, c)
2486      edge e;
2487      basic_block b, c;
2488 {
2489   rtx q;
2490
2491   /* ??? In a late-running flow pass, other folks may have deleted basic
2492      blocks by nopping out blocks, leaving multiple BARRIERs between here
2493      and the target label. They ought to be chastized and fixed.
2494
2495      We can also wind up with a sequence of undeletable labels between
2496      one block and the next.
2497
2498      So search through a sequence of barriers, labels, and notes for
2499      the head of block C and assert that we really do fall through.  */
2500
2501   if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
2502     return;
2503
2504   /* Remove what will soon cease being the jump insn from the source block.
2505      If block B consisted only of this single jump, turn it into a deleted
2506      note.  */
2507   q = b->end;
2508   if (GET_CODE (q) == JUMP_INSN
2509       && onlyjump_p (q)
2510       && (any_uncondjump_p (q)
2511           || (b->succ == e && e->succ_next == NULL)))
2512     {
2513 #ifdef HAVE_cc0
2514       /* If this was a conditional jump, we need to also delete
2515          the insn that set cc0.  */
2516       if (any_condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
2517         q = PREV_INSN (q);
2518 #endif
2519
2520       if (b->head == q)
2521         {
2522           PUT_CODE (q, NOTE);
2523           NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
2524           NOTE_SOURCE_FILE (q) = 0;
2525         }
2526       else
2527         b->end = q = PREV_INSN (q);
2528     }
2529
2530   /* Selectively unlink the sequence.  */
2531   if (q != PREV_INSN (c->head))
2532     flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
2533
2534   e->flags |= EDGE_FALLTHRU;
2535 }
2536
2537 /* Fix up edges that now fall through, or rather should now fall through
2538    but previously required a jump around now deleted blocks.  Simplify
2539    the search by only examining blocks numerically adjacent, since this
2540    is how find_basic_blocks created them.  */
2541
2542 static void
2543 tidy_fallthru_edges ()
2544 {
2545   int i;
2546
2547   for (i = 1; i < n_basic_blocks; ++i)
2548     {
2549       basic_block b = BASIC_BLOCK (i - 1);
2550       basic_block c = BASIC_BLOCK (i);
2551       edge s;
2552
2553       /* We care about simple conditional or unconditional jumps with
2554          a single successor.
2555
2556          If we had a conditional branch to the next instruction when
2557          find_basic_blocks was called, then there will only be one
2558          out edge for the block which ended with the conditional
2559          branch (since we do not create duplicate edges).
2560
2561          Furthermore, the edge will be marked as a fallthru because we
2562          merge the flags for the duplicate edges.  So we do not want to
2563          check that the edge is not a FALLTHRU edge.  */
2564       if ((s = b->succ) != NULL
2565           && s->succ_next == NULL
2566           && s->dest == c
2567           /* If the jump insn has side effects, we can't tidy the edge.  */
2568           && (GET_CODE (b->end) != JUMP_INSN
2569               || onlyjump_p (b->end)))
2570         tidy_fallthru_edge (s, b, c);
2571     }
2572 }
2573 \f
2574 /* Perform data flow analysis.
2575    F is the first insn of the function; FLAGS is a set of PROP_* flags
2576    to be used in accumulating flow info.  */
2577
2578 void
2579 life_analysis (f, file, flags)
2580      rtx f;
2581      FILE *file;
2582      int flags;
2583 {
2584 #ifdef ELIMINABLE_REGS
2585   register int i;
2586   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
2587 #endif
2588
2589   /* Record which registers will be eliminated.  We use this in
2590      mark_used_regs.  */
2591
2592   CLEAR_HARD_REG_SET (elim_reg_set);
2593
2594 #ifdef ELIMINABLE_REGS
2595   for (i = 0; i < (int) (sizeof eliminables / sizeof eliminables[0]); i++)
2596     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
2597 #else
2598   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
2599 #endif
2600
2601   if (! optimize)
2602     flags &= PROP_DEATH_NOTES | PROP_REG_INFO;
2603
2604   /* The post-reload life analysis have (on a global basis) the same
2605      registers live as was computed by reload itself.  elimination
2606      Otherwise offsets and such may be incorrect.
2607
2608      Reload will make some registers as live even though they do not
2609      appear in the rtl.
2610
2611      We don't want to create new auto-incs after reload, since they
2612      are unlikely to be useful and can cause problems with shared
2613      stack slots.  */
2614   if (reload_completed)
2615     flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
2616
2617   /* We want alias analysis information for local dead store elimination.  */
2618   if (flags & PROP_SCAN_DEAD_CODE)
2619     init_alias_analysis ();
2620
2621   /* Always remove no-op moves.  Do this before other processing so
2622      that we don't have to keep re-scanning them.  */
2623   delete_noop_moves (f);
2624
2625   /* Some targets can emit simpler epilogues if they know that sp was
2626      not ever modified during the function.  After reload, of course,
2627      we've already emitted the epilogue so there's no sense searching.  */
2628   if (! reload_completed)
2629     notice_stack_pointer_modification (f);
2630
2631   /* Allocate and zero out data structures that will record the
2632      data from lifetime analysis.  */
2633   allocate_reg_life_data ();
2634   allocate_bb_life_data ();
2635
2636   /* Find the set of registers live on function exit.  */
2637   mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
2638
2639   /* "Update" life info from zero.  It'd be nice to begin the
2640      relaxation with just the exit and noreturn blocks, but that set
2641      is not immediately handy.  */
2642
2643   if (flags & PROP_REG_INFO)
2644     memset (regs_ever_live, 0, sizeof(regs_ever_live));
2645   update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
2646
2647   /* Clean up.  */
2648   if (flags & PROP_SCAN_DEAD_CODE)
2649     end_alias_analysis ();
2650
2651   if (file)
2652     dump_flow_info (file);
2653
2654   free_basic_block_vars (1);
2655 }
2656
2657 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2658    Search for REGNO.  If found, abort if it is not wider than word_mode.  */
2659
2660 static int
2661 verify_wide_reg_1 (px, pregno)
2662      rtx *px;
2663      void *pregno;
2664 {
2665   rtx x = *px;
2666   unsigned int regno = *(int *) pregno;
2667
2668   if (GET_CODE (x) == REG && REGNO (x) == regno)
2669     {
2670       if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
2671         abort ();
2672       return 1;
2673     }
2674   return 0;
2675 }
2676
2677 /* A subroutine of verify_local_live_at_start.  Search through insns
2678    between HEAD and END looking for register REGNO.  */
2679
2680 static void
2681 verify_wide_reg (regno, head, end)
2682      int regno;
2683      rtx head, end;
2684 {
2685   while (1)
2686     {
2687       if (GET_RTX_CLASS (GET_CODE (head)) == 'i'
2688           && for_each_rtx (&PATTERN (head), verify_wide_reg_1, &regno))
2689         return;
2690       if (head == end)
2691         break;
2692       head = NEXT_INSN (head);
2693     }
2694
2695   /* We didn't find the register at all.  Something's way screwy.  */
2696   abort ();
2697 }
2698
2699 /* A subroutine of update_life_info.  Verify that there are no untoward
2700    changes in live_at_start during a local update.  */
2701
2702 static void
2703 verify_local_live_at_start (new_live_at_start, bb)
2704      regset new_live_at_start;
2705      basic_block bb;
2706 {
2707   if (reload_completed)
2708     {
2709       /* After reload, there are no pseudos, nor subregs of multi-word
2710          registers.  The regsets should exactly match.  */
2711       if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
2712         abort ();
2713     }
2714   else
2715     {
2716       int i;
2717
2718       /* Find the set of changed registers.  */
2719       XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
2720
2721       EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i,
2722         {
2723           /* No registers should die.  */
2724           if (REGNO_REG_SET_P (bb->global_live_at_start, i))
2725             abort ();
2726           /* Verify that the now-live register is wider than word_mode.  */
2727           verify_wide_reg (i, bb->head, bb->end);
2728         });
2729     }
2730 }
2731
2732 /* Updates life information starting with the basic blocks set in BLOCKS.
2733    If BLOCKS is null, consider it to be the universal set.
2734
2735    If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
2736    we are only expecting local modifications to basic blocks.  If we find
2737    extra registers live at the beginning of a block, then we either killed
2738    useful data, or we have a broken split that wants data not provided.
2739    If we find registers removed from live_at_start, that means we have
2740    a broken peephole that is killing a register it shouldn't.
2741
2742    ??? This is not true in one situation -- when a pre-reload splitter
2743    generates subregs of a multi-word pseudo, current life analysis will
2744    lose the kill.  So we _can_ have a pseudo go live.  How irritating.
2745
2746    Including PROP_REG_INFO does not properly refresh regs_ever_live
2747    unless the caller resets it to zero.  */
2748
2749 void
2750 update_life_info (blocks, extent, prop_flags)
2751      sbitmap blocks;
2752      enum update_life_extent extent;
2753      int prop_flags;
2754 {
2755   regset tmp;
2756   regset_head tmp_head;
2757   int i;
2758
2759   tmp = INITIALIZE_REG_SET (tmp_head);
2760
2761   /* For a global update, we go through the relaxation process again.  */
2762   if (extent != UPDATE_LIFE_LOCAL)
2763     {
2764       calculate_global_regs_live (blocks, blocks,
2765                                   prop_flags & PROP_SCAN_DEAD_CODE);
2766
2767       /* If asked, remove notes from the blocks we'll update.  */
2768       if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
2769         count_or_remove_death_notes (blocks, 1);
2770     }
2771
2772   if (blocks)
2773     {
2774       EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
2775         {
2776           basic_block bb = BASIC_BLOCK (i);
2777
2778           COPY_REG_SET (tmp, bb->global_live_at_end);
2779           propagate_block (bb, tmp, (regset) NULL, prop_flags);
2780
2781           if (extent == UPDATE_LIFE_LOCAL)
2782             verify_local_live_at_start (tmp, bb);
2783         });
2784     }
2785   else
2786     {
2787       for (i = n_basic_blocks - 1; i >= 0; --i)
2788         {
2789           basic_block bb = BASIC_BLOCK (i);
2790
2791           COPY_REG_SET (tmp, bb->global_live_at_end);
2792           propagate_block (bb, tmp, (regset) NULL, prop_flags);
2793
2794           if (extent == UPDATE_LIFE_LOCAL)
2795             verify_local_live_at_start (tmp, bb);
2796         }
2797     }
2798
2799   FREE_REG_SET (tmp);
2800
2801   if (prop_flags & PROP_REG_INFO)
2802     {
2803       /* The only pseudos that are live at the beginning of the function
2804          are those that were not set anywhere in the function.  local-alloc
2805          doesn't know how to handle these correctly, so mark them as not
2806          local to any one basic block.  */
2807       EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
2808                                  FIRST_PSEUDO_REGISTER, i,
2809                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
2810
2811       /* We have a problem with any pseudoreg that lives across the setjmp.
2812          ANSI says that if a user variable does not change in value between
2813          the setjmp and the longjmp, then the longjmp preserves it.  This
2814          includes longjmp from a place where the pseudo appears dead.
2815          (In principle, the value still exists if it is in scope.)
2816          If the pseudo goes in a hard reg, some other value may occupy
2817          that hard reg where this pseudo is dead, thus clobbering the pseudo.
2818          Conclusion: such a pseudo must not go in a hard reg.  */
2819       EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
2820                                  FIRST_PSEUDO_REGISTER, i,
2821                                  {
2822                                    if (regno_reg_rtx[i] != 0)
2823                                      {
2824                                        REG_LIVE_LENGTH (i) = -1;
2825                                        REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2826                                      }
2827                                  });
2828     }
2829 }
2830
2831 /* Free the variables allocated by find_basic_blocks.
2832
2833    KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed.  */
2834
2835 void
2836 free_basic_block_vars (keep_head_end_p)
2837      int keep_head_end_p;
2838 {
2839   if (basic_block_for_insn)
2840     {
2841       VARRAY_FREE (basic_block_for_insn);
2842       basic_block_for_insn = NULL;
2843     }
2844
2845   if (! keep_head_end_p)
2846     {
2847       clear_edges ();
2848       VARRAY_FREE (basic_block_info);
2849       n_basic_blocks = 0;
2850
2851       ENTRY_BLOCK_PTR->aux = NULL;
2852       ENTRY_BLOCK_PTR->global_live_at_end = NULL;
2853       EXIT_BLOCK_PTR->aux = NULL;
2854       EXIT_BLOCK_PTR->global_live_at_start = NULL;
2855     }
2856 }
2857
2858 /* Return nonzero if the destination of SET equals the source.  */
2859 static int
2860 set_noop_p (set)
2861      rtx set;
2862 {
2863   rtx src = SET_SRC (set);
2864   rtx dst = SET_DEST (set);
2865
2866   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
2867     {
2868       if (SUBREG_WORD (src) != SUBREG_WORD (dst))
2869         return 0;
2870       src = SUBREG_REG (src);
2871       dst = SUBREG_REG (dst);
2872     }
2873
2874   return (GET_CODE (src) == REG && GET_CODE (dst) == REG
2875           && REGNO (src) == REGNO (dst));
2876 }
2877
2878 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2879    value to itself.  */
2880 static int
2881 noop_move_p (insn)
2882      rtx insn;
2883 {
2884   rtx pat = PATTERN (insn);
2885
2886   /* Insns carrying these notes are useful later on.  */
2887   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
2888     return 0;
2889
2890   if (GET_CODE (pat) == SET && set_noop_p (pat))
2891     return 1;
2892
2893   if (GET_CODE (pat) == PARALLEL)
2894     {
2895       int i;
2896       /* If nothing but SETs of registers to themselves,
2897          this insn can also be deleted.  */
2898       for (i = 0; i < XVECLEN (pat, 0); i++)
2899         {
2900           rtx tem = XVECEXP (pat, 0, i);
2901
2902           if (GET_CODE (tem) == USE
2903               || GET_CODE (tem) == CLOBBER)
2904             continue;
2905
2906           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
2907             return 0;
2908         }
2909
2910       return 1;
2911     }
2912   return 0;
2913 }
2914
2915 /* Delete any insns that copy a register to itself.  */
2916
2917 static void
2918 delete_noop_moves (f)
2919      rtx f;
2920 {
2921   rtx insn;
2922   for (insn = f; insn; insn = NEXT_INSN (insn))
2923     {
2924       if (GET_CODE (insn) == INSN && noop_move_p (insn))
2925         {
2926           PUT_CODE (insn, NOTE);
2927           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2928           NOTE_SOURCE_FILE (insn) = 0;
2929         }
2930     }
2931 }
2932
2933 /* Determine if the stack pointer is constant over the life of the function.
2934    Only useful before prologues have been emitted.  */
2935
2936 static void
2937 notice_stack_pointer_modification_1 (x, pat, data)
2938      rtx x;
2939      rtx pat ATTRIBUTE_UNUSED;
2940      void *data ATTRIBUTE_UNUSED;
2941 {
2942   if (x == stack_pointer_rtx
2943       /* The stack pointer is only modified indirectly as the result
2944          of a push until later in flow.  See the comments in rtl.texi
2945          regarding Embedded Side-Effects on Addresses.  */
2946       || (GET_CODE (x) == MEM
2947           && (GET_CODE (XEXP (x, 0)) == PRE_DEC
2948               || GET_CODE (XEXP (x, 0)) == PRE_INC
2949               || GET_CODE (XEXP (x, 0)) == POST_DEC
2950               || GET_CODE (XEXP (x, 0)) == POST_INC)
2951           && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
2952     current_function_sp_is_unchanging = 0;
2953 }
2954
2955 static void
2956 notice_stack_pointer_modification (f)
2957      rtx f;
2958 {
2959   rtx insn;
2960
2961   /* Assume that the stack pointer is unchanging if alloca hasn't
2962      been used.  */
2963   current_function_sp_is_unchanging = !current_function_calls_alloca;
2964   if (! current_function_sp_is_unchanging)
2965     return;
2966
2967   for (insn = f; insn; insn = NEXT_INSN (insn))
2968     {
2969       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2970         {
2971           /* Check if insn modifies the stack pointer.  */
2972           note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
2973                        NULL);
2974           if (! current_function_sp_is_unchanging)
2975             return;
2976         }
2977     }
2978 }
2979
2980 /* Mark a register in SET.  Hard registers in large modes get all
2981    of their component registers set as well.  */
2982 static void
2983 mark_reg (reg, xset)
2984      rtx reg;
2985      void *xset;
2986 {
2987   regset set = (regset) xset;
2988   int regno = REGNO (reg);
2989
2990   if (GET_MODE (reg) == BLKmode)
2991     abort ();
2992
2993   SET_REGNO_REG_SET (set, regno);
2994   if (regno < FIRST_PSEUDO_REGISTER)
2995     {
2996       int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2997       while (--n > 0)
2998         SET_REGNO_REG_SET (set, regno + n);
2999     }
3000 }
3001
3002 /* Mark those regs which are needed at the end of the function as live
3003    at the end of the last basic block.  */
3004 static void
3005 mark_regs_live_at_end (set)
3006      regset set;
3007 {
3008   int i;
3009
3010   /* If exiting needs the right stack value, consider the stack pointer
3011      live at the end of the function.  */
3012   if ((HAVE_epilogue && reload_completed)
3013       || ! EXIT_IGNORE_STACK
3014       || (! FRAME_POINTER_REQUIRED
3015           && ! current_function_calls_alloca
3016           && flag_omit_frame_pointer)
3017       || current_function_sp_is_unchanging)
3018     {
3019       SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
3020     }
3021
3022   /* Mark the frame pointer if needed at the end of the function.  If
3023      we end up eliminating it, it will be removed from the live list
3024      of each basic block by reload.  */
3025
3026   if (! reload_completed || frame_pointer_needed)
3027     {
3028       SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
3029 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3030       /* If they are different, also mark the hard frame pointer as live */
3031       SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
3032 #endif
3033     }
3034
3035 #ifdef PIC_OFFSET_TABLE_REGNUM
3036 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3037   /* Many architectures have a GP register even without flag_pic.
3038      Assume the pic register is not in use, or will be handled by
3039      other means, if it is not fixed.  */
3040   if (fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3041     SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
3042 #endif
3043 #endif
3044
3045   /* Mark all global registers, and all registers used by the epilogue
3046      as being live at the end of the function since they may be
3047      referenced by our caller.  */
3048   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3049     if (global_regs[i]
3050 #ifdef EPILOGUE_USES
3051         || EPILOGUE_USES (i)
3052 #endif
3053         )
3054       SET_REGNO_REG_SET (set, i);
3055
3056   /* Mark all call-saved registers that we actaully used.  */
3057   if (HAVE_epilogue && reload_completed)
3058     {
3059       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3060         if (! call_used_regs[i] && regs_ever_live[i])
3061           SET_REGNO_REG_SET (set, i);
3062     }
3063
3064   /* Mark function return value.  */
3065   diddle_return_value (mark_reg, set);
3066 }
3067
3068 /* Callback function for for_each_successor_phi.  DATA is a regset.
3069    Sets the SRC_REGNO, the regno of the phi alternative for phi node
3070    INSN, in the regset.  */
3071
3072 static int
3073 set_phi_alternative_reg (insn, dest_regno, src_regno, data)
3074      rtx insn ATTRIBUTE_UNUSED;
3075      int dest_regno ATTRIBUTE_UNUSED;
3076      int src_regno;
3077      void *data;
3078 {
3079   regset live = (regset) data;
3080   SET_REGNO_REG_SET (live, src_regno);
3081   return 0;
3082 }
3083
3084 /* Propagate global life info around the graph of basic blocks.  Begin
3085    considering blocks with their corresponding bit set in BLOCKS_IN.
3086    If BLOCKS_IN is null, consider it the universal set.
3087
3088    BLOCKS_OUT is set for every block that was changed.  */
3089
3090 static void
3091 calculate_global_regs_live (blocks_in, blocks_out, flags)
3092      sbitmap blocks_in, blocks_out;
3093      int flags;
3094 {
3095   basic_block *queue, *qhead, *qtail, *qend;
3096   regset tmp, new_live_at_end;
3097   regset_head tmp_head;
3098   regset_head new_live_at_end_head;
3099   int i;
3100
3101   tmp = INITIALIZE_REG_SET (tmp_head);
3102   new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
3103
3104   /* Create a worklist.  Allocate an extra slot for ENTRY_BLOCK, and one
3105      because the `head == tail' style test for an empty queue doesn't
3106      work with a full queue.  */
3107   queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
3108   qtail = queue;
3109   qhead = qend = queue + n_basic_blocks + 2;
3110
3111   /* Clear out the garbage that might be hanging out in bb->aux.  */
3112   for (i = n_basic_blocks - 1; i >= 0; --i)
3113     BASIC_BLOCK (i)->aux = NULL;
3114
3115   /* Queue the blocks set in the initial mask.  Do this in reverse block
3116      number order so that we are more likely for the first round to do
3117      useful work.  We use AUX non-null to flag that the block is queued.  */
3118   if (blocks_in)
3119     {
3120       EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
3121         {
3122           basic_block bb = BASIC_BLOCK (i);
3123           *--qhead = bb;
3124           bb->aux = bb;
3125         });
3126     }
3127   else
3128     {
3129       for (i = 0; i < n_basic_blocks; ++i)
3130         {
3131           basic_block bb = BASIC_BLOCK (i);
3132           *--qhead = bb;
3133           bb->aux = bb;
3134         }
3135     }
3136
3137   if (blocks_out)
3138     sbitmap_zero (blocks_out);
3139
3140   while (qhead != qtail)
3141     {
3142       int rescan, changed;
3143       basic_block bb;
3144       edge e;
3145
3146       bb = *qhead++;
3147       if (qhead == qend)
3148         qhead = queue;
3149       bb->aux = NULL;
3150
3151       /* Begin by propogating live_at_start from the successor blocks.  */
3152       CLEAR_REG_SET (new_live_at_end);
3153       for (e = bb->succ; e ; e = e->succ_next)
3154         {
3155           basic_block sb = e->dest;
3156           IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
3157         }
3158
3159       /* Force the stack pointer to be live -- which might not already be
3160          the case for blocks within infinite loops.  */
3161       SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
3162
3163       /* Regs used in phi nodes are not included in
3164          global_live_at_start, since they are live only along a
3165          particular edge.  Set those regs that are live because of a
3166          phi node alternative corresponding to this particular block.  */
3167       if (in_ssa_form)
3168         for_each_successor_phi (bb, &set_phi_alternative_reg,
3169                                 new_live_at_end);
3170
3171       if (bb == ENTRY_BLOCK_PTR)
3172         {
3173           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3174           continue;
3175         }
3176
3177       /* On our first pass through this block, we'll go ahead and continue.
3178          Recognize first pass by local_set NULL.  On subsequent passes, we
3179          get to skip out early if live_at_end wouldn't have changed.  */
3180
3181       if (bb->local_set == NULL)
3182         {
3183           bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
3184           rescan = 1;
3185         }
3186       else
3187         {
3188           /* If any bits were removed from live_at_end, we'll have to
3189              rescan the block.  This wouldn't be necessary if we had
3190              precalculated local_live, however with PROP_SCAN_DEAD_CODE
3191              local_live is really dependant on live_at_end.  */
3192           CLEAR_REG_SET (tmp);
3193           rescan = bitmap_operation (tmp, bb->global_live_at_end,
3194                                      new_live_at_end, BITMAP_AND_COMPL);
3195
3196           if (! rescan)
3197             {
3198               /* Find the set of changed bits.  Take this opportunity
3199                  to notice that this set is empty and early out.  */
3200               CLEAR_REG_SET (tmp);
3201               changed = bitmap_operation (tmp, bb->global_live_at_end,
3202                                           new_live_at_end, BITMAP_XOR);
3203               if (! changed)
3204                 continue;
3205
3206               /* If any of the changed bits overlap with local_set,
3207                  we'll have to rescan the block.  Detect overlap by
3208                  the AND with ~local_set turning off bits.  */
3209               rescan = bitmap_operation (tmp, tmp, bb->local_set,
3210                                          BITMAP_AND_COMPL);
3211             }
3212         }
3213
3214       /* Let our caller know that BB changed enough to require its
3215          death notes updated.  */
3216       if (blocks_out)
3217         SET_BIT (blocks_out, bb->index);
3218
3219       if (! rescan)
3220         {
3221           /* Add to live_at_start the set of all registers in
3222              new_live_at_end that aren't in the old live_at_end.  */
3223
3224           bitmap_operation (tmp, new_live_at_end, bb->global_live_at_end,
3225                             BITMAP_AND_COMPL);
3226           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3227
3228           changed = bitmap_operation (bb->global_live_at_start,
3229                                       bb->global_live_at_start,
3230                                       tmp, BITMAP_IOR);
3231           if (! changed)
3232             continue;
3233         }
3234       else
3235         {
3236           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3237
3238           /* Rescan the block insn by insn to turn (a copy of) live_at_end
3239              into live_at_start.  */
3240           propagate_block (bb, new_live_at_end, bb->local_set, flags);
3241
3242           /* If live_at start didn't change, no need to go farther.  */
3243           if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
3244             continue;
3245
3246           COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
3247         }
3248
3249       /* Queue all predecessors of BB so that we may re-examine
3250          their live_at_end.  */
3251       for (e = bb->pred; e ; e = e->pred_next)
3252         {
3253           basic_block pb = e->src;
3254           if (pb->aux == NULL)
3255             {
3256               *qtail++ = pb;
3257               if (qtail == qend)
3258                 qtail = queue;
3259               pb->aux = pb;
3260             }
3261         }
3262     }
3263
3264   FREE_REG_SET (tmp);
3265   FREE_REG_SET (new_live_at_end);
3266
3267   if (blocks_out)
3268     {
3269       EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
3270         {
3271           basic_block bb = BASIC_BLOCK (i);
3272           FREE_REG_SET (bb->local_set);
3273         });
3274     }
3275   else
3276     {
3277       for (i = n_basic_blocks - 1; i >= 0; --i)
3278         {
3279           basic_block bb = BASIC_BLOCK (i);
3280           FREE_REG_SET (bb->local_set);
3281         }
3282     }
3283
3284   free (queue);
3285 }
3286 \f
3287 /* Subroutines of life analysis.  */
3288
3289 /* Allocate the permanent data structures that represent the results
3290    of life analysis.  Not static since used also for stupid life analysis.  */
3291
3292 void
3293 allocate_bb_life_data ()
3294 {
3295   register int i;
3296
3297   for (i = 0; i < n_basic_blocks; i++)
3298     {
3299       basic_block bb = BASIC_BLOCK (i);
3300
3301       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
3302       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
3303     }
3304
3305   ENTRY_BLOCK_PTR->global_live_at_end
3306     = OBSTACK_ALLOC_REG_SET (function_obstack);
3307   EXIT_BLOCK_PTR->global_live_at_start
3308     = OBSTACK_ALLOC_REG_SET (function_obstack);
3309
3310   regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
3311 }
3312
3313 void
3314 allocate_reg_life_data ()
3315 {
3316   int i;
3317
3318   max_regno = max_reg_num ();
3319
3320   /* Recalculate the register space, in case it has grown.  Old style
3321      vector oriented regsets would set regset_{size,bytes} here also.  */
3322   allocate_reg_info (max_regno, FALSE, FALSE);
3323
3324   /* Reset all the data we'll collect in propagate_block and its
3325      subroutines.  */
3326   for (i = 0; i < max_regno; i++)
3327     {
3328       REG_N_SETS (i) = 0;
3329       REG_N_REFS (i) = 0;
3330       REG_N_DEATHS (i) = 0;
3331       REG_N_CALLS_CROSSED (i) = 0;
3332       REG_LIVE_LENGTH (i) = 0;
3333       REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
3334     }
3335 }
3336
3337 /* Delete dead instructions for propagate_block.  */
3338
3339 static void
3340 propagate_block_delete_insn (bb, insn)
3341      basic_block bb;
3342      rtx insn;
3343 {
3344   rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
3345
3346   /* If the insn referred to a label, and that label was attached to
3347      an ADDR_VEC, it's safe to delete the ADDR_VEC.  In fact, it's
3348      pretty much mandatory to delete it, because the ADDR_VEC may be
3349      referencing labels that no longer exist.  */
3350
3351   if (inote)
3352     {
3353       rtx label = XEXP (inote, 0);
3354       rtx next;
3355
3356       if (LABEL_NUSES (label) == 1
3357           && (next = next_nonnote_insn (label)) != NULL
3358           && GET_CODE (next) == JUMP_INSN
3359           && (GET_CODE (PATTERN (next)) == ADDR_VEC
3360               || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
3361         {
3362           rtx pat = PATTERN (next);
3363           int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3364           int len = XVECLEN (pat, diff_vec_p);
3365           int i;
3366
3367           for (i = 0; i < len; i++)
3368             LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
3369
3370           flow_delete_insn (next);
3371         }
3372     }
3373
3374   if (bb->end == insn)
3375     bb->end = PREV_INSN (insn);
3376   flow_delete_insn (insn);
3377 }
3378
3379 /* Delete dead libcalls for propagate_block.  Return the insn
3380    before the libcall.  */
3381
3382 static rtx
3383 propagate_block_delete_libcall (bb, insn, note)
3384      basic_block bb;
3385      rtx insn, note;
3386 {
3387   rtx first = XEXP (note, 0);
3388   rtx before = PREV_INSN (first);
3389
3390   if (insn == bb->end)
3391     bb->end = before;
3392
3393   flow_delete_insn_chain (first, insn);
3394   return before;
3395 }
3396
3397 /* Update the life-status of regs for one insn.  Return the previous insn.  */
3398
3399 rtx
3400 propagate_one_insn (pbi, insn)
3401      struct propagate_block_info *pbi;
3402      rtx insn;
3403 {
3404   rtx prev = PREV_INSN (insn);
3405   int flags = pbi->flags;
3406   int insn_is_dead = 0;
3407   int libcall_is_dead = 0;
3408   rtx note;
3409   int i;
3410
3411   if (! INSN_P (insn))
3412     return prev;
3413
3414   note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3415   if (flags & PROP_SCAN_DEAD_CODE)
3416     {
3417       insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
3418                                   REG_NOTES (insn));
3419       libcall_is_dead = (insn_is_dead && note != 0
3420                          && libcall_dead_p (pbi, PATTERN (insn),
3421                                             note, insn));
3422     }
3423
3424   /* We almost certainly don't want to delete prologue or epilogue
3425      instructions.  Warn about probable compiler losage.  */
3426   if (insn_is_dead
3427       && reload_completed
3428       && (((HAVE_epilogue || HAVE_prologue)
3429            && prologue_epilogue_contains (insn))
3430           || (HAVE_sibcall_epilogue
3431               && sibcall_epilogue_contains (insn))))
3432     {
3433       if (flags & PROP_KILL_DEAD_CODE)
3434         {
3435           warning ("ICE: would have deleted prologue/epilogue insn");
3436           if (!inhibit_warnings)
3437             debug_rtx (insn);
3438         }
3439       libcall_is_dead = insn_is_dead = 0;
3440     }
3441
3442   /* If an instruction consists of just dead store(s) on final pass,
3443      delete it.  */
3444   if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
3445     {
3446       /* Record sets.  Do this even for dead instructions, since they
3447          would have killed the values if they hadn't been deleted.  */
3448       mark_set_regs (pbi, PATTERN (insn), insn);
3449
3450       /* CC0 is now known to be dead.  Either this insn used it,
3451          in which case it doesn't anymore, or clobbered it,
3452          so the next insn can't use it.  */
3453       pbi->cc0_live = 0;
3454
3455       if (libcall_is_dead)
3456         {
3457           prev = propagate_block_delete_libcall (pbi->bb, insn, note);
3458           insn = NEXT_INSN (prev);
3459         }
3460       else
3461         propagate_block_delete_insn (pbi->bb, insn);
3462
3463       return prev;
3464     }
3465
3466   /* See if this is an increment or decrement that can be merged into
3467      a following memory address.  */
3468 #ifdef AUTO_INC_DEC
3469   {
3470     register rtx x = single_set (insn);
3471
3472     /* Does this instruction increment or decrement a register?  */
3473     if ((flags & PROP_AUTOINC)
3474         && x != 0
3475         && GET_CODE (SET_DEST (x)) == REG
3476         && (GET_CODE (SET_SRC (x)) == PLUS
3477             || GET_CODE (SET_SRC (x)) == MINUS)
3478         && XEXP (SET_SRC (x), 0) == SET_DEST (x)
3479         && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
3480         /* Ok, look for a following memory ref we can combine with.
3481            If one is found, change the memory ref to a PRE_INC
3482            or PRE_DEC, cancel this insn, and return 1.
3483            Return 0 if nothing has been done.  */
3484         && try_pre_increment_1 (pbi, insn))
3485       return prev;
3486   }
3487 #endif /* AUTO_INC_DEC */
3488
3489   CLEAR_REG_SET (pbi->new_set);
3490
3491   /* If this is not the final pass, and this insn is copying the value of
3492      a library call and it's dead, don't scan the insns that perform the
3493      library call, so that the call's arguments are not marked live.  */
3494   if (libcall_is_dead)
3495     {
3496       /* Record the death of the dest reg.  */
3497       mark_set_regs (pbi, PATTERN (insn), insn);
3498
3499       insn = XEXP (note, 0);
3500       return PREV_INSN (insn);
3501     }
3502   else if (GET_CODE (PATTERN (insn)) == SET
3503            && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
3504            && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
3505            && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
3506            && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
3507     /* We have an insn to pop a constant amount off the stack.
3508        (Such insns use PLUS regardless of the direction of the stack,
3509        and any insn to adjust the stack by a constant is always a pop.)
3510        These insns, if not dead stores, have no effect on life.  */
3511     ;
3512   else
3513     {
3514       /* Any regs live at the time of a call instruction must not go
3515          in a register clobbered by calls.  Find all regs now live and
3516          record this for them.  */
3517
3518       if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
3519         EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3520                                    { REG_N_CALLS_CROSSED (i)++; });
3521
3522       /* Record sets.  Do this even for dead instructions, since they
3523          would have killed the values if they hadn't been deleted.  */
3524       mark_set_regs (pbi, PATTERN (insn), insn);
3525
3526       if (GET_CODE (insn) == CALL_INSN)
3527         {
3528           register int i;
3529           rtx note, cond;
3530
3531           cond = NULL_RTX;
3532           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3533             cond = COND_EXEC_TEST (PATTERN (insn));
3534
3535           /* Non-constant calls clobber memory.  */
3536           if (! CONST_CALL_P (insn))
3537             free_EXPR_LIST_list (&pbi->mem_set_list);
3538
3539           /* There may be extra registers to be clobbered.  */
3540           for (note = CALL_INSN_FUNCTION_USAGE (insn);
3541                note;
3542                note = XEXP (note, 1))
3543             if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3544               mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
3545                           cond, insn, pbi->flags);
3546
3547           /* Calls change all call-used and global registers.  */
3548           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3549             if (call_used_regs[i] && ! global_regs[i]
3550                 && ! fixed_regs[i])
3551               {
3552                 /* We do not want REG_UNUSED notes for these registers.  */
3553                 mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
3554                             cond, insn,
3555                             pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
3556               }
3557         }
3558
3559       /* If an insn doesn't use CC0, it becomes dead since we assume
3560          that every insn clobbers it.  So show it dead here;
3561          mark_used_regs will set it live if it is referenced.  */
3562       pbi->cc0_live = 0;
3563
3564       /* Record uses.  */
3565       if (! insn_is_dead)
3566         mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
3567
3568       /* Sometimes we may have inserted something before INSN (such as a move)
3569          when we make an auto-inc.  So ensure we will scan those insns.  */
3570 #ifdef AUTO_INC_DEC
3571       prev = PREV_INSN (insn);
3572 #endif
3573
3574       if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
3575         {
3576           register int i;
3577           rtx note, cond;
3578
3579           cond = NULL_RTX;
3580           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3581             cond = COND_EXEC_TEST (PATTERN (insn));
3582
3583           /* Calls use their arguments.  */
3584           for (note = CALL_INSN_FUNCTION_USAGE (insn);
3585                note;
3586                note = XEXP (note, 1))
3587             if (GET_CODE (XEXP (note, 0)) == USE)
3588               mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
3589                               cond, insn);
3590
3591           /* The stack ptr is used (honorarily) by a CALL insn.  */
3592           SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
3593
3594           /* Calls may also reference any of the global registers,
3595              so they are made live.  */
3596           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3597             if (global_regs[i])
3598               mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
3599                              cond, insn);
3600         }
3601     }
3602
3603   /* On final pass, update counts of how many insns in which each reg
3604      is live.  */
3605   if (flags & PROP_REG_INFO)
3606     EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3607                                { REG_LIVE_LENGTH (i)++; });
3608
3609   return prev;
3610 }
3611
3612 /* Initialize a propagate_block_info struct for public consumption.
3613    Note that the structure itself is opaque to this file, but that
3614    the user can use the regsets provided here.  */
3615
3616 struct propagate_block_info *
3617 init_propagate_block_info (bb, live, local_set, flags)
3618      basic_block bb;
3619      regset live;
3620      regset local_set;
3621      int flags;
3622 {
3623   struct propagate_block_info *pbi = xmalloc (sizeof(*pbi));
3624
3625   pbi->bb = bb;
3626   pbi->reg_live = live;
3627   pbi->mem_set_list = NULL_RTX;
3628   pbi->local_set = local_set;
3629   pbi->cc0_live = 0;
3630   pbi->flags = flags;
3631
3632   if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3633     pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
3634   else
3635     pbi->reg_next_use = NULL;
3636
3637   pbi->new_set = BITMAP_XMALLOC ();
3638
3639 #ifdef HAVE_conditional_execution
3640   pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
3641                                        free_reg_cond_life_info);
3642   pbi->reg_cond_reg = BITMAP_XMALLOC ();
3643
3644   /* If this block ends in a conditional branch, for each register live
3645      from one side of the branch and not the other, record the register
3646      as conditionally dead.  */
3647   if ((flags & (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE))
3648       && GET_CODE (bb->end) == JUMP_INSN
3649       && any_condjump_p (bb->end))
3650     {
3651       regset_head diff_head;
3652       regset diff = INITIALIZE_REG_SET (diff_head);
3653       basic_block bb_true, bb_false;
3654       rtx cond_true, cond_false;
3655       int i;
3656
3657       /* Identify the successor blocks.  */
3658       bb_true = bb->succ->dest;
3659       if (bb->succ->succ_next != NULL)
3660         {
3661           bb_false = bb->succ->succ_next->dest;
3662
3663           if (bb->succ->flags & EDGE_FALLTHRU)
3664             {
3665               basic_block t = bb_false;
3666               bb_false = bb_true;
3667               bb_true = t;
3668             }
3669           else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
3670             abort ();
3671         }
3672       else
3673         {
3674           /* This can happen with a conditional jump to the next insn.  */
3675           if (JUMP_LABEL (bb->end) != bb_true->head)
3676             abort ();
3677
3678           /* Simplest way to do nothing.  */
3679           bb_false = bb_true;
3680         }
3681
3682       /* Extract the condition from the branch.  */
3683       cond_true = XEXP (SET_SRC (PATTERN (bb->end)), 0);
3684       cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
3685                                    GET_MODE (cond_true), XEXP (cond_true, 0),
3686                                    XEXP (cond_true, 1));
3687       if (GET_CODE (XEXP (SET_SRC (PATTERN (bb->end)), 1)) == PC)
3688         {
3689           rtx t = cond_false;
3690           cond_false = cond_true;
3691           cond_true = t;
3692         }
3693
3694       /* Compute which register lead different lives in the successors.  */
3695       if (bitmap_operation (diff, bb_true->global_live_at_start,
3696                             bb_false->global_live_at_start, BITMAP_XOR))
3697         {
3698           if (GET_CODE (XEXP (cond_true, 0)) != REG)
3699             abort ();
3700           SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond_true, 0)));
3701
3702           /* For each such register, mark it conditionally dead.  */
3703           EXECUTE_IF_SET_IN_REG_SET
3704             (diff, 0, i,
3705              {
3706                struct reg_cond_life_info *rcli;
3707                rtx cond;
3708
3709                rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
3710
3711                if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
3712                  cond = cond_false;
3713                else
3714                  cond = cond_true;
3715                rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
3716
3717                splay_tree_insert (pbi->reg_cond_dead, i,
3718                                   (splay_tree_value) rcli);
3719              });
3720         }
3721
3722       FREE_REG_SET (diff);
3723     }
3724 #endif
3725
3726   /* If this block has no successors, any stores to the frame that aren't
3727      used later in the block are dead.  So make a pass over the block
3728      recording any such that are made and show them dead at the end.  We do
3729      a very conservative and simple job here.  */
3730   if ((flags & PROP_SCAN_DEAD_CODE)
3731       && (bb->succ == NULL
3732           || (bb->succ->succ_next == NULL
3733               && bb->succ->dest == EXIT_BLOCK_PTR)))
3734     {
3735       rtx insn;
3736       for (insn = bb->end; insn != bb->head; insn = PREV_INSN (insn))
3737         if (GET_CODE (insn) == INSN
3738             && GET_CODE (PATTERN (insn)) == SET
3739             && GET_CODE (SET_DEST (PATTERN (insn))) == MEM)
3740           {
3741             rtx mem = SET_DEST (PATTERN (insn));
3742
3743             if (XEXP (mem, 0) == frame_pointer_rtx
3744                 || (GET_CODE (XEXP (mem, 0)) == PLUS
3745                     && XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx
3746                     && GET_CODE (XEXP (XEXP (mem, 0), 1)) == CONST_INT))
3747               pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
3748           }
3749     }
3750
3751   return pbi;
3752 }
3753
3754 /* Release a propagate_block_info struct.  */
3755
3756 void
3757 free_propagate_block_info (pbi)
3758      struct propagate_block_info *pbi;
3759 {
3760   free_EXPR_LIST_list (&pbi->mem_set_list);
3761
3762   BITMAP_XFREE (pbi->new_set);
3763
3764 #ifdef HAVE_conditional_execution
3765   splay_tree_delete (pbi->reg_cond_dead);
3766   BITMAP_XFREE (pbi->reg_cond_reg);
3767 #endif
3768
3769   if (pbi->reg_next_use)
3770     free (pbi->reg_next_use);
3771
3772   free (pbi);
3773 }
3774
3775 /* Compute the registers live at the beginning of a basic block BB from
3776    those live at the end.
3777
3778    When called, REG_LIVE contains those live at the end.  On return, it
3779    contains those live at the beginning.
3780
3781    LOCAL_SET, if non-null, will be set with all registers killed by
3782    this basic block.  */
3783
3784 void
3785 propagate_block (bb, live, local_set, flags)
3786      basic_block bb;
3787      regset live;
3788      regset local_set;
3789      int flags;
3790 {
3791   struct propagate_block_info *pbi;
3792   rtx insn, prev;
3793
3794   pbi = init_propagate_block_info (bb, live, local_set, flags);
3795
3796   if (flags & PROP_REG_INFO)
3797     {
3798       register int i;
3799
3800       /* Process the regs live at the end of the block.
3801          Mark them as not local to any one basic block. */
3802       EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
3803                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
3804     }
3805
3806   /* Scan the block an insn at a time from end to beginning.  */
3807
3808   for (insn = bb->end; ; insn = prev)
3809     {
3810       /* If this is a call to `setjmp' et al, warn if any
3811          non-volatile datum is live.  */
3812       if ((flags & PROP_REG_INFO)
3813           && GET_CODE (insn) == NOTE
3814           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3815         IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
3816
3817       prev = propagate_one_insn (pbi, insn);
3818
3819       if (insn == bb->head)
3820         break;
3821     }
3822
3823   free_propagate_block_info (pbi);
3824 }
3825 \f
3826 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3827    (SET expressions whose destinations are registers dead after the insn).
3828    NEEDED is the regset that says which regs are alive after the insn.
3829
3830    Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3831
3832    If X is the entire body of an insn, NOTES contains the reg notes
3833    pertaining to the insn.  */
3834
3835 static int
3836 insn_dead_p (pbi, x, call_ok, notes)
3837      struct propagate_block_info *pbi;
3838      rtx x;
3839      int call_ok;
3840      rtx notes ATTRIBUTE_UNUSED;
3841 {
3842   enum rtx_code code = GET_CODE (x);
3843
3844 #ifdef AUTO_INC_DEC
3845   /* If flow is invoked after reload, we must take existing AUTO_INC
3846      expresions into account.  */
3847   if (reload_completed)
3848     {
3849       for ( ; notes; notes = XEXP (notes, 1))
3850         {
3851           if (REG_NOTE_KIND (notes) == REG_INC)
3852             {
3853               int regno = REGNO (XEXP (notes, 0));
3854
3855               /* Don't delete insns to set global regs.  */
3856               if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3857                   || REGNO_REG_SET_P (pbi->reg_live, regno))
3858                 return 0;
3859             }
3860         }
3861     }
3862 #endif
3863
3864   /* If setting something that's a reg or part of one,
3865      see if that register's altered value will be live.  */
3866
3867   if (code == SET)
3868     {
3869       rtx r = SET_DEST (x);
3870
3871 #ifdef HAVE_cc0
3872       if (GET_CODE (r) == CC0)
3873         return ! pbi->cc0_live;
3874 #endif
3875
3876       /* A SET that is a subroutine call cannot be dead.  */
3877       if (GET_CODE (SET_SRC (x)) == CALL)
3878         {
3879           if (! call_ok)
3880             return 0;
3881         }
3882
3883       /* Don't eliminate loads from volatile memory or volatile asms.  */
3884       else if (volatile_refs_p (SET_SRC (x)))
3885         return 0;
3886
3887       if (GET_CODE (r) == MEM)
3888         {
3889           rtx temp;
3890
3891           if (MEM_VOLATILE_P (r))
3892             return 0;
3893
3894           /* Walk the set of memory locations we are currently tracking
3895              and see if one is an identical match to this memory location.
3896              If so, this memory write is dead (remember, we're walking
3897              backwards from the end of the block to the start).  */
3898           temp = pbi->mem_set_list;
3899           while (temp)
3900             {
3901               if (rtx_equal_p (XEXP (temp, 0), r))
3902                 return 1;
3903               temp = XEXP (temp, 1);
3904             }
3905         }
3906       else
3907         {
3908           while (GET_CODE (r) == SUBREG
3909                  || GET_CODE (r) == STRICT_LOW_PART
3910                  || GET_CODE (r) == ZERO_EXTRACT)
3911             r = XEXP (r, 0);
3912
3913           if (GET_CODE (r) == REG)
3914             {
3915               int regno = REGNO (r);
3916
3917               /* Obvious.  */
3918               if (REGNO_REG_SET_P (pbi->reg_live, regno))
3919                 return 0;
3920
3921               /* If this is a hard register, verify that subsequent
3922                  words are not needed.  */
3923               if (regno < FIRST_PSEUDO_REGISTER)
3924                 {
3925                   int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
3926
3927                   while (--n > 0)
3928                     if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
3929                       return 0;
3930                 }
3931
3932               /* Don't delete insns to set global regs.  */
3933               if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3934                 return 0;
3935
3936               /* Make sure insns to set the stack pointer aren't deleted.  */
3937               if (regno == STACK_POINTER_REGNUM)
3938                 return 0;
3939
3940               /* Make sure insns to set the frame pointer aren't deleted.  */
3941               if (regno == FRAME_POINTER_REGNUM
3942                   && (! reload_completed || frame_pointer_needed))
3943                 return 0;
3944 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3945               if (regno == HARD_FRAME_POINTER_REGNUM
3946                   && (! reload_completed || frame_pointer_needed))
3947                 return 0;
3948 #endif
3949
3950 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3951               /* Make sure insns to set arg pointer are never deleted
3952                  (if the arg pointer isn't fixed, there will be a USE
3953                  for it, so we can treat it normally).  */
3954               if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
3955                 return 0;
3956 #endif
3957
3958 #ifdef PIC_OFFSET_TABLE_REGNUM
3959               /* Before reload, do not allow sets of the pic register
3960                  to be deleted.  Reload can insert references to
3961                  constant pool memory anywhere in the function, making
3962                  the PIC register live where it wasn't before.  */
3963               if (regno == PIC_OFFSET_TABLE_REGNUM && fixed_regs[regno]
3964                   && ! reload_completed)
3965                 return 0;
3966 #endif
3967
3968               /* Otherwise, the set is dead.  */
3969               return 1;
3970             }
3971         }
3972     }
3973
3974   /* If performing several activities, insn is dead if each activity
3975      is individually dead.  Also, CLOBBERs and USEs can be ignored; a
3976      CLOBBER or USE that's inside a PARALLEL doesn't make the insn
3977      worth keeping.  */
3978   else if (code == PARALLEL)
3979     {
3980       int i = XVECLEN (x, 0);
3981
3982       for (i--; i >= 0; i--)
3983         if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
3984             && GET_CODE (XVECEXP (x, 0, i)) != USE
3985             && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
3986           return 0;
3987
3988       return 1;
3989     }
3990
3991   /* A CLOBBER of a pseudo-register that is dead serves no purpose.  That
3992      is not necessarily true for hard registers.  */
3993   else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
3994            && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
3995            && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
3996     return 1;
3997
3998   /* We do not check other CLOBBER or USE here.  An insn consisting of just
3999      a CLOBBER or just a USE should not be deleted.  */
4000   return 0;
4001 }
4002
4003 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
4004    return 1 if the entire library call is dead.
4005    This is true if X copies a register (hard or pseudo)
4006    and if the hard return  reg of the call insn is dead.
4007    (The caller should have tested the destination of X already for death.)
4008
4009    If this insn doesn't just copy a register, then we don't
4010    have an ordinary libcall.  In that case, cse could not have
4011    managed to substitute the source for the dest later on,
4012    so we can assume the libcall is dead.
4013
4014    NEEDED is the bit vector of pseudoregs live before this insn.
4015    NOTE is the REG_RETVAL note of the insn.  INSN is the insn itself.  */
4016
4017 static int
4018 libcall_dead_p (pbi, x, note, insn)
4019      struct propagate_block_info *pbi;
4020      rtx x;
4021      rtx note;
4022      rtx insn;
4023 {
4024   register RTX_CODE code = GET_CODE (x);
4025
4026   if (code == SET)
4027     {
4028       register rtx r = SET_SRC (x);
4029       if (GET_CODE (r) == REG)
4030         {
4031           rtx call = XEXP (note, 0);
4032           rtx call_pat;
4033           register int i;
4034
4035           /* Find the call insn.  */
4036           while (call != insn && GET_CODE (call) != CALL_INSN)
4037             call = NEXT_INSN (call);
4038
4039           /* If there is none, do nothing special,
4040              since ordinary death handling can understand these insns.  */
4041           if (call == insn)
4042             return 0;
4043
4044           /* See if the hard reg holding the value is dead.
4045              If this is a PARALLEL, find the call within it.  */
4046           call_pat = PATTERN (call);
4047           if (GET_CODE (call_pat) == PARALLEL)
4048             {
4049               for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
4050                 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
4051                     && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
4052                   break;
4053
4054               /* This may be a library call that is returning a value
4055                  via invisible pointer.  Do nothing special, since
4056                  ordinary death handling can understand these insns.  */
4057               if (i < 0)
4058                 return 0;
4059
4060               call_pat = XVECEXP (call_pat, 0, i);
4061             }
4062
4063           return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
4064         }
4065     }
4066   return 1;
4067 }
4068
4069 /* Return 1 if register REGNO was used before it was set, i.e. if it is
4070    live at function entry.  Don't count global register variables, variables
4071    in registers that can be used for function arg passing, or variables in
4072    fixed hard registers.  */
4073
4074 int
4075 regno_uninitialized (regno)
4076      int regno;
4077 {
4078   if (n_basic_blocks == 0
4079       || (regno < FIRST_PSEUDO_REGISTER
4080           && (global_regs[regno]
4081               || fixed_regs[regno]
4082               || FUNCTION_ARG_REGNO_P (regno))))
4083     return 0;
4084
4085   return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno);
4086 }
4087
4088 /* 1 if register REGNO was alive at a place where `setjmp' was called
4089    and was set more than once or is an argument.
4090    Such regs may be clobbered by `longjmp'.  */
4091
4092 int
4093 regno_clobbered_at_setjmp (regno)
4094      int regno;
4095 {
4096   if (n_basic_blocks == 0)
4097     return 0;
4098
4099   return ((REG_N_SETS (regno) > 1
4100            || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno))
4101           && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
4102 }
4103 \f
4104 /* INSN references memory, possibly using autoincrement addressing modes.
4105    Find any entries on the mem_set_list that need to be invalidated due
4106    to an address change.  */
4107
4108 static void
4109 invalidate_mems_from_autoinc (pbi, insn)
4110      struct propagate_block_info *pbi;
4111      rtx insn;
4112 {
4113   rtx note = REG_NOTES (insn);
4114   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
4115     {
4116       if (REG_NOTE_KIND (note) == REG_INC)
4117         {
4118           rtx temp = pbi->mem_set_list;
4119           rtx prev = NULL_RTX;
4120           rtx next;
4121
4122           while (temp)
4123             {
4124               next = XEXP (temp, 1);
4125               if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
4126                 {
4127                   /* Splice temp out of list.  */
4128                   if (prev)
4129                     XEXP (prev, 1) = next;
4130                   else
4131                     pbi->mem_set_list = next;
4132                   free_EXPR_LIST_node (temp);
4133                 }
4134               else
4135                 prev = temp;
4136               temp = next;
4137             }
4138         }
4139     }
4140 }
4141
4142 /* Process the registers that are set within X.  Their bits are set to
4143    1 in the regset DEAD, because they are dead prior to this insn.
4144
4145    If INSN is nonzero, it is the insn being processed.
4146
4147    FLAGS is the set of operations to perform.  */
4148
4149 static void
4150 mark_set_regs (pbi, x, insn)
4151      struct propagate_block_info *pbi;
4152      rtx x, insn;
4153 {
4154   rtx cond = NULL_RTX;
4155   enum rtx_code code;
4156
4157  retry:
4158   switch (code = GET_CODE (x))
4159     {
4160     case SET:
4161     case CLOBBER:
4162       mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
4163       return;
4164
4165     case COND_EXEC:
4166       cond = COND_EXEC_TEST (x);
4167       x = COND_EXEC_CODE (x);
4168       goto retry;
4169
4170     case PARALLEL:
4171       {
4172         register int i;
4173         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4174           {
4175             rtx sub = XVECEXP (x, 0, i);
4176             switch (code = GET_CODE (sub))
4177               {
4178               case COND_EXEC:
4179                 if (cond != NULL_RTX)
4180                   abort ();
4181
4182                 cond = COND_EXEC_TEST (sub);
4183                 sub = COND_EXEC_CODE (sub);
4184                 if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
4185                   break;
4186                 /* FALLTHRU */
4187
4188               case SET:
4189               case CLOBBER:
4190                 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
4191                 break;
4192
4193               default:
4194                 break;
4195               }
4196           }
4197         break;
4198       }
4199
4200     default:
4201       break;
4202     }
4203 }
4204
4205 /* Process a single SET rtx, X.  */
4206
4207 static void
4208 mark_set_1 (pbi, code, reg, cond, insn, flags)
4209      struct propagate_block_info *pbi;
4210      enum rtx_code code;
4211      rtx reg, cond, insn;
4212      int flags;
4213 {
4214   int regno_first = -1, regno_last = -1;
4215   int not_dead = 0;
4216   int i;
4217
4218   /* Some targets place small structures in registers for
4219      return values of functions.  We have to detect this
4220      case specially here to get correct flow information.  */
4221   if (GET_CODE (reg) == PARALLEL
4222       && GET_MODE (reg) == BLKmode)
4223     {
4224       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4225         mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
4226       return;
4227     }
4228
4229   /* Modifying just one hardware register of a multi-reg value or just a
4230      byte field of a register does not mean the value from before this insn
4231      is now dead.  Of course, if it was dead after it's unused now.  */
4232
4233   switch (GET_CODE (reg))
4234     {
4235     case ZERO_EXTRACT:
4236     case SIGN_EXTRACT:
4237     case STRICT_LOW_PART:
4238       /* ??? Assumes STRICT_LOW_PART not used on multi-word registers.  */
4239       do
4240         reg = XEXP (reg, 0);
4241       while (GET_CODE (reg) == SUBREG
4242              || GET_CODE (reg) == ZERO_EXTRACT
4243              || GET_CODE (reg) == SIGN_EXTRACT
4244              || GET_CODE (reg) == STRICT_LOW_PART);
4245       if (GET_CODE (reg) == MEM)
4246         break;
4247       not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
4248       /* FALLTHRU */
4249
4250     case REG:
4251       regno_last = regno_first = REGNO (reg);
4252       if (regno_first < FIRST_PSEUDO_REGISTER)
4253         regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
4254       break;
4255
4256     case SUBREG:
4257       if (GET_CODE (SUBREG_REG (reg)) == REG)
4258         {
4259           enum machine_mode outer_mode = GET_MODE (reg);
4260           enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
4261
4262           /* Identify the range of registers affected.  This is moderately
4263              tricky for hard registers.  See alter_subreg.  */
4264
4265           regno_last = regno_first = REGNO (SUBREG_REG (reg));
4266           if (regno_first < FIRST_PSEUDO_REGISTER)
4267             {
4268 #ifdef ALTER_HARD_SUBREG
4269               regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
4270                                                inner_mode, regno_first);
4271 #else
4272               regno_first += SUBREG_WORD (reg);
4273 #endif
4274               regno_last = (regno_first
4275                             + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
4276
4277               /* Since we've just adjusted the register number ranges, make
4278                  sure REG matches.  Otherwise some_was_live will be clear
4279                  when it shouldn't have been, and we'll create incorrect
4280                  REG_UNUSED notes.  */
4281               reg = gen_rtx_REG (outer_mode, regno_first);
4282             }
4283           else
4284             {
4285               /* If the number of words in the subreg is less than the number
4286                  of words in the full register, we have a well-defined partial
4287                  set.  Otherwise the high bits are undefined.
4288
4289                  This is only really applicable to pseudos, since we just took
4290                  care of multi-word hard registers.  */
4291               if (((GET_MODE_SIZE (outer_mode)
4292                     + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
4293                   < ((GET_MODE_SIZE (inner_mode)
4294                       + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
4295                 not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
4296
4297               reg = SUBREG_REG (reg);
4298             }
4299         }
4300       else
4301         reg = SUBREG_REG (reg);
4302       break;
4303
4304     default:
4305       break;
4306     }
4307
4308   /* If this set is a MEM, then it kills any aliased writes.
4309      If this set is a REG, then it kills any MEMs which use the reg.  */
4310   if (flags & PROP_SCAN_DEAD_CODE)
4311     {
4312       if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
4313         {
4314           rtx temp = pbi->mem_set_list;
4315           rtx prev = NULL_RTX;
4316           rtx next;
4317
4318           while (temp)
4319             {
4320               next = XEXP (temp, 1);
4321               if ((GET_CODE (reg) == MEM
4322                    && output_dependence (XEXP (temp, 0), reg))
4323                   || (GET_CODE (reg) == REG
4324                       && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
4325                 {
4326                   /* Splice this entry out of the list.  */
4327                   if (prev)
4328                     XEXP (prev, 1) = next;
4329                   else
4330                     pbi->mem_set_list = next;
4331                   free_EXPR_LIST_node (temp);
4332                 }
4333               else
4334                 prev = temp;
4335               temp = next;
4336             }
4337         }
4338
4339       /* If the memory reference had embedded side effects (autoincrement
4340          address modes.  Then we may need to kill some entries on the
4341          memory set list.  */
4342       if (insn && GET_CODE (reg) == MEM)
4343         invalidate_mems_from_autoinc (pbi, insn);
4344
4345       if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
4346           /* ??? With more effort we could track conditional memory life.  */
4347           && ! cond
4348           /* We do not know the size of a BLKmode store, so we do not track
4349              them for redundant store elimination.  */
4350           && GET_MODE (reg) != BLKmode
4351           /* There are no REG_INC notes for SP, so we can't assume we'll see
4352              everything that invalidates it.  To be safe, don't eliminate any
4353              stores though SP; none of them should be redundant anyway.  */
4354           && ! reg_mentioned_p (stack_pointer_rtx, reg))
4355         pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
4356     }
4357
4358   if (GET_CODE (reg) == REG
4359       && ! (regno_first == FRAME_POINTER_REGNUM
4360             && (! reload_completed || frame_pointer_needed))
4361 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4362       && ! (regno_first == HARD_FRAME_POINTER_REGNUM
4363             && (! reload_completed || frame_pointer_needed))
4364 #endif
4365 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4366       && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
4367 #endif
4368       )
4369     {
4370       int some_was_live = 0, some_was_dead = 0;
4371
4372       for (i = regno_first; i <= regno_last; ++i)
4373         {
4374           int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
4375           if (pbi->local_set)
4376             SET_REGNO_REG_SET (pbi->local_set, i);
4377           if (code != CLOBBER)
4378             SET_REGNO_REG_SET (pbi->new_set, i);
4379
4380           some_was_live |= needed_regno;
4381           some_was_dead |= ! needed_regno;
4382         }
4383
4384 #ifdef HAVE_conditional_execution
4385       /* Consider conditional death in deciding that the register needs
4386          a death note.  */
4387       if (some_was_live && ! not_dead
4388           /* The stack pointer is never dead.  Well, not strictly true,
4389              but it's very difficult to tell from here.  Hopefully
4390              combine_stack_adjustments will fix up the most egregious
4391              errors.  */
4392           && regno_first != STACK_POINTER_REGNUM)
4393         {
4394           for (i = regno_first; i <= regno_last; ++i)
4395             if (! mark_regno_cond_dead (pbi, i, cond))
4396               not_dead = 1;
4397         }
4398 #endif
4399
4400       /* Additional data to record if this is the final pass.  */
4401       if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
4402                    | PROP_DEATH_NOTES | PROP_AUTOINC))
4403         {
4404           register rtx y;
4405           register int blocknum = pbi->bb->index;
4406
4407           y = NULL_RTX;
4408           if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4409             {
4410               y = pbi->reg_next_use[regno_first];
4411
4412               /* The next use is no longer next, since a store intervenes.  */
4413               for (i = regno_first; i <= regno_last; ++i)
4414                 pbi->reg_next_use[i] = 0;
4415             }
4416
4417           if (flags & PROP_REG_INFO)
4418             {
4419               for (i = regno_first; i <= regno_last; ++i)
4420                 {
4421                   /* Count (weighted) references, stores, etc.  This counts a
4422                      register twice if it is modified, but that is correct.  */
4423                   REG_N_SETS (i) += 1;
4424                   REG_N_REFS (i) += (optimize_size ? 1
4425                                      : pbi->bb->loop_depth + 1);
4426
4427                   /* The insns where a reg is live are normally counted
4428                      elsewhere, but we want the count to include the insn
4429                      where the reg is set, and the normal counting mechanism
4430                      would not count it.  */
4431                   REG_LIVE_LENGTH (i) += 1;
4432                 }
4433
4434               /* If this is a hard reg, record this function uses the reg.  */
4435               if (regno_first < FIRST_PSEUDO_REGISTER)
4436                 {
4437                   for (i = regno_first; i <= regno_last; i++)
4438                     regs_ever_live[i] = 1;
4439                 }
4440               else
4441                 {
4442                   /* Keep track of which basic blocks each reg appears in.  */
4443                   if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
4444                     REG_BASIC_BLOCK (regno_first) = blocknum;
4445                   else if (REG_BASIC_BLOCK (regno_first) != blocknum)
4446                     REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
4447                 }
4448             }
4449
4450           if (! some_was_dead)
4451             {
4452               if (flags & PROP_LOG_LINKS)
4453                 {
4454                   /* Make a logical link from the next following insn
4455                      that uses this register, back to this insn.
4456                      The following insns have already been processed.
4457
4458                      We don't build a LOG_LINK for hard registers containing
4459                      in ASM_OPERANDs.  If these registers get replaced,
4460                      we might wind up changing the semantics of the insn,
4461                      even if reload can make what appear to be valid
4462                      assignments later.  */
4463                   if (y && (BLOCK_NUM (y) == blocknum)
4464                       && (regno_first >= FIRST_PSEUDO_REGISTER
4465                           || asm_noperands (PATTERN (y)) < 0))
4466                     LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
4467                 }
4468             }
4469           else if (not_dead)
4470             ;
4471           else if (! some_was_live)
4472             {
4473               if (flags & PROP_REG_INFO)
4474                 REG_N_DEATHS (regno_first) += 1;
4475
4476               if (flags & PROP_DEATH_NOTES)
4477                 {
4478                   /* Note that dead stores have already been deleted
4479                      when possible.  If we get here, we have found a
4480                      dead store that cannot be eliminated (because the
4481                      same insn does something useful).  Indicate this
4482                      by marking the reg being set as dying here.  */
4483                   REG_NOTES (insn)
4484                     = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4485                 }
4486             }
4487           else
4488             {
4489               if (flags & PROP_DEATH_NOTES)
4490                 {
4491                   /* This is a case where we have a multi-word hard register
4492                      and some, but not all, of the words of the register are
4493                      needed in subsequent insns.  Write REG_UNUSED notes
4494                      for those parts that were not needed.  This case should
4495                      be rare.  */
4496
4497                   for (i = regno_first; i <= regno_last; ++i)
4498                     if (! REGNO_REG_SET_P (pbi->reg_live, i))
4499                       REG_NOTES (insn)
4500                         = alloc_EXPR_LIST (REG_UNUSED,
4501                                            gen_rtx_REG (reg_raw_mode[i], i),
4502                                            REG_NOTES (insn));
4503                 }
4504             }
4505         }
4506
4507       /* Mark the register as being dead.  */
4508       if (some_was_live
4509           && ! not_dead
4510           /* The stack pointer is never dead.  Well, not strictly true,
4511              but it's very difficult to tell from here.  Hopefully
4512              combine_stack_adjustments will fix up the most egregious
4513              errors.  */
4514           && regno_first != STACK_POINTER_REGNUM)
4515         {
4516           for (i = regno_first; i <= regno_last; ++i)
4517             CLEAR_REGNO_REG_SET (pbi->reg_live, i);
4518         }
4519     }
4520   else if (GET_CODE (reg) == REG)
4521     {
4522       if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4523         pbi->reg_next_use[regno_first] = 0;
4524     }
4525
4526   /* If this is the last pass and this is a SCRATCH, show it will be dying
4527      here and count it.  */
4528   else if (GET_CODE (reg) == SCRATCH)
4529     {
4530       if (flags & PROP_DEATH_NOTES)
4531         REG_NOTES (insn)
4532           = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4533     }
4534 }
4535 \f
4536 #ifdef HAVE_conditional_execution
4537 /* Mark REGNO conditionally dead.  Return true if the register is
4538    now unconditionally dead.  */
4539
4540 static int
4541 mark_regno_cond_dead (pbi, regno, cond)
4542      struct propagate_block_info *pbi;
4543      int regno;
4544      rtx cond;
4545 {
4546   /* If this is a store to a predicate register, the value of the
4547      predicate is changing, we don't know that the predicate as seen
4548      before is the same as that seen after.  Flush all dependant
4549      conditions from reg_cond_dead.  This will make all such
4550      conditionally live registers unconditionally live.  */
4551   if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
4552     flush_reg_cond_reg (pbi, regno);
4553
4554   /* If this is an unconditional store, remove any conditional
4555      life that may have existed.  */
4556   if (cond == NULL_RTX)
4557     splay_tree_remove (pbi->reg_cond_dead, regno);
4558   else
4559     {
4560       splay_tree_node node;
4561       struct reg_cond_life_info *rcli;
4562       rtx ncond;
4563
4564       /* Otherwise this is a conditional set.  Record that fact.
4565          It may have been conditionally used, or there may be a
4566          subsequent set with a complimentary condition.  */
4567
4568       node = splay_tree_lookup (pbi->reg_cond_dead, regno);
4569       if (node == NULL)
4570         {
4571           /* The register was unconditionally live previously.
4572              Record the current condition as the condition under
4573              which it is dead.  */
4574           rcli = (struct reg_cond_life_info *)
4575             xmalloc (sizeof (*rcli));
4576           rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
4577           splay_tree_insert (pbi->reg_cond_dead, regno,
4578                              (splay_tree_value) rcli);
4579
4580           SET_REGNO_REG_SET (pbi->reg_cond_reg,
4581                              REGNO (XEXP (cond, 0)));
4582
4583           /* Not unconditionaly dead.  */
4584           return 0;
4585         }
4586       else
4587         {
4588           /* The register was conditionally live previously.
4589              Add the new condition to the old.  */
4590           rcli = (struct reg_cond_life_info *) node->value;
4591           ncond = rcli->condition;
4592           ncond = ior_reg_cond (ncond, cond);
4593
4594           /* If the register is now unconditionally dead,
4595              remove the entry in the splay_tree.  */
4596           if (ncond == const1_rtx)
4597             splay_tree_remove (pbi->reg_cond_dead, regno);
4598           else
4599             {
4600               rcli->condition = ncond;
4601
4602               SET_REGNO_REG_SET (pbi->reg_cond_reg,
4603                                  REGNO (XEXP (cond, 0)));
4604
4605               /* Not unconditionaly dead.  */
4606               return 0;
4607             }
4608         }
4609     }
4610
4611   return 1;
4612 }
4613
4614 /* Called from splay_tree_delete for pbi->reg_cond_life.  */
4615
4616 static void
4617 free_reg_cond_life_info (value)
4618      splay_tree_value value;
4619 {
4620   struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
4621   free_EXPR_LIST_list (&rcli->condition);
4622   free (rcli);
4623 }
4624
4625 /* Helper function for flush_reg_cond_reg.  */
4626
4627 static int
4628 flush_reg_cond_reg_1 (node, data)
4629      splay_tree_node node;
4630      void *data;
4631 {
4632   struct reg_cond_life_info *rcli;
4633   int *xdata = (int *) data;
4634   unsigned int regno = xdata[0];
4635   rtx c, *prev;
4636
4637   /* Don't need to search if last flushed value was farther on in
4638      the in-order traversal.  */
4639   if (xdata[1] >= (int) node->key)
4640     return 0;
4641
4642   /* Splice out portions of the expression that refer to regno.  */
4643   rcli = (struct reg_cond_life_info *) node->value;
4644   c = *(prev = &rcli->condition);
4645   while (c)
4646     {
4647       if (regno == REGNO (XEXP (XEXP (c, 0), 0)))
4648         {
4649           rtx next = XEXP (c, 1);
4650           free_EXPR_LIST_node (c);
4651           c = *prev = next;
4652         }
4653       else
4654         c = *(prev = &XEXP (c, 1));
4655     }
4656
4657   /* If the entire condition is now NULL, signal the node to be removed.  */
4658   if (! rcli->condition)
4659     {
4660       xdata[1] = node->key;
4661       return -1;
4662     }
4663   else
4664     return 0;
4665 }
4666
4667 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE.  */
4668
4669 static void
4670 flush_reg_cond_reg (pbi, regno)
4671      struct propagate_block_info *pbi;
4672      int regno;
4673 {
4674   int pair[2];
4675
4676   pair[0] = regno;
4677   pair[1] = -1;
4678   while (splay_tree_foreach (pbi->reg_cond_dead,
4679                              flush_reg_cond_reg_1, pair) == -1)
4680     splay_tree_remove (pbi->reg_cond_dead, pair[1]);
4681
4682   CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
4683 }
4684
4685 /* Logical arithmetic on predicate conditions.  IOR, NOT and NAND.
4686    We actually use EXPR_LIST to chain the sub-expressions together
4687    instead of IOR because it's easier to manipulate and we have
4688    the lists.c functions to reuse nodes.
4689
4690    Return a new rtl expression as appropriate.  */
4691
4692 static rtx
4693 ior_reg_cond (old, x)
4694      rtx old, x;
4695 {
4696   enum rtx_code x_code;
4697   rtx x_reg;
4698   rtx c;
4699
4700   /* We expect these conditions to be of the form (eq reg 0).  */
4701   x_code = GET_CODE (x);
4702   if (GET_RTX_CLASS (x_code) != '<'
4703       || GET_CODE (x_reg = XEXP (x, 0)) != REG
4704       || XEXP (x, 1) != const0_rtx)
4705     abort ();
4706
4707   /* Search the expression for an existing sub-expression of X_REG.  */
4708   for (c = old; c ; c = XEXP (c, 1))
4709     {
4710       rtx y = XEXP (c, 0);
4711       if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4712         {
4713           /* If we find X already present in OLD, we need do nothing.  */
4714           if (GET_CODE (y) == x_code)
4715             return old;
4716
4717           /* If we find X being a compliment of a condition in OLD,
4718              then the entire condition is true.  */
4719           if (GET_CODE (y) == reverse_condition (x_code))
4720             return const1_rtx;
4721         }
4722     }
4723
4724   /* Otherwise just add to the chain.  */
4725   return alloc_EXPR_LIST (0, x, old);
4726 }
4727
4728 static rtx
4729 not_reg_cond (x)
4730      rtx x;
4731 {
4732   enum rtx_code x_code;
4733   rtx x_reg;
4734
4735   /* We expect these conditions to be of the form (eq reg 0).  */
4736   x_code = GET_CODE (x);
4737   if (GET_RTX_CLASS (x_code) != '<'
4738       || GET_CODE (x_reg = XEXP (x, 0)) != REG
4739       || XEXP (x, 1) != const0_rtx)
4740     abort ();
4741
4742   return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4743                                              VOIDmode, x_reg, const0_rtx),
4744                           NULL_RTX);
4745 }
4746
4747 static rtx
4748 nand_reg_cond (old, x)
4749      rtx old, x;
4750 {
4751   enum rtx_code x_code;
4752   rtx x_reg;
4753   rtx c, *prev;
4754
4755   /* We expect these conditions to be of the form (eq reg 0).  */
4756   x_code = GET_CODE (x);
4757   if (GET_RTX_CLASS (x_code) != '<'
4758       || GET_CODE (x_reg = XEXP (x, 0)) != REG
4759       || XEXP (x, 1) != const0_rtx)
4760     abort ();
4761
4762   /* Search the expression for an existing sub-expression of X_REG.  */
4763
4764   for (c = *(prev = &old); c ; c = *(prev = &XEXP (c, 1)))
4765     {
4766       rtx y = XEXP (c, 0);
4767       if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4768         {
4769           /* If we find X already present in OLD, then we need to
4770              splice it out.  */
4771           if (GET_CODE (y) == x_code)
4772             {
4773               *prev = XEXP (c, 1);
4774               free_EXPR_LIST_node (c);
4775               return old ? old : const0_rtx;
4776             }
4777
4778           /* If we find X being a compliment of a condition in OLD,
4779              then we need do nothing.  */
4780           if (GET_CODE (y) == reverse_condition (x_code))
4781             return old;
4782         }
4783     }
4784
4785   /* Otherwise, by implication, the register in question is now live for
4786      the inverse of the condition X.  */
4787   return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4788                                              VOIDmode, x_reg, const0_rtx),
4789                           old);
4790 }
4791 #endif /* HAVE_conditional_execution */
4792 \f
4793 #ifdef AUTO_INC_DEC
4794
4795 /* X is a MEM found in INSN.  See if we can convert it into an auto-increment
4796    reference.  */
4797
4798 static void
4799 find_auto_inc (pbi, x, insn)
4800      struct propagate_block_info *pbi;
4801      rtx x;
4802      rtx insn;
4803 {
4804   rtx addr = XEXP (x, 0);
4805   HOST_WIDE_INT offset = 0;
4806   rtx set;
4807
4808   /* Here we detect use of an index register which might be good for
4809      postincrement, postdecrement, preincrement, or predecrement.  */
4810
4811   if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
4812     offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
4813
4814   if (GET_CODE (addr) == REG)
4815     {
4816       register rtx y;
4817       register int size = GET_MODE_SIZE (GET_MODE (x));
4818       rtx use;
4819       rtx incr;
4820       int regno = REGNO (addr);
4821
4822       /* Is the next use an increment that might make auto-increment? */
4823       if ((incr = pbi->reg_next_use[regno]) != 0
4824           && (set = single_set (incr)) != 0
4825           && GET_CODE (set) == SET
4826           && BLOCK_NUM (incr) == BLOCK_NUM (insn)
4827           /* Can't add side effects to jumps; if reg is spilled and
4828              reloaded, there's no way to store back the altered value.  */
4829           && GET_CODE (insn) != JUMP_INSN
4830           && (y = SET_SRC (set), GET_CODE (y) == PLUS)
4831           && XEXP (y, 0) == addr
4832           && GET_CODE (XEXP (y, 1)) == CONST_INT
4833           && ((HAVE_POST_INCREMENT
4834                && (INTVAL (XEXP (y, 1)) == size && offset == 0))
4835               || (HAVE_POST_DECREMENT
4836                   && (INTVAL (XEXP (y, 1)) == - size && offset == 0))
4837               || (HAVE_PRE_INCREMENT
4838                   && (INTVAL (XEXP (y, 1)) == size && offset == size))
4839               || (HAVE_PRE_DECREMENT
4840                   && (INTVAL (XEXP (y, 1)) == - size && offset == - size)))
4841           /* Make sure this reg appears only once in this insn.  */
4842           && (use = find_use_as_address (PATTERN (insn), addr, offset),
4843               use != 0 && use != (rtx) 1))
4844         {
4845           rtx q = SET_DEST (set);
4846           enum rtx_code inc_code = (INTVAL (XEXP (y, 1)) == size
4847                                     ? (offset ? PRE_INC : POST_INC)
4848                                     : (offset ? PRE_DEC : POST_DEC));
4849
4850           if (dead_or_set_p (incr, addr)
4851               /* Mustn't autoinc an eliminable register.  */
4852               && (regno >= FIRST_PSEUDO_REGISTER
4853                   || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
4854             {
4855               /* This is the simple case.  Try to make the auto-inc.  If
4856                  we can't, we are done.  Otherwise, we will do any
4857                  needed updates below.  */
4858               if (! validate_change (insn, &XEXP (x, 0),
4859                                      gen_rtx_fmt_e (inc_code, Pmode, addr),
4860                                      0))
4861                 return;
4862             }
4863           else if (GET_CODE (q) == REG
4864                    /* PREV_INSN used here to check the semi-open interval
4865                       [insn,incr).  */
4866                    && ! reg_used_between_p (q,  PREV_INSN (insn), incr)
4867                    /* We must also check for sets of q as q may be
4868                       a call clobbered hard register and there may
4869                       be a call between PREV_INSN (insn) and incr.  */
4870                    && ! reg_set_between_p (q,  PREV_INSN (insn), incr))
4871             {
4872               /* We have *p followed sometime later by q = p+size.
4873                  Both p and q must be live afterward,
4874                  and q is not used between INSN and its assignment.
4875                  Change it to q = p, ...*q..., q = q+size.
4876                  Then fall into the usual case.  */
4877               rtx insns, temp;
4878
4879               start_sequence ();
4880               emit_move_insn (q, addr);
4881               insns = get_insns ();
4882               end_sequence ();
4883
4884               if (basic_block_for_insn)
4885                 for (temp = insns; temp; temp = NEXT_INSN (temp))
4886                   set_block_for_insn (temp, pbi->bb);
4887
4888               /* If we can't make the auto-inc, or can't make the
4889                  replacement into Y, exit.  There's no point in making
4890                  the change below if we can't do the auto-inc and doing
4891                  so is not correct in the pre-inc case.  */
4892
4893               validate_change (insn, &XEXP (x, 0),
4894                                gen_rtx_fmt_e (inc_code, Pmode, q),
4895                                1);
4896               validate_change (incr, &XEXP (y, 0), q, 1);
4897               if (! apply_change_group ())
4898                 return;
4899
4900               /* We now know we'll be doing this change, so emit the
4901                  new insn(s) and do the updates.  */
4902               emit_insns_before (insns, insn);
4903
4904               if (pbi->bb->head == insn)
4905                 pbi->bb->head = insns;
4906
4907               /* INCR will become a NOTE and INSN won't contain a
4908                  use of ADDR.  If a use of ADDR was just placed in
4909                  the insn before INSN, make that the next use.
4910                  Otherwise, invalidate it.  */
4911               if (GET_CODE (PREV_INSN (insn)) == INSN
4912                   && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
4913                   && SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
4914                 pbi->reg_next_use[regno] = PREV_INSN (insn);
4915               else
4916                 pbi->reg_next_use[regno] = 0;
4917
4918               addr = q;
4919               regno = REGNO (q);
4920
4921               /* REGNO is now used in INCR which is below INSN, but it
4922                  previously wasn't live here.  If we don't mark it as
4923                  live, we'll put a REG_DEAD note for it on this insn,
4924                  which is incorrect.  */
4925               SET_REGNO_REG_SET (pbi->reg_live, regno);
4926
4927               /* If there are any calls between INSN and INCR, show
4928                  that REGNO now crosses them.  */
4929               for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
4930                 if (GET_CODE (temp) == CALL_INSN)
4931                   REG_N_CALLS_CROSSED (regno)++;
4932             }
4933           else
4934             return;
4935
4936           /* If we haven't returned, it means we were able to make the
4937              auto-inc, so update the status.  First, record that this insn
4938              has an implicit side effect.  */
4939
4940           REG_NOTES (insn)
4941             = alloc_EXPR_LIST (REG_INC, addr, REG_NOTES (insn));
4942
4943           /* Modify the old increment-insn to simply copy
4944              the already-incremented value of our register.  */
4945           if (! validate_change (incr, &SET_SRC (set), addr, 0))
4946             abort ();
4947
4948           /* If that makes it a no-op (copying the register into itself) delete
4949              it so it won't appear to be a "use" and a "set" of this
4950              register.  */
4951           if (SET_DEST (set) == addr)
4952             {
4953               /* If the original source was dead, it's dead now.  */
4954               rtx note = find_reg_note (incr, REG_DEAD, NULL_RTX);
4955               if (note && XEXP (note, 0) != addr)
4956                 CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
4957
4958               PUT_CODE (incr, NOTE);
4959               NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
4960               NOTE_SOURCE_FILE (incr) = 0;
4961             }
4962
4963           if (regno >= FIRST_PSEUDO_REGISTER)
4964             {
4965               /* Count an extra reference to the reg.  When a reg is
4966                  incremented, spilling it is worse, so we want to make
4967                  that less likely.  */
4968               REG_N_REFS (regno) += (optimize_size ? 1
4969                                      : pbi->bb->loop_depth + 1);
4970
4971               /* Count the increment as a setting of the register,
4972                  even though it isn't a SET in rtl.  */
4973               REG_N_SETS (regno)++;
4974             }
4975         }
4976     }
4977 }
4978 #endif /* AUTO_INC_DEC */
4979 \f
4980 static void
4981 mark_used_reg (pbi, reg, cond, insn)
4982      struct propagate_block_info *pbi;
4983      rtx reg;
4984      rtx cond ATTRIBUTE_UNUSED;
4985      rtx insn;
4986 {
4987   int regno = REGNO (reg);
4988   int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
4989   int some_was_dead = ! some_was_live;
4990   int some_not_set;
4991   int n;
4992
4993   /* A hard reg in a wide mode may really be multiple registers.
4994      If so, mark all of them just like the first.  */
4995   if (regno < FIRST_PSEUDO_REGISTER)
4996     {
4997       n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
4998       while (--n > 0)
4999         {
5000           int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
5001           some_was_live |= needed_regno;
5002           some_was_dead |= ! needed_regno;
5003         }
5004     }
5005
5006   if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
5007     {
5008       /* Record where each reg is used, so when the reg is set we know
5009          the next insn that uses it.  */
5010       pbi->reg_next_use[regno] = insn;
5011     }
5012
5013   if (pbi->flags & PROP_REG_INFO)
5014     {
5015       if (regno < FIRST_PSEUDO_REGISTER)
5016         {
5017           /* If this is a register we are going to try to eliminate,
5018              don't mark it live here.  If we are successful in
5019              eliminating it, it need not be live unless it is used for
5020              pseudos, in which case it will have been set live when it
5021              was allocated to the pseudos.  If the register will not
5022              be eliminated, reload will set it live at that point.
5023
5024              Otherwise, record that this function uses this register.  */
5025           /* ??? The PPC backend tries to "eliminate" on the pic
5026              register to itself.  This should be fixed.  In the mean
5027              time, hack around it.  */
5028
5029           if (! (TEST_HARD_REG_BIT (elim_reg_set, regno)
5030                  && (regno == FRAME_POINTER_REGNUM
5031                      || regno == ARG_POINTER_REGNUM)))
5032             {
5033               int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5034               do
5035                 regs_ever_live[regno + --n] = 1;
5036               while (n > 0);
5037             }
5038         }
5039       else
5040         {
5041           /* Keep track of which basic block each reg appears in.  */
5042
5043           register int blocknum = pbi->bb->index;
5044           if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
5045             REG_BASIC_BLOCK (regno) = blocknum;
5046           else if (REG_BASIC_BLOCK (regno) != blocknum)
5047             REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
5048
5049           /* Count (weighted) number of uses of each reg.  */
5050           REG_N_REFS (regno) += (optimize_size ? 1
5051                                  : pbi->bb->loop_depth + 1);
5052         }
5053     }
5054
5055   /* Find out if any of the register was set this insn.  */
5056   some_not_set = ! REGNO_REG_SET_P (pbi->new_set, regno);
5057   if (regno < FIRST_PSEUDO_REGISTER)
5058     {
5059       n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5060       while (--n > 0)
5061         some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, regno + n);
5062     }
5063
5064   /* Record and count the insns in which a reg dies.  If it is used in
5065      this insn and was dead below the insn then it dies in this insn.
5066      If it was set in this insn, we do not make a REG_DEAD note;
5067      likewise if we already made such a note.  */
5068   if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
5069       && some_was_dead
5070       && some_not_set)
5071     {
5072       /* Check for the case where the register dying partially
5073          overlaps the register set by this insn.  */
5074       if (regno < FIRST_PSEUDO_REGISTER
5075           && HARD_REGNO_NREGS (regno, GET_MODE (reg)) > 1)
5076         {
5077           n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5078           while (--n >= 0)
5079             some_was_live |= REGNO_REG_SET_P (pbi->new_set, regno + n);
5080         }
5081
5082       /* If none of the words in X is needed, make a REG_DEAD note.
5083          Otherwise, we must make partial REG_DEAD notes.  */
5084       if (! some_was_live)
5085         {
5086           if ((pbi->flags & PROP_DEATH_NOTES)
5087               && ! find_regno_note (insn, REG_DEAD, regno))
5088             REG_NOTES (insn)
5089               = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
5090
5091           if (pbi->flags & PROP_REG_INFO)
5092             REG_N_DEATHS (regno)++;
5093         }
5094       else
5095         {
5096           /* Don't make a REG_DEAD note for a part of a register
5097              that is set in the insn.  */
5098
5099           n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
5100           for (; n >= regno; n--)
5101             if (! REGNO_REG_SET_P (pbi->reg_live, n)
5102                 && ! dead_or_set_regno_p (insn, n))
5103               REG_NOTES (insn)
5104                 = alloc_EXPR_LIST (REG_DEAD,
5105                                    gen_rtx_REG (reg_raw_mode[n], n),
5106                                    REG_NOTES (insn));
5107         }
5108     }
5109
5110   SET_REGNO_REG_SET (pbi->reg_live, regno);
5111   if (regno < FIRST_PSEUDO_REGISTER)
5112     {
5113       n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5114       while (--n > 0)
5115         SET_REGNO_REG_SET (pbi->reg_live, regno + n);
5116     }
5117
5118 #ifdef HAVE_conditional_execution
5119   /* If this is a conditional use, record that fact.  If it is later
5120      conditionally set, we'll know to kill the register.  */
5121   if (cond != NULL_RTX)
5122     {
5123       splay_tree_node node;
5124       struct reg_cond_life_info *rcli;
5125       rtx ncond;
5126
5127       if (some_was_live)
5128         {
5129           node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5130           if (node == NULL)
5131             {
5132               /* The register was unconditionally live previously.
5133                  No need to do anything.  */
5134             }
5135           else
5136             {
5137               /* The register was conditionally live previously.
5138                  Subtract the new life cond from the old death cond.  */
5139               rcli = (struct reg_cond_life_info *) node->value;
5140               ncond = rcli->condition;
5141               ncond = nand_reg_cond (ncond, cond);
5142
5143               /* If the register is now unconditionally live, remove the
5144                  entry in the splay_tree.  */
5145               if (ncond == const0_rtx)
5146                 {
5147                   rcli->condition = NULL_RTX;
5148                   splay_tree_remove (pbi->reg_cond_dead, regno);
5149                 }
5150               else
5151                 rcli->condition = ncond;
5152             }
5153         }
5154       else
5155         {
5156           /* The register was not previously live at all.  Record
5157              the condition under which it is still dead.  */
5158           rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
5159           rcli->condition = not_reg_cond (cond);
5160           splay_tree_insert (pbi->reg_cond_dead, regno,
5161                              (splay_tree_value) rcli);
5162         }
5163     }
5164   else if (some_was_live)
5165     {
5166       splay_tree_node node;
5167       struct reg_cond_life_info *rcli;
5168
5169       node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5170       if (node != NULL)
5171         {
5172           /* The register was conditionally live previously, but is now
5173              unconditionally so.  Remove it from the conditionally dead
5174              list, so that a conditional set won't cause us to think
5175              it dead.  */
5176           rcli = (struct reg_cond_life_info *) node->value;
5177           rcli->condition = NULL_RTX;
5178           splay_tree_remove (pbi->reg_cond_dead, regno);
5179         }
5180     }
5181
5182 #endif
5183 }
5184
5185 /* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
5186    This is done assuming the registers needed from X are those that
5187    have 1-bits in PBI->REG_LIVE.
5188
5189    INSN is the containing instruction.  If INSN is dead, this function
5190    is not called.  */
5191
5192 static void
5193 mark_used_regs (pbi, x, cond, insn)
5194      struct propagate_block_info *pbi;
5195      rtx x, cond, insn;
5196 {
5197   register RTX_CODE code;
5198   register int regno;
5199   int flags = pbi->flags;
5200
5201  retry:
5202   code = GET_CODE (x);
5203   switch (code)
5204     {
5205     case LABEL_REF:
5206     case SYMBOL_REF:
5207     case CONST_INT:
5208     case CONST:
5209     case CONST_DOUBLE:
5210     case PC:
5211     case ADDR_VEC:
5212     case ADDR_DIFF_VEC:
5213       return;
5214
5215 #ifdef HAVE_cc0
5216     case CC0:
5217       pbi->cc0_live = 1;
5218       return;
5219 #endif
5220
5221     case CLOBBER:
5222       /* If we are clobbering a MEM, mark any registers inside the address
5223          as being used.  */
5224       if (GET_CODE (XEXP (x, 0)) == MEM)
5225         mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
5226       return;
5227
5228     case MEM:
5229       /* Don't bother watching stores to mems if this is not the
5230          final pass.  We'll not be deleting dead stores this round.  */
5231       if (flags & PROP_SCAN_DEAD_CODE)
5232         {
5233           /* Invalidate the data for the last MEM stored, but only if MEM is
5234              something that can be stored into.  */
5235           if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
5236               && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
5237             ; /* needn't clear the memory set list */
5238           else
5239             {
5240               rtx temp = pbi->mem_set_list;
5241               rtx prev = NULL_RTX;
5242               rtx next;
5243
5244               while (temp)
5245                 {
5246                   next = XEXP (temp, 1);
5247                   if (anti_dependence (XEXP (temp, 0), x))
5248                     {
5249                       /* Splice temp out of the list.  */
5250                       if (prev)
5251                         XEXP (prev, 1) = next;
5252                       else
5253                         pbi->mem_set_list = next;
5254                       free_EXPR_LIST_node (temp);
5255                     }
5256                   else
5257                     prev = temp;
5258                   temp = next;
5259                 }
5260             }
5261
5262           /* If the memory reference had embedded side effects (autoincrement
5263              address modes.  Then we may need to kill some entries on the
5264              memory set list.  */
5265           if (insn)
5266             invalidate_mems_from_autoinc (pbi, insn);
5267         }
5268
5269 #ifdef AUTO_INC_DEC
5270       if (flags & PROP_AUTOINC)
5271         find_auto_inc (pbi, x, insn);
5272 #endif
5273       break;
5274
5275     case SUBREG:
5276 #ifdef CLASS_CANNOT_CHANGE_MODE
5277       if (GET_CODE (SUBREG_REG (x)) == REG
5278           && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
5279           && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (x),
5280                                          GET_MODE (SUBREG_REG (x))))
5281         REG_CHANGES_MODE (REGNO (SUBREG_REG (x))) = 1;
5282 #endif
5283
5284       /* While we're here, optimize this case.  */
5285       x = SUBREG_REG (x);
5286       if (GET_CODE (x) != REG)
5287         goto retry;
5288       /* FALLTHRU */
5289
5290     case REG:
5291       /* See a register other than being set => mark it as needed.  */
5292       mark_used_reg (pbi, x, cond, insn);
5293       return;
5294
5295     case SET:
5296       {
5297         register rtx testreg = SET_DEST (x);
5298         int mark_dest = 0;
5299
5300         /* If storing into MEM, don't show it as being used.  But do
5301            show the address as being used.  */
5302         if (GET_CODE (testreg) == MEM)
5303           {
5304 #ifdef AUTO_INC_DEC
5305             if (flags & PROP_AUTOINC)
5306               find_auto_inc (pbi, testreg, insn);
5307 #endif
5308             mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
5309             mark_used_regs (pbi, SET_SRC (x), cond, insn);
5310             return;
5311           }
5312
5313         /* Storing in STRICT_LOW_PART is like storing in a reg
5314            in that this SET might be dead, so ignore it in TESTREG.
5315            but in some other ways it is like using the reg.
5316
5317            Storing in a SUBREG or a bit field is like storing the entire
5318            register in that if the register's value is not used
5319            then this SET is not needed.  */
5320         while (GET_CODE (testreg) == STRICT_LOW_PART
5321                || GET_CODE (testreg) == ZERO_EXTRACT
5322                || GET_CODE (testreg) == SIGN_EXTRACT
5323                || GET_CODE (testreg) == SUBREG)
5324           {
5325 #ifdef CLASS_CANNOT_CHANGE_MODE
5326             if (GET_CODE (testreg) == SUBREG
5327                 && GET_CODE (SUBREG_REG (testreg)) == REG
5328                 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
5329                 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (SUBREG_REG (testreg)),
5330                                                GET_MODE (testreg)))
5331               REG_CHANGES_MODE (REGNO (SUBREG_REG (testreg))) = 1;
5332 #endif
5333
5334             /* Modifying a single register in an alternate mode
5335                does not use any of the old value.  But these other
5336                ways of storing in a register do use the old value.  */
5337             if (GET_CODE (testreg) == SUBREG
5338                 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
5339               ;
5340             else
5341               mark_dest = 1;
5342
5343             testreg = XEXP (testreg, 0);
5344           }
5345
5346         /* If this is a store into a register, recursively scan the
5347            value being stored.  */
5348
5349         if ((GET_CODE (testreg) == PARALLEL
5350              && GET_MODE (testreg) == BLKmode)
5351             || (GET_CODE (testreg) == REG
5352                 && (regno = REGNO (testreg),
5353                     ! (regno == FRAME_POINTER_REGNUM
5354                        && (! reload_completed || frame_pointer_needed)))
5355 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
5356                 && ! (regno == HARD_FRAME_POINTER_REGNUM
5357                       && (! reload_completed || frame_pointer_needed))
5358 #endif
5359 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
5360                 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
5361 #endif
5362                 ))
5363           {
5364             if (mark_dest)
5365               mark_used_regs (pbi, SET_DEST (x), cond, insn);
5366             mark_used_regs (pbi, SET_SRC (x), cond, insn);
5367             return;
5368           }
5369       }
5370       break;
5371
5372     case ASM_OPERANDS:
5373     case UNSPEC_VOLATILE:
5374     case TRAP_IF:
5375     case ASM_INPUT:
5376       {
5377         /* Traditional and volatile asm instructions must be considered to use
5378            and clobber all hard registers, all pseudo-registers and all of
5379            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
5380
5381            Consider for instance a volatile asm that changes the fpu rounding
5382            mode.  An insn should not be moved across this even if it only uses
5383            pseudo-regs because it might give an incorrectly rounded result.
5384
5385            ?!? Unfortunately, marking all hard registers as live causes massive
5386            problems for the register allocator and marking all pseudos as live
5387            creates mountains of uninitialized variable warnings.
5388
5389            So for now, just clear the memory set list and mark any regs
5390            we can find in ASM_OPERANDS as used.  */
5391         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
5392           free_EXPR_LIST_list (&pbi->mem_set_list);
5393
5394         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
5395            We can not just fall through here since then we would be confused
5396            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
5397            traditional asms unlike their normal usage.  */
5398         if (code == ASM_OPERANDS)
5399           {
5400             int j;
5401
5402             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
5403               mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
5404           }
5405         break;
5406       }
5407
5408     case COND_EXEC:
5409       if (cond != NULL_RTX)
5410         abort ();
5411
5412       mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
5413
5414       cond = COND_EXEC_TEST (x);
5415       x = COND_EXEC_CODE (x);
5416       goto retry;
5417
5418     case PHI:
5419       /* We _do_not_ want to scan operands of phi nodes.  Operands of
5420          a phi function are evaluated only when control reaches this
5421          block along a particular edge.  Therefore, regs that appear
5422          as arguments to phi should not be added to the global live at
5423          start.  */
5424       return;
5425
5426     default:
5427       break;
5428     }
5429
5430   /* Recursively scan the operands of this expression.  */
5431
5432   {
5433     register const char *fmt = GET_RTX_FORMAT (code);
5434     register int i;
5435
5436     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5437       {
5438         if (fmt[i] == 'e')
5439           {
5440             /* Tail recursive case: save a function call level.  */
5441             if (i == 0)
5442               {
5443                 x = XEXP (x, 0);
5444                 goto retry;
5445               }
5446             mark_used_regs (pbi, XEXP (x, i), cond, insn);
5447           }
5448         else if (fmt[i] == 'E')
5449           {
5450             register int j;
5451             for (j = 0; j < XVECLEN (x, i); j++)
5452               mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
5453           }
5454       }
5455   }
5456 }
5457 \f
5458 #ifdef AUTO_INC_DEC
5459
5460 static int
5461 try_pre_increment_1 (pbi, insn)
5462      struct propagate_block_info *pbi;
5463      rtx insn;
5464 {
5465   /* Find the next use of this reg.  If in same basic block,
5466      make it do pre-increment or pre-decrement if appropriate.  */
5467   rtx x = single_set (insn);
5468   HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
5469                 * INTVAL (XEXP (SET_SRC (x), 1)));
5470   int regno = REGNO (SET_DEST (x));
5471   rtx y = pbi->reg_next_use[regno];
5472   if (y != 0
5473       && BLOCK_NUM (y) == BLOCK_NUM (insn)
5474       /* Don't do this if the reg dies, or gets set in y; a standard addressing
5475          mode would be better.  */
5476       && ! dead_or_set_p (y, SET_DEST (x))
5477       && try_pre_increment (y, SET_DEST (x), amount))
5478     {
5479       /* We have found a suitable auto-increment
5480          and already changed insn Y to do it.
5481          So flush this increment-instruction.  */
5482       PUT_CODE (insn, NOTE);
5483       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5484       NOTE_SOURCE_FILE (insn) = 0;
5485       /* Count a reference to this reg for the increment
5486          insn we are deleting.  When a reg is incremented.
5487          spilling it is worse, so we want to make that
5488          less likely.  */
5489       if (regno >= FIRST_PSEUDO_REGISTER)
5490         {
5491           REG_N_REFS (regno) += (optimize_size ? 1
5492                                  : pbi->bb->loop_depth + 1);
5493           REG_N_SETS (regno)++;
5494         }
5495       return 1;
5496     }
5497   return 0;
5498 }
5499
5500 /* Try to change INSN so that it does pre-increment or pre-decrement
5501    addressing on register REG in order to add AMOUNT to REG.
5502    AMOUNT is negative for pre-decrement.
5503    Returns 1 if the change could be made.
5504    This checks all about the validity of the result of modifying INSN.  */
5505
5506 static int
5507 try_pre_increment (insn, reg, amount)
5508      rtx insn, reg;
5509      HOST_WIDE_INT amount;
5510 {
5511   register rtx use;
5512
5513   /* Nonzero if we can try to make a pre-increment or pre-decrement.
5514      For example, addl $4,r1; movl (r1),... can become movl +(r1),...  */
5515   int pre_ok = 0;
5516   /* Nonzero if we can try to make a post-increment or post-decrement.
5517      For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
5518      It is possible for both PRE_OK and POST_OK to be nonzero if the machine
5519      supports both pre-inc and post-inc, or both pre-dec and post-dec.  */
5520   int post_ok = 0;
5521
5522   /* Nonzero if the opportunity actually requires post-inc or post-dec.  */
5523   int do_post = 0;
5524
5525   /* From the sign of increment, see which possibilities are conceivable
5526      on this target machine.  */
5527   if (HAVE_PRE_INCREMENT && amount > 0)
5528     pre_ok = 1;
5529   if (HAVE_POST_INCREMENT && amount > 0)
5530     post_ok = 1;
5531
5532   if (HAVE_PRE_DECREMENT && amount < 0)
5533     pre_ok = 1;
5534   if (HAVE_POST_DECREMENT && amount < 0)
5535     post_ok = 1;
5536
5537   if (! (pre_ok || post_ok))
5538     return 0;
5539
5540   /* It is not safe to add a side effect to a jump insn
5541      because if the incremented register is spilled and must be reloaded
5542      there would be no way to store the incremented value back in memory.  */
5543
5544   if (GET_CODE (insn) == JUMP_INSN)
5545     return 0;
5546
5547   use = 0;
5548   if (pre_ok)
5549     use = find_use_as_address (PATTERN (insn), reg, 0);
5550   if (post_ok && (use == 0 || use == (rtx) 1))
5551     {
5552       use = find_use_as_address (PATTERN (insn), reg, -amount);
5553       do_post = 1;
5554     }
5555
5556   if (use == 0 || use == (rtx) 1)
5557     return 0;
5558
5559   if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
5560     return 0;
5561
5562   /* See if this combination of instruction and addressing mode exists.  */
5563   if (! validate_change (insn, &XEXP (use, 0),
5564                          gen_rtx_fmt_e (amount > 0
5565                                         ? (do_post ? POST_INC : PRE_INC)
5566                                         : (do_post ? POST_DEC : PRE_DEC),
5567                                         Pmode, reg), 0))
5568     return 0;
5569
5570   /* Record that this insn now has an implicit side effect on X.  */
5571   REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
5572   return 1;
5573 }
5574
5575 #endif /* AUTO_INC_DEC */
5576 \f
5577 /* Find the place in the rtx X where REG is used as a memory address.
5578    Return the MEM rtx that so uses it.
5579    If PLUSCONST is nonzero, search instead for a memory address equivalent to
5580    (plus REG (const_int PLUSCONST)).
5581
5582    If such an address does not appear, return 0.
5583    If REG appears more than once, or is used other than in such an address,
5584    return (rtx)1.  */
5585
5586 rtx
5587 find_use_as_address (x, reg, plusconst)
5588      register rtx x;
5589      rtx reg;
5590      HOST_WIDE_INT plusconst;
5591 {
5592   enum rtx_code code = GET_CODE (x);
5593   const char *fmt = GET_RTX_FORMAT (code);
5594   register int i;
5595   register rtx value = 0;
5596   register rtx tem;
5597
5598   if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
5599     return x;
5600
5601   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
5602       && XEXP (XEXP (x, 0), 0) == reg
5603       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
5604       && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
5605     return x;
5606
5607   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
5608     {
5609       /* If REG occurs inside a MEM used in a bit-field reference,
5610          that is unacceptable.  */
5611       if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
5612         return (rtx) (HOST_WIDE_INT) 1;
5613     }
5614
5615   if (x == reg)
5616     return (rtx) (HOST_WIDE_INT) 1;
5617
5618   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5619     {
5620       if (fmt[i] == 'e')
5621         {
5622           tem = find_use_as_address (XEXP (x, i), reg, plusconst);
5623           if (value == 0)
5624             value = tem;
5625           else if (tem != 0)
5626             return (rtx) (HOST_WIDE_INT) 1;
5627         }
5628       else if (fmt[i] == 'E')
5629         {
5630           register int j;
5631           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5632             {
5633               tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
5634               if (value == 0)
5635                 value = tem;
5636               else if (tem != 0)
5637                 return (rtx) (HOST_WIDE_INT) 1;
5638             }
5639         }
5640     }
5641
5642   return value;
5643 }
5644 \f
5645 /* Write information about registers and basic blocks into FILE.
5646    This is part of making a debugging dump.  */
5647
5648 void
5649 dump_regset (r, outf)
5650      regset r;
5651      FILE *outf;
5652 {
5653   int i;
5654   if (r == NULL)
5655     {
5656       fputs (" (nil)", outf);
5657       return;
5658     }
5659
5660   EXECUTE_IF_SET_IN_REG_SET (r, 0, i,
5661     {
5662       fprintf (outf, " %d", i);
5663       if (i < FIRST_PSEUDO_REGISTER)
5664         fprintf (outf, " [%s]",
5665                  reg_names[i]);
5666     });
5667 }
5668
5669 void
5670 debug_regset (r)
5671      regset r;
5672 {
5673   dump_regset (r, stderr);
5674   putc ('\n', stderr);
5675 }
5676
5677 void
5678 dump_flow_info (file)
5679      FILE *file;
5680 {
5681   register int i;
5682   static const char * const reg_class_names[] = REG_CLASS_NAMES;
5683
5684   fprintf (file, "%d registers.\n", max_regno);
5685   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
5686     if (REG_N_REFS (i))
5687       {
5688         enum reg_class class, altclass;
5689         fprintf (file, "\nRegister %d used %d times across %d insns",
5690                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
5691         if (REG_BASIC_BLOCK (i) >= 0)
5692           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
5693         if (REG_N_SETS (i))
5694           fprintf (file, "; set %d time%s", REG_N_SETS (i),
5695                    (REG_N_SETS (i) == 1) ? "" : "s");
5696         if (REG_USERVAR_P (regno_reg_rtx[i]))
5697           fprintf (file, "; user var");
5698         if (REG_N_DEATHS (i) != 1)
5699           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
5700         if (REG_N_CALLS_CROSSED (i) == 1)
5701           fprintf (file, "; crosses 1 call");
5702         else if (REG_N_CALLS_CROSSED (i))
5703           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
5704         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
5705           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
5706         class = reg_preferred_class (i);
5707         altclass = reg_alternate_class (i);
5708         if (class != GENERAL_REGS || altclass != ALL_REGS)
5709           {
5710             if (altclass == ALL_REGS || class == ALL_REGS)
5711               fprintf (file, "; pref %s", reg_class_names[(int) class]);
5712             else if (altclass == NO_REGS)
5713               fprintf (file, "; %s or none", reg_class_names[(int) class]);
5714             else
5715               fprintf (file, "; pref %s, else %s",
5716                        reg_class_names[(int) class],
5717                        reg_class_names[(int) altclass]);
5718           }
5719         if (REGNO_POINTER_FLAG (i))
5720           fprintf (file, "; pointer");
5721         fprintf (file, ".\n");
5722       }
5723
5724   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
5725   for (i = 0; i < n_basic_blocks; i++)
5726     {
5727       register basic_block bb = BASIC_BLOCK (i);
5728       register edge e;
5729
5730       fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count %d.\n",
5731                i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth, bb->count);
5732
5733       fprintf (file, "Predecessors: ");
5734       for (e = bb->pred; e ; e = e->pred_next)
5735         dump_edge_info (file, e, 0);
5736
5737       fprintf (file, "\nSuccessors: ");
5738       for (e = bb->succ; e ; e = e->succ_next)
5739         dump_edge_info (file, e, 1);
5740
5741       fprintf (file, "\nRegisters live at start:");
5742       dump_regset (bb->global_live_at_start, file);
5743
5744       fprintf (file, "\nRegisters live at end:");
5745       dump_regset (bb->global_live_at_end, file);
5746
5747       putc('\n', file);
5748     }
5749
5750   putc('\n', file);
5751 }
5752
5753 void
5754 debug_flow_info ()
5755 {
5756   dump_flow_info (stderr);
5757 }
5758
5759 static void
5760 dump_edge_info (file, e, do_succ)
5761      FILE *file;
5762      edge e;
5763      int do_succ;
5764 {
5765   basic_block side = (do_succ ? e->dest : e->src);
5766
5767   if (side == ENTRY_BLOCK_PTR)
5768     fputs (" ENTRY", file);
5769   else if (side == EXIT_BLOCK_PTR)
5770     fputs (" EXIT", file);
5771   else
5772     fprintf (file, " %d", side->index);
5773
5774   if (e->count)
5775     fprintf (file, " count:%d", e->count);
5776
5777   if (e->flags)
5778     {
5779       static const char * const bitnames[] = {
5780         "fallthru", "crit", "ab", "abcall", "eh", "fake"
5781       };
5782       int comma = 0;
5783       int i, flags = e->flags;
5784
5785       fputc (' ', file);
5786       fputc ('(', file);
5787       for (i = 0; flags; i++)
5788         if (flags & (1 << i))
5789           {
5790             flags &= ~(1 << i);
5791
5792             if (comma)
5793               fputc (',', file);
5794             if (i < (int)(sizeof (bitnames) / sizeof (*bitnames)))
5795               fputs (bitnames[i], file);
5796             else
5797               fprintf (file, "%d", i);
5798             comma = 1;
5799           }
5800       fputc (')', file);
5801     }
5802 }
5803
5804 \f
5805 /* Print out one basic block with live information at start and end.  */
5806 void
5807 dump_bb (bb, outf)
5808      basic_block bb;
5809      FILE *outf;
5810 {
5811   rtx insn;
5812   rtx last;
5813   edge e;
5814
5815   fprintf (outf, ";; Basic block %d, loop depth %d, count %d",
5816            bb->index, bb->loop_depth, bb->count);
5817   if (bb->eh_beg != -1 || bb->eh_end != -1)
5818     fprintf (outf, ", eh regions %d/%d", bb->eh_beg, bb->eh_end);
5819   putc ('\n', outf);
5820
5821   fputs (";; Predecessors: ", outf);
5822   for (e = bb->pred; e ; e = e->pred_next)
5823     dump_edge_info (outf, e, 0);
5824   putc ('\n', outf);
5825
5826   fputs (";; Registers live at start:", outf);
5827   dump_regset (bb->global_live_at_start, outf);
5828   putc ('\n', outf);
5829
5830   for (insn = bb->head, last = NEXT_INSN (bb->end);
5831        insn != last;
5832        insn = NEXT_INSN (insn))
5833     print_rtl_single (outf, insn);
5834
5835   fputs (";; Registers live at end:", outf);
5836   dump_regset (bb->global_live_at_end, outf);
5837   putc ('\n', outf);
5838
5839   fputs (";; Successors: ", outf);
5840   for (e = bb->succ; e; e = e->succ_next)
5841     dump_edge_info (outf, e, 1);
5842   putc ('\n', outf);
5843 }
5844
5845 void
5846 debug_bb (bb)
5847      basic_block bb;
5848 {
5849   dump_bb (bb, stderr);
5850 }
5851
5852 void
5853 debug_bb_n (n)
5854      int n;
5855 {
5856   dump_bb (BASIC_BLOCK(n), stderr);
5857 }
5858
5859 /* Like print_rtl, but also print out live information for the start of each
5860    basic block.  */
5861
5862 void
5863 print_rtl_with_bb (outf, rtx_first)
5864      FILE *outf;
5865      rtx rtx_first;
5866 {
5867   register rtx tmp_rtx;
5868
5869   if (rtx_first == 0)
5870     fprintf (outf, "(nil)\n");
5871   else
5872     {
5873       int i;
5874       enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
5875       int max_uid = get_max_uid ();
5876       basic_block *start = (basic_block *)
5877         xcalloc (max_uid, sizeof (basic_block));
5878       basic_block *end = (basic_block *)
5879         xcalloc (max_uid, sizeof (basic_block));
5880       enum bb_state *in_bb_p = (enum bb_state *)
5881         xcalloc (max_uid, sizeof (enum bb_state));
5882
5883       for (i = n_basic_blocks - 1; i >= 0; i--)
5884         {
5885           basic_block bb = BASIC_BLOCK (i);
5886           rtx x;
5887
5888           start[INSN_UID (bb->head)] = bb;
5889           end[INSN_UID (bb->end)] = bb;
5890           for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
5891             {
5892               enum bb_state state = IN_MULTIPLE_BB;
5893               if (in_bb_p[INSN_UID(x)] == NOT_IN_BB)
5894                 state = IN_ONE_BB;
5895               in_bb_p[INSN_UID(x)] = state;
5896
5897               if (x == bb->end)
5898                 break;
5899             }
5900         }
5901
5902       for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
5903         {
5904           int did_output;
5905           basic_block bb;
5906
5907           if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
5908             {
5909               fprintf (outf, ";; Start of basic block %d, registers live:",
5910                        bb->index);
5911               dump_regset (bb->global_live_at_start, outf);
5912               putc ('\n', outf);
5913             }
5914
5915           if (in_bb_p[INSN_UID(tmp_rtx)] == NOT_IN_BB
5916               && GET_CODE (tmp_rtx) != NOTE
5917               && GET_CODE (tmp_rtx) != BARRIER)
5918             fprintf (outf, ";; Insn is not within a basic block\n");
5919           else if (in_bb_p[INSN_UID(tmp_rtx)] == IN_MULTIPLE_BB)
5920             fprintf (outf, ";; Insn is in multiple basic blocks\n");
5921
5922           did_output = print_rtl_single (outf, tmp_rtx);
5923
5924           if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
5925             {
5926               fprintf (outf, ";; End of basic block %d, registers live:\n",
5927                        bb->index);
5928               dump_regset (bb->global_live_at_end, outf);
5929               putc ('\n', outf);
5930             }
5931
5932           if (did_output)
5933             putc ('\n', outf);
5934         }
5935
5936       free (start);
5937       free (end);
5938       free (in_bb_p);
5939     }
5940
5941   if (current_function_epilogue_delay_list != 0)
5942     {
5943       fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
5944       for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
5945            tmp_rtx = XEXP (tmp_rtx, 1))
5946         print_rtl_single (outf, XEXP (tmp_rtx, 0));
5947     }
5948 }
5949
5950 /* Compute dominator relationships using new flow graph structures.  */
5951 void
5952 compute_flow_dominators (dominators, post_dominators)
5953      sbitmap *dominators;
5954      sbitmap *post_dominators;
5955 {
5956   int bb;
5957   sbitmap *temp_bitmap;
5958   edge e;
5959   basic_block *worklist, *workend, *qin, *qout;
5960   int qlen;
5961
5962   /* Allocate a worklist array/queue.  Entries are only added to the
5963      list if they were not already on the list.  So the size is
5964      bounded by the number of basic blocks.  */
5965   worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
5966   workend = &worklist[n_basic_blocks];
5967
5968   temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
5969   sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
5970
5971   if (dominators)
5972     {
5973       /* The optimistic setting of dominators requires us to put every
5974          block on the work list initially.  */
5975       qin = qout = worklist;
5976       for (bb = 0; bb < n_basic_blocks; bb++)
5977         {
5978           *qin++ = BASIC_BLOCK (bb);
5979           BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
5980         }
5981       qlen = n_basic_blocks;
5982       qin = worklist;
5983
5984       /* We want a maximal solution, so initially assume everything dominates
5985          everything else.  */
5986       sbitmap_vector_ones (dominators, n_basic_blocks);
5987
5988       /* Mark successors of the entry block so we can identify them below.  */
5989       for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
5990         e->dest->aux = ENTRY_BLOCK_PTR;
5991
5992       /* Iterate until the worklist is empty.  */
5993       while (qlen)
5994         {
5995           /* Take the first entry off the worklist.  */
5996           basic_block b = *qout++;
5997           if (qout >= workend)
5998             qout = worklist;
5999           qlen--;
6000
6001           bb = b->index;
6002
6003           /* Compute the intersection of the dominators of all the
6004              predecessor blocks.
6005
6006              If one of the predecessor blocks is the ENTRY block, then the
6007              intersection of the dominators of the predecessor blocks is
6008              defined as the null set.  We can identify such blocks by the
6009              special value in the AUX field in the block structure.  */
6010           if (b->aux == ENTRY_BLOCK_PTR)
6011             {
6012               /* Do not clear the aux field for blocks which are
6013                  successors of the ENTRY block.  That way we we never
6014                  add them to the worklist again.
6015
6016                  The intersect of dominators of the preds of this block is
6017                  defined as the null set.  */
6018               sbitmap_zero (temp_bitmap[bb]);
6019             }
6020           else
6021             {
6022               /* Clear the aux field of this block so it can be added to
6023                  the worklist again if necessary.  */
6024               b->aux = NULL;
6025               sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
6026             }
6027
6028           /* Make sure each block always dominates itself.  */
6029           SET_BIT (temp_bitmap[bb], bb);
6030
6031           /* If the out state of this block changed, then we need to
6032              add the successors of this block to the worklist if they
6033              are not already on the worklist.  */
6034           if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
6035             {
6036               for (e = b->succ; e; e = e->succ_next)
6037                 {
6038                   if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
6039                     {
6040                       *qin++ = e->dest;
6041                       if (qin >= workend)
6042                         qin = worklist;
6043                       qlen++;
6044
6045                       e->dest->aux = e;
6046                     }
6047                 }
6048             }
6049         }
6050     }
6051
6052   if (post_dominators)
6053     {
6054       /* The optimistic setting of dominators requires us to put every
6055          block on the work list initially.  */
6056       qin = qout = worklist;
6057       for (bb = 0; bb < n_basic_blocks; bb++)
6058         {
6059           *qin++ = BASIC_BLOCK (bb);
6060           BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6061         }
6062       qlen = n_basic_blocks;
6063       qin = worklist;
6064
6065       /* We want a maximal solution, so initially assume everything post
6066          dominates everything else.  */
6067       sbitmap_vector_ones (post_dominators, n_basic_blocks);
6068
6069       /* Mark predecessors of the exit block so we can identify them below.  */
6070       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
6071         e->src->aux = EXIT_BLOCK_PTR;
6072
6073       /* Iterate until the worklist is empty.  */
6074       while (qlen)
6075         {
6076           /* Take the first entry off the worklist.  */
6077           basic_block b = *qout++;
6078           if (qout >= workend)
6079             qout = worklist;
6080           qlen--;
6081
6082           bb = b->index;
6083
6084           /* Compute the intersection of the post dominators of all the
6085              successor blocks.
6086
6087              If one of the successor blocks is the EXIT block, then the
6088              intersection of the dominators of the successor blocks is
6089              defined as the null set.  We can identify such blocks by the
6090              special value in the AUX field in the block structure.  */
6091           if (b->aux == EXIT_BLOCK_PTR)
6092             {
6093               /* Do not clear the aux field for blocks which are
6094                  predecessors of the EXIT block.  That way we we never
6095                  add them to the worklist again.
6096
6097                  The intersect of dominators of the succs of this block is
6098                  defined as the null set.  */
6099               sbitmap_zero (temp_bitmap[bb]);
6100             }
6101           else
6102             {
6103               /* Clear the aux field of this block so it can be added to
6104                  the worklist again if necessary.  */
6105               b->aux = NULL;
6106               sbitmap_intersection_of_succs (temp_bitmap[bb],
6107                                              post_dominators, bb);
6108             }
6109
6110           /* Make sure each block always post dominates itself.  */
6111           SET_BIT (temp_bitmap[bb], bb);
6112
6113           /* If the out state of this block changed, then we need to
6114              add the successors of this block to the worklist if they
6115              are not already on the worklist.  */
6116           if (sbitmap_a_and_b (post_dominators[bb],
6117                                post_dominators[bb],
6118                                temp_bitmap[bb]))
6119             {
6120               for (e = b->pred; e; e = e->pred_next)
6121                 {
6122                   if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
6123                     {
6124                       *qin++ = e->src;
6125                       if (qin >= workend)
6126                         qin = worklist;
6127                       qlen++;
6128
6129                       e->src->aux = e;
6130                     }
6131                 }
6132             }
6133         }
6134     }
6135
6136   free (worklist);
6137   free (temp_bitmap);
6138 }
6139
6140 /* Given DOMINATORS, compute the immediate dominators into IDOM.  */
6141
6142 void
6143 compute_immediate_dominators (idom, dominators)
6144      int *idom;
6145      sbitmap *dominators;
6146 {
6147   sbitmap *tmp;
6148   int b;
6149
6150   tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6151
6152   /* Begin with tmp(n) = dom(n) - { n }.  */
6153   for (b = n_basic_blocks; --b >= 0; )
6154     {
6155       sbitmap_copy (tmp[b], dominators[b]);
6156       RESET_BIT (tmp[b], b);
6157     }
6158
6159   /* Subtract out all of our dominator's dominators.  */
6160   for (b = n_basic_blocks; --b >= 0; )
6161     {
6162       sbitmap tmp_b = tmp[b];
6163       int s;
6164
6165       for (s = n_basic_blocks; --s >= 0; )
6166         if (TEST_BIT (tmp_b, s))
6167           sbitmap_difference (tmp_b, tmp_b, tmp[s]);
6168     }
6169
6170   /* Find the one bit set in the bitmap and put it in the output array.  */
6171   for (b = n_basic_blocks; --b >= 0; )
6172     {
6173       int t;
6174       EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
6175     }
6176
6177   sbitmap_vector_free (tmp);
6178 }
6179
6180 /* Recompute register set/reference counts immediately prior to register
6181    allocation.
6182
6183    This avoids problems with set/reference counts changing to/from values
6184    which have special meanings to the register allocators.
6185
6186    Additionally, the reference counts are the primary component used by the
6187    register allocators to prioritize pseudos for allocation to hard regs.
6188    More accurate reference counts generally lead to better register allocation.
6189
6190    F is the first insn to be scanned.
6191
6192    LOOP_STEP denotes how much loop_depth should be incremented per
6193    loop nesting level in order to increase the ref count more for
6194    references in a loop.
6195
6196    It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
6197    possibly other information which is used by the register allocators.  */
6198
6199 void
6200 recompute_reg_usage (f, loop_step)
6201      rtx f ATTRIBUTE_UNUSED;
6202      int loop_step ATTRIBUTE_UNUSED;
6203 {
6204   allocate_reg_life_data ();
6205   update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO);
6206 }
6207
6208 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
6209    blocks.  If BLOCKS is NULL, assume the universal set.  Returns a count
6210    of the number of registers that died.  */
6211
6212 int
6213 count_or_remove_death_notes (blocks, kill)
6214     sbitmap blocks;
6215     int kill;
6216 {
6217   int i, count = 0;
6218
6219   for (i = n_basic_blocks - 1; i >= 0; --i)
6220     {
6221       basic_block bb;
6222       rtx insn;
6223
6224       if (blocks && ! TEST_BIT (blocks, i))
6225         continue;
6226
6227       bb = BASIC_BLOCK (i);
6228
6229       for (insn = bb->head; ; insn = NEXT_INSN (insn))
6230         {
6231           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
6232             {
6233               rtx *pprev = &REG_NOTES (insn);
6234               rtx link = *pprev;
6235
6236               while (link)
6237                 {
6238                   switch (REG_NOTE_KIND (link))
6239                     {
6240                     case REG_DEAD:
6241                       if (GET_CODE (XEXP (link, 0)) == REG)
6242                         {
6243                           rtx reg = XEXP (link, 0);
6244                           int n;
6245
6246                           if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
6247                             n = 1;
6248                           else
6249                             n = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
6250                           count += n;
6251                         }
6252                       /* FALLTHRU */
6253
6254                     case REG_UNUSED:
6255                       if (kill)
6256                         {
6257                           rtx next = XEXP (link, 1);
6258                           free_EXPR_LIST_node (link);
6259                           *pprev = link = next;
6260                           break;
6261                         }
6262                       /* FALLTHRU */
6263
6264                     default:
6265                       pprev = &XEXP (link, 1);
6266                       link = *pprev;
6267                       break;
6268                     }
6269                 }
6270             }
6271
6272           if (insn == bb->end)
6273             break;
6274         }
6275     }
6276
6277   return count;
6278 }
6279
6280 /* Record INSN's block as BB.  */
6281
6282 void
6283 set_block_for_insn (insn, bb)
6284      rtx insn;
6285      basic_block bb;
6286 {
6287   size_t uid = INSN_UID (insn);
6288   if (uid >= basic_block_for_insn->num_elements)
6289     {
6290       int new_size;
6291
6292       /* Add one-eighth the size so we don't keep calling xrealloc.  */
6293       new_size = uid + (uid + 7) / 8;
6294
6295       VARRAY_GROW (basic_block_for_insn, new_size);
6296     }
6297   VARRAY_BB (basic_block_for_insn, uid) = bb;
6298 }
6299
6300 /* Record INSN's block number as BB.  */
6301 /* ??? This has got to go.  */
6302
6303 void
6304 set_block_num (insn, bb)
6305      rtx insn;
6306      int bb;
6307 {
6308   set_block_for_insn (insn, BASIC_BLOCK (bb));
6309 }
6310 \f
6311 /* Verify the CFG consistency.  This function check some CFG invariants and
6312    aborts when something is wrong.  Hope that this function will help to
6313    convert many optimization passes to preserve CFG consistent.
6314
6315    Currently it does following checks:
6316
6317    - test head/end pointers
6318    - overlapping of basic blocks
6319    - edge list corectness
6320    - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
6321    - tails of basic blocks (ensure that boundary is necesary)
6322    - scans body of the basic block for JUMP_INSN, CODE_LABEL
6323      and NOTE_INSN_BASIC_BLOCK
6324    - check that all insns are in the basic blocks
6325    (except the switch handling code, barriers and notes)
6326    - check that all returns are followed by barriers
6327
6328    In future it can be extended check a lot of other stuff as well
6329    (reachability of basic blocks, life information, etc. etc.).  */
6330
6331 void
6332 verify_flow_info ()
6333 {
6334   const int max_uid = get_max_uid ();
6335   const rtx rtx_first = get_insns ();
6336   basic_block *bb_info;
6337   rtx x;
6338   int i, last_bb_num_seen, num_bb_notes, err = 0;
6339
6340   bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
6341
6342   /* First pass check head/end pointers and set bb_info array used by
6343      later passes.  */
6344   for (i = n_basic_blocks - 1; i >= 0; i--)
6345     {
6346       basic_block bb = BASIC_BLOCK (i);
6347
6348       /* Check the head pointer and make sure that it is pointing into
6349          insn list.  */
6350       for (x = rtx_first; x != NULL_RTX; x = NEXT_INSN (x))
6351         if (x == bb->head)
6352           break;
6353       if (!x)
6354         {
6355           error ("Head insn %d for block %d not found in the insn stream.",
6356                  INSN_UID (bb->head), bb->index);
6357           err = 1;
6358         }
6359
6360       /* Check the end pointer and make sure that it is pointing into
6361          insn list.  */
6362       for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
6363         {
6364           if (bb_info[INSN_UID (x)] != NULL)
6365             {
6366               error ("Insn %d is in multiple basic blocks (%d and %d)",
6367                      INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
6368               err = 1;
6369             }
6370           bb_info[INSN_UID (x)] = bb;
6371
6372           if (x == bb->end)
6373             break;
6374         }
6375       if (!x)
6376         {
6377           error ("End insn %d for block %d not found in the insn stream.",
6378                  INSN_UID (bb->end), bb->index);
6379           err = 1;
6380         }
6381     }
6382
6383   /* Now check the basic blocks (boundaries etc.) */
6384   for (i = n_basic_blocks - 1; i >= 0; i--)
6385     {
6386       basic_block bb = BASIC_BLOCK (i);
6387       /* Check corectness of edge lists */
6388       edge e;
6389
6390       e = bb->succ;
6391       while (e)
6392         {
6393           if (e->src != bb)
6394             {
6395               fprintf (stderr, "verify_flow_info: Basic block %d succ edge is corrupted\n",
6396                        bb->index);
6397               fprintf (stderr, "Predecessor: ");
6398               dump_edge_info (stderr, e, 0);
6399               fprintf (stderr, "\nSuccessor: ");
6400               dump_edge_info (stderr, e, 1);
6401               fflush (stderr);
6402               err = 1;
6403             }
6404           if (e->dest != EXIT_BLOCK_PTR)
6405             {
6406               edge e2 = e->dest->pred;
6407               while (e2 && e2 != e)
6408                 e2 = e2->pred_next;
6409               if (!e2)
6410                 {
6411                   error ("Basic block %i edge lists are corrupted", bb->index);
6412                   err = 1;
6413                 }
6414             }
6415           e = e->succ_next;
6416         }
6417
6418       e = bb->pred;
6419       while (e)
6420         {
6421           if (e->dest != bb)
6422             {
6423               error ("Basic block %d pred edge is corrupted", bb->index);
6424               fputs ("Predecessor: ", stderr);
6425               dump_edge_info (stderr, e, 0);
6426               fputs ("\nSuccessor: ", stderr);
6427               dump_edge_info (stderr, e, 1);
6428               fputc ('\n', stderr);
6429               err = 1;
6430             }
6431           if (e->src != ENTRY_BLOCK_PTR)
6432             {
6433               edge e2 = e->src->succ;
6434               while (e2 && e2 != e)
6435                 e2 = e2->succ_next;
6436               if (!e2)
6437                 {
6438                   error ("Basic block %i edge lists are corrupted", bb->index);
6439                   err = 1;
6440                 }
6441             }
6442           e = e->pred_next;
6443         }
6444
6445       /* OK pointers are correct.  Now check the header of basic
6446          block.  It ought to contain optional CODE_LABEL followed
6447          by NOTE_BASIC_BLOCK.  */
6448       x = bb->head;
6449       if (GET_CODE (x) == CODE_LABEL)
6450         {
6451           if (bb->end == x)
6452             {
6453               error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
6454                      bb->index);
6455               err = 1;
6456             }
6457           x = NEXT_INSN (x);
6458         }
6459       if (GET_CODE (x) != NOTE
6460           || NOTE_LINE_NUMBER (x) != NOTE_INSN_BASIC_BLOCK
6461           || NOTE_BASIC_BLOCK (x) != bb)
6462         {
6463           error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
6464                  bb->index);
6465           err = 1;
6466         }
6467
6468       if (bb->end == x)
6469         {
6470           /* Do checks for empty blocks here */
6471         }
6472       else
6473         {
6474           x = NEXT_INSN (x);
6475           while (x)
6476             {
6477               if (GET_CODE (x) == NOTE
6478                   && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
6479                 {
6480                   error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
6481                          INSN_UID (x), bb->index);
6482                   err = 1;
6483                 }
6484
6485               if (x == bb->end)
6486                 break;
6487
6488               if (GET_CODE (x) == JUMP_INSN
6489                   || GET_CODE (x) == CODE_LABEL
6490                   || GET_CODE (x) == BARRIER)
6491                 {
6492                   error ("In basic block %d:", bb->index);
6493                   fatal_insn ("Flow control insn inside a basic block", x);
6494                 }
6495
6496               x = NEXT_INSN (x);
6497             }
6498         }
6499     }
6500
6501   last_bb_num_seen = -1;
6502   num_bb_notes = 0;
6503   x = rtx_first;
6504   while (x)
6505     {
6506       if (GET_CODE (x) == NOTE
6507           && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
6508         {
6509           basic_block bb = NOTE_BASIC_BLOCK (x);
6510           num_bb_notes++;
6511           if (bb->index != last_bb_num_seen + 1)
6512             fatal ("Basic blocks not numbered consecutively");
6513           last_bb_num_seen = bb->index;
6514         }
6515
6516       if (!bb_info[INSN_UID (x)])
6517         {
6518           switch (GET_CODE (x))
6519             {
6520             case BARRIER:
6521             case NOTE:
6522               break;
6523
6524             case CODE_LABEL:
6525               /* An addr_vec is placed outside any block block.  */
6526               if (NEXT_INSN (x)
6527                   && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
6528                   && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
6529                       || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
6530                 {
6531                   x = NEXT_INSN (x);
6532                 }
6533
6534               /* But in any case, non-deletable labels can appear anywhere.  */
6535               break;
6536
6537             default:
6538               fatal_insn ("Insn outside basic block", x);
6539             }
6540         }
6541
6542       if (GET_RTX_CLASS (GET_CODE (x)) == 'i'
6543           && GET_CODE (x) == JUMP_INSN
6544           && returnjump_p (x) && ! condjump_p (x)
6545           && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
6546             fatal_insn ("Return not followed by barrier", x);
6547
6548       x = NEXT_INSN (x);
6549     }
6550
6551   if (num_bb_notes != n_basic_blocks)
6552     fatal ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
6553            num_bb_notes, n_basic_blocks);
6554
6555   if (err)
6556     abort ();
6557
6558   /* Clean up.  */
6559   free (bb_info);
6560 }
6561 \f
6562 /* Functions to access an edge list with a vector representation.
6563    Enough data is kept such that given an index number, the
6564    pred and succ that edge reprsents can be determined, or
6565    given a pred and a succ, it's index number can be returned.
6566    This allows algorithms which comsume a lot of memory to
6567    represent the normally full matrix of edge (pred,succ) with a
6568    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
6569    wasted space in the client code due to sparse flow graphs.  */
6570
6571 /* This functions initializes the edge list. Basically the entire
6572    flowgraph is processed, and all edges are assigned a number,
6573    and the data structure is filed in.  */
6574 struct edge_list *
6575 create_edge_list ()
6576 {
6577   struct edge_list *elist;
6578   edge e;
6579   int num_edges;
6580   int x;
6581   int block_count;
6582
6583   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
6584
6585   num_edges = 0;
6586
6587   /* Determine the number of edges in the flow graph by counting successor
6588      edges on each basic block.  */
6589   for (x = 0; x < n_basic_blocks; x++)
6590     {
6591       basic_block bb = BASIC_BLOCK (x);
6592
6593       for (e = bb->succ; e; e = e->succ_next)
6594         num_edges++;
6595     }
6596   /* Don't forget successors of the entry block.  */
6597   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6598     num_edges++;
6599
6600   elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
6601   elist->num_blocks = block_count;
6602   elist->num_edges = num_edges;
6603   elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
6604
6605   num_edges = 0;
6606
6607   /* Follow successors of the entry block, and register these edges.  */
6608   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6609     {
6610       elist->index_to_edge[num_edges] = e;
6611       num_edges++;
6612     }
6613
6614   for (x = 0; x < n_basic_blocks; x++)
6615     {
6616       basic_block bb = BASIC_BLOCK (x);
6617
6618       /* Follow all successors of blocks, and register these edges.  */
6619       for (e = bb->succ; e; e = e->succ_next)
6620         {
6621           elist->index_to_edge[num_edges] = e;
6622           num_edges++;
6623         }
6624     }
6625   return elist;
6626 }
6627
6628 /* This function free's memory associated with an edge list.  */
6629 void
6630 free_edge_list (elist)
6631      struct edge_list *elist;
6632 {
6633   if (elist)
6634     {
6635       free (elist->index_to_edge);
6636       free (elist);
6637     }
6638 }
6639
6640 /* This function provides debug output showing an edge list.  */
6641 void
6642 print_edge_list (f, elist)
6643      FILE *f;
6644      struct edge_list *elist;
6645 {
6646   int x;
6647   fprintf(f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
6648           elist->num_blocks - 2, elist->num_edges);
6649
6650   for (x = 0; x < elist->num_edges; x++)
6651     {
6652       fprintf (f, " %-4d - edge(", x);
6653       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
6654         fprintf (f,"entry,");
6655       else
6656         fprintf (f,"%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
6657
6658       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
6659         fprintf (f,"exit)\n");
6660       else
6661         fprintf (f,"%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
6662     }
6663 }
6664
6665 /* This function provides an internal consistancy check of an edge list,
6666    verifying that all edges are present, and that there are no
6667    extra edges.  */
6668 void
6669 verify_edge_list (f, elist)
6670      FILE *f;
6671      struct edge_list *elist;
6672 {
6673   int x, pred, succ, index;
6674   edge e;
6675
6676   for (x = 0; x < n_basic_blocks; x++)
6677     {
6678       basic_block bb = BASIC_BLOCK (x);
6679
6680       for (e = bb->succ; e; e = e->succ_next)
6681         {
6682           pred = e->src->index;
6683           succ = e->dest->index;
6684           index = EDGE_INDEX (elist, e->src, e->dest);
6685           if (index == EDGE_INDEX_NO_EDGE)
6686             {
6687               fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6688               continue;
6689             }
6690           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6691             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6692                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6693           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6694             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6695                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6696         }
6697     }
6698   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6699     {
6700       pred = e->src->index;
6701       succ = e->dest->index;
6702       index = EDGE_INDEX (elist, e->src, e->dest);
6703       if (index == EDGE_INDEX_NO_EDGE)
6704         {
6705           fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6706           continue;
6707         }
6708       if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6709         fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6710                  index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6711       if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6712         fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6713                  index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6714     }
6715   /* We've verified that all the edges are in the list, no lets make sure
6716      there are no spurious edges in the list.  */
6717
6718   for (pred = 0 ; pred < n_basic_blocks; pred++)
6719     for (succ = 0 ; succ < n_basic_blocks; succ++)
6720       {
6721         basic_block p = BASIC_BLOCK (pred);
6722         basic_block s = BASIC_BLOCK (succ);
6723
6724         int found_edge = 0;
6725
6726         for (e = p->succ; e; e = e->succ_next)
6727           if (e->dest == s)
6728             {
6729               found_edge = 1;
6730               break;
6731             }
6732         for (e = s->pred; e; e = e->pred_next)
6733           if (e->src == p)
6734             {
6735               found_edge = 1;
6736               break;
6737             }
6738         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6739             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6740           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
6741                    pred, succ);
6742         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6743             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6744           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
6745                    pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6746                                            BASIC_BLOCK (succ)));
6747       }
6748     for (succ = 0 ; succ < n_basic_blocks; succ++)
6749       {
6750         basic_block p = ENTRY_BLOCK_PTR;
6751         basic_block s = BASIC_BLOCK (succ);
6752
6753         int found_edge = 0;
6754
6755         for (e = p->succ; e; e = e->succ_next)
6756           if (e->dest == s)
6757             {
6758               found_edge = 1;
6759               break;
6760             }
6761         for (e = s->pred; e; e = e->pred_next)
6762           if (e->src == p)
6763             {
6764               found_edge = 1;
6765               break;
6766             }
6767         if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6768             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6769           fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
6770                    succ);
6771         if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6772             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6773           fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
6774                    succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
6775                                      BASIC_BLOCK (succ)));
6776       }
6777     for (pred = 0 ; pred < n_basic_blocks; pred++)
6778       {
6779         basic_block p = BASIC_BLOCK (pred);
6780         basic_block s = EXIT_BLOCK_PTR;
6781
6782         int found_edge = 0;
6783
6784         for (e = p->succ; e; e = e->succ_next)
6785           if (e->dest == s)
6786             {
6787               found_edge = 1;
6788               break;
6789             }
6790         for (e = s->pred; e; e = e->pred_next)
6791           if (e->src == p)
6792             {
6793               found_edge = 1;
6794               break;
6795             }
6796         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6797             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6798           fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
6799                    pred);
6800         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6801             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6802           fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
6803                    pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6804                                      EXIT_BLOCK_PTR));
6805       }
6806 }
6807
6808 /* This routine will determine what, if any, edge there is between
6809    a specified predecessor and successor.  */
6810
6811 int
6812 find_edge_index (edge_list, pred, succ)
6813      struct edge_list *edge_list;
6814      basic_block pred, succ;
6815 {
6816   int x;
6817   for (x = 0; x < NUM_EDGES (edge_list); x++)
6818     {
6819       if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
6820           && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
6821         return x;
6822     }
6823   return (EDGE_INDEX_NO_EDGE);
6824 }
6825
6826 /* This function will remove an edge from the flow graph.  */
6827 void
6828 remove_edge (e)
6829      edge e;
6830 {
6831   edge last_pred = NULL;
6832   edge last_succ = NULL;
6833   edge tmp;
6834   basic_block src, dest;
6835   src = e->src;
6836   dest = e->dest;
6837   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
6838     last_succ = tmp;
6839
6840   if (!tmp)
6841     abort ();
6842   if (last_succ)
6843     last_succ->succ_next = e->succ_next;
6844   else
6845     src->succ = e->succ_next;
6846
6847   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
6848     last_pred = tmp;
6849
6850   if (!tmp)
6851     abort ();
6852   if (last_pred)
6853     last_pred->pred_next = e->pred_next;
6854   else
6855     dest->pred = e->pred_next;
6856
6857   n_edges--;
6858   free (e);
6859 }
6860
6861 /* This routine will remove any fake successor edges for a basic block.
6862    When the edge is removed, it is also removed from whatever predecessor
6863    list it is in.  */
6864 static void
6865 remove_fake_successors (bb)
6866      basic_block bb;
6867 {
6868   edge e;
6869   for (e = bb->succ; e ; )
6870     {
6871       edge tmp = e;
6872       e = e->succ_next;
6873       if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
6874         remove_edge (tmp);
6875     }
6876 }
6877
6878 /* This routine will remove all fake edges from the flow graph.  If
6879    we remove all fake successors, it will automatically remove all
6880    fake predecessors.  */
6881 void
6882 remove_fake_edges ()
6883 {
6884   int x;
6885
6886   for (x = 0; x < n_basic_blocks; x++)
6887     remove_fake_successors (BASIC_BLOCK (x));
6888
6889   /* We've handled all successors except the entry block's.  */
6890   remove_fake_successors (ENTRY_BLOCK_PTR);
6891 }
6892
6893 /* This functions will add a fake edge between any block which has no
6894    successors, and the exit block. Some data flow equations require these
6895    edges to exist.  */
6896 void
6897 add_noreturn_fake_exit_edges ()
6898 {
6899   int x;
6900
6901   for (x = 0; x < n_basic_blocks; x++)
6902     if (BASIC_BLOCK (x)->succ == NULL)
6903       make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
6904 }
6905
6906 /* Redirect an edge's successor from one block to another.  */
6907
6908 void
6909 redirect_edge_succ (e, new_succ)
6910      edge e;
6911      basic_block new_succ;
6912 {
6913   edge *pe;
6914
6915   /* Disconnect the edge from the old successor block.  */
6916   for (pe = &e->dest->pred; *pe != e ; pe = &(*pe)->pred_next)
6917     continue;
6918   *pe = (*pe)->pred_next;
6919
6920   /* Reconnect the edge to the new successor block.  */
6921   e->pred_next = new_succ->pred;
6922   new_succ->pred = e;
6923   e->dest = new_succ;
6924 }
6925
6926 /* Redirect an edge's predecessor from one block to another.  */
6927
6928 void
6929 redirect_edge_pred (e, new_pred)
6930      edge e;
6931      basic_block new_pred;
6932 {
6933   edge *pe;
6934
6935   /* Disconnect the edge from the old predecessor block.  */
6936   for (pe = &e->src->succ; *pe != e ; pe = &(*pe)->succ_next)
6937     continue;
6938   *pe = (*pe)->succ_next;
6939
6940   /* Reconnect the edge to the new predecessor block.  */
6941   e->succ_next = new_pred->succ;
6942   new_pred->succ = e;
6943   e->src = new_pred;
6944 }
6945 \f
6946 /* Dump the list of basic blocks in the bitmap NODES.  */
6947 static void
6948 flow_nodes_print (str, nodes, file)
6949      const char *str;
6950      const sbitmap nodes;
6951      FILE *file;
6952 {
6953   int node;
6954
6955   fprintf (file, "%s { ", str);
6956   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
6957   fputs ("}\n", file);
6958 }
6959
6960
6961 /* Dump the list of exiting edges in the array EDGES.  */
6962 static void
6963 flow_exits_print (str, edges, num_edges, file)
6964      const char *str;
6965      const edge *edges;
6966      int num_edges;
6967      FILE *file;
6968 {
6969   int i;
6970
6971   fprintf (file, "%s { ", str);
6972   for (i = 0; i < num_edges; i++)
6973     fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
6974   fputs ("}\n", file);
6975 }
6976
6977
6978 /* Dump loop related CFG information.  */
6979 static void
6980 flow_loops_cfg_dump (loops, file)
6981      const struct loops *loops;
6982      FILE *file;
6983 {
6984   int i;
6985
6986   if (! loops->num || ! file || ! loops->cfg.dom)
6987     return;
6988
6989   for (i = 0; i < n_basic_blocks; i++)
6990     {
6991       edge succ;
6992
6993       fprintf (file, ";; %d succs { ", i);
6994       for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
6995         fprintf (file, "%d ", succ->dest->index);
6996       flow_nodes_print ("} dom", loops->cfg.dom[i], file);
6997     }
6998
6999
7000   /* Dump the DFS node order.  */
7001   if (loops->cfg.dfs_order)
7002     {
7003       fputs (";; DFS order: ", file);
7004       for (i = 0; i < n_basic_blocks; i++)
7005         fprintf (file, "%d ", loops->cfg.dfs_order[i]);
7006       fputs ("\n", file);
7007     }
7008 }
7009
7010
7011 /* Return non-zero if the nodes of LOOP are a subset of OUTER.  */
7012 static int
7013 flow_loop_nested_p (outer, loop)
7014      struct loop *outer;
7015      struct loop *loop;
7016 {
7017   return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
7018 }
7019
7020
7021 /* Dump the loop information specified by LOOPS to the stream FILE.  */
7022 void
7023 flow_loops_dump (loops, file, verbose)
7024      const struct loops *loops;
7025      FILE *file;
7026      int verbose;
7027 {
7028   int i;
7029   int num_loops;
7030
7031   num_loops = loops->num;
7032   if (! num_loops || ! file)
7033     return;
7034
7035   fprintf (file, ";; %d loops found, %d levels\n",
7036            num_loops, loops->levels);
7037
7038   for (i = 0; i < num_loops; i++)
7039     {
7040       struct loop *loop = &loops->array[i];
7041
7042       fprintf (file, ";; loop %d (%d to %d):\n;;   header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
7043                i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
7044                loop->header->index, loop->latch->index,
7045                loop->pre_header ? loop->pre_header->index : -1,
7046                loop->depth, loop->level,
7047                (long) (loop->outer ? (loop->outer - loops->array) : -1));
7048       fprintf (file, ";;   %d", loop->num_nodes);
7049       flow_nodes_print (" nodes", loop->nodes, file);
7050       fprintf (file, ";;   %d", loop->num_exits);
7051       flow_exits_print (" exits", loop->exits, loop->num_exits, file);
7052
7053       if (loop->shared)
7054         {
7055           int j;
7056
7057           for (j = 0; j < i; j++)
7058             {
7059               struct loop *oloop = &loops->array[j];
7060
7061               if (loop->header == oloop->header)
7062                 {
7063                   int disjoint;
7064                   int smaller;
7065
7066                   smaller = loop->num_nodes < oloop->num_nodes;
7067
7068                   /* If the union of LOOP and OLOOP is different than
7069                      the larger of LOOP and OLOOP then LOOP and OLOOP
7070                      must be disjoint.  */
7071                   disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
7072                                                    smaller ? oloop : loop);
7073                   fprintf (file, ";; loop header %d shared by loops %d, %d %s\n",
7074                            loop->header->index, i, j,
7075                            disjoint ? "disjoint" : "nested");
7076                 }
7077             }
7078         }
7079
7080       if (verbose)
7081         {
7082           /* Print diagnostics to compare our concept of a loop with
7083              what the loop notes say.  */
7084           if (GET_CODE (PREV_INSN (loop->first->head)) != NOTE
7085               || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
7086               != NOTE_INSN_LOOP_BEG)
7087             fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
7088                      INSN_UID (PREV_INSN (loop->first->head)));
7089           if (GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
7090               || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
7091               != NOTE_INSN_LOOP_END)
7092             fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
7093                      INSN_UID (NEXT_INSN (loop->last->end)));
7094         }
7095     }
7096
7097   if (verbose)
7098     flow_loops_cfg_dump (loops, file);
7099 }
7100
7101
7102 /* Free all the memory allocated for LOOPS.  */
7103 void
7104 flow_loops_free (loops)
7105        struct loops *loops;
7106 {
7107   if (loops->array)
7108     {
7109       int i;
7110
7111       if (! loops->num)
7112         abort ();
7113
7114       /* Free the loop descriptors.  */
7115       for (i = 0; i < loops->num; i++)
7116         {
7117           struct loop *loop = &loops->array[i];
7118
7119           if (loop->nodes)
7120             sbitmap_free (loop->nodes);
7121           if (loop->exits)
7122             free (loop->exits);
7123         }
7124       free (loops->array);
7125       loops->array = NULL;
7126
7127       if (loops->cfg.dom)
7128         sbitmap_vector_free (loops->cfg.dom);
7129       if (loops->cfg.dfs_order)
7130         free (loops->cfg.dfs_order);
7131
7132       sbitmap_free (loops->shared_headers);
7133     }
7134 }
7135
7136
7137 /* Find the exits from the loop using the bitmap of loop nodes NODES
7138    and store in EXITS array.  Return the number of exits from the
7139    loop.  */
7140 static int
7141 flow_loop_exits_find (nodes, exits)
7142      const sbitmap nodes;
7143      edge **exits;
7144 {
7145   edge e;
7146   int node;
7147   int num_exits;
7148
7149   *exits = NULL;
7150
7151   /* Check all nodes within the loop to see if there are any
7152      successors not in the loop.  Note that a node may have multiple
7153      exiting edges.  */
7154   num_exits = 0;
7155   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7156     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7157       {
7158         basic_block dest = e->dest;
7159
7160         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7161             num_exits++;
7162       }
7163   });
7164
7165   if (! num_exits)
7166     return 0;
7167
7168   *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
7169
7170   /* Store all exiting edges into an array.  */
7171   num_exits = 0;
7172   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7173     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7174       {
7175         basic_block dest = e->dest;
7176
7177         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7178           (*exits)[num_exits++] = e;
7179       }
7180   });
7181
7182   return num_exits;
7183 }
7184
7185
7186 /* Find the nodes contained within the loop with header HEADER and
7187    latch LATCH and store in NODES.  Return the number of nodes within
7188    the loop.  */
7189 static int
7190 flow_loop_nodes_find (header, latch, nodes)
7191      basic_block header;
7192      basic_block latch;
7193      sbitmap nodes;
7194 {
7195   basic_block *stack;
7196   int sp;
7197   int num_nodes = 0;
7198
7199   stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
7200   sp = 0;
7201
7202   /* Start with only the loop header in the set of loop nodes.  */
7203   sbitmap_zero (nodes);
7204   SET_BIT (nodes, header->index);
7205   num_nodes++;
7206   header->loop_depth++;
7207
7208   /* Push the loop latch on to the stack.  */
7209   if (! TEST_BIT (nodes, latch->index))
7210     {
7211       SET_BIT (nodes, latch->index);
7212       latch->loop_depth++;
7213       num_nodes++;
7214       stack[sp++] = latch;
7215     }
7216
7217   while (sp)
7218     {
7219       basic_block node;
7220       edge e;
7221
7222       node = stack[--sp];
7223       for (e = node->pred; e; e = e->pred_next)
7224         {
7225           basic_block ancestor = e->src;
7226
7227           /* If each ancestor not marked as part of loop, add to set of
7228              loop nodes and push on to stack.  */
7229           if (ancestor != ENTRY_BLOCK_PTR
7230               && ! TEST_BIT (nodes, ancestor->index))
7231             {
7232               SET_BIT (nodes, ancestor->index);
7233               ancestor->loop_depth++;
7234               num_nodes++;
7235               stack[sp++] = ancestor;
7236             }
7237         }
7238     }
7239   free (stack);
7240   return num_nodes;
7241 }
7242
7243
7244 /* Compute the depth first search order and store in the array
7245    DFS_ORDER, marking the nodes visited in VISITED.  Returns the
7246    number of nodes visited.  */
7247 static int
7248 flow_depth_first_order_compute (dfs_order)
7249      int *dfs_order;
7250 {
7251   edge e;
7252   edge *stack;
7253   int sp;
7254   int dfsnum = 0;
7255   sbitmap visited;
7256
7257   /* Allocate stack for back-tracking up CFG.  */
7258   stack = (edge *) xmalloc (n_basic_blocks * sizeof (edge));
7259   sp = 0;
7260
7261   /* Allocate bitmap to track nodes that have been visited.  */
7262   visited = sbitmap_alloc (n_basic_blocks);
7263
7264   /* None of the nodes in the CFG have been visited yet.  */
7265   sbitmap_zero (visited);
7266
7267   /* Start with the first successor edge from the entry block.  */
7268   e = ENTRY_BLOCK_PTR->succ;
7269   while (e)
7270     {
7271       basic_block src = e->src;
7272       basic_block dest = e->dest;
7273
7274       /* Mark that we have visited this node.  */
7275       if (src != ENTRY_BLOCK_PTR)
7276         SET_BIT (visited, src->index);
7277
7278       /* If this node has not been visited before, push the current
7279          edge on to the stack and proceed with the first successor
7280          edge of this node.  */
7281       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
7282           && dest->succ)
7283         {
7284           stack[sp++] = e;
7285           e = dest->succ;
7286         }
7287       else
7288         {
7289           if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
7290               && ! dest->succ)
7291             {
7292               /* DEST has no successors (for example, a non-returning
7293                  function is called) so do not push the current edge
7294                  but carry on with its next successor.  */
7295               dfs_order[dest->index] = n_basic_blocks - ++dfsnum;
7296               SET_BIT (visited, dest->index);
7297             }
7298
7299           while (! e->succ_next && src != ENTRY_BLOCK_PTR)
7300             {
7301               dfs_order[src->index] = n_basic_blocks - ++dfsnum;
7302
7303               /* Pop edge off stack.  */
7304               e = stack[--sp];
7305               src = e->src;
7306             }
7307           e = e->succ_next;
7308         }
7309     }
7310   free (stack);
7311   sbitmap_free (visited);
7312
7313   /* The number of nodes visited should not be greater than
7314      n_basic_blocks.  */
7315   if (dfsnum > n_basic_blocks)
7316     abort ();
7317
7318   /* There are some nodes left in the CFG that are unreachable.  */
7319   if (dfsnum < n_basic_blocks)
7320     abort ();
7321   return dfsnum;
7322 }
7323
7324
7325 /* Return the block for the pre-header of the loop with header
7326    HEADER where DOM specifies the dominator information.  Return NULL if
7327    there is no pre-header.  */
7328 static basic_block
7329 flow_loop_pre_header_find (header, dom)
7330      basic_block header;
7331      const sbitmap *dom;
7332 {
7333   basic_block pre_header;
7334   edge e;
7335
7336   /* If block p is a predecessor of the header and is the only block
7337      that the header does not dominate, then it is the pre-header.  */
7338   pre_header = NULL;
7339   for (e = header->pred; e; e = e->pred_next)
7340     {
7341       basic_block node = e->src;
7342
7343       if (node != ENTRY_BLOCK_PTR
7344           && ! TEST_BIT (dom[node->index], header->index))
7345         {
7346           if (pre_header == NULL)
7347             pre_header = node;
7348           else
7349             {
7350               /* There are multiple edges into the header from outside
7351                  the loop so there is no pre-header block.  */
7352               pre_header = NULL;
7353               break;
7354             }
7355         }
7356     }
7357   return pre_header;
7358 }
7359
7360
7361 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
7362    previously added.  The insertion algorithm assumes that the loops
7363    are added in the order found by a depth first search of the CFG.  */
7364 static void
7365 flow_loop_tree_node_add (prevloop, loop)
7366      struct loop *prevloop;
7367      struct loop *loop;
7368 {
7369
7370   if (flow_loop_nested_p (prevloop, loop))
7371     {
7372       prevloop->inner = loop;
7373       loop->outer = prevloop;
7374       return;
7375     }
7376
7377   while (prevloop->outer)
7378     {
7379       if (flow_loop_nested_p (prevloop->outer, loop))
7380         {
7381           prevloop->next = loop;
7382           loop->outer = prevloop->outer;
7383           return;
7384         }
7385       prevloop = prevloop->outer;
7386     }
7387
7388   prevloop->next = loop;
7389   loop->outer = NULL;
7390 }
7391
7392
7393 /* Build the loop hierarchy tree for LOOPS.  */
7394 static void
7395 flow_loops_tree_build (loops)
7396        struct loops *loops;
7397 {
7398   int i;
7399   int num_loops;
7400
7401   num_loops = loops->num;
7402   if (! num_loops)
7403     return;
7404
7405   /* Root the loop hierarchy tree with the first loop found.
7406      Since we used a depth first search this should be the
7407      outermost loop.  */
7408   loops->tree = &loops->array[0];
7409   loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
7410
7411   /* Add the remaining loops to the tree.  */
7412   for (i = 1; i < num_loops; i++)
7413     flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
7414 }
7415
7416
7417 /* Helper function to compute loop nesting depth and enclosed loop level
7418    for the natural loop specified by LOOP at the loop depth DEPTH.
7419    Returns the loop level.  */
7420 static int
7421 flow_loop_level_compute (loop, depth)
7422      struct loop *loop;
7423      int depth;
7424 {
7425   struct loop *inner;
7426   int level = 1;
7427
7428   if (! loop)
7429     return 0;
7430
7431   /* Traverse loop tree assigning depth and computing level as the
7432      maximum level of all the inner loops of this loop.  The loop
7433      level is equivalent to the height of the loop in the loop tree
7434      and corresponds to the number of enclosed loop levels (including
7435      itself).  */
7436   for (inner = loop->inner; inner; inner = inner->next)
7437     {
7438       int ilevel;
7439
7440       ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
7441
7442       if (ilevel > level)
7443         level = ilevel;
7444     }
7445   loop->level = level;
7446   loop->depth = depth;
7447   return level;
7448 }
7449
7450
7451 /* Compute the loop nesting depth and enclosed loop level for the loop
7452    hierarchy tree specfied by LOOPS.  Return the maximum enclosed loop
7453    level.  */
7454
7455 static int
7456 flow_loops_level_compute (loops)
7457      struct loops *loops;
7458 {
7459   struct loop *loop;
7460   int level;
7461   int levels = 0;
7462
7463   /* Traverse all the outer level loops.  */
7464   for (loop = loops->tree; loop; loop = loop->next)
7465     {
7466       level = flow_loop_level_compute (loop, 1);
7467       if (level > levels)
7468         levels = level;
7469     }
7470   return levels;
7471 }
7472
7473
7474 /* Find all the natural loops in the function and save in LOOPS structure
7475    and recalculate loop_depth information in basic block structures.
7476    Return the number of natural loops found.  */
7477
7478 int
7479 flow_loops_find (loops)
7480        struct loops *loops;
7481 {
7482   int i;
7483   int b;
7484   int num_loops;
7485   edge e;
7486   sbitmap headers;
7487   sbitmap *dom;
7488   int *dfs_order;
7489
7490   loops->num = 0;
7491   loops->array = NULL;
7492   loops->tree = NULL;
7493   dfs_order = NULL;
7494
7495   /* Taking care of this degenerate case makes the rest of
7496      this code simpler.  */
7497   if (n_basic_blocks == 0)
7498     return 0;
7499
7500   /* Compute the dominators.  */
7501   dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7502   compute_flow_dominators (dom, NULL);
7503
7504   /* Count the number of loop edges (back edges).  This should be the
7505      same as the number of natural loops.  Also clear the loop_depth
7506      and as we work from inner->outer in a loop nest we call
7507      find_loop_nodes_find which will increment loop_depth for nodes
7508      within the current loop, which happens to enclose inner loops.  */
7509
7510   num_loops = 0;
7511   for (b = 0; b < n_basic_blocks; b++)
7512     {
7513       BASIC_BLOCK (b)->loop_depth = 0;
7514       for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
7515         {
7516           basic_block latch = e->src;
7517
7518           /* Look for back edges where a predecessor is dominated
7519              by this block.  A natural loop has a single entry
7520              node (header) that dominates all the nodes in the
7521              loop.  It also has single back edge to the header
7522              from a latch node.  Note that multiple natural loops
7523              may share the same header.  */
7524           if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
7525             num_loops++;
7526         }
7527     }
7528
7529   if (num_loops)
7530     {
7531       /* Compute depth first search order of the CFG so that outer
7532          natural loops will be found before inner natural loops.  */
7533       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7534       flow_depth_first_order_compute (dfs_order);
7535
7536       /* Allocate loop structures.  */
7537       loops->array
7538         = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
7539
7540       headers = sbitmap_alloc (n_basic_blocks);
7541       sbitmap_zero (headers);
7542
7543       loops->shared_headers = sbitmap_alloc (n_basic_blocks);
7544       sbitmap_zero (loops->shared_headers);
7545
7546       /* Find and record information about all the natural loops
7547          in the CFG.  */
7548       num_loops = 0;
7549       for (b = 0; b < n_basic_blocks; b++)
7550         {
7551           basic_block header;
7552
7553           /* Search the nodes of the CFG in DFS order that we can find
7554              outer loops first.  */
7555           header = BASIC_BLOCK (dfs_order[b]);
7556
7557           /* Look for all the possible latch blocks for this header.  */
7558           for (e = header->pred; e; e = e->pred_next)
7559             {
7560               basic_block latch = e->src;
7561
7562               /* Look for back edges where a predecessor is dominated
7563                  by this block.  A natural loop has a single entry
7564                  node (header) that dominates all the nodes in the
7565                  loop.  It also has single back edge to the header
7566                  from a latch node.  Note that multiple natural loops
7567                  may share the same header.  */
7568               if (latch != ENTRY_BLOCK_PTR
7569                   && TEST_BIT (dom[latch->index], header->index))
7570                 {
7571                   struct loop *loop;
7572
7573                   loop = loops->array + num_loops;
7574
7575                   loop->header = header;
7576                   loop->latch = latch;
7577
7578                   /* Keep track of blocks that are loop headers so
7579                      that we can tell which loops should be merged.  */
7580                   if (TEST_BIT (headers, header->index))
7581                     SET_BIT (loops->shared_headers, header->index);
7582                   SET_BIT (headers, header->index);
7583
7584                   /* Find nodes contained within the loop.  */
7585                   loop->nodes = sbitmap_alloc (n_basic_blocks);
7586                   loop->num_nodes
7587                     = flow_loop_nodes_find (header, latch, loop->nodes);
7588
7589                   /* Compute first and last blocks within the loop.
7590                      These are often the same as the loop header and
7591                      loop latch respectively, but this is not always
7592                      the case.  */
7593                   loop->first
7594                     = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
7595                   loop->last
7596                     = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
7597
7598                   /* Find edges which exit the loop.  Note that a node
7599                      may have several exit edges.  */
7600                   loop->num_exits
7601                     = flow_loop_exits_find (loop->nodes, &loop->exits);
7602
7603                   /* Look to see if the loop has a pre-header node.  */
7604                   loop->pre_header
7605                     = flow_loop_pre_header_find (header, dom);
7606
7607                   num_loops++;
7608                 }
7609             }
7610         }
7611
7612       /* Natural loops with shared headers may either be disjoint or
7613          nested.  Disjoint loops with shared headers cannot be inner
7614          loops and should be merged.  For now just mark loops that share
7615          headers.  */
7616       for (i = 0; i < num_loops; i++)
7617         if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
7618           loops->array[i].shared = 1;
7619
7620       sbitmap_free (headers);
7621     }
7622
7623   loops->num = num_loops;
7624
7625   /* Save CFG derived information to avoid recomputing it.  */
7626   loops->cfg.dom = dom;
7627   loops->cfg.dfs_order = dfs_order;
7628
7629   /* Build the loop hierarchy tree.  */
7630   flow_loops_tree_build (loops);
7631
7632   /* Assign the loop nesting depth and enclosed loop level for each
7633      loop.  */
7634   loops->levels = flow_loops_level_compute (loops);
7635
7636   return num_loops;
7637 }
7638
7639
7640 /* Return non-zero if edge E enters header of LOOP from outside of LOOP.  */
7641
7642 int
7643 flow_loop_outside_edge_p (loop, e)
7644      const struct loop *loop;
7645      edge e;
7646 {
7647   if (e->dest != loop->header)
7648     abort ();
7649   return (e->src == ENTRY_BLOCK_PTR)
7650     || ! TEST_BIT (loop->nodes, e->src->index);
7651 }
7652
7653
7654 /* Clear LOG_LINKS fields of insns in a chain.  */
7655
7656 void
7657 clear_log_links (insns)
7658      rtx insns;
7659 {
7660   rtx i;
7661   for (i = insns; i; i = NEXT_INSN (i))
7662     if (GET_RTX_CLASS (GET_CODE (i)) == 'i')
7663       LOG_LINKS (i) = 0;
7664 }
7665
7666 /* Given a register bitmap, turn on the bits in a HARD_REG_SET that
7667    correspond to the hard registers, if any, set in that map.  This
7668    could be done far more efficiently by having all sorts of special-cases
7669    with moving single words, but probably isn't worth the trouble.  */
7670
7671 void
7672 reg_set_to_hard_reg_set (to, from)
7673      HARD_REG_SET *to;
7674      bitmap from;
7675 {
7676   int i;
7677
7678   EXECUTE_IF_SET_IN_BITMAP
7679     (from, 0, i,
7680      {
7681        if (i >= FIRST_PSEUDO_REGISTER)
7682          return;
7683        SET_HARD_REG_BIT (*to, i);
7684      });
7685 }
7686