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