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