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