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