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