gcc/flow.c

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