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