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