gcc/cfglayout.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000, 2001 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 #include "config.h"
  22 #include "system.h"
  23 #include "rtl.h"
  24 #include "hard-reg-set.h"
  25 #include "basic-block.h"
  26 #include "insn-config.h"
  27 #include "output.h"
  28 #include "function.h"
  29 #include "obstack.h"
  30 #include "cfglayout.h"
  31
  32 /* The contents of the current function definition are allocated
  33    in this obstack, and all are freed at the end of the function.
  34    For top-level functions, this is temporary_obstack.
  35    Separate obstacks are made for nested functions.  */
  36
  37 extern struct obstack flow_obstack;
  38
  39 /* Structure to hold information about lexical scopes.  */
  40 struct scope_def
  41 {
  42   int level;
  43
  44   /* The NOTE_INSN_BLOCK_BEG that started this scope.  */
  45   rtx note_beg;
  46
  47   /* The NOTE_INSN_BLOCK_END that ended this scope.  */
  48   rtx note_end;
  49
  50   /* The bb containing note_beg (if any).  */
  51   basic_block bb_beg;
  52
  53   /* The bb containing note_end (if any).  */
  54   basic_block bb_end;
  55
  56   /* List of basic blocks contained within this scope.  */
  57   basic_block *bbs;
  58
  59   /* Number of blocks contained within this scope.  */
  60   int num_bbs;
  61
  62   /* The outer scope or NULL if outermost scope.  */
  63   struct scope_def *outer;
  64
  65   /* The first inner scope or NULL if innermost scope.  */
  66   struct scope_def *inner;
  67
  68   /* The last inner scope or NULL if innermost scope.  */
  69   struct scope_def *inner_last;
  70
  71   /* Link to the next (sibling) scope.  */
  72   struct scope_def *next;
  73 };
  74
  75 /* Structure to hold information about the scope forest.  */
  76 typedef struct
  77 {
  78   /* Number of trees in forest.  */
  79   int num_trees;
  80
  81   /* List of tree roots.  */
  82   scope *trees;
  83 } scope_forest_info;
  84
  85 /* Holds the interesting trailing notes for the function.  */
  86 static rtx function_tail_eff_head;
  87
  88 /* The scope forest of current function.  */
  89 static scope_forest_info forest;
  90
  91 static rtx skip_insns_after_block       PARAMS ((basic_block));
  92 static void record_effective_endpoints  PARAMS ((void));
  93 static rtx label_for_bb                 PARAMS ((basic_block));
  94 static void fixup_reorder_chain         PARAMS ((void));
  95
  96 static void relate_bbs_with_scopes      PARAMS ((scope));
  97 static scope make_new_scope             PARAMS ((int, rtx));
  98 static void build_scope_forest          PARAMS ((scope_forest_info *));
  99 static void remove_scope_notes          PARAMS ((void));
 100 static void insert_intra_1              PARAMS ((scope, rtx *, basic_block));
 101 static void insert_intra_bb_scope_notes PARAMS ((basic_block));
 102 static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
 103 static void rebuild_scope_notes         PARAMS ((scope_forest_info *));
 104 static void free_scope_forest_1         PARAMS ((scope));
 105 static void free_scope_forest           PARAMS ((scope_forest_info *));
 106 void dump_scope_forest                  PARAMS ((scope_forest_info *));
 107 static void dump_scope_forest_1         PARAMS ((scope, int));
 108
 109 static rtx get_next_bb_note             PARAMS ((rtx));
 110 static rtx get_prev_bb_note             PARAMS ((rtx));
 111
 112 void verify_insn_chain                  PARAMS ((void));
 113 static void fixup_fallthru_exit_predecessor PARAMS ((void));
 114 \f
 115 /* Skip over inter-block insns occurring after BB which are typically
 116    associated with BB (e.g., barriers). If there are any such insns,
 117    we return the last one. Otherwise, we return the end of BB.  */
 118
 119 static rtx
 120 skip_insns_after_block (bb)
 121      basic_block bb;
 122 {
 123   rtx insn, last_insn, next_head, prev;
 124
 125   next_head = NULL_RTX;
 126   if (bb->index + 1 != n_basic_blocks)
 127     next_head = BASIC_BLOCK (bb->index + 1)->head;
 128
 129   for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)); )
 130     {
 131       if (insn == next_head)
 132         break;
 133
 134       switch (GET_CODE (insn))
 135         {
 136         case BARRIER:
 137           last_insn = insn;
 138           continue;
 139
 140         case NOTE:
 141           switch (NOTE_LINE_NUMBER (insn))
 142             {
 143             case NOTE_INSN_LOOP_END:
 144             case NOTE_INSN_BLOCK_END:
 145               last_insn = insn;
 146               continue;
 147             case NOTE_INSN_DELETED:
 148             case NOTE_INSN_DELETED_LABEL:
 149               continue;
 150
 151             default:
 152               continue;
 153               break;
 154             }
 155           break;
 156
 157         case CODE_LABEL:
 158           if (NEXT_INSN (insn)
 159               && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 160               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 161                   || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 162             {
 163               insn = NEXT_INSN (insn);
 164               last_insn = insn;
 165               continue;
 166             }
 167           break;
 168
 169         default:
 170           break;
 171         }
 172
 173       break;
 174     }
 175   /* It is possible to hit contradicting sequence.  For instance:
 176
 177      jump_insn
 178      NOTE_INSN_LOOP_BEG
 179      barrier
 180
 181      Where barrier belongs to jump_insn, but the note does not.
 182      This can be created by removing the basic block originally
 183      following NOTE_INSN_LOOP_BEG.
 184
 185      In such case reorder the notes.  */
 186   for (insn = last_insn; insn != bb->end; insn = prev)
 187     {
 188     prev = PREV_INSN (insn);
 189     if (GET_CODE (insn) == NOTE)
 190       switch (NOTE_LINE_NUMBER (insn))
 191         {
 192           case NOTE_INSN_LOOP_END:
 193           case NOTE_INSN_BLOCK_END:
 194           case NOTE_INSN_DELETED:
 195           case NOTE_INSN_DELETED_LABEL:
 196         continue;
 197           default:
 198         reorder_insns (insn, insn, last_insn);
 199         }
 200     }
 201
 202   return last_insn;
 203 }
 204
 205 /* Locate or create a label for a given basic block.  */
 206
 207 static rtx
 208 label_for_bb (bb)
 209      basic_block bb;
 210 {
 211   rtx label = bb->head;
 212
 213   if (GET_CODE (label) != CODE_LABEL)
 214     {
 215       if (rtl_dump_file)
 216         fprintf (rtl_dump_file, "Emitting label for block %d\n",
 217                  bb->index);
 218
 219       label = block_label (bb);
 220       if (bb->head == PREV_INSN (RBI (bb)->eff_head))
 221         RBI (bb)->eff_head = label;
 222     }
 223
 224   return label;
 225 }
 226
 227 /* Locate the effective beginning and end of the insn chain for each
 228    block, as defined by skip_insns_after_block above.  */
 229
 230 static void
 231 record_effective_endpoints ()
 232 {
 233   rtx next_insn = get_insns ();
 234   int i;
 235
 236   for (i = 0; i < n_basic_blocks; ++i)
 237     {
 238       basic_block bb = BASIC_BLOCK (i);
 239       rtx end;
 240
 241       RBI (bb)->eff_head = next_insn;
 242       end = skip_insns_after_block (bb);
 243       RBI (bb)->eff_end = end;
 244       next_insn = NEXT_INSN (end);
 245     }
 246   function_tail_eff_head = next_insn;
 247 }
 248 \f
 249 static rtx
 250 get_next_bb_note (x)
 251      rtx x;
 252 {
 253   while (x)
 254     {
 255       if (NOTE_INSN_BASIC_BLOCK_P (x))
 256         return x;
 257       x = NEXT_INSN (x);
 258     }
 259   return NULL;
 260 }
 261
 262 static rtx
 263 get_prev_bb_note (x)
 264      rtx x;
 265 {
 266   while (x)
 267     {
 268       if (NOTE_INSN_BASIC_BLOCK_P (x))
 269         return x;
 270       x = PREV_INSN (x);
 271     }
 272   return NULL;
 273 }
 274
 275 /* Determine and record the relationships between basic blocks and
 276    scopes in scope tree S.  */
 277
 278 static void
 279 relate_bbs_with_scopes (s)
 280      scope s;
 281 {
 282   scope p;
 283   int i, bbi1, bbi2, bbs_spanned;
 284   rtx bbnote;
 285
 286   for (p = s->inner; p; p = p->next)
 287     relate_bbs_with_scopes (p);
 288
 289   bbi1 = bbi2 = -1;
 290   bbs_spanned = 0;
 291
 292   /* If the begin and end notes are both inside the same basic block,
 293      or if they are both outside of basic blocks, then we know immediately
 294      how they are related. Otherwise, we need to poke around to make the
 295      determination.  */
 296   if (s->bb_beg != s->bb_end)
 297     {
 298       if (s->bb_beg && s->bb_end)
 299         {
 300           /* Both notes are in different bbs. This implies that all the
 301              basic blocks spanned by the pair of notes are contained in
 302              this scope.  */
 303           bbi1 = s->bb_beg->index;
 304           bbi2 = s->bb_end->index;
 305           bbs_spanned = 1;
 306         }
 307       else if (! s->bb_beg)
 308         {
 309           /* First note is outside of a bb. If the scope spans more than
 310              one basic block, then they all are contained within this
 311              scope. Otherwise, this scope is contained within the basic
 312              block.  */
 313           bbnote = get_next_bb_note (s->note_beg);
 314           if (! bbnote)
 315             abort ();
 316           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
 317             {
 318               bbs_spanned = 0;
 319               s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
 320             }
 321           else
 322             {
 323               bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
 324               bbi2 = s->bb_end->index;
 325               s->bb_end = NULL;
 326               bbs_spanned = 1;
 327             }
 328         }
 329       else /* ! s->bb_end */
 330         {
 331           /* Second note is outside of a bb. If the scope spans more than
 332              one basic block, then they all are contained within this
 333              scope. Otherwise, this scope is contained within the basic
 334              block.  */
 335           bbnote = get_prev_bb_note (s->note_end);
 336           if (! bbnote)
 337             abort ();
 338           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
 339             {
 340               bbs_spanned = 0;
 341               s->bb_end = NOTE_BASIC_BLOCK (bbnote);
 342             }
 343           else
 344             {
 345               bbi1 = s->bb_beg->index;
 346               bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
 347               s->bb_beg = NULL;
 348               bbs_spanned = 1;
 349             }
 350         }
 351     }
 352   else
 353     {
 354       if (s->bb_beg)
 355         /* Both notes are in the same bb, which implies the block
 356            contains this scope.  */
 357         bbs_spanned = 0;
 358       else
 359         {
 360           rtx x1, x2;
 361           /* Both notes are outside of any bbs. This implies that all the
 362              basic blocks spanned by the pair of notes are contained in
 363              this scope.
 364              There is a degenerate case to consider. If the notes do not
 365              span any basic blocks, then it is an empty scope that can
 366              safely be deleted or ignored. Mark these with level = -1.  */
 367
 368           x1 = get_next_bb_note (s->note_beg);
 369           x2 = get_prev_bb_note (s->note_end);
 370           if (! (x1 && x2))
 371             {
 372               s->level = -1;
 373               bbs_spanned = 0;
 374             }
 375           else
 376             {
 377               bbi1 = NOTE_BASIC_BLOCK (x1)->index;
 378               bbi2 = NOTE_BASIC_BLOCK (x2)->index;
 379               bbs_spanned = 1;
 380             }
 381         }
 382     }
 383
 384   /* If the scope spans one or more basic blocks, we record them. We
 385      only record the bbs that are immediately contained within this
 386      scope. Note that if a scope is contained within a bb, we can tell
 387      by checking that bb_beg = bb_end and that they are non-null.  */
 388   if (bbs_spanned)
 389     {
 390       int j = 0;
 391
 392       s->num_bbs = 0;
 393       for (i = bbi1; i <= bbi2; i++)
 394         if (! RBI (BASIC_BLOCK (i))->scope)
 395           s->num_bbs++;
 396
 397       s->bbs = xmalloc (s->num_bbs * sizeof (basic_block));
 398       for (i = bbi1; i <= bbi2; i++)
 399         {
 400           basic_block curr_bb = BASIC_BLOCK (i);
 401           if (! RBI (curr_bb)->scope)
 402             {
 403               s->bbs[j++] = curr_bb;
 404               RBI (curr_bb)->scope = s;
 405             }
 406         }
 407     }
 408   else
 409     s->num_bbs = 0;
 410 }
 411
 412 /* Allocate and initialize a new scope structure with scope level LEVEL,
 413    and record the NOTE beginning the scope.  */
 414
 415 static scope
 416 make_new_scope (level, note)
 417      int level;
 418      rtx note;
 419 {
 420   scope new_scope = xcalloc (1, sizeof (struct scope_def));
 421   new_scope->level = level;
 422   new_scope->note_beg = note;
 423   return new_scope;
 424 }
 425
 426
 427 /* Build a forest representing the scope structure of the function.
 428    Return a pointer to a structure describing the forest.  */
 429
 430 static void
 431 build_scope_forest (forest)
 432     scope_forest_info *forest;
 433 {
 434   rtx x;
 435   int level, bbi, i;
 436   basic_block curr_bb;
 437   scope root, curr_scope = 0;
 438
 439   forest->num_trees = 0;
 440   forest->trees = NULL;
 441   level = -1;
 442   root = NULL;
 443   curr_bb = NULL;
 444   bbi = 0;
 445   for (x = get_insns (); x; x = NEXT_INSN (x))
 446     {
 447       if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
 448         curr_bb = BASIC_BLOCK (bbi);
 449
 450       if (GET_CODE (x) == NOTE)
 451         {
 452           if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
 453             {
 454               if (root)
 455                 {
 456                   scope new_scope;
 457                   if (! curr_scope)
 458                     abort();
 459                   level++;
 460                   new_scope = make_new_scope (level, x);
 461                   new_scope->outer = curr_scope;
 462                   new_scope->next = NULL;
 463                   if (! curr_scope->inner)
 464                     {
 465                       curr_scope->inner = new_scope;
 466                       curr_scope->inner_last = new_scope;
 467                     }
 468                   else
 469                     {
 470                       curr_scope->inner_last->next = new_scope;
 471                       curr_scope->inner_last = new_scope;
 472                     }
 473                   curr_scope = curr_scope->inner_last;
 474                 }
 475               else
 476                 {
 477                   int ntrees = forest->num_trees;
 478                   level++;
 479                   curr_scope = make_new_scope (level, x);
 480                   root = curr_scope;
 481                   forest->trees = xrealloc (forest->trees,
 482                                             sizeof (scope) * (ntrees + 1));
 483                   forest->trees[forest->num_trees++] = root;
 484                 }
 485               curr_scope->bb_beg = curr_bb;
 486             }
 487           else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
 488             {
 489               curr_scope->bb_end = curr_bb;
 490               curr_scope->note_end = x;
 491               level--;
 492               curr_scope = curr_scope->outer;
 493               if (level == -1)
 494                 root = NULL;
 495             }
 496         } /* if note */
 497
 498       if (curr_bb && curr_bb->end == x)
 499         {
 500           curr_bb = NULL;
 501           bbi++;
 502         }
 503
 504     } /* for */
 505
 506   for (i = 0; i < forest->num_trees; i++)
 507     relate_bbs_with_scopes (forest->trees[i]);
 508 }
 509 \f
 510 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
 511    the insn chain.  */
 512
 513 static void
 514 remove_scope_notes ()
 515 {
 516   rtx x, next;
 517   basic_block currbb = NULL;
 518
 519   for (x = get_insns (); x; x = next)
 520     {
 521       next = NEXT_INSN (x);
 522       if (NOTE_INSN_BASIC_BLOCK_P (x))
 523         currbb = NOTE_BASIC_BLOCK (x);
 524
 525       if (GET_CODE (x) == NOTE
 526           && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
 527               || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
 528         {
 529           /* Check if the scope note happens to be the end of a bb.  */
 530           if (currbb && x == currbb->end)
 531             currbb->end = PREV_INSN (x);
 532           if (currbb && x == currbb->head)
 533             abort ();
 534
 535           if (PREV_INSN (x))
 536             {
 537               NEXT_INSN (PREV_INSN (x)) = next;
 538               PREV_INSN (next) = PREV_INSN (x);
 539
 540               NEXT_INSN (x) = NULL;
 541               PREV_INSN (x) = NULL;
 542             }
 543           else
 544             abort ();
 545         }
 546     }
 547 }
 548 \f
 549 /* Insert scope note pairs for a contained scope tree S after insn IP.  */
 550
 551 static void
 552 insert_intra_1 (s, ip, bb)
 553      scope s;
 554      rtx *ip;
 555      basic_block bb;
 556 {
 557   scope p;
 558
 559   if (NOTE_BLOCK (s->note_beg))
 560     {
 561       *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
 562       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
 563     }
 564
 565   for (p = s->inner; p; p = p->next)
 566     insert_intra_1 (p, ip, bb);
 567
 568   if (NOTE_BLOCK (s->note_beg))
 569     {
 570       *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
 571       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
 572     }
 573 }
 574
 575
 576 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
 577    scopes that are contained within BB.  */
 578
 579 static void
 580 insert_intra_bb_scope_notes (bb)
 581      basic_block bb;
 582 {
 583   scope s = RBI (bb)->scope;
 584   scope p;
 585   rtx ip;
 586
 587   if (! s)
 588     return;
 589
 590   ip = bb->head;
 591   if (GET_CODE (ip) == CODE_LABEL)
 592     ip = NEXT_INSN (ip);
 593
 594   for (p = s->inner; p; p = p->next)
 595     {
 596       if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
 597         insert_intra_1 (p, &ip, bb);
 598     }
 599 }
 600
 601
 602 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
 603    insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
 604    notes before BB2 such that the notes are correctly balanced. If BB1 or
 605    BB2 is NULL, we are inserting scope notes for the first and last basic
 606    blocks, respectively.  */
 607
 608 static void
 609 insert_inter_bb_scope_notes (bb1, bb2)
 610      basic_block bb1;
 611      basic_block bb2;
 612 {
 613   rtx ip;
 614   scope com;
 615
 616   /* It is possible that a basic block is not contained in any scope.
 617      In that case, we either open or close a scope but not both.  */
 618   if (bb1 && bb2)
 619     {
 620       scope s1 = RBI (bb1)->scope;
 621       scope s2 = RBI (bb2)->scope;
 622       if (! s1 && ! s2)
 623         return;
 624       if (! s1)
 625         bb1 = NULL;
 626       else if (! s2)
 627         bb2 = NULL;
 628     }
 629
 630   /* Find common ancestor scope.  */
 631   if (bb1 && bb2)
 632     {
 633       scope s1 = RBI (bb1)->scope;
 634       scope s2 = RBI (bb2)->scope;
 635       while (s1 != s2)
 636         {
 637           if (! (s1 && s2))
 638             abort ();
 639           if (s1->level > s2->level)
 640             s1 = s1->outer;
 641           else if (s2->level > s1->level)
 642             s2 = s2->outer;
 643           else
 644             {
 645               s1 = s1->outer;
 646               s2 = s2->outer;
 647             }
 648         }
 649       com = s1;
 650     }
 651   else
 652     com = NULL;
 653
 654   /* Close scopes.  */
 655   if (bb1)
 656     {
 657       rtx end = bb1->end;
 658
 659       scope s = RBI (bb1)->scope;
 660       ip = RBI (bb1)->eff_end;
 661       while (s != com)
 662         {
 663           if (NOTE_BLOCK (s->note_beg))
 664             {
 665               ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
 666               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
 667             }
 668           s = s->outer;
 669         }
 670       /* Emitting note may move the end of basic block to unwanted place.  */
 671       bb1->end = end;
 672     }
 673
 674   /* Open scopes.  */
 675   if (bb2)
 676     {
 677       scope s = RBI (bb2)->scope;
 678       ip = bb2->head;
 679       while (s != com)
 680         {
 681           if (NOTE_BLOCK (s->note_beg))
 682             {
 683               ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
 684               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
 685             }
 686           s = s->outer;
 687         }
 688     }
 689 }
 690
 691
 692 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
 693    on the scope forest and the newly reordered basic blocks.  */
 694
 695 static void
 696 rebuild_scope_notes (forest)
 697     scope_forest_info *forest;
 698 {
 699   int i;
 700
 701   if (forest->num_trees == 0)
 702     return;
 703
 704   /* Start by opening the scopes before the first basic block.  */
 705   insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
 706
 707   /* Then, open and close scopes as needed between blocks.  */
 708   for (i = 0; i < n_basic_blocks - 1; i++)
 709     {
 710       basic_block bb1 = BASIC_BLOCK (i);
 711       basic_block bb2 = BASIC_BLOCK (i + 1);
 712       if (RBI (bb1)->scope != RBI (bb2)->scope)
 713         insert_inter_bb_scope_notes (bb1, bb2);
 714       insert_intra_bb_scope_notes (bb1);
 715     }
 716
 717   /* Finally, close the scopes after the last basic block.  */
 718   insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
 719   insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
 720 }
 721 \f
 722 /* Free the storage associated with the scope tree at S.  */
 723
 724 static void
 725 free_scope_forest_1 (s)
 726     scope s;
 727 {
 728   scope p, next;
 729
 730   for (p = s->inner; p; p = next)
 731     {
 732       next = p->next;
 733       free_scope_forest_1 (p);
 734     }
 735
 736   if (s->bbs)
 737     free (s->bbs);
 738   free (s);
 739 }
 740
 741 /* Free the storage associated with the scope forest.  */
 742
 743 static void
 744 free_scope_forest (forest)
 745     scope_forest_info *forest;
 746 {
 747   int i;
 748   for (i = 0; i < forest->num_trees; i++)
 749     free_scope_forest_1 (forest->trees[i]);
 750 }
 751 \f
 752 /* Visualize the scope forest.  */
 753
 754 void
 755 dump_scope_forest (forest)
 756     scope_forest_info *forest;
 757 {
 758   if (forest->num_trees == 0)
 759     fprintf (stderr, "\n< Empty scope forest >\n");
 760   else
 761     {
 762       int i;
 763       fprintf (stderr, "\n< Scope forest >\n");
 764       for (i = 0; i < forest->num_trees; i++)
 765         dump_scope_forest_1 (forest->trees[i], 0);
 766     }
 767 }
 768
 769 /* Recursive portion of dump_scope_forest.  */
 770
 771 static void
 772 dump_scope_forest_1 (s, indent)
 773      scope s;
 774      int indent;
 775 {
 776   scope p;
 777   int i;
 778
 779   if (s->bb_beg != NULL && s->bb_beg == s->bb_end
 780       && RBI (s->bb_beg)->scope
 781       && RBI (s->bb_beg)->scope->level + 1 == s->level)
 782     {
 783       fprintf (stderr, "%*s", indent, "");
 784       fprintf (stderr, "BB%d:\n", s->bb_beg->index);
 785     }
 786
 787   fprintf (stderr, "%*s", indent, "");
 788   fprintf (stderr, "{ level %d (block %p)\n", s->level,
 789            (PTR) NOTE_BLOCK (s->note_beg));
 790
 791   fprintf (stderr, "%*s%s", indent, "", "bbs:");
 792   for (i = 0; i < s->num_bbs; i++)
 793     fprintf (stderr, " %d", s->bbs[i]->index);
 794   fprintf (stderr, "\n");
 795
 796   for (p = s->inner; p; p = p->next)
 797     dump_scope_forest_1 (p, indent + 2);
 798
 799   fprintf (stderr, "%*s", indent, "");
 800   fprintf (stderr, "}\n");
 801 }
 802 \f
 803 /* Given a reorder chain, rearrange the code to match.  */
 804
 805 static void
 806 fixup_reorder_chain ()
 807 {
 808   basic_block bb, last_bb;
 809   int index;
 810   rtx insn;
 811   int old_n_basic_blocks = n_basic_blocks;
 812
 813   /* First do the bulk reordering -- rechain the blocks without regard to
 814      the needed changes to jumps and labels.  */
 815
 816   last_bb = BASIC_BLOCK (0);
 817   bb = RBI (last_bb)->next;
 818   index = 1;
 819   while (bb)
 820     {
 821       rtx last_e = RBI (last_bb)->eff_end;
 822       rtx curr_h = RBI (bb)->eff_head;
 823
 824       NEXT_INSN (last_e) = curr_h;
 825       PREV_INSN (curr_h) = last_e;
 826
 827       last_bb = bb;
 828       bb = RBI (bb)->next;
 829       index++;
 830     }
 831
 832   if (index != n_basic_blocks)
 833     abort ();
 834
 835   insn = RBI (last_bb)->eff_end;
 836
 837   NEXT_INSN (insn) = function_tail_eff_head;
 838   if (function_tail_eff_head)
 839     PREV_INSN (function_tail_eff_head) = insn;
 840
 841   while (NEXT_INSN (insn))
 842     insn = NEXT_INSN (insn);
 843   set_last_insn (insn);
 844 #ifdef ENABLE_CHECKING
 845   verify_insn_chain ();
 846 #endif
 847
 848   /* Now add jumps and labels as needed to match the blocks new
 849      outgoing edges.  */
 850
 851   for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
 852     {
 853       edge e_fall, e_taken, e;
 854       rtx bb_end_insn;
 855       basic_block nb;
 856
 857       if (bb->succ == NULL)
 858         continue;
 859
 860       /* Find the old fallthru edge, and another non-EH edge for
 861          a taken jump.  */
 862       e_taken = e_fall = NULL;
 863       for (e = bb->succ; e ; e = e->succ_next)
 864         if (e->flags & EDGE_FALLTHRU)
 865           e_fall = e;
 866         else if (! (e->flags & EDGE_EH))
 867           e_taken = e;
 868
 869       bb_end_insn = bb->end;
 870       if (GET_CODE (bb_end_insn) == JUMP_INSN)
 871         {
 872           if (any_condjump_p (bb_end_insn))
 873             {
 874               /* If the old fallthru is still next, nothing to do.  */
 875               if (RBI (bb)->next == e_fall->dest
 876                   || (!RBI (bb)->next
 877                       && e_fall->dest == EXIT_BLOCK_PTR))
 878                 continue;
 879
 880               /* There is one special case: if *neither* block is next,
 881                  such as happens at the very end of a function, then we'll
 882                  need to add a new unconditional jump.  Choose the taken
 883                  edge based on known or assumed probability.  */
 884               if (RBI (bb)->next != e_taken->dest)
 885                 {
 886                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 887                   if (note
 888                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 889                       && invert_jump (bb_end_insn,
 890                                       label_for_bb (e_fall->dest), 0))
 891                     {
 892                       e_fall->flags &= ~EDGE_FALLTHRU;
 893                       e_taken->flags |= EDGE_FALLTHRU;
 894                       e = e_fall, e_fall = e_taken, e_taken = e;
 895                     }
 896                 }
 897
 898               /* Otherwise we can try to invert the jump.  This will
 899                  basically never fail, however, keep up the pretense.  */
 900               else if (invert_jump (bb_end_insn,
 901                                     label_for_bb (e_fall->dest), 0))
 902                 {
 903                   e_fall->flags &= ~EDGE_FALLTHRU;
 904                   e_taken->flags |= EDGE_FALLTHRU;
 905                   continue;
 906                 }
 907             }
 908           else if (returnjump_p (bb_end_insn))
 909             continue;
 910           else
 911             {
 912               /* Otherwise we have some switch or computed jump.  In the
 913                  99% case, there should not have been a fallthru edge.  */
 914               if (! e_fall)
 915                 continue;
 916 #ifdef CASE_DROPS_THROUGH
 917               /* Except for VAX.  Since we didn't have predication for the
 918                  tablejump, the fallthru block should not have moved.  */
 919               if (RBI (bb)->next == e_fall->dest)
 920                 continue;
 921               bb_end_insn = skip_insns_after_block (bb);
 922 #else
 923               abort ();
 924 #endif
 925             }
 926         }
 927       else
 928         {
 929           /* No fallthru implies a noreturn function with EH edges, or
 930              something similarly bizarre.  In any case, we don't need to
 931              do anything.  */
 932           if (! e_fall)
 933             continue;
 934
 935           /* If the fallthru block is still next, nothing to do.  */
 936           if (RBI (bb)->next == e_fall->dest)
 937             continue;
 938
 939           /* An fallthru to exit block.  */
 940           if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
 941             continue;
 942         }
 943
 944       /* We got here if we need to add a new jump insn.  */
 945
 946       nb = force_nonfallthru (e_fall);
 947
 948       if (nb)
 949         {
 950           alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
 951           RBI (nb)->eff_head = nb->head;
 952           RBI (nb)->eff_end = NEXT_INSN (nb->end);
 953           RBI (nb)->scope = RBI (bb)->scope;
 954           RBI (nb)->visited = 1;
 955           RBI (nb)->next = RBI (bb)->next;
 956           RBI (bb)->next = nb;
 957           /* Don't process this new block.  */
 958           bb = nb;
 959         }
 960     }
 961
 962   /* Put basic_block_info in the new order.  */
 963   bb = BASIC_BLOCK (0);
 964   index = 0;
 965
 966   if (rtl_dump_file)
 967     fprintf (rtl_dump_file, "Reordered sequence:\n");
 968   while (bb)
 969     {
 970       if (rtl_dump_file)
 971         fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
 972                  bb->index >= old_n_basic_blocks ? "compensation " : "",
 973                  bb->index,
 974                  bb->frequency);
 975       bb->index = index;
 976       BASIC_BLOCK (index) = bb;
 977
 978       bb = RBI (bb)->next;
 979       index++;
 980     }
 981 }
 982 \f
 983 /* Perform sanity checks on the insn chain.
 984    1. Check that next/prev pointers are consistent in both the forward and
 985       reverse direction.
 986    2. Count insns in chain, going both directions, and check if equal.
 987    3. Check that get_last_insn () returns the actual end of chain.  */
 988
 989 void
 990 verify_insn_chain ()
 991 {
 992   rtx x,
 993       prevx,
 994       nextx;
 995   int insn_cnt1,
 996       insn_cnt2;
 997
 998   prevx = NULL;
 999   insn_cnt1 = 1;
1000   for (x = get_insns (); x; x = NEXT_INSN (x))
1001     {
1002       if (PREV_INSN (x) != prevx)
1003         {
1004           fprintf (stderr, "Forward traversal: insn chain corrupt.\n");
1005           fprintf (stderr, "previous insn:\n");
1006           debug_rtx (prevx);
1007           fprintf (stderr, "current insn:\n");
1008           debug_rtx (x);
1009           abort ();
1010         }
1011       ++insn_cnt1;
1012       prevx = x;
1013     }
1014
1015   if (prevx != get_last_insn ())
1016     {
1017       fprintf (stderr, "last_insn corrupt.\n");
1018       abort ();
1019     }
1020
1021   nextx = NULL;
1022   insn_cnt2 = 1;
1023   for (x = get_last_insn (); x; x = PREV_INSN (x))
1024     {
1025       if (NEXT_INSN (x) != nextx)
1026         {
1027           fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
1028           fprintf (stderr, "current insn:\n");
1029           debug_rtx (x);
1030           fprintf (stderr, "next insn:\n");
1031           debug_rtx (nextx);
1032           abort ();
1033         }
1034       ++insn_cnt2;
1035       nextx = x;
1036     }
1037
1038   if (insn_cnt1 != insn_cnt2)
1039     {
1040       fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
1041                insn_cnt1, insn_cnt2);
1042       abort ();
1043     }
1044 }
1045
1046 /* The block falling through to exit must be the last one in the
1047    reordered chain.  Ensure that this condition is met.  */
1048 static void
1049 fixup_fallthru_exit_predecessor ()
1050 {
1051   edge e;
1052   basic_block bb = NULL;
1053
1054   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
1055     if (e->flags & EDGE_FALLTHRU)
1056       bb = e->src;
1057   if (bb && RBI (bb)->next)
1058     {
1059       basic_block c = BASIC_BLOCK (0);
1060       while (RBI (c)->next != bb)
1061         c = RBI (c)->next;
1062       RBI (c)->next = RBI (bb)->next;
1063       while (RBI (c)->next)
1064         c = RBI (c)->next;
1065       RBI (c)->next = bb;
1066       RBI (bb)->next = NULL;
1067     }
1068 }
1069 \f
1070 /* Main entry point to this module - initialize the datastructures for
1071    CFG layout changes.  */
1072
1073 void
1074 cfg_layout_initialize ()
1075 {
1076   alloc_aux_for_blocks (sizeof (struct reorder_block_def));
1077
1078   build_scope_forest (&forest);
1079   remove_scope_notes ();
1080
1081   record_effective_endpoints ();
1082 }
1083
1084 /* Finalize the changes - reorder insn list according to the sequence,
1085    enter compensation code, rebuild scope forest.  */
1086
1087 void
1088 cfg_layout_finalize ()
1089 {
1090   fixup_fallthru_exit_predecessor ();
1091   fixup_reorder_chain ();
1092 #ifdef ENABLE_CHECKING
1093   verify_insn_chain ();
1094 #endif
1095
1096   rebuild_scope_notes (&forest);
1097   free_scope_forest (&forest);
1098   reorder_blocks ();
1099
1100   free_aux_for_blocks ();
1101
1102 #ifdef ENABLE_CHECKING
1103   verify_flow_info ();
1104 #endif
1105 }