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