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