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