gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000, 2002, 2003, 2004 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 #include "function.h"
  81 #include "obstack.h"
  82 #include "expr.h"
  83 #include "regs.h"
  84
  85 /* The number of rounds.  In most cases there will only be 4 rounds, but
  86    when partitioning hot and cold basic blocks into separate sections of
  87    the .o file there will be an extra round.*/
  88 #define N_ROUNDS 5
  89
  90 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.  */
  91 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
  92
  93 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0.  */
  94 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
  95
  96 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
  97    block the edge destination is not duplicated while connecting traces.  */
  98 #define DUPLICATION_THRESHOLD 100
  99
 100 /* Length of unconditional jump instruction.  */
 101 static int uncond_jump_length;
 102
 103 /* Structure to hold needed information for each basic block.  */
 104 typedef struct bbro_basic_block_data_def
 105 {
 106   /* Which trace is the bb start of (-1 means it is not a start of a trace).  */
 107   int start_of_trace;
 108
 109   /* Which trace is the bb end of (-1 means it is not an end of a trace).  */
 110   int end_of_trace;
 111
 112   /* Which heap is BB in (if any)?  */
 113   fibheap_t heap;
 114
 115   /* Which heap node is BB in (if any)?  */
 116   fibnode_t node;
 117 } bbro_basic_block_data;
 118
 119 /* The current size of the following dynamic array.  */
 120 static int array_size;
 121
 122 /* The array which holds needed information for basic blocks.  */
 123 static bbro_basic_block_data *bbd;
 124
 125 /* To avoid frequent reallocation the size of arrays is greater than needed,
 126    the number of elements is (not less than) 1.25 * size_wanted.  */
 127 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
 128
 129 /* Free the memory and set the pointer to NULL.  */
 130 #define FREE(P) \
 131   do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
 132
 133 /* Structure for holding information about a trace.  */
 134 struct trace
 135 {
 136   /* First and last basic block of the trace.  */
 137   basic_block first, last;
 138
 139   /* The round of the STC creation which this trace was found in.  */
 140   int round;
 141
 142   /* The length (i.e. the number of basic blocks) of the trace.  */
 143   int length;
 144 };
 145
 146 /* Maximum frequency and count of one of the entry blocks.  */
 147 int max_entry_frequency;
 148 gcov_type max_entry_count;
 149
 150 /* Local function prototypes.  */
 151 static void find_traces (int *, struct trace *);
 152 static basic_block rotate_loop (edge, struct trace *, int);
 153 static void mark_bb_visited (basic_block, int);
 154 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
 155                                  int, fibheap_t *, int);
 156 static basic_block copy_bb (basic_block, edge, basic_block, int);
 157 static fibheapkey_t bb_to_key (basic_block);
 158 static bool better_edge_p (basic_block, edge, int, int, int, int, edge);
 159 static void connect_traces (int, struct trace *);
 160 static bool copy_bb_p (basic_block, int);
 161 static int get_uncond_jump_length (void);
 162 static bool push_to_next_round_p (basic_block, int, int, int, gcov_type);
 163 static void add_unlikely_executed_notes (void);
 164 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
 165                                                                   int *,
 166                                                                   int *);
 167 static void mark_bb_for_unlikely_executed_section  (basic_block);
 168 static void add_labels_and_missing_jumps (edge *, int);
 169 static void add_reg_crossing_jump_notes (void);
 170 static void fix_up_fall_thru_edges (void);
 171 static void fix_edges_for_rarely_executed_code (edge *, int);
 172 static void fix_crossing_conditional_branches (void);
 173 static void fix_crossing_unconditional_branches (void);
 174 \f
 175 /* Check to see if bb should be pushed into the next round of trace
 176    collections or not.  Reasons for pushing the block forward are 1).
 177    If the block is cold, we are doing partitioning, and there will be
 178    another round (cold partition blocks are not supposed to be
 179    collected into traces until the very last round); or 2). There will
 180    be another round, and the basic block is not "hot enough" for the
 181    current round of trace collection.  */
 182
 183 static bool
 184 push_to_next_round_p (basic_block bb, int round, int number_of_rounds,
 185                       int exec_th, gcov_type count_th)
 186 {
 187   bool there_exists_another_round;
 188   bool cold_block;
 189   bool block_not_hot_enough;
 190
 191   there_exists_another_round = round < number_of_rounds - 1;
 192
 193   cold_block = (flag_reorder_blocks_and_partition
 194                 && bb->partition == COLD_PARTITION);
 195
 196   block_not_hot_enough = (bb->frequency < exec_th
 197                           || bb->count < count_th
 198                           || probably_never_executed_bb_p (bb));
 199
 200   if (there_exists_another_round
 201       && (cold_block || block_not_hot_enough))
 202     return true;
 203   else
 204     return false;
 205 }
 206
 207 /* Find the traces for Software Trace Cache.  Chain each trace through
 208    RBI()->next.  Store the number of traces to N_TRACES and description of
 209    traces to TRACES.  */
 210
 211 static void
 212 find_traces (int *n_traces, struct trace *traces)
 213 {
 214   int i;
 215   int number_of_rounds;
 216   edge e;
 217   fibheap_t heap;
 218
 219   /* Add one extra round of trace collection when partitioning hot/cold
 220      basic blocks into separate sections.  The last round is for all the
 221      cold blocks (and ONLY the cold blocks).  */
 222
 223   number_of_rounds = N_ROUNDS - 1;
 224   if (flag_reorder_blocks_and_partition)
 225     number_of_rounds = N_ROUNDS;
 226
 227   /* Insert entry points of function into heap.  */
 228   heap = fibheap_new ();
 229   max_entry_frequency = 0;
 230   max_entry_count = 0;
 231   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 232     {
 233       bbd[e->dest->index].heap = heap;
 234       bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
 235                                                     e->dest);
 236       if (e->dest->frequency > max_entry_frequency)
 237         max_entry_frequency = e->dest->frequency;
 238       if (e->dest->count > max_entry_count)
 239         max_entry_count = e->dest->count;
 240     }
 241
 242   /* Find the traces.  */
 243   for (i = 0; i < number_of_rounds; i++)
 244     {
 245       gcov_type count_threshold;
 246
 247       if (dump_file)
 248         fprintf (dump_file, "STC - round %d\n", i + 1);
 249
 250       if (max_entry_count < INT_MAX / 1000)
 251         count_threshold = max_entry_count * exec_threshold[i] / 1000;
 252       else
 253         count_threshold = max_entry_count / 1000 * exec_threshold[i];
 254
 255       find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
 256                            max_entry_frequency * exec_threshold[i] / 1000,
 257                            count_threshold, traces, n_traces, i, &heap,
 258                            number_of_rounds);
 259     }
 260   fibheap_delete (heap);
 261
 262   if (dump_file)
 263     {
 264       for (i = 0; i < *n_traces; i++)
 265         {
 266           basic_block bb;
 267           fprintf (dump_file, "Trace %d (round %d):  ", i + 1,
 268                    traces[i].round + 1);
 269           for (bb = traces[i].first; bb != traces[i].last; bb = bb->rbi->next)
 270             fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
 271           fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
 272         }
 273       fflush (dump_file);
 274     }
 275 }
 276
 277 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
 278    (with sequential number TRACE_N).  */
 279
 280 static basic_block
 281 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
 282 {
 283   basic_block bb;
 284
 285   /* Information about the best end (end after rotation) of the loop.  */
 286   basic_block best_bb = NULL;
 287   edge best_edge = NULL;
 288   int best_freq = -1;
 289   gcov_type best_count = -1;
 290   /* The best edge is preferred when its destination is not visited yet
 291      or is a start block of some trace.  */
 292   bool is_preferred = false;
 293
 294   /* Find the most frequent edge that goes out from current trace.  */
 295   bb = back_edge->dest;
 296   do
 297     {
 298       edge e;
 299       for (e = bb->succ; e; e = e->succ_next)
 300         if (e->dest != EXIT_BLOCK_PTR
 301             && e->dest->rbi->visited != trace_n
 302             && (e->flags & EDGE_CAN_FALLTHRU)
 303             && !(e->flags & EDGE_COMPLEX))
 304         {
 305           if (is_preferred)
 306             {
 307               /* The best edge is preferred.  */
 308               if (!e->dest->rbi->visited
 309                   || bbd[e->dest->index].start_of_trace >= 0)
 310                 {
 311                   /* The current edge E is also preferred.  */
 312                   int freq = EDGE_FREQUENCY (e);
 313                   if (freq > best_freq || e->count > best_count)
 314                     {
 315                       best_freq = freq;
 316                       best_count = e->count;
 317                       best_edge = e;
 318                       best_bb = bb;
 319                     }
 320                 }
 321             }
 322           else
 323             {
 324               if (!e->dest->rbi->visited
 325                   || bbd[e->dest->index].start_of_trace >= 0)
 326                 {
 327                   /* The current edge E is preferred.  */
 328                   is_preferred = true;
 329                   best_freq = EDGE_FREQUENCY (e);
 330                   best_count = e->count;
 331                   best_edge = e;
 332                   best_bb = bb;
 333                 }
 334               else
 335                 {
 336                   int freq = EDGE_FREQUENCY (e);
 337                   if (!best_edge || freq > best_freq || e->count > best_count)
 338                     {
 339                       best_freq = freq;
 340                       best_count = e->count;
 341                       best_edge = e;
 342                       best_bb = bb;
 343                     }
 344                 }
 345             }
 346         }
 347       bb = bb->rbi->next;
 348     }
 349   while (bb != back_edge->dest);
 350
 351   if (best_bb)
 352     {
 353       /* Rotate the loop so that the BEST_EDGE goes out from the last block of
 354          the trace.  */
 355       if (back_edge->dest == trace->first)
 356         {
 357           trace->first = best_bb->rbi->next;
 358         }
 359       else
 360         {
 361           basic_block prev_bb;
 362
 363           for (prev_bb = trace->first;
 364                prev_bb->rbi->next != back_edge->dest;
 365                prev_bb = prev_bb->rbi->next)
 366             ;
 367           prev_bb->rbi->next = best_bb->rbi->next;
 368
 369           /* Try to get rid of uncond jump to cond jump.  */
 370           if (prev_bb->succ && !prev_bb->succ->succ_next)
 371             {
 372               basic_block header = prev_bb->succ->dest;
 373
 374               /* Duplicate HEADER if it is a small block containing cond jump
 375                  in the end.  */
 376               if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0))
 377                 {
 378                   copy_bb (header, prev_bb->succ, prev_bb, trace_n);
 379                 }
 380             }
 381         }
 382     }
 383   else
 384     {
 385       /* We have not found suitable loop tail so do no rotation.  */
 386       best_bb = back_edge->src;
 387     }
 388   best_bb->rbi->next = NULL;
 389   return best_bb;
 390 }
 391
 392 /* This function marks BB that it was visited in trace number TRACE.  */
 393
 394 static void
 395 mark_bb_visited (basic_block bb, int trace)
 396 {
 397   bb->rbi->visited = trace;
 398   if (bbd[bb->index].heap)
 399     {
 400       fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
 401       bbd[bb->index].heap = NULL;
 402       bbd[bb->index].node = NULL;
 403     }
 404 }
 405
 406 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
 407    not include basic blocks their probability is lower than BRANCH_TH or their
 408    frequency is lower than EXEC_TH into traces (or count is lower than
 409    COUNT_TH).  It stores the new traces into TRACES and modifies the number of
 410    traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
 411    expects that starting basic blocks are in *HEAP and at the end it deletes
 412    *HEAP and stores starting points for the next round into new *HEAP.  */
 413
 414 static void
 415 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
 416                      struct trace *traces, int *n_traces, int round,
 417                      fibheap_t *heap, int number_of_rounds)
 418 {
 419   /* The following variable refers to the last round in which non-"cold"
 420      blocks may be collected into a trace.  */
 421
 422   int last_round = N_ROUNDS - 1;
 423
 424   /* Heap for discarded basic blocks which are possible starting points for
 425      the next round.  */
 426   fibheap_t new_heap = fibheap_new ();
 427
 428   while (!fibheap_empty (*heap))
 429     {
 430       basic_block bb;
 431       struct trace *trace;
 432       edge best_edge, e;
 433       fibheapkey_t key;
 434
 435       bb = fibheap_extract_min (*heap);
 436       bbd[bb->index].heap = NULL;
 437       bbd[bb->index].node = NULL;
 438
 439       if (dump_file)
 440         fprintf (dump_file, "Getting bb %d\n", bb->index);
 441
 442       /* If the BB's frequency is too low send BB to the next round.  When
 443          partitioning hot/cold blocks into separate sections, make sure all
 444          the cold blocks (and ONLY the cold blocks) go into the (extra) final
 445          round.  */
 446
 447       if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
 448                                 count_th))
 449         {
 450           int key = bb_to_key (bb);
 451           bbd[bb->index].heap = new_heap;
 452           bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
 453
 454           if (dump_file)
 455             fprintf (dump_file,
 456                      "  Possible start point of next round: %d (key: %d)\n",
 457                      bb->index, key);
 458           continue;
 459         }
 460
 461       trace = traces + *n_traces;
 462       trace->first = bb;
 463       trace->round = round;
 464       trace->length = 0;
 465       (*n_traces)++;
 466
 467       do
 468         {
 469           int prob, freq;
 470
 471           /* The probability and frequency of the best edge.  */
 472           int best_prob = INT_MIN / 2;
 473           int best_freq = INT_MIN / 2;
 474
 475           best_edge = NULL;
 476           mark_bb_visited (bb, *n_traces);
 477           trace->length++;
 478
 479           if (dump_file)
 480             fprintf (dump_file, "Basic block %d was visited in trace %d\n",
 481                      bb->index, *n_traces - 1);
 482
 483           /* Select the successor that will be placed after BB.  */
 484           for (e = bb->succ; e; e = e->succ_next)
 485             {
 486 #ifdef ENABLE_CHECKING
 487               if (e->flags & EDGE_FAKE)
 488                 abort ();
 489 #endif
 490
 491               if (e->dest == EXIT_BLOCK_PTR)
 492                 continue;
 493
 494               if (e->dest->rbi->visited
 495                   && e->dest->rbi->visited != *n_traces)
 496                 continue;
 497
 498               if (e->dest->partition == COLD_PARTITION
 499                   && round < last_round)
 500                 continue;
 501
 502               prob = e->probability;
 503               freq = EDGE_FREQUENCY (e);
 504
 505               /* Edge that cannot be fallthru or improbable or infrequent
 506                  successor (ie. it is unsuitable successor).  */
 507               if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
 508                   || prob < branch_th || freq < exec_th || e->count < count_th)
 509                 continue;
 510
 511               /* If partitioning hot/cold basic blocks, don't consider edges
 512                  that cross section boundaries.  */
 513
 514               if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
 515                                  best_edge))
 516                 {
 517                   best_edge = e;
 518                   best_prob = prob;
 519                   best_freq = freq;
 520                 }
 521             }
 522
 523           /* If the best destination has multiple predecessors, and can be
 524              duplicated cheaper than a jump, don't allow it to be added
 525              to a trace.  We'll duplicate it when connecting traces.  */
 526           if (best_edge && best_edge->dest->pred->pred_next
 527               && copy_bb_p (best_edge->dest, 0))
 528             best_edge = NULL;
 529
 530           /* Add all non-selected successors to the heaps.  */
 531           for (e = bb->succ; e; e = e->succ_next)
 532             {
 533               if (e == best_edge
 534                   || e->dest == EXIT_BLOCK_PTR
 535                   || e->dest->rbi->visited)
 536                 continue;
 537
 538               key = bb_to_key (e->dest);
 539
 540               if (bbd[e->dest->index].heap)
 541                 {
 542                   /* E->DEST is already in some heap.  */
 543                   if (key != bbd[e->dest->index].node->key)
 544                     {
 545                       if (dump_file)
 546                         {
 547                           fprintf (dump_file,
 548                                    "Changing key for bb %d from %ld to %ld.\n",
 549                                    e->dest->index,
 550                                    (long) bbd[e->dest->index].node->key,
 551                                    key);
 552                         }
 553                       fibheap_replace_key (bbd[e->dest->index].heap,
 554                                            bbd[e->dest->index].node, key);
 555                     }
 556                 }
 557               else
 558                 {
 559                   fibheap_t which_heap = *heap;
 560
 561                   prob = e->probability;
 562                   freq = EDGE_FREQUENCY (e);
 563
 564                   if (!(e->flags & EDGE_CAN_FALLTHRU)
 565                       || (e->flags & EDGE_COMPLEX)
 566                       || prob < branch_th || freq < exec_th
 567                       || e->count < count_th)
 568                     {
 569                       /* When partitioning hot/cold basic blocks, make sure
 570                          the cold blocks (and only the cold blocks) all get
 571                          pushed to the last round of trace collection.  */
 572
 573                       if (push_to_next_round_p (e->dest, round,
 574                                                 number_of_rounds,
 575                                                 exec_th, count_th))
 576                         which_heap = new_heap;
 577                     }
 578
 579                   bbd[e->dest->index].heap = which_heap;
 580                   bbd[e->dest->index].node = fibheap_insert (which_heap,
 581                                                                 key, e->dest);
 582
 583                   if (dump_file)
 584                     {
 585                       fprintf (dump_file,
 586                                "  Possible start of %s round: %d (key: %ld)\n",
 587                                (which_heap == new_heap) ? "next" : "this",
 588                                e->dest->index, (long) key);
 589                     }
 590
 591                 }
 592             }
 593
 594           if (best_edge) /* Suitable successor was found.  */
 595             {
 596               if (best_edge->dest->rbi->visited == *n_traces)
 597                 {
 598                   /* We do nothing with one basic block loops.  */
 599                   if (best_edge->dest != bb)
 600                     {
 601                       if (EDGE_FREQUENCY (best_edge)
 602                           > 4 * best_edge->dest->frequency / 5)
 603                         {
 604                           /* The loop has at least 4 iterations.  If the loop
 605                              header is not the first block of the function
 606                              we can rotate the loop.  */
 607
 608                           if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
 609                             {
 610                               if (dump_file)
 611                                 {
 612                                   fprintf (dump_file,
 613                                            "Rotating loop %d - %d\n",
 614                                            best_edge->dest->index, bb->index);
 615                                 }
 616                               bb->rbi->next = best_edge->dest;
 617                               bb = rotate_loop (best_edge, trace, *n_traces);
 618                             }
 619                         }
 620                       else
 621                         {
 622                           /* The loop has less than 4 iterations.  */
 623
 624                           /* Check whether there is another edge from BB.  */
 625                           edge another_edge;
 626                           for (another_edge = bb->succ;
 627                                another_edge;
 628                                another_edge = another_edge->succ_next)
 629                             if (another_edge != best_edge)
 630                               break;
 631
 632                           if (!another_edge && copy_bb_p (best_edge->dest,
 633                                                           !optimize_size))
 634                             {
 635                               bb = copy_bb (best_edge->dest, best_edge, bb,
 636                                             *n_traces);
 637                             }
 638                         }
 639                     }
 640
 641                   /* Terminate the trace.  */
 642                   break;
 643                 }
 644               else
 645                 {
 646                   /* Check for a situation
 647
 648                     A
 649                    /|
 650                   B |
 651                    \|
 652                     C
 653
 654                   where
 655                   EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
 656                     >= EDGE_FREQUENCY (AC).
 657                   (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
 658                   Best ordering is then A B C.
 659
 660                   This situation is created for example by:
 661
 662                   if (A) B;
 663                   C;
 664
 665                   */
 666
 667                   for (e = bb->succ; e; e = e->succ_next)
 668                     if (e != best_edge
 669                         && (e->flags & EDGE_CAN_FALLTHRU)
 670                         && !(e->flags & EDGE_COMPLEX)
 671                         && !e->dest->rbi->visited
 672                         && !e->dest->pred->pred_next
 673                         && !e->crossing_edge
 674                         && e->dest->succ
 675                         && (e->dest->succ->flags & EDGE_CAN_FALLTHRU)
 676                         && !(e->dest->succ->flags & EDGE_COMPLEX)
 677                         && !e->dest->succ->succ_next
 678                         && e->dest->succ->dest == best_edge->dest
 679                         && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
 680                       {
 681                         best_edge = e;
 682                         if (dump_file)
 683                           fprintf (dump_file, "Selecting BB %d\n",
 684                                    best_edge->dest->index);
 685                         break;
 686                       }
 687
 688                   bb->rbi->next = best_edge->dest;
 689                   bb = best_edge->dest;
 690                 }
 691             }
 692         }
 693       while (best_edge);
 694       trace->last = bb;
 695       bbd[trace->first->index].start_of_trace = *n_traces - 1;
 696       bbd[trace->last->index].end_of_trace = *n_traces - 1;
 697
 698       /* The trace is terminated so we have to recount the keys in heap
 699          (some block can have a lower key because now one of its predecessors
 700          is an end of the trace).  */
 701       for (e = bb->succ; e; e = e->succ_next)
 702         {
 703           if (e->dest == EXIT_BLOCK_PTR
 704               || e->dest->rbi->visited)
 705             continue;
 706
 707           if (bbd[e->dest->index].heap)
 708             {
 709               key = bb_to_key (e->dest);
 710               if (key != bbd[e->dest->index].node->key)
 711                 {
 712                   if (dump_file)
 713                     {
 714                       fprintf (dump_file,
 715                                "Changing key for bb %d from %ld to %ld.\n",
 716                                e->dest->index,
 717                                (long) bbd[e->dest->index].node->key, key);
 718                     }
 719                   fibheap_replace_key (bbd[e->dest->index].heap,
 720                                        bbd[e->dest->index].node,
 721                                        key);
 722                 }
 723             }
 724         }
 725     }
 726
 727   fibheap_delete (*heap);
 728
 729   /* "Return" the new heap.  */
 730   *heap = new_heap;
 731 }
 732
 733 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
 734    it to trace after BB, mark OLD_BB visited and update pass' data structures
 735    (TRACE is a number of trace which OLD_BB is duplicated to).  */
 736
 737 static basic_block
 738 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
 739 {
 740   basic_block new_bb;
 741
 742   new_bb = cfg_layout_duplicate_bb (old_bb, e);
 743   if (e->dest != new_bb)
 744     abort ();
 745   if (e->dest->rbi->visited)
 746     abort ();
 747   if (dump_file)
 748     fprintf (dump_file,
 749              "Duplicated bb %d (created bb %d)\n",
 750              old_bb->index, new_bb->index);
 751   new_bb->rbi->visited = trace;
 752   new_bb->rbi->next = bb->rbi->next;
 753   bb->rbi->next = new_bb;
 754
 755   if (new_bb->index >= array_size || last_basic_block > array_size)
 756     {
 757       int i;
 758       int new_size;
 759
 760       new_size = MAX (last_basic_block, new_bb->index + 1);
 761       new_size = GET_ARRAY_SIZE (new_size);
 762       bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
 763       for (i = array_size; i < new_size; i++)
 764         {
 765           bbd[i].start_of_trace = -1;
 766           bbd[i].end_of_trace = -1;
 767           bbd[i].heap = NULL;
 768           bbd[i].node = NULL;
 769         }
 770       array_size = new_size;
 771
 772       if (dump_file)
 773         {
 774           fprintf (dump_file,
 775                    "Growing the dynamic array to %d elements.\n",
 776                    array_size);
 777         }
 778     }
 779
 780   return new_bb;
 781 }
 782
 783 /* Compute and return the key (for the heap) of the basic block BB.  */
 784
 785 static fibheapkey_t
 786 bb_to_key (basic_block bb)
 787 {
 788   edge e;
 789
 790   int priority = 0;
 791
 792   /* Do not start in probably never executed blocks.  */
 793
 794   if (bb->partition == COLD_PARTITION || probably_never_executed_bb_p (bb))
 795     return BB_FREQ_MAX;
 796
 797   /* Prefer blocks whose predecessor is an end of some trace
 798      or whose predecessor edge is EDGE_DFS_BACK.  */
 799   for (e = bb->pred; e; e = e->pred_next)
 800     {
 801       if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
 802           || (e->flags & EDGE_DFS_BACK))
 803         {
 804           int edge_freq = EDGE_FREQUENCY (e);
 805
 806           if (edge_freq > priority)
 807             priority = edge_freq;
 808         }
 809     }
 810
 811   if (priority)
 812     /* The block with priority should have significantly lower key.  */
 813     return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
 814   return -bb->frequency;
 815 }
 816
 817 /* Return true when the edge E from basic block BB is better than the temporary
 818    best edge (details are in function).  The probability of edge E is PROB. The
 819    frequency of the successor is FREQ.  The current best probability is
 820    BEST_PROB, the best frequency is BEST_FREQ.
 821    The edge is considered to be equivalent when PROB does not differ much from
 822    BEST_PROB; similarly for frequency.  */
 823
 824 static bool
 825 better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
 826                int best_freq, edge cur_best_edge)
 827 {
 828   bool is_better_edge;
 829
 830   /* The BEST_* values do not have to be best, but can be a bit smaller than
 831      maximum values.  */
 832   int diff_prob = best_prob / 10;
 833   int diff_freq = best_freq / 10;
 834
 835   if (prob > best_prob + diff_prob)
 836     /* The edge has higher probability than the temporary best edge.  */
 837     is_better_edge = true;
 838   else if (prob < best_prob - diff_prob)
 839     /* The edge has lower probability than the temporary best edge.  */
 840     is_better_edge = false;
 841   else if (freq < best_freq - diff_freq)
 842     /* The edge and the temporary best edge  have almost equivalent
 843        probabilities.  The higher frequency of a successor now means
 844        that there is another edge going into that successor.
 845        This successor has lower frequency so it is better.  */
 846     is_better_edge = true;
 847   else if (freq > best_freq + diff_freq)
 848     /* This successor has higher frequency so it is worse.  */
 849     is_better_edge = false;
 850   else if (e->dest->prev_bb == bb)
 851     /* The edges have equivalent probabilities and the successors
 852        have equivalent frequencies.  Select the previous successor.  */
 853     is_better_edge = true;
 854   else
 855     is_better_edge = false;
 856
 857   /* If we are doing hot/cold partitioning, make sure that we always favor
 858      non-crossing edges over crossing edges.  */
 859
 860   if (!is_better_edge
 861       && flag_reorder_blocks_and_partition
 862       && cur_best_edge
 863       && cur_best_edge->crossing_edge
 864       && !e->crossing_edge)
 865     is_better_edge = true;
 866
 867   return is_better_edge;
 868 }
 869
 870 /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
 871
 872 static void
 873 connect_traces (int n_traces, struct trace *traces)
 874 {
 875   int i;
 876   int unconnected_hot_trace_count = 0;
 877   bool cold_connected = true;
 878   bool *connected;
 879   bool *cold_traces;
 880   int last_trace;
 881   int freq_threshold;
 882   gcov_type count_threshold;
 883
 884   freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
 885   if (max_entry_count < INT_MAX / 1000)
 886     count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
 887   else
 888     count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
 889
 890   connected = xcalloc (n_traces, sizeof (bool));
 891   last_trace = -1;
 892
 893   /* If we are partitioning hot/cold basic blocks, mark the cold
 894      traces as already connnected, to remove them from consideration
 895      for connection to the hot traces.  After the hot traces have all
 896      been connected (determined by "unconnected_hot_trace_count"), we
 897      will go back and connect the cold traces.  */
 898
 899   cold_traces = xcalloc (n_traces, sizeof (bool));
 900
 901   if (flag_reorder_blocks_and_partition)
 902     for (i = 0; i < n_traces; i++)
 903       {
 904         if (traces[i].first->partition == COLD_PARTITION)
 905           {
 906             connected[i] = true;
 907             cold_traces[i] = true;
 908             cold_connected = false;
 909           }
 910         else
 911           unconnected_hot_trace_count++;
 912       }
 913
 914   for (i = 0; i < n_traces || !cold_connected ; i++)
 915     {
 916       int t = i;
 917       int t2;
 918       edge e, best;
 919       int best_len;
 920
 921       /* If we are partitioning hot/cold basic blocks, check to see
 922          if all the hot traces have been connected.  If so, go back
 923          and mark the cold traces as unconnected so we can connect
 924          them up too.  Re-set "i" to the first (unconnected) cold
 925          trace. Use flag "cold_connected" to make sure we don't do
 926          this step more than once.  */
 927
 928       if (flag_reorder_blocks_and_partition
 929           && (i >= n_traces || unconnected_hot_trace_count <= 0)
 930           && !cold_connected)
 931         {
 932           int j;
 933           int first_cold_trace = -1;
 934
 935           for (j = 0; j < n_traces; j++)
 936             if (cold_traces[j])
 937               {
 938                 connected[j] = false;
 939                 if (first_cold_trace == -1)
 940                   first_cold_trace = j;
 941               }
 942           i = t = first_cold_trace;
 943           cold_connected = true;
 944         }
 945
 946       if (connected[t])
 947         continue;
 948
 949       connected[t] = true;
 950       if (unconnected_hot_trace_count > 0)
 951         unconnected_hot_trace_count--;
 952
 953       /* Find the predecessor traces.  */
 954       for (t2 = t; t2 > 0;)
 955         {
 956           best = NULL;
 957           best_len = 0;
 958           for (e = traces[t2].first->pred; e; e = e->pred_next)
 959             {
 960               int si = e->src->index;
 961
 962               if (e->src != ENTRY_BLOCK_PTR
 963                   && (e->flags & EDGE_CAN_FALLTHRU)
 964                   && !(e->flags & EDGE_COMPLEX)
 965                   && bbd[si].end_of_trace >= 0
 966                   && !connected[bbd[si].end_of_trace]
 967                   && (!best
 968                       || e->probability > best->probability
 969                       || (e->probability == best->probability
 970                           && traces[bbd[si].end_of_trace].length > best_len)))
 971                 {
 972                   best = e;
 973                   best_len = traces[bbd[si].end_of_trace].length;
 974                 }
 975             }
 976           if (best)
 977             {
 978               best->src->rbi->next = best->dest;
 979               t2 = bbd[best->src->index].end_of_trace;
 980               connected[t2] = true;
 981
 982               if (unconnected_hot_trace_count > 0)
 983                 unconnected_hot_trace_count--;
 984
 985               if (dump_file)
 986                 {
 987                   fprintf (dump_file, "Connection: %d %d\n",
 988                            best->src->index, best->dest->index);
 989                 }
 990             }
 991           else
 992             break;
 993         }
 994
 995       if (last_trace >= 0)
 996         traces[last_trace].last->rbi->next = traces[t2].first;
 997       last_trace = t;
 998
 999       /* Find the successor traces.  */
1000       while (1)
1001         {
1002           /* Find the continuation of the chain.  */
1003           best = NULL;
1004           best_len = 0;
1005           for (e = traces[t].last->succ; e; e = e->succ_next)
1006             {
1007               int di = e->dest->index;
1008
1009               if (e->dest != EXIT_BLOCK_PTR
1010                   && (e->flags & EDGE_CAN_FALLTHRU)
1011                   && !(e->flags & EDGE_COMPLEX)
1012                   && bbd[di].start_of_trace >= 0
1013                   && !connected[bbd[di].start_of_trace]
1014                   && (!best
1015                       || e->probability > best->probability
1016                       || (e->probability == best->probability
1017                           && traces[bbd[di].start_of_trace].length > best_len)))
1018                 {
1019                   best = e;
1020                   best_len = traces[bbd[di].start_of_trace].length;
1021                 }
1022             }
1023
1024           if (best)
1025             {
1026               if (dump_file)
1027                 {
1028                   fprintf (dump_file, "Connection: %d %d\n",
1029                            best->src->index, best->dest->index);
1030                 }
1031               t = bbd[best->dest->index].start_of_trace;
1032               traces[last_trace].last->rbi->next = traces[t].first;
1033               connected[t] = true;
1034               if (unconnected_hot_trace_count > 0)
1035                 unconnected_hot_trace_count--;
1036               last_trace = t;
1037             }
1038           else
1039             {
1040               /* Try to connect the traces by duplication of 1 block.  */
1041               edge e2;
1042               basic_block next_bb = NULL;
1043               bool try_copy = false;
1044
1045               for (e = traces[t].last->succ; e; e = e->succ_next)
1046                 if (e->dest != EXIT_BLOCK_PTR
1047                     && (e->flags & EDGE_CAN_FALLTHRU)
1048                     && !(e->flags & EDGE_COMPLEX)
1049                     && (!best || e->probability > best->probability))
1050                   {
1051                     edge best2 = NULL;
1052                     int best2_len = 0;
1053
1054                     /* If the destination is a start of a trace which is only
1055                        one block long, then no need to search the successor
1056                        blocks of the trace.  Accept it.  */
1057                     if (bbd[e->dest->index].start_of_trace >= 0
1058                         && traces[bbd[e->dest->index].start_of_trace].length
1059                            == 1)
1060                       {
1061                         best = e;
1062                         try_copy = true;
1063                         continue;
1064                       }
1065
1066                     for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
1067                       {
1068                         int di = e2->dest->index;
1069
1070                         if (e2->dest == EXIT_BLOCK_PTR
1071                             || ((e2->flags & EDGE_CAN_FALLTHRU)
1072                                 && !(e2->flags & EDGE_COMPLEX)
1073                                 && bbd[di].start_of_trace >= 0
1074                                 && !connected[bbd[di].start_of_trace]
1075                                 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1076                                 && (e2->count >= count_threshold)
1077                                 && (!best2
1078                                     || e2->probability > best2->probability
1079                                     || (e2->probability == best2->probability
1080                                         && traces[bbd[di].start_of_trace].length
1081                                            > best2_len))))
1082                           {
1083                             best = e;
1084                             best2 = e2;
1085                             if (e2->dest != EXIT_BLOCK_PTR)
1086                               best2_len = traces[bbd[di].start_of_trace].length;
1087                             else
1088                               best2_len = INT_MAX;
1089                             next_bb = e2->dest;
1090                             try_copy = true;
1091                           }
1092                       }
1093                   }
1094
1095               if (flag_reorder_blocks_and_partition)
1096                 try_copy = false;
1097
1098               /* Copy tiny blocks always; copy larger blocks only when the
1099                  edge is traversed frequently enough.  */
1100               if (try_copy
1101                   && copy_bb_p (best->dest,
1102                                 !optimize_size
1103                                 && EDGE_FREQUENCY (best) >= freq_threshold
1104                                 && best->count >= count_threshold))
1105                 {
1106                   basic_block new_bb;
1107
1108                   if (dump_file)
1109                     {
1110                       fprintf (dump_file, "Connection: %d %d ",
1111                                traces[t].last->index, best->dest->index);
1112                       if (!next_bb)
1113                         fputc ('\n', dump_file);
1114                       else if (next_bb == EXIT_BLOCK_PTR)
1115                         fprintf (dump_file, "exit\n");
1116                       else
1117                         fprintf (dump_file, "%d\n", next_bb->index);
1118                     }
1119
1120                   new_bb = copy_bb (best->dest, best, traces[t].last, t);
1121                   traces[t].last = new_bb;
1122                   if (next_bb && next_bb != EXIT_BLOCK_PTR)
1123                     {
1124                       t = bbd[next_bb->index].start_of_trace;
1125                       traces[last_trace].last->rbi->next = traces[t].first;
1126                       connected[t] = true;
1127                       if (unconnected_hot_trace_count > 0)
1128                         unconnected_hot_trace_count--;
1129                       last_trace = t;
1130                     }
1131                   else
1132                     break;      /* Stop finding the successor traces.  */
1133                 }
1134               else
1135                 break;  /* Stop finding the successor traces.  */
1136             }
1137         }
1138     }
1139
1140   if (dump_file)
1141     {
1142       basic_block bb;
1143
1144       fprintf (dump_file, "Final order:\n");
1145       for (bb = traces[0].first; bb; bb = bb->rbi->next)
1146         fprintf (dump_file, "%d ", bb->index);
1147       fprintf (dump_file, "\n");
1148       fflush (dump_file);
1149     }
1150
1151   FREE (connected);
1152 }
1153
1154 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1155    when code size is allowed to grow by duplication.  */
1156
1157 static bool
1158 copy_bb_p (basic_block bb, int code_may_grow)
1159 {
1160   int size = 0;
1161   int max_size = uncond_jump_length;
1162   rtx insn;
1163   int n_succ;
1164   edge e;
1165
1166   if (!bb->frequency)
1167     return false;
1168   if (!bb->pred || !bb->pred->pred_next)
1169     return false;
1170   if (!cfg_layout_can_duplicate_bb_p (bb))
1171     return false;
1172
1173   /* Avoid duplicating blocks which have many successors (PR/13430).  */
1174   n_succ = 0;
1175   for (e = bb->succ; e; e = e->succ_next)
1176     {
1177       n_succ++;
1178       if (n_succ > 8)
1179         return false;
1180     }
1181
1182   if (code_may_grow && maybe_hot_bb_p (bb))
1183     max_size *= 8;
1184
1185   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1186        insn = NEXT_INSN (insn))
1187     {
1188       if (INSN_P (insn))
1189         size += get_attr_length (insn);
1190     }
1191
1192   if (size <= max_size)
1193     return true;
1194
1195   if (dump_file)
1196     {
1197       fprintf (dump_file,
1198                "Block %d can't be copied because its size = %d.\n",
1199                bb->index, size);
1200     }
1201
1202   return false;
1203 }
1204
1205 /* Return the length of unconditional jump instruction.  */
1206
1207 static int
1208 get_uncond_jump_length (void)
1209 {
1210   rtx label, jump;
1211   int length;
1212
1213   label = emit_label_before (gen_label_rtx (), get_insns ());
1214   jump = emit_jump_insn (gen_jump (label));
1215
1216   length = get_attr_length (jump);
1217
1218   delete_insn (jump);
1219   delete_insn (label);
1220   return length;
1221 }
1222
1223 static void
1224 add_unlikely_executed_notes (void)
1225 {
1226   basic_block bb;
1227
1228   FOR_EACH_BB (bb)
1229     if (bb->partition == COLD_PARTITION)
1230       mark_bb_for_unlikely_executed_section (bb);
1231 }
1232
1233 /* Find the basic blocks that are rarely executed and need to be moved to
1234    a separate section of the .o file (to cut down on paging and improve
1235    cache locality).  */
1236
1237 static void
1238 find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
1239                                                       int *n_crossing_edges,
1240                                                       int *max_idx)
1241 {
1242   basic_block bb;
1243   edge e;
1244   int i;
1245
1246   /* Mark which partition (hot/cold) each basic block belongs in.  */
1247
1248   FOR_EACH_BB (bb)
1249     {
1250       if (probably_never_executed_bb_p (bb))
1251         bb->partition = COLD_PARTITION;
1252       else
1253         bb->partition = HOT_PARTITION;
1254     }
1255
1256   /* Mark every edge that crosses between sections.  */
1257
1258   i = 0;
1259   FOR_EACH_BB (bb)
1260     for (e = bb->succ; e; e = e->succ_next)
1261       {
1262         if (e->src != ENTRY_BLOCK_PTR
1263             && e->dest != EXIT_BLOCK_PTR
1264             && e->src->partition != e->dest->partition)
1265           {
1266             e->crossing_edge = true;
1267             if (i == *max_idx)
1268               {
1269                 *max_idx *= 2;
1270                 crossing_edges = xrealloc (crossing_edges,
1271                                            (*max_idx) * sizeof (edge));
1272               }
1273             crossing_edges[i++] = e;
1274           }
1275         else
1276           e->crossing_edge = false;
1277       }
1278
1279   *n_crossing_edges = i;
1280 }
1281
1282 /* Add NOTE_INSN_UNLIKELY_EXECUTED_CODE to top of basic block.   This note
1283    is later used to mark the basic block to be put in the
1284    unlikely-to-be-executed section of the .o file.  */
1285
1286 static void
1287 mark_bb_for_unlikely_executed_section (basic_block bb)
1288 {
1289   rtx cur_insn;
1290   rtx insert_insn = NULL;
1291   rtx new_note;
1292
1293   /* Find first non-note instruction and insert new NOTE before it (as
1294      long as new NOTE is not first instruction in basic block).  */
1295
1296   for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
1297        cur_insn = NEXT_INSN (cur_insn))
1298     if (GET_CODE (cur_insn) != NOTE
1299         && GET_CODE (cur_insn) != CODE_LABEL)
1300       {
1301         insert_insn = cur_insn;
1302         break;
1303       }
1304
1305   /* Insert note and assign basic block number to it.  */
1306
1307   if (insert_insn)
1308     {
1309       new_note = emit_note_before (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1310                                    insert_insn);
1311       NOTE_BASIC_BLOCK (new_note) = bb;
1312     }
1313   else
1314     {
1315       new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1316                                   BB_END (bb));
1317       NOTE_BASIC_BLOCK (new_note) = bb;
1318     }
1319 }
1320
1321 /* If any destination of a crossing edge does not have a label, add label;
1322    Convert any fall-through crossing edges (for blocks that do not contain
1323    a jump) to unconditional jumps.   */
1324
1325 static void
1326 add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
1327 {
1328   int i;
1329   basic_block src;
1330   basic_block dest;
1331   rtx label;
1332   rtx barrier;
1333   rtx new_jump;
1334
1335   for (i=0; i < n_crossing_edges; i++)
1336     {
1337       if (crossing_edges[i])
1338         {
1339           src = crossing_edges[i]->src;
1340           dest = crossing_edges[i]->dest;
1341
1342           /* Make sure dest has a label.  */
1343
1344           if (dest && (dest != EXIT_BLOCK_PTR))
1345             {
1346               label = block_label (dest);
1347
1348               /* Make sure source block ends with a jump.  */
1349
1350               if (src && (src != ENTRY_BLOCK_PTR))
1351                 {
1352                   if (GET_CODE (BB_END (src)) != JUMP_INSN)
1353                     /* bb just falls through.  */
1354                     {
1355                       /* make sure there's only one successor */
1356                       if (src->succ && (src->succ->succ_next == NULL))
1357                         {
1358                           /* Find label in dest block.  */
1359                           label = block_label (dest);
1360
1361                           new_jump = emit_jump_insn_after (gen_jump (label),
1362                                                            BB_END (src));
1363                           barrier = emit_barrier_after (new_jump);
1364                           JUMP_LABEL (new_jump) = label;
1365                           LABEL_NUSES (label) += 1;
1366                           src->rbi->footer = unlink_insn_chain (barrier,
1367                                                                 barrier);
1368                           /* Mark edge as non-fallthru.  */
1369                           crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
1370                         }
1371                       else
1372                         {
1373                           /* Basic block has two successors, but
1374                              doesn't end in a jump; something is wrong
1375                              here!  */
1376                           abort();
1377                         }
1378                     } /* end: 'if (GET_CODE ... '  */
1379                 } /* end: 'if (src && src->index...'  */
1380             } /* end: 'if (dest && dest->index...'  */
1381         } /* end: 'if (crossing_edges[i]...'  */
1382     } /* end for loop  */
1383 }
1384
1385 /* Find any bb's where the fall-through edge is a crossing edge (note that
1386    these bb's must also contain a conditional jump; we've already
1387    dealt with fall-through edges for blocks that didn't have a
1388    conditional jump in the call to add_labels_and_missing_jumps).
1389    Convert the fall-through edge to non-crossing edge by inserting a
1390    new bb to fall-through into.  The new bb will contain an
1391    unconditional jump (crossing edge) to the original fall through
1392    destination.  */
1393
1394 static void
1395 fix_up_fall_thru_edges (void)
1396 {
1397   basic_block cur_bb;
1398   basic_block new_bb;
1399   edge succ1;
1400   edge succ2;
1401   edge fall_thru;
1402   edge cond_jump;
1403   edge e;
1404   bool cond_jump_crosses;
1405   int invert_worked;
1406   rtx old_jump;
1407   rtx fall_thru_label;
1408   rtx barrier;
1409
1410   FOR_EACH_BB (cur_bb)
1411     {
1412       fall_thru = NULL;
1413       succ1 = cur_bb->succ;
1414       if (succ1)
1415         succ2 = succ1->succ_next;
1416       else
1417         succ2 = NULL;
1418
1419       /* Find the fall-through edge.  */
1420
1421       if (succ1
1422           && (succ1->flags & EDGE_FALLTHRU))
1423         {
1424           fall_thru = succ1;
1425           cond_jump = succ2;
1426         }
1427       else if (succ2
1428                && (succ2->flags & EDGE_FALLTHRU))
1429         {
1430           fall_thru = succ2;
1431           cond_jump = succ1;
1432         }
1433
1434       if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1435         {
1436           /* Check to see if the fall-thru edge is a crossing edge.  */
1437
1438           if (fall_thru->crossing_edge)
1439             {
1440               /* The fall_thru edge crosses; now check the cond jump edge, if
1441                  it exists.  */
1442
1443               cond_jump_crosses = true;
1444               invert_worked  = 0;
1445               old_jump = BB_END (cur_bb);
1446
1447               /* Find the jump instruction, if there is one.  */
1448
1449               if (cond_jump)
1450                 {
1451                   if (!cond_jump->crossing_edge)
1452                     cond_jump_crosses = false;
1453
1454                   /* We know the fall-thru edge crosses; if the cond
1455                      jump edge does NOT cross, and its destination is the
1456                      next block in the bb order, invert the jump
1457                      (i.e. fix it so the fall thru does not cross and
1458                      the cond jump does).  */
1459
1460                   if (!cond_jump_crosses
1461                       && cur_bb->rbi->next == cond_jump->dest)
1462                     {
1463                       /* Find label in fall_thru block. We've already added
1464                          any missing labels, so there must be one. */
1465
1466                       fall_thru_label = block_label (fall_thru->dest);
1467
1468                       if (old_jump && fall_thru_label)
1469                         invert_worked = invert_jump (old_jump,
1470                                                      fall_thru_label,0);
1471                       if (invert_worked)
1472                         {
1473                           fall_thru->flags &= ~EDGE_FALLTHRU;
1474                           cond_jump->flags |= EDGE_FALLTHRU;
1475                           update_br_prob_note (cur_bb);
1476                           e = fall_thru;
1477                           fall_thru = cond_jump;
1478                           cond_jump = e;
1479                           cond_jump->crossing_edge = true;
1480                           fall_thru->crossing_edge = false;
1481                         }
1482                     }
1483                 }
1484
1485               if (cond_jump_crosses || !invert_worked)
1486                 {
1487                   /* This is the case where both edges out of the basic
1488                      block are crossing edges. Here we will fix up the
1489                      fall through edge. The jump edge will be taken care
1490                      of later.  */
1491
1492                   new_bb = force_nonfallthru (fall_thru);
1493
1494                   if (new_bb)
1495                     {
1496                       new_bb->rbi->next = cur_bb->rbi->next;
1497                       cur_bb->rbi->next = new_bb;
1498
1499                       /* Make sure new fall-through bb is in same
1500                          partition as bb it's falling through from.  */
1501
1502                       new_bb->partition = cur_bb->partition;
1503                       new_bb->succ->crossing_edge = true;
1504                     }
1505
1506                   /* Add barrier after new jump */
1507
1508                   if (new_bb)
1509                     {
1510                       barrier = emit_barrier_after (BB_END (new_bb));
1511                       new_bb->rbi->footer = unlink_insn_chain (barrier,
1512                                                                barrier);
1513                     }
1514                   else
1515                     {
1516                       barrier = emit_barrier_after (BB_END (cur_bb));
1517                       cur_bb->rbi->footer = unlink_insn_chain (barrier,
1518                                                                barrier);
1519                     }
1520                 }
1521             }
1522         }
1523     }
1524 }
1525
1526 /* This function checks the destination blockof a "crossing jump" to
1527    see if it has any crossing predecessors that begin with a code label
1528    and end with an unconditional jump.  If so, it returns that predecessor
1529    block.  (This is to avoid creating lots of new basic blocks that all
1530    contain unconditional jumps to the same destination).  */
1531
1532 static basic_block
1533 find_jump_block (basic_block jump_dest)
1534 {
1535   basic_block source_bb = NULL;
1536   edge e;
1537   rtx insn;
1538
1539   for (e = jump_dest->pred; e; e = e->pred_next)
1540     if (e->crossing_edge)
1541       {
1542         basic_block src = e->src;
1543
1544         /* Check each predecessor to see if it has a label, and contains
1545            only one executable instruction, which is an unconditional jump.
1546            If so, we can use it.   */
1547
1548         if (GET_CODE (BB_HEAD (src)) == CODE_LABEL)
1549           for (insn = BB_HEAD (src);
1550                !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1551                insn = NEXT_INSN (insn))
1552             {
1553               if (INSN_P (insn)
1554                   && insn == BB_END (src)
1555                   && GET_CODE (insn) == JUMP_INSN
1556                   && !any_condjump_p (insn))
1557                 {
1558                   source_bb = src;
1559                   break;
1560                 }
1561             }
1562
1563         if (source_bb)
1564           break;
1565       }
1566
1567   return source_bb;
1568 }
1569
1570 /* Find all BB's with conditional jumps that are crossing edges;
1571    insert a new bb and make the conditional jump branch to the new
1572    bb instead (make the new bb same color so conditional branch won't
1573    be a 'crossing' edge).  Insert an unconditional jump from the
1574    new bb to the original destination of the conditional jump.  */
1575
1576 static void
1577 fix_crossing_conditional_branches (void)
1578 {
1579   basic_block cur_bb;
1580   basic_block new_bb;
1581   basic_block last_bb;
1582   basic_block dest;
1583   basic_block prev_bb;
1584   edge succ1;
1585   edge succ2;
1586   edge crossing_edge;
1587   edge new_edge;
1588   rtx old_jump;
1589   rtx set_src;
1590   rtx old_label = NULL_RTX;
1591   rtx new_label;
1592   rtx new_jump;
1593   rtx barrier;
1594
1595  last_bb = EXIT_BLOCK_PTR->prev_bb;
1596
1597   FOR_EACH_BB (cur_bb)
1598     {
1599       crossing_edge = NULL;
1600       succ1 = cur_bb->succ;
1601       if (succ1)
1602         succ2 = succ1->succ_next;
1603       else
1604         succ2 = NULL;
1605
1606       /* We already took care of fall-through edges, so only one successor
1607          can be a crossing edge.  */
1608
1609       if (succ1 && succ1->crossing_edge)
1610         crossing_edge = succ1;
1611       else if (succ2 && succ2->crossing_edge)
1612         crossing_edge = succ2;
1613
1614       if (crossing_edge)
1615         {
1616           old_jump = BB_END (cur_bb);
1617
1618           /* Check to make sure the jump instruction is a
1619              conditional jump.  */
1620
1621           set_src = NULL_RTX;
1622
1623           if (any_condjump_p (old_jump))
1624             {
1625               if (GET_CODE (PATTERN (old_jump)) == SET)
1626                 set_src = SET_SRC (PATTERN (old_jump));
1627               else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1628                 {
1629                   set_src = XVECEXP (PATTERN (old_jump), 0,0);
1630                   if (GET_CODE (set_src) == SET)
1631                     set_src = SET_SRC (set_src);
1632                   else
1633                     set_src = NULL_RTX;
1634                 }
1635             }
1636
1637           if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1638             {
1639               if (GET_CODE (XEXP (set_src, 1)) == PC)
1640                 old_label = XEXP (set_src, 2);
1641               else if (GET_CODE (XEXP (set_src, 2)) == PC)
1642                 old_label = XEXP (set_src, 1);
1643
1644               /* Check to see if new bb for jumping to that dest has
1645                  already been created; if so, use it; if not, create
1646                  a new one.  */
1647
1648               new_bb = find_jump_block (crossing_edge->dest);
1649
1650               if (new_bb)
1651                 new_label = block_label (new_bb);
1652               else
1653                 {
1654                   /* Create new basic block to be dest for
1655                      conditional jump.  */
1656
1657                   new_bb = create_basic_block (NULL, NULL, last_bb);
1658                   new_bb->rbi->next = last_bb->rbi->next;
1659                   last_bb->rbi->next = new_bb;
1660                   prev_bb = last_bb;
1661                   last_bb = new_bb;
1662
1663                   /* Update register liveness information.  */
1664
1665                   new_bb->global_live_at_start =
1666                     OBSTACK_ALLOC_REG_SET (&flow_obstack);
1667                   new_bb->global_live_at_end =
1668                     OBSTACK_ALLOC_REG_SET (&flow_obstack);
1669                   COPY_REG_SET (new_bb->global_live_at_end,
1670                                 prev_bb->global_live_at_end);
1671                   COPY_REG_SET (new_bb->global_live_at_start,
1672                                 prev_bb->global_live_at_end);
1673
1674                   /* Put appropriate instructions in new bb.  */
1675
1676                   new_label = gen_label_rtx ();
1677                   emit_label_before (new_label, BB_HEAD (new_bb));
1678                   BB_HEAD (new_bb) = new_label;
1679
1680                   if (GET_CODE (old_label) == LABEL_REF)
1681                     {
1682                       old_label = JUMP_LABEL (old_jump);
1683                       new_jump = emit_jump_insn_after (gen_jump
1684                                                        (old_label),
1685                                                        BB_END (new_bb));
1686                     }
1687 #ifdef HAVE_return
1688                   else if (GET_CODE (old_label) == RETURN)
1689                     new_jump = emit_jump_insn_after (gen_return (),
1690                                                      BB_END (new_bb));
1691 #endif
1692                   else
1693                     abort ();
1694
1695                   barrier = emit_barrier_after (new_jump);
1696                   JUMP_LABEL (new_jump) = old_label;
1697                   new_bb->rbi->footer = unlink_insn_chain (barrier,
1698                                                            barrier);
1699
1700                   /* Make sure new bb is in same partition as source
1701                      of conditional branch.  */
1702
1703                   new_bb->partition = cur_bb->partition;
1704                 }
1705
1706               /* Make old jump branch to new bb.  */
1707
1708               redirect_jump (old_jump, new_label, 0);
1709
1710               /* Remove crossing_edge as predecessor of 'dest'.  */
1711
1712               dest = crossing_edge->dest;
1713
1714               redirect_edge_succ (crossing_edge, new_bb);
1715
1716               /* Make a new edge from new_bb to old dest; new edge
1717                  will be a successor for new_bb and a predecessor
1718                  for 'dest'.  */
1719
1720               if (!new_bb->succ)
1721                 new_edge = make_edge (new_bb, dest, 0);
1722               else
1723                 new_edge = new_bb->succ;
1724
1725               crossing_edge->crossing_edge = false;
1726               new_edge->crossing_edge = true;
1727             }
1728         }
1729     }
1730 }
1731
1732 /* Find any unconditional branches that cross between hot and cold
1733    sections.  Convert them into indirect jumps instead.  */
1734
1735 static void
1736 fix_crossing_unconditional_branches (void)
1737 {
1738   basic_block cur_bb;
1739   rtx last_insn;
1740   rtx label;
1741   rtx label_addr;
1742   rtx indirect_jump_sequence;
1743   rtx jump_insn = NULL_RTX;
1744   rtx new_reg;
1745   rtx cur_insn;
1746   edge succ;
1747
1748   FOR_EACH_BB (cur_bb)
1749     {
1750       last_insn = BB_END (cur_bb);
1751       succ = cur_bb->succ;
1752
1753       /* Check to see if bb ends in a crossing (unconditional) jump.  At
1754          this point, no crossing jumps should be conditional.  */
1755
1756       if (GET_CODE (last_insn) == JUMP_INSN
1757           && succ->crossing_edge)
1758         {
1759           rtx label2, table;
1760
1761           if (any_condjump_p (last_insn))
1762             abort ();
1763
1764           /* Make sure the jump is not already an indirect or table jump.  */
1765
1766           else if (!computed_jump_p (last_insn)
1767                    && !tablejump_p (last_insn, &label2, &table))
1768             {
1769               /* We have found a "crossing" unconditional branch.  Now
1770                  we must convert it to an indirect jump.  First create
1771                  reference of label, as target for jump.  */
1772
1773               label = JUMP_LABEL (last_insn);
1774               label_addr = gen_rtx_LABEL_REF (VOIDmode, label);
1775               LABEL_NUSES (label) += 1;
1776
1777               /* Get a register to use for the indirect jump.  */
1778
1779               new_reg = gen_reg_rtx (Pmode);
1780
1781               /* Generate indirect the jump sequence.  */
1782
1783               start_sequence ();
1784               emit_move_insn (new_reg, label_addr);
1785               emit_indirect_jump (new_reg);
1786               indirect_jump_sequence = get_insns ();
1787               end_sequence ();
1788
1789               /* Make sure every instruction in the new jump sequence has
1790                  its basic block set to be cur_bb.  */
1791
1792               for (cur_insn = indirect_jump_sequence; cur_insn;
1793                    cur_insn = NEXT_INSN (cur_insn))
1794                 {
1795                   BLOCK_FOR_INSN (cur_insn) = cur_bb;
1796                   if (GET_CODE (cur_insn) == JUMP_INSN)
1797                     jump_insn = cur_insn;
1798                 }
1799
1800               /* Insert the new (indirect) jump sequence immediately before
1801                  the unconditional jump, then delete the unconditional jump.  */
1802
1803               emit_insn_before (indirect_jump_sequence, last_insn);
1804               delete_insn (last_insn);
1805
1806               /* Make BB_END for cur_bb be the jump instruction (NOT the
1807                  barrier instruction at the end of the sequence...).  */
1808
1809               BB_END (cur_bb) = jump_insn;
1810             }
1811         }
1812     }
1813 }
1814
1815 /* Add REG_CROSSING_JUMP note to all crossing jump insns.  */
1816
1817 static void
1818 add_reg_crossing_jump_notes (void)
1819 {
1820   basic_block bb;
1821   edge e;
1822
1823   FOR_EACH_BB (bb)
1824     for (e = bb->succ; e; e = e->succ_next)
1825       if (e->crossing_edge
1826           && GET_CODE (BB_END (e->src)) == JUMP_INSN)
1827         REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
1828                                                          NULL_RTX,
1829                                                          REG_NOTES (BB_END
1830                                                                   (e->src)));
1831 }
1832
1833 /* Basic blocks containing NOTE_INSN_UNLIKELY_EXECUTED_CODE will be
1834    put in a separate section of the .o file, to reduce paging and
1835    improve cache performance (hopefully).  This can result in bits of
1836    code from the same function being widely separated in the .o file.
1837    However this is not obvious to the current bb structure.  Therefore
1838    we must take care to ensure that: 1). There are no fall_thru edges
1839    that cross between sections;  2). For those architectures which
1840    have "short" conditional branches, all conditional branches that
1841    attempt to cross between sections are converted to unconditional
1842    branches; and, 3). For those architectures which have "short"
1843    unconditional branches, all unconditional branches that attempt
1844    to cross between sections are converted to indirect jumps.
1845
1846    The code for fixing up fall_thru edges that cross between hot and
1847    cold basic blocks does so by creating new basic blocks containing
1848    unconditional branches to the appropriate label in the "other"
1849    section.  The new basic block is then put in the same (hot or cold)
1850    section as the original conditional branch, and the fall_thru edge
1851    is modified to fall into the new basic block instead.  By adding
1852    this level of indirection we end up with only unconditional branches
1853    crossing between hot and cold sections.
1854
1855    Conditional branches are dealt with by adding a level of indirection.
1856    A new basic block is added in the same (hot/cold) section as the
1857    conditional branch, and the conditional branch is retargeted to the
1858    new basic block.  The new basic block contains an unconditional branch
1859    to the original target of the conditional branch (in the other section).
1860
1861    Unconditional branches are dealt with by converting them into
1862    indirect jumps.  */
1863
1864 static void
1865 fix_edges_for_rarely_executed_code (edge *crossing_edges,
1866                                     int n_crossing_edges)
1867 {
1868   /* Make sure the source of any crossing edge ends in a jump and the
1869      destination of any crossing edge has a label.  */
1870
1871   add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
1872
1873   /* Convert all crossing fall_thru edges to non-crossing fall
1874      thrus to unconditional jumps (that jump to the original fall
1875      thru dest).  */
1876
1877   fix_up_fall_thru_edges ();
1878
1879   /* If the architecture does not have conditional branches that can
1880      span all of memory, convert crossing conditional branches into
1881      crossing unconditional branches.  */
1882
1883   if (!HAS_LONG_COND_BRANCH)
1884     fix_crossing_conditional_branches ();
1885
1886   /* If the architecture does not have unconditional branches that
1887      can span all of memory, convert crossing unconditional branches
1888      into indirect jumps.  Since adding an indirect jump also adds
1889      a new register usage, update the register usage information as
1890      well.  */
1891
1892   if (!HAS_LONG_UNCOND_BRANCH)
1893     {
1894       fix_crossing_unconditional_branches ();
1895       reg_scan (get_insns(), max_reg_num (), 1);
1896     }
1897
1898   add_reg_crossing_jump_notes ();
1899 }
1900
1901 /* Reorder basic blocks.  The main entry point to this file.  */
1902
1903 void
1904 reorder_basic_blocks (void)
1905 {
1906   int n_traces;
1907   int i;
1908   struct trace *traces;
1909
1910   if (n_basic_blocks <= 1)
1911     return;
1912
1913   if (targetm.cannot_modify_jumps_p ())
1914     return;
1915
1916   timevar_push (TV_REORDER_BLOCKS);
1917
1918   cfg_layout_initialize ();
1919
1920   set_edge_can_fallthru_flag ();
1921   mark_dfs_back_edges ();
1922
1923   /* We are estimating the length of uncond jump insn only once since the code
1924      for getting the insn length always returns the minimal length now.  */
1925   if (uncond_jump_length == 0)
1926     uncond_jump_length = get_uncond_jump_length ();
1927
1928   /* We need to know some information for each basic block.  */
1929   array_size = GET_ARRAY_SIZE (last_basic_block);
1930   bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
1931   for (i = 0; i < array_size; i++)
1932     {
1933       bbd[i].start_of_trace = -1;
1934       bbd[i].end_of_trace = -1;
1935       bbd[i].heap = NULL;
1936       bbd[i].node = NULL;
1937     }
1938
1939   traces = xmalloc (n_basic_blocks * sizeof (struct trace));
1940   n_traces = 0;
1941   find_traces (&n_traces, traces);
1942   connect_traces (n_traces, traces);
1943   FREE (traces);
1944   FREE (bbd);
1945
1946   if (dump_file)
1947     dump_flow_info (dump_file);
1948
1949   if (flag_reorder_blocks_and_partition)
1950     add_unlikely_executed_notes ();
1951
1952   cfg_layout_finalize ();
1953
1954   timevar_pop (TV_REORDER_BLOCKS);
1955 }
1956
1957 /* This function is the main 'entrance' for the optimization that
1958    partitions hot and cold basic blocks into separate sections of the
1959    .o file (to improve performance and cache locality).  Ideally it
1960    would be called after all optimizations that rearrange the CFG have
1961    been called.  However part of this optimization may introduce new
1962    register usage, so it must be called before register allocation has
1963    occurred.  This means that this optimization is actually called
1964    well before the optimization that reorders basic blocks (see function
1965    above).
1966
1967    This optimization checks the feedback information to determine
1968    which basic blocks are hot/cold and adds
1969    NOTE_INSN_UNLIKELY_EXECUTED_CODE to non-hot basic blocks.  The
1970    presence or absence of this note is later used for writing out
1971    sections in the .o file.  This optimization must also modify the
1972    CFG to make sure there are no fallthru edges between hot & cold
1973    blocks, as those blocks will not necessarily be contiguous in the
1974    .o (or assembly) file; and in those cases where the architecture
1975    requires it, conditional and unconditional branches that cross
1976    between sections are converted into unconditional or indirect
1977    jumps, depending on what is appropriate.  */
1978
1979 void
1980 partition_hot_cold_basic_blocks (void)
1981 {
1982   basic_block cur_bb;
1983   edge *crossing_edges;
1984   int n_crossing_edges;
1985   int max_edges = 2 * last_basic_block;
1986
1987   if (n_basic_blocks <= 1)
1988     return;
1989
1990   crossing_edges = xcalloc (max_edges, sizeof (edge));
1991
1992   cfg_layout_initialize ();
1993
1994   FOR_EACH_BB (cur_bb)
1995     if (cur_bb->index >= 0
1996         && cur_bb->next_bb->index >= 0)
1997       cur_bb->rbi->next = cur_bb->next_bb;
1998
1999   find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
2000                                                         &n_crossing_edges,
2001                                                         &max_edges);
2002
2003   if (n_crossing_edges > 0)
2004     fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
2005
2006   free (crossing_edges);
2007
2008   cfg_layout_finalize();
2009 }