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->sindex);
 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_ALL_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;
 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 != num_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   if (rtl_dump_file)
 526     {
 527       fprintf (rtl_dump_file, "Reordered sequence:\n");
 528       for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
 529            bb;
 530            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->sindex);
 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->sindex);
 540           fprintf (rtl_dump_file, " [%i]\n", bb->frequency);
 541         }
 542     }
 543
 544   prev_bb = ENTRY_BLOCK_PTR;
 545   bb = ENTRY_BLOCK_PTR->next_bb;
 546   index = 0;
 547
 548   for (; bb; prev_bb = bb, bb = RBI (bb)->next, index++)
 549     {
 550       bb->sindex = 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   basic_block bb;
 601
 602   FOR_ALL_BB (bb)
 603     {
 604       if (!bb->succ)
 605         continue;
 606       if (bb->succ->flags & EDGE_FALLTHRU)
 607         continue;
 608       if (!bb->succ->succ_next)
 609         {
 610           rtx insn;
 611           if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb)
 612               && bb->prev_bb != ENTRY_BLOCK_PTR)
 613             {
 614               basic_block prev = bb->prev_bb;
 615
 616               if (rtl_dump_file)
 617                 fprintf (rtl_dump_file, "Removing forwarder BB %i\n",
 618                          bb->sindex);
 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->sindex);
 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 = ENTRY_BLOCK_PTR->next_bb;
 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   basic_block src = e->src;
 826   basic_block old_next_bb = src->next_bb;
 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   src->next_bb = NULL;
 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   src->next_bb = old_next_bb;
 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 }