gcc/flow.c

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