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