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