gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000 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
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License 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 /* References:
  22
  23    "Profile Guided Code Positioning"
  24    Pettis and Hanson; PLDI '90.
  25
  26    TODO:
  27
  28    (1) Consider:
  29
  30                 if (p) goto A;          // predict taken
  31                 foo ();
  32               A:
  33                 if (q) goto B;          // predict taken
  34                 bar ();
  35               B:
  36                 baz ();
  37                 return;
  38
  39        We'll currently reorder this as
  40
  41                 if (!p) goto C;
  42               A:
  43                 if (!q) goto D;
  44               B:
  45                 baz ();
  46                 return;
  47               D:
  48                 bar ();
  49                 goto B;
  50               C:
  51                 foo ();
  52                 goto A;
  53
  54        A better ordering is
  55
  56                 if (!p) goto C;
  57                 if (!q) goto D;
  58               B:
  59                 baz ();
  60                 return;
  61               C:
  62                 foo ();
  63                 if (q) goto B;
  64               D:
  65                 bar ();
  66                 goto B;
  67
  68        This requires that we be able to duplicate the jump at A, and
  69        adjust the graph traversal such that greedy placement doesn't
  70        fix D before C is considered.
  71
  72    (2) Coordinate with shorten_branches to minimize the number of
  73        long branches.
  74
  75    (3) Invent a method by which sufficiently non-predicted code can
  76        be moved to either the end of the section or another section
  77        entirely.  Some sort of NOTE_INSN note would work fine.
  78
  79        This completely scroggs all debugging formats, so the user
  80        would have to explicitly ask for it.
  81 */
  82
  83 #include "config.h"
  84 #include "system.h"
  85 #include "tree.h"
  86 #include "rtl.h"
  87 #include "tm_p.h"
  88 #include "hard-reg-set.h"
  89 #include "basic-block.h"
  90 #include "insn-config.h"
  91 #include "regs.h"
  92 #include "flags.h"
  93 #include "output.h"
  94 #include "function.h"
  95 #include "toplev.h"
  96 #include "recog.h"
  97 #include "expr.h"
  98 #include "obstack.h"
  99
 100
 101 #ifndef HAVE_epilogue
 102 #define HAVE_epilogue 0
 103 #endif
 104
 105
 106 /* The contents of the current function definition are allocated
 107    in this obstack, and all are freed at the end of the function.
 108    For top-level functions, this is temporary_obstack.
 109    Separate obstacks are made for nested functions.  */
 110
 111 extern struct obstack flow_obstack;
 112
 113
 114 /* Structure to hold information about lexical scopes.  */
 115 typedef struct scope_def
 116 {
 117   int level;
 118
 119   /* The NOTE_INSN_BLOCK_BEG that started this scope.  */
 120   rtx note_beg;
 121
 122   /* The NOTE_INSN_BLOCK_END that ended this scope.  */
 123   rtx note_end;
 124
 125   /* The bb containing note_beg (if any).  */
 126   basic_block bb_beg;
 127
 128   /* The bb containing note_end (if any).  */
 129   basic_block bb_end;
 130
 131   /* List of basic blocks contained within this scope.  */
 132   basic_block *bbs;
 133
 134   /* Number of blocks contained within this scope.  */
 135   int num_bbs;
 136
 137   /* The outer scope or NULL if outermost scope.  */
 138   struct scope_def *outer;
 139
 140   /* The first inner scope or NULL if innermost scope.  */
 141   struct scope_def *inner;
 142
 143   /* The last inner scope or NULL if innermost scope.  */
 144   struct scope_def *inner_last;
 145
 146   /* Link to the next (sibling) scope.  */
 147   struct scope_def *next;
 148 } *scope;
 149
 150
 151 /* Structure to hold information about the scope forest.  */
 152 typedef struct
 153 {
 154   /* Number of trees in forest.  */
 155   int num_trees;
 156
 157   /* List of tree roots.  */
 158   scope *trees;
 159 } scope_forest_info;
 160
 161 /* Structure to hold information about the blocks during reordering.  */
 162 typedef struct reorder_block_def
 163 {
 164   rtx eff_head;
 165   rtx eff_end;
 166   scope scope;
 167   basic_block next;
 168   int visited;
 169 } *reorder_block_def;
 170
 171 #define RBI(BB) ((reorder_block_def) (BB)->aux)
 172
 173 /* Holds the interesting trailing notes for the function.  */
 174 static rtx function_tail_eff_head;
 175
 176
 177 /* Local function prototypes.  */
 178 static rtx skip_insns_after_block       PARAMS ((basic_block));
 179 static void record_effective_endpoints  PARAMS ((void));
 180 static void make_reorder_chain          PARAMS ((void));
 181 static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
 182 static rtx label_for_bb                 PARAMS ((basic_block));
 183 static rtx emit_jump_to_block_after     PARAMS ((basic_block, rtx));
 184 static void fixup_reorder_chain         PARAMS ((void));
 185 static void relate_bbs_with_scopes      PARAMS ((scope));
 186 static scope make_new_scope             PARAMS ((int, rtx));
 187 static void build_scope_forest          PARAMS ((scope_forest_info *));
 188 static void remove_scope_notes          PARAMS ((void));
 189 static void insert_intra_1              PARAMS ((scope, rtx *, basic_block));
 190 static void insert_intra_bb_scope_notes PARAMS ((basic_block));
 191 static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
 192 static void rebuild_scope_notes         PARAMS ((scope_forest_info *));
 193 static void free_scope_forest_1         PARAMS ((scope));
 194 static void free_scope_forest           PARAMS ((scope_forest_info *));
 195 void dump_scope_forest                  PARAMS ((scope_forest_info *));
 196 static void dump_scope_forest_1         PARAMS ((scope, int));
 197 static rtx get_next_bb_note             PARAMS ((rtx));
 198 static rtx get_prev_bb_note             PARAMS ((rtx));
 199
 200 void verify_insn_chain                  PARAMS ((void));
 201 \f
 202 /* Skip over inter-block insns occurring after BB which are typically
 203    associated with BB (e.g., barriers). If there are any such insns,
 204    we return the last one. Otherwise, we return the end of BB.  */
 205
 206 static rtx
 207 skip_insns_after_block (bb)
 208      basic_block bb;
 209 {
 210   rtx insn, last_insn, next_head, prev;
 211
 212   next_head = NULL_RTX;
 213   if (bb->index + 1 != n_basic_blocks)
 214     next_head = BASIC_BLOCK (bb->index + 1)->head;
 215
 216   for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)); )
 217     {
 218       if (insn == next_head)
 219         break;
 220
 221       switch (GET_CODE (insn))
 222         {
 223         case BARRIER:
 224           last_insn = insn;
 225           continue;
 226
 227         case NOTE:
 228           switch (NOTE_LINE_NUMBER (insn))
 229             {
 230             case NOTE_INSN_LOOP_END:
 231             case NOTE_INSN_BLOCK_END:
 232               last_insn = insn;
 233               continue;
 234             case NOTE_INSN_DELETED:
 235             case NOTE_INSN_DELETED_LABEL:
 236               continue;
 237
 238             default:
 239               continue;
 240               break;
 241             }
 242           break;
 243
 244         case CODE_LABEL:
 245           if (NEXT_INSN (insn)
 246               && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 247               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 248                   || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 249             {
 250               insn = NEXT_INSN (insn);
 251               last_insn = insn;
 252               continue;
 253             }
 254           break;
 255
 256         default:
 257           break;
 258         }
 259
 260       break;
 261     }
 262   /* It is possible to hit contradicting sequence.  For instance:
 263
 264      jump_insn
 265      NOTE_INSN_LOOP_BEG
 266      barrier
 267
 268      Where barrier belongs to jump_insn, but the note does not.
 269      This can be created by removing the basic block originally
 270      following NOTE_INSN_LOOP_BEG.
 271
 272      In such case reorder the notes.  */
 273   for (insn = last_insn; insn != bb->end; insn = prev)
 274     {
 275     prev = PREV_INSN (insn);
 276     if (GET_CODE (insn) == NOTE)
 277       switch (NOTE_LINE_NUMBER (insn))
 278         {
 279           case NOTE_INSN_LOOP_END:
 280           case NOTE_INSN_BLOCK_END:
 281           case NOTE_INSN_DELETED:
 282           case NOTE_INSN_DELETED_LABEL:
 283         continue;
 284           default:
 285         reorder_insns (insn, insn, last_insn);
 286         }
 287     }
 288
 289   return last_insn;
 290 }
 291
 292
 293 /* Locate the effective beginning and end of the insn chain for each
 294    block, as defined by skip_insns_after_block above.  */
 295
 296 static void
 297 record_effective_endpoints ()
 298 {
 299   rtx next_insn = get_insns ();
 300   int i;
 301
 302   for (i = 0; i < n_basic_blocks; ++i)
 303     {
 304       basic_block bb = BASIC_BLOCK (i);
 305       rtx end;
 306
 307       RBI (bb)->eff_head = next_insn;
 308       end = skip_insns_after_block (bb);
 309       RBI (bb)->eff_end = end;
 310       next_insn = NEXT_INSN (end);
 311     }
 312   function_tail_eff_head = next_insn;
 313 }
 314
 315
 316 /* Compute an ordering for a subgraph beginning with block BB.  Record the
 317    ordering in RBI()->index and chained through RBI()->next.  */
 318
 319 static void
 320 make_reorder_chain ()
 321 {
 322   basic_block last_block = NULL;
 323   basic_block prev = NULL;
 324   int nbb_m1 = n_basic_blocks - 1;
 325   basic_block next;
 326
 327   /* If we've not got epilogue in RTL, we must fallthru to the exit.
 328      Force the last block to be at the end.  */
 329   /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
 330      end of the function for stack unwinding purposes.  */
 331   if (! HAVE_epilogue)
 332     {
 333       last_block = BASIC_BLOCK (nbb_m1);
 334       RBI (last_block)->visited = 1;
 335       nbb_m1 -= 1;
 336     }
 337
 338   /* Loop until we've placed every block.  */
 339   do
 340     {
 341       int i;
 342
 343       next = NULL;
 344
 345       /* Find the next unplaced block.  */
 346       /* ??? Get rid of this loop, and track which blocks are not yet
 347          placed more directly, so as to avoid the O(N^2) worst case.
 348          Perhaps keep a doubly-linked list of all to-be-placed blocks;
 349          remove from the list as we place.  The head of that list is
 350          what we're looking for here.  */
 351
 352       for (i = 0; i <= nbb_m1 && !next; ++i)
 353         {
 354           basic_block bb = BASIC_BLOCK (i);
 355           if (! RBI (bb)->visited)
 356             next = bb;
 357         }
 358       if (next)
 359         prev = make_reorder_chain_1 (next, prev);
 360     }
 361   while (next);
 362
 363   /* Terminate the chain.  */
 364   if (! HAVE_epilogue)
 365     {
 366       RBI (prev)->next = last_block;
 367       prev = last_block;
 368     }
 369   RBI (prev)->next = NULL;
 370 }
 371
 372 /* A helper function for make_reorder_chain.
 373
 374    We do not follow EH edges, or non-fallthru edges to noreturn blocks.
 375    These are assumed to be the error condition and we wish to cluster
 376    all of them at the very end of the function for the benefit of cache
 377    locality for the rest of the function.
 378
 379    ??? We could do slightly better by noticing earlier that some subgraph
 380    has all paths leading to noreturn functions, but for there to be more
 381    than one block in such a subgraph is rare.  */
 382
 383 static basic_block
 384 make_reorder_chain_1 (bb, prev)
 385      basic_block bb;
 386      basic_block prev;
 387 {
 388   edge e;
 389   basic_block next;
 390   rtx note;
 391
 392   /* Mark this block visited.  */
 393   if (prev)
 394     {
 395  restart:
 396       RBI (prev)->next = bb;
 397
 398       if (rtl_dump_file && prev->index + 1 != bb->index)
 399         fprintf (rtl_dump_file, "Reordering block %d after %d\n",
 400                  bb->index, prev->index);
 401     }
 402   else
 403     {
 404       if (bb->index != 0)
 405         abort ();
 406     }
 407   RBI (bb)->visited = 1;
 408   prev = bb;
 409
 410   if (bb->succ == NULL)
 411     return prev;
 412
 413   /* Find the most probable block.  */
 414
 415   next = NULL;
 416   if (any_condjump_p (bb->end)
 417       && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
 418     {
 419       int taken, probability;
 420       edge e_taken, e_fall;
 421
 422       probability = INTVAL (XEXP (note, 0));
 423       taken = probability > REG_BR_PROB_BASE / 2;
 424
 425       /* Find the normal taken edge and the normal fallthru edge.
 426
 427          Note, conditional jumps with other side effects may not
 428          be fully optimized.  In this case it is possible for
 429          the conditional jump to branch to the same location as
 430          the fallthru path.
 431
 432          We should probably work to improve optimization of that
 433          case; however, it seems silly not to also deal with such
 434          problems here if they happen to occur.  */
 435
 436       e_taken = e_fall = NULL;
 437       for (e = bb->succ; e ; e = e->succ_next)
 438         {
 439           if (e->flags & EDGE_FALLTHRU)
 440             e_fall = e;
 441           else if (! (e->flags & EDGE_EH))
 442             e_taken = e;
 443         }
 444
 445       next = (taken ? e_taken : e_fall)->dest;
 446     }
 447
 448   /* In the absence of a prediction, disturb things as little as possible
 449      by selecting the old "next" block from the list of successors.  If
 450      there had been a fallthru edge, that will be the one.  */
 451   if (! next)
 452     {
 453       for (e = bb->succ; e ; e = e->succ_next)
 454         if (e->dest->index == bb->index + 1)
 455           {
 456             if ((e->flags & EDGE_FALLTHRU)
 457                 || (e->dest->succ
 458                     && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))))
 459               next = e->dest;
 460             break;
 461           }
 462     }
 463
 464   /* Make sure we didn't select a silly next block.  */
 465   if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
 466     next = NULL;
 467
 468   /* Recurse on the successors.  Unroll the last call, as the normal
 469      case is exactly one or two edges, and we can tail recurse.  */
 470   for (e = bb->succ; e; e = e->succ_next)
 471     if (e->dest != EXIT_BLOCK_PTR
 472         && ! RBI (e->dest)->visited
 473         && e->dest->succ
 474         && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
 475       {
 476         if (next)
 477           {
 478             prev = make_reorder_chain_1 (next, prev);
 479             next = RBI (e->dest)->visited ? NULL : e->dest;
 480           }
 481         else
 482           next = e->dest;
 483       }
 484   if (next)
 485     {
 486       bb = next;
 487       goto restart;
 488     }
 489
 490   return prev;
 491 }
 492
 493
 494 /* Locate or create a label for a given basic block.  */
 495
 496 static rtx
 497 label_for_bb (bb)
 498      basic_block bb;
 499 {
 500   rtx label = bb->head;
 501
 502   if (GET_CODE (label) != CODE_LABEL)
 503     {
 504       if (rtl_dump_file)
 505         fprintf (rtl_dump_file, "Emitting label for block %d\n",
 506                  bb->index);
 507
 508       label = emit_label_before (gen_label_rtx (), label);
 509       if (bb->head == RBI (bb)->eff_head)
 510         RBI (bb)->eff_head = label;
 511       bb->head = label;
 512       if (basic_block_for_insn)
 513         set_block_for_insn (label, bb);
 514     }
 515
 516   return label;
 517 }
 518
 519
 520 /* Emit a jump to BB after insn AFTER.  */
 521
 522 static rtx
 523 emit_jump_to_block_after (bb, after)
 524      basic_block bb;
 525      rtx after;
 526 {
 527   rtx jump;
 528
 529   if (bb != EXIT_BLOCK_PTR)
 530     {
 531       rtx label = label_for_bb (bb);
 532       jump = emit_jump_insn_after (gen_jump (label), after);
 533       JUMP_LABEL (jump) = label;
 534       LABEL_NUSES (label) += 1;
 535       if (basic_block_for_insn)
 536         set_block_for_new_insns (jump, bb);
 537
 538       if (rtl_dump_file)
 539         fprintf (rtl_dump_file, "Emitting jump to block %d\n",
 540                  bb->index);
 541     }
 542   else
 543     {
 544 #ifdef HAVE_return
 545       if (! HAVE_return)
 546         abort ();
 547       jump = emit_jump_insn_after (gen_return (), after);
 548       if (basic_block_for_insn)
 549         set_block_for_new_insns (jump, bb);
 550
 551       if (rtl_dump_file)
 552         fprintf (rtl_dump_file, "Emitting return\n");
 553 #else
 554       abort ();
 555 #endif
 556     }
 557
 558   return jump;
 559 }
 560
 561
 562 /* Given a reorder chain, rearrange the code to match.  */
 563
 564 static void
 565 fixup_reorder_chain ()
 566 {
 567   basic_block bb, last_bb;
 568   int index;
 569   rtx insn;
 570   int old_n_basic_blocks = n_basic_blocks;
 571
 572   /* First do the bulk reordering -- rechain the blocks without regard to
 573      the needed changes to jumps and labels.  */
 574
 575   last_bb = BASIC_BLOCK (0);
 576   bb = RBI (last_bb)->next;
 577   index = 1;
 578   while (bb)
 579     {
 580       rtx last_e = RBI (last_bb)->eff_end;
 581       rtx curr_h = RBI (bb)->eff_head;
 582
 583       NEXT_INSN (last_e) = curr_h;
 584       PREV_INSN (curr_h) = last_e;
 585
 586       last_bb = bb;
 587       bb = RBI (bb)->next;
 588       index++;
 589     }
 590
 591   if (index != n_basic_blocks)
 592     abort ();
 593
 594   insn = RBI (last_bb)->eff_end;
 595
 596   NEXT_INSN (insn) = function_tail_eff_head;
 597   if (function_tail_eff_head)
 598     PREV_INSN (function_tail_eff_head) = insn;
 599
 600   while (NEXT_INSN (insn))
 601     insn = NEXT_INSN (insn);
 602   set_last_insn (insn);
 603 #ifdef ENABLE_CHECKING
 604   verify_insn_chain ();
 605 #endif
 606
 607   /* Now add jumps and labels as needed to match the blocks new
 608      outgoing edges.  */
 609
 610   for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
 611     {
 612       edge e_fall, e_taken, e;
 613       rtx jump_insn, barrier_insn, bb_end_insn;
 614       basic_block nb;
 615
 616       if (bb->succ == NULL)
 617         continue;
 618
 619       /* Find the old fallthru edge, and another non-EH edge for
 620          a taken jump.  */
 621       e_taken = e_fall = NULL;
 622       for (e = bb->succ; e ; e = e->succ_next)
 623         if (e->flags & EDGE_FALLTHRU)
 624           e_fall = e;
 625         else if (! (e->flags & EDGE_EH))
 626           e_taken = e;
 627
 628       bb_end_insn = bb->end;
 629       if (GET_CODE (bb_end_insn) == JUMP_INSN)
 630         {
 631           if (any_condjump_p (bb_end_insn))
 632             {
 633               /* If the old fallthru is still next, nothing to do.  */
 634               if (RBI (bb)->next == e_fall->dest
 635                   || (!RBI (bb)->next
 636                       && e_fall->dest == EXIT_BLOCK_PTR))
 637                 continue;
 638
 639               /* There is one special case: if *neither* block is next,
 640                  such as happens at the very end of a function, then we'll
 641                  need to add a new unconditional jump.  Choose the taken
 642                  edge based on known or assumed probability.  */
 643               if (RBI (bb)->next != e_taken->dest)
 644                 {
 645                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 646                   if (note
 647                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 648                       && invert_jump (bb_end_insn,
 649                                       label_for_bb (e_fall->dest), 0))
 650                     {
 651                       e_fall->flags &= ~EDGE_FALLTHRU;
 652                       e_taken->flags |= EDGE_FALLTHRU;
 653                       e = e_fall, e_fall = e_taken, e_taken = e;
 654                     }
 655                 }
 656
 657               /* Otherwise we can try to invert the jump.  This will
 658                  basically never fail, however, keep up the pretense.  */
 659               else if (invert_jump (bb_end_insn,
 660                                     label_for_bb (e_fall->dest), 0))
 661                 {
 662                   e_fall->flags &= ~EDGE_FALLTHRU;
 663                   e_taken->flags |= EDGE_FALLTHRU;
 664                   continue;
 665                 }
 666             }
 667           else if (returnjump_p (bb_end_insn))
 668             continue;
 669           else
 670             {
 671               /* Otherwise we have some switch or computed jump.  In the
 672                  99% case, there should not have been a fallthru edge.  */
 673               if (! e_fall)
 674                 continue;
 675 #ifdef CASE_DROPS_THROUGH
 676               /* Except for VAX.  Since we didn't have predication for the
 677                  tablejump, the fallthru block should not have moved.  */
 678               if (RBI (bb)->next == e_fall->dest)
 679                 continue;
 680               bb_end_insn = skip_insns_after_block (bb);
 681 #else
 682               abort ();
 683 #endif
 684             }
 685         }
 686       else
 687         {
 688           /* No fallthru implies a noreturn function with EH edges, or
 689              something similarly bizarre.  In any case, we don't need to
 690              do anything.  */
 691           if (! e_fall)
 692             continue;
 693
 694           /* If the fallthru block is still next, nothing to do.  */
 695           if (RBI (bb)->next == e_fall->dest)
 696             continue;
 697
 698           /* An fallthru to exit block.  */
 699           if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
 700             continue;
 701
 702           /* We need a new jump insn.  If the block has only one outgoing
 703              edge, then we can stuff the new jump insn in directly.  */
 704           if (bb->succ->succ_next == NULL)
 705             {
 706               e_fall->flags &= ~EDGE_FALLTHRU;
 707
 708               jump_insn = emit_jump_to_block_after (e_fall->dest, bb_end_insn);
 709               bb->end = jump_insn;
 710               barrier_insn = emit_barrier_after (jump_insn);
 711               RBI (bb)->eff_end = barrier_insn;
 712               continue;
 713             }
 714         }
 715
 716       /* We got here if we need to add a new jump insn in a new block
 717          across the edge e_fall.  */
 718
 719       jump_insn = emit_jump_to_block_after (e_fall->dest, bb_end_insn);
 720       barrier_insn = emit_barrier_after (jump_insn);
 721
 722       VARRAY_GROW (basic_block_info, ++n_basic_blocks);
 723       create_basic_block (n_basic_blocks - 1, jump_insn, jump_insn, NULL);
 724
 725       nb = BASIC_BLOCK (n_basic_blocks - 1);
 726       nb->local_set = 0;
 727       nb->count = e_fall->count;
 728       nb->frequency = EDGE_FREQUENCY (e_fall);
 729
 730       nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 731       nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 732       COPY_REG_SET (nb->global_live_at_start, bb->global_live_at_start);
 733       COPY_REG_SET (nb->global_live_at_end, bb->global_live_at_start);
 734
 735       nb->aux = xmalloc (sizeof (struct reorder_block_def));
 736       RBI (nb)->eff_head = nb->head;
 737       RBI (nb)->eff_end = barrier_insn;
 738       RBI (nb)->scope = RBI (bb)->scope;
 739       RBI (nb)->visited = 1;
 740       RBI (nb)->next = RBI (bb)->next;
 741       RBI (bb)->next = nb;
 742
 743       /* Link to new block.  */
 744       make_single_succ_edge (nb, e_fall->dest, 0);
 745       redirect_edge_succ (e_fall, nb);
 746
 747       /* Don't process this new block.  */
 748       bb = nb;
 749     }
 750
 751   /* Put basic_block_info in the new order.  */
 752   bb = BASIC_BLOCK (0);
 753   index = 0;
 754
 755   if (rtl_dump_file)
 756     fprintf (rtl_dump_file, "Reordered sequence:\n");
 757   while (bb)
 758     {
 759       if (rtl_dump_file)
 760         fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
 761                  bb->index >= old_n_basic_blocks ? "compensation " : "",
 762                  bb->index,
 763                  bb->frequency);
 764       bb->index = index;
 765       BASIC_BLOCK (index) = bb;
 766
 767       bb = RBI (bb)->next;
 768       index++;
 769     }
 770 }
 771
 772
 773 /* Perform sanity checks on the insn chain.
 774    1. Check that next/prev pointers are consistent in both the forward and
 775       reverse direction.
 776    2. Count insns in chain, going both directions, and check if equal.
 777    3. Check that get_last_insn () returns the actual end of chain.  */
 778
 779 void
 780 verify_insn_chain ()
 781 {
 782   rtx x,
 783       prevx,
 784       nextx;
 785   int insn_cnt1,
 786       insn_cnt2;
 787
 788   prevx = NULL;
 789   insn_cnt1 = 1;
 790   for (x = get_insns (); x; x = NEXT_INSN (x))
 791     {
 792       if (PREV_INSN (x) != prevx)
 793         {
 794           fprintf (stderr, "Forward traversal: insn chain corrupt.\n");
 795           fprintf (stderr, "previous insn:\n");
 796           debug_rtx (prevx);
 797           fprintf (stderr, "current insn:\n");
 798           debug_rtx (x);
 799           abort ();
 800         }
 801       ++insn_cnt1;
 802       prevx = x;
 803     }
 804
 805   if (prevx != get_last_insn ())
 806     {
 807       fprintf (stderr, "last_insn corrupt.\n");
 808       abort ();
 809     }
 810
 811   nextx = NULL;
 812   insn_cnt2 = 1;
 813   for (x = get_last_insn (); x; x = PREV_INSN (x))
 814     {
 815       if (NEXT_INSN (x) != nextx)
 816         {
 817           fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
 818           fprintf (stderr, "current insn:\n");
 819           debug_rtx (x);
 820           fprintf (stderr, "next insn:\n");
 821           debug_rtx (nextx);
 822           abort ();
 823         }
 824       ++insn_cnt2;
 825       nextx = x;
 826     }
 827
 828   if (insn_cnt1 != insn_cnt2)
 829     {
 830       fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
 831                insn_cnt1, insn_cnt2);
 832       abort ();
 833     }
 834 }
 835
 836 static rtx
 837 get_next_bb_note (x)
 838      rtx x;
 839 {
 840   while (x)
 841     {
 842       if (NOTE_INSN_BASIC_BLOCK_P (x))
 843         return x;
 844       x = NEXT_INSN (x);
 845     }
 846   return NULL;
 847 }
 848
 849
 850 static rtx
 851 get_prev_bb_note (x)
 852      rtx x;
 853 {
 854   while (x)
 855     {
 856       if (NOTE_INSN_BASIC_BLOCK_P (x))
 857         return x;
 858       x = PREV_INSN (x);
 859     }
 860   return NULL;
 861 }
 862
 863
 864 /* Determine and record the relationships between basic blocks and
 865    scopes in scope tree S.  */
 866
 867 static void
 868 relate_bbs_with_scopes (s)
 869      scope s;
 870 {
 871   scope p;
 872   int i, bbi1, bbi2, bbs_spanned;
 873   rtx bbnote;
 874
 875   for (p = s->inner; p; p = p->next)
 876     relate_bbs_with_scopes (p);
 877
 878   bbi1 = bbi2 = -1;
 879   bbs_spanned = 0;
 880
 881   /* If the begin and end notes are both inside the same basic block,
 882      or if they are both outside of basic blocks, then we know immediately
 883      how they are related. Otherwise, we need to poke around to make the
 884      determination.  */
 885   if (s->bb_beg != s->bb_end)
 886     {
 887       if (s->bb_beg && s->bb_end)
 888         {
 889           /* Both notes are in different bbs. This implies that all the
 890              basic blocks spanned by the pair of notes are contained in
 891              this scope.  */
 892           bbi1 = s->bb_beg->index;
 893           bbi2 = s->bb_end->index;
 894           bbs_spanned = 1;
 895         }
 896       else if (! s->bb_beg)
 897         {
 898           /* First note is outside of a bb. If the scope spans more than
 899              one basic block, then they all are contained within this
 900              scope. Otherwise, this scope is contained within the basic
 901              block.  */
 902           bbnote = get_next_bb_note (s->note_beg);
 903           if (! bbnote)
 904             abort ();
 905           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
 906             {
 907               bbs_spanned = 0;
 908               s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
 909             }
 910           else
 911             {
 912               bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
 913               bbi2 = s->bb_end->index;
 914               s->bb_end = NULL;
 915               bbs_spanned = 1;
 916             }
 917         }
 918       else /* ! s->bb_end */
 919         {
 920           /* Second note is outside of a bb. If the scope spans more than
 921              one basic block, then they all are contained within this
 922              scope. Otherwise, this scope is contained within the basic
 923              block.  */
 924           bbnote = get_prev_bb_note (s->note_end);
 925           if (! bbnote)
 926             abort ();
 927           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
 928             {
 929               bbs_spanned = 0;
 930               s->bb_end = NOTE_BASIC_BLOCK (bbnote);
 931             }
 932           else
 933             {
 934               bbi1 = s->bb_beg->index;
 935               bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
 936               s->bb_beg = NULL;
 937               bbs_spanned = 1;
 938             }
 939         }
 940     }
 941   else
 942     {
 943       if (s->bb_beg)
 944         /* Both notes are in the same bb, which implies the block
 945            contains this scope.  */
 946         bbs_spanned = 0;
 947       else
 948         {
 949           rtx x1, x2;
 950           /* Both notes are outside of any bbs. This implies that all the
 951              basic blocks spanned by the pair of notes are contained in
 952              this scope.
 953              There is a degenerate case to consider. If the notes do not
 954              span any basic blocks, then it is an empty scope that can
 955              safely be deleted or ignored. Mark these with level = -1.  */
 956
 957           x1 = get_next_bb_note (s->note_beg);
 958           x2 = get_prev_bb_note (s->note_end);
 959           if (! (x1 && x2))
 960             {
 961               s->level = -1;
 962               bbs_spanned = 0;
 963             }
 964           else
 965             {
 966               bbi1 = NOTE_BASIC_BLOCK (x1)->index;
 967               bbi2 = NOTE_BASIC_BLOCK (x2)->index;
 968               bbs_spanned = 1;
 969             }
 970         }
 971     }
 972
 973   /* If the scope spans one or more basic blocks, we record them. We
 974      only record the bbs that are immediately contained within this
 975      scope. Note that if a scope is contained within a bb, we can tell
 976      by checking that bb_beg = bb_end and that they are non-null.  */
 977   if (bbs_spanned)
 978     {
 979       int j = 0;
 980
 981       s->num_bbs = 0;
 982       for (i = bbi1; i <= bbi2; i++)
 983         if (! RBI (BASIC_BLOCK (i))->scope)
 984           s->num_bbs++;
 985
 986       s->bbs = xmalloc (s->num_bbs * sizeof (basic_block));
 987       for (i = bbi1; i <= bbi2; i++)
 988         {
 989           basic_block curr_bb = BASIC_BLOCK (i);
 990           if (! RBI (curr_bb)->scope)
 991             {
 992               s->bbs[j++] = curr_bb;
 993               RBI (curr_bb)->scope = s;
 994             }
 995         }
 996     }
 997   else
 998     s->num_bbs = 0;
 999 }
