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