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 typedef struct reorder_block_def {
  56   int flags;
  57   int index;
  58   basic_block add_jump;
  59   edge succ;
  60   rtx end;
  61   int block_begin;
  62   int block_end;
  63 } *reorder_block_def;
  64
  65 #define REORDER_BLOCK_HEAD      0x1
  66 #define REORDER_BLOCK_VISITED   0x2
  67 #define REORDER_MOVED_BLOCK_END 0x3
  68
  69 #define REORDER_BLOCK_FLAGS(bb) \
  70   ((reorder_block_def) (bb)->aux)->flags
  71
  72 #define REORDER_BLOCK_INDEX(bb) \
  73   ((reorder_block_def) (bb)->aux)->index
  74
  75 #define REORDER_BLOCK_ADD_JUMP(bb) \
  76   ((reorder_block_def) (bb)->aux)->add_jump
  77
  78 #define REORDER_BLOCK_SUCC(bb) \
  79   ((reorder_block_def) (bb)->aux)->succ
  80
  81 #define REORDER_BLOCK_OLD_END(bb) \
  82   ((reorder_block_def) (bb)->aux)->end
  83
  84 #define REORDER_BLOCK_BEGIN(bb) \
  85   ((reorder_block_def) (bb)->aux)->block_begin
  86
  87 #define REORDER_BLOCK_END(bb) \
  88   ((reorder_block_def) (bb)->aux)->block_end
  89
  90
  91 static int reorder_index;
  92 static basic_block reorder_last_visited;
  93
  94 enum reorder_skip_type {REORDER_SKIP_BEFORE, REORDER_SKIP_AFTER,
  95                         REORDER_SKIP_BLOCK_END};
  96
  97
  98 /* Local function prototypes.  */
  99 static rtx skip_insns_between_block     PARAMS ((basic_block,
 100                                                  enum reorder_skip_type));
 101 static basic_block get_common_dest      PARAMS ((basic_block, basic_block));
 102 static basic_block chain_reorder_blocks PARAMS ((edge, basic_block));
 103 static void make_reorder_chain          PARAMS ((basic_block));
 104 static void fixup_reorder_chain         PARAMS ((void));
 105
 106
 107 /* Skip over insns BEFORE or AFTER BB which are typically associated with
 108    basic block BB.  */
 109
 110 static rtx
 111 skip_insns_between_block (bb, skip_type)
 112      basic_block bb;
 113      enum reorder_skip_type skip_type;
 114 {
 115   rtx insn, last_insn;
 116
 117   if (skip_type == REORDER_SKIP_BEFORE)
 118     {
 119       if (bb == ENTRY_BLOCK_PTR)
 120         return 0;
 121
 122       last_insn = bb->head;
 123       for (insn = PREV_INSN (bb->head);
 124            insn && insn != BASIC_BLOCK (bb->index - 1)->end;
 125            last_insn = insn, insn = PREV_INSN (insn))
 126         {
 127           if (NEXT_INSN (insn) != last_insn)
 128             break;
 129
 130           if (GET_CODE (insn) == NOTE
 131               && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
 132               && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
 133               && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END)
 134             continue;
 135
 136           break;
 137         }
 138     }
 139
 140   else
 141     {
 142       last_insn = bb->end;
 143
 144       if (bb == EXIT_BLOCK_PTR)
 145         return 0;
 146
 147       for (insn = NEXT_INSN (bb->end);
 148            insn;
 149            last_insn = insn, insn = NEXT_INSN (insn))
 150         {
 151           if (bb->index + 1 != n_basic_blocks
 152               && insn == BASIC_BLOCK (bb->index + 1)->head)
 153             break;
 154
 155           if (GET_CODE (insn) == BARRIER
 156               || GET_CODE (insn) == JUMP_INSN
 157               || (GET_CODE (insn) == NOTE
 158                   && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
 159                       || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)))
 160             continue;
 161
 162           if (GET_CODE (insn) == CODE_LABEL
 163               && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 164               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 165                   || GET_CODE (PATTERN
 166                                (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 167             {
 168               insn = NEXT_INSN (insn);
 169               continue;
 170             }
 171           break;
 172         }
 173
 174       if (skip_type == REORDER_SKIP_BLOCK_END)
 175         {
 176           int found_block_end = 0;
 177
 178           for (; insn; last_insn = insn, insn = NEXT_INSN (insn))
 179             {
 180               if (bb->index + 1 != n_basic_blocks
 181                   && insn == BASIC_BLOCK (bb->index + 1)->head)
 182                 break;
 183
 184               if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
 185                 {
 186                   found_block_end = 1;
 187                   continue;
 188                 }
 189
 190               if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
 191                 continue;
 192
 193               if (GET_CODE (insn) == NOTE
 194                   && NOTE_LINE_NUMBER (insn) >= 0
 195                   && NEXT_INSN (insn)
 196                   && (NOTE_LINE_NUMBER (NEXT_INSN (insn))
 197                       == NOTE_INSN_BLOCK_END))
 198                 continue;
 199               break;
 200             }
 201
 202           if (! found_block_end)
 203             last_insn = 0;
 204         }
 205     }
 206
 207   return last_insn;
 208 }
 209
 210
 211 /* Return common destination for blocks BB0 and BB1.  */
 212
 213 static basic_block
 214 get_common_dest (bb0, bb1)
 215      basic_block bb0, bb1;
 216 {
 217   edge e0, e1;
 218
 219   for (e0 = bb0->succ; e0; e0 = e0->succ_next)
 220     {
 221       for (e1 = bb1->succ; e1; e1 = e1->succ_next)
 222         {
 223           if (e0->dest == e1->dest)
 224             {
 225               return e0->dest;
 226             }
 227         }
 228     }
 229   return 0;
 230 }
 231
 232
 233 /* Move the destination block for edge E after chain end block CEB
 234    Adding jumps and labels is deferred until fixup_reorder_chain.  */
 235
 236 static basic_block
 237 chain_reorder_blocks (e, ceb)
 238      edge e;
 239      basic_block ceb;
 240 {
 241   basic_block sb = e->src;
 242   basic_block db = e->dest;
 243   rtx cebe_insn, cebbe_insn, dbh_insn, dbe_insn;
 244   edge ee, last_edge;
 245
 246   enum cond_types {NO_COND, PREDICT_THEN_WITH_ELSE, PREDICT_ELSE,
 247                    PREDICT_THEN_NO_ELSE, PREDICT_NOT_THEN_NO_ELSE};
 248   enum cond_types cond_type;
 249   enum cond_block_types {NO_COND_BLOCK, THEN_BLOCK, ELSE_BLOCK,
 250                          NO_ELSE_BLOCK};
 251   enum cond_block_types cond_block_type;
 252
 253   if (rtl_dump_file)
 254     fprintf (rtl_dump_file,
 255              "Edge from basic block %d to basic block %d last visited %d\n",
 256              sb->index, db->index, ceb->index);
 257
 258   dbh_insn = skip_insns_between_block (db, REORDER_SKIP_BEFORE);
 259   cebe_insn = skip_insns_between_block (ceb, REORDER_SKIP_AFTER);
 260   cebbe_insn = skip_insns_between_block (ceb, REORDER_SKIP_BLOCK_END);
 261
 262   {
 263     int block_begins = 0;
 264     rtx insn;
 265
 266     for (insn = dbh_insn; insn && insn != db->end; insn = NEXT_INSN (insn))
 267       {
 268         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG)
 269           {
 270             block_begins += 1;
 271             break;
 272           }
 273       }
 274     REORDER_BLOCK_BEGIN (sb) = block_begins;
 275   }
 276
 277   if (cebbe_insn)
 278     {
 279       int block_ends = 0;
 280       rtx insn;
 281
 282       for (insn = cebe_insn; insn; insn = NEXT_INSN (insn))
 283         {
 284           if (PREV_INSN (insn) == cebbe_insn)
 285             break;
 286           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
 287             {
 288               block_ends += 1;
 289               continue;
 290             }
 291         }
 292       REORDER_BLOCK_END (ceb) = block_ends;
 293     }
 294
 295   /* Blocks are in original order.  */
 296   if (sb->index == ceb->index
 297       && ceb->index + 1 == db->index && NEXT_INSN (cebe_insn))
 298     return db;
 299
 300   /* Get the type of block and type of condition.  */
 301   cond_type = NO_COND;
 302   cond_block_type = NO_COND_BLOCK;
 303   if (GET_CODE (sb->end) == JUMP_INSN && ! simplejump_p (sb->end)
 304       && condjump_p (sb->end))
 305     {
 306       if (e->flags & EDGE_FALLTHRU)
 307         cond_block_type = THEN_BLOCK;
 308       else if (get_common_dest (sb->succ->dest, sb))
 309         cond_block_type = NO_ELSE_BLOCK;
 310       else
 311         cond_block_type = ELSE_BLOCK;
 312
 313       if (sb->succ->succ_next
 314           && get_common_dest (sb->succ->dest, sb))
 315         {
 316           if (cond_block_type == THEN_BLOCK)
 317             {
 318               if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
 319                      & REORDER_BLOCK_VISITED))
 320                 cond_type = PREDICT_THEN_NO_ELSE;
 321               else
 322                 cond_type = PREDICT_NOT_THEN_NO_ELSE;
 323             }
 324           else if (cond_block_type == NO_ELSE_BLOCK)
 325             {
 326               if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
 327                      & REORDER_BLOCK_VISITED))
 328                 cond_type = PREDICT_NOT_THEN_NO_ELSE;
 329               else
 330                 cond_type = PREDICT_THEN_NO_ELSE;
 331             }
 332         }
 333       else
 334         {
 335           if (cond_block_type == THEN_BLOCK)
 336             {
 337               if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
 338                      & REORDER_BLOCK_VISITED))
 339                 cond_type = PREDICT_THEN_WITH_ELSE;
 340               else
 341                 cond_type = PREDICT_ELSE;
 342             }
 343           else if (cond_block_type == ELSE_BLOCK
 344                    && sb->succ->dest != EXIT_BLOCK_PTR)
 345             {
 346               if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
 347                      & REORDER_BLOCK_VISITED))
 348                 cond_type = PREDICT_ELSE;
 349               else
 350                 cond_type = PREDICT_THEN_WITH_ELSE;
 351             }
 352         }
 353     }
 354
 355   if (rtl_dump_file)
 356     {
 357       static const char * cond_type_str [] = {"not cond jump", "predict then",
 358                                               "predict else",
 359                                               "predict then w/o else",
 360                                               "predict not then w/o else"};
 361       static const char * cond_block_type_str [] = {"not then or else block",
 362                                                     "then block",
 363                                                     "else block",
 364                                                     "then w/o else block"};
 365
 366       fprintf (rtl_dump_file, "     %s (looking at %s)\n",
 367                cond_type_str[(int)cond_type],
 368                cond_block_type_str[(int)cond_block_type]);
 369     }
 370
 371   /* Reflect that then block will move and we'll jump to it.  */
 372   if (cond_block_type != THEN_BLOCK
 373       && (cond_type == PREDICT_ELSE
 374           || cond_type == PREDICT_NOT_THEN_NO_ELSE))
 375     {
 376       if (rtl_dump_file)
 377         fprintf (rtl_dump_file,
 378                  "    then jump from block %d to block %d\n",
 379                  sb->index, sb->succ->dest->index);
 380
 381       /* Jump to reordered then block.  */
 382       REORDER_BLOCK_ADD_JUMP (sb) = sb->succ->dest;
 383     }
 384
 385   /* Reflect that then block will jump back when we have no else.  */
 386   if (cond_block_type != THEN_BLOCK
 387       && cond_type == PREDICT_NOT_THEN_NO_ELSE)
 388     {
 389       for (ee = sb->succ->dest->succ;
 390            ee && ! (ee->flags & EDGE_FALLTHRU);
 391            ee = ee->succ_next)
 392         continue;
 393
 394       if (ee && ! (GET_CODE (sb->succ->dest->end) == JUMP_INSN
 395                    && ! simplejump_p (sb->succ->dest->end)))
 396         {
 397           REORDER_BLOCK_ADD_JUMP (sb->succ->dest) = ee->dest;
 398         }
 399     }
 400
 401   /* Reflect that else block will jump back.  */
 402   if (cond_block_type == ELSE_BLOCK
 403       && (cond_type == PREDICT_THEN_WITH_ELSE || cond_type == PREDICT_ELSE))
 404     {
 405       last_edge=db->succ;
 406
 407       if (last_edge
 408           && last_edge->dest != EXIT_BLOCK_PTR
 409           && GET_CODE (last_edge->dest->head) == CODE_LABEL
 410           && ! (GET_CODE (db->end) == JUMP_INSN))
 411         {
 412           if (rtl_dump_file)
 413             fprintf (rtl_dump_file,
 414                      "     else jump from block %d to block %d\n",
 415                      db->index, last_edge->dest->index);
 416
 417           REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
 418         }
 419     }
 420
 421   /* This block's successor has already been reordered. This can happen
 422      when we reorder a chain starting at a then or else.  */
 423   for (last_edge = db->succ;
 424        last_edge && ! (last_edge->flags & EDGE_FALLTHRU);
 425        last_edge = last_edge->succ_next)
 426     continue;
 427
 428   if (last_edge
 429       && last_edge->dest != EXIT_BLOCK_PTR
 430       && (REORDER_BLOCK_FLAGS (last_edge->dest)
 431           & REORDER_BLOCK_VISITED))
 432     {
 433       if (rtl_dump_file)
 434         fprintf (rtl_dump_file,
 435                  "     end of chain jump from block %d to block %d\n",
 436                  db->index, last_edge->dest->index);
 437
 438       REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
 439     }
 440
 441   dbh_insn = skip_insns_between_block (db, REORDER_SKIP_BEFORE);
 442   cebe_insn = skip_insns_between_block (ceb, REORDER_SKIP_AFTER);
 443   dbe_insn = skip_insns_between_block (db, REORDER_SKIP_AFTER);
 444
 445   /* Leave behind any lexical block markers.  */
 446   if (debug_info_level > DINFO_LEVEL_TERSE
 447       && ceb->index + 1 < db->index)
 448     {
 449       rtx insn, last_insn = get_last_insn ();
 450       insn = NEXT_INSN (ceb->end);
 451       if (! insn)
 452         insn = REORDER_BLOCK_OLD_END (ceb);
 453
 454       if (NEXT_INSN (cebe_insn) == 0)
 455           set_last_insn (cebe_insn);
 456       for (; insn && insn != db->head/*dbh_insn*/;
 457            insn = NEXT_INSN (insn))
 458         {
 459           if (GET_CODE (insn) == NOTE
 460               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG))
 461             {
 462               cebe_insn = emit_note_after (NOTE_INSN_BLOCK_BEG, cebe_insn);
 463               delete_insn (insn);
 464             }
 465           if (GET_CODE (insn) == NOTE
 466               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
 467             {
 468               cebe_insn = emit_note_after (NOTE_INSN_BLOCK_END, cebe_insn);
 469               delete_insn (insn);
 470             }
 471         }
 472       set_last_insn (last_insn);
 473     }
 474
 475   /* Rechain predicted block.  */
 476   NEXT_INSN (cebe_insn) = dbh_insn;
 477   PREV_INSN (dbh_insn) = cebe_insn;
 478
 479   REORDER_BLOCK_OLD_END (db) = NEXT_INSN (dbe_insn);
 480   if (db->index != n_basic_blocks - 1)
 481     NEXT_INSN (dbe_insn) = 0;
 482
 483   return db;
 484 }
 485
 486
 487 /* Reorder blocks starting at block B.  */
 488
 489 static void
 490 make_reorder_chain (bb)
 491      basic_block bb;
 492 {
 493   edge e;
 494   basic_block visited_edge = NULL;
 495   rtx block_end;
 496   int probability;
 497
 498   if (bb == EXIT_BLOCK_PTR)
 499     return;
 500
 501   /* Find the most probable block.  */
 502   e = bb->succ;
 503   block_end = bb->end;
 504   if (GET_CODE (block_end) == JUMP_INSN && condjump_p (block_end))
 505     {
 506       rtx note = find_reg_note (block_end, REG_BR_PROB, 0);
 507
 508       if (note)
 509         probability = XINT (XEXP (note, 0), 0);
 510       else
 511         probability = 0;
 512
 513       if (probability >= REG_BR_PROB_BASE / 2)
 514         e = bb->succ->succ_next;
 515     }
 516
 517   /* Add chosen successor to chain and recurse on it.  */
 518   if (e && e->dest != EXIT_BLOCK_PTR
 519       && e->dest != e->src
 520       && (! (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
 521           || (REORDER_BLOCK_FLAGS (e->dest) == REORDER_BLOCK_HEAD)))
 522     {
 523       if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
 524         {
 525           REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_HEAD;
 526           REORDER_BLOCK_INDEX (bb) = reorder_index++;
 527           REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
 528         }
 529
 530       if (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
 531         REORDER_BLOCK_FLAGS (e->dest) &= ~REORDER_BLOCK_HEAD;
 532
 533       REORDER_BLOCK_SUCC (bb) = e;
 534
 535       visited_edge = e->dest;
 536
 537       reorder_last_visited = chain_reorder_blocks (e, bb);
 538
 539       if (e->dest
 540           && ! (REORDER_BLOCK_FLAGS (e->dest)
 541                 & REORDER_BLOCK_VISITED))
 542         make_reorder_chain (e->dest);
 543     }
 544   else
 545     {
 546       if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
 547         {
 548           REORDER_BLOCK_INDEX (bb) = reorder_index++;
 549           REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
 550         }
 551     }
 552
 553   /* Recurse on the successors.  */
 554   for (e = bb->succ; e; e = e->succ_next)
 555     {
 556       if (e->dest && e->dest == EXIT_BLOCK_PTR)
 557         continue;
 558
 559       if (e->dest
 560           && e->dest != e->src
 561           && e->dest != visited_edge
 562           && ! (REORDER_BLOCK_FLAGS (e->dest)
 563                 & REORDER_BLOCK_VISITED))
 564         {
 565           reorder_last_visited
 566             = chain_reorder_blocks (e, reorder_last_visited);
 567           make_reorder_chain (e->dest);
 568         }
 569     }
 570 }
 571
 572
 573 /* Fixup jumps and labels after reordering basic blocks.  */
 574
 575 static void
 576 fixup_reorder_chain ()
 577 {
 578   int i, j;
 579   rtx insn;
 580
 581   /* Set the new last insn.  */
 582   for (i = 0;
 583        i < n_basic_blocks - 1
 584          && REORDER_BLOCK_INDEX (BASIC_BLOCK (i)) != n_basic_blocks;
 585        i++)
 586     continue;
 587
 588   for (insn = BASIC_BLOCK (i)->head;
 589        NEXT_INSN (insn) != 0;
 590        insn = NEXT_INSN (insn))
 591     continue;
 592
 593   set_last_insn (insn);
 594
 595   /* Add jumps and labels to fixup blocks.  */
 596   for (i = 0; i < n_basic_blocks - 1; i++)
 597     {
 598       basic_block bbi = BASIC_BLOCK (i);
 599       if (REORDER_BLOCK_ADD_JUMP (bbi))
 600         {
 601           rtx label_insn, jump_insn, barrier_insn;
 602
 603           if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi)->head)
 604               == CODE_LABEL)
 605             label_insn  = REORDER_BLOCK_ADD_JUMP (bbi)->head;
 606           else
 607             {
 608               rtx new_label = gen_label_rtx ();
 609               label_insn = emit_label_before (new_label,
 610                               REORDER_BLOCK_ADD_JUMP (bbi)->head);
 611             }
 612           REORDER_BLOCK_ADD_JUMP (bbi)->head = label_insn;
 613
 614           jump_insn = emit_jump_insn_after (gen_jump (label_insn),
 615                                             bbi->end);
 616           JUMP_LABEL (jump_insn) = label_insn;
 617           ++LABEL_NUSES (label_insn);
 618           barrier_insn = emit_barrier_after (jump_insn);
 619           if (GET_CODE (bbi->end) != JUMP_INSN)
 620             bbi->end = jump_insn;
 621           /* Add block for jump.  Typically this is when a then is not
 622              predicted and we are jumping to the moved then block.  */
 623           else
 624             {
 625               basic_block nb;
 626
 627               VARRAY_GROW (basic_block_info, ++n_basic_blocks);
 628               create_basic_block (n_basic_blocks - 1, jump_insn,
 629                                   jump_insn, NULL);
 630               nb = BASIC_BLOCK (n_basic_blocks - 1);
 631               nb->global_live_at_start
 632                 = OBSTACK_ALLOC_REG_SET (function_obstack);
 633               nb->global_live_at_end
 634                 = OBSTACK_ALLOC_REG_SET (function_obstack);
 635
 636               COPY_REG_SET (nb->global_live_at_start,
 637                             bbi->global_live_at_start);
 638               COPY_REG_SET (nb->global_live_at_end,
 639                             bbi->global_live_at_start);
 640               BASIC_BLOCK (nb->index)->local_set = 0;
 641
 642               nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
 643               REORDER_BLOCK_INDEX (BASIC_BLOCK (n_basic_blocks - 1))
 644                 = REORDER_BLOCK_INDEX (bbi) + 1;
 645               /* Relink to new block.  */
 646               nb->succ = bbi->succ;
 647               nb->succ->src = nb;
 648
 649               make_edge (NULL, bbi, nb, 0);
 650               bbi->succ->succ_next
 651                 = bbi->succ->succ_next->succ_next;
 652               nb->succ->succ_next = 0;
 653               /* Fix reorder block index to reflect new block.  */
 654               for (j = 0; j < n_basic_blocks - 1; j++)
 655                 {
 656                   basic_block bbj = BASIC_BLOCK (j);
 657                   if (REORDER_BLOCK_INDEX (bbj)
 658                       >= REORDER_BLOCK_INDEX (bbi) + 1)
 659                     REORDER_BLOCK_INDEX (bbj)++;
 660                 }
 661             }
 662         }
 663     }
 664 }
 665
 666
 667 /* Reorder basic blocks.  */
 668
 669 void
 670 reorder_basic_blocks ()
 671 {
 672   int i, j;
 673   struct loops loops_info;
 674   int num_loops;
 675   rtx last_insn;
 676
 677   if (profile_arc_flag)
 678     return;
 679
 680   if (n_basic_blocks <= 1)
 681     return;
 682
 683   /* Exception edges are not currently handled.  */
 684   for (i = 0; i < n_basic_blocks; i++)
 685     {
 686       edge e;
 687
 688       for (e = BASIC_BLOCK (i)->succ; e && ! (e->flags & EDGE_EH);
 689            e = e->succ_next)
 690         continue;
 691
 692       if (e && (e->flags & EDGE_EH))
 693         return;
 694     }
 695
 696   reorder_index = 0;
 697
 698   /* Find natural loops using the CFG.  */
 699   num_loops = flow_loops_find (&loops_info);
 700
 701   /* Dump loop information.  */
 702   flow_loops_dump (&loops_info, rtl_dump_file, 0);
 703
 704   /* Estimate using heuristics if no profiling info is available.  */
 705   if (! flag_branch_probabilities)
 706     estimate_probability (&loops_info);
 707
 708   reorder_last_visited = BASIC_BLOCK (0);
 709
 710   for (i = 0; i < n_basic_blocks; i++)
 711     BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def));
 712
 713   last_insn
 714     = NEXT_INSN (skip_insns_between_block (BASIC_BLOCK (n_basic_blocks - 1),
 715                                            REORDER_SKIP_AFTER));
 716
 717   make_reorder_chain (BASIC_BLOCK (0));
 718
 719   fixup_reorder_chain ();
 720
 721 #ifdef ENABLE_CHECKING
 722     {
 723       rtx insn, last_insn;
 724       last_insn = get_insns ();
 725       for (insn = NEXT_INSN (get_insns ());
 726            insn && PREV_INSN (insn) == last_insn
 727              && NEXT_INSN (PREV_INSN (insn)) == insn;
 728            last_insn = insn,
 729              insn = NEXT_INSN (insn))
 730         continue;
 731
 732       if (insn)
 733         {
 734           if (rtl_dump_file)
 735             fprintf (rtl_dump_file, "insn chaining error at %d\n",
 736                      INSN_UID (last_insn));
 737           abort();
 738         }
 739     }
 740 #endif
 741
 742   /* Put basic_block_info in new order.  */
 743   for (i = 0; i < n_basic_blocks - 1; i++)
 744     {
 745       for (j = i; i != REORDER_BLOCK_INDEX (BASIC_BLOCK (j)); j++)
 746         continue;
 747
 748       if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j)) == i
 749           && i != j)
 750         {
 751           basic_block tempbb;
 752           int temprbi;
 753           int rbi = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
 754
 755           temprbi = BASIC_BLOCK (rbi)->index;
 756           BASIC_BLOCK (rbi)->index = BASIC_BLOCK (j)->index;
 757           BASIC_BLOCK (j)->index = temprbi;
 758           tempbb = BASIC_BLOCK (rbi);
 759           BASIC_BLOCK (rbi) = BASIC_BLOCK (j);
 760           BASIC_BLOCK (j) = tempbb;
 761         }
 762     }
 763
 764     {
 765       rtx xafter = skip_insns_between_block (BASIC_BLOCK (n_basic_blocks - 1),
 766                                              REORDER_SKIP_AFTER);
 767       if (xafter)
 768         {
 769           NEXT_INSN (xafter) = last_insn;
 770           if (last_insn)
 771             {
 772               rtx x = last_insn;
 773               PREV_INSN (last_insn) = xafter;
 774               while (NEXT_INSN (x))
 775                 x = NEXT_INSN (x);
 776               set_last_insn (x);
 777             }
 778         }
 779       else
 780         abort();
 781     }
 782
 783 #ifdef ENABLE_CHECKING
 784   verify_flow_info ();
 785 #endif
 786
 787   for (i = 0; i < n_basic_blocks; i++)
 788     free (BASIC_BLOCK (i)->aux);
 789
 790   /* Free loop information.  */
 791   flow_loops_free (&loops_info);
 792 }
 793