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 ((flags & PROP_KILL_DEAD_CODE)
3299               && insn_is_dead
3300               && reload_completed
3301               && (HAVE_epilogue || HAVE_prologue)
3302               && prologue_epilogue_contains (insn))
3303             {
3304               warning ("ICE: would have deleted prologue/epilogue insn");
3305               debug_rtx (insn);
3306               libcall_is_dead = insn_is_dead = 0;
3307             }
3308
3309           /* If an instruction consists of just dead store(s) on final pass,
3310              "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
3311              We could really delete it with delete_insn, but that
3312              can cause trouble for first or last insn in a basic block.  */
3313           if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
3314             {
3315               rtx inote;
3316               /* If the insn referred to a label, note that the label is
3317                  now less used.  */
3318               for (inote = REG_NOTES (insn); inote; inote = XEXP (inote, 1))
3319                 {
3320                   if (REG_NOTE_KIND (inote) == REG_LABEL)
3321                     {
3322                       rtx label = XEXP (inote, 0);
3323                       rtx next;
3324                       LABEL_NUSES (label)--;
3325
3326                       /* If this label was attached to an ADDR_VEC, it's
3327                          safe to delete the ADDR_VEC.  In fact, it's pretty much
3328                          mandatory to delete it, because the ADDR_VEC may
3329                          be referencing labels that no longer exist.  */
3330                       if (LABEL_NUSES (label) == 0
3331                           && (next = next_nonnote_insn (label)) != NULL
3332                           && GET_CODE (next) == JUMP_INSN
3333                           && (GET_CODE (PATTERN (next)) == ADDR_VEC
3334                               || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
3335                         {
3336                           rtx pat = PATTERN (next);
3337                           int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3338                           int len = XVECLEN (pat, diff_vec_p);
3339                           int i;
3340                           for (i = 0; i < len; i++)
3341                             LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
3342                           PUT_CODE (next, NOTE);
3343                           NOTE_LINE_NUMBER (next) = NOTE_INSN_DELETED;
3344                           NOTE_SOURCE_FILE (next) = 0;
3345                         }
3346                     }
3347                 }
3348
3349               PUT_CODE (insn, NOTE);
3350               NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
3351               NOTE_SOURCE_FILE (insn) = 0;
3352
3353               /* CC0 is now known to be dead.  Either this insn used it,
3354                  in which case it doesn't anymore, or clobbered it,
3355                  so the next insn can't use it.  */
3356               cc0_live = 0;
3357
3358               /* If this insn is copying the return value from a library call,
3359                  delete the entire library call.  */
3360               if (libcall_is_dead)
3361                 {
3362                   rtx first = XEXP (note, 0);
3363                   rtx p = insn;
3364                   while (INSN_DELETED_P (first))
3365                     first = NEXT_INSN (first);
3366                   while (p != first)
3367                     {
3368                       p = PREV_INSN (p);
3369                       PUT_CODE (p, NOTE);
3370                       NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
3371                       NOTE_SOURCE_FILE (p) = 0;
3372                     }
3373                 }
3374               goto flushed;
3375             }
3376
3377           CLEAR_REG_SET (dead);
3378           CLEAR_REG_SET (live);
3379
3380           /* See if this is an increment or decrement that can be
3381              merged into a following memory address.  */
3382 #ifdef AUTO_INC_DEC
3383           {
3384             register rtx x = single_set (insn);
3385
3386             /* Does this instruction increment or decrement a register?  */
3387             if (!reload_completed
3388                 && (flags & PROP_AUTOINC)
3389                 && x != 0
3390                 && GET_CODE (SET_DEST (x)) == REG
3391                 && (GET_CODE (SET_SRC (x)) == PLUS
3392                     || GET_CODE (SET_SRC (x)) == MINUS)
3393                 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
3394                 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
3395                 /* Ok, look for a following memory ref we can combine with.
3396                    If one is found, change the memory ref to a PRE_INC
3397                    or PRE_DEC, cancel this insn, and return 1.
3398                    Return 0 if nothing has been done.  */
3399                 && try_pre_increment_1 (insn))
3400               goto flushed;
3401           }
3402 #endif /* AUTO_INC_DEC */
3403
3404           /* If this is not the final pass, and this insn is copying the
3405              value of a library call and it's dead, don't scan the
3406              insns that perform the library call, so that the call's
3407              arguments are not marked live.  */
3408           if (libcall_is_dead)
3409             {
3410               /* Mark the dest reg as `significant'.  */
3411               mark_set_regs (old, dead, PATTERN (insn), NULL_RTX,
3412                              significant, flags);
3413
3414               insn = XEXP (note, 0);
3415               prev = PREV_INSN (insn);
3416             }
3417           else if (GET_CODE (PATTERN (insn)) == SET
3418                    && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
3419                    && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
3420                    && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
3421                    && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
3422             /* We have an insn to pop a constant amount off the stack.
3423                (Such insns use PLUS regardless of the direction of the stack,
3424                and any insn to adjust the stack by a constant is always a pop.)
3425                These insns, if not dead stores, have no effect on life.  */
3426             ;
3427           else
3428             {
3429               /* Any regs live at the time of a call instruction
3430                  must not go in a register clobbered by calls.
3431                  Find all regs now live and record this for them.  */
3432
3433               if (GET_CODE (insn) == CALL_INSN
3434                   && (flags & PROP_REG_INFO))
3435                 EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
3436                                            {
3437                                              REG_N_CALLS_CROSSED (i)++;
3438                                            });
3439
3440               /* LIVE gets the regs used in INSN;
3441                  DEAD gets those set by it.  Dead insns don't make anything
3442                  live.  */
3443
3444               mark_set_regs (old, dead, PATTERN (insn),
3445                              insn, significant, flags);
3446
3447               /* If an insn doesn't use CC0, it becomes dead since we
3448                  assume that every insn clobbers it.  So show it dead here;
3449                  mark_used_regs will set it live if it is referenced.  */
3450               cc0_live = 0;
3451
3452               if (! insn_is_dead)
3453                 mark_used_regs (old, live, PATTERN (insn), flags, insn);
3454
3455               /* Sometimes we may have inserted something before INSN (such as
3456                  a move) when we make an auto-inc.  So ensure we will scan
3457                  those insns.  */
3458 #ifdef AUTO_INC_DEC
3459               prev = PREV_INSN (insn);
3460 #endif
3461
3462               if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
3463                 {
3464                   register int i;
3465
3466                   rtx note;
3467
3468                   for (note = CALL_INSN_FUNCTION_USAGE (insn);
3469                        note;
3470                        note = XEXP (note, 1))
3471                     if (GET_CODE (XEXP (note, 0)) == USE)
3472                       mark_used_regs (old, live, XEXP (XEXP (note, 0), 0),
3473                                       flags, insn);
3474
3475                   /* Each call clobbers all call-clobbered regs that are not
3476                      global or fixed.  Note that the function-value reg is a
3477                      call-clobbered reg, and mark_set_regs has already had
3478                      a chance to handle it.  */
3479
3480                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3481                     if (call_used_regs[i] && ! global_regs[i]
3482                         && ! fixed_regs[i])
3483                       {
3484                         SET_REGNO_REG_SET (dead, i);
3485                         if (significant)
3486                           SET_REGNO_REG_SET (significant, i);
3487                       }
3488
3489                   /* The stack ptr is used (honorarily) by a CALL insn.  */
3490                   SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
3491
3492                   /* Calls may also reference any of the global registers,
3493                      so they are made live.  */
3494                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3495                     if (global_regs[i])
3496                       mark_used_regs (old, live,
3497                                       gen_rtx_REG (reg_raw_mode[i], i),
3498                                       flags, insn);
3499
3500                   /* Calls also clobber memory.  */
3501                   free_EXPR_LIST_list (&mem_set_list);
3502                 }
3503
3504               /* Update OLD for the registers used or set.  */
3505               AND_COMPL_REG_SET (old, dead);
3506               IOR_REG_SET (old, live);
3507
3508             }
3509
3510           /* On final pass, update counts of how many insns each reg is live
3511              at.  */
3512           if (flags & PROP_REG_INFO)
3513             EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
3514                                        { REG_LIVE_LENGTH (i)++; });
3515         }
3516     flushed: ;
3517       if (insn == first)
3518         break;
3519     }
3520
3521   FREE_REG_SET (dead);
3522   FREE_REG_SET (live);
3523   free_EXPR_LIST_list (&mem_set_list);
3524 }
3525 \f
3526 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3527    (SET expressions whose destinations are registers dead after the insn).
3528    NEEDED is the regset that says which regs are alive after the insn.
3529
3530    Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3531
3532    If X is the entire body of an insn, NOTES contains the reg notes
3533    pertaining to the insn.  */
3534
3535 static int
3536 insn_dead_p (x, needed, call_ok, notes)
3537      rtx x;
3538      regset needed;
3539      int call_ok;
3540      rtx notes ATTRIBUTE_UNUSED;
3541 {
3542   enum rtx_code code = GET_CODE (x);
3543
3544 #ifdef AUTO_INC_DEC
3545   /* If flow is invoked after reload, we must take existing AUTO_INC
3546      expresions into account.  */
3547   if (reload_completed)
3548     {
3549       for ( ; notes; notes = XEXP (notes, 1))
3550         {
3551           if (REG_NOTE_KIND (notes) == REG_INC)
3552             {
3553               int regno = REGNO (XEXP (notes, 0));
3554
3555               /* Don't delete insns to set global regs.  */
3556               if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3557                   || REGNO_REG_SET_P (needed, regno))
3558                 return 0;
3559             }
3560         }
3561     }
3562 #endif
3563
3564   /* If setting something that's a reg or part of one,
3565      see if that register's altered value will be live.  */
3566
3567   if (code == SET)
3568     {
3569       rtx r = SET_DEST (x);
3570
3571       /* A SET that is a subroutine call cannot be dead.  */
3572       if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
3573         return 0;
3574
3575 #ifdef HAVE_cc0
3576       if (GET_CODE (r) == CC0)
3577         return ! cc0_live;
3578 #endif
3579
3580       if (GET_CODE (r) == MEM && ! MEM_VOLATILE_P (r))
3581         {
3582           rtx temp;
3583           /* Walk the set of memory locations we are currently tracking
3584              and see if one is an identical match to this memory location.
3585              If so, this memory write is dead (remember, we're walking
3586              backwards from the end of the block to the start.  */
3587           temp = mem_set_list;
3588           while (temp)
3589             {
3590               if (rtx_equal_p (XEXP (temp, 0), r))
3591                 return 1;
3592               temp = XEXP (temp, 1);
3593             }
3594         }
3595
3596       while (GET_CODE (r) == SUBREG || GET_CODE (r) == STRICT_LOW_PART
3597              || GET_CODE (r) == ZERO_EXTRACT)
3598         r = XEXP (r, 0);
3599
3600       if (GET_CODE (r) == REG)
3601         {
3602           int regno = REGNO (r);
3603
3604           /* Don't delete insns to set global regs.  */
3605           if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3606               /* Make sure insns to set frame pointer aren't deleted.  */
3607               || (regno == FRAME_POINTER_REGNUM
3608                   && (! reload_completed || frame_pointer_needed))
3609 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3610               || (regno == HARD_FRAME_POINTER_REGNUM
3611                   && (! reload_completed || frame_pointer_needed))
3612 #endif
3613 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3614               /* Make sure insns to set arg pointer are never deleted
3615                  (if the arg pointer isn't fixed, there will be a USE for
3616                  it, so we can treat it normally).  */
3617               || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
3618 #endif
3619               || REGNO_REG_SET_P (needed, regno))
3620             return 0;
3621
3622           /* If this is a hard register, verify that subsequent words are
3623              not needed.  */
3624           if (regno < FIRST_PSEUDO_REGISTER)
3625             {
3626               int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
3627
3628               while (--n > 0)
3629                 if (REGNO_REG_SET_P (needed, regno+n))
3630                   return 0;
3631             }
3632
3633           return 1;
3634         }
3635     }
3636
3637   /* If performing several activities,
3638      insn is dead if each activity is individually dead.
3639      Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
3640      that's inside a PARALLEL doesn't make the insn worth keeping.  */
3641   else if (code == PARALLEL)
3642     {
3643       int i = XVECLEN (x, 0);
3644
3645       for (i--; i >= 0; i--)
3646         if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
3647             && GET_CODE (XVECEXP (x, 0, i)) != USE
3648             && ! insn_dead_p (XVECEXP (x, 0, i), needed, call_ok, NULL_RTX))
3649           return 0;
3650
3651       return 1;
3652     }
3653
3654   /* A CLOBBER of a pseudo-register that is dead serves no purpose.  That
3655      is not necessarily true for hard registers.  */
3656   else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
3657            && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
3658            && ! REGNO_REG_SET_P (needed, REGNO (XEXP (x, 0))))
3659     return 1;
3660
3661   /* We do not check other CLOBBER or USE here.  An insn consisting of just
3662      a CLOBBER or just a USE should not be deleted.  */
3663   return 0;
3664 }
3665
3666 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
3667    return 1 if the entire library call is dead.
3668    This is true if X copies a register (hard or pseudo)
3669    and if the hard return  reg of the call insn is dead.
3670    (The caller should have tested the destination of X already for death.)
3671
3672    If this insn doesn't just copy a register, then we don't
3673    have an ordinary libcall.  In that case, cse could not have
3674    managed to substitute the source for the dest later on,
3675    so we can assume the libcall is dead.
3676
3677    NEEDED is the bit vector of pseudoregs live before this insn.
3678    NOTE is the REG_RETVAL note of the insn.  INSN is the insn itself.  */
3679
3680 static int
3681 libcall_dead_p (x, needed, note, insn)
3682      rtx x;
3683      regset needed;
3684      rtx note;
3685      rtx insn;
3686 {
3687   register RTX_CODE code = GET_CODE (x);
3688
3689   if (code == SET)
3690     {
3691       register rtx r = SET_SRC (x);
3692       if (GET_CODE (r) == REG)
3693         {
3694           rtx call = XEXP (note, 0);
3695           rtx call_pat;
3696           register int i;
3697
3698           /* Find the call insn.  */
3699           while (call != insn && GET_CODE (call) != CALL_INSN)
3700             call = NEXT_INSN (call);
3701
3702           /* If there is none, do nothing special,
3703              since ordinary death handling can understand these insns.  */
3704           if (call == insn)
3705             return 0;
3706
3707           /* See if the hard reg holding the value is dead.
3708              If this is a PARALLEL, find the call within it.  */
3709           call_pat = PATTERN (call);
3710           if (GET_CODE (call_pat) == PARALLEL)
3711             {
3712               for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
3713                 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
3714                     && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
3715                   break;
3716
3717               /* This may be a library call that is returning a value
3718                  via invisible pointer.  Do nothing special, since
3719                  ordinary death handling can understand these insns.  */
3720               if (i < 0)
3721                 return 0;
3722
3723               call_pat = XVECEXP (call_pat, 0, i);
3724             }
3725
3726           return insn_dead_p (call_pat, needed, 1, REG_NOTES (call));
3727         }
3728     }
3729   return 1;
3730 }
3731
3732 /* Return 1 if register REGNO was used before it was set, i.e. if it is
3733    live at function entry.  Don't count global register variables, variables
3734    in registers that can be used for function arg passing, or variables in
3735    fixed hard registers.  */
3736
3737 int
3738 regno_uninitialized (regno)
3739      int regno;
3740 {
3741   if (n_basic_blocks == 0
3742       || (regno < FIRST_PSEUDO_REGISTER
3743           && (global_regs[regno]
3744               || fixed_regs[regno]
3745               || FUNCTION_ARG_REGNO_P (regno))))
3746     return 0;
3747
3748   return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno);
3749 }
3750
3751 /* 1 if register REGNO was alive at a place where `setjmp' was called
3752    and was set more than once or is an argument.
3753    Such regs may be clobbered by `longjmp'.  */
3754
3755 int
3756 regno_clobbered_at_setjmp (regno)
3757      int regno;
3758 {
3759   if (n_basic_blocks == 0)
3760     return 0;
3761
3762   return ((REG_N_SETS (regno) > 1
3763            || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno))
3764           && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
3765 }
3766 \f
3767 /* INSN references memory, possibly using autoincrement addressing modes.
3768    Find any entries on the mem_set_list that need to be invalidated due
3769    to an address change.  */
3770 static void
3771 invalidate_mems_from_autoinc (insn)
3772      rtx insn;
3773 {
3774   rtx note = REG_NOTES (insn);
3775   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3776     {
3777       if (REG_NOTE_KIND (note) == REG_INC)
3778         {
3779           rtx temp = mem_set_list;
3780           rtx prev = NULL_RTX;
3781           rtx next;
3782
3783           while (temp)
3784             {
3785               next = XEXP (temp, 1);
3786               if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
3787                 {
3788                   /* Splice temp out of list.  */
3789                   if (prev)
3790                     XEXP (prev, 1) = next;
3791                   else
3792                     mem_set_list = next;
3793                   free_EXPR_LIST_node (temp);
3794                 }
3795               else
3796                 prev = temp;
3797               temp = next;
3798             }
3799         }
3800     }
3801 }
3802
3803 /* Process the registers that are set within X.  Their bits are set to
3804    1 in the regset DEAD, because they are dead prior to this insn.
3805
3806    If INSN is nonzero, it is the insn being processed.
3807
3808    FLAGS is the set of operations to perform.  */
3809
3810 static void
3811 mark_set_regs (needed, dead, x, insn, significant, flags)
3812      regset needed;
3813      regset dead;
3814      rtx x;
3815      rtx insn;
3816      regset significant;
3817      int flags;
3818 {
3819   register RTX_CODE code = GET_CODE (x);
3820
3821   if (code == SET || code == CLOBBER)
3822     mark_set_1 (needed, dead, x, insn, significant, flags);
3823   else if (code == PARALLEL)
3824     {
3825       register int i;
3826       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3827         {
3828           code = GET_CODE (XVECEXP (x, 0, i));
3829           if (code == SET || code == CLOBBER)
3830             mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn,
3831                         significant, flags);
3832         }
3833     }
3834 }
3835
3836 /* Process a single SET rtx, X.  */
3837
3838 static void
3839 mark_set_1 (needed, dead, x, insn, significant, flags)
3840      regset needed;
3841      regset dead;
3842      rtx x;
3843      rtx insn;
3844      regset significant;
3845      int flags;
3846 {
3847   register int regno = -1;
3848   register rtx reg = SET_DEST (x);
3849
3850   /* Some targets place small structures in registers for
3851      return values of functions.  We have to detect this
3852      case specially here to get correct flow information.  */
3853   if (GET_CODE (reg) == PARALLEL
3854       && GET_MODE (reg) == BLKmode)
3855     {
3856       register int i;
3857
3858       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
3859         mark_set_1 (needed, dead, XVECEXP (reg, 0, i), insn,
3860                     significant, flags);
3861       return;
3862     }
3863
3864   /* Modifying just one hardware register of a multi-reg value
3865      or just a byte field of a register
3866      does not mean the value from before this insn is now dead.
3867      But it does mean liveness of that register at the end of the block
3868      is significant.
3869
3870      Within mark_set_1, however, we treat it as if the register is
3871      indeed modified.  mark_used_regs will, however, also treat this
3872      register as being used.  Thus, we treat these insns as setting a
3873      new value for the register as a function of its old value.  This
3874      cases LOG_LINKS to be made appropriately and this will help combine.  */
3875
3876   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
3877          || GET_CODE (reg) == SIGN_EXTRACT
3878          || GET_CODE (reg) == STRICT_LOW_PART)
3879     reg = XEXP (reg, 0);
3880
3881   /* If this set is a MEM, then it kills any aliased writes.
3882      If this set is a REG, then it kills any MEMs which use the reg.  */
3883   if (flags & PROP_SCAN_DEAD_CODE)
3884     {
3885       if (GET_CODE (reg) == MEM
3886           || GET_CODE (reg) == REG)
3887         {
3888           rtx temp = mem_set_list;
3889           rtx prev = NULL_RTX;
3890           rtx next;
3891
3892           while (temp)
3893             {
3894               next = XEXP (temp, 1);
3895               if ((GET_CODE (reg) == MEM
3896                    && output_dependence (XEXP (temp, 0), reg))
3897                   || (GET_CODE (reg) == REG
3898                       && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
3899                 {
3900                   /* Splice this entry out of the list.  */
3901                   if (prev)
3902                     XEXP (prev, 1) = next;
3903                   else
3904                     mem_set_list = next;
3905                   free_EXPR_LIST_node (temp);
3906                 }
3907               else
3908                 prev = temp;
3909               temp = next;
3910             }
3911         }
3912
3913       /* If the memory reference had embedded side effects (autoincrement
3914          address modes.  Then we may need to kill some entries on the
3915          memory set list.  */
3916       if (insn && GET_CODE (reg) == MEM)
3917         invalidate_mems_from_autoinc (insn);
3918
3919       if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
3920           /* We do not know the size of a BLKmode store, so we do not track
3921              them for redundant store elimination.  */
3922           && GET_MODE (reg) != BLKmode
3923           /* There are no REG_INC notes for SP, so we can't assume we'll see
3924              everything that invalidates it.  To be safe, don't eliminate any
3925              stores though SP; none of them should be redundant anyway.  */
3926           && ! reg_mentioned_p (stack_pointer_rtx, reg))
3927         mem_set_list = alloc_EXPR_LIST (0, reg, mem_set_list);
3928     }
3929
3930   if (GET_CODE (reg) == REG
3931       && (regno = REGNO (reg),
3932           ! (regno == FRAME_POINTER_REGNUM
3933              && (! reload_completed || frame_pointer_needed)))
3934 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3935       && ! (regno == HARD_FRAME_POINTER_REGNUM
3936             && (! reload_completed || frame_pointer_needed))
3937 #endif
3938 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3939       && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
3940 #endif
3941       && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
3942       /* && regno != STACK_POINTER_REGNUM) -- let's try without this.  */
3943     {
3944       int some_needed = REGNO_REG_SET_P (needed, regno);
3945       int some_not_needed = ! some_needed;
3946
3947       /* Mark it as a significant register for this basic block.  */
3948       if (significant)
3949         SET_REGNO_REG_SET (significant, regno);
3950
3951       /* Mark it as dead before this insn.  */
3952       SET_REGNO_REG_SET (dead, regno);
3953
3954       /* A hard reg in a wide mode may really be multiple registers.
3955          If so, mark all of them just like the first.  */
3956       if (regno < FIRST_PSEUDO_REGISTER)
3957         {
3958           int n;
3959
3960           /* Nothing below is needed for the stack pointer; get out asap.
3961              Eg, log links aren't needed, since combine won't use them.  */
3962           if (regno == STACK_POINTER_REGNUM)
3963             return;
3964
3965           n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3966           while (--n > 0)
3967             {
3968               int regno_n = regno + n;
3969               int needed_regno = REGNO_REG_SET_P (needed, regno_n);
3970               if (significant)
3971                 SET_REGNO_REG_SET (significant, regno_n);
3972
3973               SET_REGNO_REG_SET (dead, regno_n);
3974               some_needed |= needed_regno;
3975               some_not_needed |= ! needed_regno;
3976             }
3977         }
3978
3979       /* Additional data to record if this is the final pass.  */
3980       if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
3981                    | PROP_DEATH_NOTES | PROP_AUTOINC))
3982         {
3983           register rtx y;
3984           register int blocknum = BLOCK_NUM (insn);
3985
3986           y = NULL_RTX;
3987           if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3988             y = reg_next_use[regno];
3989
3990           /* If this is a hard reg, record this function uses the reg.  */
3991
3992           if (regno < FIRST_PSEUDO_REGISTER)
3993             {
3994               register int i;
3995               int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
3996
3997               if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3998                 for (i = regno; i < endregno; i++)
3999                   {
4000                     /* The next use is no longer "next", since a store
4001                        intervenes.  */
4002                     reg_next_use[i] = 0;
4003                   }
4004
4005               if (flags & PROP_REG_INFO)
4006                 for (i = regno; i < endregno; i++)
4007                   {
4008                     regs_ever_live[i] = 1;
4009                     REG_N_SETS (i)++;
4010                   }
4011             }
4012           else
4013             {
4014               /* The next use is no longer "next", since a store
4015                  intervenes.  */
4016               if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4017                 reg_next_use[regno] = 0;
4018
4019               /* Keep track of which basic blocks each reg appears in.  */
4020
4021               if (flags & PROP_REG_INFO)
4022                 {
4023                   if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
4024                     REG_BASIC_BLOCK (regno) = blocknum;
4025                   else if (REG_BASIC_BLOCK (regno) != blocknum)
4026                     REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
4027
4028                   /* Count (weighted) references, stores, etc.  This counts a
4029                      register twice if it is modified, but that is correct.  */
4030                   REG_N_SETS (regno)++;
4031                   REG_N_REFS (regno) += loop_depth + 1;
4032
4033                   /* The insns where a reg is live are normally counted
4034                      elsewhere, but we want the count to include the insn
4035                      where the reg is set, and the normal counting mechanism
4036                      would not count it.  */
4037                   REG_LIVE_LENGTH (regno)++;
4038                 }
4039             }
4040
4041           if (! some_not_needed)
4042             {
4043               if (flags & PROP_LOG_LINKS)
4044                 {
4045                   /* Make a logical link from the next following insn
4046                      that uses this register, back to this insn.
4047                      The following insns have already been processed.
4048
4049                      We don't build a LOG_LINK for hard registers containing
4050                      in ASM_OPERANDs.  If these registers get replaced,
4051                      we might wind up changing the semantics of the insn,
4052                      even if reload can make what appear to be valid
4053                      assignments later.  */
4054                   if (y && (BLOCK_NUM (y) == blocknum)
4055                       && (regno >= FIRST_PSEUDO_REGISTER
4056                           || asm_noperands (PATTERN (y)) < 0))
4057                     LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
4058                 }
4059             }
4060           else if (! some_needed)
4061             {
4062               if (flags & PROP_REG_INFO)
4063                 REG_N_DEATHS (REGNO (reg))++;
4064
4065               if (flags & PROP_DEATH_NOTES)
4066                 {
4067                   /* Note that dead stores have already been deleted
4068                      when possible.  If we get here, we have found a
4069                      dead store that cannot be eliminated (because the
4070                      same insn does something useful).  Indicate this
4071                      by marking the reg being set as dying here.  */
4072                   REG_NOTES (insn)
4073                     = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4074                 }
4075             }
4076           else
4077             {
4078               if (flags & PROP_DEATH_NOTES)
4079                 {
4080                   /* This is a case where we have a multi-word hard register
4081                      and some, but not all, of the words of the register are
4082                      needed in subsequent insns.  Write REG_UNUSED notes
4083                      for those parts that were not needed.  This case should
4084                      be rare.  */
4085
4086                   int i;
4087
4088                   for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
4089                        i >= 0; i--)
4090                     if (!REGNO_REG_SET_P (needed, regno + i))
4091                       REG_NOTES (insn)
4092                         = (alloc_EXPR_LIST
4093                            (REG_UNUSED,
4094                             gen_rtx_REG (reg_raw_mode[regno + i], regno + i),
4095                             REG_NOTES (insn)));
4096                 }
4097             }
4098         }
4099     }
4100   else if (GET_CODE (reg) == REG)
4101     {
4102       if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4103         reg_next_use[regno] = 0;
4104     }
4105
4106   /* If this is the last pass and this is a SCRATCH, show it will be dying
4107      here and count it.  */
4108   else if (GET_CODE (reg) == SCRATCH)
4109     {
4110       if (flags & PROP_DEATH_NOTES)
4111         REG_NOTES (insn)
4112           = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4113     }
4114 }
4115 \f
4116 #ifdef AUTO_INC_DEC
4117
4118 /* X is a MEM found in INSN.  See if we can convert it into an auto-increment
4119    reference.  */
4120
4121 static void
4122 find_auto_inc (needed, x, insn)
4123      regset needed;
4124      rtx x;
4125      rtx insn;
4126 {
4127   rtx addr = XEXP (x, 0);
4128   HOST_WIDE_INT offset = 0;
4129   rtx set;
4130
4131   /* Here we detect use of an index register which might be good for
4132      postincrement, postdecrement, preincrement, or predecrement.  */
4133
4134   if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
4135     offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
4136
4137   if (GET_CODE (addr) == REG)
4138     {
4139       register rtx y;
4140       register int size = GET_MODE_SIZE (GET_MODE (x));
4141       rtx use;
4142       rtx incr;
4143       int regno = REGNO (addr);
4144
4145       /* Is the next use an increment that might make auto-increment? */
4146       if ((incr = reg_next_use[regno]) != 0
4147           && (set = single_set (incr)) != 0
4148           && GET_CODE (set) == SET
4149           && BLOCK_NUM (incr) == BLOCK_NUM (insn)
4150           /* Can't add side effects to jumps; if reg is spilled and
4151              reloaded, there's no way to store back the altered value.  */
4152           && GET_CODE (insn) != JUMP_INSN
4153           && (y = SET_SRC (set), GET_CODE (y) == PLUS)
4154           && XEXP (y, 0) == addr
4155           && GET_CODE (XEXP (y, 1)) == CONST_INT
4156           && ((HAVE_POST_INCREMENT
4157                && (INTVAL (XEXP (y, 1)) == size && offset == 0))
4158               || (HAVE_POST_DECREMENT
4159                   && (INTVAL (XEXP (y, 1)) == - size && offset == 0))
4160               || (HAVE_PRE_INCREMENT
4161                   && (INTVAL (XEXP (y, 1)) == size && offset == size))
4162               || (HAVE_PRE_DECREMENT
4163                   && (INTVAL (XEXP (y, 1)) == - size && offset == - size)))
4164           /* Make sure this reg appears only once in this insn.  */
4165           && (use = find_use_as_address (PATTERN (insn), addr, offset),
4166               use != 0 && use != (rtx) 1))
4167         {
4168           rtx q = SET_DEST (set);
4169           enum rtx_code inc_code = (INTVAL (XEXP (y, 1)) == size
4170                                     ? (offset ? PRE_INC : POST_INC)
4171                                     : (offset ? PRE_DEC : POST_DEC));
4172
4173           if (dead_or_set_p (incr, addr))
4174             {
4175               /* This is the simple case.  Try to make the auto-inc.  If
4176                  we can't, we are done.  Otherwise, we will do any
4177                  needed updates below.  */
4178               if (! validate_change (insn, &XEXP (x, 0),
4179                                      gen_rtx_fmt_e (inc_code, Pmode, addr),
4180                                      0))
4181                 return;
4182             }
4183           else if (GET_CODE (q) == REG
4184                    /* PREV_INSN used here to check the semi-open interval
4185                       [insn,incr).  */
4186                    && ! reg_used_between_p (q,  PREV_INSN (insn), incr)
4187                    /* We must also check for sets of q as q may be
4188                       a call clobbered hard register and there may
4189                       be a call between PREV_INSN (insn) and incr.  */
4190                    && ! reg_set_between_p (q,  PREV_INSN (insn), incr))
4191             {
4192               /* We have *p followed sometime later by q = p+size.
4193                  Both p and q must be live afterward,
4194                  and q is not used between INSN and its assignment.
4195                  Change it to q = p, ...*q..., q = q+size.
4196                  Then fall into the usual case.  */
4197               rtx insns, temp;
4198               basic_block bb;
4199
4200               start_sequence ();
4201               emit_move_insn (q, addr);
4202               insns = get_insns ();
4203               end_sequence ();
4204
4205               bb = BLOCK_FOR_INSN (insn);
4206               for (temp = insns; temp; temp = NEXT_INSN (temp))
4207                 set_block_for_insn (temp, bb);
4208
4209               /* If we can't make the auto-inc, or can't make the
4210                  replacement into Y, exit.  There's no point in making
4211                  the change below if we can't do the auto-inc and doing
4212                  so is not correct in the pre-inc case.  */
4213
4214               validate_change (insn, &XEXP (x, 0),
4215                                gen_rtx_fmt_e (inc_code, Pmode, q),
4216                                1);
4217               validate_change (incr, &XEXP (y, 0), q, 1);
4218               if (! apply_change_group ())
4219                 return;
4220
4221               /* We now know we'll be doing this change, so emit the
4222                  new insn(s) and do the updates.  */
4223               emit_insns_before (insns, insn);
4224
4225               if (BLOCK_FOR_INSN (insn)->head == insn)
4226                 BLOCK_FOR_INSN (insn)->head = insns;
4227
4228               /* INCR will become a NOTE and INSN won't contain a
4229                  use of ADDR.  If a use of ADDR was just placed in
4230                  the insn before INSN, make that the next use.
4231                  Otherwise, invalidate it.  */
4232               if (GET_CODE (PREV_INSN (insn)) == INSN
4233                   && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
4234                   && SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
4235                 reg_next_use[regno] = PREV_INSN (insn);
4236               else
4237                 reg_next_use[regno] = 0;
4238
4239               addr = q;
4240               regno = REGNO (q);
4241
4242               /* REGNO is now used in INCR which is below INSN, but
4243                  it previously wasn't live here.  If we don't mark
4244                  it as needed, we'll put a REG_DEAD note for it
4245                  on this insn, which is incorrect.  */
4246               SET_REGNO_REG_SET (needed, regno);
4247
4248               /* If there are any calls between INSN and INCR, show
4249                  that REGNO now crosses them.  */
4250               for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
4251                 if (GET_CODE (temp) == CALL_INSN)
4252                   REG_N_CALLS_CROSSED (regno)++;
4253             }
4254           else
4255             return;
4256
4257           /* If we haven't returned, it means we were able to make the
4258              auto-inc, so update the status.  First, record that this insn
4259              has an implicit side effect.  */
4260
4261           REG_NOTES (insn)
4262             = alloc_EXPR_LIST (REG_INC, addr, REG_NOTES (insn));
4263
4264           /* Modify the old increment-insn to simply copy
4265              the already-incremented value of our register.  */
4266           if (! validate_change (incr, &SET_SRC (set), addr, 0))
4267             abort ();
4268
4269           /* If that makes it a no-op (copying the register into itself) delete
4270              it so it won't appear to be a "use" and a "set" of this
4271              register.  */
4272           if (SET_DEST (set) == addr)
4273             {
4274               PUT_CODE (incr, NOTE);
4275               NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
4276               NOTE_SOURCE_FILE (incr) = 0;
4277             }
4278
4279           if (regno >= FIRST_PSEUDO_REGISTER)
4280             {
4281               /* Count an extra reference to the reg.  When a reg is
4282                  incremented, spilling it is worse, so we want to make
4283                  that less likely.  */
4284               REG_N_REFS (regno) += loop_depth + 1;
4285
4286               /* Count the increment as a setting of the register,
4287                  even though it isn't a SET in rtl.  */
4288               REG_N_SETS (regno)++;
4289             }
4290         }
4291     }
4292 }
4293 #endif /* AUTO_INC_DEC */
4294 \f
4295 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
4296    This is done assuming the registers needed from X
4297    are those that have 1-bits in NEEDED.
4298
4299    FLAGS is the set of enabled operations.
4300
4301    INSN is the containing instruction.  If INSN is dead, this function is not
4302    called.  */
4303
4304 static void
4305 mark_used_regs (needed, live, x, flags, insn)
4306      regset needed;
4307      regset live;
4308      rtx x;
4309      int flags;
4310      rtx insn;
4311 {
4312   register RTX_CODE code;
4313   register int regno;
4314   int i;
4315
4316  retry:
4317   code = GET_CODE (x);
4318   switch (code)
4319     {
4320     case LABEL_REF:
4321     case SYMBOL_REF:
4322     case CONST_INT:
4323     case CONST:
4324     case CONST_DOUBLE:
4325     case PC:
4326     case ADDR_VEC:
4327     case ADDR_DIFF_VEC:
4328       return;
4329
4330 #ifdef HAVE_cc0
4331     case CC0:
4332       cc0_live = 1;
4333       return;
4334 #endif
4335
4336     case CLOBBER:
4337       /* If we are clobbering a MEM, mark any registers inside the address
4338          as being used.  */
4339       if (GET_CODE (XEXP (x, 0)) == MEM)
4340         mark_used_regs (needed, live, XEXP (XEXP (x, 0), 0), flags, insn);
4341       return;
4342
4343     case MEM:
4344       /* Don't bother watching stores to mems if this is not the
4345          final pass.  We'll not be deleting dead stores this round.  */
4346       if (flags & PROP_SCAN_DEAD_CODE)
4347         {
4348           /* Invalidate the data for the last MEM stored, but only if MEM is
4349              something that can be stored into.  */
4350           if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
4351               && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
4352             ; /* needn't clear the memory set list */
4353           else
4354             {
4355               rtx temp = mem_set_list;
4356               rtx prev = NULL_RTX;
4357               rtx next;
4358
4359               while (temp)
4360                 {
4361                   next = XEXP (temp, 1);
4362                   if (anti_dependence (XEXP (temp, 0), x))
4363                     {
4364                       /* Splice temp out of the list.  */
4365                       if (prev)
4366                         XEXP (prev, 1) = next;
4367                       else
4368                         mem_set_list = next;
4369                       free_EXPR_LIST_node (temp);
4370                     }
4371                   else
4372                     prev = temp;
4373                   temp = next;
4374                 }
4375             }
4376
4377           /* If the memory reference had embedded side effects (autoincrement
4378              address modes.  Then we may need to kill some entries on the
4379              memory set list.  */
4380           if (insn)
4381             invalidate_mems_from_autoinc (insn);
4382         }
4383
4384 #ifdef AUTO_INC_DEC
4385       if (flags & PROP_AUTOINC)
4386         find_auto_inc (needed, x, insn);
4387 #endif
4388       break;
4389
4390     case SUBREG:
4391       if (GET_CODE (SUBREG_REG (x)) == REG
4392           && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
4393           && (GET_MODE_SIZE (GET_MODE (x))
4394               != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))))
4395         REG_CHANGES_SIZE (REGNO (SUBREG_REG (x))) = 1;
4396
4397       /* While we're here, optimize this case.  */
4398       x = SUBREG_REG (x);
4399
4400       /* In case the SUBREG is not of a register, don't optimize */
4401       if (GET_CODE (x) != REG)
4402         {
4403           mark_used_regs (needed, live, x, flags, insn);
4404           return;
4405         }
4406
4407       /* ... fall through ...  */
4408
4409     case REG:
4410       /* See a register other than being set
4411          => mark it as needed.  */
4412
4413       regno = REGNO (x);
4414       {
4415         int some_needed = REGNO_REG_SET_P (needed, regno);
4416         int some_not_needed = ! some_needed;
4417
4418         SET_REGNO_REG_SET (live, regno);
4419
4420         /* A hard reg in a wide mode may really be multiple registers.
4421            If so, mark all of them just like the first.  */
4422         if (regno < FIRST_PSEUDO_REGISTER)
4423           {
4424             int n;
4425
4426             /* For stack ptr or fixed arg pointer,
4427                nothing below can be necessary, so waste no more time.  */
4428             if (regno == STACK_POINTER_REGNUM
4429 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4430                 || (regno == HARD_FRAME_POINTER_REGNUM
4431                     && (! reload_completed || frame_pointer_needed))
4432 #endif
4433 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4434                 || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4435 #endif
4436                 || (regno == FRAME_POINTER_REGNUM
4437                     && (! reload_completed || frame_pointer_needed)))
4438               {
4439                 /* If this is a register we are going to try to eliminate,
4440                    don't mark it live here.  If we are successful in
4441                    eliminating it, it need not be live unless it is used for
4442                    pseudos, in which case it will have been set live when
4443                    it was allocated to the pseudos.  If the register will not
4444                    be eliminated, reload will set it live at that point.  */
4445
4446                 if (! TEST_HARD_REG_BIT (elim_reg_set, regno))
4447                   regs_ever_live[regno] = 1;
4448                 return;
4449               }
4450             /* No death notes for global register variables;
4451                their values are live after this function exits.  */
4452             if (global_regs[regno])
4453               {
4454                 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4455                   reg_next_use[regno] = insn;
4456                 return;
4457               }
4458
4459             n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4460             while (--n > 0)
4461               {
4462                 int regno_n = regno + n;
4463                 int needed_regno = REGNO_REG_SET_P (needed, regno_n);
4464
4465                 SET_REGNO_REG_SET (live, regno_n);
4466                 some_needed |= needed_regno;
4467                 some_not_needed |= ! needed_regno;
4468               }
4469           }
4470
4471         if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4472           {
4473             /* Record where each reg is used, so when the reg
4474                is set we know the next insn that uses it.  */
4475
4476             reg_next_use[regno] = insn;
4477           }
4478         if (flags & PROP_REG_INFO)
4479           {
4480             if (regno < FIRST_PSEUDO_REGISTER)
4481               {
4482                 /* If a hard reg is being used,
4483                    record that this function does use it.  */
4484
4485                 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
4486                 if (i == 0)
4487                   i = 1;
4488                 do
4489                   regs_ever_live[regno + --i] = 1;
4490                 while (i > 0);
4491               }
4492             else
4493               {
4494                 /* Keep track of which basic block each reg appears in.  */
4495
4496                 register int blocknum = BLOCK_NUM (insn);
4497
4498                 if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
4499                   REG_BASIC_BLOCK (regno) = blocknum;
4500                 else if (REG_BASIC_BLOCK (regno) != blocknum)
4501                   REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
4502
4503                 /* Count (weighted) number of uses of each reg.  */
4504
4505                 REG_N_REFS (regno) += loop_depth + 1;
4506               }
4507           }
4508
4509         /* Record and count the insns in which a reg dies.
4510            If it is used in this insn and was dead below the insn
4511            then it dies in this insn.  If it was set in this insn,
4512            we do not make a REG_DEAD note; likewise if we already
4513            made such a note.  */
4514
4515         if (flags & PROP_DEATH_NOTES)
4516           {
4517             if (some_not_needed
4518                 && ! dead_or_set_p (insn, x)
4519 #if 0
4520                 && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
4521 #endif
4522                 )
4523               {
4524                 /* Check for the case where the register dying partially
4525                    overlaps the register set by this insn.  */
4526                 if (regno < FIRST_PSEUDO_REGISTER
4527                     && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
4528                   {
4529                     int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
4530                     while (--n >= 0)
4531                       some_needed |= dead_or_set_regno_p (insn, regno + n);
4532                   }
4533
4534                 /* If none of the words in X is needed, make a REG_DEAD
4535                    note.  Otherwise, we must make partial REG_DEAD notes.  */
4536                 if (! some_needed)
4537                   {
4538                     REG_NOTES (insn)
4539                       = alloc_EXPR_LIST (REG_DEAD, x, REG_NOTES (insn));
4540                     REG_N_DEATHS (regno)++;
4541                   }
4542                 else
4543                   {
4544                     int i;
4545
4546                     /* Don't make a REG_DEAD note for a part of a register
4547                        that is set in the insn.  */
4548
4549                     for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
4550                          i >= 0; i--)
4551                       if (!REGNO_REG_SET_P (needed, regno + i)
4552                           && ! dead_or_set_regno_p (insn, regno + i))
4553                         REG_NOTES (insn)
4554                           = (alloc_EXPR_LIST
4555                              (REG_DEAD, gen_rtx_REG (reg_raw_mode[regno + i],
4556                                                      regno + i),
4557                               REG_NOTES (insn)));
4558                   }
4559               }
4560           }
4561       }
4562       return;
4563
4564     case SET:
4565       {
4566         register rtx testreg = SET_DEST (x);
4567         int mark_dest = 0;
4568
4569         /* If storing into MEM, don't show it as being used.  But do
4570            show the address as being used.  */
4571         if (GET_CODE (testreg) == MEM)
4572           {
4573 #ifdef AUTO_INC_DEC
4574             if (flags & PROP_AUTOINC)
4575               find_auto_inc (needed, testreg, insn);
4576 #endif
4577             mark_used_regs (needed, live, XEXP (testreg, 0), flags, insn);
4578             mark_used_regs (needed, live, SET_SRC (x), flags, insn);
4579             return;
4580           }
4581
4582         /* Storing in STRICT_LOW_PART is like storing in a reg
4583            in that this SET might be dead, so ignore it in TESTREG.
4584            but in some other ways it is like using the reg.
4585
4586            Storing in a SUBREG or a bit field is like storing the entire
4587            register in that if the register's value is not used
4588            then this SET is not needed.  */
4589         while (GET_CODE (testreg) == STRICT_LOW_PART
4590                || GET_CODE (testreg) == ZERO_EXTRACT
4591                || GET_CODE (testreg) == SIGN_EXTRACT
4592                || GET_CODE (testreg) == SUBREG)
4593           {
4594             if (GET_CODE (testreg) == SUBREG
4595                 && GET_CODE (SUBREG_REG (testreg)) == REG
4596                 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
4597                 && (GET_MODE_SIZE (GET_MODE (testreg))
4598                     != GET_MODE_SIZE (GET_MODE (SUBREG_REG (testreg)))))
4599               REG_CHANGES_SIZE (REGNO (SUBREG_REG (testreg))) = 1;
4600
4601             /* Modifying a single register in an alternate mode
4602                does not use any of the old value.  But these other
4603                ways of storing in a register do use the old value.  */
4604             if (GET_CODE (testreg) == SUBREG
4605                 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
4606               ;
4607             else
4608               mark_dest = 1;
4609
4610             testreg = XEXP (testreg, 0);
4611           }
4612
4613         /* If this is a store into a register,
4614            recursively scan the value being stored.  */
4615
4616         if ((GET_CODE (testreg) == PARALLEL
4617              && GET_MODE (testreg) == BLKmode)
4618             || (GET_CODE (testreg) == REG
4619                 && (regno = REGNO (testreg), ! (regno == FRAME_POINTER_REGNUM
4620                                                 && (! reload_completed || frame_pointer_needed)))
4621 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4622                 && ! (regno == HARD_FRAME_POINTER_REGNUM
4623                       && (! reload_completed || frame_pointer_needed))
4624 #endif
4625 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4626                 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4627 #endif
4628                 ))
4629           /* We used to exclude global_regs here, but that seems wrong.
4630              Storing in them is like storing in mem.  */
4631           {
4632             mark_used_regs (needed, live, SET_SRC (x), flags, insn);
4633             if (mark_dest)
4634               mark_used_regs (needed, live, SET_DEST (x), flags, insn);
4635             return;
4636           }
4637       }
4638       break;
4639
4640     case RETURN:
4641       /* ??? This info should have been gotten from mark_regs_live_at_end,
4642          as applied to the EXIT block, and propagated along the edge that
4643          connects this block to the EXIT.  */
4644       break;
4645
4646     case ASM_OPERANDS:
4647     case UNSPEC_VOLATILE:
4648     case TRAP_IF:
4649     case ASM_INPUT:
4650       {
4651         /* Traditional and volatile asm instructions must be considered to use
4652            and clobber all hard registers, all pseudo-registers and all of
4653            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
4654
4655            Consider for instance a volatile asm that changes the fpu rounding
4656            mode.  An insn should not be moved across this even if it only uses
4657            pseudo-regs because it might give an incorrectly rounded result.
4658
4659            ?!? Unfortunately, marking all hard registers as live causes massive
4660            problems for the register allocator and marking all pseudos as live
4661            creates mountains of uninitialized variable warnings.
4662
4663            So for now, just clear the memory set list and mark any regs
4664            we can find in ASM_OPERANDS as used.  */
4665         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
4666           free_EXPR_LIST_list (&mem_set_list);
4667
4668         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
4669            We can not just fall through here since then we would be confused
4670            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
4671            traditional asms unlike their normal usage.  */
4672         if (code == ASM_OPERANDS)
4673           {
4674             int j;
4675
4676             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
4677               mark_used_regs (needed, live, ASM_OPERANDS_INPUT (x, j),
4678                               flags, insn);
4679           }
4680         break;
4681       }
4682
4683
4684     default:
4685       break;
4686     }
4687
4688   /* Recursively scan the operands of this expression.  */
4689
4690   {
4691     register const char *fmt = GET_RTX_FORMAT (code);
4692     register int i;
4693
4694     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4695       {
4696         if (fmt[i] == 'e')
4697           {
4698             /* Tail recursive case: save a function call level.  */
4699             if (i == 0)
4700               {
4701                 x = XEXP (x, 0);
4702                 goto retry;
4703               }
4704             mark_used_regs (needed, live, XEXP (x, i), flags, insn);
4705           }
4706         else if (fmt[i] == 'E')
4707           {
4708             register int j;
4709             for (j = 0; j < XVECLEN (x, i); j++)
4710               mark_used_regs (needed, live, XVECEXP (x, i, j), flags, insn);
4711           }
4712       }
4713   }
4714 }
4715 \f
4716 #ifdef AUTO_INC_DEC
4717
4718 static int
4719 try_pre_increment_1 (insn)
4720      rtx insn;
4721 {
4722   /* Find the next use of this reg.  If in same basic block,
4723      make it do pre-increment or pre-decrement if appropriate.  */
4724   rtx x = single_set (insn);
4725   HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
4726                 * INTVAL (XEXP (SET_SRC (x), 1)));
4727   int regno = REGNO (SET_DEST (x));
4728   rtx y = reg_next_use[regno];
4729   if (y != 0
4730       && BLOCK_NUM (y) == BLOCK_NUM (insn)
4731       /* Don't do this if the reg dies, or gets set in y; a standard addressing
4732          mode would be better.  */
4733       && ! dead_or_set_p (y, SET_DEST (x))
4734       && try_pre_increment (y, SET_DEST (x), amount))
4735     {
4736       /* We have found a suitable auto-increment
4737          and already changed insn Y to do it.
4738          So flush this increment-instruction.  */
4739       PUT_CODE (insn, NOTE);
4740       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4741       NOTE_SOURCE_FILE (insn) = 0;
4742       /* Count a reference to this reg for the increment
4743          insn we are deleting.  When a reg is incremented.
4744          spilling it is worse, so we want to make that
4745          less likely.  */
4746       if (regno >= FIRST_PSEUDO_REGISTER)
4747         {
4748           REG_N_REFS (regno) += loop_depth + 1;
4749           REG_N_SETS (regno)++;
4750         }
4751       return 1;
4752     }
4753   return 0;
4754 }
4755
4756 /* Try to change INSN so that it does pre-increment or pre-decrement
4757    addressing on register REG in order to add AMOUNT to REG.
4758    AMOUNT is negative for pre-decrement.
4759    Returns 1 if the change could be made.
4760    This checks all about the validity of the result of modifying INSN.  */
4761
4762 static int
4763 try_pre_increment (insn, reg, amount)
4764      rtx insn, reg;
4765      HOST_WIDE_INT amount;
4766 {
4767   register rtx use;
4768
4769   /* Nonzero if we can try to make a pre-increment or pre-decrement.
4770      For example, addl $4,r1; movl (r1),... can become movl +(r1),...  */
4771   int pre_ok = 0;
4772   /* Nonzero if we can try to make a post-increment or post-decrement.
4773      For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
4774      It is possible for both PRE_OK and POST_OK to be nonzero if the machine
4775      supports both pre-inc and post-inc, or both pre-dec and post-dec.  */
4776   int post_ok = 0;
4777
4778   /* Nonzero if the opportunity actually requires post-inc or post-dec.  */
4779   int do_post = 0;
4780
4781   /* From the sign of increment, see which possibilities are conceivable
4782      on this target machine.  */
4783   if (HAVE_PRE_INCREMENT && amount > 0)
4784     pre_ok = 1;
4785   if (HAVE_POST_INCREMENT && amount > 0)
4786     post_ok = 1;
4787
4788   if (HAVE_PRE_DECREMENT && amount < 0)
4789     pre_ok = 1;
4790   if (HAVE_POST_DECREMENT && amount < 0)
4791     post_ok = 1;
4792
4793   if (! (pre_ok || post_ok))
4794     return 0;
4795
4796   /* It is not safe to add a side effect to a jump insn
4797      because if the incremented register is spilled and must be reloaded
4798      there would be no way to store the incremented value back in memory.  */
4799
4800   if (GET_CODE (insn) == JUMP_INSN)
4801     return 0;
4802
4803   use = 0;
4804   if (pre_ok)
4805     use = find_use_as_address (PATTERN (insn), reg, 0);
4806   if (post_ok && (use == 0 || use == (rtx) 1))
4807     {
4808       use = find_use_as_address (PATTERN (insn), reg, -amount);
4809       do_post = 1;
4810     }
4811
4812   if (use == 0 || use == (rtx) 1)
4813     return 0;
4814
4815   if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
4816     return 0;
4817
4818   /* See if this combination of instruction and addressing mode exists.  */
4819   if (! validate_change (insn, &XEXP (use, 0),
4820                          gen_rtx_fmt_e (amount > 0
4821                                         ? (do_post ? POST_INC : PRE_INC)
4822                                         : (do_post ? POST_DEC : PRE_DEC),
4823                                         Pmode, reg), 0))
4824     return 0;
4825
4826   /* Record that this insn now has an implicit side effect on X.  */
4827   REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
4828   return 1;
4829 }
4830
4831 #endif /* AUTO_INC_DEC */
4832 \f
4833 /* Find the place in the rtx X where REG is used as a memory address.
4834    Return the MEM rtx that so uses it.
4835    If PLUSCONST is nonzero, search instead for a memory address equivalent to
4836    (plus REG (const_int PLUSCONST)).
4837
4838    If such an address does not appear, return 0.
4839    If REG appears more than once, or is used other than in such an address,
4840    return (rtx)1.  */
4841
4842 rtx
4843 find_use_as_address (x, reg, plusconst)
4844      register rtx x;
4845      rtx reg;
4846      HOST_WIDE_INT plusconst;
4847 {
4848   enum rtx_code code = GET_CODE (x);
4849   const char *fmt = GET_RTX_FORMAT (code);
4850   register int i;
4851   register rtx value = 0;
4852   register rtx tem;
4853
4854   if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
4855     return x;
4856
4857   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
4858       && XEXP (XEXP (x, 0), 0) == reg
4859       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
4860       && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
4861     return x;
4862
4863   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4864     {
4865       /* If REG occurs inside a MEM used in a bit-field reference,
4866          that is unacceptable.  */
4867       if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
4868         return (rtx) (HOST_WIDE_INT) 1;
4869     }
4870
4871   if (x == reg)
4872     return (rtx) (HOST_WIDE_INT) 1;
4873
4874   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4875     {
4876       if (fmt[i] == 'e')
4877         {
4878           tem = find_use_as_address (XEXP (x, i), reg, plusconst);
4879           if (value == 0)
4880             value = tem;
4881           else if (tem != 0)
4882             return (rtx) (HOST_WIDE_INT) 1;
4883         }
4884       else if (fmt[i] == 'E')
4885         {
4886           register int j;
4887           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4888             {
4889               tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
4890               if (value == 0)
4891                 value = tem;
4892               else if (tem != 0)
4893                 return (rtx) (HOST_WIDE_INT) 1;
4894             }
4895         }
4896     }
4897
4898   return value;
4899 }
4900 \f
4901 /* Write information about registers and basic blocks into FILE.
4902    This is part of making a debugging dump.  */
4903
4904 void
4905 dump_flow_info (file)
4906      FILE *file;
4907 {
4908   register int i;
4909   static const char * const reg_class_names[] = REG_CLASS_NAMES;
4910
4911   fprintf (file, "%d registers.\n", max_regno);
4912   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
4913     if (REG_N_REFS (i))
4914       {
4915         enum reg_class class, altclass;
4916         fprintf (file, "\nRegister %d used %d times across %d insns",
4917                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
4918         if (REG_BASIC_BLOCK (i) >= 0)
4919           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
4920         if (REG_N_SETS (i))
4921           fprintf (file, "; set %d time%s", REG_N_SETS (i),
4922                    (REG_N_SETS (i) == 1) ? "" : "s");
4923         if (REG_USERVAR_P (regno_reg_rtx[i]))
4924           fprintf (file, "; user var");
4925         if (REG_N_DEATHS (i) != 1)
4926           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
4927         if (REG_N_CALLS_CROSSED (i) == 1)
4928           fprintf (file, "; crosses 1 call");
4929         else if (REG_N_CALLS_CROSSED (i))
4930           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
4931         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
4932           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
4933         class = reg_preferred_class (i);
4934         altclass = reg_alternate_class (i);
4935         if (class != GENERAL_REGS || altclass != ALL_REGS)
4936           {
4937             if (altclass == ALL_REGS || class == ALL_REGS)
4938               fprintf (file, "; pref %s", reg_class_names[(int) class]);
4939             else if (altclass == NO_REGS)
4940               fprintf (file, "; %s or none", reg_class_names[(int) class]);
4941             else
4942               fprintf (file, "; pref %s, else %s",
4943                        reg_class_names[(int) class],
4944                        reg_class_names[(int) altclass]);
4945           }
4946         if (REGNO_POINTER_FLAG (i))
4947           fprintf (file, "; pointer");
4948         fprintf (file, ".\n");
4949       }
4950
4951   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
4952   for (i = 0; i < n_basic_blocks; i++)
4953     {
4954       register basic_block bb = BASIC_BLOCK (i);
4955       register int regno;
4956       register edge e;
4957
4958       fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d.\n",
4959                i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth);
4960
4961       fprintf (file, "Predecessors: ");
4962       for (e = bb->pred; e ; e = e->pred_next)
4963         dump_edge_info (file, e, 0);
4964
4965       fprintf (file, "\nSuccessors: ");
4966       for (e = bb->succ; e ; e = e->succ_next)
4967         dump_edge_info (file, e, 1);
4968
4969       fprintf (file, "\nRegisters live at start:");
4970       if (bb->global_live_at_start)
4971         {
4972           for (regno = 0; regno < max_regno; regno++)
4973             if (REGNO_REG_SET_P (bb->global_live_at_start, regno))
4974               fprintf (file, " %d", regno);
4975         }
4976       else
4977         fprintf (file, " n/a");
4978
4979       fprintf (file, "\nRegisters live at end:");
4980       if (bb->global_live_at_end)
4981         {
4982           for (regno = 0; regno < max_regno; regno++)
4983             if (REGNO_REG_SET_P (bb->global_live_at_end, regno))
4984               fprintf (file, " %d", regno);
4985         }
4986       else
4987         fprintf (file, " n/a");
4988
4989       putc('\n', file);
4990     }
4991
4992   putc('\n', file);
4993 }
4994
4995 void
4996 debug_flow_info ()
4997 {
4998   dump_flow_info (stderr);
4999 }
5000
5001 static void
5002 dump_edge_info (file, e, do_succ)
5003      FILE *file;
5004      edge e;
5005      int do_succ;
5006 {
5007   basic_block side = (do_succ ? e->dest : e->src);
5008
5009   if (side == ENTRY_BLOCK_PTR)
5010     fputs (" ENTRY", file);
5011   else if (side == EXIT_BLOCK_PTR)
5012     fputs (" EXIT", file);
5013   else
5014     fprintf (file, " %d", side->index);
5015
5016   if (e->flags)
5017     {
5018       static const char * const bitnames[] = {
5019         "fallthru", "crit", "ab", "abcall", "eh", "fake"
5020       };
5021       int comma = 0;
5022       int i, flags = e->flags;
5023
5024       fputc (' ', file);
5025       fputc ('(', file);
5026       for (i = 0; flags; i++)
5027         if (flags & (1 << i))
5028           {
5029             flags &= ~(1 << i);
5030
5031             if (comma)
5032               fputc (',', file);
5033             if (i < (int)(sizeof (bitnames) / sizeof (*bitnames)))
5034               fputs (bitnames[i], file);
5035             else
5036               fprintf (file, "%d", i);
5037             comma = 1;
5038           }
5039       fputc (')', file);
5040     }
5041 }
5042
5043 \f
5044 /* Like print_rtl, but also print out live information for the start of each
5045    basic block.  */
5046
5047 void
5048 print_rtl_with_bb (outf, rtx_first)
5049      FILE *outf;
5050      rtx rtx_first;
5051 {
5052   register rtx tmp_rtx;
5053
5054   if (rtx_first == 0)
5055     fprintf (outf, "(nil)\n");
5056   else
5057     {
5058       int i;
5059       enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
5060       int max_uid = get_max_uid ();
5061       basic_block *start = (basic_block *)
5062         xcalloc (max_uid, sizeof (basic_block));
5063       basic_block *end = (basic_block *)
5064         xcalloc (max_uid, sizeof (basic_block));
5065       enum bb_state *in_bb_p = (enum bb_state *)
5066         xcalloc (max_uid, sizeof (enum bb_state));
5067
5068       for (i = n_basic_blocks - 1; i >= 0; i--)
5069         {
5070           basic_block bb = BASIC_BLOCK (i);
5071           rtx x;
5072
5073           start[INSN_UID (bb->head)] = bb;
5074           end[INSN_UID (bb->end)] = bb;
5075           for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
5076             {
5077               enum bb_state state = IN_MULTIPLE_BB;
5078               if (in_bb_p[INSN_UID(x)] == NOT_IN_BB)
5079                 state = IN_ONE_BB;
5080               in_bb_p[INSN_UID(x)] = state;
5081
5082               if (x == bb->end)
5083                 break;
5084             }
5085         }
5086
5087       for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
5088         {
5089           int did_output;
5090           basic_block bb;
5091
5092           if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
5093             {
5094               fprintf (outf, ";; Start of basic block %d, registers live:",
5095                        bb->index);
5096
5097               EXECUTE_IF_SET_IN_REG_SET (bb->global_live_at_start, 0, i,
5098                                          {
5099                                            fprintf (outf, " %d", i);
5100                                            if (i < FIRST_PSEUDO_REGISTER)
5101                                              fprintf (outf, " [%s]",
5102                                                       reg_names[i]);
5103                                          });
5104               putc ('\n', outf);
5105             }
5106
5107           if (in_bb_p[INSN_UID(tmp_rtx)] == NOT_IN_BB
5108               && GET_CODE (tmp_rtx) != NOTE
5109               && GET_CODE (tmp_rtx) != BARRIER
5110               && ! obey_regdecls)
5111             fprintf (outf, ";; Insn is not within a basic block\n");
5112           else if (in_bb_p[INSN_UID(tmp_rtx)] == IN_MULTIPLE_BB)
5113             fprintf (outf, ";; Insn is in multiple basic blocks\n");
5114
5115           did_output = print_rtl_single (outf, tmp_rtx);
5116
5117           if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
5118             fprintf (outf, ";; End of basic block %d\n", bb->index);
5119
5120           if (did_output)
5121             putc ('\n', outf);
5122         }
5123
5124       free (start);
5125       free (end);
5126       free (in_bb_p);
5127     }
5128
5129   if (current_function_epilogue_delay_list != 0)
5130     {
5131       fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
5132       for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
5133            tmp_rtx = XEXP (tmp_rtx, 1))
5134         print_rtl_single (outf, XEXP (tmp_rtx, 0));
5135     }
5136 }
5137
5138 /* Compute dominator relationships using new flow graph structures.  */
5139 void
5140 compute_flow_dominators (dominators, post_dominators)
5141      sbitmap *dominators;
5142      sbitmap *post_dominators;
5143 {
5144   int bb;
5145   sbitmap *temp_bitmap;
5146   edge e;
5147   basic_block *worklist, *tos;
5148
5149   /* Allocate a worklist array/queue.  Entries are only added to the
5150      list if they were not already on the list.  So the size is
5151      bounded by the number of basic blocks.  */
5152   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
5153                     * n_basic_blocks);
5154
5155   temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
5156   sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
5157
5158   if (dominators)
5159     {
5160       /* The optimistic setting of dominators requires us to put every
5161          block on the work list initially.  */
5162       for (bb = 0; bb < n_basic_blocks; bb++)
5163         {
5164           *tos++ = BASIC_BLOCK (bb);
5165           BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
5166         }
5167
5168       /* We want a maximal solution, so initially assume everything dominates
5169          everything else.  */
5170       sbitmap_vector_ones (dominators, n_basic_blocks);
5171
5172       /* Mark successors of the entry block so we can identify them below.  */
5173       for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
5174         e->dest->aux = ENTRY_BLOCK_PTR;
5175
5176       /* Iterate until the worklist is empty.  */
5177       while (tos != worklist)
5178         {
5179           /* Take the first entry off the worklist.  */
5180           basic_block b = *--tos;
5181           bb = b->index;
5182
5183           /* Compute the intersection of the dominators of all the
5184              predecessor blocks.
5185
5186              If one of the predecessor blocks is the ENTRY block, then the
5187              intersection of the dominators of the predecessor blocks is
5188              defined as the null set.  We can identify such blocks by the
5189              special value in the AUX field in the block structure.  */
5190           if (b->aux == ENTRY_BLOCK_PTR)
5191             {
5192               /* Do not clear the aux field for blocks which are
5193                  successors of the ENTRY block.  That way we we never
5194                  add them to the worklist again.
5195
5196                  The intersect of dominators of the preds of this block is
5197                  defined as the null set.  */
5198               sbitmap_zero (temp_bitmap[bb]);
5199             }
5200           else
5201             {
5202               /* Clear the aux field of this block so it can be added to
5203                  the worklist again if necessary.  */
5204               b->aux = NULL;
5205               sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
5206             }
5207
5208           /* Make sure each block always dominates itself.  */
5209           SET_BIT (temp_bitmap[bb], bb);
5210
5211           /* If the out state of this block changed, then we need to
5212              add the successors of this block to the worklist if they
5213              are not already on the worklist.  */
5214           if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
5215             {
5216               for (e = b->succ; e; e = e->succ_next)
5217                 {
5218                   if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
5219                     {
5220                       *tos++ = e->dest;
5221                       e->dest->aux = e;
5222                     }
5223                 }
5224             }
5225         }
5226     }
5227
5228   if (post_dominators)
5229     {
5230       /* The optimistic setting of dominators requires us to put every
5231          block on the work list initially.  */
5232       for (bb = 0; bb < n_basic_blocks; bb++)
5233         {
5234           *tos++ = BASIC_BLOCK (bb);
5235           BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
5236         }
5237
5238       /* We want a maximal solution, so initially assume everything post
5239          dominates everything else.  */
5240       sbitmap_vector_ones (post_dominators, n_basic_blocks);
5241
5242       /* Mark predecessors of the exit block so we can identify them below.  */
5243       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
5244         e->src->aux = EXIT_BLOCK_PTR;
5245
5246       /* Iterate until the worklist is empty.  */
5247       while (tos != worklist)
5248         {
5249           /* Take the first entry off the worklist.  */
5250           basic_block b = *--tos;
5251           bb = b->index;
5252
5253           /* Compute the intersection of the post dominators of all the
5254              successor blocks.
5255
5256              If one of the successor blocks is the EXIT block, then the
5257              intersection of the dominators of the successor blocks is
5258              defined as the null set.  We can identify such blocks by the
5259              special value in the AUX field in the block structure.  */
5260           if (b->aux == EXIT_BLOCK_PTR)
5261             {
5262               /* Do not clear the aux field for blocks which are
5263                  predecessors of the EXIT block.  That way we we never
5264                  add them to the worklist again.
5265
5266                  The intersect of dominators of the succs of this block is
5267                  defined as the null set.  */
5268               sbitmap_zero (temp_bitmap[bb]);
5269             }
5270           else
5271             {
5272               /* Clear the aux field of this block so it can be added to
5273                  the worklist again if necessary.  */
5274               b->aux = NULL;
5275               sbitmap_intersection_of_succs (temp_bitmap[bb],
5276                                              post_dominators, bb);
5277             }
5278
5279           /* Make sure each block always post dominates itself.  */
5280           SET_BIT (temp_bitmap[bb], bb);
5281
5282           /* If the out state of this block changed, then we need to
5283              add the successors of this block to the worklist if they
5284              are not already on the worklist.  */
5285           if (sbitmap_a_and_b (post_dominators[bb],
5286                                post_dominators[bb],
5287                                temp_bitmap[bb]))
5288             {
5289               for (e = b->pred; e; e = e->pred_next)
5290                 {
5291                   if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
5292                     {
5293                       *tos++ = e->src;
5294                       e->src->aux = e;
5295                     }
5296                 }
5297             }
5298         }
5299     }
5300   free (temp_bitmap);
5301 }
5302
5303 /* Given DOMINATORS, compute the immediate dominators into IDOM.  */
5304
5305 void
5306 compute_immediate_dominators (idom, dominators)
5307      int *idom;
5308      sbitmap *dominators;
5309 {
5310   sbitmap *tmp;
5311   int b;
5312
5313   tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
5314
5315   /* Begin with tmp(n) = dom(n) - { n }.  */
5316   for (b = n_basic_blocks; --b >= 0; )
5317     {
5318       sbitmap_copy (tmp[b], dominators[b]);
5319       RESET_BIT (tmp[b], b);
5320     }
5321
5322   /* Subtract out all of our dominator's dominators.  */
5323   for (b = n_basic_blocks; --b >= 0; )
5324     {
5325       sbitmap tmp_b = tmp[b];
5326       int s;
5327
5328       for (s = n_basic_blocks; --s >= 0; )
5329         if (TEST_BIT (tmp_b, s))
5330           sbitmap_difference (tmp_b, tmp_b, tmp[s]);
5331     }
5332
5333   /* Find the one bit set in the bitmap and put it in the output array.  */
5334   for (b = n_basic_blocks; --b >= 0; )
5335     {
5336       int t;
5337       EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
5338     }
5339
5340   sbitmap_vector_free (tmp);
5341 }
5342
5343 /* Count for a single SET rtx, X.  */
5344
5345 static void
5346 count_reg_sets_1 (x)
5347      rtx x;
5348 {
5349   register int regno;
5350   register rtx reg = SET_DEST (x);
5351
5352   /* Find the register that's set/clobbered.  */
5353   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
5354          || GET_CODE (reg) == SIGN_EXTRACT
5355          || GET_CODE (reg) == STRICT_LOW_PART)
5356     reg = XEXP (reg, 0);
5357
5358   if (GET_CODE (reg) == PARALLEL
5359       && GET_MODE (reg) == BLKmode)
5360     {
5361       register int i;
5362       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
5363         count_reg_sets_1 (XVECEXP (reg, 0, i));
5364       return;
5365     }
5366
5367   if (GET_CODE (reg) == REG)
5368     {
5369       regno = REGNO (reg);
5370       if (regno >= FIRST_PSEUDO_REGISTER)
5371         {
5372           /* Count (weighted) references, stores, etc.  This counts a
5373              register twice if it is modified, but that is correct.  */
5374           REG_N_SETS (regno)++;
5375           REG_N_REFS (regno) += loop_depth + 1;
5376         }
5377     }
5378 }
5379
5380 /* Increment REG_N_SETS for each SET or CLOBBER found in X; also increment
5381    REG_N_REFS by the current loop depth for each SET or CLOBBER found.  */
5382
5383 static void
5384 count_reg_sets  (x)
5385      rtx x;
5386 {
5387   register RTX_CODE code = GET_CODE (x);
5388
5389   if (code == SET || code == CLOBBER)
5390     count_reg_sets_1 (x);
5391   else if (code == PARALLEL)
5392     {
5393       register int i;
5394       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
5395         {
5396           code = GET_CODE (XVECEXP (x, 0, i));
5397           if (code == SET || code == CLOBBER)
5398             count_reg_sets_1 (XVECEXP (x, 0, i));
5399         }
5400     }
5401 }
5402
5403 /* Increment REG_N_REFS by the current loop depth each register reference
5404    found in X.  */
5405
5406 static void
5407 count_reg_references (x)
5408      rtx x;
5409 {
5410   register RTX_CODE code;
5411
5412  retry:
5413   code = GET_CODE (x);
5414   switch (code)
5415     {
5416     case LABEL_REF:
5417     case SYMBOL_REF:
5418     case CONST_INT:
5419     case CONST:
5420     case CONST_DOUBLE:
5421     case PC:
5422     case ADDR_VEC:
5423     case ADDR_DIFF_VEC:
5424     case ASM_INPUT:
5425       return;
5426
5427 #ifdef HAVE_cc0
5428     case CC0:
5429       return;
5430 #endif
5431
5432     case CLOBBER:
5433       /* If we are clobbering a MEM, mark any registers inside the address
5434          as being used.  */
5435       if (GET_CODE (XEXP (x, 0)) == MEM)
5436         count_reg_references (XEXP (XEXP (x, 0), 0));
5437       return;
5438
5439     case SUBREG:
5440       /* While we're here, optimize this case.  */
5441       x = SUBREG_REG (x);
5442
5443       /* In case the SUBREG is not of a register, don't optimize */
5444       if (GET_CODE (x) != REG)
5445         {
5446           count_reg_references (x);
5447           return;
5448         }
5449
5450       /* ... fall through ...  */
5451
5452     case REG:
5453       if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
5454         REG_N_REFS (REGNO (x)) += loop_depth + 1;
5455       return;
5456
5457     case SET:
5458       {
5459         register rtx testreg = SET_DEST (x);
5460         int mark_dest = 0;
5461
5462         /* If storing into MEM, don't show it as being used.  But do
5463            show the address as being used.  */
5464         if (GET_CODE (testreg) == MEM)
5465           {
5466             count_reg_references (XEXP (testreg, 0));
5467             count_reg_references (SET_SRC (x));
5468             return;
5469           }
5470
5471         /* Storing in STRICT_LOW_PART is like storing in a reg
5472            in that this SET might be dead, so ignore it in TESTREG.
5473            but in some other ways it is like using the reg.
5474
5475            Storing in a SUBREG or a bit field is like storing the entire
5476            register in that if the register's value is not used
5477            then this SET is not needed.  */
5478         while (GET_CODE (testreg) == STRICT_LOW_PART
5479                || GET_CODE (testreg) == ZERO_EXTRACT
5480                || GET_CODE (testreg) == SIGN_EXTRACT
5481                || GET_CODE (testreg) == SUBREG)
5482           {
5483             /* Modifying a single register in an alternate mode
5484                does not use any of the old value.  But these other
5485                ways of storing in a register do use the old value.  */
5486             if (GET_CODE (testreg) == SUBREG
5487                 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
5488               ;
5489             else
5490               mark_dest = 1;
5491
5492             testreg = XEXP (testreg, 0);
5493           }
5494
5495         /* If this is a store into a register,
5496            recursively scan the value being stored.  */
5497
5498         if ((GET_CODE (testreg) == PARALLEL
5499              && GET_MODE (testreg) == BLKmode)
5500             || GET_CODE (testreg) == REG)
5501           {
5502             count_reg_references (SET_SRC (x));
5503             if (mark_dest)
5504               count_reg_references (SET_DEST (x));
5505             return;
5506           }
5507       }
5508       break;
5509
5510     default:
5511       break;
5512     }
5513
5514   /* Recursively scan the operands of this expression.  */
5515
5516   {
5517     register const char *fmt = GET_RTX_FORMAT (code);
5518     register int i;
5519
5520     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5521       {
5522         if (fmt[i] == 'e')
5523           {
5524             /* Tail recursive case: save a function call level.  */
5525             if (i == 0)
5526               {
5527                 x = XEXP (x, 0);
5528                 goto retry;
5529               }
5530             count_reg_references (XEXP (x, i));
5531           }
5532         else if (fmt[i] == 'E')
5533           {
5534             register int j;
5535             for (j = 0; j < XVECLEN (x, i); j++)
5536               count_reg_references (XVECEXP (x, i, j));
5537           }
5538       }
5539   }
5540 }
5541
5542 /* Recompute register set/reference counts immediately prior to register
5543    allocation.
5544
5545    This avoids problems with set/reference counts changing to/from values
5546    which have special meanings to the register allocators.
5547
5548    Additionally, the reference counts are the primary component used by the
5549    register allocators to prioritize pseudos for allocation to hard regs.
5550    More accurate reference counts generally lead to better register allocation.
5551
5552    F is the first insn to be scanned.
5553
5554    LOOP_STEP denotes how much loop_depth should be incremented per
5555    loop nesting level in order to increase the ref count more for
5556    references in a loop.
5557
5558    It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
5559    possibly other information which is used by the register allocators.  */
5560
5561 void
5562 recompute_reg_usage (f, loop_step)
5563      rtx f ATTRIBUTE_UNUSED;
5564      int loop_step ATTRIBUTE_UNUSED;
5565 {
5566   rtx insn;
5567   int i, max_reg;
5568   int index;
5569
5570   /* Clear out the old data.  */
5571   max_reg = max_reg_num ();
5572   for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
5573     {
5574       REG_N_SETS (i) = 0;
5575       REG_N_REFS (i) = 0;
5576     }
5577
5578   /* Scan each insn in the chain and count how many times each register is
5579      set/used.  */
5580   for (index = 0; index < n_basic_blocks; index++)
5581     {
5582       basic_block bb = BASIC_BLOCK (index);
5583       loop_depth = bb->loop_depth;
5584       for (insn = bb->head; insn; insn = NEXT_INSN (insn))
5585         {
5586           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5587             {
5588               rtx links;
5589
5590               /* This call will increment REG_N_SETS for each SET or CLOBBER
5591                  of a register in INSN.  It will also increment REG_N_REFS
5592                  by the loop depth for each set of a register in INSN.  */
5593               count_reg_sets (PATTERN (insn));
5594
5595               /* count_reg_sets does not detect autoincrement address modes, so
5596                  detect them here by looking at the notes attached to INSN.  */
5597               for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
5598                 {
5599                   if (REG_NOTE_KIND (links) == REG_INC)
5600                     /* Count (weighted) references, stores, etc.  This counts a
5601                        register twice if it is modified, but that is correct.  */
5602                     REG_N_SETS (REGNO (XEXP (links, 0)))++;
5603                 }
5604
5605               /* This call will increment REG_N_REFS by the current loop depth for
5606                  each reference to a register in INSN.  */
5607               count_reg_references (PATTERN (insn));
5608
5609               /* count_reg_references will not include counts for arguments to
5610                  function calls, so detect them here by examining the
5611                  CALL_INSN_FUNCTION_USAGE data.  */
5612               if (GET_CODE (insn) == CALL_INSN)
5613                 {
5614                   rtx note;
5615
5616                   for (note = CALL_INSN_FUNCTION_USAGE (insn);
5617                        note;
5618                        note = XEXP (note, 1))
5619                     if (GET_CODE (XEXP (note, 0)) == USE)
5620                       count_reg_references (XEXP (XEXP (note, 0), 0));
5621                 }
5622             }
5623           if (insn == bb->end)
5624             break;
5625         }
5626     }
5627 }
5628
5629 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
5630    blocks.  If BLOCKS is NULL, assume the universal set.  Returns a count
5631    of the number of registers that died.  */
5632
5633 int
5634 count_or_remove_death_notes (blocks, kill)
5635     sbitmap blocks;
5636     int kill;
5637 {
5638   int i, count = 0;
5639
5640   for (i = n_basic_blocks - 1; i >= 0; --i)
5641     {
5642       basic_block bb;
5643       rtx insn;
5644
5645       if (blocks && ! TEST_BIT (blocks, i))
5646         continue;
5647
5648       bb = BASIC_BLOCK (i);
5649
5650       for (insn = bb->head; ; insn = NEXT_INSN (insn))
5651         {
5652           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
5653             {
5654               rtx *pprev = &REG_NOTES (insn);
5655               rtx link = *pprev;
5656
5657               while (link)
5658                 {
5659                   switch (REG_NOTE_KIND (link))
5660                     {
5661                     case REG_DEAD:
5662                       if (GET_CODE (XEXP (link, 0)) == REG)
5663                         {
5664                           rtx reg = XEXP (link, 0);
5665                           int n;
5666
5667                           if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
5668                             n = 1;
5669                           else
5670                             n = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
5671                           count += n;
5672                         }
5673                       /* FALLTHRU */
5674
5675                     case REG_UNUSED:
5676                       if (kill)
5677                         {
5678                           rtx next = XEXP (link, 1);
5679                           free_EXPR_LIST_node (link);
5680                           *pprev = link = next;
5681                           break;
5682                         }
5683                       /* FALLTHRU */
5684
5685                     default:
5686                       pprev = &XEXP (link, 1);
5687                       link = *pprev;
5688                       break;
5689                     }
5690                 }
5691             }
5692
5693           if (insn == bb->end)
5694             break;
5695         }
5696     }
5697
5698   return count;
5699 }
5700
5701 /* Record INSN's block as BB.  */
5702
5703 void
5704 set_block_for_insn (insn, bb)
5705      rtx insn;
5706      basic_block bb;
5707 {
5708   size_t uid = INSN_UID (insn);
5709   if (uid >= basic_block_for_insn->num_elements)
5710     {
5711       int new_size;
5712
5713       /* Add one-eighth the size so we don't keep calling xrealloc.  */
5714       new_size = uid + (uid + 7) / 8;
5715
5716       VARRAY_GROW (basic_block_for_insn, new_size);
5717     }
5718   VARRAY_BB (basic_block_for_insn, uid) = bb;
5719 }
5720
5721 /* Record INSN's block number as BB.  */
5722 /* ??? This has got to go.  */
5723
5724 void
5725 set_block_num (insn, bb)
5726      rtx insn;
5727      int bb;
5728 {
5729   set_block_for_insn (insn, BASIC_BLOCK (bb));
5730 }
5731 \f
5732 /* Verify the CFG consistency.  This function check some CFG invariants and
5733    aborts when something is wrong.  Hope that this function will help to
5734    convert many optimization passes to preserve CFG consistent.
5735
5736    Currently it does following checks:
5737
5738    - test head/end pointers
5739    - overlapping of basic blocks
5740    - edge list corectness
5741    - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
5742    - tails of basic blocks (ensure that boundary is necesary)
5743    - scans body of the basic block for JUMP_INSN, CODE_LABEL
5744      and NOTE_INSN_BASIC_BLOCK
5745    - check that all insns are in the basic blocks
5746    (except the switch handling code, barriers and notes)
5747
5748    In future it can be extended check a lot of other stuff as well
5749    (reachability of basic blocks, life information, etc. etc.).  */
5750
5751 void
5752 verify_flow_info ()
5753 {
5754   const int max_uid = get_max_uid ();
5755   const rtx rtx_first = get_insns ();
5756   basic_block *bb_info;
5757   rtx x;
5758   int i, err = 0;
5759
5760   bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
5761
5762   /* First pass check head/end pointers and set bb_info array used by
5763      later passes.  */
5764   for (i = n_basic_blocks - 1; i >= 0; i--)
5765     {
5766       basic_block bb = BASIC_BLOCK (i);
5767
5768       /* Check the head pointer and make sure that it is pointing into
5769          insn list.  */
5770       for (x = rtx_first; x != NULL_RTX; x = NEXT_INSN (x))
5771         if (x == bb->head)
5772           break;
5773       if (!x)
5774         {
5775           error ("Head insn %d for block %d not found in the insn stream.",
5776                  INSN_UID (bb->head), bb->index);
5777           err = 1;
5778         }
5779
5780       /* Check the end pointer and make sure that it is pointing into
5781          insn list.  */
5782       for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
5783         {
5784           if (bb_info[INSN_UID (x)] != NULL)
5785             {
5786               error ("Insn %d is in multiple basic blocks (%d and %d)",
5787                      INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
5788               err = 1;
5789             }
5790           bb_info[INSN_UID (x)] = bb;
5791
5792           if (x == bb->end)
5793             break;
5794         }
5795       if (!x)
5796         {
5797           error ("End insn %d for block %d not found in the insn stream.",
5798                  INSN_UID (bb->end), bb->index);
5799           err = 1;
5800         }
5801     }
5802
5803   /* Now check the basic blocks (boundaries etc.) */
5804   for (i = n_basic_blocks - 1; i >= 0; i--)
5805     {
5806       basic_block bb = BASIC_BLOCK (i);
5807       /* Check corectness of edge lists */
5808       edge e;
5809
5810       e = bb->succ;
5811       while (e)
5812         {
5813           if (e->src != bb)
5814             {
5815               fprintf (stderr, "verify_flow_info: Basic block %d succ edge is corrupted\n",
5816                        bb->index);
5817               fprintf (stderr, "Predecessor: ");
5818               dump_edge_info (stderr, e, 0);
5819               fprintf (stderr, "\nSuccessor: ");
5820               dump_edge_info (stderr, e, 1);
5821               fflush (stderr);
5822               err = 1;
5823             }
5824           if (e->dest != EXIT_BLOCK_PTR)
5825             {
5826               edge e2 = e->dest->pred;
5827               while (e2 && e2 != e)
5828                 e2 = e2->pred_next;
5829               if (!e2)
5830                 {
5831                   error ("Basic block %i edge lists are corrupted", bb->index);
5832                   err = 1;
5833                 }
5834             }
5835           e = e->succ_next;
5836         }
5837
5838       e = bb->pred;
5839       while (e)
5840         {
5841           if (e->dest != bb)
5842             {
5843               error ("Basic block %d pred edge is corrupted", bb->index);
5844               fputs ("Predecessor: ", stderr);
5845               dump_edge_info (stderr, e, 0);
5846               fputs ("\nSuccessor: ", stderr);
5847               dump_edge_info (stderr, e, 1);
5848               fputc ('\n', stderr);
5849               err = 1;
5850             }
5851           if (e->src != ENTRY_BLOCK_PTR)
5852             {
5853               edge e2 = e->src->succ;
5854               while (e2 && e2 != e)
5855                 e2 = e2->succ_next;
5856               if (!e2)
5857                 {
5858                   error ("Basic block %i edge lists are corrupted", bb->index);
5859                   err = 1;
5860                 }
5861             }
5862           e = e->pred_next;
5863         }
5864
5865       /* OK pointers are correct.  Now check the header of basic
5866          block.  It ought to contain optional CODE_LABEL followed
5867          by NOTE_BASIC_BLOCK.  */
5868       x = bb->head;
5869       if (GET_CODE (x) == CODE_LABEL)
5870         {
5871           if (bb->end == x)
5872             {
5873               error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
5874                      bb->index);
5875               err = 1;
5876             }
5877           x = NEXT_INSN (x);
5878         }
5879       if (GET_CODE (x) != NOTE
5880           || NOTE_LINE_NUMBER (x) != NOTE_INSN_BASIC_BLOCK
5881           || NOTE_BASIC_BLOCK (x) != bb)
5882         {
5883           error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
5884                  bb->index);
5885           err = 1;
5886         }
5887
5888       if (bb->end == x)
5889         {
5890           /* Do checks for empty blocks here */
5891         }
5892       else
5893         {
5894           x = NEXT_INSN (x);
5895           while (x)
5896             {
5897               if (GET_CODE (x) == NOTE
5898                   && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
5899                 {
5900                   error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
5901                          INSN_UID (x), bb->index);
5902                   err = 1;
5903                 }
5904
5905               if (x == bb->end)
5906                 break;
5907
5908               if (GET_CODE (x) == JUMP_INSN
5909                   || GET_CODE (x) == CODE_LABEL
5910                   || GET_CODE (x) == BARRIER)
5911                 {
5912                   error ("In basic block %d:", bb->index);
5913                   fatal_insn ("Flow control insn inside a basic block", x);
5914                 }
5915
5916               x = NEXT_INSN (x);
5917             }
5918         }
5919     }
5920
5921   x = rtx_first;
5922   while (x)
5923     {
5924       if (!bb_info[INSN_UID (x)])
5925         {
5926           switch (GET_CODE (x))
5927             {
5928             case BARRIER:
5929             case NOTE:
5930               break;
5931
5932             case CODE_LABEL:
5933               /* An addr_vec is placed outside any block block.  */
5934               if (NEXT_INSN (x)
5935                   && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
5936                   && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
5937                       || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
5938                 {
5939                   x = NEXT_INSN (x);
5940                 }
5941
5942               /* But in any case, non-deletable labels can appear anywhere.  */
5943               break;
5944
5945             default:
5946               fatal_insn ("Insn outside basic block", x);
5947             }
5948         }
5949
5950       x = NEXT_INSN (x);
5951     }
5952
5953   if (err)
5954     abort ();
5955
5956   /* Clean up.  */
5957   free (bb_info);
5958 }
5959 \f
5960 /* Functions to access an edge list with a vector representation.
5961    Enough data is kept such that given an index number, the
5962    pred and succ that edge reprsents can be determined, or
5963    given a pred and a succ, it's index number can be returned.
5964    This allows algorithms which comsume a lot of memory to
5965    represent the normally full matrix of edge (pred,succ) with a
5966    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
5967    wasted space in the client code due to sparse flow graphs.  */
5968
5969 /* This functions initializes the edge list. Basically the entire
5970    flowgraph is processed, and all edges are assigned a number,
5971    and the data structure is filed in.  */
5972 struct edge_list *
5973 create_edge_list ()
5974 {
5975   struct edge_list *elist;
5976   edge e;
5977   int num_edges;
5978   int x;
5979   int block_count;
5980
5981   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
5982
5983   num_edges = 0;
5984
5985   /* Determine the number of edges in the flow graph by counting successor
5986      edges on each basic block.  */
5987   for (x = 0; x < n_basic_blocks; x++)
5988     {
5989       basic_block bb = BASIC_BLOCK (x);
5990
5991       for (e = bb->succ; e; e = e->succ_next)
5992         num_edges++;
5993     }
5994   /* Don't forget successors of the entry block.  */
5995   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
5996     num_edges++;
5997
5998   elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
5999   elist->num_blocks = block_count;
6000   elist->num_edges = num_edges;
6001   elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
6002
6003   num_edges = 0;
6004
6005   /* Follow successors of the entry block, and register these edges.  */
6006   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6007     {
6008       elist->index_to_edge[num_edges] = e;
6009       num_edges++;
6010     }
6011
6012   for (x = 0; x < n_basic_blocks; x++)
6013     {
6014       basic_block bb = BASIC_BLOCK (x);
6015
6016       /* Follow all successors of blocks, and register these edges.  */
6017       for (e = bb->succ; e; e = e->succ_next)
6018         {
6019           elist->index_to_edge[num_edges] = e;
6020           num_edges++;
6021         }
6022     }
6023   return elist;
6024 }
6025
6026 /* This function free's memory associated with an edge list.  */
6027 void
6028 free_edge_list (elist)
6029      struct edge_list *elist;
6030 {
6031   if (elist)
6032     {
6033       free (elist->index_to_edge);
6034       free (elist);
6035     }
6036 }
6037
6038 /* This function provides debug output showing an edge list.  */
6039 void
6040 print_edge_list (f, elist)
6041      FILE *f;
6042      struct edge_list *elist;
6043 {
6044   int x;
6045   fprintf(f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
6046           elist->num_blocks - 2, elist->num_edges);
6047
6048   for (x = 0; x < elist->num_edges; x++)
6049     {
6050       fprintf (f, " %-4d - edge(", x);
6051       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
6052         fprintf (f,"entry,");
6053       else
6054         fprintf (f,"%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
6055
6056       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
6057         fprintf (f,"exit)\n");
6058       else
6059         fprintf (f,"%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
6060     }
6061 }
6062
6063 /* This function provides an internal consistancy check of an edge list,
6064    verifying that all edges are present, and that there are no
6065    extra edges.  */
6066 void
6067 verify_edge_list (f, elist)
6068      FILE *f;
6069      struct edge_list *elist;
6070 {
6071   int x, pred, succ, index;
6072   edge e;
6073
6074   for (x = 0; x < n_basic_blocks; x++)
6075     {
6076       basic_block bb = BASIC_BLOCK (x);
6077
6078       for (e = bb->succ; e; e = e->succ_next)
6079         {
6080           pred = e->src->index;
6081           succ = e->dest->index;
6082           index = EDGE_INDEX (elist, e->src, e->dest);
6083           if (index == EDGE_INDEX_NO_EDGE)
6084             {
6085               fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6086               continue;
6087             }
6088           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6089             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6090                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6091           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6092             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6093                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6094         }
6095     }
6096   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6097     {
6098       pred = e->src->index;
6099       succ = e->dest->index;
6100       index = EDGE_INDEX (elist, e->src, e->dest);
6101       if (index == EDGE_INDEX_NO_EDGE)
6102         {
6103           fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6104           continue;
6105         }
6106       if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6107         fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6108                  index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6109       if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6110         fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6111                  index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6112     }
6113   /* We've verified that all the edges are in the list, no lets make sure
6114      there are no spurious edges in the list.  */
6115
6116   for (pred = 0 ; pred < n_basic_blocks; pred++)
6117     for (succ = 0 ; succ < n_basic_blocks; succ++)
6118       {
6119         basic_block p = BASIC_BLOCK (pred);
6120         basic_block s = BASIC_BLOCK (succ);
6121
6122         int found_edge = 0;
6123
6124         for (e = p->succ; e; e = e->succ_next)
6125           if (e->dest == s)
6126             {
6127               found_edge = 1;
6128               break;
6129             }
6130         for (e = s->pred; e; e = e->pred_next)
6131           if (e->src == p)
6132             {
6133               found_edge = 1;
6134               break;
6135             }
6136         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6137             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6138           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
6139                    pred, succ);
6140         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6141             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6142           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
6143                    pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6144                                            BASIC_BLOCK (succ)));
6145       }
6146     for (succ = 0 ; succ < n_basic_blocks; succ++)
6147       {
6148         basic_block p = ENTRY_BLOCK_PTR;
6149         basic_block s = BASIC_BLOCK (succ);
6150
6151         int found_edge = 0;
6152
6153         for (e = p->succ; e; e = e->succ_next)
6154           if (e->dest == s)
6155             {
6156               found_edge = 1;
6157               break;
6158             }
6159         for (e = s->pred; e; e = e->pred_next)
6160           if (e->src == p)
6161             {
6162               found_edge = 1;
6163               break;
6164             }
6165         if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6166             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6167           fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
6168                    succ);
6169         if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6170             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6171           fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
6172                    succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
6173                                      BASIC_BLOCK (succ)));
6174       }
6175     for (pred = 0 ; pred < n_basic_blocks; pred++)
6176       {
6177         basic_block p = BASIC_BLOCK (pred);
6178         basic_block s = EXIT_BLOCK_PTR;
6179
6180         int found_edge = 0;
6181
6182         for (e = p->succ; e; e = e->succ_next)
6183           if (e->dest == s)
6184             {
6185               found_edge = 1;
6186               break;
6187             }
6188         for (e = s->pred; e; e = e->pred_next)
6189           if (e->src == p)
6190             {
6191               found_edge = 1;
6192               break;
6193             }
6194         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6195             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6196           fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
6197                    pred);
6198         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6199             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6200           fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
6201                    pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6202                                      EXIT_BLOCK_PTR));
6203       }
6204 }
6205
6206 /* This routine will determine what, if any, edge there is between
6207    a specified predecessor and successor.  */
6208
6209 int
6210 find_edge_index (edge_list, pred, succ)
6211      struct edge_list *edge_list;
6212      basic_block pred, succ;
6213 {
6214   int x;
6215   for (x = 0; x < NUM_EDGES (edge_list); x++)
6216     {
6217       if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
6218           && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
6219         return x;
6220     }
6221   return (EDGE_INDEX_NO_EDGE);
6222 }
6223
6224 /* This function will remove an edge from the flow graph.  */
6225 static void
6226 remove_edge (e)
6227      edge e;
6228 {
6229   edge last_pred = NULL;
6230   edge last_succ = NULL;
6231   edge tmp;
6232   basic_block src, dest;
6233   src = e->src;
6234   dest = e->dest;
6235   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
6236     last_succ = tmp;
6237
6238   if (!tmp)
6239     abort ();
6240   if (last_succ)
6241     last_succ->succ_next = e->succ_next;
6242   else
6243     src->succ = e->succ_next;
6244
6245   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
6246     last_pred = tmp;
6247
6248   if (!tmp)
6249     abort ();
6250   if (last_pred)
6251     last_pred->pred_next = e->pred_next;
6252   else
6253     dest->pred = e->pred_next;
6254
6255   n_edges--;
6256   free (e);
6257 }
6258
6259 /* This routine will remove any fake successor edges for a basic block.
6260    When the edge is removed, it is also removed from whatever predecessor
6261    list it is in.  */
6262 static void
6263 remove_fake_successors (bb)
6264      basic_block bb;
6265 {
6266   edge e;
6267   for (e = bb->succ; e ; )
6268     {
6269       edge tmp = e;
6270       e = e->succ_next;
6271       if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
6272         remove_edge (tmp);
6273     }
6274 }
6275
6276 /* This routine will remove all fake edges from the flow graph.  If
6277    we remove all fake successors, it will automatically remove all
6278    fake predecessors.  */
6279 void
6280 remove_fake_edges ()
6281 {
6282   int x;
6283
6284   for (x = 0; x < n_basic_blocks; x++)
6285     remove_fake_successors (BASIC_BLOCK (x));
6286
6287   /* We've handled all successors except the entry block's.  */
6288   remove_fake_successors (ENTRY_BLOCK_PTR);
6289 }
6290
6291 /* This functions will add a fake edge between any block which has no
6292    successors, and the exit block. Some data flow equations require these
6293    edges to exist.  */
6294 void
6295 add_noreturn_fake_exit_edges ()
6296 {
6297   int x;
6298
6299   for (x = 0; x < n_basic_blocks; x++)
6300     if (BASIC_BLOCK (x)->succ == NULL)
6301       make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
6302 }
6303 \f
6304 /* Dump the list of basic blocks in the bitmap NODES.  */
6305 static void
6306 flow_nodes_print (str, nodes, file)
6307      const char *str;
6308      const sbitmap nodes;
6309      FILE *file;
6310 {
6311   int node;
6312
6313   fprintf (file, "%s { ", str);
6314   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
6315   fputs ("}\n", file);
6316 }
6317
6318
6319 /* Dump the list of exiting edges in the array EDGES.  */
6320 static void
6321 flow_exits_print (str, edges, num_edges, file)
6322      const char *str;
6323      const edge *edges;
6324      int num_edges;
6325      FILE *file;
6326 {
6327   int i;
6328
6329   fprintf (file, "%s { ", str);
6330   for (i = 0; i < num_edges; i++)
6331     fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
6332   fputs ("}\n", file);
6333 }
6334
6335
6336 /* Dump loop related CFG information.  */
6337 static void
6338 flow_loops_cfg_dump (loops, file)
6339      const struct loops *loops;
6340      FILE *file;
6341 {
6342   int i;
6343
6344   if (! loops->num || ! file || ! loops->cfg.dom)
6345     return;
6346
6347   for (i = 0; i < n_basic_blocks; i++)
6348     {
6349       edge succ;
6350
6351       fprintf (file, ";; %d succs { ", i);
6352       for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
6353         fprintf (file, "%d ", succ->dest->index);
6354       flow_nodes_print ("} dom", loops->cfg.dom[i], file);
6355     }
6356
6357
6358   /* Dump the DFS node order.  */
6359   if (loops->cfg.dfs_order)
6360     {
6361       fputs (";; DFS order: ", file);
6362       for (i = 0; i < n_basic_blocks; i++)
6363         fprintf (file, "%d ", loops->cfg.dfs_order[i]);
6364       fputs ("\n", file);
6365     }
6366 }
6367
6368
6369 /* Return non-zero if the nodes of LOOP are a subset of OUTER.  */
6370 static int
6371 flow_loop_nested_p (outer, loop)
6372      struct loop *outer;
6373      struct loop *loop;
6374 {
6375   return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
6376 }
6377
6378
6379 /* Dump the loop information specified by LOOPS to the stream FILE.  */
6380 void
6381 flow_loops_dump (loops, file, verbose)
6382      const struct loops *loops;
6383      FILE *file;
6384      int verbose;
6385 {
6386   int i;
6387   int num_loops;
6388
6389   num_loops = loops->num;
6390   if (! num_loops || ! file)
6391     return;
6392
6393   fprintf (file, ";; %d loops found\n", num_loops);
6394
6395   for (i = 0; i < num_loops; i++)
6396     {
6397       struct loop *loop = &loops->array[i];
6398
6399       fprintf (file, ";; loop %d (%d to %d):\n;;   header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
6400                i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
6401                loop->header->index, loop->latch->index,
6402                loop->pre_header ? loop->pre_header->index : -1,
6403                loop->depth, loop->level,
6404                (long) (loop->outer ? (loop->outer - loops->array) : -1));
6405       fprintf (file, ";;   %d", loop->num_nodes);
6406       flow_nodes_print (" nodes", loop->nodes, file);
6407       fprintf (file, ";;   %d", loop->num_exits);
6408       flow_exits_print (" exits", loop->exits, loop->num_exits, file);
6409
6410       if (loop->shared)
6411         {
6412           int j;
6413
6414           for (j = 0; j < i; j++)
6415             {
6416               struct loop *oloop = &loops->array[j];
6417
6418               if (loop->header == oloop->header)
6419                 {
6420                   int disjoint;
6421                   int smaller;
6422
6423                   smaller = loop->num_nodes < oloop->num_nodes;
6424
6425                   /* If the union of LOOP and OLOOP is different than
6426                      the larger of LOOP and OLOOP then LOOP and OLOOP
6427                      must be disjoint.  */
6428                   disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
6429                                                    smaller ? oloop : loop);
6430                   fprintf (file, ";; loop header %d shared by loops %d, %d %s\n",
6431                            loop->header->index, i, j,
6432                            disjoint ? "disjoint" : "nested");
6433                 }
6434             }
6435         }
6436
6437       if (verbose)
6438         {
6439           /* Print diagnostics to compare our concept of a loop with
6440              what the loop notes say.  */
6441           if (GET_CODE (PREV_INSN (loop->header->head)) != NOTE
6442               || NOTE_LINE_NUMBER (PREV_INSN (loop->header->head))
6443               != NOTE_INSN_LOOP_BEG)
6444             fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
6445                      INSN_UID (PREV_INSN (loop->header->head)));
6446           if (GET_CODE (NEXT_INSN (loop->latch->end)) != NOTE
6447               || NOTE_LINE_NUMBER (NEXT_INSN (loop->latch->end))
6448               != NOTE_INSN_LOOP_END)
6449             fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
6450                      INSN_UID (NEXT_INSN (loop->latch->end)));
6451         }
6452     }
6453
6454   if (verbose)
6455     flow_loops_cfg_dump (loops, file);
6456 }
6457
6458
6459 /* Free all the memory allocated for LOOPS.  */
6460 void
6461 flow_loops_free (loops)
6462        struct loops *loops;
6463 {
6464   if (loops->array)
6465     {
6466       int i;
6467
6468       if (! loops->num)
6469         abort ();
6470
6471       /* Free the loop descriptors.  */
6472       for (i = 0; i < loops->num; i++)
6473         {
6474           struct loop *loop = &loops->array[i];
6475
6476           if (loop->nodes)
6477             sbitmap_free (loop->nodes);
6478           if (loop->exits)
6479             free (loop->exits);
6480         }
6481       free (loops->array);
6482       loops->array = NULL;
6483
6484       if (loops->cfg.dom)
6485         sbitmap_vector_free (loops->cfg.dom);
6486       if (loops->cfg.dfs_order)
6487         free (loops->cfg.dfs_order);
6488
6489       sbitmap_free (loops->shared_headers);
6490     }
6491 }
6492
6493
6494 /* Find the exits from the loop using the bitmap of loop nodes NODES
6495    and store in EXITS array.  Return the number of exits from the
6496    loop.  */
6497 static int
6498 flow_loop_exits_find (nodes, exits)
6499      const sbitmap nodes;
6500      edge **exits;
6501 {
6502   edge e;
6503   int node;
6504   int num_exits;
6505
6506   *exits = NULL;
6507
6508   /* Check all nodes within the loop to see if there are any
6509      successors not in the loop.  Note that a node may have multiple
6510      exiting edges.  */
6511   num_exits = 0;
6512   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
6513     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
6514       {
6515         basic_block dest = e->dest;
6516
6517         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
6518             num_exits++;
6519       }
6520   });
6521
6522   if (! num_exits)
6523     return 0;
6524
6525   *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
6526
6527   /* Store all exiting edges into an array.  */
6528   num_exits = 0;
6529   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
6530     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
6531       {
6532         basic_block dest = e->dest;
6533
6534         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
6535           (*exits)[num_exits++] = e;
6536       }
6537   });
6538
6539   return num_exits;
6540 }
6541
6542
6543 /* Find the nodes contained within the loop with header HEADER and
6544    latch LATCH and store in NODES.  Return the number of nodes within
6545    the loop.  */
6546 static int
6547 flow_loop_nodes_find (header, latch, nodes)
6548      basic_block header;
6549      basic_block latch;
6550      sbitmap nodes;
6551 {
6552   basic_block *stack;
6553   int sp;
6554   int num_nodes = 0;
6555
6556   stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
6557   sp = 0;
6558
6559   /* Start with only the loop header in the set of loop nodes.  */
6560   sbitmap_zero (nodes);
6561   SET_BIT (nodes, header->index);
6562   num_nodes++;
6563   header->loop_depth++;
6564
6565   /* Push the loop latch on to the stack.  */
6566   if (! TEST_BIT (nodes, latch->index))
6567     {
6568       SET_BIT (nodes, latch->index);
6569       latch->loop_depth++;
6570       num_nodes++;
6571       stack[sp++] = latch;
6572     }
6573
6574   while (sp)
6575     {
6576       basic_block node;
6577       edge e;
6578
6579       node = stack[--sp];
6580       for (e = node->pred; e; e = e->pred_next)
6581         {
6582           basic_block ancestor = e->src;
6583
6584           /* If each ancestor not marked as part of loop, add to set of
6585              loop nodes and push on to stack.  */
6586           if (ancestor != ENTRY_BLOCK_PTR
6587               && ! TEST_BIT (nodes, ancestor->index))
6588             {
6589               SET_BIT (nodes, ancestor->index);
6590               ancestor->loop_depth++;
6591               num_nodes++;
6592               stack[sp++] = ancestor;
6593             }
6594         }
6595     }
6596   free (stack);
6597   return num_nodes;
6598 }
6599
6600
6601 /* Compute the depth first search order and store in the array
6602    DFS_ORDER, marking the nodes visited in VISITED.  Returns the
6603    number of nodes visited.  */
6604 static int
6605 flow_depth_first_order_compute (dfs_order)
6606      int *dfs_order;
6607 {
6608   edge e;
6609   edge *stack;
6610   int sp;
6611   int dfsnum = 0;
6612   sbitmap visited;
6613
6614   /* Allocate stack for back-tracking up CFG.  */
6615   stack = (edge *) xmalloc (n_basic_blocks * sizeof (edge));
6616   sp = 0;
6617
6618   /* Allocate bitmap to track nodes that have been visited.  */
6619   visited = sbitmap_alloc (n_basic_blocks);
6620
6621   /* None of the nodes in the CFG have been visited yet.  */
6622   sbitmap_zero (visited);
6623
6624   /* Start with the first successor edge from the entry block.  */
6625   e = ENTRY_BLOCK_PTR->succ;
6626   while (e)
6627     {
6628       basic_block src = e->src;
6629       basic_block dest = e->dest;
6630
6631       /* Mark that we have visited this node.  */
6632       if (src != ENTRY_BLOCK_PTR)
6633         SET_BIT (visited, src->index);
6634
6635       /* If this node has not been visited before, push the current
6636          edge on to the stack and proceed with the first successor
6637          edge of this node.  */
6638       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
6639           && dest->succ)
6640         {
6641           stack[sp++] = e;
6642           e = dest->succ;
6643         }
6644       else
6645         {
6646           if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
6647               && ! dest->succ)
6648             {
6649               /* DEST has no successors (for example, a non-returning
6650                  function is called) so do not push the current edge
6651                  but carry on with its next successor.  */
6652               dfs_order[dest->index] = n_basic_blocks - ++dfsnum;
6653               SET_BIT (visited, dest->index);
6654             }
6655
6656           while (! e->succ_next && src != ENTRY_BLOCK_PTR)
6657             {
6658               dfs_order[src->index] = n_basic_blocks - ++dfsnum;
6659
6660               /* Pop edge off stack.  */
6661               e = stack[--sp];
6662               src = e->src;
6663             }
6664           e = e->succ_next;
6665         }
6666     }
6667   free (stack);
6668   sbitmap_free (visited);
6669
6670   /* The number of nodes visited should not be greater than
6671      n_basic_blocks.  */
6672   if (dfsnum > n_basic_blocks)
6673     abort ();
6674
6675   /* There are some nodes left in the CFG that are unreachable.  */
6676   if (dfsnum < n_basic_blocks)
6677     abort ();
6678   return dfsnum;
6679 }
6680
6681
6682 /* Return the block for the pre-header of the loop with header
6683    HEADER where DOM specifies the dominator information.  Return NULL if
6684    there is no pre-header.  */
6685 static basic_block
6686 flow_loop_pre_header_find (header, dom)
6687      basic_block header;
6688      const sbitmap *dom;
6689 {
6690   basic_block pre_header;
6691   edge e;
6692
6693   /* If block p is a predecessor of the header and is the only block
6694      that the header does not dominate, then it is the pre-header.  */
6695   pre_header = NULL;
6696   for (e = header->pred; e; e = e->pred_next)
6697     {
6698       basic_block node = e->src;
6699
6700       if (node != ENTRY_BLOCK_PTR
6701           && ! TEST_BIT (dom[node->index], header->index))
6702         {
6703           if (pre_header == NULL)
6704             pre_header = node;
6705           else
6706             {
6707               /* There are multiple edges into the header from outside
6708                  the loop so there is no pre-header block.  */
6709               pre_header = NULL;
6710               break;
6711             }
6712         }
6713     }
6714   return pre_header;
6715 }
6716
6717
6718 /* Add LOOP to the loop hierarchy tree so that it is a sibling or a
6719    descendant of ROOT.  */
6720 static void
6721 flow_loop_tree_node_add (root, loop)
6722      struct loop *root;
6723      struct loop *loop;
6724 {
6725   struct loop *outer;
6726
6727   if (! loop)
6728     return;
6729
6730   for (outer = root; outer; outer = outer->next)
6731     {
6732       if (flow_loop_nested_p (outer, loop))
6733         {
6734           if (outer->inner)
6735             {
6736               /* Add LOOP as a sibling or descendent of OUTER->INNER.  */
6737               flow_loop_tree_node_add (outer->inner, loop);
6738             }
6739           else
6740             {
6741               /* Add LOOP as child of OUTER.  */
6742               outer->inner = loop;
6743               loop->outer = outer;
6744               loop->next = NULL;
6745             }
6746           return;
6747         }
6748     }
6749   /* Add LOOP as a sibling of ROOT.  */
6750   loop->next = root->next;
6751   root->next = loop;
6752   loop->outer = root->outer;
6753 }
6754
6755
6756 /* Build the loop hierarchy tree for LOOPS.  */
6757 static void
6758 flow_loops_tree_build (loops)
6759        struct loops *loops;
6760 {
6761   int i;
6762   int num_loops;
6763
6764   num_loops = loops->num;
6765   if (! num_loops)
6766     return;
6767
6768   /* Root the loop hierarchy tree with the first loop found.
6769      Since we used a depth first search this should be the
6770      outermost loop.  */
6771   loops->tree = &loops->array[0];
6772   loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
6773
6774   /* Add the remaining loops to the tree.  */
6775   for (i = 1; i < num_loops; i++)
6776     flow_loop_tree_node_add (loops->tree, &loops->array[i]);
6777 }
6778
6779
6780 /* Helper function to compute loop nesting depth and enclosed loop level
6781    for the natural loop specified by LOOP at the loop depth DEPTH.
6782    Returns the loop level.  */
6783 static int
6784 flow_loop_level_compute (loop, depth)
6785      struct loop *loop;
6786      int depth;
6787 {
6788   struct loop *inner;
6789   int level = 0;
6790
6791   if (! loop)
6792     return 0;
6793
6794   /* Traverse loop tree assigning depth and computing level as the
6795      maximum level of all the inner loops of this loop.  The loop
6796      level is equivalent to the height of the loop in the loop tree
6797      and corresponds to the number of enclosed loop levels.  */
6798   for (inner = loop->inner; inner; inner = inner->next)
6799     {
6800       int ilevel;
6801
6802       ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
6803
6804       if (ilevel > level)
6805         level = ilevel;
6806     }
6807   loop->level = level;
6808   loop->depth = depth;
6809   return level;
6810 }
6811
6812
6813 /* Compute the loop nesting depth and enclosed loop level for the loop
6814    hierarchy tree specfied by LOOPS.  Return the maximum enclosed loop
6815    level.  */
6816
6817 static int
6818 flow_loops_level_compute (loops)
6819      struct loops *loops;
6820 {
6821   return flow_loop_level_compute (loops->tree, 1);
6822 }
6823
6824
6825 /* Find all the natural loops in the function and save in LOOPS structure
6826    and recalculate loop_depth information in basic block structures.
6827    Return the number of natural loops found.  */
6828
6829 int
6830 flow_loops_find (loops)
6831        struct loops *loops;
6832 {
6833   int i;
6834   int b;
6835   int num_loops;
6836   edge e;
6837   sbitmap headers;
6838   sbitmap *dom;
6839   int *dfs_order;
6840
6841   loops->num = 0;
6842   loops->array = NULL;
6843   loops->tree = NULL;
6844   dfs_order = NULL;
6845
6846   /* Taking care of this degenerate case makes the rest of
6847      this code simpler.  */
6848   if (n_basic_blocks == 0)
6849     return 0;
6850
6851   /* Compute the dominators.  */
6852   dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6853   compute_flow_dominators (dom, NULL);
6854
6855   /* Count the number of loop edges (back edges).  This should be the
6856      same as the number of natural loops.  Also clear the loop_depth
6857      and as we work from inner->outer in a loop nest we call
6858      find_loop_nodes_find which will increment loop_depth for nodes
6859      within the current loop, which happens to enclose inner loops.  */
6860
6861   num_loops = 0;
6862   for (b = 0; b < n_basic_blocks; b++)
6863     {
6864       BASIC_BLOCK (b)->loop_depth = 0;
6865       for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
6866         {
6867           basic_block latch = e->src;
6868
6869           /* Look for back edges where a predecessor is dominated
6870              by this block.  A natural loop has a single entry
6871              node (header) that dominates all the nodes in the
6872              loop.  It also has single back edge to the header
6873              from a latch node.  Note that multiple natural loops
6874              may share the same header.  */
6875           if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
6876             num_loops++;
6877         }
6878     }
6879
6880   if (num_loops)
6881     {
6882       /* Compute depth first search order of the CFG so that outer
6883          natural loops will be found before inner natural loops.  */
6884       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
6885       flow_depth_first_order_compute (dfs_order);
6886
6887       /* Allocate loop structures.  */
6888       loops->array
6889         = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
6890
6891       headers = sbitmap_alloc (n_basic_blocks);
6892       sbitmap_zero (headers);
6893
6894       loops->shared_headers = sbitmap_alloc (n_basic_blocks);
6895       sbitmap_zero (loops->shared_headers);
6896
6897       /* Find and record information about all the natural loops
6898          in the CFG.  */
6899       num_loops = 0;
6900       for (b = 0; b < n_basic_blocks; b++)
6901         {
6902           basic_block header;
6903
6904           /* Search the nodes of the CFG in DFS order that we can find
6905              outer loops first.  */
6906           header = BASIC_BLOCK (dfs_order[b]);
6907
6908           /* Look for all the possible latch blocks for this header.  */
6909           for (e = header->pred; e; e = e->pred_next)
6910             {
6911               basic_block latch = e->src;
6912
6913               /* Look for back edges where a predecessor is dominated
6914                  by this block.  A natural loop has a single entry
6915                  node (header) that dominates all the nodes in the
6916                  loop.  It also has single back edge to the header
6917                  from a latch node.  Note that multiple natural loops
6918                  may share the same header.  */
6919               if (latch != ENTRY_BLOCK_PTR
6920                   && TEST_BIT (dom[latch->index], header->index))
6921                 {
6922                   struct loop *loop;
6923
6924                   loop = loops->array + num_loops;
6925
6926                   loop->header = header;
6927                   loop->latch = latch;
6928
6929                   /* Keep track of blocks that are loop headers so
6930                      that we can tell which loops should be merged.  */
6931                   if (TEST_BIT (headers, header->index))
6932                     SET_BIT (loops->shared_headers, header->index);
6933                   SET_BIT (headers, header->index);
6934
6935                   /* Find nodes contained within the loop.  */
6936                   loop->nodes = sbitmap_alloc (n_basic_blocks);
6937                   loop->num_nodes
6938                     = flow_loop_nodes_find (header, latch, loop->nodes);
6939
6940                   /* Find edges which exit the loop.  Note that a node
6941                      may have several exit edges.  */
6942                   loop->num_exits
6943                     = flow_loop_exits_find (loop->nodes, &loop->exits);
6944
6945                   /* Look to see if the loop has a pre-header node.  */
6946                   loop->pre_header
6947                     = flow_loop_pre_header_find (header, dom);
6948
6949                   num_loops++;
6950                 }
6951             }
6952         }
6953
6954       /* Natural loops with shared headers may either be disjoint or
6955          nested.  Disjoint loops with shared headers cannot be inner
6956          loops and should be merged.  For now just mark loops that share
6957          headers.  */
6958       for (i = 0; i < num_loops; i++)
6959         if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
6960           loops->array[i].shared = 1;
6961
6962       sbitmap_free (headers);
6963     }
6964
6965   loops->num = num_loops;
6966
6967   /* Save CFG derived information to avoid recomputing it.  */
6968   loops->cfg.dom = dom;
6969   loops->cfg.dfs_order = dfs_order;
6970
6971   /* Build the loop hierarchy tree.  */
6972   flow_loops_tree_build (loops);
6973
6974   /* Assign the loop nesting depth and enclosed loop level for each
6975      loop.  */
6976   flow_loops_level_compute (loops);
6977
6978   return num_loops;
6979 }
6980
6981
6982 /* Return non-zero if edge E enters header of LOOP from outside of LOOP.  */
6983 int
6984 flow_loop_outside_edge_p (loop, e)
6985      const struct loop *loop;
6986      edge e;
6987 {
6988   if (e->dest != loop->header)
6989     abort ();
6990   return (e->src == ENTRY_BLOCK_PTR)
6991     || ! TEST_BIT (loop->nodes, e->src->index);
6992 }