1000
1001
1002 /* Allocate and initialize a new scope structure with scope level LEVEL,
1003    and record the NOTE beginning the scope.  */
1004
1005 static scope
1006 make_new_scope (level, note)
1007      int level;
1008      rtx note;
1009 {
1010   scope new_scope = xcalloc (1, sizeof (struct scope_def));
1011   new_scope->level = level;
1012   new_scope->note_beg = note;
1013   return new_scope;
1014 }
1015
1016
1017 /* Build a forest representing the scope structure of the function.
1018    Return a pointer to a structure describing the forest.  */
1019
1020 static void
1021 build_scope_forest (forest)
1022     scope_forest_info *forest;
1023 {
1024   rtx x;
1025   int level, bbi, i;
1026   basic_block curr_bb;
1027   scope root, curr_scope = 0;
1028
1029   forest->num_trees = 0;
1030   forest->trees = NULL;
1031   level = -1;
1032   root = NULL;
1033   curr_bb = NULL;
1034   bbi = 0;
1035   for (x = get_insns (); x; x = NEXT_INSN (x))
1036     {
1037       if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
1038         curr_bb = BASIC_BLOCK (bbi);
1039
1040       if (GET_CODE (x) == NOTE)
1041         {
1042           if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
1043             {
1044               if (root)
1045                 {
1046                   scope new_scope;
1047                   if (! curr_scope)
1048                     abort();
1049                   level++;
1050                   new_scope = make_new_scope (level, x);
1051                   new_scope->outer = curr_scope;
1052                   new_scope->next = NULL;
1053                   if (! curr_scope->inner)
1054                     {
1055                       curr_scope->inner = new_scope;
1056                       curr_scope->inner_last = new_scope;
1057                     }
1058                   else
1059                     {
1060                       curr_scope->inner_last->next = new_scope;
1061                       curr_scope->inner_last = new_scope;
1062                     }
1063                   curr_scope = curr_scope->inner_last;
1064                 }
1065               else
1066                 {
1067                   int ntrees = forest->num_trees;
1068                   level++;
1069                   curr_scope = make_new_scope (level, x);
1070                   root = curr_scope;
1071                   forest->trees = xrealloc (forest->trees,
1072                                             sizeof (scope) * (ntrees + 1));
1073                   forest->trees[forest->num_trees++] = root;
1074                 }
1075               curr_scope->bb_beg = curr_bb;
1076             }
1077           else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
1078             {
1079               curr_scope->bb_end = curr_bb;
1080               curr_scope->note_end = x;
1081               level--;
1082               curr_scope = curr_scope->outer;
1083               if (level == -1)
1084                 root = NULL;
1085             }
1086         } /* if note */
1087
1088       if (curr_bb && curr_bb->end == x)
1089         {
1090           curr_bb = NULL;
1091           bbi++;
1092         }
1093
1094     } /* for */
1095
1096   for (i = 0; i < forest->num_trees; i++)
1097     relate_bbs_with_scopes (forest->trees[i]);
1098 }
1099
1100
1101 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1102    the insn chain.  */
1103
1104 static void
1105 remove_scope_notes ()
1106 {
1107   rtx x, next;
1108   basic_block currbb = NULL;
1109
1110   for (x = get_insns (); x; x = next)
1111     {
1112       next = NEXT_INSN (x);
1113       if (NOTE_INSN_BASIC_BLOCK_P (x))
1114         currbb = NOTE_BASIC_BLOCK (x);
1115
1116       if (GET_CODE (x) == NOTE
1117           && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
1118               || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
1119         {
1120           /* Check if the scope note happens to be the end of a bb.  */
1121           if (currbb && x == currbb->end)
1122             currbb->end = PREV_INSN (x);
1123           if (currbb && x == currbb->head)
1124             abort ();
1125
1126           if (PREV_INSN (x))
1127             {
1128               NEXT_INSN (PREV_INSN (x)) = next;
1129               PREV_INSN (next) = PREV_INSN (x);
1130
1131               NEXT_INSN (x) = NULL;
1132               PREV_INSN (x) = NULL;
1133             }
1134           else
1135             abort ();
1136         }
1137     }
1138 }
1139
1140
1141 /* Insert scope note pairs for a contained scope tree S after insn IP.  */
1142
1143 static void
1144 insert_intra_1 (s, ip, bb)
1145      scope s;
1146      rtx *ip;
1147      basic_block bb;
1148 {
1149   scope p;
1150
1151   if (NOTE_BLOCK (s->note_beg))
1152     {
1153       *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
1154       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
1155       if (basic_block_for_insn)
1156         set_block_for_insn (*ip, bb);
1157     }
1158
1159   for (p = s->inner; p; p = p->next)
1160     insert_intra_1 (p, ip, bb);
1161
1162   if (NOTE_BLOCK (s->note_beg))
1163     {
1164       *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
1165       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
1166       if (basic_block_for_insn)
1167         set_block_for_insn (*ip, bb);
1168     }
1169 }
1170
1171
1172 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1173    scopes that are contained within BB.  */
1174
1175 static void
1176 insert_intra_bb_scope_notes (bb)
1177      basic_block bb;
1178 {
1179   scope s = RBI (bb)->scope;
1180   scope p;
1181   rtx ip;
1182
1183   if (! s)
1184     return;
1185
1186   ip = bb->head;
1187   if (GET_CODE (ip) == CODE_LABEL)
1188     ip = NEXT_INSN (ip);
1189
1190   for (p = s->inner; p; p = p->next)
1191     {
1192       if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
1193         insert_intra_1 (p, &ip, bb);
1194     }
1195 }
1196
1197
1198 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1199    insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1200    notes before BB2 such that the notes are correctly balanced. If BB1 or
1201    BB2 is NULL, we are inserting scope notes for the first and last basic
1202    blocks, respectively.  */
1203
1204 static void
1205 insert_inter_bb_scope_notes (bb1, bb2)
1206      basic_block bb1;
1207      basic_block bb2;
1208 {
1209   rtx ip;
1210   scope com;
1211
1212   /* It is possible that a basic block is not contained in any scope.
1213      In that case, we either open or close a scope but not both.  */
1214   if (bb1 && bb2)
1215     {
1216       scope s1 = RBI (bb1)->scope;
1217       scope s2 = RBI (bb2)->scope;
1218       if (! s1 && ! s2)
1219         return;
1220       if (! s1)
1221         bb1 = NULL;
1222       else if (! s2)
1223         bb2 = NULL;
1224     }
1225
1226   /* Find common ancestor scope.  */
1227   if (bb1 && bb2)
1228     {
1229       scope s1 = RBI (bb1)->scope;
1230       scope s2 = RBI (bb2)->scope;
1231       while (s1 != s2)
1232         {
1233           if (! (s1 && s2))
1234             abort ();
1235           if (s1->level > s2->level)
1236             s1 = s1->outer;
1237           else if (s2->level > s1->level)
1238             s2 = s2->outer;
1239           else
1240             {
1241               s1 = s1->outer;
1242               s2 = s2->outer;
1243             }
1244         }
1245       com = s1;
1246     }
1247   else
1248     com = NULL;
1249
1250   /* Close scopes.  */
1251   if (bb1)
1252     {
1253       scope s = RBI (bb1)->scope;
1254       ip = RBI (bb1)->eff_end;
1255       while (s != com)
1256         {
1257           if (NOTE_BLOCK (s->note_beg))
1258             {
1259               ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
1260               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
1261               if (basic_block_for_insn)
1262                 set_block_for_insn (ip, bb1);
1263             }
1264           s = s->outer;
1265         }
1266     }
1267
1268   /* Open scopes.  */
1269   if (bb2)
1270     {
1271       scope s = RBI (bb2)->scope;
1272       ip = bb2->head;
1273       while (s != com)
1274         {
1275           if (NOTE_BLOCK (s->note_beg))
1276             {
1277               ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
1278               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
1279               if (basic_block_for_insn)
1280                 set_block_for_insn (ip, bb2);
1281             }
1282           s = s->outer;
1283         }
1284     }
1285 }
1286
1287
1288 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1289    on the scope forest and the newly reordered basic blocks.  */
1290
1291 static void
1292 rebuild_scope_notes (forest)
1293     scope_forest_info *forest;
1294 {
1295   int i;
1296
1297   if (forest->num_trees == 0)
1298     return;
1299
1300   /* Start by opening the scopes before the first basic block.  */
1301   insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
1302
1303   /* Then, open and close scopes as needed between blocks.  */
1304   for (i = 0; i < n_basic_blocks - 1; i++)
1305     {
1306       basic_block bb1 = BASIC_BLOCK (i);
1307       basic_block bb2 = BASIC_BLOCK (i + 1);
1308       if (RBI (bb1)->scope != RBI (bb2)->scope)
1309         insert_inter_bb_scope_notes (bb1, bb2);
1310       insert_intra_bb_scope_notes (bb1);
1311     }
1312
1313   /* Finally, close the scopes after the last basic block.  */
1314   insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
1315   insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
1316 }
1317
1318
1319 /* Free the storage associated with the scope tree at S.  */
1320
1321 static void
1322 free_scope_forest_1 (s)
1323     scope s;
1324 {
1325   scope p, next;
1326
1327   for (p = s->inner; p; p = next)
1328     {
1329       next = p->next;
1330       free_scope_forest_1 (p);
1331     }
1332
1333   if (s->bbs)
1334     free (s->bbs);
1335   free (s);
1336 }
1337
1338
1339 /* Free the storage associated with the scope forest.  */
1340
1341 static void
1342 free_scope_forest (forest)
1343     scope_forest_info *forest;
1344 {
1345   int i;
1346   for (i = 0; i < forest->num_trees; i++)
1347     free_scope_forest_1 (forest->trees[i]);
1348 }
1349
1350
1351 /* Visualize the scope forest.  */
1352
1353 void
1354 dump_scope_forest (forest)
1355     scope_forest_info *forest;
1356 {
1357   if (forest->num_trees == 0)
1358     fprintf (stderr, "\n< Empty scope forest >\n");
1359   else
1360     {
1361       int i;
1362       fprintf (stderr, "\n< Scope forest >\n");
1363       for (i = 0; i < forest->num_trees; i++)
1364         dump_scope_forest_1 (forest->trees[i], 0);
1365     }
1366 }
1367
1368
1369 /* Recursive portion of dump_scope_forest.  */
1370
1371 static void
1372 dump_scope_forest_1 (s, indent)
1373      scope s;
1374      int indent;
1375 {
1376   scope p;
1377   int i;
1378
1379   if (s->bb_beg != NULL && s->bb_beg == s->bb_end
1380       && RBI (s->bb_beg)->scope
1381       && RBI (s->bb_beg)->scope->level + 1 == s->level)
1382     {
1383       fprintf (stderr, "%*s", indent, "");
1384       fprintf (stderr, "BB%d:\n", s->bb_beg->index);
1385     }
1386
1387   fprintf (stderr, "%*s", indent, "");
1388   fprintf (stderr, "{ level %d (block %p)\n", s->level,
1389            (PTR) NOTE_BLOCK (s->note_beg));
1390
1391   fprintf (stderr, "%*s%s", indent, "", "bbs:");
1392   for (i = 0; i < s->num_bbs; i++)
1393     fprintf (stderr, " %d", s->bbs[i]->index);
1394   fprintf (stderr, "\n");
1395
1396   for (p = s->inner; p; p = p->next)
1397     dump_scope_forest_1 (p, indent + 2);
1398
1399   fprintf (stderr, "%*s", indent, "");
1400   fprintf (stderr, "}\n");
1401 }
1402
1403
1404 /* Reorder basic blocks.  The main entry point to this file.  */
1405
1406 void
1407 reorder_basic_blocks ()
1408 {
1409   scope_forest_info forest;
1410   int i;
1411
1412   if (n_basic_blocks <= 1)
1413     return;
1414
1415   for (i = 0; i < n_basic_blocks; i++)
1416     BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def));
1417
1418   EXIT_BLOCK_PTR->aux = xcalloc (1, sizeof (struct reorder_block_def));
1419
1420   build_scope_forest (&forest);
1421   remove_scope_notes ();
1422
1423   record_effective_endpoints ();
1424   make_reorder_chain ();
1425
1426   if (rtl_dump_file)
1427     dump_flow_info (rtl_dump_file);
1428
1429   fixup_reorder_chain ();
1430
1431 #ifdef ENABLE_CHECKING
1432   verify_insn_chain ();
1433 #endif
1434
1435   rebuild_scope_notes (&forest);
1436   free_scope_forest (&forest);
1437   reorder_blocks ();
1438
1439   for (i = 0; i < n_basic_blocks; i++)
1440     free (BASIC_BLOCK (i)->aux);
1441
1442   free (EXIT_BLOCK_PTR->aux);
1443
1444 #ifdef ENABLE_CHECKING
1445   verify_flow_info ();
1446 #endif
1447 }