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 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
 703       /* We got here if we need to add a new jump insn.  */
 704
 705       nb = force_nonfallthru (e_fall);
 706
 707       if (nb)
 708         {
 709           nb->aux = xmalloc (sizeof (struct reorder_block_def));
 710           RBI (nb)->eff_head = nb->head;
 711           RBI (nb)->eff_end = NEXT_INSN (nb->end);
 712           RBI (nb)->scope = RBI (bb)->scope;
 713           RBI (nb)->visited = 1;
 714           RBI (nb)->next = RBI (bb)->next;
 715           RBI (bb)->next = nb;
 716           /* Don't process this new block.  */
 717           bb = nb;
 718         }
 719     }
 720
 721   /* Put basic_block_info in the new order.  */
 722   bb = BASIC_BLOCK (0);
 723   index = 0;
 724
 725   if (rtl_dump_file)
 726     fprintf (rtl_dump_file, "Reordered sequence:\n");
 727   while (bb)
 728     {
 729       if (rtl_dump_file)
 730         fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
 731                  bb->index >= old_n_basic_blocks ? "compensation " : "",
 732                  bb->index,
 733                  bb->frequency);
 734       bb->index = index;
 735       BASIC_BLOCK (index) = bb;
 736
 737       bb = RBI (bb)->next;
 738       index++;
 739     }
 740 }
 741
 742
 743 /* Perform sanity checks on the insn chain.
 744    1. Check that next/prev pointers are consistent in both the forward and
 745       reverse direction.
 746    2. Count insns in chain, going both directions, and check if equal.
 747    3. Check that get_last_insn () returns the actual end of chain.  */
 748
 749 void
 750 verify_insn_chain ()
 751 {
 752   rtx x,
 753       prevx,
 754       nextx;
 755   int insn_cnt1,
 756       insn_cnt2;
 757
 758   prevx = NULL;
 759   insn_cnt1 = 1;
 760   for (x = get_insns (); x; x = NEXT_INSN (x))
 761     {
 762       if (PREV_INSN (x) != prevx)
 763         {
 764           fprintf (stderr, "Forward traversal: insn chain corrupt.\n");
 765           fprintf (stderr, "previous insn:\n");
 766           debug_rtx (prevx);
 767           fprintf (stderr, "current insn:\n");
 768           debug_rtx (x);
 769           abort ();
 770         }
 771       ++insn_cnt1;
 772       prevx = x;
 773     }
 774
 775   if (prevx != get_last_insn ())
 776     {
 777       fprintf (stderr, "last_insn corrupt.\n");
 778       abort ();
 779     }
 780
 781   nextx = NULL;
 782   insn_cnt2 = 1;
 783   for (x = get_last_insn (); x; x = PREV_INSN (x))
 784     {
 785       if (NEXT_INSN (x) != nextx)
 786         {
 787           fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
 788           fprintf (stderr, "current insn:\n");
 789           debug_rtx (x);
 790           fprintf (stderr, "next insn:\n");
 791           debug_rtx (nextx);
 792           abort ();
 793         }
 794       ++insn_cnt2;
 795       nextx = x;
 796     }
 797
 798   if (insn_cnt1 != insn_cnt2)
 799     {
 800       fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
 801                insn_cnt1, insn_cnt2);
 802       abort ();
 803     }
 804 }
 805
 806 static rtx
 807 get_next_bb_note (x)
 808      rtx x;
 809 {
 810   while (x)
 811     {
 812       if (NOTE_INSN_BASIC_BLOCK_P (x))
 813         return x;
 814       x = NEXT_INSN (x);
 815     }
 816   return NULL;
 817 }
 818
 819
 820 static rtx
 821 get_prev_bb_note (x)
 822      rtx x;
 823 {
 824   while (x)
 825     {
 826       if (NOTE_INSN_BASIC_BLOCK_P (x))
 827         return x;
 828       x = PREV_INSN (x);
 829     }
 830   return NULL;
 831 }
 832
 833
 834 /* Determine and record the relationships between basic blocks and
 835    scopes in scope tree S.  */
 836
 837 static void
 838 relate_bbs_with_scopes (s)
 839      scope s;
 840 {
 841   scope p;
 842   int i, bbi1, bbi2, bbs_spanned;
 843   rtx bbnote;
 844
 845   for (p = s->inner; p; p = p->next)
 846     relate_bbs_with_scopes (p);
 847
 848   bbi1 = bbi2 = -1;
 849   bbs_spanned = 0;
 850
 851   /* If the begin and end notes are both inside the same basic block,
 852      or if they are both outside of basic blocks, then we know immediately
 853      how they are related. Otherwise, we need to poke around to make the
 854      determination.  */
 855   if (s->bb_beg != s->bb_end)
 856     {
 857       if (s->bb_beg && s->bb_end)
 858         {
 859           /* Both notes are in different bbs. This implies that all the
 860              basic blocks spanned by the pair of notes are contained in
 861              this scope.  */
 862           bbi1 = s->bb_beg->index;
 863           bbi2 = s->bb_end->index;
 864           bbs_spanned = 1;
 865         }
 866       else if (! s->bb_beg)
 867         {
 868           /* First note is outside of a bb. If the scope spans more than
 869              one basic block, then they all are contained within this
 870              scope. Otherwise, this scope is contained within the basic
 871              block.  */
 872           bbnote = get_next_bb_note (s->note_beg);
 873           if (! bbnote)
 874             abort ();
 875           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
 876             {
 877               bbs_spanned = 0;
 878               s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
 879             }
 880           else
 881             {
 882               bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
 883               bbi2 = s->bb_end->index;
 884               s->bb_end = NULL;
 885               bbs_spanned = 1;
 886             }
 887         }
 888       else /* ! s->bb_end */
 889         {
 890           /* Second note is outside of a bb. If the scope spans more than
 891              one basic block, then they all are contained within this
 892              scope. Otherwise, this scope is contained within the basic
 893              block.  */
 894           bbnote = get_prev_bb_note (s->note_end);
 895           if (! bbnote)
 896             abort ();
 897           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
 898             {
 899               bbs_spanned = 0;
 900               s->bb_end = NOTE_BASIC_BLOCK (bbnote);
 901             }
 902           else
 903             {
 904               bbi1 = s->bb_beg->index;
 905               bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
 906               s->bb_beg = NULL;
 907               bbs_spanned = 1;
 908             }
 909         }
 910     }
 911   else
 912     {
 913       if (s->bb_beg)
 914         /* Both notes are in the same bb, which implies the block
 915            contains this scope.  */
 916         bbs_spanned = 0;
 917       else
 918         {
 919           rtx x1, x2;
 920           /* Both notes are outside of any bbs. This implies that all the
 921              basic blocks spanned by the pair of notes are contained in
 922              this scope.
 923              There is a degenerate case to consider. If the notes do not
 924              span any basic blocks, then it is an empty scope that can
 925              safely be deleted or ignored. Mark these with level = -1.  */
 926
 927           x1 = get_next_bb_note (s->note_beg);
 928           x2 = get_prev_bb_note (s->note_end);
 929           if (! (x1 && x2))
 930             {
 931               s->level = -1;
 932               bbs_spanned = 0;
 933             }
 934           else
 935             {
 936               bbi1 = NOTE_BASIC_BLOCK (x1)->index;
 937               bbi2 = NOTE_BASIC_BLOCK (x2)->index;
 938               bbs_spanned = 1;
 939             }
 940         }
 941     }
 942
 943   /* If the scope spans one or more basic blocks, we record them. We
 944      only record the bbs that are immediately contained within this
 945      scope. Note that if a scope is contained within a bb, we can tell
 946      by checking that bb_beg = bb_end and that they are non-null.  */
 947   if (bbs_spanned)
 948     {
 949       int j = 0;
 950
 951       s->num_bbs = 0;
 952       for (i = bbi1; i <= bbi2; i++)
 953         if (! RBI (BASIC_BLOCK (i))->scope)
 954           s->num_bbs++;
 955
 956       s->bbs = xmalloc (s->num_bbs * sizeof (basic_block));
 957       for (i = bbi1; i <= bbi2; i++)
 958         {
 959           basic_block curr_bb = BASIC_BLOCK (i);
 960           if (! RBI (curr_bb)->scope)
 961             {
 962               s->bbs[j++] = curr_bb;
 963               RBI (curr_bb)->scope = s;
 964             }
 965         }
 966     }
 967   else
 968     s->num_bbs = 0;
 969 }
 970
 971
 972 /* Allocate and initialize a new scope structure with scope level LEVEL,
 973    and record the NOTE beginning the scope.  */
 974
 975 static scope
 976 make_new_scope (level, note)
 977      int level;
 978      rtx note;
 979 {
 980   scope new_scope = xcalloc (1, sizeof (struct scope_def));
 981   new_scope->level = level;
 982   new_scope->note_beg = note;
 983   return new_scope;
 984 }
 985
 986
 987 /* Build a forest representing the scope structure of the function.
 988    Return a pointer to a structure describing the forest.  */
 989
 990 static void
 991 build_scope_forest (forest)
 992     scope_forest_info *forest;
 993 {
 994   rtx x;
 995   int level, bbi, i;
 996   basic_block curr_bb;
 997   scope root, curr_scope = 0;
 998
 999   forest->num_trees = 0;
1000   forest->trees = NULL;
1001   level = -1;
1002   root = NULL;
1003   curr_bb = NULL;
1004   bbi = 0;
1005   for (x = get_insns (); x; x = NEXT_INSN (x))
1006     {
1007       if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
1008         curr_bb = BASIC_BLOCK (bbi);
1009
1010       if (GET_CODE (x) == NOTE)
1011         {
1012           if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
1013             {
1014               if (root)
1015                 {
1016                   scope new_scope;
1017                   if (! curr_scope)
1018                     abort();
1019                   level++;
1020                   new_scope = make_new_scope (level, x);
1021                   new_scope->outer = curr_scope;
1022                   new_scope->next = NULL;
1023                   if (! curr_scope->inner)
1024                     {
1025                       curr_scope->inner = new_scope;
1026                       curr_scope->inner_last = new_scope;
1027                     }
1028                   else
1029                     {
1030                       curr_scope->inner_last->next = new_scope;
1031                       curr_scope->inner_last = new_scope;
1032                     }
1033                   curr_scope = curr_scope->inner_last;
1034                 }
1035               else
1036                 {
1037                   int ntrees = forest->num_trees;
1038                   level++;
1039                   curr_scope = make_new_scope (level, x);
1040                   root = curr_scope;
1041                   forest->trees = xrealloc (forest->trees,
1042                                             sizeof (scope) * (ntrees + 1));
1043                   forest->trees[forest->num_trees++] = root;
1044                 }
1045               curr_scope->bb_beg = curr_bb;
1046             }
1047           else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
1048             {
1049               curr_scope->bb_end = curr_bb;
1050               curr_scope->note_end = x;
1051               level--;
1052               curr_scope = curr_scope->outer;
1053               if (level == -1)
1054                 root = NULL;
1055             }
1056         } /* if note */
1057
1058       if (curr_bb && curr_bb->end == x)
1059         {
1060           curr_bb = NULL;
1061           bbi++;
1062         }
1063
1064     } /* for */
1065
1066   for (i = 0; i < forest->num_trees; i++)
1067     relate_bbs_with_scopes (forest->trees[i]);
1068 }
1069
1070
1071 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1072    the insn chain.  */
1073
1074 static void
1075 remove_scope_notes ()
1076 {
1077   rtx x, next;
1078   basic_block currbb = NULL;
1079
1080   for (x = get_insns (); x; x = next)
1081     {
1082       next = NEXT_INSN (x);
1083       if (NOTE_INSN_BASIC_BLOCK_P (x))
1084         currbb = NOTE_BASIC_BLOCK (x);
1085
1086       if (GET_CODE (x) == NOTE
1087           && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
1088               || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
1089         {
1090           /* Check if the scope note happens to be the end of a bb.  */
1091           if (currbb && x == currbb->end)
1092             currbb->end = PREV_INSN (x);
1093           if (currbb && x == currbb->head)
1094             abort ();
1095
1096           if (PREV_INSN (x))
1097             {
1098               NEXT_INSN (PREV_INSN (x)) = next;
1099               PREV_INSN (next) = PREV_INSN (x);
1100
1101               NEXT_INSN (x) = NULL;
1102               PREV_INSN (x) = NULL;
1103             }
1104           else
1105             abort ();
1106         }
1107     }
1108 }
1109
1110
1111 /* Insert scope note pairs for a contained scope tree S after insn IP.  */
1112
1113 static void
1114 insert_intra_1 (s, ip, bb)
1115      scope s;
1116      rtx *ip;
1117      basic_block bb;
1118 {
1119   scope p;
1120
1121   if (NOTE_BLOCK (s->note_beg))
1122     {
1123       *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
1124       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
1125       if (basic_block_for_insn)
1126         set_block_for_insn (*ip, bb);
1127     }
1128
1129   for (p = s->inner; p; p = p->next)
1130     insert_intra_1 (p, ip, bb);
1131
1132   if (NOTE_BLOCK (s->note_beg))
1133     {
1134       *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
1135       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
1136       if (basic_block_for_insn)
1137         set_block_for_insn (*ip, bb);
1138     }
1139 }
1140
1141
1142 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1143    scopes that are contained within BB.  */
1144
1145 static void
1146 insert_intra_bb_scope_notes (bb)
1147      basic_block bb;
1148 {
1149   scope s = RBI (bb)->scope;
1150   scope p;
1151   rtx ip;
1152
1153   if (! s)
1154     return;
1155
1156   ip = bb->head;
1157   if (GET_CODE (ip) == CODE_LABEL)
1158     ip = NEXT_INSN (ip);
1159
1160   for (p = s->inner; p; p = p->next)
1161     {
1162       if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
1163         insert_intra_1 (p, &ip, bb);
1164     }
1165 }
1166
1167
1168 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1169    insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1170    notes before BB2 such that the notes are correctly balanced. If BB1 or
1171    BB2 is NULL, we are inserting scope notes for the first and last basic
1172    blocks, respectively.  */
1173
1174 static void
1175 insert_inter_bb_scope_notes (bb1, bb2)
1176      basic_block bb1;
1177      basic_block bb2;
1178 {
1179   rtx ip;
1180   scope com;
1181
1182   /* It is possible that a basic block is not contained in any scope.
1183      In that case, we either open or close a scope but not both.  */
1184   if (bb1 && bb2)
1185     {
1186       scope s1 = RBI (bb1)->scope;
1187       scope s2 = RBI (bb2)->scope;
1188       if (! s1 && ! s2)
1189         return;
1190       if (! s1)
1191         bb1 = NULL;
1192       else if (! s2)
1193         bb2 = NULL;
1194     }
1195
1196   /* Find common ancestor scope.  */
1197   if (bb1 && bb2)
1198     {
1199       scope s1 = RBI (bb1)->scope;
1200       scope s2 = RBI (bb2)->scope;
1201       while (s1 != s2)
1202         {
1203           if (! (s1 && s2))
1204             abort ();
1205           if (s1->level > s2->level)
1206             s1 = s1->outer;
1207           else if (s2->level > s1->level)
1208             s2 = s2->outer;
1209           else
1210             {
1211               s1 = s1->outer;
1212               s2 = s2->outer;
1213             }
1214         }
1215       com = s1;
1216     }
1217   else
1218     com = NULL;
1219
1220   /* Close scopes.  */
1221   if (bb1)
1222     {
1223       scope s = RBI (bb1)->scope;
1224       ip = RBI (bb1)->eff_end;
1225       while (s != com)
1226         {
1227           if (NOTE_BLOCK (s->note_beg))
1228             {
1229               ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
1230               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
1231               if (basic_block_for_insn)
1232                 set_block_for_insn (ip, bb1);
1233             }
1234           s = s->outer;
1235         }
1236     }
1237
1238   /* Open scopes.  */
1239   if (bb2)
1240     {
1241       scope s = RBI (bb2)->scope;
1242       ip = bb2->head;
1243       while (s != com)
1244         {
1245           if (NOTE_BLOCK (s->note_beg))
1246             {
1247               ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
1248               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
1249               if (basic_block_for_insn)
1250                 set_block_for_insn (ip, bb2);
1251             }
1252           s = s->outer;
1253         }
1254     }
1255 }
1256
1257
1258 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1259    on the scope forest and the newly reordered basic blocks.  */
1260
1261 static void
1262 rebuild_scope_notes (forest)
1263     scope_forest_info *forest;
1264 {
1265   int i;
1266
1267   if (forest->num_trees == 0)
1268     return;
1269
1270   /* Start by opening the scopes before the first basic block.  */
1271   insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
1272
1273   /* Then, open and close scopes as needed between blocks.  */
1274   for (i = 0; i < n_basic_blocks - 1; i++)
1275     {
1276       basic_block bb1 = BASIC_BLOCK (i);
1277       basic_block bb2 = BASIC_BLOCK (i + 1);
1278       if (RBI (bb1)->scope != RBI (bb2)->scope)
1279         insert_inter_bb_scope_notes (bb1, bb2);
1280       insert_intra_bb_scope_notes (bb1);
1281     }
1282
1283   /* Finally, close the scopes after the last basic block.  */
1284   insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
1285   insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
1286 }
1287
1288
1289 /* Free the storage associated with the scope tree at S.  */
1290
1291 static void
1292 free_scope_forest_1 (s)
1293     scope s;
1294 {
1295   scope p, next;
1296
1297   for (p = s->inner; p; p = next)
1298     {
1299       next = p->next;
1300       free_scope_forest_1 (p);
1301     }
1302
1303   if (s->bbs)
1304     free (s->bbs);
1305   free (s);
1306 }
1307
1308
1309 /* Free the storage associated with the scope forest.  */
1310
1311 static void
1312 free_scope_forest (forest)
1313     scope_forest_info *forest;
1314 {
1315   int i;
1316   for (i = 0; i < forest->num_trees; i++)
1317     free_scope_forest_1 (forest->trees[i]);
1318 }
1319
1320
1321 /* Visualize the scope forest.  */
1322
1323 void
1324 dump_scope_forest (forest)
1325     scope_forest_info *forest;
1326 {
1327   if (forest->num_trees == 0)
1328     fprintf (stderr, "\n< Empty scope forest >\n");
1329   else
1330     {
1331       int i;
1332       fprintf (stderr, "\n< Scope forest >\n");
1333       for (i = 0; i < forest->num_trees; i++)
1334         dump_scope_forest_1 (forest->trees[i], 0);
1335     }
1336 }
1337
1338
1339 /* Recursive portion of dump_scope_forest.  */
1340
1341 static void
1342 dump_scope_forest_1 (s, indent)
1343      scope s;
1344      int indent;
1345 {
1346   scope p;
1347   int i;
1348
1349   if (s->bb_beg != NULL && s->bb_beg == s->bb_end
1350       && RBI (s->bb_beg)->scope
1351       && RBI (s->bb_beg)->scope->level + 1 == s->level)
1352     {
1353       fprintf (stderr, "%*s", indent, "");
1354       fprintf (stderr, "BB%d:\n", s->bb_beg->index);
1355     }
1356
1357   fprintf (stderr, "%*s", indent, "");
1358   fprintf (stderr, "{ level %d (block %p)\n", s->level,
1359            (PTR) NOTE_BLOCK (s->note_beg));
1360
1361   fprintf (stderr, "%*s%s", indent, "", "bbs:");
1362   for (i = 0; i < s->num_bbs; i++)
1363     fprintf (stderr, " %d", s->bbs[i]->index);
1364   fprintf (stderr, "\n");
1365
1366   for (p = s->inner; p; p = p->next)
1367     dump_scope_forest_1 (p, indent + 2);
1368
1369   fprintf (stderr, "%*s", indent, "");
1370   fprintf (stderr, "}\n");
1371 }
1372
1373
1374 /* Reorder basic blocks.  The main entry point to this file.  */
1375
1376 void
1377 reorder_basic_blocks ()
1378 {
1379   scope_forest_info forest;
1380   int i;
1381
1382   if (n_basic_blocks <= 1)
1383     return;
1384
1385   for (i = 0; i < n_basic_blocks; i++)
1386     BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def));
1387
1388   EXIT_BLOCK_PTR->aux = xcalloc (1, sizeof (struct reorder_block_def));
1389
1390   build_scope_forest (&forest);
1391   remove_scope_notes ();
1392
1393   record_effective_endpoints ();
1394   make_reorder_chain ();
1395
1396   if (rtl_dump_file)
1397     dump_flow_info (rtl_dump_file);
1398
1399   fixup_reorder_chain ();
1400
1401 #ifdef ENABLE_CHECKING
1402   verify_insn_chain ();
1403 #endif
1404
1405   rebuild_scope_notes (&forest);
1406   free_scope_forest (&forest);
1407   reorder_blocks ();
1408
1409   for (i = 0; i < n_basic_blocks; i++)
1410     free (BASIC_BLOCK (i)->aux);
1411
1412   free (EXIT_BLOCK_PTR->aux);
1413
1414 #ifdef ENABLE_CHECKING
1415   verify_flow_info ();
1416 #endif
1417 }