gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000 Free Software Foundation, Inc.
   3
   4    This file is part of GNU CC.
   5
   6    GNU CC is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GNU CC is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GNU CC; see the file COPYING.  If not, write to
  18    the Free Software Foundation, 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 /* References:
  22
  23    "Profile Guided Code Positioning"
  24    Pettis and Hanson; PLDI '90.
  25 */
  26
  27 #include "config.h"
  28 #include "system.h"
  29 #include "tree.h"
  30 #include "rtl.h"
  31 #include "tm_p.h"
  32 #include "basic-block.h"
  33 #include "insn-config.h"
  34 #include "regs.h"
  35 #include "hard-reg-set.h"
  36 #include "flags.h"
  37 #include "output.h"
  38 #include "function.h"
  39 #include "except.h"
  40 #include "toplev.h"
  41 #include "recog.h"
  42 #include "insn-flags.h"
  43 #include "expr.h"
  44 #include "obstack.h"
  45
  46
  47 /* The contents of the current function definition are allocated
  48    in this obstack, and all are freed at the end of the function.
  49    For top-level functions, this is temporary_obstack.
  50    Separate obstacks are made for nested functions.  */
  51
  52 extern struct obstack *function_obstack;
  53
  54
  55 /* Structure to hold information about lexical scopes.  */
  56 typedef struct scope_def
  57 {
  58   int level;
  59
  60   /* The NOTE_INSN_BLOCK_BEG that started this scope.  */
  61   rtx note_beg;
  62
  63   /* The NOTE_INSN_BLOCK_END that ended this scope.  */
  64   rtx note_end;
  65
  66   /* The bb containing note_beg (if any).  */
  67   basic_block bb_beg;
  68
  69   /* The bb containing note_end (if any).  */
  70   basic_block bb_end;
  71
  72   /* List of basic blocks contained within this scope.  */
  73   basic_block *bbs;
  74
  75   /* Number of blocks contained within this scope.  */
  76   int num_bbs;
  77
  78   /* The outer scope or NULL if outermost scope.  */
  79   struct scope_def *outer;
  80
  81   /* The first inner scope or NULL if innermost scope.  */
  82   struct scope_def *inner;
  83
  84   /* The last inner scope or NULL if innermost scope.  */
  85   struct scope_def *inner_last;
  86
  87   /* Link to the next (sibling) scope.  */
  88   struct scope_def *next;
  89 } *scope;
  90
  91 /* Structure to hold information about the scope forest.  */
  92 typedef struct
  93 {
  94   /* Number of trees in forest.  */
  95   int num_trees;
  96
  97   /* List of tree roots.  */
  98   scope *trees;
  99 } scope_forest_info;
 100
 101
 102 typedef struct reorder_block_def {
 103   int flags;
 104   int index;
 105   basic_block add_jump;
 106   rtx eff_head;
 107   rtx eff_end;
 108   scope scope;
 109 } *reorder_block_def;
 110
 111 static struct reorder_block_def rbd_init
 112 = {
 113     0,                  /* flags */
 114     0,                  /* index */
 115     NULL,               /* add_jump */
 116     NULL_RTX,           /* eff_head */
 117     NULL_RTX,           /* eff_end */
 118     NULL                /* scope */
 119 };
 120
 121
 122 #define REORDER_BLOCK_HEAD      0x1
 123 #define REORDER_BLOCK_VISITED   0x2
 124
 125 #define REORDER_BLOCK_FLAGS(bb) \
 126   ((reorder_block_def) (bb)->aux)->flags
 127
 128 #define REORDER_BLOCK_INDEX(bb) \
 129   ((reorder_block_def) (bb)->aux)->index
 130
 131 #define REORDER_BLOCK_ADD_JUMP(bb) \
 132   ((reorder_block_def) (bb)->aux)->add_jump
 133
 134 #define REORDER_BLOCK_EFF_HEAD(bb) \
 135   ((reorder_block_def) (bb)->aux)->eff_head
 136
 137 #define REORDER_BLOCK_EFF_END(bb) \
 138   ((reorder_block_def) (bb)->aux)->eff_end
 139
 140 #define REORDER_BLOCK_SCOPE(bb) \
 141   ((reorder_block_def) (bb)->aux)->scope
 142
 143
 144 static int reorder_index;
 145 static basic_block reorder_last_visited;
 146
 147
 148 /* Local function prototypes.  */
 149 static rtx skip_insns_after_block       PARAMS ((basic_block));
 150 static basic_block get_common_dest      PARAMS ((basic_block, basic_block));
 151 static basic_block chain_reorder_blocks PARAMS ((edge, basic_block));
 152 static void make_reorder_chain          PARAMS ((basic_block));
 153 static void fixup_reorder_chain         PARAMS ((void));
 154 #ifdef ENABLE_CHECKING
 155 static void verify_insn_chain           PARAMS ((void));
 156 #endif
 157 static void relate_bbs_with_scopes      PARAMS ((scope));
 158 static scope make_new_scope             PARAMS ((int, rtx));
 159 static void build_scope_forest          PARAMS ((scope_forest_info *));
 160 static void remove_scope_notes          PARAMS ((void));
 161 static void insert_intra_1              PARAMS ((scope, rtx *));
 162 static void insert_intra_bb_scope_notes PARAMS ((basic_block));
 163 static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
 164 static void rebuild_scope_notes         PARAMS ((scope_forest_info *));
 165 static void free_scope_forest_1         PARAMS ((scope));
 166 static void free_scope_forest           PARAMS ((scope_forest_info *));
 167 void dump_scope_forest                  PARAMS ((scope_forest_info *));
 168 static void dump_scope_forest_1         PARAMS ((scope, int));
 169 static rtx get_next_bb_note             PARAMS ((rtx));
 170 static rtx get_prev_bb_note             PARAMS ((rtx));
 171
 172 /* Skip over inter-block insns occurring after BB which are typically
 173    associated with BB (e.g., barriers). If there are any such insns,
 174    we return the last one. Otherwise, we return the end of BB.  */
 175
 176 static rtx
 177 skip_insns_after_block (bb)
 178      basic_block bb;
 179 {
 180   rtx insn, last_insn;
 181
 182   last_insn = bb->end;
 183
 184   if (bb == EXIT_BLOCK_PTR)
 185     return 0;
 186
 187   for (insn = NEXT_INSN (bb->end);
 188        insn;
 189        last_insn = insn, insn = NEXT_INSN (insn))
 190     {
 191       if (bb->index + 1 != n_basic_blocks
 192           && insn == BASIC_BLOCK (bb->index + 1)->head)
 193         break;
 194
 195       if (GET_CODE (insn) == BARRIER
 196           || GET_CODE (insn) == JUMP_INSN
 197           || (GET_CODE (insn) == NOTE
 198               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
 199                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)))
 200         continue;
 201
 202       if (GET_CODE (insn) == CODE_LABEL
 203           && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 204           && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 205               || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 206         {
 207           insn = NEXT_INSN (insn);
 208           continue;
 209         }
 210
 211       /* Skip to next non-deleted insn.  */
 212       if (GET_CODE (insn) == NOTE
 213           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED
 214               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
 215         continue;
 216
 217       break;
 218     }
 219
 220   return last_insn;
 221 }
 222
 223
 224 /* Return common destination for blocks BB0 and BB1.  */
 225
 226 static basic_block
 227 get_common_dest (bb0, bb1)
 228      basic_block bb0, bb1;
 229 {
 230   edge e0, e1;
 231
 232   for (e0 = bb0->succ; e0; e0 = e0->succ_next)
 233     {
 234       for (e1 = bb1->succ; e1; e1 = e1->succ_next)
 235         {
 236           if (e0->dest == e1->dest)
 237             {
 238               return e0->dest;
 239             }
 240         }
 241     }
 242   return 0;
 243 }
 244
 245
 246 /* Move the destination block for edge E after chain end block CEB
 247    Adding jumps and labels is deferred until fixup_reorder_chain.  */
 248
 249 static basic_block
 250 chain_reorder_blocks (e, ceb)
 251      edge e;
 252      basic_block ceb;
 253 {
 254   basic_block sb = e->src;
 255   basic_block db = e->dest;
 256   rtx cebe_insn, dbh_insn, dbe_insn;
 257   edge ee, last_edge;
 258   edge e_fallthru, e_jump;
 259
 260   enum cond_types {NO_COND, PREDICT_THEN_WITH_ELSE, PREDICT_ELSE,
 261                    PREDICT_THEN_NO_ELSE, PREDICT_NOT_THEN_NO_ELSE};
 262   enum cond_types cond_type;
 263   enum cond_block_types {NO_COND_BLOCK, THEN_BLOCK, ELSE_BLOCK,
 264                          NO_ELSE_BLOCK};
 265   enum cond_block_types cond_block_type;
 266
 267   if (rtl_dump_file)
 268     fprintf (rtl_dump_file,
 269              "Edge from basic block %d to basic block %d last visited %d\n",
 270              sb->index, db->index, ceb->index);
 271   cebe_insn = REORDER_BLOCK_EFF_END (ceb);
 272
 273   /* Blocks are in original order.  */
 274   if (sb->index == ceb->index
 275       && ceb->index + 1 == db->index && NEXT_INSN (cebe_insn))
 276     return db;
 277
 278   e_fallthru = e_jump = e;
 279
 280   /* Get the type of block and type of condition.  */
 281   cond_type = NO_COND;
 282   cond_block_type = NO_COND_BLOCK;
 283   if (GET_CODE (sb->end) == JUMP_INSN && ! simplejump_p (sb->end)
 284       && condjump_p (sb->end))
 285     {
 286       if (e->flags & EDGE_FALLTHRU)
 287         {
 288           if (e == sb->succ)
 289             e_jump = sb->succ->succ_next;
 290           else if (e == sb->succ->succ_next)
 291             e_jump = sb->succ;
 292           else
 293             abort ();
 294         }
 295       else
 296         {
 297           if (e == sb->succ)
 298             e_fallthru = sb->succ->succ_next;
 299           else if (e == sb->succ->succ_next)
 300             e_fallthru = sb->succ;
 301           else
 302             abort ();
 303         }
 304
 305       if (e->flags & EDGE_FALLTHRU)
 306         cond_block_type = THEN_BLOCK;
 307       else if (get_common_dest (e_fallthru->dest, sb))
 308         cond_block_type = NO_ELSE_BLOCK;
 309       else
 310         cond_block_type = ELSE_BLOCK;
 311
 312       if (get_common_dest (e_fallthru->dest, sb))
 313         {
 314           if (cond_block_type == THEN_BLOCK)
 315             {
 316               if (! (REORDER_BLOCK_FLAGS (e->dest)
 317                      & REORDER_BLOCK_VISITED))
 318                 cond_type = PREDICT_THEN_NO_ELSE;
 319               else
 320                 cond_type = PREDICT_NOT_THEN_NO_ELSE;
 321             }
 322           else if (cond_block_type == NO_ELSE_BLOCK)
 323             {
 324               if (! (REORDER_BLOCK_FLAGS (e->dest)
 325                      & REORDER_BLOCK_VISITED))
 326                 cond_type = PREDICT_NOT_THEN_NO_ELSE;
 327               else
 328                 cond_type = PREDICT_THEN_NO_ELSE;
 329             }
 330         }
 331       else
 332         {
 333           if (cond_block_type == THEN_BLOCK)
 334             {
 335               if (! (REORDER_BLOCK_FLAGS (e->dest)
 336                      & REORDER_BLOCK_VISITED))
 337                 cond_type = PREDICT_THEN_WITH_ELSE;
 338               else
 339                 cond_type = PREDICT_ELSE;
 340             }
 341           else if (cond_block_type == ELSE_BLOCK
 342                    && e_fallthru->dest != EXIT_BLOCK_PTR)
 343             {
 344               if (! (REORDER_BLOCK_FLAGS (e->dest)
 345                      & REORDER_BLOCK_VISITED))
 346                 cond_type = PREDICT_ELSE;
 347               else
 348                 cond_type = PREDICT_THEN_WITH_ELSE;
 349             }
 350         }
 351     }
 352
 353   if (rtl_dump_file)
 354     {
 355       static const char * cond_type_str [] = {"not cond jump", "predict then",
 356                                               "predict else",
 357                                               "predict then w/o else",
 358                                               "predict not then w/o else"};
 359       static const char * cond_block_type_str [] = {"not then or else block",
 360                                                     "then block",
 361                                                     "else block",
 362                                                     "then w/o else block"};
 363
 364       fprintf (rtl_dump_file, "     %s (looking at %s)\n",
 365                cond_type_str[(int)cond_type],
 366                cond_block_type_str[(int)cond_block_type]);
 367     }
 368
 369   /* Reflect that then block will move and we'll jump to it.  */
 370   if (cond_block_type != THEN_BLOCK
 371       && (cond_type == PREDICT_ELSE
 372           || cond_type == PREDICT_NOT_THEN_NO_ELSE))
 373     {
 374       if (rtl_dump_file)
 375         fprintf (rtl_dump_file,
 376                  "    then jump from block %d to block %d\n",
 377                  sb->index, e_fallthru->dest->index);
 378
 379       /* Jump to reordered then block.  */
 380       REORDER_BLOCK_ADD_JUMP (sb) = e_fallthru->dest;
 381     }
 382
 383   /* Reflect that then block will jump back when we have no else.  */
 384   if (cond_block_type != THEN_BLOCK
 385       && cond_type == PREDICT_NOT_THEN_NO_ELSE)
 386     {
 387       basic_block jbb = e_fallthru->dest;
 388       for (ee = jbb->succ;
 389            ee && ! (ee->flags & EDGE_FALLTHRU);
 390            ee = ee->succ_next)
 391         continue;
 392
 393       if (ee && ! (GET_CODE (jbb->end) == JUMP_INSN
 394                    && ! simplejump_p (jbb->end)))
 395         {
 396           REORDER_BLOCK_ADD_JUMP (jbb) = ee->dest;
 397         }
 398     }
 399
 400   /* Reflect that else block will jump back.  */
 401   if (cond_block_type == ELSE_BLOCK
 402       && (cond_type == PREDICT_THEN_WITH_ELSE || cond_type == PREDICT_ELSE))
 403     {
 404       last_edge=db->succ;
 405
 406       if (last_edge
 407           && last_edge->dest != EXIT_BLOCK_PTR
 408           && GET_CODE (last_edge->dest->head) == CODE_LABEL
 409           && ! (GET_CODE (db->end) == JUMP_INSN))
 410         {
 411           if (rtl_dump_file)
 412             fprintf (rtl_dump_file,
 413                      "     else jump from block %d to block %d\n",
 414                      db->index, last_edge->dest->index);
 415
 416           REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
 417         }
 418     }
 419
 420   /* This block's successor has already been reordered. This can happen
 421      when we reorder a chain starting at a then or else.  */
 422   for (last_edge = db->succ;
 423        last_edge && ! (last_edge->flags & EDGE_FALLTHRU);
 424        last_edge = last_edge->succ_next)
 425     continue;
 426
 427   if (last_edge
 428       && last_edge->dest != EXIT_BLOCK_PTR
 429       && (REORDER_BLOCK_FLAGS (last_edge->dest)
 430           & REORDER_BLOCK_VISITED))
 431     {
 432       if (rtl_dump_file)
 433         fprintf (rtl_dump_file,
 434                  "     end of chain jump from block %d to block %d\n",
 435                  db->index, last_edge->dest->index);
 436
 437       REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
 438     }
 439
 440   dbh_insn = REORDER_BLOCK_EFF_HEAD (db);
 441   cebe_insn = REORDER_BLOCK_EFF_END (ceb);
 442   dbe_insn = REORDER_BLOCK_EFF_END (db);
 443
 444   /* Rechain predicted block.  */
 445   NEXT_INSN (cebe_insn) = dbh_insn;
 446   PREV_INSN (dbh_insn) = cebe_insn;
 447
 448   if (db->index != n_basic_blocks - 1)
 449     NEXT_INSN (dbe_insn) = 0;
 450
 451   return db;
 452 }
 453
 454
 455 /* Reorder blocks starting at block BB.  */
 456
 457 static void
 458 make_reorder_chain (bb)
 459      basic_block bb;
 460 {
 461   edge e;
 462   basic_block visited_edge = NULL;
 463   rtx block_end;
 464   int probability;
 465
 466   if (bb == EXIT_BLOCK_PTR)
 467     return;
 468
 469   /* Find the most probable block.  */
 470   e = bb->succ;
 471   block_end = bb->end;
 472   if (GET_CODE (block_end) == JUMP_INSN && condjump_p (block_end))
 473     {
 474       rtx note = find_reg_note (block_end, REG_BR_PROB, 0);
 475
 476       if (note)
 477         probability = INTVAL (XEXP (note, 0));
 478       else
 479         probability = 0;
 480
 481       if (probability >= REG_BR_PROB_BASE / 2)
 482         e = bb->succ->succ_next;
 483     }
 484
 485   /* Add chosen successor to chain and recurse on it.  */
 486   if (e && e->dest != EXIT_BLOCK_PTR
 487       && e->dest != e->src
 488       && (! (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
 489           || (REORDER_BLOCK_FLAGS (e->dest) == REORDER_BLOCK_HEAD)))
 490     {
 491       if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
 492         {
 493           REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_HEAD;
 494           REORDER_BLOCK_INDEX (bb) = reorder_index++;
 495           REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
 496         }
 497
 498       if (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
 499         REORDER_BLOCK_FLAGS (e->dest) &= ~REORDER_BLOCK_HEAD;
 500
 501       visited_edge = e->dest;
 502
 503       reorder_last_visited = chain_reorder_blocks (e, bb);
 504
 505       if (e->dest
 506           && ! (REORDER_BLOCK_FLAGS (e->dest)
 507                 & REORDER_BLOCK_VISITED))
 508         make_reorder_chain (e->dest);
 509     }
 510   else
 511     {
 512       if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
 513         {
 514           REORDER_BLOCK_INDEX (bb) = reorder_index++;
 515           REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
 516         }
 517     }
 518
 519   /* Recurse on the successors.  */
 520   for (e = bb->succ; e; e = e->succ_next)
 521     {
 522       if (e->dest && e->dest == EXIT_BLOCK_PTR)
 523         continue;
 524
 525       if (e->dest
 526           && e->dest != e->src
 527           && e->dest != visited_edge
 528           && ! (REORDER_BLOCK_FLAGS (e->dest)
 529                 & REORDER_BLOCK_VISITED))
 530         {
 531           reorder_last_visited
 532             = chain_reorder_blocks (e, reorder_last_visited);
 533           make_reorder_chain (e->dest);
 534         }
 535     }
 536 }
 537
 538
 539 /* Fixup jumps and labels after reordering basic blocks.  */
 540
 541 static void
 542 fixup_reorder_chain ()
 543 {
 544   int i, j;
 545   rtx insn;
 546   int orig_num_blocks = n_basic_blocks;
 547
 548   /* Set the new last insn.  */
 549   {
 550     int max_val = 0;
 551     int max_index = 0;
 552     for (j = 0; j < n_basic_blocks; j++)
 553       {
 554         int val = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
 555         if (val > max_val)
 556           {
 557             max_val = val;
 558             max_index = j;
 559           }
 560       }
 561     insn = REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index));
 562     NEXT_INSN (insn) = NULL_RTX;
 563     set_last_insn (insn);
 564   }
 565
 566   /* Add jumps and labels to fixup blocks.  */
 567   for (i = 0; i < orig_num_blocks; i++)
 568     {
 569       int need_block = 0;
 570       basic_block bbi = BASIC_BLOCK (i);
 571       if (REORDER_BLOCK_ADD_JUMP (bbi))
 572         {
 573           rtx label_insn, jump_insn, barrier_insn;
 574
 575           if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi)->head) == CODE_LABEL)
 576             label_insn  = REORDER_BLOCK_ADD_JUMP (bbi)->head;
 577           else
 578             {
 579               rtx new_label = gen_label_rtx ();
 580               label_insn = emit_label_before (new_label,
 581                               REORDER_BLOCK_ADD_JUMP (bbi)->head);
 582               REORDER_BLOCK_ADD_JUMP (bbi)->head = label_insn;
 583             }
 584
 585           if (GET_CODE (bbi->end) != JUMP_INSN)
 586             {
 587               jump_insn = emit_jump_insn_after (gen_jump (label_insn),
 588                                                 bbi->end);
 589               bbi->end = jump_insn;
 590               need_block = 0;
 591             }
 592           else
 593             {
 594               jump_insn = emit_jump_insn_after (gen_jump (label_insn),
 595                                                 REORDER_BLOCK_EFF_END (bbi));
 596               need_block = 1;
 597             }
 598
 599           JUMP_LABEL (jump_insn) = label_insn;
 600           ++LABEL_NUSES (label_insn);
 601           barrier_insn = emit_barrier_after (jump_insn);
 602
 603           /* Add block for jump.  Typically this is when a then is not
 604              predicted and we are jumping to the moved then block.  */
 605           if (need_block)
 606             {
 607               basic_block nb;
 608
 609               VARRAY_GROW (basic_block_info, ++n_basic_blocks);
 610               create_basic_block (n_basic_blocks - 1, jump_insn,
 611                                   jump_insn, NULL);
 612               nb = BASIC_BLOCK (n_basic_blocks - 1);
 613               nb->global_live_at_start
 614                 = OBSTACK_ALLOC_REG_SET (function_obstack);
 615               nb->global_live_at_end
 616                 = OBSTACK_ALLOC_REG_SET (function_obstack);
 617
 618               COPY_REG_SET (nb->global_live_at_start,
 619                             bbi->global_live_at_start);
 620               COPY_REG_SET (nb->global_live_at_end,
 621                             bbi->global_live_at_start);
 622               BASIC_BLOCK (nb->index)->local_set = 0;
 623
 624               nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
 625               REORDER_BLOCK_INDEX (nb) = REORDER_BLOCK_INDEX (bbi) + 1;
 626               /* Relink to new block.  */
 627               nb->succ = bbi->succ;
 628               nb->succ->src = nb;
 629
 630               make_edge (NULL, bbi, nb, 0);
 631               bbi->succ->succ_next
 632                 = bbi->succ->succ_next->succ_next;
 633               nb->succ->succ_next = 0;
 634               /* Fix reorder block index to reflect new block.  */
 635               for (j = 0; j < n_basic_blocks - 1; j++)
 636                 {
 637                   basic_block bbj = BASIC_BLOCK (j);
 638                   if (REORDER_BLOCK_INDEX (bbj)
 639                       >= REORDER_BLOCK_INDEX (bbi) + 1)
 640                     REORDER_BLOCK_INDEX (bbj)++;
 641                 }
 642               REORDER_BLOCK_SCOPE (nb) = REORDER_BLOCK_SCOPE (bbi);
 643               REORDER_BLOCK_EFF_HEAD (nb) = nb->head;
 644               REORDER_BLOCK_EFF_END (nb) = barrier_insn;
 645             }
 646           else
 647             REORDER_BLOCK_EFF_END (bbi) = barrier_insn;
 648         }
 649     }
 650 }
 651
 652
 653 /* Perform sanity checks on the insn chain.
 654    1. Check that next/prev pointers are consistent in both the forward and
 655       reverse direction.
 656    2. Count insns in chain, going both directions, and check if equal.
 657    3. Check that get_last_insn () returns the actual end of chain.  */
 658 #ifdef ENABLE_CHECKING
 659 static void
 660 verify_insn_chain ()
 661 {
 662   rtx x,
 663       prevx,
 664       nextx;
 665   int insn_cnt1,
 666       insn_cnt2;
 667
 668   prevx = NULL;
 669   insn_cnt1 = 1;
 670   for (x = get_insns (); x; x = NEXT_INSN (x))
 671     {
 672       if (PREV_INSN (x) != prevx)
 673         {
 674           fprintf (stderr, "Forward traversal: insn chain corrupt.\n");
 675           fprintf (stderr, "previous insn:\n");
 676           debug_rtx (prevx);
 677           fprintf (stderr, "current insn:\n");
 678           debug_rtx (x);
 679           abort ();
 680         }
 681       ++insn_cnt1;
 682       prevx = x;
 683     }
 684
 685   if (prevx != get_last_insn ())
 686     {
 687       fprintf (stderr, "last_insn corrupt.\n");
 688       abort ();
 689     }
 690
 691   nextx = NULL;
 692   insn_cnt2 = 1;
 693   for (x = get_last_insn (); x; x = PREV_INSN (x))
 694     {
 695       if (NEXT_INSN (x) != nextx)
 696         {
 697           fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
 698           fprintf (stderr, "current insn:\n");
 699           debug_rtx (x);
 700           fprintf (stderr, "next insn:\n");
 701           debug_rtx (nextx);
 702           abort ();
 703         }
 704       ++insn_cnt2;
 705       nextx = x;
 706     }
 707
 708   if (insn_cnt1 != insn_cnt2)
 709     {
 710       fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
 711                insn_cnt1, insn_cnt2);
 712       abort ();
 713     }
 714 }
 715 #endif
 716
 717 static rtx
 718 get_next_bb_note (x)
 719      rtx x;
 720 {
 721   while (x)
 722     {
 723       if (GET_CODE (x) == NOTE
 724           && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
 725         return x;
 726       x = NEXT_INSN (x);
 727     }
 728   return NULL;
 729 }
 730
 731
 732 static rtx
 733 get_prev_bb_note (x)
 734      rtx x;
 735 {
 736   while (x)
 737     {
 738       if (GET_CODE (x) == NOTE
 739           && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
 740         return x;
 741       x = PREV_INSN (x);
 742     }
 743   return NULL;
 744 }
 745
 746
 747 /* Determine and record the relationships between basic blocks and
 748    scopes in scope tree S.  */
 749
 750 static void
 751 relate_bbs_with_scopes (s)
 752      scope s;
 753 {
 754   scope p;
 755   int i, bbi1, bbi2, bbs_spanned;
 756   rtx bbnote;
 757
 758   for (p = s->inner; p; p = p->next)
 759     relate_bbs_with_scopes (p);
 760
 761   bbi1 = bbi2 = -1;
 762   bbs_spanned = 0;
 763
 764   /* If the begin and end notes are both inside the same basic block,
 765      or if they are both outside of basic blocks, then we know immediately
 766      how they are related. Otherwise, we need to poke around to make the
 767      determination.  */
 768   if (s->bb_beg != s->bb_end)
 769     {
 770       if (s->bb_beg && s->bb_end)
 771         {
 772           /* Both notes are in different bbs. This implies that all the
 773              basic blocks spanned by the pair of notes are contained in
 774              this scope.  */
 775           bbi1 = s->bb_beg->index;
 776           bbi2 = s->bb_end->index;
 777           bbs_spanned = 1;
 778         }
 779       else if (! s->bb_beg)
 780         {
 781           /* First note is outside of a bb. If the scope spans more than
 782              one basic block, then they all are contained within this
 783              scope. Otherwise, this scope is contained within the basic
 784              block.  */
 785           bbnote = get_next_bb_note (s->note_beg);
 786           if (! bbnote)
 787             abort ();
 788           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
 789             {
 790               bbs_spanned = 0;
 791               s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
 792             }
 793           else
 794             {
 795               bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
 796               bbi2 = s->bb_end->index;
 797               s->bb_end = NULL;
 798               bbs_spanned = 1;
 799             }
 800         }
 801       else /* ! s->bb_end */
 802         {
 803           /* Second note is outside of a bb. If the scope spans more than
 804              one basic block, then they all are contained within this
 805              scope. Otherwise, this scope is contained within the basic
 806              block.  */
 807           bbnote = get_prev_bb_note (s->note_end);
 808           if (! bbnote)
 809             abort ();
 810           if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
 811             {
 812               bbs_spanned = 0;
 813               s->bb_end = NOTE_BASIC_BLOCK (bbnote);
 814             }
 815           else
 816             {
 817               bbi1 = s->bb_beg->index;
 818               bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
 819               s->bb_beg = NULL;
 820               bbs_spanned = 1;
 821             }
 822         }
 823     }
 824   else
 825     {
 826       if (s->bb_beg)
 827         /* Both notes are in the same bb, which implies the block
 828            contains this scope.  */
 829         bbs_spanned = 0;
 830       else
 831         {
 832           rtx x1, x2;
 833           /* Both notes are outside of any bbs. This implies that all the
 834              basic blocks spanned by the pair of notes are contained in
 835              this scope.
 836              There is a degenerate case to consider. If the notes do not
 837              span any basic blocks, then it is an empty scope that can
 838              safely be deleted or ignored. Mark these with level = -1.  */
 839
 840           x1 = get_next_bb_note (s->note_beg);
 841           x2 = get_prev_bb_note (s->note_end);
 842           if (! (x1 && x2))
 843             {
 844               s->level = -1;
 845               bbs_spanned = 0;
 846             }
 847           else
 848             {
 849               bbi1 = NOTE_BASIC_BLOCK (x1)->index;
 850               bbi2 = NOTE_BASIC_BLOCK (x2)->index;
 851               bbs_spanned = 1;
 852             }
 853         }
 854     }
 855
 856
 857   /* If the scope spans one or more basic blocks, we record them. We
 858      only record the bbs that are immediately contained within this
 859      scope. Note that if a scope is contained within a bb, we can tell
 860      by checking that bb_beg = bb_end and that they are non-null.  */
 861   if (bbs_spanned)
 862     {
 863       int j = 0;
 864
 865       s->num_bbs = 0;
 866       for (i = bbi1; i <= bbi2; i++)
 867         if (! REORDER_BLOCK_SCOPE (BASIC_BLOCK (i)))
 868           s->num_bbs++;
 869
 870       s->bbs = xcalloc (s->num_bbs, sizeof (struct basic_block_def));
 871       for (i = bbi1; i <= bbi2; i++)
 872         {
 873           basic_block curr_bb = BASIC_BLOCK (i);
 874           if (! REORDER_BLOCK_SCOPE (curr_bb))
 875             {
 876               s->bbs[j++] = curr_bb;
 877               REORDER_BLOCK_SCOPE (curr_bb) = s;
 878             }
 879         }
 880     }
 881   else
 882     s->num_bbs = 0;
 883 }
 884
 885
 886 /* Allocate and initialize a new scope structure with scope level LEVEL,
 887    and record the NOTE beginning the scope.  */
 888
 889 static scope
 890 make_new_scope (level, note)
 891      int level;
 892      rtx note;
 893 {
 894   scope new_scope = xcalloc (1, sizeof (struct scope_def));
 895   new_scope->level = level;
 896   new_scope->note_beg = note;
 897   new_scope->note_end = NULL;
 898   new_scope->bb_beg = NULL;
 899   new_scope->bb_end = NULL;
 900   new_scope->inner = NULL;
 901   new_scope->inner_last = NULL;
 902   new_scope->outer = NULL;
 903   new_scope->next = NULL;
 904   new_scope->num_bbs = 0;
 905   new_scope->bbs = NULL;
 906   return new_scope;
 907 }
 908
 909
 910 /* Build a forest representing the scope structure of the function.
 911    Return a pointer to a structure describing the forest.  */
 912
 913 static void
 914 build_scope_forest (forest)
 915     scope_forest_info *forest;
 916 {
 917   rtx x;
 918   int level, bbi, i;
 919   basic_block curr_bb;
 920   scope root, curr_scope;
 921
 922   forest->num_trees = 0;
 923   forest->trees = NULL;
 924   level = -1;
 925   root = NULL;
 926   curr_bb = NULL;
 927   bbi = 0;
 928   for (x = get_insns (); x; x = NEXT_INSN (x))
 929     {
 930       if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
 931         curr_bb = BASIC_BLOCK (bbi);
 932
 933       if (GET_CODE (x) == NOTE)
 934         {
 935           if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
 936             {
 937               if (root)
 938                 {
 939                   scope new_scope;
 940                   if (! curr_scope)
 941                     abort();
 942                   level++;
 943                   new_scope = make_new_scope (level, x);
 944                   new_scope->outer = curr_scope;
 945                   new_scope->next = NULL;
 946                   if (! curr_scope->inner)
 947                     {
 948                       curr_scope->inner = new_scope;
 949                       curr_scope->inner_last = new_scope;
 950                     }
 951                   else
 952                     {
 953                       curr_scope->inner_last->next = new_scope;
 954                       curr_scope->inner_last = new_scope;
 955                     }
 956                   curr_scope = curr_scope->inner_last;
 957                 }
 958               else
 959                 {
 960                   int ntrees = forest->num_trees;
 961                   level++;
 962                   curr_scope = make_new_scope (level, x);
 963                   root = curr_scope;
 964                   if (ntrees == 0)
 965                     forest->trees = xcalloc (1, sizeof (scope));
 966                   else
 967                     forest->trees = xrealloc (forest->trees,
 968                                               sizeof (scope) * (ntrees + 1));
 969                   forest->trees[forest->num_trees++] = root;
 970                 }
 971               curr_scope->bb_beg = curr_bb;
 972             }
 973           else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
 974             {
 975               curr_scope->bb_end = curr_bb;
 976               curr_scope->note_end = x;
 977               level--;
 978               curr_scope = curr_scope->outer;
 979               if (level == -1)
 980                 root = NULL;
 981             }
 982         } /* if note */
 983
 984       if (curr_bb && curr_bb->end == x)
 985         {
 986           curr_bb = NULL;
 987           bbi++;
 988         }
 989
 990     } /* for */
 991
 992   for (i = 0; i < forest->num_trees; i++)
 993     relate_bbs_with_scopes (forest->trees[i]);
 994 }
 995
 996
 997 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
 998    the insn chain.  */
 999
1000 static void
1001 remove_scope_notes ()
1002 {
1003   rtx x, next;
1004   basic_block currbb = NULL;
1005
1006   for (x = get_insns (); x; x = next)
1007     {
1008       next = NEXT_INSN (x);
1009       if (GET_CODE (x) == NOTE
1010           && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
1011         currbb = NOTE_BASIC_BLOCK (x);
1012
1013       if (GET_CODE (x) == NOTE
1014           && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
1015               || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
1016         {
1017           /* Check if the scope note happens to be the end of a bb.  */
1018           if (currbb && x == currbb->end)
1019             currbb->end = PREV_INSN (x);
1020           if (currbb && x == currbb->head)
1021             abort ();
1022
1023           if (PREV_INSN (x))
1024             {
1025               NEXT_INSN (PREV_INSN (x)) = next;
1026               PREV_INSN (next) = PREV_INSN (x);
1027
1028               NEXT_INSN (x) = NULL;
1029               PREV_INSN (x) = NULL;
1030             }
1031           else
1032             abort ();
1033         }
1034     }
1035 }
1036
1037
1038 /* Insert scope note pairs for a contained scope tree S after insn IP.  */
1039 static void
1040 insert_intra_1 (s, ip)
1041      scope s;
1042      rtx *ip;
1043 {
1044   scope p;
1045
1046   if (NOTE_BLOCK (s->note_beg))
1047     {
1048       *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
1049       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
1050     }
1051
1052   for (p = s->inner; p; p = p->next)
1053     insert_intra_1 (p, ip);
1054
1055   if (NOTE_BLOCK (s->note_beg))
1056     {
1057       *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
1058       NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
1059     }
1060 }
1061
1062
1063 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1064    scopes that are contained within BB.  */
1065
1066 static void
1067 insert_intra_bb_scope_notes (bb)
1068      basic_block bb;
1069 {
1070   scope s = REORDER_BLOCK_SCOPE (bb);
1071   scope p;
1072   rtx ip;
1073
1074   if (! s)
1075     return;
1076
1077   ip = bb->head;
1078   if (GET_CODE (ip) == CODE_LABEL)
1079     ip = NEXT_INSN (ip);
1080
1081   for (p = s->inner; p; p = p->next)
1082     {
1083       if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
1084         insert_intra_1 (p, &ip);
1085     }
1086 }
1087
1088
1089 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1090    insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1091    notes before BB2 such that the notes are correctly balanced. If BB1 or
1092    BB2 is NULL, we are inserting scope notes for the first and last basic
1093    blocks, respectively.  */
1094
1095 static void
1096 insert_inter_bb_scope_notes (bb1, bb2)
1097      basic_block bb1;
1098      basic_block bb2;
1099 {
1100   rtx ip;
1101   scope com;
1102
1103   /* It is possible that a basic block is not contained in any scope.
1104      In that case, we either open or close a scope but not both.  */
1105   if (bb1 && bb2)
1106     {
1107       scope s1 = REORDER_BLOCK_SCOPE (bb1);
1108       scope s2 = REORDER_BLOCK_SCOPE (bb2);
1109       if (! s1 && ! s2)
1110         return;
1111       if (! s1)
1112         bb1 = NULL;
1113       else if (! s2)
1114         bb2 = NULL;
1115     }
1116
1117   /* Find common ancestor scope.  */
1118   if (bb1 && bb2)
1119     {
1120       scope s1 = REORDER_BLOCK_SCOPE (bb1);
1121       scope s2 = REORDER_BLOCK_SCOPE (bb2);
1122       while (s1 != s2)
1123         {
1124           if (! (s1 && s2))
1125             abort ();
1126           if (s1->level > s2->level)
1127             s1 = s1->outer;
1128           else if (s2->level > s1->level)
1129             s2 = s2->outer;
1130           else
1131             {
1132               s1 = s1->outer;
1133               s2 = s2->outer;
1134             }
1135         }
1136       com = s1;
1137     }
1138   else
1139     com = NULL;
1140
1141   /* Close scopes.  */
1142   if (bb1)
1143     {
1144       scope s = REORDER_BLOCK_SCOPE (bb1);
1145       ip = REORDER_BLOCK_EFF_END (bb1);
1146       while (s != com)
1147         {
1148           if (NOTE_BLOCK (s->note_beg))
1149             {
1150               ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
1151               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
1152             }
1153           s = s->outer;
1154         }
1155     }
1156
1157   /* Open scopes.  */
1158   if (bb2)
1159     {
1160       scope s = REORDER_BLOCK_SCOPE (bb2);
1161       ip = bb2->head;
1162       while (s != com)
1163         {
1164           if (NOTE_BLOCK (s->note_beg))
1165             {
1166               ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
1167               NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
1168             }
1169           s = s->outer;
1170         }
1171     }
1172 }
1173
1174
1175 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1176    on the scope forest and the newly reordered basic blocks.  */
1177
1178 static void
1179 rebuild_scope_notes (forest)
1180     scope_forest_info *forest;
1181 {
1182   int i;
1183
1184   if (forest->num_trees == 0)
1185     return;
1186
1187   /* Start by opening the scopes before the first basic block.  */
1188   insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
1189
1190   /* Then, open and close scopes as needed between blocks.  */
1191   for (i = 0; i < n_basic_blocks - 1; i++)
1192     {
1193       basic_block bb1 = BASIC_BLOCK (i);
1194       basic_block bb2 = BASIC_BLOCK (i + 1);
1195       if (REORDER_BLOCK_SCOPE (bb1) != REORDER_BLOCK_SCOPE (bb2))
1196         insert_inter_bb_scope_notes (bb1, bb2);
1197       insert_intra_bb_scope_notes (bb1);
1198     }
1199
1200   /* Finally, close the scopes after the last basic block.  */
1201   insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
1202   insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
1203 }
1204
1205
1206 /* Free the storage associated with the scope tree at S.  */
1207
1208 static void
1209 free_scope_forest_1 (s)
1210     scope s;
1211 {
1212   scope p, next;
1213
1214   for (p = s->inner; p; p = next)
1215     {
1216       next = p->next;
1217       free_scope_forest_1 (p);
1218     }
1219
1220   if (s->bbs)
1221     free (s->bbs);
1222   free (s);
1223 }
1224
1225
1226 /* Free the storage associated with the scope forest.  */
1227
1228 static void
1229 free_scope_forest (forest)
1230     scope_forest_info *forest;
1231 {
1232   int i;
1233   for (i = 0; i < forest->num_trees; i++)
1234     free_scope_forest_1 (forest->trees[i]);
1235 }
1236
1237
1238 /* Visualize the scope forest.  */
1239
1240 void
1241 dump_scope_forest (forest)
1242     scope_forest_info *forest;
1243 {
1244   if (forest->num_trees == 0)
1245     fprintf (stderr, "\n< Empty scope forest >\n");
1246   else
1247     {
1248       int i;
1249       fprintf (stderr, "\n< Scope forest >\n");
1250       for (i = 0; i < forest->num_trees; i++)
1251         dump_scope_forest_1 (forest->trees[i], 0);
1252     }
1253 }
1254
1255
1256 /* Recursive portion of dump_scope_forest.  */
1257
1258 static void
1259 dump_scope_forest_1 (s, indent)
1260      scope s;
1261      int indent;
1262 {
1263   scope p;
1264   int i;
1265
1266   if (s->bb_beg != NULL && s->bb_beg == s->bb_end
1267       && REORDER_BLOCK_SCOPE (s->bb_beg)
1268       && REORDER_BLOCK_SCOPE (s->bb_beg)->level + 1 == s->level)
1269     {
1270       fprintf (stderr, "%*s", indent, "");
1271       fprintf (stderr, "BB%d:\n", s->bb_beg->index);
1272     }
1273
1274   fprintf (stderr, "%*s", indent, "");
1275   fprintf (stderr, "{ level %d (block %p)\n", s->level,
1276            NOTE_BLOCK (s->note_beg));
1277
1278   fprintf (stderr, "%*s%s", indent, "", "bbs:");
1279   for (i = 0; i < s->num_bbs; i++)
1280     fprintf (stderr, " %d", s->bbs[i]->index);
1281   fprintf (stderr, "\n");
1282
1283   for (p = s->inner; p; p = p->next)
1284     dump_scope_forest_1 (p, indent + 2);
1285
1286   fprintf (stderr, "%*s", indent, "");
1287   fprintf (stderr, "}\n");
1288 }
1289
1290
1291 /* Reorder basic blocks.  */
1292
1293 void
1294 reorder_basic_blocks ()
1295 {
1296   int i, j;
1297   struct loops loops_info;
1298   int num_loops;
1299   scope_forest_info forest;
1300
1301   if (profile_arc_flag)
1302     return;
1303
1304   if (n_basic_blocks <= 1)
1305     return;
1306
1307   /* Exception edges are not currently handled.  */
1308   for (i = 0; i < n_basic_blocks; i++)
1309     {
1310       edge e;
1311
1312       for (e = BASIC_BLOCK (i)->succ; e && ! (e->flags & EDGE_EH);
1313            e = e->succ_next)
1314         continue;
1315
1316       if (e && (e->flags & EDGE_EH))
1317         return;
1318     }
1319
1320   reorder_index = 0;
1321
1322   /* Find natural loops using the CFG.  */
1323   num_loops = flow_loops_find (&loops_info);
1324
1325   /* Dump loop information.  */
1326   flow_loops_dump (&loops_info, rtl_dump_file, 0);
1327
1328   reorder_last_visited = BASIC_BLOCK (0);
1329
1330   for (i = 0; i < n_basic_blocks; i++)
1331     {
1332       basic_block bbi = BASIC_BLOCK (i);
1333       bbi->aux = xcalloc (1, sizeof (struct reorder_block_def));
1334       *((struct reorder_block_def *)bbi->aux) = rbd_init;
1335     }
1336
1337   build_scope_forest (&forest);
1338   remove_scope_notes ();
1339
1340   for (i = 0; i < n_basic_blocks; i++)
1341     {
1342       basic_block bbi = BASIC_BLOCK (i);
1343       REORDER_BLOCK_EFF_END (bbi) = skip_insns_after_block (bbi);
1344       if (i == 0)
1345         REORDER_BLOCK_EFF_HEAD (bbi) = get_insns ();
1346       else
1347         {
1348           rtx prev_eff_end = REORDER_BLOCK_EFF_END (BASIC_BLOCK (i - 1));
1349           REORDER_BLOCK_EFF_HEAD (bbi) = NEXT_INSN (prev_eff_end);
1350         }
1351     }
1352
1353   /* If we've not got epilogue in RTL, we must fallthru to the exit.
1354      Force the last block to be at the end.  */
1355   /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
1356      end of the function for stack unwinding purposes.  */
1357
1358 #ifndef HAVE_epilogue
1359 #define HAVE_epilogue 0
1360 #endif
1361
1362   if (! HAVE_epilogue)
1363     {
1364       basic_block last = BASIC_BLOCK (n_basic_blocks - 1);
1365       REORDER_BLOCK_INDEX (last) = n_basic_blocks - 1;
1366       REORDER_BLOCK_FLAGS (last) |= REORDER_BLOCK_VISITED;
1367     }
1368
1369   make_reorder_chain (BASIC_BLOCK (0));
1370
1371   fixup_reorder_chain ();
1372
1373 #ifdef ENABLE_CHECKING
1374   verify_insn_chain ();
1375 #endif
1376
1377   /* Put basic_block_info in new order.  */
1378   for (i = 0; i < n_basic_blocks - 1; i++)
1379     {
1380       for (j = i; i != REORDER_BLOCK_INDEX (BASIC_BLOCK (j)); j++)
1381         continue;
1382
1383       if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j)) == i
1384           && i != j)
1385         {
1386           basic_block tempbb;
1387           int temprbi;
1388           int rbi = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
1389
1390           temprbi = BASIC_BLOCK (rbi)->index;
1391           BASIC_BLOCK (rbi)->index = BASIC_BLOCK (j)->index;
1392           BASIC_BLOCK (j)->index = temprbi;
1393           tempbb = BASIC_BLOCK (rbi);
1394           BASIC_BLOCK (rbi) = BASIC_BLOCK (j);
1395           BASIC_BLOCK (j) = tempbb;
1396         }
1397     }
1398
1399   rebuild_scope_notes (&forest);
1400   free_scope_forest (&forest);
1401   reorder_blocks ();
1402
1403 #ifdef ENABLE_CHECKING
1404   verify_flow_info ();
1405 #endif
1406
1407   for (i = 0; i < n_basic_blocks; i++)
1408     free (BASIC_BLOCK (i)->aux);
1409
1410   /* Free loop information.  */
1411   flow_loops_free (&loops_info);
1412
1413 }
1414