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