gcc/cfglayout.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "tree.h"
  24 #include "rtl.h"
  25 #include "hard-reg-set.h"
  26 #include "basic-block.h"
  27 #include "insn-config.h"
  28 #include "output.h"
  29 #include "function.h"
  30 #include "obstack.h"
  31 #include "cfglayout.h"
  32
  33 /* The contents of the current function definition are allocated
  34    in this obstack, and all are freed at the end of the function.  */
  35 extern struct obstack flow_obstack;
  36
  37 /* Holds the interesting trailing notes for the function.  */
  38 static rtx function_footer;
  39
  40 static rtx skip_insns_after_block       PARAMS ((basic_block));
  41 static void record_effective_endpoints  PARAMS ((void));
  42 static rtx label_for_bb                 PARAMS ((basic_block));
  43 static void fixup_reorder_chain         PARAMS ((void));
  44
  45 static void set_block_levels            PARAMS ((tree, int));
  46 static void change_scope                PARAMS ((rtx, tree, tree));
  47
  48 void verify_insn_chain                  PARAMS ((void));
  49 static void cleanup_unconditional_jumps PARAMS ((void));
  50 static void fixup_fallthru_exit_predecessor PARAMS ((void));
  51 static rtx unlink_insn_chain PARAMS ((rtx, rtx));
  52 static rtx duplicate_insn_chain PARAMS ((rtx, rtx));
  53
  54 /* Map insn uid to lexical block.  */
  55 static varray_type insn_scopes;
  56 \f
  57 static rtx
  58 unlink_insn_chain (first, last)
  59      rtx first;
  60      rtx last;
  61 {
  62   rtx prevfirst = PREV_INSN (first);
  63   rtx nextlast = NEXT_INSN (last);
  64
  65   PREV_INSN (first) = NULL;
  66   NEXT_INSN (last) = NULL;
  67   if (prevfirst)
  68     NEXT_INSN (prevfirst) = nextlast;
  69   if (nextlast)
  70     PREV_INSN (nextlast) = prevfirst;
  71   else
  72     set_last_insn (prevfirst);
  73   if (!prevfirst)
  74     set_first_insn (nextlast);
  75   return first;
  76 }
  77 \f
  78 /* Skip over inter-block insns occurring after BB which are typically
  79    associated with BB (e.g., barriers). If there are any such insns,
  80    we return the last one. Otherwise, we return the end of BB.  */
  81
  82 static rtx
  83 skip_insns_after_block (bb)
  84      basic_block bb;
  85 {
  86   rtx insn, last_insn, next_head, prev;
  87
  88   next_head = NULL_RTX;
  89   if (bb->index + 1 != n_basic_blocks)
  90     next_head = BASIC_BLOCK (bb->index + 1)->head;
  91
  92   for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; )
  93     {
  94       if (insn == next_head)
  95         break;
  96
  97       switch (GET_CODE (insn))
  98         {
  99         case BARRIER:
 100           last_insn = insn;
 101           continue;
 102
 103         case NOTE:
 104           switch (NOTE_LINE_NUMBER (insn))
 105             {
 106             case NOTE_INSN_LOOP_END:
 107             case NOTE_INSN_BLOCK_END:
 108               last_insn = insn;
 109               continue;
 110             case NOTE_INSN_DELETED:
 111             case NOTE_INSN_DELETED_LABEL:
 112               continue;
 113
 114             default:
 115               continue;
 116               break;
 117             }
 118           break;
 119
 120         case CODE_LABEL:
 121           if (NEXT_INSN (insn)
 122               && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 123               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 124                   || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 125             {
 126               insn = NEXT_INSN (insn);
 127               last_insn = insn;
 128               continue;
 129             }
 130           break;
 131
 132         default:
 133           break;
 134         }
 135
 136       break;
 137     }
 138
 139   /* It is possible to hit contradictory sequence.  For instance:
 140
 141      jump_insn
 142      NOTE_INSN_LOOP_BEG
 143      barrier
 144
 145      Where barrier belongs to jump_insn, but the note does not.  This can be
 146      created by removing the basic block originally following
 147      NOTE_INSN_LOOP_BEG.  In such case reorder the notes.  */
 148
 149   for (insn = last_insn; insn != bb->end; insn = prev)
 150     {
 151       prev = PREV_INSN (insn);
 152       if (GET_CODE (insn) == NOTE)
 153         switch (NOTE_LINE_NUMBER (insn))
 154           {
 155           case NOTE_INSN_LOOP_END:
 156           case NOTE_INSN_BLOCK_END:
 157           case NOTE_INSN_DELETED:
 158           case NOTE_INSN_DELETED_LABEL:
 159             continue;
 160           default:
 161             reorder_insns (insn, insn, last_insn);
 162         }
 163     }
 164
 165   return last_insn;
 166 }
 167
 168 /* Locate or create a label for a given basic block.  */
 169
 170 static rtx
 171 label_for_bb (bb)
 172      basic_block bb;
 173 {
 174   rtx label = bb->head;
 175
 176   if (GET_CODE (label) != CODE_LABEL)
 177     {
 178       if (rtl_dump_file)
 179         fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index);
 180
 181       label = block_label (bb);
 182     }
 183
 184   return label;
 185 }
 186
 187 /* Locate the effective beginning and end of the insn chain for each
 188    block, as defined by skip_insns_after_block above.  */
 189
 190 static void
 191 record_effective_endpoints ()
 192 {
 193   rtx next_insn = get_insns ();
 194   int i;
 195
 196   for (i = 0; i < n_basic_blocks; i++)
 197     {
 198       basic_block bb = BASIC_BLOCK (i);
 199       rtx end;
 200
 201       if (PREV_INSN (bb->head) && next_insn != bb->head)
 202         RBI (bb)->header = unlink_insn_chain (next_insn,
 203                                               PREV_INSN (bb->head));
 204       end = skip_insns_after_block (bb);
 205       if (NEXT_INSN (bb->end) && bb->end != end)
 206         RBI (bb)->footer = unlink_insn_chain (NEXT_INSN (bb->end), end);
 207       next_insn = NEXT_INSN (bb->end);
 208     }
 209
 210   function_footer = next_insn;
 211   if (function_footer)
 212     function_footer = unlink_insn_chain (function_footer, get_last_insn ());
 213 }
 214 \f
 215 /* Build a varray mapping INSN_UID to lexical block.  Return it.  */
 216
 217 void
 218 scope_to_insns_initialize ()
 219 {
 220   tree block = NULL;
 221   rtx insn, next;
 222
 223   VARRAY_TREE_INIT (insn_scopes, get_max_uid (), "insn scopes");
 224
 225   for (insn = get_insns (); insn; insn = next)
 226     {
 227       next = NEXT_INSN (insn);
 228
 229       if (active_insn_p (insn)
 230           && GET_CODE (PATTERN (insn)) != ADDR_VEC
 231           && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
 232         VARRAY_TREE (insn_scopes, INSN_UID (insn)) = block;
 233       else if (GET_CODE (insn) == NOTE)
 234         {
 235           switch (NOTE_LINE_NUMBER (insn))
 236             {
 237             case NOTE_INSN_BLOCK_BEG:
 238               block = NOTE_BLOCK (insn);
 239               delete_insn (insn);
 240               break;
 241             case NOTE_INSN_BLOCK_END:
 242               block = BLOCK_SUPERCONTEXT (block);
 243               delete_insn (insn);
 244               break;
 245             default:
 246               break;
 247             }
 248         }
 249     }
 250 }
 251
 252 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
 253    found in the block tree.  */
 254
 255 static void
 256 set_block_levels (block, level)
 257      tree block;
 258      int level;
 259 {
 260   while (block)
 261     {
 262       BLOCK_NUMBER (block) = level;
 263       set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
 264       block = BLOCK_CHAIN (block);
 265     }
 266 }
 267 \f
 268 /* Emit lexical block notes needed to change scope from S1 to S2.  */
 269
 270 static void
 271 change_scope (orig_insn, s1, s2)
 272      rtx orig_insn;
 273      tree s1, s2;
 274 {
 275   rtx insn = orig_insn;
 276   tree com = NULL_TREE;
 277   tree ts1 = s1, ts2 = s2;
 278   tree s;
 279
 280   while (ts1 != ts2)
 281     {
 282       if (ts1 == NULL || ts2 == NULL)
 283         abort ();
 284       if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
 285         ts1 = BLOCK_SUPERCONTEXT (ts1);
 286       else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
 287         ts2 = BLOCK_SUPERCONTEXT (ts2);
 288       else
 289         {
 290           ts1 = BLOCK_SUPERCONTEXT (ts1);
 291           ts2 = BLOCK_SUPERCONTEXT (ts2);
 292         }
 293     }
 294   com = ts1;
 295
 296   /* Close scopes.  */
 297   s = s1;
 298   while (s != com)
 299     {
 300       rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
 301       NOTE_BLOCK (note) = s;
 302       s = BLOCK_SUPERCONTEXT (s);
 303     }
 304
 305   /* Open scopes.  */
 306   s = s2;
 307   while (s != com)
 308     {
 309       insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
 310       NOTE_BLOCK (insn) = s;
 311       s = BLOCK_SUPERCONTEXT (s);
 312     }
 313 }
 314
 315 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
 316    on the scope tree and the newly reordered instructions.  */
 317
 318 void
 319 scope_to_insns_finalize ()
 320 {
 321   tree cur_block = DECL_INITIAL (cfun->decl);
 322   rtx insn, note;
 323
 324   /* Tag the blocks with a depth number so that change_scope can find
 325      the common parent easily.  */
 326   set_block_levels (cur_block, 0);
 327
 328   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 329     {
 330       tree this_block;
 331
 332       if ((size_t) INSN_UID (insn) >= insn_scopes->num_elements)
 333         continue;
 334       this_block = VARRAY_TREE (insn_scopes, INSN_UID (insn));
 335       if (! this_block)
 336         continue;
 337
 338       if (this_block != cur_block)
 339         {
 340           change_scope (insn, cur_block, this_block);
 341           cur_block = this_block;
 342         }
 343     }
 344
 345   VARRAY_FREE (insn_scopes);
 346
 347   /* change_scope emits before the insn, not after.  */
 348   note = emit_note (NULL, NOTE_INSN_DELETED);
 349   change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
 350   delete_insn (note);
 351
 352   reorder_blocks ();
 353 }
 354 \f
 355 /* Given a reorder chain, rearrange the code to match.  */
 356
 357 static void
 358 fixup_reorder_chain ()
 359 {
 360   basic_block bb, prev_bb;
 361   int index;
 362   rtx insn = NULL;
 363
 364   /* First do the bulk reordering -- rechain the blocks without regard to
 365      the needed changes to jumps and labels.  */
 366
 367   for (bb = BASIC_BLOCK (0), index = 0;
 368        bb != 0;
 369        bb = RBI (bb)->next, index++)
 370     {
 371       if (RBI (bb)->header)
 372         {
 373           if (insn)
 374             NEXT_INSN (insn) = RBI (bb)->header;
 375           else
 376             set_first_insn (RBI (bb)->header);
 377           PREV_INSN (RBI (bb)->header) = insn;
 378           insn = RBI (bb)->header;
 379           while (NEXT_INSN (insn))
 380             insn = NEXT_INSN (insn);
 381         }
 382       if (insn)
 383         NEXT_INSN (insn) = bb->head;
 384       else
 385         set_first_insn (bb->head);
 386       PREV_INSN (bb->head) = insn;
 387       insn = bb->end;
 388       if (RBI (bb)->footer)
 389         {
 390           NEXT_INSN (insn) = RBI (bb)->footer;
 391           PREV_INSN (RBI (bb)->footer) = insn;
 392           while (NEXT_INSN (insn))
 393             insn = NEXT_INSN (insn);
 394         }
 395     }
 396
 397   if (index != n_basic_blocks)
 398     abort ();
 399
 400   NEXT_INSN (insn) = function_footer;
 401   if (function_footer)
 402     PREV_INSN (function_footer) = insn;
 403
 404   while (NEXT_INSN (insn))
 405     insn = NEXT_INSN (insn);
 406
 407   set_last_insn (insn);
 408 #ifdef ENABLE_CHECKING
 409   verify_insn_chain ();
 410 #endif
 411
 412   /* Now add jumps and labels as needed to match the blocks new
 413      outgoing edges.  */
 414
 415   for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
 416     {
 417       edge e_fall, e_taken, e;
 418       rtx bb_end_insn;
 419       basic_block nb;
 420
 421       if (bb->succ == NULL)
 422         continue;
 423
 424       /* Find the old fallthru edge, and another non-EH edge for
 425          a taken jump.  */
 426       e_taken = e_fall = NULL;
 427       for (e = bb->succ; e ; e = e->succ_next)
 428         if (e->flags & EDGE_FALLTHRU)
 429           e_fall = e;
 430         else if (! (e->flags & EDGE_EH))
 431           e_taken = e;
 432
 433       bb_end_insn = bb->end;
 434       if (GET_CODE (bb_end_insn) == JUMP_INSN)
 435         {
 436           if (any_condjump_p (bb_end_insn))
 437             {
 438               /* If the old fallthru is still next, nothing to do.  */
 439               if (RBI (bb)->next == e_fall->dest
 440                   || (!RBI (bb)->next
 441                       && e_fall->dest == EXIT_BLOCK_PTR))
 442                 continue;
 443
 444               /* There is one special case: if *neither* block is next,
 445                  such as happens at the very end of a function, then we'll
 446                  need to add a new unconditional jump.  Choose the taken
 447                  edge based on known or assumed probability.  */
 448               if (RBI (bb)->next != e_taken->dest)
 449                 {
 450                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 451
 452                   if (note
 453                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 454                       && invert_jump (bb_end_insn,
 455                                       label_for_bb (e_fall->dest), 0))
 456                     {
 457                       e_fall->flags &= ~EDGE_FALLTHRU;
 458                       e_taken->flags |= EDGE_FALLTHRU;
 459                       update_br_prob_note (bb);
 460                       e = e_fall, e_fall = e_taken, e_taken = e;
 461                     }
 462                 }
 463
 464               /* Otherwise we can try to invert the jump.  This will
 465                  basically never fail, however, keep up the pretense.  */
 466               else if (invert_jump (bb_end_insn,
 467                                     label_for_bb (e_fall->dest), 0))
 468                 {
 469                   e_fall->flags &= ~EDGE_FALLTHRU;
 470                   e_taken->flags |= EDGE_FALLTHRU;
 471                   update_br_prob_note (bb);
 472                   continue;
 473                 }
 474             }
 475           else if (returnjump_p (bb_end_insn))
 476             continue;
 477           else
 478             {
 479               /* Otherwise we have some switch or computed jump.  In the
 480                  99% case, there should not have been a fallthru edge.  */
 481               if (! e_fall)
 482                 continue;
 483
 484 #ifdef CASE_DROPS_THROUGH
 485               /* Except for VAX.  Since we didn't have predication for the
 486                  tablejump, the fallthru block should not have moved.  */
 487               if (RBI (bb)->next == e_fall->dest)
 488                 continue;
 489               bb_end_insn = skip_insns_after_block (bb);
 490 #else
 491               abort ();
 492 #endif
 493             }
 494         }
 495       else
 496         {
 497           /* No fallthru implies a noreturn function with EH edges, or
 498              something similarly bizarre.  In any case, we don't need to
 499              do anything.  */
 500           if (! e_fall)
 501             continue;
 502
 503           /* If the fallthru block is still next, nothing to do.  */
 504           if (RBI (bb)->next == e_fall->dest)
 505             continue;
 506
 507           /* A fallthru to exit block.  */
 508           if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
 509             continue;
 510         }
 511
 512       /* We got here if we need to add a new jump insn.  */
 513       nb = force_nonfallthru (e_fall);
 514       if (nb)
 515         {
 516           alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
 517           RBI (nb)->visited = 1;
 518           RBI (nb)->next = RBI (bb)->next;
 519           RBI (bb)->next = nb;
 520           /* Don't process this new block.  */
 521           bb = nb;
 522         }
 523     }
 524
 525   /* Put basic_block_info in the new order.  */
 526
 527   if (rtl_dump_file)
 528     {
 529       fprintf (rtl_dump_file, "Reordered sequence:\n");
 530       for (bb = BASIC_BLOCK (0), index = 0; bb; bb = RBI (bb)->next, index ++)
 531         {
 532           fprintf (rtl_dump_file, " %i ", index);
 533           if (RBI (bb)->original)
 534             fprintf (rtl_dump_file, "duplicate of %i ",
 535                      RBI (bb)->original->index);
 536           else if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL)
 537             fprintf (rtl_dump_file, "compensation ");
 538           else
 539             fprintf (rtl_dump_file, "bb %i ", bb->index);
 540           fprintf (rtl_dump_file, " [%i]\n", bb->frequency);
 541         }
 542     }
 543
 544   prev_bb = ENTRY_BLOCK_PTR;
 545   bb = BASIC_BLOCK (0);
 546   index = 0;
 547
 548   for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++)
 549     {
 550       bb->index = index;
 551       BASIC_BLOCK (index) = bb;
 552
 553       bb->prev_bb = prev_bb;
 554       prev_bb->next_bb = bb;
 555     }
 556   prev_bb->next_bb = EXIT_BLOCK_PTR;
 557   EXIT_BLOCK_PTR->prev_bb = prev_bb;
 558 }
 559 \f
 560 /* Perform sanity checks on the insn chain.
 561    1. Check that next/prev pointers are consistent in both the forward and
 562       reverse direction.
 563    2. Count insns in chain, going both directions, and check if equal.
 564    3. Check that get_last_insn () returns the actual end of chain.  */
 565
 566 void
 567 verify_insn_chain ()
 568 {
 569   rtx x, prevx, nextx;
 570   int insn_cnt1, insn_cnt2;
 571
 572   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
 573        x != 0;
 574        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
 575     if (PREV_INSN (x) != prevx)
 576       abort ();
 577
 578   if (prevx != get_last_insn ())
 579     abort ();
 580
 581   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
 582        x != 0;
 583        nextx = x, insn_cnt2++, x = PREV_INSN (x))
 584     if (NEXT_INSN (x) != nextx)
 585       abort ();
 586
 587   if (insn_cnt1 != insn_cnt2)
 588     abort ();
 589 }
 590 \f
 591 /* Remove any unconditional jumps and forwarder block creating fallthru
 592    edges instead.  During BB reordering fallthru edges are not required
 593    to target next basic block in the linear CFG layout, so the unconditional
 594    jumps are not needed.  If LOOPS is not null, also update loop structure &
 595    dominators.  */
 596
 597 static void
 598 cleanup_unconditional_jumps ()
 599 {
 600   int i;
 601   for (i = 0; i < n_basic_blocks; i++)
 602     {
 603       basic_block bb = BASIC_BLOCK (i);
 604
 605       if (!bb->succ)
 606         continue;
 607       if (bb->succ->flags & EDGE_FALLTHRU)
 608         continue;
 609       if (!bb->succ->succ_next)
 610         {
 611           rtx insn;
 612           if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb) && i)
 613             {
 614               basic_block prev = BASIC_BLOCK (--i);
 615
 616               if (rtl_dump_file)
 617                 fprintf (rtl_dump_file, "Removing forwarder BB %i\n",
 618                          bb->index);
 619
 620               redirect_edge_succ (bb->pred, bb->succ->dest);
 621               flow_delete_block (bb);
 622               bb = prev;
 623             }
 624           else if (simplejump_p (bb->end))
 625             {
 626               rtx jump = bb->end;
 627
 628               if (rtl_dump_file)
 629                 fprintf (rtl_dump_file, "Removing jump %i in BB %i\n",
 630                          INSN_UID (jump), bb->index);
 631               delete_insn (jump);
 632               bb->succ->flags |= EDGE_FALLTHRU;
 633             }
 634           else
 635             continue;
 636
 637           /* Cleanup barriers and delete ADDR_VECs in a way as they are belonging
 638              to removed tablejump anyway.  */
 639           insn = NEXT_INSN (bb->end);
 640           while (insn
 641                  && (GET_CODE (insn) != NOTE
 642                      || NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK))
 643             {
 644               rtx next = NEXT_INSN (insn);
 645
 646               if (GET_CODE (insn) == BARRIER)
 647                 delete_barrier (insn);
 648               else if (GET_CODE (insn) == JUMP_INSN)
 649                 delete_insn_chain (PREV_INSN (insn), insn);
 650               else if (GET_CODE (insn) == CODE_LABEL)
 651                 ;
 652               else if (GET_CODE (insn) != NOTE)
 653                 abort ();
 654
 655               insn = next;
 656             }
 657         }
 658     }
 659 }
 660 \f
 661 /* The block falling through to exit must be the last one in the
 662    reordered chain.  Ensure that this condition is met.  */
 663 static void
 664 fixup_fallthru_exit_predecessor ()
 665 {
 666   edge e;
 667   basic_block bb = NULL;
 668
 669   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 670     if (e->flags & EDGE_FALLTHRU)
 671       bb = e->src;
 672
 673   if (bb && RBI (bb)->next)
 674     {
 675       basic_block c = BASIC_BLOCK (0);
 676
 677       while (RBI (c)->next != bb)
 678         c = RBI (c)->next;
 679
 680       RBI (c)->next = RBI (bb)->next;
 681       while (RBI (c)->next)
 682         c = RBI (c)->next;
 683
 684       RBI (c)->next = bb;
 685       RBI (bb)->next = NULL;
 686     }
 687 }
 688 \f
 689 /* Return true in case it is possible to duplicate the basic block BB.  */
 690
 691 bool
 692 cfg_layout_can_duplicate_bb_p (bb)
 693      basic_block bb;
 694 {
 695   rtx next;
 696   edge s;
 697
 698   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 699     return false;
 700
 701   /* Duplicating fallthru block to exit would require adding an jump
 702      and splitting the real last BB.  */
 703   for (s = bb->succ; s; s = s->succ_next)
 704     if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU)
 705        return false;
 706
 707   /* Do not attempt to duplicate tablejumps, as we need to unshare
 708      the dispatch table.  This is dificult to do, as the instructions
 709      computing jump destination may be hoisted outside the basic block.  */
 710   if (GET_CODE (bb->end) == JUMP_INSN && JUMP_LABEL (bb->end)
 711       && (next = next_nonnote_insn (JUMP_LABEL (bb->end)))
 712       && GET_CODE (next) == JUMP_INSN
 713       && (GET_CODE (PATTERN (next)) == ADDR_VEC
 714           || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
 715     return false;
 716   return true;
 717 }
 718
 719 static rtx
 720 duplicate_insn_chain (from, to)
 721      rtx from, to;
 722 {
 723   rtx insn, last;
 724
 725   /* Avoid updating of boundaries of previous basic block.  The
 726      note will get removed from insn stream in fixup.  */
 727   last = emit_note (NULL, NOTE_INSN_DELETED);
 728
 729   /* Create copy at the end of INSN chain.  The chain will
 730      be reordered later.  */
 731   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
 732     {
 733       rtx new;
 734       switch (GET_CODE (insn))
 735         {
 736         case INSN:
 737         case CALL_INSN:
 738         case JUMP_INSN:
 739           /* Avoid copying of dispatch tables.  We never duplicate
 740              tablejumps, so this can hit only in case the table got
 741              moved far from original jump.  */
 742           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 743               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 744             break;
 745           new = emit_copy_of_insn_after (insn, get_last_insn ());
 746           /* Record the INSN_SCOPE.  */
 747           VARRAY_GROW (insn_scopes, INSN_UID (new) + 1);
 748           VARRAY_TREE (insn_scopes, INSN_UID (new))
 749             = VARRAY_TREE (insn_scopes, INSN_UID (insn));
 750           break;
 751
 752         case CODE_LABEL:
 753           break;
 754
 755         case BARRIER:
 756           emit_barrier ();
 757           break;
 758
 759         case NOTE:
 760           switch (NOTE_LINE_NUMBER (insn))
 761             {
 762               /* In case prologue is empty and function contain label
 763                  in first BB, we may want to copy the block.  */
 764             case NOTE_INSN_PROLOGUE_END:
 765
 766             case NOTE_INSN_LOOP_VTOP:
 767             case NOTE_INSN_LOOP_CONT:
 768             case NOTE_INSN_LOOP_BEG:
 769             case NOTE_INSN_LOOP_END:
 770               /* Strip down the loop notes - we don't really want to keep
 771                  them consistent in loop copies.  */
 772             case NOTE_INSN_DELETED:
 773             case NOTE_INSN_DELETED_LABEL:
 774               /* No problem to strip these.  */
 775             case NOTE_INSN_EPILOGUE_BEG:
 776             case NOTE_INSN_FUNCTION_END:
 777               /* Debug code expect these notes to exist just once.
 778                  Keep them in the master copy.
 779                  ??? It probably makes more sense to duplicate them for each
 780                  epilogue copy.  */
 781             case NOTE_INSN_FUNCTION_BEG:
 782               /* There is always just single entry to function.  */
 783             case NOTE_INSN_BASIC_BLOCK:
 784               break;
 785
 786               /* There is no purpose to duplicate prologue.  */
 787             case NOTE_INSN_BLOCK_BEG:
 788             case NOTE_INSN_BLOCK_END:
 789               /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
 790                  reordering is in the progress.  */
 791             case NOTE_INSN_EH_REGION_BEG:
 792             case NOTE_INSN_EH_REGION_END:
 793             case NOTE_INSN_RANGE_BEG:
 794             case NOTE_INSN_RANGE_END:
 795               /* Should never exist at BB duplication time.  */
 796               abort ();
 797               break;
 798             case NOTE_INSN_REPEATED_LINE_NUMBER:
 799               emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
 800               break;
 801
 802             default:
 803               if (NOTE_LINE_NUMBER (insn) < 0)
 804                 abort ();
 805               /* It is possible that no_line_number is set and the note
 806                  won't be emitted.  */
 807               emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
 808             }
 809           break;
 810         default:
 811           abort ();
 812         }
 813     }
 814   insn = NEXT_INSN (last);
 815   delete_insn (last);
 816   return insn;
 817 }
 818
 819 /* Redirect Edge to DEST.  */
 820 void
 821 cfg_layout_redirect_edge (e, dest)
 822      edge e;
 823      basic_block dest;
 824 {
 825   int old_index = dest->index;
 826   basic_block src = e->src;
 827
 828   /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
 829      in the case the basic block appears to be in sequence.  Avoid this
 830      transformation.  */
 831
 832   dest->index = n_basic_blocks + 1;
 833   if (e->flags & EDGE_FALLTHRU)
 834     {
 835       /* In case we are redirecting fallthru edge to the branch edge
 836          of conditional jump, remove it.  */
 837       if (src->succ->succ_next
 838           && !src->succ->succ_next->succ_next)
 839         {
 840           edge s = e->succ_next ? e->succ_next : src->succ;
 841           if (s->dest == dest
 842               && any_condjump_p (src->end)
 843               && onlyjump_p (src->end))
 844             delete_insn (src->end);
 845         }
 846       redirect_edge_succ_nodup (e, dest);
 847     }
 848   else
 849     redirect_edge_and_branch (e, dest);
 850
 851   /* We don't want simplejumps in the insn stream during cfglayout.  */
 852   if (simplejump_p (src->end))
 853     {
 854       delete_insn (src->end);
 855       delete_barrier (NEXT_INSN (src->end));
 856       src->succ->flags |= EDGE_FALLTHRU;
 857     }
 858   dest->index = old_index;
 859 }
 860
 861 /* Create an duplicate of the basic block BB and redirect edge E into it.  */
 862
 863 basic_block
 864 cfg_layout_duplicate_bb (bb, e)
 865      basic_block bb;
 866      edge e;
 867 {
 868   rtx insn;
 869   edge s, n;
 870   basic_block new_bb;
 871   gcov_type new_count = e ? e->count : 0;
 872
 873   if (bb->count < new_count)
 874     new_count = bb->count;
 875   if (!bb->pred)
 876     abort ();
 877 #ifdef ENABLE_CHECKING
 878   if (!cfg_layout_can_duplicate_bb_p (bb))
 879     abort ();
 880 #endif
 881
 882   insn = duplicate_insn_chain (bb->head, bb->end);
 883   new_bb = create_basic_block (insn,
 884                                insn ? get_last_insn () : NULL,
 885                                EXIT_BLOCK_PTR->prev_bb);
 886   alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
 887
 888   if (RBI (bb)->header)
 889     {
 890       insn = RBI (bb)->header;
 891       while (NEXT_INSN (insn))
 892         insn = NEXT_INSN (insn);
 893       insn = duplicate_insn_chain (RBI (bb)->header, insn);
 894       if (insn)
 895         RBI (new_bb)->header = unlink_insn_chain (insn, get_last_insn ());
 896     }
 897
 898   if (RBI (bb)->footer)
 899     {
 900       insn = RBI (bb)->footer;
 901       while (NEXT_INSN (insn))
 902         insn = NEXT_INSN (insn);
 903       insn = duplicate_insn_chain (RBI (bb)->footer, insn);
 904       if (insn)
 905         RBI (new_bb)->footer = unlink_insn_chain (insn, get_last_insn ());
 906     }
 907
 908   if (bb->global_live_at_start)
 909     {
 910       new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 911       new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 912       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
 913       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
 914     }
 915
 916   new_bb->loop_depth = bb->loop_depth;
 917   new_bb->flags = bb->flags;
 918   for (s = bb->succ; s; s = s->succ_next)
 919     {
 920       n = make_edge (new_bb, s->dest, s->flags);
 921       n->probability = s->probability;
 922       if (new_count)
 923         /* Take care for overflows!  */
 924         n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 925       else
 926         n->count = 0;
 927       s->count -= n->count;
 928     }
 929
 930   new_bb->count = new_count;
 931   bb->count -= new_count;
 932
 933   if (e)
 934    {
 935      new_bb->frequency = EDGE_FREQUENCY (e);
 936      bb->frequency -= EDGE_FREQUENCY (e);
 937
 938      cfg_layout_redirect_edge (e, new_bb);
 939    }
 940
 941   if (bb->count < 0)
 942     bb->count = 0;
 943   if (bb->frequency < 0)
 944     bb->frequency = 0;
 945
 946   RBI (new_bb)->original = bb;
 947   return new_bb;
 948 }
 949 \f
 950 /* Main entry point to this module - initialize the datastructures for
 951    CFG layout changes.  It keeps LOOPS up-to-date if not null.  */
 952
 953 void
 954 cfg_layout_initialize ()
 955 {
 956   /* Our algorithm depends on fact that there are now dead jumptables
 957      around the code.  */
 958   alloc_aux_for_blocks (sizeof (struct reorder_block_def));
 959
 960   cleanup_unconditional_jumps ();
 961
 962   scope_to_insns_initialize ();
 963
 964   record_effective_endpoints ();
 965 }
 966
 967 /* Finalize the changes: reorder insn list according to the sequence, enter
 968    compensation code, rebuild scope forest.  */
 969
 970 void
 971 cfg_layout_finalize ()
 972 {
 973   fixup_fallthru_exit_predecessor ();
 974   fixup_reorder_chain ();
 975
 976 #ifdef ENABLE_CHECKING
 977   verify_insn_chain ();
 978 #endif
 979
 980   scope_to_insns_finalize ();
 981
 982   free_aux_for_blocks ();
 983
 984 #ifdef ENABLE_CHECKING
 985   verify_flow_info ();
 986 #endif
 987 }