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