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