gcc/flow.c

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