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 = RBI (bb)->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             && RBI (e->dest)->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 (!RBI (e->dest)->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 (!RBI (e->dest)->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 = RBI (bb)->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 = RBI (best_bb)->next;
 297         }
 298       else
 299         {
 300           basic_block prev_bb;
 301
 302           for (prev_bb = trace->first;
 303                RBI (prev_bb)->next != back_edge->dest;
 304                prev_bb = RBI (prev_bb)->next)
 305             ;
 306           RBI (prev_bb)->next = RBI (best_bb)->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   RBI (best_bb)->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   RBI (bb)->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 (bb->frequency < exec_th || bb->count < count_th
 378           || ((round < N_ROUNDS - 1) && probably_never_executed_bb_p (bb)))
 379         {
 380           int key = bb_to_key (bb);
 381           bbd[bb->index].heap = new_heap;
 382           bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
 383
 384           if (rtl_dump_file)
 385             fprintf (rtl_dump_file,
 386                      "  Possible start point of next round: %d (key: %d)\n",
 387                      bb->index, key);
 388           continue;
 389         }
 390
 391       trace = traces + *n_traces;
 392       trace->first = bb;
 393       trace->round = round;
 394       trace->length = 0;
 395       (*n_traces)++;
 396
 397       do
 398         {
 399           int prob, freq;
 400
 401           /* The probability and frequency of the best edge.  */
 402           int best_prob = INT_MIN / 2;
 403           int best_freq = INT_MIN / 2;
 404
 405           best_edge = NULL;
 406           mark_bb_visited (bb, *n_traces);
 407           trace->length++;
 408
 409           if (rtl_dump_file)
 410             fprintf (rtl_dump_file, "Basic block %d was visited in trace %d\n",
 411                      bb->index, *n_traces - 1);
 412
 413           /* Select the successor that will be placed after BB.  */
 414           for (e = bb->succ; e; e = e->succ_next)
 415             {
 416               if (e->flags & EDGE_FAKE)
 417                 abort ();
 418
 419               if (e->dest == EXIT_BLOCK_PTR)
 420                 continue;
 421
 422               if (RBI (e->dest)->visited
 423                   && RBI (e->dest)->visited != *n_traces)
 424                 continue;
 425
 426               prob = e->probability;
 427               freq = EDGE_FREQUENCY (e);
 428
 429               /* Edge that cannot be fallthru or improbable or infrequent
 430                  successor (ie. it is unsuitable successor).  */
 431               if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
 432                   || prob < branch_th || freq < exec_th || e->count < count_th)
 433                 continue;
 434
 435               if (better_edge_p (bb, e, prob, freq, best_prob, best_freq))
 436                 {
 437                   best_edge = e;
 438                   best_prob = prob;
 439                   best_freq = freq;
 440                 }
 441             }
 442
 443           /* If the best destination has multiple predecessors, and can be
 444              duplicated cheaper than a jump, don't allow it to be added
 445              to a trace.  We'll duplicate it when connecting traces.  */
 446           if (best_edge && best_edge->dest->pred->pred_next
 447               && copy_bb_p (best_edge->dest, 0))
 448             best_edge = NULL;
 449
 450           /* Add all non-selected successors to the heaps.  */
 451           for (e = bb->succ; e; e = e->succ_next)
 452             {
 453               if (e == best_edge
 454                   || e->dest == EXIT_BLOCK_PTR
 455                   || RBI (e->dest)->visited)
 456                 continue;
 457
 458               key = bb_to_key (e->dest);
 459
 460               if (bbd[e->dest->index].heap)
 461                 {
 462                   /* E->DEST is already in some heap.  */
 463                   if (key != bbd[e->dest->index].node->key)
 464                     {
 465                       if (rtl_dump_file)
 466                         {
 467                           fprintf (rtl_dump_file,
 468                                    "Changing key for bb %d from %ld to %ld.\n",
 469                                    e->dest->index,
 470                                    (long) bbd[e->dest->index].node->key,
 471                                    key);
 472                         }
 473                       fibheap_replace_key (bbd[e->dest->index].heap,
 474                                            bbd[e->dest->index].node, key);
 475                     }
 476                 }
 477               else
 478                 {
 479                   fibheap_t which_heap = *heap;
 480
 481                   prob = e->probability;
 482                   freq = EDGE_FREQUENCY (e);
 483
 484                   if (!(e->flags & EDGE_CAN_FALLTHRU)
 485                       || (e->flags & EDGE_COMPLEX)
 486                       || prob < branch_th || freq < exec_th
 487                       || e->count < count_th)
 488                     {
 489                       if (round < N_ROUNDS - 1)
 490                         which_heap = new_heap;
 491                     }
 492
 493                   bbd[e->dest->index].heap = which_heap;
 494                   bbd[e->dest->index].node = fibheap_insert (which_heap,
 495                                                                 key, e->dest);
 496
 497                   if (rtl_dump_file)
 498                     {
 499                       fprintf (rtl_dump_file,
 500                                "  Possible start of %s round: %d (key: %ld)\n",
 501                                (which_heap == new_heap) ? "next" : "this",
 502                                e->dest->index, (long) key);
 503                     }
 504
 505                 }
 506             }
 507
 508           if (best_edge) /* Suitable successor was found.  */
 509             {
 510               if (RBI (best_edge->dest)->visited == *n_traces)
 511                 {
 512                   /* We do nothing with one basic block loops.  */
 513                   if (best_edge->dest != bb)
 514                     {
 515                       if (EDGE_FREQUENCY (best_edge)
 516                           > 4 * best_edge->dest->frequency / 5)
 517                         {
 518                           /* The loop has at least 4 iterations.  If the loop
 519                              header is not the first block of the function
 520                              we can rotate the loop.  */
 521
 522                           if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
 523                             {
 524                               if (rtl_dump_file)
 525                                 {
 526                                   fprintf (rtl_dump_file,
 527                                            "Rotating loop %d - %d\n",
 528                                            best_edge->dest->index, bb->index);
 529                                 }
 530                               RBI (bb)->next = best_edge->dest;
 531                               bb = rotate_loop (best_edge, trace, *n_traces);
 532                             }
 533                         }
 534                       else
 535                         {
 536                           /* The loop has less than 4 iterations.  */
 537
 538                           /* Check whether there is another edge from BB.  */
 539                           edge another_edge;
 540                           for (another_edge = bb->succ;
 541                                another_edge;
 542                                another_edge = another_edge->succ_next)
 543                             if (another_edge != best_edge)
 544                               break;
 545
 546                           if (!another_edge && copy_bb_p (best_edge->dest,
 547                                                           !optimize_size))
 548                             {
 549                               bb = copy_bb (best_edge->dest, best_edge, bb,
 550                                             *n_traces);
 551                             }
 552                         }
 553                     }
 554
 555                   /* Terminate the trace.  */
 556                   break;
 557                 }
 558               else
 559                 {
 560                   /* Check for a situation
 561
 562                     A
 563                    /|
 564                   B |
 565                    \|
 566                     C
 567
 568                   where
 569                   EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
 570                     >= EDGE_FREQUENCY (AC).
 571                   (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
 572                   Best ordering is then A B C.
 573
 574                   This situation is created for example by:
 575
 576                   if (A) B;
 577                   C;
 578
 579                   */
 580
 581                   for (e = bb->succ; e; e = e->succ_next)
 582                     if (e != best_edge
 583                         && (e->flags & EDGE_CAN_FALLTHRU)
 584                         && !(e->flags & EDGE_COMPLEX)
 585                         && !RBI (e->dest)->visited
 586                         && !e->dest->pred->pred_next
 587                         && e->dest->succ
 588                         && (e->dest->succ->flags & EDGE_CAN_FALLTHRU)
 589                         && !(e->dest->succ->flags & EDGE_COMPLEX)
 590                         && !e->dest->succ->succ_next
 591                         && e->dest->succ->dest == best_edge->dest
 592                         && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
 593                       {
 594                         best_edge = e;
 595                         if (rtl_dump_file)
 596                           fprintf (rtl_dump_file, "Selecting BB %d\n",
 597                                    best_edge->dest->index);
 598                         break;
 599                       }
 600
 601                   RBI (bb)->next = best_edge->dest;
 602                   bb = best_edge->dest;
 603                 }
 604             }
 605         }
 606       while (best_edge);
 607       trace->last = bb;
 608       bbd[trace->first->index].start_of_trace = *n_traces - 1;
 609       bbd[trace->last->index].end_of_trace = *n_traces - 1;
 610
 611       /* The trace is terminated so we have to recount the keys in heap
 612          (some block can have a lower key because now one of its predecessors
 613          is an end of the trace).  */
 614       for (e = bb->succ; e; e = e->succ_next)
 615         {
 616           if (e->dest == EXIT_BLOCK_PTR
 617               || RBI (e->dest)->visited)
 618             continue;
 619
 620           if (bbd[e->dest->index].heap)
 621             {
 622               key = bb_to_key (e->dest);
 623               if (key != bbd[e->dest->index].node->key)
 624                 {
 625                   if (rtl_dump_file)
 626                     {
 627                       fprintf (rtl_dump_file,
 628                                "Changing key for bb %d from %ld to %ld.\n",
 629                                e->dest->index,
 630                                (long) bbd[e->dest->index].node->key, key);
 631                     }
 632                   fibheap_replace_key (bbd[e->dest->index].heap,
 633                                        bbd[e->dest->index].node,
 634                                        key);
 635                 }
 636             }
 637         }
 638     }
 639
 640   fibheap_delete (*heap);
 641
 642   /* "Return" the new heap.  */
 643   *heap = new_heap;
 644 }
 645
 646 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
 647    it to trace after BB, mark OLD_BB visited and update pass' data structures
 648    (TRACE is a number of trace which OLD_BB is duplicated to).  */
 649
 650 static basic_block
 651 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
 652 {
 653   basic_block new_bb;
 654
 655   new_bb = cfg_layout_duplicate_bb (old_bb, e);
 656   if (e->dest != new_bb)
 657     abort ();
 658   if (RBI (e->dest)->visited)
 659     abort ();
 660   if (rtl_dump_file)
 661     fprintf (rtl_dump_file,
 662              "Duplicated bb %d (created bb %d)\n",
 663              old_bb->index, new_bb->index);
 664   RBI (new_bb)->visited = trace;
 665   RBI (new_bb)->next = RBI (bb)->next;
 666   RBI (bb)->next = new_bb;
 667
 668   if (new_bb->index >= array_size || last_basic_block > array_size)
 669     {
 670       int i;
 671       int new_size;
 672
 673       new_size = MAX (last_basic_block, new_bb->index + 1);
 674       new_size = GET_ARRAY_SIZE (new_size);
 675       bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
 676       for (i = array_size; i < new_size; i++)
 677         {
 678           bbd[i].start_of_trace = -1;
 679           bbd[i].end_of_trace = -1;
 680           bbd[i].heap = NULL;
 681           bbd[i].node = NULL;
 682         }
 683       array_size = new_size;
 684
 685       if (rtl_dump_file)
 686         {
 687           fprintf (rtl_dump_file,
 688                    "Growing the dynamic array to %d elements.\n",
 689                    array_size);
 690         }
 691     }
 692
 693   return new_bb;
 694 }
 695
 696 /* Compute and return the key (for the heap) of the basic block BB.  */
 697
 698 static fibheapkey_t
 699 bb_to_key (basic_block bb)
 700 {
 701   edge e;
 702
 703   int priority = 0;
 704
 705   /* Do not start in probably never executed blocks.  */
 706   if (probably_never_executed_bb_p (bb))
 707     return BB_FREQ_MAX;
 708
 709   /* Prefer blocks whose predecessor is an end of some trace
 710      or whose predecessor edge is EDGE_DFS_BACK.  */
 711   for (e = bb->pred; e; e = e->pred_next)
 712     {
 713       if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
 714           || (e->flags & EDGE_DFS_BACK))
 715         {
 716           int edge_freq = EDGE_FREQUENCY (e);
 717
 718           if (edge_freq > priority)
 719             priority = edge_freq;
 720         }
 721     }
 722
 723   if (priority)
 724     /* The block with priority should have significantly lower key.  */
 725     return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
 726   return -bb->frequency;
 727 }
 728
 729 /* Return true when the edge E from basic block BB is better than the temporary
 730    best edge (details are in function).  The probability of edge E is PROB. The
 731    frequency of the successor is FREQ.  The current best probability is
 732    BEST_PROB, the best frequency is BEST_FREQ.
 733    The edge is considered to be equivalent when PROB does not differ much from
 734    BEST_PROB; similarly for frequency.  */
 735
 736 static bool
 737 better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
 738                int best_freq)
 739 {
 740   bool is_better_edge;
 741
 742   /* The BEST_* values do not have to be best, but can be a bit smaller than
 743      maximum values.  */
 744   int diff_prob = best_prob / 10;
 745   int diff_freq = best_freq / 10;
 746
 747   if (prob > best_prob + diff_prob)
 748     /* The edge has higher probability than the temporary best edge.  */
 749     is_better_edge = true;
 750   else if (prob < best_prob - diff_prob)
 751     /* The edge has lower probability than the temporary best edge.  */
 752     is_better_edge = false;
 753   else if (freq < best_freq - diff_freq)
 754     /* The edge and the temporary best edge  have almost equivalent
 755        probabilities.  The higher frequency of a successor now means
 756        that there is another edge going into that successor.
 757        This successor has lower frequency so it is better.  */
 758     is_better_edge = true;
 759   else if (freq > best_freq + diff_freq)
 760     /* This successor has higher frequency so it is worse.  */
 761     is_better_edge = false;
 762   else if (e->dest->prev_bb == bb)
 763     /* The edges have equivalent probabilities and the successors
 764        have equivalent frequencies.  Select the previous successor.  */
 765     is_better_edge = true;
 766   else
 767     is_better_edge = false;
 768
 769   return is_better_edge;
 770 }
 771
 772 /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
 773
 774 static void
 775 connect_traces (int n_traces, struct trace *traces)
 776 {
 777   int i;
 778   bool *connected;
 779   int last_trace;
 780   int freq_threshold;
 781   gcov_type count_threshold;
 782
 783   freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
 784   if (max_entry_count < INT_MAX / 1000)
 785     count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
 786   else
 787     count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
 788
 789   connected = xcalloc (n_traces, sizeof (bool));
 790   last_trace = -1;
 791   for (i = 0; i < n_traces; i++)
 792     {
 793       int t = i;
 794       int t2;
 795       edge e, best;
 796       int best_len;
 797
 798       if (connected[t])
 799         continue;
 800
 801       connected[t] = true;
 802
 803       /* Find the predecessor traces.  */
 804       for (t2 = t; t2 > 0;)
 805         {
 806           best = NULL;
 807           best_len = 0;
 808           for (e = traces[t2].first->pred; e; e = e->pred_next)
 809             {
 810               int si = e->src->index;
 811
 812               if (e->src != ENTRY_BLOCK_PTR
 813                   && (e->flags & EDGE_CAN_FALLTHRU)
 814                   && !(e->flags & EDGE_COMPLEX)
 815                   && bbd[si].end_of_trace >= 0
 816                   && !connected[bbd[si].end_of_trace]
 817                   && (!best
 818                       || e->probability > best->probability
 819                       || (e->probability == best->probability
 820                           && traces[bbd[si].end_of_trace].length > best_len)))
 821                 {
 822                   best = e;
 823                   best_len = traces[bbd[si].end_of_trace].length;
 824                 }
 825             }
 826           if (best)
 827             {
 828               RBI (best->src)->next = best->dest;
 829               t2 = bbd[best->src->index].end_of_trace;
 830               connected[t2] = true;
 831               if (rtl_dump_file)
 832                 {
 833                   fprintf (rtl_dump_file, "Connection: %d %d\n",
 834                            best->src->index, best->dest->index);
 835                 }
 836             }
 837           else
 838             break;
 839         }
 840
 841       if (last_trace >= 0)
 842         RBI (traces[last_trace].last)->next = traces[t2].first;
 843       last_trace = t;
 844
 845       /* Find the successor traces.  */
 846       while (1)
 847         {
 848           /* Find the continuation of the chain.  */
 849           best = NULL;
 850           best_len = 0;
 851           for (e = traces[t].last->succ; e; e = e->succ_next)
 852             {
 853               int di = e->dest->index;
 854
 855               if (e->dest != EXIT_BLOCK_PTR
 856                   && (e->flags & EDGE_CAN_FALLTHRU)
 857                   && !(e->flags & EDGE_COMPLEX)
 858                   && bbd[di].start_of_trace >= 0
 859                   && !connected[bbd[di].start_of_trace]
 860                   && (!best
 861                       || e->probability > best->probability
 862                       || (e->probability == best->probability
 863                           && traces[bbd[di].start_of_trace].length > best_len)))
 864                 {
 865                   best = e;
 866                   best_len = traces[bbd[di].start_of_trace].length;
 867                 }
 868             }
 869
 870           if (best)
 871             {
 872               if (rtl_dump_file)
 873                 {
 874                   fprintf (rtl_dump_file, "Connection: %d %d\n",
 875                            best->src->index, best->dest->index);
 876                 }
 877               t = bbd[best->dest->index].start_of_trace;
 878               RBI (traces[last_trace].last)->next = traces[t].first;
 879               connected[t] = true;
 880               last_trace = t;
 881             }
 882           else
 883             {
 884               /* Try to connect the traces by duplication of 1 block.  */
 885               edge e2;
 886               basic_block next_bb = NULL;
 887               bool try_copy = false;
 888
 889               for (e = traces[t].last->succ; e; e = e->succ_next)
 890                 if (e->dest != EXIT_BLOCK_PTR
 891                     && (e->flags & EDGE_CAN_FALLTHRU)
 892                     && !(e->flags & EDGE_COMPLEX)
 893                     && (!best || e->probability > best->probability))
 894                   {
 895                     edge best2 = NULL;
 896                     int best2_len = 0;
 897
 898                     /* If the destination is a start of a trace which is only
 899                        one block long, then no need to search the successor
 900                        blocks of the trace.  Accept it.  */
 901                     if (bbd[e->dest->index].start_of_trace >= 0
 902                         && traces[bbd[e->dest->index].start_of_trace].length
 903                            == 1)
 904                       {
 905                         best = e;
 906                         try_copy = true;
 907                         continue;
 908                       }
 909
 910                     for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
 911                       {
 912                         int di = e2->dest->index;
 913
 914                         if (e2->dest == EXIT_BLOCK_PTR
 915                             || ((e2->flags & EDGE_CAN_FALLTHRU)
 916                                 && !(e2->flags & EDGE_COMPLEX)
 917                                 && bbd[di].start_of_trace >= 0
 918                                 && !connected[bbd[di].start_of_trace]
 919                                 && (EDGE_FREQUENCY (e2) >= freq_threshold)
 920                                 && (e2->count >= count_threshold)
 921                                 && (!best2
 922                                     || e2->probability > best2->probability
 923                                     || (e2->probability == best2->probability
 924                                         && traces[bbd[di].start_of_trace].length
 925                                            > best2_len))))
 926                           {
 927                             best = e;
 928                             best2 = e2;
 929                             if (e2->dest != EXIT_BLOCK_PTR)
 930                               best2_len = traces[bbd[di].start_of_trace].length;
 931                             else
 932                               best2_len = INT_MAX;
 933                             next_bb = e2->dest;
 934                             try_copy = true;
 935                           }
 936                       }
 937                   }
 938
 939               /* Copy tiny blocks always; copy larger blocks only when the
 940                  edge is traversed frequently enough.  */
 941               if (try_copy
 942                   && copy_bb_p (best->dest,
 943                                 !optimize_size
 944                                 && EDGE_FREQUENCY (best) >= freq_threshold
 945                                 && best->count >= count_threshold))
 946                 {
 947                   basic_block new_bb;
 948
 949                   if (rtl_dump_file)
 950                     {
 951                       fprintf (rtl_dump_file, "Connection: %d %d ",
 952                                traces[t].last->index, best->dest->index);
 953                       if (!next_bb)
 954                         fputc ('\n', rtl_dump_file);
 955                       else if (next_bb == EXIT_BLOCK_PTR)
 956                         fprintf (rtl_dump_file, "exit\n");
 957                       else
 958                         fprintf (rtl_dump_file, "%d\n", next_bb->index);
 959                     }
 960
 961                   new_bb = copy_bb (best->dest, best, traces[t].last, t);
 962                   traces[t].last = new_bb;
 963                   if (next_bb && next_bb != EXIT_BLOCK_PTR)
 964                     {
 965                       t = bbd[next_bb->index].start_of_trace;
 966                       RBI (traces[last_trace].last)->next = traces[t].first;
 967                       connected[t] = true;
 968                       last_trace = t;
 969                     }
 970                   else
 971                     break;      /* Stop finding the successor traces.  */
 972                 }
 973               else
 974                 break;  /* Stop finding the successor traces.  */
 975             }
 976         }
 977     }
 978
 979   if (rtl_dump_file)
 980     {
 981       basic_block bb;
 982
 983       fprintf (rtl_dump_file, "Final order:\n");
 984       for (bb = traces[0].first; bb; bb = RBI (bb)->next)
 985         fprintf (rtl_dump_file, "%d ", bb->index);
 986       fprintf (rtl_dump_file, "\n");
 987       fflush (rtl_dump_file);
 988     }
 989
 990   FREE (connected);
 991 }
 992
 993 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
 994    when code size is allowed to grow by duplication.  */
 995
 996 static bool
 997 copy_bb_p (basic_block bb, int code_may_grow)
 998 {
 999   int size = 0;
1000   int max_size = uncond_jump_length;
1001   rtx insn;
1002
1003   if (!bb->frequency)
1004     return false;
1005   if (!bb->pred || !bb->pred->pred_next)
1006     return false;
1007   if (!cfg_layout_can_duplicate_bb_p (bb))
1008     return false;
1009
1010   if (code_may_grow && maybe_hot_bb_p (bb))
1011     max_size *= 8;
1012
1013   for (insn = bb->head; insn != NEXT_INSN (bb->end);
1014        insn = NEXT_INSN (insn))
1015     {
1016       if (INSN_P (insn))
1017         size += get_attr_length (insn);
1018     }
1019
1020   if (size <= max_size)
1021     return true;
1022
1023   if (rtl_dump_file)
1024     {
1025       fprintf (rtl_dump_file,
1026                "Block %d can't be copied because its size = %d.\n",
1027                bb->index, size);
1028     }
1029
1030   return false;
1031 }
1032
1033 /* Return the length of unconditional jump instruction.  */
1034
1035 static int
1036 get_uncond_jump_length (void)
1037 {
1038   rtx label, jump;
1039   int length;
1040
1041   label = emit_label_before (gen_label_rtx (), get_insns ());
1042   jump = emit_jump_insn (gen_jump (label));
1043
1044   length = get_attr_length (jump);
1045
1046   delete_insn (jump);
1047   delete_insn (label);
1048   return length;
1049 }
1050
1051 /* Reorder basic blocks.  The main entry point to this file.  */
1052
1053 void
1054 reorder_basic_blocks (void)
1055 {
1056   int n_traces;
1057   int i;
1058   struct trace *traces;
1059
1060   if (n_basic_blocks <= 1)
1061     return;
1062
1063   if ((* targetm.cannot_modify_jumps_p) ())
1064     return;
1065
1066   cfg_layout_initialize (NULL);
1067
1068   set_edge_can_fallthru_flag ();
1069   mark_dfs_back_edges ();
1070
1071   /* We are estimating the lenght of uncond jump insn only once since the code
1072      for getting the insn lenght always returns the minimal length now.  */
1073   if (uncond_jump_length == 0)
1074     uncond_jump_length = get_uncond_jump_length ();
1075
1076   /* We need to know some information for each basic block.  */
1077   array_size = GET_ARRAY_SIZE (last_basic_block);
1078   bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
1079   for (i = 0; i < array_size; i++)
1080     {
1081       bbd[i].start_of_trace = -1;
1082       bbd[i].end_of_trace = -1;
1083       bbd[i].heap = NULL;
1084       bbd[i].node = NULL;
1085     }
1086
1087   traces = xmalloc (n_basic_blocks * sizeof (struct trace));
1088   n_traces = 0;
1089   find_traces (&n_traces, traces);
1090   connect_traces (n_traces, traces);
1091   FREE (traces);
1092   FREE (bbd);
1093
1094   if (rtl_dump_file)
1095     dump_flow_info (rtl_dump_file);
1096
1097   cfg_layout_finalize ();
1098 }