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