gcc/bb-reorder.c

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