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