gcc/cfg.c

   1 /* Control flow graph manipulation code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains low level functions to manipulate with CFG and analyze it.
  23    All other modules should not transform the datastructure directly and use
  24    abstraction instead.  The file is supposed to be ordered bottom-up.
  25
  26    Available functionality:
  27      - Initialization/deallocation
  28          init_flow, clear_edges
  29      - CFG aware instruction chain manipulation
  30          flow_delete_insn, flow_delete_insn_chain
  31      - Basic block manipulation
  32          create_basic_block, flow_delete_block, split_block, merge_blocks_nomove
  33      - Infrastructure to determine quickly basic block for instruction.
  34          compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
  35          set_block_for_new_insns
  36      - Edge manipulation
  37          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
  38          - Low level edge redirection (without updating instruction chain)
  39              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
  40          - High level edge redirection (with updating and optimizing instruction
  41            chain)
  42              block_label, redirect_edge_and_branch,
  43              redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
  44       - Edge splitting and commiting to edges
  45           split_edge, insert_insn_on_edge, commit_edge_insertions
  46       - Dumpipng and debugging
  47           dump_flow_info, debug_flow_info, dump_edge_info, dump_bb, debug_bb,
  48           debug_bb_n, print_rtl_with_bb
  49       - Consistency checking
  50           verify_flow_info
  51       - CFG updating after constant propagation
  52           purge_dead_edges, purge_all_dead_edges
  53  */
  54 \f
  55 #include "config.h"
  56 #include "system.h"
  57 #include "tree.h"
  58 #include "rtl.h"
  59 #include "hard-reg-set.h"
  60 #include "basic-block.h"
  61 #include "regs.h"
  62 #include "flags.h"
  63 #include "output.h"
  64 #include "function.h"
  65 #include "except.h"
  66 #include "toplev.h"
  67
  68 #include "obstack.h"
  69
  70 /* The obstack on which the flow graph components are allocated.  */
  71
  72 struct obstack flow_obstack;
  73 static char *flow_firstobj;
  74
  75 /* Number of basic blocks in the current function.  */
  76
  77 int n_basic_blocks;
  78
  79 /* Number of edges in the current function.  */
  80
  81 int n_edges;
  82
  83 /* First edge in the deleted edges chain.  */
  84
  85 edge first_deleted_edge;
  86
  87 /* The basic block array.  */
  88
  89 varray_type basic_block_info;
  90
  91 /* The special entry and exit blocks.  */
  92
  93 struct basic_block_def entry_exit_blocks[2]
  94 = {{NULL,                       /* head */
  95     NULL,                       /* end */
  96     NULL,                       /* head_tree */
  97     NULL,                       /* end_tree */
  98     NULL,                       /* pred */
  99     NULL,                       /* succ */
 100     NULL,                       /* local_set */
 101     NULL,                       /* cond_local_set */
 102     NULL,                       /* global_live_at_start */
 103     NULL,                       /* global_live_at_end */
 104     NULL,                       /* aux */
 105     ENTRY_BLOCK,                /* index */
 106     0,                          /* loop_depth */
 107     0,                          /* count */
 108     0,                          /* frequency */
 109     0                           /* flags */
 110   },
 111   {
 112     NULL,                       /* head */
 113     NULL,                       /* end */
 114     NULL,                       /* head_tree */
 115     NULL,                       /* end_tree */
 116     NULL,                       /* pred */
 117     NULL,                       /* succ */
 118     NULL,                       /* local_set */
 119     NULL,                       /* cond_local_set */
 120     NULL,                       /* global_live_at_start */
 121     NULL,                       /* global_live_at_end */
 122     NULL,                       /* aux */
 123     EXIT_BLOCK,                 /* index */
 124     0,                          /* loop_depth */
 125     0,                          /* count */
 126     0,                          /* frequency */
 127     0                           /* flags */
 128   }
 129 };
 130
 131 /* The basic block structure for every insn, indexed by uid.  */
 132
 133 varray_type basic_block_for_insn;
 134
 135 /* The labels mentioned in non-jump rtl.  Valid during find_basic_blocks.  */
 136 /* ??? Should probably be using LABEL_NUSES instead.  It would take a
 137    bit of surgery to be able to use or co-opt the routines in jump.  */
 138
 139 rtx label_value_list;
 140 rtx tail_recursion_label_list;
 141
 142 void debug_flow_info                    PARAMS ((void));
 143 static int can_delete_note_p            PARAMS ((rtx));
 144 static int can_delete_label_p           PARAMS ((rtx));
 145 static void commit_one_edge_insertion   PARAMS ((edge));
 146 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
 147 static void expunge_block               PARAMS ((basic_block));
 148 static rtx last_loop_beg_note           PARAMS ((rtx));
 149 static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
 150 static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
 151 \f
 152 /* Called once at intialization time.  */
 153
 154 void
 155 init_flow ()
 156 {
 157   static int initialized;
 158
 159   first_deleted_edge = 0;
 160   n_edges = 0;
 161
 162   if (!initialized)
 163     {
 164       gcc_obstack_init (&flow_obstack);
 165       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
 166       initialized = 1;
 167     }
 168   else
 169     {
 170       obstack_free (&flow_obstack, flow_firstobj);
 171       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
 172     }
 173 }
 174 \f
 175 /* Free the memory associated with the edge structures.  */
 176
 177 void
 178 clear_edges ()
 179 {
 180   int i;
 181
 182   for (i = 0; i < n_basic_blocks; ++i)
 183     {
 184       basic_block bb = BASIC_BLOCK (i);
 185
 186       while (bb->succ)
 187         remove_edge (bb->succ);
 188     }
 189
 190   while (ENTRY_BLOCK_PTR->succ)
 191     remove_edge (ENTRY_BLOCK_PTR->succ);
 192
 193   if (n_edges)
 194     abort ();
 195 }
 196 \f
 197 /* Return true if NOTE is not one of the ones that must be kept paired,
 198    so that we may simply delete them.  */
 199
 200 static int
 201 can_delete_note_p (note)
 202      rtx note;
 203 {
 204   return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
 205           || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
 206 }
 207
 208 /* True if a given label can be deleted.  */
 209
 210 static int
 211 can_delete_label_p (label)
 212      rtx label;
 213 {
 214   rtx x;
 215
 216   if (LABEL_PRESERVE_P (label))
 217     return 0;
 218
 219   for (x = forced_labels; x; x = XEXP (x, 1))
 220     if (label == XEXP (x, 0))
 221       return 0;
 222   for (x = label_value_list; x; x = XEXP (x, 1))
 223     if (label == XEXP (x, 0))
 224       return 0;
 225   for (x = exception_handler_labels; x; x = XEXP (x, 1))
 226     if (label == XEXP (x, 0))
 227       return 0;
 228
 229   /* User declared labels must be preserved.  */
 230   if (LABEL_NAME (label) != 0)
 231     return 0;
 232
 233   return 1;
 234 }
 235
 236 /* Delete INSN by patching it out.  Return the next insn.  */
 237
 238 rtx
 239 flow_delete_insn (insn)
 240      rtx insn;
 241 {
 242   rtx prev = PREV_INSN (insn);
 243   rtx next = NEXT_INSN (insn);
 244   rtx note;
 245
 246   PREV_INSN (insn) = NULL_RTX;
 247   NEXT_INSN (insn) = NULL_RTX;
 248   INSN_DELETED_P (insn) = 1;
 249
 250   if (prev)
 251     NEXT_INSN (prev) = next;
 252   if (next)
 253     PREV_INSN (next) = prev;
 254   else
 255     set_last_insn (prev);
 256
 257   if (GET_CODE (insn) == CODE_LABEL)
 258     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
 259
 260   /* If deleting a jump, decrement the use count of the label.  Deleting
 261      the label itself should happen in the normal course of block merging.  */
 262   if (GET_CODE (insn) == JUMP_INSN
 263       && JUMP_LABEL (insn)
 264       && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
 265     LABEL_NUSES (JUMP_LABEL (insn))--;
 266
 267   /* Also if deleting an insn that references a label.  */
 268   else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
 269            && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
 270     LABEL_NUSES (XEXP (note, 0))--;
 271
 272   if (GET_CODE (insn) == JUMP_INSN
 273       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
 274           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
 275     {
 276       rtx pat = PATTERN (insn);
 277       int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
 278       int len = XVECLEN (pat, diff_vec_p);
 279       int i;
 280
 281       for (i = 0; i < len; i++)
 282         LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
 283     }
 284
 285   return next;
 286 }
 287
 288 /* Unlink a chain of insns between START and FINISH, leaving notes
 289    that must be paired.  */
 290
 291 void
 292 flow_delete_insn_chain (start, finish)
 293      rtx start, finish;
 294 {
 295   /* Unchain the insns one by one.  It would be quicker to delete all
 296      of these with a single unchaining, rather than one at a time, but
 297      we need to keep the NOTE's.  */
 298
 299   rtx next;
 300
 301   while (1)
 302     {
 303       next = NEXT_INSN (start);
 304       if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
 305         ;
 306       else if (GET_CODE (start) == CODE_LABEL
 307                && ! can_delete_label_p (start))
 308         {
 309           const char *name = LABEL_NAME (start);
 310           PUT_CODE (start, NOTE);
 311           NOTE_LINE_NUMBER (start) = NOTE_INSN_DELETED_LABEL;
 312           NOTE_SOURCE_FILE (start) = name;
 313         }
 314       else
 315         next = flow_delete_insn (start);
 316
 317       if (start == finish)
 318         break;
 319       start = next;
 320     }
 321 }
 322 \f
 323 /* Create a new basic block consisting of the instructions between
 324    HEAD and END inclusive.  This function is designed to allow fast
 325    BB construction - reuses the note and basic block struct
 326    in BB_NOTE, if any and do not grow BASIC_BLOCK chain and should
 327    be used directly only by CFG construction code.
 328    END can be NULL in to create new empty basic block before HEAD.
 329    Both END and HEAD can be NULL to create basic block at the end of
 330    INSN chain.  */
 331
 332 basic_block
 333 create_basic_block_structure (index, head, end, bb_note)
 334      int index;
 335      rtx head, end, bb_note;
 336 {
 337   basic_block bb;
 338
 339   if (bb_note
 340       && ! RTX_INTEGRATED_P (bb_note)
 341       && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
 342       && bb->aux == NULL)
 343     {
 344       /* If we found an existing note, thread it back onto the chain.  */
 345
 346       rtx after;
 347
 348       if (GET_CODE (head) == CODE_LABEL)
 349         after = head;
 350       else
 351         {
 352           after = PREV_INSN (head);
 353           head = bb_note;
 354         }
 355
 356       if (after != bb_note && NEXT_INSN (after) != bb_note)
 357         reorder_insns (bb_note, bb_note, after);
 358     }
 359   else
 360     {
 361       /* Otherwise we must create a note and a basic block structure.
 362          Since we allow basic block structs in rtl, give the struct
 363          the same lifetime by allocating it off the function obstack
 364          rather than using malloc.  */
 365
 366       bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
 367       memset (bb, 0, sizeof (*bb));
 368
 369       if (!head && !end)
 370         {
 371           head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK,
 372                                                   get_last_insn ());
 373         }
 374       else if (GET_CODE (head) == CODE_LABEL && end)
 375         {
 376           bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
 377           if (head == end)
 378             end = bb_note;
 379         }
 380       else
 381         {
 382           bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
 383           head = bb_note;
 384           if (!end)
 385             end = head;
 386         }
 387       NOTE_BASIC_BLOCK (bb_note) = bb;
 388     }
 389
 390   /* Always include the bb note in the block.  */
 391   if (NEXT_INSN (end) == bb_note)
 392     end = bb_note;
 393
 394   bb->head = head;
 395   bb->end = end;
 396   bb->index = index;
 397   BASIC_BLOCK (index) = bb;
 398   if (basic_block_for_insn)
 399     update_bb_for_insn (bb);
 400
 401   /* Tag the block so that we know it has been used when considering
 402      other basic block notes.  */
 403   bb->aux = bb;
 404
 405   return bb;
 406 }
 407
 408 /* Create new basic block consisting of instructions in between HEAD and
 409    END and place it to the BB chain at possition INDEX.
 410    END can be NULL in to create new empty basic block before HEAD.
 411    Both END and HEAD can be NULL to create basic block at the end of
 412    INSN chain.  */
 413
 414 basic_block
 415 create_basic_block (index, head, end)
 416      int index;
 417      rtx head, end;
 418 {
 419   basic_block bb;
 420   int i;
 421
 422   /* Place the new block just after the block being split.  */
 423   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
 424
 425   /* Some parts of the compiler expect blocks to be number in
 426      sequential order so insert the new block immediately after the
 427      block being split..  */
 428   for (i = n_basic_blocks - 1; i > index; --i)
 429     {
 430       basic_block tmp = BASIC_BLOCK (i - 1);
 431       BASIC_BLOCK (i) = tmp;
 432       tmp->index = i;
 433     }
 434
 435   bb = create_basic_block_structure (index, head, end, NULL);
 436   bb->aux = NULL;
 437   return bb;
 438 }
 439
 440 /* Remove block B from the basic block array and compact behind it.  */
 441
 442 static void
 443 expunge_block (b)
 444      basic_block b;
 445 {
 446   int i, n = n_basic_blocks;
 447
 448   for (i = b->index; i + 1 < n; ++i)
 449     {
 450       basic_block x = BASIC_BLOCK (i + 1);
 451       BASIC_BLOCK (i) = x;
 452       x->index = i;
 453     }
 454
 455   basic_block_info->num_elements--;
 456   n_basic_blocks--;
 457 }
 458
 459 /* Delete the insns in a (non-live) block.  We physically delete every
 460    non-deleted-note insn, and update the flow graph appropriately.
 461
 462    Return nonzero if we deleted an exception handler.  */
 463
 464 /* ??? Preserving all such notes strikes me as wrong.  It would be nice
 465    to post-process the stream to remove empty blocks, loops, ranges, etc.  */
 466
 467 int
 468 flow_delete_block (b)
 469      basic_block b;
 470 {
 471   int deleted_handler = 0;
 472   rtx insn, end, tmp;
 473
 474   /* If the head of this block is a CODE_LABEL, then it might be the
 475      label for an exception handler which can't be reached.
 476
 477      We need to remove the label from the exception_handler_label list
 478      and remove the associated NOTE_INSN_EH_REGION_BEG and
 479      NOTE_INSN_EH_REGION_END notes.  */
 480
 481   insn = b->head;
 482
 483   never_reached_warning (insn);
 484
 485   if (GET_CODE (insn) == CODE_LABEL)
 486     maybe_remove_eh_handler (insn);
 487
 488   /* Include any jump table following the basic block.  */
 489   end = b->end;
 490   if (GET_CODE (end) == JUMP_INSN
 491       && (tmp = JUMP_LABEL (end)) != NULL_RTX
 492       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
 493       && GET_CODE (tmp) == JUMP_INSN
 494       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
 495           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
 496     end = tmp;
 497
 498   /* Include any barrier that may follow the basic block.  */
 499   tmp = next_nonnote_insn (end);
 500   if (tmp && GET_CODE (tmp) == BARRIER)
 501     end = tmp;
 502
 503   /* Selectively delete the entire chain.  */
 504   flow_delete_insn_chain (insn, end);
 505
 506   /* Remove the edges into and out of this block.  Note that there may
 507      indeed be edges in, if we are removing an unreachable loop.  */
 508   {
 509     while (b->pred != NULL)
 510       remove_edge (b->pred);
 511     while (b->succ != NULL)
 512       remove_edge (b->succ);
 513
 514     b->pred = NULL;
 515     b->succ = NULL;
 516   }
 517
 518   /* Remove the basic block from the array, and compact behind it.  */
 519   expunge_block (b);
 520
 521   return deleted_handler;
 522 }
 523 \f
 524 /* Records the basic block struct in BB_FOR_INSN, for every instruction
 525    indexed by INSN_UID.  MAX is the size of the array.  */
 526
 527 void
 528 compute_bb_for_insn (max)
 529      int max;
 530 {
 531   int i;
 532
 533   if (basic_block_for_insn)
 534     VARRAY_FREE (basic_block_for_insn);
 535   VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
 536
 537   for (i = 0; i < n_basic_blocks; ++i)
 538     {
 539       basic_block bb = BASIC_BLOCK (i);
 540       rtx insn, end;
 541
 542       end = bb->end;
 543       insn = bb->head;
 544       while (1)
 545         {
 546           int uid = INSN_UID (insn);
 547           if (uid < max)
 548             VARRAY_BB (basic_block_for_insn, uid) = bb;
 549           if (insn == end)
 550             break;
 551           insn = NEXT_INSN (insn);
 552         }
 553     }
 554 }
 555
 556 /* Update insns block within BB.  */
 557
 558 void
 559 update_bb_for_insn (bb)
 560      basic_block bb;
 561 {
 562   rtx insn;
 563
 564   if (! basic_block_for_insn)
 565     return;
 566
 567   for (insn = bb->head; ; insn = NEXT_INSN (insn))
 568     {
 569       set_block_for_insn (insn, bb);
 570
 571       if (insn == bb->end)
 572         break;
 573     }
 574 }
 575
 576 /* Record INSN's block as BB.  */
 577
 578 void
 579 set_block_for_insn (insn, bb)
 580      rtx insn;
 581      basic_block bb;
 582 {
 583   size_t uid = INSN_UID (insn);
 584   if (uid >= basic_block_for_insn->num_elements)
 585     {
 586       int new_size;
 587
 588       /* Add one-eighth the size so we don't keep calling xrealloc.  */
 589       new_size = uid + (uid + 7) / 8;
 590
 591       VARRAY_GROW (basic_block_for_insn, new_size);
 592     }
 593   VARRAY_BB (basic_block_for_insn, uid) = bb;
 594 }
 595
 596 /* When a new insn has been inserted into an existing block, it will
 597    sometimes emit more than a single insn. This routine will set the
 598    block number for the specified insn, and look backwards in the insn
 599    chain to see if there are any other uninitialized insns immediately
 600    previous to this one, and set the block number for them too.  */
 601
 602 void
 603 set_block_for_new_insns (insn, bb)
 604      rtx insn;
 605      basic_block bb;
 606 {
 607   set_block_for_insn (insn, bb);
 608
 609   /* Scan the previous instructions setting the block number until we find
 610      an instruction that has the block number set, or we find a note
 611      of any kind.  */
 612   for (insn = PREV_INSN (insn); insn != NULL_RTX; insn = PREV_INSN (insn))
 613     {
 614       if (GET_CODE (insn) == NOTE)
 615         break;
 616       if ((unsigned) INSN_UID (insn) >= basic_block_for_insn->num_elements
 617           || BLOCK_FOR_INSN (insn) == 0)
 618         set_block_for_insn (insn, bb);
 619       else
 620         break;
 621     }
 622 }
 623 \f
 624 /* Create an edge connecting SRC and DST with FLAGS optionally using
 625    edge cache CACHE.  Return the new edge, NULL if already exist. */
 626
 627 edge
 628 cached_make_edge (edge_cache, src, dst, flags)
 629      sbitmap *edge_cache;
 630      basic_block src, dst;
 631      int flags;
 632 {
 633   int use_edge_cache;
 634   edge e;
 635
 636   /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
 637      many edges to them, and we didn't allocate memory for it.  */
 638   use_edge_cache = (edge_cache
 639                     && src != ENTRY_BLOCK_PTR
 640                     && dst != EXIT_BLOCK_PTR);
 641
 642   /* Make sure we don't add duplicate edges.  */
 643   switch (use_edge_cache)
 644     {
 645     default:
 646       /* Quick test for non-existance of the edge.  */
 647       if (! TEST_BIT (edge_cache[src->index], dst->index))
 648         break;
 649
 650       /* The edge exists; early exit if no work to do.  */
 651       if (flags == 0)
 652         return NULL;
 653
 654       /* FALLTHRU */
 655     case 0:
 656       for (e = src->succ; e; e = e->succ_next)
 657         if (e->dest == dst)
 658           {
 659             e->flags |= flags;
 660             return NULL;
 661           }
 662       break;
 663     }
 664
 665   if (first_deleted_edge)
 666     {
 667       e = first_deleted_edge;
 668       first_deleted_edge = e->succ_next;
 669     }
 670   else
 671     {
 672       e = (edge) obstack_alloc (&flow_obstack, sizeof (*e));
 673       memset (e, 0, sizeof (*e));
 674     }
 675   n_edges++;
 676
 677   e->succ_next = src->succ;
 678   e->pred_next = dst->pred;
 679   e->src = src;
 680   e->dest = dst;
 681   e->flags = flags;
 682
 683   src->succ = e;
 684   dst->pred = e;
 685
 686   if (use_edge_cache)
 687     SET_BIT (edge_cache[src->index], dst->index);
 688
 689   return e;
 690 }
 691
 692 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 693    created edge or NULL if already exist.  */
 694
 695 edge
 696 make_edge (src, dest, flags)
 697      basic_block src, dest;
 698      int flags;
 699 {
 700   return cached_make_edge (NULL, src, dest, flags);
 701 }
 702
 703 /* Create an edge connecting SRC to DEST and set probability by knowling
 704    that it is the single edge leaving SRC.  */
 705
 706 edge
 707 make_single_succ_edge (src, dest, flags)
 708      basic_block src, dest;
 709      int flags;
 710 {
 711   edge e = make_edge (src, dest, flags);
 712
 713   e->probability = REG_BR_PROB_BASE;
 714   e->count = src->count;
 715   return e;
 716 }
 717
 718 /* This function will remove an edge from the flow graph.  */
 719
 720 void
 721 remove_edge (e)
 722      edge e;
 723 {
 724   edge last_pred = NULL;
 725   edge last_succ = NULL;
 726   edge tmp;
 727   basic_block src, dest;
 728   src = e->src;
 729   dest = e->dest;
 730   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
 731     last_succ = tmp;
 732
 733   if (!tmp)
 734     abort ();
 735   if (last_succ)
 736     last_succ->succ_next = e->succ_next;
 737   else
 738     src->succ = e->succ_next;
 739
 740   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
 741     last_pred = tmp;
 742
 743   if (!tmp)
 744     abort ();
 745   if (last_pred)
 746     last_pred->pred_next = e->pred_next;
 747   else
 748     dest->pred = e->pred_next;
 749
 750   n_edges--;
 751   memset (e, 0, sizeof (*e));
 752   e->succ_next = first_deleted_edge;
 753   first_deleted_edge = e;
 754 }
 755
 756 /* Redirect an edge's successor from one block to another.  */
 757
 758 void
 759 redirect_edge_succ (e, new_succ)
 760      edge e;
 761      basic_block new_succ;
 762 {
 763   edge *pe;
 764
 765   /* Disconnect the edge from the old successor block.  */
 766   for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
 767     continue;
 768   *pe = (*pe)->pred_next;
 769
 770   /* Reconnect the edge to the new successor block.  */
 771   e->pred_next = new_succ->pred;
 772   new_succ->pred = e;
 773   e->dest = new_succ;
 774 }
 775
 776 /* Like previous but avoid possible dupplicate edge.  */
 777
 778 edge
 779 redirect_edge_succ_nodup (e, new_succ)
 780      edge e;
 781      basic_block new_succ;
 782 {
 783   edge s;
 784   /* Check whether the edge is already present.  */
 785   for (s = e->src->succ; s; s = s->succ_next)
 786     if (s->dest == new_succ && s != e)
 787       break;
 788   if (s)
 789     {
 790       s->flags |= e->flags;
 791       s->probability += e->probability;
 792       s->count += e->count;
 793       remove_edge (e);
 794       e = s;
 795     }
 796   else
 797     redirect_edge_succ (e, new_succ);
 798   return e;
 799 }
 800
 801 /* Redirect an edge's predecessor from one block to another.  */
 802
 803 void
 804 redirect_edge_pred (e, new_pred)
 805      edge e;
 806      basic_block new_pred;
 807 {
 808   edge *pe;
 809
 810   /* Disconnect the edge from the old predecessor block.  */
 811   for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
 812     continue;
 813   *pe = (*pe)->succ_next;
 814
 815   /* Reconnect the edge to the new predecessor block.  */
 816   e->succ_next = new_pred->succ;
 817   new_pred->succ = e;
 818   e->src = new_pred;
 819 }
 820 \f
 821 /* Split a block BB after insn INSN creating a new fallthru edge.
 822    Return the new edge.  Note that to keep other parts of the compiler happy,
 823    this function renumbers all the basic blocks so that the new
 824    one has a number one greater than the block split.  */
 825
 826 edge
 827 split_block (bb, insn)
 828      basic_block bb;
 829      rtx insn;
 830 {
 831   basic_block new_bb;
 832   edge new_edge;
 833   edge e;
 834
 835   /* There is no point splitting the block after its end.  */
 836   if (bb->end == insn)
 837     return 0;
 838
 839   /* Create the new basic block.  */
 840   new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
 841   new_bb->count = bb->count;
 842   new_bb->frequency = bb->frequency;
 843   new_bb->loop_depth = bb->loop_depth;
 844   bb->end = insn;
 845
 846   /* Redirect the outgoing edges.  */
 847   new_bb->succ = bb->succ;
 848   bb->succ = NULL;
 849   for (e = new_bb->succ; e; e = e->succ_next)
 850     e->src = new_bb;
 851
 852   new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
 853
 854   if (bb->global_live_at_start)
 855     {
 856       new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 857       new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 858       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
 859
 860       /* We now have to calculate which registers are live at the end
 861          of the split basic block and at the start of the new basic
 862          block.  Start with those registers that are known to be live
 863          at the end of the original basic block and get
 864          propagate_block to determine which registers are live.  */
 865       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
 866       propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
 867       COPY_REG_SET (bb->global_live_at_end,
 868                     new_bb->global_live_at_start);
 869     }
 870
 871   return new_edge;
 872 }
 873
 874 /* Blocks A and B are to be merged into a single block A.  The insns
 875    are already contiguous, hence `nomove'.  */
 876
 877 void
 878 merge_blocks_nomove (a, b)
 879      basic_block a, b;
 880 {
 881   edge e;
 882   rtx b_head, b_end, a_end;
 883   rtx del_first = NULL_RTX, del_last = NULL_RTX;
 884   int b_empty = 0;
 885
 886   /* If there was a CODE_LABEL beginning B, delete it.  */
 887   b_head = b->head;
 888   b_end = b->end;
 889   if (GET_CODE (b_head) == CODE_LABEL)
 890     {
 891       /* Detect basic blocks with nothing but a label.  This can happen
 892          in particular at the end of a function.  */
 893       if (b_head == b_end)
 894         b_empty = 1;
 895       del_first = del_last = b_head;
 896       b_head = NEXT_INSN (b_head);
 897     }
 898
 899   /* Delete the basic block note.  */
 900   if (NOTE_INSN_BASIC_BLOCK_P (b_head))
 901     {
 902       if (b_head == b_end)
 903         b_empty = 1;
 904       if (! del_last)
 905         del_first = b_head;
 906       del_last = b_head;
 907       b_head = NEXT_INSN (b_head);
 908     }
 909
 910   /* If there was a jump out of A, delete it.  */
 911   a_end = a->end;
 912   if (GET_CODE (a_end) == JUMP_INSN)
 913     {
 914       rtx prev;
 915
 916       for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
 917         if (GET_CODE (prev) != NOTE
 918             || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
 919             || prev == a->head)
 920           break;
 921
 922       del_first = a_end;
 923
 924 #ifdef HAVE_cc0
 925       /* If this was a conditional jump, we need to also delete
 926          the insn that set cc0.  */
 927       if (only_sets_cc0_p (prev))
 928         {
 929           rtx tmp = prev;
 930           prev = prev_nonnote_insn (prev);
 931           if (!prev)
 932             prev = a->head;
 933           del_first = tmp;
 934         }
 935 #endif
 936
 937       a_end = prev;
 938     }
 939   else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
 940     del_first = NEXT_INSN (a_end);
 941
 942   /* Delete everything marked above as well as crap that might be
 943      hanging out between the two blocks.  */
 944   flow_delete_insn_chain (del_first, del_last);
 945
 946   /* Normally there should only be one successor of A and that is B, but
 947      partway though the merge of blocks for conditional_execution we'll
 948      be merging a TEST block with THEN and ELSE successors.  Free the
 949      whole lot of them and hope the caller knows what they're doing.  */
 950   while (a->succ)
 951     remove_edge (a->succ);
 952
 953   /* Adjust the edges out of B for the new owner.  */
 954   for (e = b->succ; e; e = e->succ_next)
 955     e->src = a;
 956   a->succ = b->succ;
 957
 958   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 959   b->pred = b->succ = NULL;
 960
 961   /* Reassociate the insns of B with A.  */
 962   if (!b_empty)
 963     {
 964       if (basic_block_for_insn)
 965         {
 966           BLOCK_FOR_INSN (b_head) = a;
 967           while (b_head != b_end)
 968             {
 969               b_head = NEXT_INSN (b_head);
 970               BLOCK_FOR_INSN (b_head) = a;
 971             }
 972         }
 973       a_end = b_end;
 974     }
 975   a->end = a_end;
 976
 977   expunge_block (b);
 978 }
 979 \f
 980 /* Return label in the head of basic block.  Create one if it doesn't exist.  */
 981
 982 rtx
 983 block_label (block)
 984      basic_block block;
 985 {
 986   if (block == EXIT_BLOCK_PTR)
 987     return NULL_RTX;
 988   if (GET_CODE (block->head) != CODE_LABEL)
 989     {
 990       block->head = emit_label_before (gen_label_rtx (), block->head);
 991       if (basic_block_for_insn)
 992         set_block_for_insn (block->head, block);
 993     }
 994   return block->head;
 995 }
 996
 997 /* Attempt to perform edge redirection by replacing possibly complex jump
 998    instruction by unconditional jump or removing jump completely.
 999    This can apply only if all edges now point to the same block.
1000
1001    The parameters and return values are equivalent to redirect_edge_and_branch.
1002  */
1003
1004 static bool
1005 try_redirect_by_replacing_jump (e, target)
1006      edge e;
1007      basic_block target;
1008 {
1009   basic_block src = e->src;
1010   rtx insn = src->end, kill_from;
1011   edge tmp;
1012   rtx set;
1013   int fallthru = 0;
1014
1015   /* Verify that all targets will be TARGET.  */
1016   for (tmp = src->succ; tmp; tmp = tmp->succ_next)
1017     if (tmp->dest != target && tmp != e)
1018       break;
1019   if (tmp || !onlyjump_p (insn))
1020     return false;
1021
1022   /* Avoid removing branch with side effects.  */
1023   set = single_set (insn);
1024   if (!set || side_effects_p (set))
1025     return false;
1026
1027   /* In case we zap a conditional jump, we'll need to kill
1028      the cc0 setter too.  */
1029   kill_from = insn;
1030 #ifdef HAVE_cc0
1031   if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
1032     kill_from = PREV_INSN (insn);
1033 #endif
1034
1035   /* See if we can create the fallthru edge.  */
1036   if (can_fallthru (src, target))
1037     {
1038       src->end = PREV_INSN (kill_from);
1039       if (rtl_dump_file)
1040         fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
1041       fallthru = 1;
1042
1043       /* Selectivly unlink whole insn chain.  */
1044       flow_delete_insn_chain (kill_from, PREV_INSN (target->head));
1045     }
1046   /* If this already is simplejump, redirect it.  */
1047   else if (simplejump_p (insn))
1048     {
1049       if (e->dest == target)
1050         return false;
1051       if (rtl_dump_file)
1052         fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
1053                  INSN_UID (insn), e->dest->index, target->index);
1054       redirect_jump (insn, block_label (target), 0);
1055     }
1056   /* Or replace possibly complicated jump insn by simple jump insn.  */
1057   else
1058     {
1059       rtx target_label = block_label (target);
1060       rtx barrier;
1061
1062       src->end = emit_jump_insn_before (gen_jump (target_label), kill_from);
1063       JUMP_LABEL (src->end) = target_label;
1064       LABEL_NUSES (target_label)++;
1065       if (basic_block_for_insn)
1066         set_block_for_new_insns (src->end, src);
1067       if (rtl_dump_file)
1068         fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
1069                  INSN_UID (insn), INSN_UID (src->end));
1070
1071       flow_delete_insn_chain (kill_from, insn);
1072
1073       barrier = next_nonnote_insn (src->end);
1074       if (!barrier || GET_CODE (barrier) != BARRIER)
1075         emit_barrier_after (src->end);
1076     }
1077
1078   /* Keep only one edge out and set proper flags.  */
1079   while (src->succ->succ_next)
1080     remove_edge (src->succ);
1081   e = src->succ;
1082   if (fallthru)
1083     e->flags = EDGE_FALLTHRU;
1084   else
1085     e->flags = 0;
1086   e->probability = REG_BR_PROB_BASE;
1087   e->count = src->count;
1088
1089   /* We don't want a block to end on a line-number note since that has
1090      the potential of changing the code between -g and not -g.  */
1091   while (GET_CODE (e->src->end) == NOTE
1092          && NOTE_LINE_NUMBER (e->src->end) >= 0)
1093     {
1094       rtx prev = PREV_INSN (e->src->end);
1095       flow_delete_insn (e->src->end);
1096       e->src->end = prev;
1097     }
1098
1099   if (e->dest != target)
1100     redirect_edge_succ (e, target);
1101   return true;
1102 }
1103
1104 /* Return last loop_beg note appearing after INSN, before start of next
1105    basic block.  Return INSN if there are no such notes.
1106
1107    When emmiting jump to redirect an fallthru edge, it should always
1108    appear after the LOOP_BEG notes, as loop optimizer expect loop to
1109    eighter start by fallthru edge or jump following the LOOP_BEG note
1110    jumping to the loop exit test.  */
1111
1112 static rtx
1113 last_loop_beg_note (insn)
1114      rtx insn;
1115 {
1116   rtx last = insn;
1117   insn = NEXT_INSN (insn);
1118   while (insn && GET_CODE (insn) == NOTE
1119          && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
1120     {
1121       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1122         last = insn;
1123       insn = NEXT_INSN (insn);
1124     }
1125   return last;
1126 }
1127
1128 /* Attempt to change code to redirect edge E to TARGET.
1129    Don't do that on expense of adding new instructions or reordering
1130    basic blocks.
1131
1132    Function can be also called with edge destionation equivalent to the
1133    TARGET.  Then it should try the simplifications and do nothing if
1134    none is possible.
1135
1136    Return true if transformation suceeded.  We still return flase in case
1137    E already destinated TARGET and we didn't managed to simplify instruction
1138    stream.  */
1139
1140 bool
1141 redirect_edge_and_branch (e, target)
1142      edge e;
1143      basic_block target;
1144 {
1145   rtx tmp;
1146   rtx old_label = e->dest->head;
1147   basic_block src = e->src;
1148   rtx insn = src->end;
1149
1150   if (e->flags & EDGE_COMPLEX)
1151     return false;
1152
1153   if (try_redirect_by_replacing_jump (e, target))
1154     return true;
1155   /* Do this fast path late, as we want above code to simplify for cases
1156      where called on single edge leaving basic block containing nontrivial
1157      jump insn.  */
1158   else if (e->dest == target)
1159     return false;
1160
1161   /* We can only redirect non-fallthru edges of jump insn.  */
1162   if (e->flags & EDGE_FALLTHRU)
1163     return false;
1164   if (GET_CODE (insn) != JUMP_INSN)
1165     return false;
1166
1167   /* Recognize a tablejump and adjust all matching cases.  */
1168   if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1169       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1170       && GET_CODE (tmp) == JUMP_INSN
1171       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1172           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1173     {
1174       rtvec vec;
1175       int j;
1176       rtx new_label = block_label (target);
1177
1178       if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1179         vec = XVEC (PATTERN (tmp), 0);
1180       else
1181         vec = XVEC (PATTERN (tmp), 1);
1182
1183       for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1184         if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1185           {
1186             RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1187             --LABEL_NUSES (old_label);
1188             ++LABEL_NUSES (new_label);
1189           }
1190
1191       /* Handle casesi dispatch insns */
1192       if ((tmp = single_set (insn)) != NULL
1193           && SET_DEST (tmp) == pc_rtx
1194           && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1195           && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1196           && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1197         {
1198           XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
1199                                                        new_label);
1200           --LABEL_NUSES (old_label);
1201           ++LABEL_NUSES (new_label);
1202         }
1203     }
1204   else
1205     {
1206       /* ?? We may play the games with moving the named labels from
1207          one basic block to the other in case only one computed_jump is
1208          available.  */
1209       if (computed_jump_p (insn))
1210         return false;
1211
1212       /* A return instruction can't be redirected.  */
1213       if (returnjump_p (insn))
1214         return false;
1215
1216       /* If the insn doesn't go where we think, we're confused.  */
1217       if (JUMP_LABEL (insn) != old_label)
1218         abort ();
1219       redirect_jump (insn, block_label (target), 0);
1220     }
1221
1222   if (rtl_dump_file)
1223     fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
1224              e->src->index, e->dest->index, target->index);
1225   if (e->dest != target)
1226     redirect_edge_succ_nodup (e, target);
1227   return true;
1228 }
1229
1230 /* Like force_nonfallthru bellow, but additionally performs redirection
1231    Used by redirect_edge_and_branch_force.  */
1232
1233 static basic_block
1234 force_nonfallthru_and_redirect (e, target)
1235      edge e;
1236      basic_block target;
1237 {
1238   basic_block jump_block, new_bb = NULL;
1239   rtx note;
1240   edge new_edge;
1241   rtx label;
1242
1243   if (e->flags & EDGE_ABNORMAL)
1244     abort ();
1245   if (!(e->flags & EDGE_FALLTHRU))
1246     abort ();
1247   if (e->src->succ->succ_next)
1248     {
1249       /* Create the new structures.  */
1250       note = last_loop_beg_note (e->src->end);
1251       jump_block = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
1252       jump_block->count = e->count;
1253       jump_block->frequency = EDGE_FREQUENCY (e);
1254       jump_block->loop_depth = target->loop_depth;
1255
1256       if (target->global_live_at_start)
1257         {
1258           jump_block->global_live_at_start =
1259             OBSTACK_ALLOC_REG_SET (&flow_obstack);
1260           jump_block->global_live_at_end =
1261             OBSTACK_ALLOC_REG_SET (&flow_obstack);
1262           COPY_REG_SET (jump_block->global_live_at_start,
1263                         target->global_live_at_start);
1264           COPY_REG_SET (jump_block->global_live_at_end,
1265                         target->global_live_at_start);
1266         }
1267
1268       /* Wire edge in.  */
1269       new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1270       new_edge->probability = e->probability;
1271       new_edge->count = e->count;
1272
1273       /* Redirect old edge.  */
1274       redirect_edge_pred (e, jump_block);
1275       e->probability = REG_BR_PROB_BASE;
1276
1277       new_bb = jump_block;
1278     }
1279   else
1280     jump_block = e->src;
1281   e->flags &= ~EDGE_FALLTHRU;
1282   label = block_label (target);
1283   jump_block->end = emit_jump_insn_after (gen_jump (label), jump_block->end);
1284   JUMP_LABEL (jump_block->end) = label;
1285   LABEL_NUSES (label)++;
1286   if (basic_block_for_insn)
1287     set_block_for_new_insns (jump_block->end, jump_block);
1288   emit_barrier_after (jump_block->end);
1289   redirect_edge_succ_nodup (e, target);
1290
1291   return new_bb;
1292 }
1293
1294 /* Edge E is assumed to be fallthru edge.  Emit needed jump instruction
1295    (and possibly create new basic block) to make edge non-fallthru.
1296    Return newly created BB or NULL if none.  */
1297 basic_block
1298 force_nonfallthru (e)
1299      edge e;
1300 {
1301   return force_nonfallthru_and_redirect (e, e->dest);
1302 }
1303
1304 /* Redirect edge even at the expense of creating new jump insn or
1305    basic block.  Return new basic block if created, NULL otherwise.
1306    Abort if converison is impossible.  */
1307
1308 basic_block
1309 redirect_edge_and_branch_force (e, target)
1310      edge e;
1311      basic_block target;
1312 {
1313   basic_block new_bb;
1314
1315   if (redirect_edge_and_branch (e, target))
1316     return NULL;
1317   if (e->dest == target)
1318     return NULL;
1319
1320   /* In case the edge redirection failed, try to force it to be non-fallthru
1321      and redirect newly created simplejump.  */
1322   new_bb = force_nonfallthru_and_redirect (e, target);
1323   return new_bb;
1324 }
1325
1326 /* The given edge should potentially be a fallthru edge.  If that is in
1327    fact true, delete the jump and barriers that are in the way.  */
1328
1329 void
1330 tidy_fallthru_edge (e, b, c)
1331      edge e;
1332      basic_block b, c;
1333 {
1334   rtx q;
1335
1336   /* ??? In a late-running flow pass, other folks may have deleted basic
1337      blocks by nopping out blocks, leaving multiple BARRIERs between here
1338      and the target label. They ought to be chastized and fixed.
1339
1340      We can also wind up with a sequence of undeletable labels between
1341      one block and the next.
1342
1343      So search through a sequence of barriers, labels, and notes for
1344      the head of block C and assert that we really do fall through.  */
1345
1346   if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1347     return;
1348
1349   /* Remove what will soon cease being the jump insn from the source block.
1350      If block B consisted only of this single jump, turn it into a deleted
1351      note.  */
1352   q = b->end;
1353   if (GET_CODE (q) == JUMP_INSN
1354       && onlyjump_p (q)
1355       && (any_uncondjump_p (q)
1356           || (b->succ == e && e->succ_next == NULL)))
1357     {
1358 #ifdef HAVE_cc0
1359       /* If this was a conditional jump, we need to also delete
1360          the insn that set cc0.  */
1361       if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1362         q = PREV_INSN (q);
1363 #endif
1364
1365       if (b->head == q)
1366         {
1367           PUT_CODE (q, NOTE);
1368           NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1369           NOTE_SOURCE_FILE (q) = 0;
1370         }
1371       else
1372         {
1373           q = PREV_INSN (q);
1374
1375           /* We don't want a block to end on a line-number note since that has
1376              the potential of changing the code between -g and not -g.  */
1377           while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1378             q = PREV_INSN (q);
1379         }
1380
1381       b->end = q;
1382     }
1383
1384   /* Selectively unlink the sequence.  */
1385   if (q != PREV_INSN (c->head))
1386     flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1387
1388   e->flags |= EDGE_FALLTHRU;
1389 }
1390
1391 /* Fix up edges that now fall through, or rather should now fall through
1392    but previously required a jump around now deleted blocks.  Simplify
1393    the search by only examining blocks numerically adjacent, since this
1394    is how find_basic_blocks created them.  */
1395
1396 void
1397 tidy_fallthru_edges ()
1398 {
1399   int i;
1400
1401   for (i = 1; i < n_basic_blocks; ++i)
1402     {
1403       basic_block b = BASIC_BLOCK (i - 1);
1404       basic_block c = BASIC_BLOCK (i);
1405       edge s;
1406
1407       /* We care about simple conditional or unconditional jumps with
1408          a single successor.
1409
1410          If we had a conditional branch to the next instruction when
1411          find_basic_blocks was called, then there will only be one
1412          out edge for the block which ended with the conditional
1413          branch (since we do not create duplicate edges).
1414
1415          Furthermore, the edge will be marked as a fallthru because we
1416          merge the flags for the duplicate edges.  So we do not want to
1417          check that the edge is not a FALLTHRU edge.  */
1418       if ((s = b->succ) != NULL
1419           && ! (s->flags & EDGE_COMPLEX)
1420           && s->succ_next == NULL
1421           && s->dest == c
1422           /* If the jump insn has side effects, we can't tidy the edge.  */
1423           && (GET_CODE (b->end) != JUMP_INSN
1424               || onlyjump_p (b->end)))
1425         tidy_fallthru_edge (s, b, c);
1426     }
1427 }
1428 \f
1429 /* Helper function for split_edge.  Return true in case edge BB2 to BB1
1430    is back edge of syntactic loop.  */
1431
1432 static bool
1433 back_edge_of_syntactic_loop_p (bb1, bb2)
1434         basic_block bb1, bb2;
1435 {
1436   rtx insn;
1437   int count = 0;
1438
1439   if (bb1->index > bb2->index)
1440     return false;
1441
1442   if (bb1->index == bb2->index)
1443     return true;
1444
1445   for (insn = bb1->end; insn != bb2->head && count >= 0;
1446        insn = NEXT_INSN (insn))
1447     if (GET_CODE (insn) == NOTE)
1448       {
1449         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1450           count++;
1451         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1452           count--;
1453       }
1454
1455   return count >= 0;
1456 }
1457
1458 /* Split a (typically critical) edge.  Return the new block.
1459    Abort on abnormal edges.
1460
1461    ??? The code generally expects to be called on critical edges.
1462    The case of a block ending in an unconditional jump to a
1463    block with multiple predecessors is not handled optimally.  */
1464
1465 basic_block
1466 split_edge (edge_in)
1467      edge edge_in;
1468 {
1469   basic_block bb;
1470   edge edge_out;
1471   rtx before;
1472
1473   /* Abnormal edges cannot be split.  */
1474   if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1475     abort ();
1476
1477   /* We are going to place the new block in front of edge destination.
1478      Avoid existence of fallthru predecesors.  */
1479   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1480     {
1481       edge e;
1482       for (e = edge_in->dest->pred; e; e = e->pred_next)
1483         if (e->flags & EDGE_FALLTHRU)
1484           break;
1485
1486       if (e)
1487         force_nonfallthru (e);
1488     }
1489
1490   /* Create the basic block note.
1491
1492      Where we place the note can have a noticable impact on the generated
1493      code.  Consider this cfg:
1494
1495                         E
1496                         |
1497                         0
1498                        / \
1499                    +->1-->2--->E
1500                    |  |
1501                    +--+
1502
1503       If we need to insert an insn on the edge from block 0 to block 1,
1504       we want to ensure the instructions we insert are outside of any
1505       loop notes that physically sit between block 0 and block 1.  Otherwise
1506       we confuse the loop optimizer into thinking the loop is a phony.  */
1507
1508   if (edge_in->dest != EXIT_BLOCK_PTR
1509       && PREV_INSN (edge_in->dest->head)
1510       && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1511       && NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) == NOTE_INSN_LOOP_BEG
1512       && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1513     before = PREV_INSN (edge_in->dest->head);
1514   else if (edge_in->dest != EXIT_BLOCK_PTR)
1515     before = edge_in->dest->head;
1516   else
1517     before = NULL_RTX;
1518
1519   bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1520                            : edge_in->dest->index, before, NULL);
1521   bb->count = edge_in->count;
1522   bb->frequency = EDGE_FREQUENCY (edge_in);
1523
1524   /* ??? This info is likely going to be out of date very soon.  */
1525   if (edge_in->dest->global_live_at_start)
1526     {
1527       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1528       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1529       COPY_REG_SET (bb->global_live_at_start, edge_in->dest->global_live_at_start);
1530       COPY_REG_SET (bb->global_live_at_end, edge_in->dest->global_live_at_start);
1531     }
1532
1533   edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1534
1535   /* For non-fallthry edges, we must adjust the predecessor's
1536      jump instruction to target our new block.  */
1537   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1538     {
1539       if (!redirect_edge_and_branch (edge_in, bb))
1540         abort ();
1541     }
1542   else
1543     redirect_edge_succ (edge_in, bb);
1544
1545   return bb;
1546 }
1547
1548 /* Queue instructions for insertion on an edge between two basic blocks.
1549    The new instructions and basic blocks (if any) will not appear in the
1550    CFG until commit_edge_insertions is called.  */
1551
1552 void
1553 insert_insn_on_edge (pattern, e)
1554      rtx pattern;
1555      edge e;
1556 {
1557   /* We cannot insert instructions on an abnormal critical edge.
1558      It will be easier to find the culprit if we die now.  */
1559   if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1560     abort ();
1561
1562   if (e->insns == NULL_RTX)
1563     start_sequence ();
1564   else
1565     push_to_sequence (e->insns);
1566
1567   emit_insn (pattern);
1568
1569   e->insns = get_insns ();
1570   end_sequence ();
1571 }
1572
1573 /* Update the CFG for the instructions queued on edge E.  */
1574
1575 static void
1576 commit_one_edge_insertion (e)
1577      edge e;
1578 {
1579   rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1580   basic_block bb;
1581
1582   /* Pull the insns off the edge now since the edge might go away.  */
1583   insns = e->insns;
1584   e->insns = NULL_RTX;
1585
1586   /* Figure out where to put these things.  If the destination has
1587      one predecessor, insert there.  Except for the exit block.  */
1588   if (e->dest->pred->pred_next == NULL
1589       && e->dest != EXIT_BLOCK_PTR)
1590     {
1591       bb = e->dest;
1592
1593       /* Get the location correct wrt a code label, and "nice" wrt
1594          a basic block note, and before everything else.  */
1595       tmp = bb->head;
1596       if (GET_CODE (tmp) == CODE_LABEL)
1597         tmp = NEXT_INSN (tmp);
1598       if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1599         tmp = NEXT_INSN (tmp);
1600       if (tmp == bb->head)
1601         before = tmp;
1602       else
1603         after = PREV_INSN (tmp);
1604     }
1605
1606   /* If the source has one successor and the edge is not abnormal,
1607      insert there.  Except for the entry block.  */
1608   else if ((e->flags & EDGE_ABNORMAL) == 0
1609            && e->src->succ->succ_next == NULL
1610            && e->src != ENTRY_BLOCK_PTR)
1611     {
1612       bb = e->src;
1613       /* It is possible to have a non-simple jump here.  Consider a target
1614          where some forms of unconditional jumps clobber a register.  This
1615          happens on the fr30 for example.
1616
1617          We know this block has a single successor, so we can just emit
1618          the queued insns before the jump.  */
1619       if (GET_CODE (bb->end) == JUMP_INSN)
1620         {
1621           before = bb->end;
1622           while (GET_CODE (PREV_INSN (before)) == NOTE
1623                  && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG)
1624             before = PREV_INSN (before);
1625         }
1626       else
1627         {
1628           /* We'd better be fallthru, or we've lost track of what's what.  */
1629           if ((e->flags & EDGE_FALLTHRU) == 0)
1630             abort ();
1631
1632           after = bb->end;
1633         }
1634     }
1635
1636   /* Otherwise we must split the edge.  */
1637   else
1638     {
1639       bb = split_edge (e);
1640       after = bb->end;
1641     }
1642
1643   /* Now that we've found the spot, do the insertion.  */
1644
1645   /* Set the new block number for these insns, if structure is allocated.  */
1646   if (basic_block_for_insn)
1647     {
1648       rtx i;
1649       for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
1650         set_block_for_insn (i, bb);
1651     }
1652
1653   if (before)
1654     {
1655       emit_insns_before (insns, before);
1656       if (before == bb->head)
1657         bb->head = insns;
1658
1659       last = prev_nonnote_insn (before);
1660     }
1661   else
1662     {
1663       last = emit_insns_after (insns, after);
1664       if (after == bb->end)
1665         bb->end = last;
1666     }
1667
1668   if (returnjump_p (last))
1669     {
1670       /* ??? Remove all outgoing edges from BB and add one for EXIT.
1671          This is not currently a problem because this only happens
1672          for the (single) epilogue, which already has a fallthru edge
1673          to EXIT.  */
1674
1675       e = bb->succ;
1676       if (e->dest != EXIT_BLOCK_PTR
1677           || e->succ_next != NULL
1678           || (e->flags & EDGE_FALLTHRU) == 0)
1679         abort ();
1680       e->flags &= ~EDGE_FALLTHRU;
1681
1682       emit_barrier_after (last);
1683       bb->end = last;
1684
1685       if (before)
1686         flow_delete_insn (before);
1687     }
1688   else if (GET_CODE (last) == JUMP_INSN)
1689     abort ();
1690   find_sub_basic_blocks (bb);
1691 }
1692
1693 /* Update the CFG for all queued instructions.  */
1694
1695 void
1696 commit_edge_insertions ()
1697 {
1698   int i;
1699   basic_block bb;
1700   compute_bb_for_insn (get_max_uid ());
1701
1702 #ifdef ENABLE_CHECKING
1703   verify_flow_info ();
1704 #endif
1705
1706   i = -1;
1707   bb = ENTRY_BLOCK_PTR;
1708   while (1)
1709     {
1710       edge e, next;
1711
1712       for (e = bb->succ; e; e = next)
1713         {
1714           next = e->succ_next;
1715           if (e->insns)
1716             commit_one_edge_insertion (e);
1717         }
1718
1719       if (++i >= n_basic_blocks)
1720         break;
1721       bb = BASIC_BLOCK (i);
1722     }
1723 }
1724 \f
1725 void
1726 dump_flow_info (file)
1727      FILE *file;
1728 {
1729   register int i;
1730   static const char * const reg_class_names[] = REG_CLASS_NAMES;
1731
1732   fprintf (file, "%d registers.\n", max_regno);
1733   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1734     if (REG_N_REFS (i))
1735       {
1736         enum reg_class class, altclass;
1737         fprintf (file, "\nRegister %d used %d times across %d insns",
1738                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
1739         if (REG_BASIC_BLOCK (i) >= 0)
1740           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
1741         if (REG_N_SETS (i))
1742           fprintf (file, "; set %d time%s", REG_N_SETS (i),
1743                    (REG_N_SETS (i) == 1) ? "" : "s");
1744         if (REG_USERVAR_P (regno_reg_rtx[i]))
1745           fprintf (file, "; user var");
1746         if (REG_N_DEATHS (i) != 1)
1747           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
1748         if (REG_N_CALLS_CROSSED (i) == 1)
1749           fprintf (file, "; crosses 1 call");
1750         else if (REG_N_CALLS_CROSSED (i))
1751           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
1752         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
1753           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
1754         class = reg_preferred_class (i);
1755         altclass = reg_alternate_class (i);
1756         if (class != GENERAL_REGS || altclass != ALL_REGS)
1757           {
1758             if (altclass == ALL_REGS || class == ALL_REGS)
1759               fprintf (file, "; pref %s", reg_class_names[(int) class]);
1760             else if (altclass == NO_REGS)
1761               fprintf (file, "; %s or none", reg_class_names[(int) class]);
1762             else
1763               fprintf (file, "; pref %s, else %s",
1764                        reg_class_names[(int) class],
1765                        reg_class_names[(int) altclass]);
1766           }
1767         if (REG_POINTER (regno_reg_rtx[i]))
1768           fprintf (file, "; pointer");
1769         fprintf (file, ".\n");
1770       }
1771
1772   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
1773   for (i = 0; i < n_basic_blocks; i++)
1774     {
1775       register basic_block bb = BASIC_BLOCK (i);
1776       register edge e;
1777
1778       fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count ",
1779                i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth);
1780       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1781       fprintf (file, ", freq %i.\n", bb->frequency);
1782
1783       fprintf (file, "Predecessors: ");
1784       for (e = bb->pred; e; e = e->pred_next)
1785         dump_edge_info (file, e, 0);
1786
1787       fprintf (file, "\nSuccessors: ");
1788       for (e = bb->succ; e; e = e->succ_next)
1789         dump_edge_info (file, e, 1);
1790
1791       fprintf (file, "\nRegisters live at start:");
1792       dump_regset (bb->global_live_at_start, file);
1793
1794       fprintf (file, "\nRegisters live at end:");
1795       dump_regset (bb->global_live_at_end, file);
1796
1797       putc ('\n', file);
1798     }
1799
1800   putc ('\n', file);
1801 }
1802
1803 void
1804 debug_flow_info ()
1805 {
1806   dump_flow_info (stderr);
1807 }
1808
1809 void
1810 dump_edge_info (file, e, do_succ)
1811      FILE *file;
1812      edge e;
1813      int do_succ;
1814 {
1815   basic_block side = (do_succ ? e->dest : e->src);
1816
1817   if (side == ENTRY_BLOCK_PTR)
1818     fputs (" ENTRY", file);
1819   else if (side == EXIT_BLOCK_PTR)
1820     fputs (" EXIT", file);
1821   else
1822     fprintf (file, " %d", side->index);
1823
1824   if (e->probability)
1825     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
1826
1827   if (e->count)
1828     {
1829       fprintf (file, " count:");
1830       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) e->count);
1831     }
1832
1833   if (e->flags)
1834     {
1835       static const char * const bitnames[] = {
1836         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back"
1837       };
1838       int comma = 0;
1839       int i, flags = e->flags;
1840
1841       fputc (' ', file);
1842       fputc ('(', file);
1843       for (i = 0; flags; i++)
1844         if (flags & (1 << i))
1845           {
1846             flags &= ~(1 << i);
1847
1848             if (comma)
1849               fputc (',', file);
1850             if (i < (int) ARRAY_SIZE (bitnames))
1851               fputs (bitnames[i], file);
1852             else
1853               fprintf (file, "%d", i);
1854             comma = 1;
1855           }
1856       fputc (')', file);
1857     }
1858 }
1859 \f
1860 /* Print out one basic block with live information at start and end.  */
1861
1862 void
1863 dump_bb (bb, outf)
1864      basic_block bb;
1865      FILE *outf;
1866 {
1867   rtx insn;
1868   rtx last;
1869   edge e;
1870
1871   fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1872            bb->index, bb->loop_depth);
1873   fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1874   putc ('\n', outf);
1875
1876   fputs (";; Predecessors: ", outf);
1877   for (e = bb->pred; e; e = e->pred_next)
1878     dump_edge_info (outf, e, 0);
1879   putc ('\n', outf);
1880
1881   fputs (";; Registers live at start:", outf);
1882   dump_regset (bb->global_live_at_start, outf);
1883   putc ('\n', outf);
1884
1885   for (insn = bb->head, last = NEXT_INSN (bb->end);
1886        insn != last;
1887        insn = NEXT_INSN (insn))
1888     print_rtl_single (outf, insn);
1889
1890   fputs (";; Registers live at end:", outf);
1891   dump_regset (bb->global_live_at_end, outf);
1892   putc ('\n', outf);
1893
1894   fputs (";; Successors: ", outf);
1895   for (e = bb->succ; e; e = e->succ_next)
1896     dump_edge_info (outf, e, 1);
1897   putc ('\n', outf);
1898 }
1899
1900 void
1901 debug_bb (bb)
1902      basic_block bb;
1903 {
1904   dump_bb (bb, stderr);
1905 }
1906
1907 void
1908 debug_bb_n (n)
1909      int n;
1910 {
1911   dump_bb (BASIC_BLOCK (n), stderr);
1912 }
1913
1914 /* Like print_rtl, but also print out live information for the start of each
1915    basic block.  */
1916
1917 void
1918 print_rtl_with_bb (outf, rtx_first)
1919      FILE *outf;
1920      rtx rtx_first;
1921 {
1922   register rtx tmp_rtx;
1923
1924   if (rtx_first == 0)
1925     fprintf (outf, "(nil)\n");
1926   else
1927     {
1928       int i;
1929       enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1930       int max_uid = get_max_uid ();
1931       basic_block *start = (basic_block *)
1932         xcalloc (max_uid, sizeof (basic_block));
1933       basic_block *end = (basic_block *)
1934         xcalloc (max_uid, sizeof (basic_block));
1935       enum bb_state *in_bb_p = (enum bb_state *)
1936         xcalloc (max_uid, sizeof (enum bb_state));
1937
1938       for (i = n_basic_blocks - 1; i >= 0; i--)
1939         {
1940           basic_block bb = BASIC_BLOCK (i);
1941           rtx x;
1942
1943           start[INSN_UID (bb->head)] = bb;
1944           end[INSN_UID (bb->end)] = bb;
1945           for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1946             {
1947               enum bb_state state = IN_MULTIPLE_BB;
1948               if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1949                 state = IN_ONE_BB;
1950               in_bb_p[INSN_UID (x)] = state;
1951
1952               if (x == bb->end)
1953                 break;
1954             }
1955         }
1956
1957       for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1958         {
1959           int did_output;
1960           basic_block bb;
1961
1962           if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1963             {
1964               fprintf (outf, ";; Start of basic block %d, registers live:",
1965                        bb->index);
1966               dump_regset (bb->global_live_at_start, outf);
1967               putc ('\n', outf);
1968             }
1969
1970           if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1971               && GET_CODE (tmp_rtx) != NOTE
1972               && GET_CODE (tmp_rtx) != BARRIER)
1973             fprintf (outf, ";; Insn is not within a basic block\n");
1974           else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1975             fprintf (outf, ";; Insn is in multiple basic blocks\n");
1976
1977           did_output = print_rtl_single (outf, tmp_rtx);
1978
1979           if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1980             {
1981               fprintf (outf, ";; End of basic block %d, registers live:\n",
1982                        bb->index);
1983               dump_regset (bb->global_live_at_end, outf);
1984               putc ('\n', outf);
1985             }
1986
1987           if (did_output)
1988             putc ('\n', outf);
1989         }
1990
1991       free (start);
1992       free (end);
1993       free (in_bb_p);
1994     }
1995
1996   if (current_function_epilogue_delay_list != 0)
1997     {
1998       fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1999       for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
2000            tmp_rtx = XEXP (tmp_rtx, 1))
2001         print_rtl_single (outf, XEXP (tmp_rtx, 0));
2002     }
2003 }
2004 \f
2005 /* Verify the CFG consistency.  This function check some CFG invariants and
2006    aborts when something is wrong.  Hope that this function will help to
2007    convert many optimization passes to preserve CFG consistent.
2008
2009    Currently it does following checks:
2010
2011    - test head/end pointers
2012    - overlapping of basic blocks
2013    - edge list correctness
2014    - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2015    - tails of basic blocks (ensure that boundary is necesary)
2016    - scans body of the basic block for JUMP_INSN, CODE_LABEL
2017      and NOTE_INSN_BASIC_BLOCK
2018    - check that all insns are in the basic blocks
2019    (except the switch handling code, barriers and notes)
2020    - check that all returns are followed by barriers
2021
2022    In future it can be extended check a lot of other stuff as well
2023    (reachability of basic blocks, life information, etc. etc.).  */
2024
2025 void
2026 verify_flow_info ()
2027 {
2028   const int max_uid = get_max_uid ();
2029   const rtx rtx_first = get_insns ();
2030   rtx last_head = get_last_insn ();
2031   basic_block *bb_info, *last_visited;
2032   size_t *edge_checksum;
2033   rtx x;
2034   int i, last_bb_num_seen, num_bb_notes, err = 0;
2035
2036   bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
2037   last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
2038                                           sizeof (basic_block));
2039   edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
2040
2041   for (i = n_basic_blocks - 1; i >= 0; i--)
2042     {
2043       basic_block bb = BASIC_BLOCK (i);
2044       rtx head = bb->head;
2045       rtx end = bb->end;
2046
2047       /* Verify the end of the basic block is in the INSN chain.  */
2048       for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2049         if (x == end)
2050           break;
2051       if (!x)
2052         {
2053           error ("End insn %d for block %d not found in the insn stream.",
2054                  INSN_UID (end), bb->index);
2055           err = 1;
2056         }
2057
2058       /* Work backwards from the end to the head of the basic block
2059          to verify the head is in the RTL chain.  */
2060       for (; x != NULL_RTX; x = PREV_INSN (x))
2061         {
2062           /* While walking over the insn chain, verify insns appear
2063              in only one basic block and initialize the BB_INFO array
2064              used by other passes.  */
2065           if (bb_info[INSN_UID (x)] != NULL)
2066             {
2067               error ("Insn %d is in multiple basic blocks (%d and %d)",
2068                      INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2069               err = 1;
2070             }
2071           bb_info[INSN_UID (x)] = bb;
2072
2073           if (x == head)
2074             break;
2075         }
2076       if (!x)
2077         {
2078           error ("Head insn %d for block %d not found in the insn stream.",
2079                  INSN_UID (head), bb->index);
2080           err = 1;
2081         }
2082
2083       last_head = x;
2084     }
2085
2086   /* Now check the basic blocks (boundaries etc.) */
2087   for (i = n_basic_blocks - 1; i >= 0; i--)
2088     {
2089       basic_block bb = BASIC_BLOCK (i);
2090       int has_fallthru = 0;
2091       edge e;
2092
2093       e = bb->succ;
2094       while (e)
2095         {
2096           if (last_visited [e->dest->index + 2] == bb)
2097             {
2098               error ("verify_flow_info: Duplicate edge %i->%i",
2099                      e->src->index, e->dest->index);
2100               err = 1;
2101             }
2102           last_visited [e->dest->index + 2] = bb;
2103
2104           if (e->flags & EDGE_FALLTHRU)
2105             has_fallthru = 1;
2106
2107           if ((e->flags & EDGE_FALLTHRU)
2108               && e->src != ENTRY_BLOCK_PTR
2109               && e->dest != EXIT_BLOCK_PTR)
2110             {
2111               rtx insn;
2112               if (e->src->index + 1 != e->dest->index)
2113                 {
2114                     error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2115                            e->src->index, e->dest->index);
2116                     err = 1;
2117                 }
2118               else
2119                 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
2120                      insn = NEXT_INSN (insn))
2121                   if (GET_CODE (insn) == BARRIER || INSN_P (insn))
2122                     {
2123                       error ("verify_flow_info: Incorrect fallthru %i->%i",
2124                              e->src->index, e->dest->index);
2125                       fatal_insn ("Wrong insn in the fallthru edge", insn);
2126                       err = 1;
2127                     }
2128             }
2129           if (e->src != bb)
2130             {
2131               error ("verify_flow_info: Basic block %d succ edge is corrupted",
2132                      bb->index);
2133               fprintf (stderr, "Predecessor: ");
2134               dump_edge_info (stderr, e, 0);
2135               fprintf (stderr, "\nSuccessor: ");
2136               dump_edge_info (stderr, e, 1);
2137               fprintf (stderr, "\n");
2138               err = 1;
2139             }
2140           edge_checksum[e->dest->index + 2] += (size_t) e;
2141           e = e->succ_next;
2142         }
2143       if (!has_fallthru)
2144         {
2145           rtx insn = bb->end;
2146
2147           /* Ensure existence of barrier in BB with no fallthru edges.  */
2148           for (insn = bb->end; GET_CODE (insn) != BARRIER;
2149                insn = NEXT_INSN (insn))
2150             if (!insn
2151                 || (GET_CODE (insn) == NOTE
2152                     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
2153                 {
2154                   error ("Missing barrier after block %i", bb->index);
2155                   err = 1;
2156                 }
2157         }
2158
2159       e = bb->pred;
2160       while (e)
2161         {
2162           if (e->dest != bb)
2163             {
2164               error ("Basic block %d pred edge is corrupted", bb->index);
2165               fputs ("Predecessor: ", stderr);
2166               dump_edge_info (stderr, e, 0);
2167               fputs ("\nSuccessor: ", stderr);
2168               dump_edge_info (stderr, e, 1);
2169               fputc ('\n', stderr);
2170               err = 1;
2171             }
2172           edge_checksum[e->dest->index + 2] -= (size_t) e;
2173           e = e->pred_next;
2174         }
2175
2176       /* OK pointers are correct.  Now check the header of basic
2177          block.  It ought to contain optional CODE_LABEL followed
2178          by NOTE_BASIC_BLOCK.  */
2179       x = bb->head;
2180       if (GET_CODE (x) == CODE_LABEL)
2181         {
2182           if (bb->end == x)
2183             {
2184               error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2185                      bb->index);
2186               err = 1;
2187             }
2188           x = NEXT_INSN (x);
2189         }
2190       if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2191         {
2192           error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2193                  bb->index);
2194           err = 1;
2195         }
2196
2197       if (bb->end == x)
2198         {
2199           /* Do checks for empty blocks here */
2200         }
2201       else
2202         {
2203           x = NEXT_INSN (x);
2204           while (x)
2205             {
2206               if (NOTE_INSN_BASIC_BLOCK_P (x))
2207                 {
2208                   error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
2209                          INSN_UID (x), bb->index);
2210                   err = 1;
2211                 }
2212
2213               if (x == bb->end)
2214                 break;
2215
2216               if (GET_CODE (x) == JUMP_INSN
2217                   || GET_CODE (x) == CODE_LABEL
2218                   || GET_CODE (x) == BARRIER)
2219                 {
2220                   error ("In basic block %d:", bb->index);
2221                   fatal_insn ("Flow control insn inside a basic block", x);
2222                 }
2223
2224               x = NEXT_INSN (x);
2225             }
2226         }
2227     }
2228
2229   /* Complete edge checksumming for ENTRY and EXIT.  */
2230   {
2231     edge e;
2232     for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
2233       edge_checksum[e->dest->index + 2] += (size_t) e;
2234     for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
2235       edge_checksum[e->dest->index + 2] -= (size_t) e;
2236   }
2237
2238   for (i = -2; i < n_basic_blocks; ++i)
2239     if (edge_checksum[i + 2])
2240       {
2241         error ("Basic block %i edge lists are corrupted", i);
2242         err = 1;
2243       }
2244
2245   last_bb_num_seen = -1;
2246   num_bb_notes = 0;
2247   x = rtx_first;
2248   while (x)
2249     {
2250       if (NOTE_INSN_BASIC_BLOCK_P (x))
2251         {
2252           basic_block bb = NOTE_BASIC_BLOCK (x);
2253           num_bb_notes++;
2254           if (bb->index != last_bb_num_seen + 1)
2255             internal_error ("Basic blocks not numbered consecutively.");
2256
2257           last_bb_num_seen = bb->index;
2258         }
2259
2260       if (!bb_info[INSN_UID (x)])
2261         {
2262           switch (GET_CODE (x))
2263             {
2264             case BARRIER:
2265             case NOTE:
2266               break;
2267
2268             case CODE_LABEL:
2269               /* An addr_vec is placed outside any block block.  */
2270               if (NEXT_INSN (x)
2271                   && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
2272                   && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2273                       || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2274                 {
2275                   x = NEXT_INSN (x);
2276                 }
2277
2278               /* But in any case, non-deletable labels can appear anywhere.  */
2279               break;
2280
2281             default:
2282               fatal_insn ("Insn outside basic block", x);
2283             }
2284         }
2285
2286       if (INSN_P (x)
2287           && GET_CODE (x) == JUMP_INSN
2288           && returnjump_p (x) && ! condjump_p (x)
2289           && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
2290             fatal_insn ("Return not followed by barrier", x);
2291
2292       x = NEXT_INSN (x);
2293     }
2294
2295   if (num_bb_notes != n_basic_blocks)
2296     internal_error
2297       ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2298        num_bb_notes, n_basic_blocks);
2299
2300   if (err)
2301     internal_error ("verify_flow_info failed.");
2302
2303   /* Clean up.  */
2304   free (bb_info);
2305   free (last_visited);
2306   free (edge_checksum);
2307 }
2308 \f
2309 /* Assume that the preceeding pass has possibly eliminated jump instructions
2310    or converted the unconditional jumps.  Eliminate the edges from CFG.
2311    Return true if any edges are eliminated.  */
2312
2313 bool
2314 purge_dead_edges (bb)
2315      basic_block bb;
2316 {
2317   edge e, next;
2318   rtx insn = bb->end;
2319   bool purged = false;
2320
2321   if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
2322     return false;
2323   if (GET_CODE (insn) == JUMP_INSN)
2324     {
2325       rtx note;
2326       edge b,f;
2327       /* We do care only about conditional jumps and simplejumps.  */
2328       if (!any_condjump_p (insn)
2329           && !returnjump_p (insn)
2330           && !simplejump_p (insn))
2331         return false;
2332       for (e = bb->succ; e; e = next)
2333         {
2334           next = e->succ_next;
2335
2336           /* Check purposes we can have edge.  */
2337           if ((e->flags & EDGE_FALLTHRU)
2338               && any_condjump_p (insn))
2339             continue;
2340           if (e->dest != EXIT_BLOCK_PTR
2341               && e->dest->head == JUMP_LABEL (insn))
2342             continue;
2343           if (e->dest == EXIT_BLOCK_PTR
2344               && returnjump_p (insn))
2345             continue;
2346           purged = true;
2347           remove_edge (e);
2348         }
2349       if (!bb->succ || !purged)
2350         return false;
2351       if (rtl_dump_file)
2352         fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2353       if (!optimize)
2354         return purged;
2355
2356       /* Redistribute probabilities.  */
2357       if (!bb->succ->succ_next)
2358         {
2359           bb->succ->probability = REG_BR_PROB_BASE;
2360           bb->succ->count = bb->count;
2361         }
2362       else
2363         {
2364           note = find_reg_note (insn, REG_BR_PROB, NULL);
2365           if (!note)
2366             return purged;
2367           b = BRANCH_EDGE (bb);
2368           f = FALLTHRU_EDGE (bb);
2369           b->probability = INTVAL (XEXP (note, 0));
2370           f->probability = REG_BR_PROB_BASE - b->probability;
2371           b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2372           f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2373         }
2374       return purged;
2375     }
2376
2377   /* Cleanup abnormal edges caused by throwing insns that have been
2378      eliminated.  */
2379   if (! can_throw_internal (bb->end))
2380     for (e = bb->succ; e; e = next)
2381       {
2382         next = e->succ_next;
2383         if (e->flags & EDGE_EH)
2384           {
2385             remove_edge (e);
2386             purged = true;
2387           }
2388       }
2389
2390   /* If we don't see a jump insn, we don't know exactly why the block would
2391      have been broken at this point.  Look for a simple, non-fallthru edge,
2392      as these are only created by conditional branches.  If we find such an
2393      edge we know that there used to be a jump here and can then safely
2394      remove all non-fallthru edges.  */
2395   for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2396        e = e->succ_next);
2397   if (!e)
2398     return purged;
2399   for (e = bb->succ; e; e = next)
2400     {
2401       next = e->succ_next;
2402       if (!(e->flags & EDGE_FALLTHRU))
2403         remove_edge (e), purged = true;
2404     }
2405   if (!bb->succ || bb->succ->succ_next)
2406     abort ();
2407   bb->succ->probability = REG_BR_PROB_BASE;
2408   bb->succ->count = bb->count;
2409
2410   if (rtl_dump_file)
2411     fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2412              bb->index);
2413   return purged;
2414 }
2415
2416 /* Search all basic blocks for potentionally dead edges and purge them.
2417
2418    Return true ifif some edge has been elliminated.
2419  */
2420
2421 bool
2422 purge_all_dead_edges ()
2423 {
2424   int i, purged = false;
2425   for (i = 0; i < n_basic_blocks; i++)
2426     purged |= purge_dead_edges (BASIC_BLOCK (i));
2427   return purged;
2428 }