gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000, 2002, 2003 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify it
   7    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    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING.  If not, write to the Free
  18    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19    02111-1307, USA.  */
  20
  21 /* This (greedy) algorithm constructs traces in several rounds.
  22    The construction starts from "seeds".  The seed for the first round
  23    is the entry point of function.  When there are more than one seed
  24    that one is selected first that has the lowest key in the heap
  25    (see function bb_to_key).  Then the algorithm repeatedly adds the most
  26    probable successor to the end of a trace.  Finally it connects the traces.
  27
  28    There are two parameters: Branch Threshold and Exec Threshold.
  29    If the edge to a successor of the actual basic block is lower than
  30    Branch Threshold or the frequency of the successor is lower than
  31    Exec Threshold the successor will be the seed in one of the next rounds.
  32    Each round has these parameters lower than the previous one.
  33    The last round has to have these parameters set to zero
  34    so that the remaining blocks are picked up.
  35
  36    The algorithm selects the most probable successor from all unvisited
  37    successors and successors that have been added to this trace.
  38    The other successors (that has not been "sent" to the next round) will be
  39    other seeds for this round and the secondary traces will start in them.
  40    If the successor has not been visited in this trace it is added to the trace
  41    (however, there is some heuristic for simple branches).
  42    If the successor has been visited in this trace the loop has been found.
  43    If the loop has many iterations the loop is rotated so that the
  44    source block of the most probable edge going out from the loop
  45    is the last block of the trace.
  46    If the loop has few iterations and there is no edge from the last block of
  47    the loop going out from loop the loop header is duplicated.
  48    Finally, the construction of the trace is terminated.
  49
  50    When connecting traces it first checks whether there is an edge from the
  51    last block of one trace to the first block of another trace.
  52    When there are still some unconnected traces it checks whether there exists
  53    a basic block BB such that BB is a successor of the last bb of one trace
  54    and BB is a predecessor of the first block of another trace. In this case,
  55    BB is duplicated and the traces are connected through this duplicate.
  56    The rest of traces are simply connected so there will be a jump to the
  57    beginning of the rest of trace.
  58
  59
  60    References:
  61
  62    "Software Trace Cache"
  63    A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
  64    http://citeseer.nj.nec.com/15361.html
  65
  66 */
  67
  68 #include "config.h"
  69 #include "system.h"
  70 #include "coretypes.h"
  71 #include "tm.h"
  72 #include "rtl.h"
  73 #include "basic-block.h"
  74 #include "flags.h"
  75 #include "output.h"
  76 #include "cfglayout.h"
  77 #include "fibheap.h"
  78 #include "target.h"
  79
  80 /* The number of rounds.  */
  81 #define N_ROUNDS 4
  82
  83 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.  */
  84 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0};
  85
  86 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0.  */
  87 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0};
  88
  89 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
  90    block the edge destination is not duplicated while connecting traces.  */
  91 #define DUPLICATION_THRESHOLD 100
  92
  93 /* Length of unconditional jump instruction.  */
  94 static int uncond_jump_length;
  95
  96 /* Structure to hold needed information for each basic block.  */
  97 typedef struct bbro_basic_block_data_def
  98 {
  99   /* Which trace is the bb start of (-1 means it is not a start of a trace).  */
 100   int start_of_trace;
 101
 102   /* Which trace is the bb end of (-1 means it is not an end of a trace).  */
 103   int end_of_trace;
 104
 105   /* Which heap is BB in (if any)?  */
 106   fibheap_t heap;
 107
 108   /* Which heap node is BB in (if any)?  */
 109   fibnode_t node;
 110 } bbro_basic_block_data;
 111
 112 /* The current size of the following dynamic array.  */
 113 static int array_size;
 114
 115 /* The array which holds needed information for basic blocks.  */
 116 static bbro_basic_block_data *bbd;
 117
 118 /* To avoid frequent reallocation the size of arrays is greater than needed,
 119    the number of elements is (not less than) 1.25 * size_wanted.  */
 120 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
 121
 122 /* Free the memory and set the pointer to NULL.  */
 123 #define FREE(P) \
 124   do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
 125
 126 /* Structure for holding information about a trace.  */
 127 struct trace
 128 {
 129   /* First and last basic block of the trace.  */
 130   basic_block first, last;
 131
 132   /* The round of the STC creation which this trace was found in.  */
 133   int round;
 134
 135   /* The length (i.e. the number of basic blocks) of the trace.  */
 136   int length;
 137 };
 138
 139 /* Maximum frequency and count of one of the entry blocks.  */
 140 int max_entry_frequency;
 141 gcov_type max_entry_count;
 142
 143 /* Local function prototypes.  */
 144 static void find_traces (int *, struct trace *);
 145 static basic_block rotate_loop (edge, struct trace *, int);
 146 static void mark_bb_visited (basic_block, int);
 147 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
 148                                  int, fibheap_t *);
 149 static basic_block copy_bb (basic_block, edge, basic_block, int);
 150 static fibheapkey_t bb_to_key (basic_block);
 151 static bool better_edge_p (basic_block, edge, int, int, int, int);
 152 static void connect_traces (int, struct trace *);
 153 static bool copy_bb_p (basic_block, int);
 154 static int get_uncond_jump_length (void);
 155 \f
 156 /* Find the traces for Software Trace Cache.  Chain each trace through
 157    RBI()->next.  Store the number of traces to N_TRACES and description of
 158    traces to TRACES.  */
 159
 160 static void
 161 find_traces (int *n_traces, struct trace *traces)
 162 {
 163   int i;
 164   edge e;
 165   fibheap_t heap;
 166
 167   /* Insert entry points of function into heap.  */
 168   heap = fibheap_new ();
 169   max_entry_frequency = 0;
 170   max_entry_count = 0;
 171   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 172     {
 173       bbd[e->dest->index].heap = heap;
 174       bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
 175                                                     e->dest);
 176       if (e->dest->frequency > max_entry_frequency)
 177         max_entry_frequency = e->dest->frequency;
 178       if (e->dest->count > max_entry_count)
 179         max_entry_count = e->dest->count;
 180     }
 181
 182   /* Find the traces.  */
 183   for (i = 0; i < N_ROUNDS; i++)
 184     {
 185       gcov_type count_threshold;
 186
 187       if (rtl_dump_file)
 188         fprintf (rtl_dump_file, "STC - round %d\n", i + 1);
 189
 190       if (max_entry_count < INT_MAX / 1000)
 191         count_threshold = max_entry_count * exec_threshold[i] / 1000;
 192       else
 193         count_threshold = max_entry_count / 1000 * exec_threshold[i];
 194
 195       find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
 196                            max_entry_frequency * exec_threshold[i] / 1000,
 197                            count_threshold, traces, n_traces, i, &heap);
 198     }
 199   fibheap_delete (heap);
 200
 201   if (rtl_dump_file)
 202     {
 203       for (i = 0; i < *n_traces; i++)
 204         {
 205           basic_block bb;
 206           fprintf (rtl_dump_file, "Trace %d (round %d):  ", i + 1,
 207                    traces[i].round + 1);
 208           for (bb = traces[i].first; bb != traces[i].last; bb = bb->rbi->next)
 209             fprintf (rtl_dump_file, "%d [%d] ", bb->index, bb->frequency);
 210           fprintf (rtl_dump_file, "%d [%d]\n", bb->index, bb->frequency);
 211         }
 212       fflush (rtl_dump_file);
 213     }
 214 }
 215
 216 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
 217    (with sequential number TRACE_N).  */
 218
 219 static basic_block
 220 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
 221 {
 222   basic_block bb;
 223
 224   /* Information about the best end (end after rotation) of the loop.  */
 225   basic_block best_bb = NULL;
 226   edge best_edge = NULL;
 227   int best_freq = -1;
 228   gcov_type best_count = -1;
 229   /* The best edge is preferred when its destination is not visited yet
 230      or is a start block of some trace.  */
 231   bool is_preferred = false;
 232
 233   /* Find the most frequent edge that goes out from current trace.  */
 234   bb = back_edge->dest;
 235   do
 236     {
 237       edge e;
 238       for (e = bb->succ; e; e = e->succ_next)
 239         if (e->dest != EXIT_BLOCK_PTR
 240             && e->dest->rbi->visited != trace_n
 241             && (e->flags & EDGE_CAN_FALLTHRU)
 242             && !(e->flags & EDGE_COMPLEX))
 243         {
 244           if (is_preferred)
 245             {
 246               /* The best edge is preferred.  */
 247               if (!e->dest->rbi->visited
 248                   || bbd[e->dest->index].start_of_trace >= 0)
 249                 {
 250                   /* The current edge E is also preferred.  */
 251                   int freq = EDGE_FREQUENCY (e);
 252                   if (freq > best_freq || e->count > best_count)
 253                     {
 254                       best_freq = freq;
 255                       best_count = e->count;
 256                       best_edge = e;
 257                       best_bb = bb;
 258                     }
 259                 }
 260             }
 261           else
 262             {
 263               if (!e->dest->rbi->visited
 264                   || bbd[e->dest->index].start_of_trace >= 0)
 265                 {
 266                   /* The current edge E is preferred.  */
 267                   is_preferred = true;
 268                   best_freq = EDGE_FREQUENCY (e);
 269                   best_count = e->count;
 270                   best_edge = e;
 271                   best_bb = bb;
 272                 }
 273               else
 274                 {
 275                   int freq = EDGE_FREQUENCY (e);
 276                   if (!best_edge || freq > best_freq || e->count > best_count)
 277                     {
 278                       best_freq = freq;
 279                       best_count = e->count;
 280                       best_edge = e;
 281                       best_bb = bb;
 282                     }
 283                 }
 284             }
 285         }
 286       bb = bb->rbi->next;
 287     }
 288   while (bb != back_edge->dest);
 289
 290   if (best_bb)
 291     {
 292       /* Rotate the loop so that the BEST_EDGE goes out from the last block of
 293          the trace.  */
 294       if (back_edge->dest == trace->first)
 295         {
 296           trace->first = best_bb->rbi->next;
 297         }
 298       else
 299         {
 300           basic_block prev_bb;
 301
 302           for (prev_bb = trace->first;
 303                prev_bb->rbi->next != back_edge->dest;
 304                prev_bb = prev_bb->rbi->next)
 305             ;
 306           prev_bb->rbi->next = best_bb->rbi->next;
 307
 308           /* Try to get rid of uncond jump to cond jump.  */
 309           if (prev_bb->succ && !prev_bb->succ->succ_next)
 310             {
 311               basic_block header = prev_bb->succ->dest;
 312
 313               /* Duplicate HEADER if it is a small block containing cond jump
 314                  in the end.  */
 315               if (any_condjump_p (header->end) && copy_bb_p (header, 0))
 316                 {
 317                   copy_bb (header, prev_bb->succ, prev_bb, trace_n);
 318                 }
 319             }
 320         }
 321     }
 322   else
 323     {
 324       /* We have not found suitable loop tail so do no rotation.  */
 325       best_bb = back_edge->src;
 326     }
 327   best_bb->rbi->next = NULL;
 328   return best_bb;
 329 }
 330
 331 /* This function marks BB that it was visited in trace number TRACE.  */
 332
 333 static void
 334 mark_bb_visited (basic_block bb, int trace)
 335 {
 336   bb->rbi->visited = trace;
 337   if (bbd[bb->index].heap)
 338     {
 339       fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
 340       bbd[bb->index].heap = NULL;
 341       bbd[bb->index].node = NULL;
 342     }
 343 }
 344
 345 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
 346    not include basic blocks their probability is lower than BRANCH_TH or their
 347    frequency is lower than EXEC_TH into traces (or count is lower than
 348    COUNT_TH).  It stores the new traces into TRACES and modifies the number of
 349    traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
 350    expects that starting basic blocks are in *HEAP and at the end it deletes
 351    *HEAP and stores starting points for the next round into new *HEAP.  */
 352
 353 static void
 354 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
 355                      struct trace *traces, int *n_traces, int round,
 356                      fibheap_t *heap)
 357 {
 358   /* Heap for discarded basic blocks which are possible starting points for
 359      the next round.  */
 360   fibheap_t new_heap = fibheap_new ();
 361
 362   while (!fibheap_empty (*heap))
 363     {
 364       basic_block bb;
 365       struct trace *trace;
 366       edge best_edge, e;
 367       fibheapkey_t key;
 368
 369       bb = fibheap_extract_min (*heap);
 370       bbd[bb->index].heap = NULL;
 371       bbd[bb->index].node = NULL;
 372
 373       if (rtl_dump_file)
 374         fprintf (rtl_dump_file, "Getting bb %d\n", bb->index);
 375
 376       /* If the BB's frequency is too low send BB to the next round.  */
 377       if (round < N_ROUNDS - 1
 378           && (bb->frequency < exec_th || bb->count < count_th
 379               || probably_never_executed_bb_p (bb)))
 380         {
 381           int key = bb_to_key (bb);
 382           bbd[bb->index].heap = new_heap;
 383           bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
 384
 385           if (rtl_dump_file)
 386             fprintf (rtl_dump_file,
 387                      "  Possible start point of next round: %d (key: %d)\n",
 388                      bb->index, key);
 389           continue;
 390         }
 391
 392       trace = traces + *n_traces;
 393       trace->first = bb;
 394       trace->round = round;
 395       trace->length = 0;
 396       (*n_traces)++;
 397
 398       do
 399         {
 400           int prob, freq;
 401
 402           /* The probability and frequency of the best edge.  */
 403           int best_prob = INT_MIN / 2;
 404           int best_freq = INT_MIN / 2;
 405
 406           best_edge = NULL;
 407           mark_bb_visited (bb, *n_traces);
 408           trace->length++;
 409
 410           if (rtl_dump_file)
 411             fprintf (rtl_dump_file, "Basic block %d was visited in trace %d\n",
 412                      bb->index, *n_traces - 1);
 413
 414           /* Select the successor that will be placed after BB.  */
 415           for (e = bb->succ; e; e = e->succ_next)
 416             {
 417               if (e->flags & EDGE_FAKE)
 418                 abort ();
 419
 420               if (e->dest == EXIT_BLOCK_PTR)
 421                 continue;
 422
 423               if (e->dest->rbi->visited
 424                   && e->dest->rbi->visited != *n_traces)
 425                 continue;
 426
 427               prob = e->probability;
 428               freq = EDGE_FREQUENCY (e);
 429
 430               /* Edge that cannot be fallthru or improbable or infrequent
 431                  successor (ie. it is unsuitable successor).  */
 432               if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
 433                   || prob < branch_th || freq < exec_th || e->count < count_th)
 434                 continue;
 435
 436               if (better_edge_p (bb, e, prob, freq, best_prob, best_freq))
 437                 {
 438                   best_edge = e;
 439                   best_prob = prob;
 440                   best_freq = freq;
 441                 }
 442             }
 443
 444           /* If the best destination has multiple predecessors, and can be
 445              duplicated cheaper than a jump, don't allow it to be added
 446              to a trace.  We'll duplicate it when connecting traces.  */
 447           if (best_edge && best_edge->dest->pred->pred_next
 448               && copy_bb_p (best_edge->dest, 0))
 449             best_edge = NULL;
 450
 451           /* Add all non-selected successors to the heaps.  */
 452           for (e = bb->succ; e; e = e->succ_next)
 453             {
 454               if (e == best_edge
 455                   || e->dest == EXIT_BLOCK_PTR
 456                   || e->dest->rbi->visited)
 457                 continue;
 458
 459               key = bb_to_key (e->dest);
 460
 461               if (bbd[e->dest->index].heap)
 462                 {
 463                   /* E->DEST is already in some heap.  */
 464                   if (key != bbd[e->dest->index].node->key)
 465                     {
 466                       if (rtl_dump_file)
 467                         {
 468                           fprintf (rtl_dump_file,
 469                                    "Changing key for bb %d from %ld to %ld.\n",
 470                                    e->dest->index,
 471                                    (long) bbd[e->dest->index].node->key,
 472                                    key);
 473                         }
 474                       fibheap_replace_key (bbd[e->dest->index].heap,
 475                                            bbd[e->dest->index].node, key);
 476                     }
 477                 }
 478               else
 479                 {
 480                   fibheap_t which_heap = *heap;
 481
 482                   prob = e->probability;
 483                   freq = EDGE_FREQUENCY (e);
 484
 485                   if (!(e->flags & EDGE_CAN_FALLTHRU)
 486                       || (e->flags & EDGE_COMPLEX)
 487                       || prob < branch_th || freq < exec_th
 488                       || e->count < count_th)
 489                     {
 490                       if (round < N_ROUNDS - 1)
 491                         which_heap = new_heap;
 492                     }
 493
 494                   bbd[e->dest->index].heap = which_heap;
 495                   bbd[e->dest->index].node = fibheap_insert (which_heap,
 496                                                                 key, e->dest);
 497
 498                   if (rtl_dump_file)
 499                     {
 500                       fprintf (rtl_dump_file,
 501                                "  Possible start of %s round: %d (key: %ld)\n",
 502                                (which_heap == new_heap) ? "next" : "this",
 503                                e->dest->index, (long) key);
 504                     }
 505
 506                 }
 507             }
 508
 509           if (best_edge) /* Suitable successor was found.  */
 510             {
 511               if (best_edge->dest->rbi->visited == *n_traces)
 512                 {
 513                   /* We do nothing with one basic block loops.  */
 514                   if (best_edge->dest != bb)
 515                     {
 516                       if (EDGE_FREQUENCY (best_edge)
 517                           > 4 * best_edge->dest->frequency / 5)
 518                         {
 519                           /* The loop has at least 4 iterations.  If the loop
 520                              header is not the first block of the function
 521                              we can rotate the loop.  */
 522
 523                           if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
 524                             {
 525                               if (rtl_dump_file)
 526                                 {
 527                                   fprintf (rtl_dump_file,
 528                                            "Rotating loop %d - %d\n",
 529                                            best_edge->dest->index, bb->index);
 530                                 }
 531                               bb->rbi->next = best_edge->dest;
 532                               bb = rotate_loop (best_edge, trace, *n_traces);
 533                             }
 534                         }
 535                       else
 536                         {
 537                           /* The loop has less than 4 iterations.  */
 538
 539                           /* Check whether there is another edge from BB.  */
 540                           edge another_edge;
 541                           for (another_edge = bb->succ;
 542                                another_edge;
 543                                another_edge = another_edge->succ_next)
 544                             if (another_edge != best_edge)
 545                               break;
 546
 547                           if (!another_edge && copy_bb_p (best_edge->dest,
 548                                                           !optimize_size))
 549                             {
 550                               bb = copy_bb (best_edge->dest, best_edge, bb,
 551                                             *n_traces);
 552                             }
 553                         }
 554                     }
 555
 556                   /* Terminate the trace.  */
 557                   break;
 558                 }
 559               else
 560                 {
 561                   /* Check for a situation
 562
 563                     A
 564                    /|
 565                   B |
 566                    \|
 567                     C
 568
 569                   where
 570                   EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
 571                     >= EDGE_FREQUENCY (AC).
 572                   (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
 573                   Best ordering is then A B C.
 574
 575                   This situation is created for example by:
 576
 577                   if (A) B;
 578                   C;
 579
 580                   */
 581
 582                   for (e = bb->succ; e; e = e->succ_next)
 583                     if (e != best_edge
 584                         && (e->flags & EDGE_CAN_FALLTHRU)
 585                         && !(e->flags & EDGE_COMPLEX)
 586                         && !e->dest->rbi->visited
 587                         && !e->dest->pred->pred_next
 588                         && e->dest->succ
 589                         && (e->dest->succ->flags & EDGE_CAN_FALLTHRU)
 590                         && !(e->dest->succ->flags & EDGE_COMPLEX)
 591                         && !e->dest->succ->succ_next
 592                         && e->dest->succ->dest == best_edge->dest
 593                         && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
 594                       {
 595                         best_edge = e;
 596                         if (rtl_dump_file)
 597                           fprintf (rtl_dump_file, "Selecting BB %d\n",
 598                                    best_edge->dest->index);
 599                         break;
 600                       }
 601
 602                   bb->rbi->next = best_edge->dest;
 603                   bb = best_edge->dest;
 604                 }
 605             }
 606         }
 607       while (best_edge);
 608       trace->last = bb;
 609       bbd[trace->first->index].start_of_trace = *n_traces - 1;
 610       bbd[trace->last->index].end_of_trace = *n_traces - 1;
 611
 612       /* The trace is terminated so we have to recount the keys in heap
 613          (some block can have a lower key because now one of its predecessors
 614          is an end of the trace).  */
 615       for (e = bb->succ; e; e = e->succ_next)
 616         {
 617           if (e->dest == EXIT_BLOCK_PTR
 618               || e->dest->rbi->visited)
 619             continue;
 620
 621           if (bbd[e->dest->index].heap)
 622             {
 623               key = bb_to_key (e->dest);
 624               if (key != bbd[e->dest->index].node->key)
 625                 {
 626                   if (rtl_dump_file)
 627                     {
 628                       fprintf (rtl_dump_file,
 629                                "Changing key for bb %d from %ld to %ld.\n",
 630                                e->dest->index,
 631                                (long) bbd[e->dest->index].node->key, key);
 632                     }
 633                   fibheap_replace_key (bbd[e->dest->index].heap,
 634                                        bbd[e->dest->index].node,
 635                                        key);
 636                 }
 637             }
 638         }
 639     }
 640
 641   fibheap_delete (*heap);
 642
 643   /* "Return" the new heap.  */
 644   *heap = new_heap;
 645 }
 646
 647 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
 648    it to trace after BB, mark OLD_BB visited and update pass' data structures
 649    (TRACE is a number of trace which OLD_BB is duplicated to).  */
 650
 651 static basic_block
 652 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
 653 {
 654   basic_block new_bb;
 655
 656   new_bb = cfg_layout_duplicate_bb (old_bb, e);
 657   if (e->dest != new_bb)
 658     abort ();
 659   if (e->dest->rbi->visited)
 660     abort ();
 661   if (rtl_dump_file)
 662     fprintf (rtl_dump_file,
 663              "Duplicated bb %d (created bb %d)\n",
 664              old_bb->index, new_bb->index);
 665   new_bb->rbi->visited = trace;
 666   new_bb->rbi->next = bb->rbi->next;
 667   bb->rbi->next = new_bb;
 668
 669   if (new_bb->index >= array_size || last_basic_block > array_size)
 670     {
 671       int i;
 672       int new_size;
 673
 674       new_size = MAX (last_basic_block, new_bb->index + 1);
 675       new_size = GET_ARRAY_SIZE (new_size);
 676       bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
 677       for (i = array_size; i < new_size; i++)
 678         {
 679           bbd[i].start_of_trace = -1;
 680           bbd[i].end_of_trace = -1;
 681           bbd[i].heap = NULL;
 682           bbd[i].node = NULL;
 683         }
 684       array_size = new_size;
 685
 686       if (rtl_dump_file)
 687         {
 688           fprintf (rtl_dump_file,
 689                    "Growing the dynamic array to %d elements.\n",
 690                    array_size);
 691         }
 692     }
 693
 694   return new_bb;
 695 }
 696
 697 /* Compute and return the key (for the heap) of the basic block BB.  */
 698
 699 static fibheapkey_t
 700 bb_to_key (basic_block bb)
 701 {
 702   edge e;
 703
 704   int priority = 0;
 705
 706   /* Do not start in probably never executed blocks.  */
 707   if (probably_never_executed_bb_p (bb))
 708     return BB_FREQ_MAX;
 709
 710   /* Prefer blocks whose predecessor is an end of some trace
 711      or whose predecessor edge is EDGE_DFS_BACK.  */
 712   for (e = bb->pred; e; e = e->pred_next)
 713     {
 714       if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
 715           || (e->flags & EDGE_DFS_BACK))
 716         {
 717           int edge_freq = EDGE_FREQUENCY (e);
 718
 719           if (edge_freq > priority)
 720             priority = edge_freq;
 721         }
 722     }
 723
 724   if (priority)
 725     /* The block with priority should have significantly lower key.  */
 726     return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
 727   return -bb->frequency;
 728 }
 729
 730 /* Return true when the edge E from basic block BB is better than the temporary
 731    best edge (details are in function).  The probability of edge E is PROB. The
 732    frequency of the successor is FREQ.  The current best probability is
 733    BEST_PROB, the best frequency is BEST_FREQ.
 734    The edge is considered to be equivalent when PROB does not differ much from
 735    BEST_PROB; similarly for frequency.  */
 736
 737 static bool
 738 better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
 739                int best_freq)
 740 {
 741   bool is_better_edge;
 742
 743   /* The BEST_* values do not have to be best, but can be a bit smaller than
 744      maximum values.  */
 745   int diff_prob = best_prob / 10;
 746   int diff_freq = best_freq / 10;
 747
 748   if (prob > best_prob + diff_prob)
 749     /* The edge has higher probability than the temporary best edge.  */
 750     is_better_edge = true;
 751   else if (prob < best_prob - diff_prob)
 752     /* The edge has lower probability than the temporary best edge.  */
 753     is_better_edge = false;
 754   else if (freq < best_freq - diff_freq)
 755     /* The edge and the temporary best edge  have almost equivalent
 756        probabilities.  The higher frequency of a successor now means
 757        that there is another edge going into that successor.
 758        This successor has lower frequency so it is better.  */
 759     is_better_edge = true;
 760   else if (freq > best_freq + diff_freq)
 761     /* This successor has higher frequency so it is worse.  */
 762     is_better_edge = false;
 763   else if (e->dest->prev_bb == bb)
 764     /* The edges have equivalent probabilities and the successors
 765        have equivalent frequencies.  Select the previous successor.  */
 766     is_better_edge = true;
 767   else
 768     is_better_edge = false;
 769
 770   return is_better_edge;
 771 }
 772
 773 /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
 774
 775 static void
 776 connect_traces (int n_traces, struct trace *traces)
 777 {
 778   int i;
 779   bool *connected;
 780   int last_trace;
 781   int freq_threshold;
 782   gcov_type count_threshold;
 783
 784   freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
 785   if (max_entry_count < INT_MAX / 1000)
 786     count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
 787   else
 788     count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
 789
 790   connected = xcalloc (n_traces, sizeof (bool));
 791   last_trace = -1;
 792   for (i = 0; i < n_traces; i++)
 793     {
 794       int t = i;
 795       int t2;
 796       edge e, best;
 797       int best_len;
 798
 799       if (connected[t])
 800         continue;
 801
 802       connected[t] = true;
 803
 804       /* Find the predecessor traces.  */
 805       for (t2 = t; t2 > 0;)
 806         {
 807           best = NULL;
 808           best_len = 0;
 809           for (e = traces[t2].first->pred; e; e = e->pred_next)
 810             {
 811               int si = e->src->index;
 812
 813               if (e->src != ENTRY_BLOCK_PTR
 814                   && (e->flags & EDGE_CAN_FALLTHRU)
 815                   && !(e->flags & EDGE_COMPLEX)
 816                   && bbd[si].end_of_trace >= 0
 817                   && !connected[bbd[si].end_of_trace]
 818                   && (!best
 819                       || e->probability > best->probability
 820                       || (e->probability == best->probability
 821                           && traces[bbd[si].end_of_trace].length > best_len)))
 822                 {
 823                   best = e;
 824                   best_len = traces[bbd[si].end_of_trace].length;
 825                 }
 826             }
 827           if (best)
 828             {
 829               best->src->rbi->next = best->dest;
 830               t2 = bbd[best->src->index].end_of_trace;
 831               connected[t2] = true;
 832               if (rtl_dump_file)
 833                 {
 834                   fprintf (rtl_dump_file, "Connection: %d %d\n",
 835                            best->src->index, best->dest->index);
 836                 }
 837             }
 838           else
 839             break;
 840         }
 841
 842       if (last_trace >= 0)
 843         traces[last_trace].last->rbi->next = traces[t2].first;
 844       last_trace = t;
 845
 846       /* Find the successor traces.  */
 847       while (1)
 848         {
 849           /* Find the continuation of the chain.  */
 850           best = NULL;
 851           best_len = 0;
 852           for (e = traces[t].last->succ; e; e = e->succ_next)
 853             {
 854               int di = e->dest->index;
 855
 856               if (e->dest != EXIT_BLOCK_PTR
 857                   && (e->flags & EDGE_CAN_FALLTHRU)
 858                   && !(e->flags & EDGE_COMPLEX)
 859                   && bbd[di].start_of_trace >= 0
 860                   && !connected[bbd[di].start_of_trace]
 861                   && (!best
 862                       || e->probability > best->probability
 863                       || (e->probability == best->probability
 864                           && traces[bbd[di].start_of_trace].length > best_len)))
 865                 {
 866                   best = e;
 867                   best_len = traces[bbd[di].start_of_trace].length;
 868                 }
 869             }
 870
 871           if (best)
 872             {
 873               if (rtl_dump_file)
 874                 {
 875                   fprintf (rtl_dump_file, "Connection: %d %d\n",
 876                            best->src->index, best->dest->index);
 877                 }
 878               t = bbd[best->dest->index].start_of_trace;
 879               traces[last_trace].last->rbi->next = traces[t].first;
 880               connected[t] = true;
 881               last_trace = t;
 882             }
 883           else
 884             {
 885               /* Try to connect the traces by duplication of 1 block.  */
 886               edge e2;
 887               basic_block next_bb = NULL;
 888               bool try_copy = false;
 889
 890               for (e = traces[t].last->succ; e; e = e->succ_next)
 891                 if (e->dest != EXIT_BLOCK_PTR
 892                     && (e->flags & EDGE_CAN_FALLTHRU)
 893                     && !(e->flags & EDGE_COMPLEX)
 894                     && (!best || e->probability > best->probability))
 895                   {
 896                     edge best2 = NULL;
 897                     int best2_len = 0;
 898
 899                     /* If the destination is a start of a trace which is only
 900                        one block long, then no need to search the successor
 901                        blocks of the trace.  Accept it.  */
 902                     if (bbd[e->dest->index].start_of_trace >= 0
 903                         && traces[bbd[e->dest->index].start_of_trace].length
 904                            == 1)
 905                       {
 906                         best = e;
 907                         try_copy = true;
 908                         continue;
 909                       }
 910
 911                     for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
 912                       {
 913                         int di = e2->dest->index;
 914
 915                         if (e2->dest == EXIT_BLOCK_PTR
 916                             || ((e2->flags & EDGE_CAN_FALLTHRU)
 917                                 && !(e2->flags & EDGE_COMPLEX)
 918                                 && bbd[di].start_of_trace >= 0
 919                                 && !connected[bbd[di].start_of_trace]
 920                                 && (EDGE_FREQUENCY (e2) >= freq_threshold)
 921                                 && (e2->count >= count_threshold)
 922                                 && (!best2
 923                                     || e2->probability > best2->probability
 924                                     || (e2->probability == best2->probability
 925                                         && traces[bbd[di].start_of_trace].length
 926                                            > best2_len))))
 927                           {
 928                             best = e;
 929                             best2 = e2;
 930                             if (e2->dest != EXIT_BLOCK_PTR)
 931                               best2_len = traces[bbd[di].start_of_trace].length;
 932                             else
 933                               best2_len = INT_MAX;
 934                             next_bb = e2->dest;
 935                             try_copy = true;
 936                           }
 937                       }
 938                   }
 939
 940               /* Copy tiny blocks always; copy larger blocks only when the
 941                  edge is traversed frequently enough.  */
 942               if (try_copy
 943                   && copy_bb_p (best->dest,
 944                                 !optimize_size
 945                                 && EDGE_FREQUENCY (best) >= freq_threshold
 946                                 && best->count >= count_threshold))
 947                 {
 948                   basic_block new_bb;
 949
 950                   if (rtl_dump_file)
 951                     {
 952                       fprintf (rtl_dump_file, "Connection: %d %d ",
 953                                traces[t].last->index, best->dest->index);
 954                       if (!next_bb)
 955                         fputc ('\n', rtl_dump_file);
 956                       else if (next_bb == EXIT_BLOCK_PTR)
 957                         fprintf (rtl_dump_file, "exit\n");
 958                       else
 959                         fprintf (rtl_dump_file, "%d\n", next_bb->index);
 960                     }
 961
 962                   new_bb = copy_bb (best->dest, best, traces[t].last, t);
 963                   traces[t].last = new_bb;
 964                   if (next_bb && next_bb != EXIT_BLOCK_PTR)
 965                     {
 966                       t = bbd[next_bb->index].start_of_trace;
 967                       traces[last_trace].last->rbi->next = traces[t].first;
 968                       connected[t] = true;
 969                       last_trace = t;
 970                     }
 971                   else
 972                     break;      /* Stop finding the successor traces.  */
 973                 }
 974               else
 975                 break;  /* Stop finding the successor traces.  */
 976             }
 977         }
 978     }
 979
 980   if (rtl_dump_file)
 981     {
 982       basic_block bb;
 983
 984       fprintf (rtl_dump_file, "Final order:\n");
 985       for (bb = traces[0].first; bb; bb = bb->rbi->next)
 986         fprintf (rtl_dump_file, "%d ", bb->index);
 987       fprintf (rtl_dump_file, "\n");
 988       fflush (rtl_dump_file);
 989     }
 990
 991   FREE (connected);
 992 }
 993
 994 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
 995    when code size is allowed to grow by duplication.  */
 996
 997 static bool
 998 copy_bb_p (basic_block bb, int code_may_grow)
 999 {
1000   int size = 0;
1001   int max_size = uncond_jump_length;
1002   rtx insn;
1003
1004   if (!bb->frequency)
1005     return false;
1006   if (!bb->pred || !bb->pred->pred_next)
1007     return false;
1008   if (!cfg_layout_can_duplicate_bb_p (bb))
1009     return false;
1010
1011   if (code_may_grow && maybe_hot_bb_p (bb))
1012     max_size *= 8;
1013
1014   for (insn = bb->head; insn != NEXT_INSN (bb->end);
1015        insn = NEXT_INSN (insn))
1016     {
1017       if (INSN_P (insn))
1018         size += get_attr_length (insn);
1019     }
1020
1021   if (size <= max_size)
1022     return true;
1023
1024   if (rtl_dump_file)
1025     {
1026       fprintf (rtl_dump_file,
1027                "Block %d can't be copied because its size = %d.\n",
1028                bb->index, size);
1029     }
1030
1031   return false;
1032 }
1033
1034 /* Return the length of unconditional jump instruction.  */
1035
1036 static int
1037 get_uncond_jump_length (void)
1038 {
1039   rtx label, jump;
1040   int length;
1041
1042   label = emit_label_before (gen_label_rtx (), get_insns ());
1043   jump = emit_jump_insn (gen_jump (label));
1044
1045   length = get_attr_length (jump);
1046
1047   delete_insn (jump);
1048   delete_insn (label);
1049   return length;
1050 }
1051
1052 /* Reorder basic blocks.  The main entry point to this file.  */
1053
1054 void
1055 reorder_basic_blocks (void)
1056 {
1057   int n_traces;
1058   int i;
1059   struct trace *traces;
1060
1061   if (n_basic_blocks <= 1)
1062     return;
1063
1064   if ((* targetm.cannot_modify_jumps_p) ())
1065     return;
1066
1067   cfg_layout_initialize ();
1068
1069   set_edge_can_fallthru_flag ();
1070   mark_dfs_back_edges ();
1071
1072   /* We are estimating the length of uncond jump insn only once since the code
1073      for getting the insn length always returns the minimal length now.  */
1074   if (uncond_jump_length == 0)
1075     uncond_jump_length = get_uncond_jump_length ();
1076
1077   /* We need to know some information for each basic block.  */
1078   array_size = GET_ARRAY_SIZE (last_basic_block);
1079   bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
1080   for (i = 0; i < array_size; i++)
1081     {
1082       bbd[i].start_of_trace = -1;
1083       bbd[i].end_of_trace = -1;
1084       bbd[i].heap = NULL;
1085       bbd[i].node = NULL;
1086     }
1087
1088   traces = xmalloc (n_basic_blocks * sizeof (struct trace));
1089   n_traces = 0;
1090   find_traces (&n_traces, traces);
1091   connect_traces (n_traces, traces);
1092   FREE (traces);
1093   FREE (bbd);
1094
1095   if (rtl_dump_file)
1096     dump_flow_info (rtl_dump_file);
1097
1098   cfg_layout_finalize ();
1099 }