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