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