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