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