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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 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
  35 extern struct obstack flow_obstack;
  36
  37 /* Structure to hold information about lexical scopes.  */
  38 struct scope_def
  39 {
  40   int level;
  41
  42   /* The NOTE_INSN_BLOCK_BEG that started this scope.  */
  43   rtx note_beg;
  44
  45   /* The NOTE_INSN_BLOCK_END that ended this scope.  */
  46   rtx note_end;
  47
  48   /* The bb containing note_beg (if any).  */
  49   basic_block bb_beg;
  50
  51   /* The bb containing note_end (if any).  */
  52   basic_block bb_end;
  53
  54   /* List of basic blocks contained within this scope.  */
  55   basic_block *bbs;
  56
  57   /* Number of blocks contained within this scope.  */
  58   int num_bbs;
  59
  60   /* The outer scope or NULL if outermost scope.  */
  61   struct scope_def *outer;
  62
  63   /* The first inner scope or NULL if innermost scope.  */
  64   struct scope_def *inner;
  65
  66   /* The last inner scope or NULL if innermost scope.  */
  67   struct scope_def *inner_last;
  68
  69   /* Link to the next (sibling) scope.  */
  70   struct scope_def *next;
  71 };
  72
  73 /* Structure to hold information about the scope forest.  */
  74 typedef struct
  75 {
  76   /* Number of trees in forest.  */
  77   int num_trees;
  78
  79   /* List of tree roots.  */
  80   scope *trees;
  81 } scope_forest_info;
  82
  83 /* Holds the interesting trailing notes for the function.  */
  84 static rtx function_tail_eff_head;
  85
  86 /* The scope forest of current function.  */
  87 static scope_forest_info forest;
  88
  89 static rtx skip_insns_after_block       PARAMS ((basic_block));
  90 static void record_effective_endpoints  PARAMS ((void));
  91 static rtx label_for_bb                 PARAMS ((basic_block));
  92 static void fixup_reorder_chain         PARAMS ((void));
  93
  94 static void relate_bbs_with_scopes      PARAMS ((scope));
  95 static scope make_new_scope             PARAMS ((int, rtx));
  96 static void build_scope_forest          PARAMS ((scope_forest_info *));
  97 static void remove_scope_notes          PARAMS ((void));
  98 static void insert_intra_before_1       PARAMS ((scope, rtx *, basic_block));
  99 static void insert_intra_1              PARAMS ((scope, rtx *, basic_block));
 100 static void insert_intra_bb_scope_notes PARAMS ((basic_block));
 101 static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
 102 static void rebuild_scope_notes         PARAMS ((scope_forest_info *));
 103 static void free_scope_forest_1         PARAMS ((scope));
 104 static void free_scope_forest           PARAMS ((scope_forest_info *));
 105 void dump_scope_forest                  PARAMS ((scope_forest_info *));
 106 static void dump_scope_forest_1         PARAMS ((scope, int));
 107
 108 static rtx get_next_bb_note             PARAMS ((rtx));
 109 static rtx get_prev_bb_note             PARAMS ((rtx));
 110
 111 void verify_insn_chain                  PARAMS ((void));
 112 static void fixup_fallthru_exit_predecessor 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)) != 0; )
 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
 175   /* It is possible to hit contradictory 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.  This can be
 182      created by removing the basic block originally following
 183      NOTE_INSN_LOOP_BEG.  In such case reorder the notes.  */
 184
 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", bb->index);
 216
 217       label = block_label (bb);
 218       if (bb->head == PREV_INSN (RBI (bb)->eff_head))
 219         RBI (bb)->eff_head = label;
 220     }
 221
 222   return label;
 223 }
 224
 225 /* Locate the effective beginning and end of the insn chain for each
 226    block, as defined by skip_insns_after_block above.  */
 227
 228 static void
 229 record_effective_endpoints ()
 230 {
 231   rtx next_insn = get_insns ();
 232   int i;
 233
 234   for (i = 0; i < n_basic_blocks; i++)
 235     {
 236       basic_block bb = BASIC_BLOCK (i);
 237       rtx end;
 238
 239       RBI (bb)->eff_head = next_insn;
 240       end = skip_insns_after_block (bb);
 241       RBI (bb)->eff_end = end;
 242       next_insn = NEXT_INSN (end);
 243     }
 244
 245   function_tail_eff_head = next_insn;
 246 }
 247 \f
 248 /* Return the next NOTE_INSN_BASIC_BLOCK after X.  */
 249
 250 static rtx
 251 get_next_bb_note (x)
 252      rtx x;
 253 {
 254   for (; x; x = NEXT_INSN (x))
 255     if (NOTE_INSN_BASIC_BLOCK_P (x))
 256       return x;
 257
 258   return NULL;
 259 }
 260
 261 /* Return the fist NOTE_INSN_BASIC_BLOCK before X.  */
 262
 263 static rtx
 264 get_prev_bb_note (x)
 265      rtx x;
 266 {
 267   for (; x; x = PREV_INSN (x))
 268     if (NOTE_INSN_BASIC_BLOCK_P (x))
 269       return 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
 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
 339           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
 340             {
 341               bbs_spanned = 0;
 342               s->bb_end = NOTE_BASIC_BLOCK (bbnote);
 343             }
 344           else
 345             {
 346               bbi1 = s->bb_beg->index;
 347               bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
 348               s->bb_beg = NULL;
 349               bbs_spanned = 1;
 350             }
 351         }
 352     }
 353   else
 354     {
 355       if (s->bb_beg)
 356         /* Both notes are in the same bb, which implies the block
 357            contains this scope.  */
 358         bbs_spanned = 0;
 359       else
 360         {
 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           rtx x1 = get_next_bb_note (s->note_beg);
 368           rtx x2 = get_prev_bb_note (s->note_end);
 369
 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
 422   new_scope->level = level;
 423   new_scope->note_beg = note;
 424   return new_scope;
 425 }
 426
 427
 428 /* Build a forest representing the scope structure of the function.
 429    Return a pointer to a structure describing the forest.  */
 430
 431 static void
 432 build_scope_forest (forest)
 433     scope_forest_info *forest;
 434 {
 435   rtx x;
 436   int level, bbi, i;
 437   basic_block curr_bb;
 438   scope root, curr_scope = 0;
 439
 440   forest->num_trees = 0;
 441   forest->trees = NULL;
 442   level = -1;
 443   root = NULL;
 444   curr_bb = NULL;
 445   bbi = 0;
 446
 447   for (x = get_insns (); x; x = NEXT_INSN (x))
 448     {
 449       if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
 450         curr_bb = BASIC_BLOCK (bbi);
 451
 452       if (GET_CODE (x) == NOTE)
 453         {
 454           if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
 455             {
 456               if (root)
 457                 {
 458                   scope new_scope;
 459
 460                   if (! curr_scope)
 461                     abort();
 462
 463                   level++;
 464                   new_scope = make_new_scope (level, x);
 465                   new_scope->outer = curr_scope;
 466                   new_scope->next = NULL;
 467                   if (! curr_scope->inner)
 468                     {
 469                       curr_scope->inner = new_scope;
 470                       curr_scope->inner_last = new_scope;
 471                     }
 472                   else
 473                     {
 474                       curr_scope->inner_last->next = new_scope;
 475                       curr_scope->inner_last = new_scope;
 476                     }
 477                   curr_scope = curr_scope->inner_last;
 478
 479                 }
 480               else
 481                 {
 482                   int ntrees = forest->num_trees;
 483
 484                   level++;
 485                   curr_scope = make_new_scope (level, x);
 486                   root = curr_scope;
 487                   forest->trees = xrealloc (forest->trees,
 488                                             sizeof (scope) * (ntrees + 1));
 489                   forest->trees[forest->num_trees++] = root;
 490                 }
 491
 492               curr_scope->bb_beg = curr_bb;
 493             }
 494           else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
 495             {
 496               curr_scope->bb_end = curr_bb;
 497               curr_scope->note_end = x;
 498               level--;
 499               curr_scope = curr_scope->outer;
 500               if (level == -1)
 501                 root = NULL;
 502             }
 503         }
 504
 505       if (curr_bb && curr_bb->end == x)
 506         {
 507           curr_bb = NULL;
 508           bbi++;
 509         }
 510     }
 511
 512   for (i = 0; i < forest->num_trees; i++)
 513     relate_bbs_with_scopes (forest->trees[i]);
 514 }
 515 \f
 516 /* Remove all NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from the insn
 517    chain.  */
 518
 519 static void
 520 remove_scope_notes ()
 521 {
 522   rtx x, next;
 523   basic_block currbb = NULL;
 524
 525   for (x = get_insns (); x; x = next)
 526     {
 527       next = NEXT_INSN (x);
 528       if (NOTE_INSN_BASIC_BLOCK_P (x))
 529         currbb = NOTE_BASIC_BLOCK (x);
 530
 531       if (GET_CODE (x) == NOTE
 532           && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
 533               || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
 534         {
 535           /* Check if the scope note happens to be the end of a bb.  */
 536           if (currbb && x == currbb->end)
 537             currbb->end = PREV_INSN (x);
 538           if (currbb && x == currbb->head)
 539             abort ();
 540
 541           if (PREV_INSN (x))
 542             {
 543               NEXT_INSN (PREV_INSN (x)) = next;
 544               if (next)
 545                 PREV_INSN (next) = PREV_INSN (x);
 546
 547               NEXT_INSN (x) = NULL;
 548               PREV_INSN (x) = NULL;
 549             }
 550           else
 551             abort ();
 552         }
 553     }
 554 }
 555 \f
 556 /* Insert scope note pairs for a contained scope tree S after insn IP.  */
 557
 558 static void
 559 insert_intra_1 (s, ip, bb)
 560      scope s;
 561      rtx *ip;
 562      basic_block bb;
 563 {
 564   scope p;
 565
 566   if (NOTE_BLOCK (s->note_beg))
 567     {
 568       *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
 569       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
 570     }
 571
 572   for (p = s->inner; p; p = p->next)
 573     insert_intra_1 (p, ip, bb);
 574
 575   if (NOTE_BLOCK (s->note_beg))
 576     {
 577       *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
 578       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
 579     }
 580 }
 581
 582 /* Insert scope note pairs for a contained scope tree S before insn IP.  */
 583
 584 static void
 585 insert_intra_before_1 (s, ip, bb)
 586      scope s;
 587      rtx *ip;
 588      basic_block bb;
 589 {
 590   scope p;
 591
 592   if (NOTE_BLOCK (s->note_beg))
 593     {
 594       *ip = emit_note_before (NOTE_INSN_BLOCK_END, *ip);
 595       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
 596     }
 597
 598   for (p = s->inner; p; p = p->next)
 599     insert_intra_before_1 (p, ip, bb);
 600
 601   if (NOTE_BLOCK (s->note_beg))
 602     {
 603       *ip = emit_note_before (NOTE_INSN_BLOCK_BEG, *ip);
 604       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
 605     }
 606 }
 607
 608 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
 609    scopes that are contained within BB.  */
 610
 611 static void
 612 insert_intra_bb_scope_notes (bb)
 613      basic_block bb;
 614 {
 615   scope s = RBI (bb)->scope;
 616   scope p;
 617   rtx ip;
 618
 619   if (! s)
 620     return;
 621
 622   ip = bb->head;
 623   if (GET_CODE (ip) == CODE_LABEL)
 624     ip = NEXT_INSN (ip);
 625
 626   for (p = s->inner; p; p = p->next)
 627     {
 628       if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
 629         insert_intra_1 (p, &ip, bb);
 630     }
 631 }
 632
 633 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
 634    insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
 635    notes before BB2 such that the notes are correctly balanced. If BB1 or
 636    BB2 is NULL, we are inserting scope notes for the first and last basic
 637    blocks, respectively.  */
 638
 639 static void
 640 insert_inter_bb_scope_notes (bb1, bb2)
 641      basic_block bb1;
 642      basic_block bb2;
 643 {
 644   rtx ip;
 645   scope com;
 646
 647   /* It is possible that a basic block is not contained in any scope.
 648      In that case, we either open or close a scope but not both.  */
 649   if (bb1 && bb2)
 650     {
 651       scope s1 = RBI (bb1)->scope;
 652       scope s2 = RBI (bb2)->scope;
 653
 654       if (! s1 && ! s2)
 655         return;
 656
 657       if (! s1)
 658         bb1 = NULL;
 659       else if (! s2)
 660         bb2 = NULL;
 661     }
 662
 663   /* Find common ancestor scope.  */
 664   if (bb1 && bb2)
 665     {
 666       scope s1 = RBI (bb1)->scope;
 667       scope s2 = RBI (bb2)->scope;
 668
 669       while (s1 != s2)
 670         {
 671           if (s1->level > s2->level)
 672             s1 = s1->outer;
 673           else if (s2->level > s1->level)
 674             s2 = s2->outer;
 675           else
 676             {
 677               s1 = s1->outer;
 678               s2 = s2->outer;
 679             }
 680         }
 681
 682       com = s1;
 683     }
 684   else
 685     com = NULL;
 686
 687   /* Close scopes.  */
 688   if (bb1)
 689     {
 690       rtx end = bb1->end;
 691       scope s, p;
 692
 693       ip = RBI (bb1)->eff_end;
 694       for (s = RBI (bb1)->scope; s != com; s = s->outer)
 695         {
 696           if (NOTE_BLOCK (s->note_beg))
 697             {
 698               ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
 699               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
 700             }
 701
 702           /* Now emit all sibling scopes which don't span any basic
 703              blocks.  */
 704           if (s->outer)
 705             for (p = s->outer->inner; p; p = p->next)
 706               if (p != s && p->bb_beg == bb1 && p->bb_beg == p->bb_end)
 707                 insert_intra_1 (p, &ip, bb1);
 708         }
 709
 710       /* Emitting note may move the end of basic block to unwanted place.  */
 711       bb1->end = end;
 712     }
 713
 714   /* Open scopes.  */
 715   if (bb2)
 716     {
 717       scope s, p;
 718
 719       ip = bb2->head;
 720       for (s = RBI (bb2)->scope; s != com; s = s->outer)
 721         {
 722           if (NOTE_BLOCK (s->note_beg))
 723             {
 724               ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
 725               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
 726             }
 727
 728           /* Now emit all sibling scopes which don't span any basic
 729              blocks.  */
 730           if (s->outer)
 731             for (p = s->outer->inner; p; p = p->next)
 732               if (p != s && p->bb_beg == bb2 && p->bb_beg == p->bb_end)
 733                 insert_intra_before_1 (p, &ip, bb2);
 734         }
 735     }
 736 }
 737
 738
 739 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
 740    on the scope forest and the newly reordered basic blocks.  */
 741
 742 static void
 743 rebuild_scope_notes (forest)
 744     scope_forest_info *forest;
 745 {
 746   int i;
 747
 748   if (forest->num_trees == 0)
 749     return;
 750
 751   /* Start by opening the scopes before the first basic block.  */
 752   insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
 753
 754   /* Then, open and close scopes as needed between blocks.  */
 755   for (i = 0; i < n_basic_blocks - 1; i++)
 756     {
 757       basic_block bb1 = BASIC_BLOCK (i);
 758       basic_block bb2 = BASIC_BLOCK (i + 1);
 759
 760       if (RBI (bb1)->scope != RBI (bb2)->scope)
 761         insert_inter_bb_scope_notes (bb1, bb2);
 762       insert_intra_bb_scope_notes (bb1);
 763     }
 764
 765   /* Finally, close the scopes after the last basic block.  */
 766   insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
 767   insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
 768 }
 769 \f
 770 /* Free the storage associated with the scope tree at S.  */
 771
 772 static void
 773 free_scope_forest_1 (s)
 774     scope s;
 775 {
 776   scope p, next;
 777
 778   for (p = s->inner; p; p = next)
 779     {
 780       next = p->next;
 781       free_scope_forest_1 (p);
 782     }
 783
 784   if (s->bbs)
 785     free (s->bbs);
 786   free (s);
 787 }
 788
 789 /* Free the storage associated with the scope forest.  */
 790
 791 static void
 792 free_scope_forest (forest)
 793     scope_forest_info *forest;
 794 {
 795   int i;
 796
 797   for (i = 0; i < forest->num_trees; i++)
 798     free_scope_forest_1 (forest->trees[i]);
 799 }
 800 \f
 801 /* Visualize the scope forest.  */
 802
 803 void
 804 dump_scope_forest (forest)
 805     scope_forest_info *forest;
 806 {
 807   int i;
 808
 809   if (forest->num_trees == 0)
 810     fprintf (stderr, "\n< Empty scope forest >\n");
 811   else
 812     fprintf (stderr, "\n< Scope forest >\n");
 813
 814   for (i = 0; i < forest->num_trees; i++)
 815     dump_scope_forest_1 (forest->trees[i], 0);
 816 }
 817
 818 /* Recursive portion of dump_scope_forest.  */
 819
 820 static void
 821 dump_scope_forest_1 (s, indent)
 822      scope s;
 823      int indent;
 824 {
 825   scope p;
 826   int i;
 827
 828   if (s->bb_beg != NULL && s->bb_beg == s->bb_end
 829       && RBI (s->bb_beg)->scope
 830       && RBI (s->bb_beg)->scope->level + 1 == s->level)
 831     {
 832       fprintf (stderr, "%*s", indent, "");
 833       fprintf (stderr, "BB%d:\n", s->bb_beg->index);
 834     }
 835
 836   fprintf (stderr, "%*s", indent, "");
 837   fprintf (stderr, "{ level %d (block %p)\n", s->level,
 838            (PTR) NOTE_BLOCK (s->note_beg));
 839
 840   fprintf (stderr, "%*s%s", indent, "", "bbs:");
 841   for (i = 0; i < s->num_bbs; i++)
 842     fprintf (stderr, " %d", s->bbs[i]->index);
 843   fprintf (stderr, "\n");
 844
 845   for (p = s->inner; p; p = p->next)
 846     dump_scope_forest_1 (p, indent + 2);
 847
 848   fprintf (stderr, "%*s", indent, "");
 849   fprintf (stderr, "}\n");
 850 }
 851 \f
 852 /* Given a reorder chain, rearrange the code to match.  */
 853
 854 static void
 855 fixup_reorder_chain ()
 856 {
 857   basic_block bb, last_bb;
 858   int index;
 859   rtx insn;
 860   int old_n_basic_blocks = n_basic_blocks;
 861
 862   /* First do the bulk reordering -- rechain the blocks without regard to
 863      the needed changes to jumps and labels.  */
 864
 865   for (last_bb = BASIC_BLOCK (0), bb = RBI (last_bb)->next, index = 1;
 866        bb != 0;
 867        last_bb = bb, bb = RBI (bb)->next, index++)
 868     {
 869       rtx last_e = RBI (last_bb)->eff_end;
 870       rtx curr_h = RBI (bb)->eff_head;
 871
 872       NEXT_INSN (last_e) = curr_h;
 873       PREV_INSN (curr_h) = last_e;
 874     }
 875
 876   if (index != n_basic_blocks)
 877     abort ();
 878
 879   insn = RBI (last_bb)->eff_end;
 880   NEXT_INSN (insn) = function_tail_eff_head;
 881   if (function_tail_eff_head)
 882     PREV_INSN (function_tail_eff_head) = insn;
 883
 884   while (NEXT_INSN (insn))
 885     insn = NEXT_INSN (insn);
 886
 887   set_last_insn (insn);
 888 #ifdef ENABLE_CHECKING
 889   verify_insn_chain ();
 890 #endif
 891
 892   /* Now add jumps and labels as needed to match the blocks new
 893      outgoing edges.  */
 894
 895   for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
 896     {
 897       edge e_fall, e_taken, e;
 898       rtx bb_end_insn;
 899       basic_block nb;
 900
 901       if (bb->succ == NULL)
 902         continue;
 903
 904       /* Find the old fallthru edge, and another non-EH edge for
 905          a taken jump.  */
 906       e_taken = e_fall = NULL;
 907       for (e = bb->succ; e ; e = e->succ_next)
 908         if (e->flags & EDGE_FALLTHRU)
 909           e_fall = e;
 910         else if (! (e->flags & EDGE_EH))
 911           e_taken = e;
 912
 913       bb_end_insn = bb->end;
 914       if (GET_CODE (bb_end_insn) == JUMP_INSN)
 915         {
 916           if (any_condjump_p (bb_end_insn))
 917             {
 918               /* If the old fallthru is still next, nothing to do.  */
 919               if (RBI (bb)->next == e_fall->dest
 920                   || (!RBI (bb)->next
 921                       && e_fall->dest == EXIT_BLOCK_PTR))
 922                 continue;
 923
 924               /* There is one special case: if *neither* block is next,
 925                  such as happens at the very end of a function, then we'll
 926                  need to add a new unconditional jump.  Choose the taken
 927                  edge based on known or assumed probability.  */
 928               if (RBI (bb)->next != e_taken->dest)
 929                 {
 930                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 931
 932                   if (note
 933                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 934                       && invert_jump (bb_end_insn,
 935                                       label_for_bb (e_fall->dest), 0))
 936                     {
 937                       e_fall->flags &= ~EDGE_FALLTHRU;
 938                       e_taken->flags |= EDGE_FALLTHRU;
 939                       e = e_fall, e_fall = e_taken, e_taken = e;
 940                     }
 941                 }
 942
 943               /* Otherwise we can try to invert the jump.  This will
 944                  basically never fail, however, keep up the pretense.  */
 945               else if (invert_jump (bb_end_insn,
 946                                     label_for_bb (e_fall->dest), 0))
 947                 {
 948                   e_fall->flags &= ~EDGE_FALLTHRU;
 949                   e_taken->flags |= EDGE_FALLTHRU;
 950                   continue;
 951                 }
 952             }
 953           else if (returnjump_p (bb_end_insn))
 954             continue;
 955           else
 956             {
 957               /* Otherwise we have some switch or computed jump.  In the
 958                  99% case, there should not have been a fallthru edge.  */
 959               if (! e_fall)
 960                 continue;
 961
 962 #ifdef CASE_DROPS_THROUGH
 963               /* Except for VAX.  Since we didn't have predication for the
 964                  tablejump, the fallthru block should not have moved.  */
 965               if (RBI (bb)->next == e_fall->dest)
 966                 continue;
 967               bb_end_insn = skip_insns_after_block (bb);
 968 #else
 969               abort ();
 970 #endif
 971             }
 972         }
 973       else
 974         {
 975           /* No fallthru implies a noreturn function with EH edges, or
 976              something similarly bizarre.  In any case, we don't need to
 977              do anything.  */
 978           if (! e_fall)
 979             continue;
 980
 981           /* If the fallthru block is still next, nothing to do.  */
 982           if (RBI (bb)->next == e_fall->dest)
 983             continue;
 984
 985           /* A fallthru to exit block.  */
 986           if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
 987             continue;
 988         }
 989
 990       /* We got here if we need to add a new jump insn.  */
 991       nb = force_nonfallthru (e_fall);
 992       if (nb)
 993         {
 994           alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
 995           RBI (nb)->eff_head = nb->head;
 996           RBI (nb)->eff_end = NEXT_INSN (nb->end);
 997           RBI (nb)->scope = RBI (bb)->scope;
 998           RBI (nb)->visited = 1;
 999           RBI (nb)->next = RBI (bb)->next;
1000           RBI (bb)->next = nb;
1001           /* Don't process this new block.  */
1002           bb = nb;
1003         }
1004     }
1005
1006   /* Put basic_block_info in the new order.  */
1007   bb = BASIC_BLOCK (0);
1008   index = 0;
1009
1010   if (rtl_dump_file)
1011     fprintf (rtl_dump_file, "Reordered sequence:\n");
1012
1013   for (; bb; bb = RBI (bb)->next, index++)
1014     {
1015       if (rtl_dump_file)
1016         fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
1017                  bb->index >= old_n_basic_blocks ? "compensation " : "",
1018                  bb->index,
1019                  bb->frequency);
1020
1021       bb->index = index;
1022       BASIC_BLOCK (index) = bb;
1023     }
1024 }
1025 \f
1026 /* Perform sanity checks on the insn chain.
1027    1. Check that next/prev pointers are consistent in both the forward and
1028       reverse direction.
1029    2. Count insns in chain, going both directions, and check if equal.
1030    3. Check that get_last_insn () returns the actual end of chain.  */
1031
1032 void
1033 verify_insn_chain ()
1034 {
1035   rtx x, prevx, nextx;
1036   int insn_cnt1, insn_cnt2;
1037
1038   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
1039        x != 0;
1040        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
1041     if (PREV_INSN (x) != prevx)
1042       abort ();
1043
1044   if (prevx != get_last_insn ())
1045     abort ();
1046
1047   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
1048        x != 0;
1049        nextx = x, insn_cnt2++, x = PREV_INSN (x))
1050     if (NEXT_INSN (x) != nextx)
1051       abort ();
1052
1053   if (insn_cnt1 != insn_cnt2)
1054     abort ();
1055 }
1056
1057 /* The block falling through to exit must be the last one in the reordered
1058    chain.  Ensure it is.  */
1059
1060 static void
1061 fixup_fallthru_exit_predecessor ()
1062 {
1063   edge e;
1064   basic_block bb = NULL;
1065
1066   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
1067     if (e->flags & EDGE_FALLTHRU)
1068       bb = e->src;
1069
1070   if (bb && RBI (bb)->next)
1071     {
1072       basic_block c = BASIC_BLOCK (0);
1073
1074       while (RBI (c)->next != bb)
1075         c = RBI (c)->next;
1076
1077       RBI (c)->next = RBI (bb)->next;
1078       while (RBI (c)->next)
1079         c = RBI (c)->next;
1080
1081       RBI (c)->next = bb;
1082       RBI (bb)->next = NULL;
1083     }
1084 }
1085 \f
1086 /* Main entry point to this module: initialize the datastructures for CFG
1087    layout changes.  */
1088
1089 void
1090 cfg_layout_initialize ()
1091 {
1092   alloc_aux_for_blocks (sizeof (struct reorder_block_def));
1093
1094   build_scope_forest (&forest);
1095   remove_scope_notes ();
1096
1097   record_effective_endpoints ();
1098 }
1099
1100 /* Finalize the changes: reorder insn list according to the sequence, enter
1101    compensation code, rebuild scope forest.  */
1102
1103 void
1104 cfg_layout_finalize ()
1105 {
1106   fixup_fallthru_exit_predecessor ();
1107   fixup_reorder_chain ();
1108
1109 #ifdef ENABLE_CHECKING
1110   verify_insn_chain ();
1111 #endif
1112
1113   rebuild_scope_notes (&forest);
1114   free_scope_forest (&forest);
1115   reorder_blocks ();
1116
1117   free_aux_for_blocks ();
1118
1119 #ifdef ENABLE_CHECKING
1120   verify_flow_info ();
1121 #endif
1122 }