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