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