gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT
  13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  15    License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GCC; see the file COPYING3.  If not see
  19    <http://www.gnu.org/licenses/>.  */
  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 "regs.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 "params.h"
  85 #include "diagnostic-core.h"
  86 #include "toplev.h" /* user_defined_section_attribute */
  87 #include "tree-pass.h"
  88 #include "df.h"
  89
  90 /* The number of rounds.  In most cases there will only be 4 rounds, but
  91    when partitioning hot and cold basic blocks into separate sections of
  92    the .o file there will be an extra round.*/
  93 #define N_ROUNDS 5
  94
  95 /* Stubs in case we don't have a return insn.
  96    We have to check at runtime too, not only compiletime.  */
  97
  98 #ifndef HAVE_return
  99 #define HAVE_return 0
 100 #define gen_return() NULL_RTX
 101 #endif
 102
 103
 104 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.  */
 105 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
 106
 107 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0.  */
 108 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
 109
 110 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
 111    block the edge destination is not duplicated while connecting traces.  */
 112 #define DUPLICATION_THRESHOLD 100
 113
 114 /* Length of unconditional jump instruction.  */
 115 static int uncond_jump_length;
 116
 117 /* Structure to hold needed information for each basic block.  */
 118 typedef struct bbro_basic_block_data_def
 119 {
 120   /* Which trace is the bb start of (-1 means it is not a start of a trace).  */
 121   int start_of_trace;
 122
 123   /* Which trace is the bb end of (-1 means it is not an end of a trace).  */
 124   int end_of_trace;
 125
 126   /* Which trace is the bb in?  */
 127   int in_trace;
 128
 129   /* Which heap is BB in (if any)?  */
 130   fibheap_t heap;
 131
 132   /* Which heap node is BB in (if any)?  */
 133   fibnode_t node;
 134 } bbro_basic_block_data;
 135
 136 /* The current size of the following dynamic array.  */
 137 static int array_size;
 138
 139 /* The array which holds needed information for basic blocks.  */
 140 static bbro_basic_block_data *bbd;
 141
 142 /* To avoid frequent reallocation the size of arrays is greater than needed,
 143    the number of elements is (not less than) 1.25 * size_wanted.  */
 144 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
 145
 146 /* Free the memory and set the pointer to NULL.  */
 147 #define FREE(P) (gcc_assert (P), free (P), P = 0)
 148
 149 /* Structure for holding information about a trace.  */
 150 struct trace
 151 {
 152   /* First and last basic block of the trace.  */
 153   basic_block first, last;
 154
 155   /* The round of the STC creation which this trace was found in.  */
 156   int round;
 157
 158   /* The length (i.e. the number of basic blocks) of the trace.  */
 159   int length;
 160 };
 161
 162 /* Maximum frequency and count of one of the entry blocks.  */
 163 static int max_entry_frequency;
 164 static gcov_type max_entry_count;
 165
 166 /* Local function prototypes.  */
 167 static void find_traces (int *, struct trace *);
 168 static basic_block rotate_loop (edge, struct trace *, int);
 169 static void mark_bb_visited (basic_block, int);
 170 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
 171                                  int, fibheap_t *, int);
 172 static basic_block copy_bb (basic_block, edge, basic_block, int);
 173 static fibheapkey_t bb_to_key (basic_block);
 174 static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge);
 175 static void connect_traces (int, struct trace *);
 176 static bool copy_bb_p (const_basic_block, int);
 177 static int get_uncond_jump_length (void);
 178 static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
 179 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge **,
 180                                                                   int *,
 181                                                                   int *);
 182 static void add_labels_and_missing_jumps (edge *, int);
 183 static void add_reg_crossing_jump_notes (void);
 184 static void fix_up_fall_thru_edges (void);
 185 static void fix_edges_for_rarely_executed_code (edge *, int);
 186 static void fix_crossing_conditional_branches (void);
 187 static void fix_crossing_unconditional_branches (void);
 188 \f
 189 /* Check to see if bb should be pushed into the next round of trace
 190    collections or not.  Reasons for pushing the block forward are 1).
 191    If the block is cold, we are doing partitioning, and there will be
 192    another round (cold partition blocks are not supposed to be
 193    collected into traces until the very last round); or 2). There will
 194    be another round, and the basic block is not "hot enough" for the
 195    current round of trace collection.  */
 196
 197 static bool
 198 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
 199                       int exec_th, gcov_type count_th)
 200 {
 201   bool there_exists_another_round;
 202   bool block_not_hot_enough;
 203
 204   there_exists_another_round = round < number_of_rounds - 1;
 205
 206   block_not_hot_enough = (bb->frequency < exec_th
 207                           || bb->count < count_th
 208                           || probably_never_executed_bb_p (bb));
 209
 210   if (there_exists_another_round
 211       && block_not_hot_enough)
 212     return true;
 213   else
 214     return false;
 215 }
 216
 217 /* Find the traces for Software Trace Cache.  Chain each trace through
 218    RBI()->next.  Store the number of traces to N_TRACES and description of
 219    traces to TRACES.  */
 220
 221 static void
 222 find_traces (int *n_traces, struct trace *traces)
 223 {
 224   int i;
 225   int number_of_rounds;
 226   edge e;
 227   edge_iterator ei;
 228   fibheap_t heap;
 229
 230   /* Add one extra round of trace collection when partitioning hot/cold
 231      basic blocks into separate sections.  The last round is for all the
 232      cold blocks (and ONLY the cold blocks).  */
 233
 234   number_of_rounds = N_ROUNDS - 1;
 235
 236   /* Insert entry points of function into heap.  */
 237   heap = fibheap_new ();
 238   max_entry_frequency = 0;
 239   max_entry_count = 0;
 240   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 241     {
 242       bbd[e->dest->index].heap = heap;
 243       bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
 244                                                     e->dest);
 245       if (e->dest->frequency > max_entry_frequency)
 246         max_entry_frequency = e->dest->frequency;
 247       if (e->dest->count > max_entry_count)
 248         max_entry_count = e->dest->count;
 249     }
 250
 251   /* Find the traces.  */
 252   for (i = 0; i < number_of_rounds; i++)
 253     {
 254       gcov_type count_threshold;
 255
 256       if (dump_file)
 257         fprintf (dump_file, "STC - round %d\n", i + 1);
 258
 259       if (max_entry_count < INT_MAX / 1000)
 260         count_threshold = max_entry_count * exec_threshold[i] / 1000;
 261       else
 262         count_threshold = max_entry_count / 1000 * exec_threshold[i];
 263
 264       find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
 265                            max_entry_frequency * exec_threshold[i] / 1000,
 266                            count_threshold, traces, n_traces, i, &heap,
 267                            number_of_rounds);
 268     }
 269   fibheap_delete (heap);
 270
 271   if (dump_file)
 272     {
 273       for (i = 0; i < *n_traces; i++)
 274         {
 275           basic_block bb;
 276           fprintf (dump_file, "Trace %d (round %d):  ", i + 1,
 277                    traces[i].round + 1);
 278           for (bb = traces[i].first; bb != traces[i].last; bb = (basic_block) bb->aux)
 279             fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
 280           fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
 281         }
 282       fflush (dump_file);
 283     }
 284 }
 285
 286 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
 287    (with sequential number TRACE_N).  */
 288
 289 static basic_block
 290 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
 291 {
 292   basic_block bb;
 293
 294   /* Information about the best end (end after rotation) of the loop.  */
 295   basic_block best_bb = NULL;
 296   edge best_edge = NULL;
 297   int best_freq = -1;
 298   gcov_type best_count = -1;
 299   /* The best edge is preferred when its destination is not visited yet
 300      or is a start block of some trace.  */
 301   bool is_preferred = false;
 302
 303   /* Find the most frequent edge that goes out from current trace.  */
 304   bb = back_edge->dest;
 305   do
 306     {
 307       edge e;
 308       edge_iterator ei;
 309
 310       FOR_EACH_EDGE (e, ei, bb->succs)
 311         if (e->dest != EXIT_BLOCK_PTR
 312             && e->dest->il.rtl->visited != trace_n
 313             && (e->flags & EDGE_CAN_FALLTHRU)
 314             && !(e->flags & EDGE_COMPLEX))
 315         {
 316           if (is_preferred)
 317             {
 318               /* The best edge is preferred.  */
 319               if (!e->dest->il.rtl->visited
 320                   || bbd[e->dest->index].start_of_trace >= 0)
 321                 {
 322                   /* The current edge E is also preferred.  */
 323                   int freq = EDGE_FREQUENCY (e);
 324                   if (freq > best_freq || e->count > best_count)
 325                     {
 326                       best_freq = freq;
 327                       best_count = e->count;
 328                       best_edge = e;
 329                       best_bb = bb;
 330                     }
 331                 }
 332             }
 333           else
 334             {
 335               if (!e->dest->il.rtl->visited
 336                   || bbd[e->dest->index].start_of_trace >= 0)
 337                 {
 338                   /* The current edge E is preferred.  */
 339                   is_preferred = true;
 340                   best_freq = EDGE_FREQUENCY (e);
 341                   best_count = e->count;
 342                   best_edge = e;
 343                   best_bb = bb;
 344                 }
 345               else
 346                 {
 347                   int freq = EDGE_FREQUENCY (e);
 348                   if (!best_edge || freq > best_freq || e->count > best_count)
 349                     {
 350                       best_freq = freq;
 351                       best_count = e->count;
 352                       best_edge = e;
 353                       best_bb = bb;
 354                     }
 355                 }
 356             }
 357         }
 358       bb = (basic_block) bb->aux;
 359     }
 360   while (bb != back_edge->dest);
 361
 362   if (best_bb)
 363     {
 364       /* Rotate the loop so that the BEST_EDGE goes out from the last block of
 365          the trace.  */
 366       if (back_edge->dest == trace->first)
 367         {
 368           trace->first = (basic_block) best_bb->aux;
 369         }
 370       else
 371         {
 372           basic_block prev_bb;
 373
 374           for (prev_bb = trace->first;
 375                prev_bb->aux != back_edge->dest;
 376                prev_bb = (basic_block) prev_bb->aux)
 377             ;
 378           prev_bb->aux = best_bb->aux;
 379
 380           /* Try to get rid of uncond jump to cond jump.  */
 381           if (single_succ_p (prev_bb))
 382             {
 383               basic_block header = single_succ (prev_bb);
 384
 385               /* Duplicate HEADER if it is a small block containing cond jump
 386                  in the end.  */
 387               if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
 388                   && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
 389                                      NULL_RTX))
 390                 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
 391             }
 392         }
 393     }
 394   else
 395     {
 396       /* We have not found suitable loop tail so do no rotation.  */
 397       best_bb = back_edge->src;
 398     }
 399   best_bb->aux = NULL;
 400   return best_bb;
 401 }
 402
 403 /* This function marks BB that it was visited in trace number TRACE.  */
 404
 405 static void
 406 mark_bb_visited (basic_block bb, int trace)
 407 {
 408   bb->il.rtl->visited = trace;
 409   if (bbd[bb->index].heap)
 410     {
 411       fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
 412       bbd[bb->index].heap = NULL;
 413       bbd[bb->index].node = NULL;
 414     }
 415 }
 416
 417 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
 418    not include basic blocks their probability is lower than BRANCH_TH or their
 419    frequency is lower than EXEC_TH into traces (or count is lower than
 420    COUNT_TH).  It stores the new traces into TRACES and modifies the number of
 421    traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
 422    expects that starting basic blocks are in *HEAP and at the end it deletes
 423    *HEAP and stores starting points for the next round into new *HEAP.  */
 424
 425 static void
 426 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
 427                      struct trace *traces, int *n_traces, int round,
 428                      fibheap_t *heap, int number_of_rounds)
 429 {
 430   /* Heap for discarded basic blocks which are possible starting points for
 431      the next round.  */
 432   fibheap_t new_heap = fibheap_new ();
 433
 434   while (!fibheap_empty (*heap))
 435     {
 436       basic_block bb;
 437       struct trace *trace;
 438       edge best_edge, e;
 439       fibheapkey_t key;
 440       edge_iterator ei;
 441
 442       bb = (basic_block) fibheap_extract_min (*heap);
 443       bbd[bb->index].heap = NULL;
 444       bbd[bb->index].node = NULL;
 445
 446       if (dump_file)
 447         fprintf (dump_file, "Getting bb %d\n", bb->index);
 448
 449       /* If the BB's frequency is too low send BB to the next round.  When
 450          partitioning hot/cold blocks into separate sections, make sure all
 451          the cold blocks (and ONLY the cold blocks) go into the (extra) final
 452          round.  */
 453
 454       if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
 455                                 count_th))
 456         {
 457           int key = bb_to_key (bb);
 458           bbd[bb->index].heap = new_heap;
 459           bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
 460
 461           if (dump_file)
 462             fprintf (dump_file,
 463                      "  Possible start point of next round: %d (key: %d)\n",
 464                      bb->index, key);
 465           continue;
 466         }
 467
 468       trace = traces + *n_traces;
 469       trace->first = bb;
 470       trace->round = round;
 471       trace->length = 0;
 472       bbd[bb->index].in_trace = *n_traces;
 473       (*n_traces)++;
 474
 475       do
 476         {
 477           int prob, freq;
 478           bool ends_in_call;
 479
 480           /* The probability and frequency of the best edge.  */
 481           int best_prob = INT_MIN / 2;
 482           int best_freq = INT_MIN / 2;
 483
 484           best_edge = NULL;
 485           mark_bb_visited (bb, *n_traces);
 486           trace->length++;
 487
 488           if (dump_file)
 489             fprintf (dump_file, "Basic block %d was visited in trace %d\n",
 490                      bb->index, *n_traces - 1);
 491
 492           ends_in_call = block_ends_with_call_p (bb);
 493
 494           /* Select the successor that will be placed after BB.  */
 495           FOR_EACH_EDGE (e, ei, bb->succs)
 496             {
 497               gcc_assert (!(e->flags & EDGE_FAKE));
 498
 499               if (e->dest == EXIT_BLOCK_PTR)
 500                 continue;
 501
 502               if (e->dest->il.rtl->visited
 503                   && e->dest->il.rtl->visited != *n_traces)
 504                 continue;
 505
 506               if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
 507                 continue;
 508
 509               prob = e->probability;
 510               freq = e->dest->frequency;
 511
 512               /* The only sensible preference for a call instruction is the
 513                  fallthru edge.  Don't bother selecting anything else.  */
 514               if (ends_in_call)
 515                 {
 516                   if (e->flags & EDGE_CAN_FALLTHRU)
 517                     {
 518                       best_edge = e;
 519                       best_prob = prob;
 520                       best_freq = freq;
 521                     }
 522                   continue;
 523                 }
 524
 525               /* Edge that cannot be fallthru or improbable or infrequent
 526                  successor (i.e. it is unsuitable successor).  */
 527               if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
 528                   || prob < branch_th || EDGE_FREQUENCY (e) < exec_th
 529                   || e->count < count_th)
 530                 continue;
 531
 532               /* If partitioning hot/cold basic blocks, don't consider edges
 533                  that cross section boundaries.  */
 534
 535               if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
 536                                  best_edge))
 537                 {
 538                   best_edge = e;
 539                   best_prob = prob;
 540                   best_freq = freq;
 541                 }
 542             }
 543
 544           /* If the best destination has multiple predecessors, and can be
 545              duplicated cheaper than a jump, don't allow it to be added
 546              to a trace.  We'll duplicate it when connecting traces.  */
 547           if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
 548               && copy_bb_p (best_edge->dest, 0))
 549             best_edge = NULL;
 550
 551           /* Add all non-selected successors to the heaps.  */
 552           FOR_EACH_EDGE (e, ei, bb->succs)
 553             {
 554               if (e == best_edge
 555                   || e->dest == EXIT_BLOCK_PTR
 556                   || e->dest->il.rtl->visited)
 557                 continue;
 558
 559               key = bb_to_key (e->dest);
 560
 561               if (bbd[e->dest->index].heap)
 562                 {
 563                   /* E->DEST is already in some heap.  */
 564                   if (key != bbd[e->dest->index].node->key)
 565                     {
 566                       if (dump_file)
 567                         {
 568                           fprintf (dump_file,
 569                                    "Changing key for bb %d from %ld to %ld.\n",
 570                                    e->dest->index,
 571                                    (long) bbd[e->dest->index].node->key,
 572                                    key);
 573                         }
 574                       fibheap_replace_key (bbd[e->dest->index].heap,
 575                                            bbd[e->dest->index].node, key);
 576                     }
 577                 }
 578               else
 579                 {
 580                   fibheap_t which_heap = *heap;
 581
 582                   prob = e->probability;
 583                   freq = EDGE_FREQUENCY (e);
 584
 585                   if (!(e->flags & EDGE_CAN_FALLTHRU)
 586                       || (e->flags & EDGE_COMPLEX)
 587                       || prob < branch_th || freq < exec_th
 588                       || e->count < count_th)
 589                     {
 590                       /* When partitioning hot/cold basic blocks, make sure
 591                          the cold blocks (and only the cold blocks) all get
 592                          pushed to the last round of trace collection.  */
 593
 594                       if (push_to_next_round_p (e->dest, round,
 595                                                 number_of_rounds,
 596                                                 exec_th, count_th))
 597                         which_heap = new_heap;
 598                     }
 599
 600                   bbd[e->dest->index].heap = which_heap;
 601                   bbd[e->dest->index].node = fibheap_insert (which_heap,
 602                                                                 key, e->dest);
 603
 604                   if (dump_file)
 605                     {
 606                       fprintf (dump_file,
 607                                "  Possible start of %s round: %d (key: %ld)\n",
 608                                (which_heap == new_heap) ? "next" : "this",
 609                                e->dest->index, (long) key);
 610                     }
 611
 612                 }
 613             }
 614
 615           if (best_edge) /* Suitable successor was found.  */
 616             {
 617               if (best_edge->dest->il.rtl->visited == *n_traces)
 618                 {
 619                   /* We do nothing with one basic block loops.  */
 620                   if (best_edge->dest != bb)
 621                     {
 622                       if (EDGE_FREQUENCY (best_edge)
 623                           > 4 * best_edge->dest->frequency / 5)
 624                         {
 625                           /* The loop has at least 4 iterations.  If the loop
 626                              header is not the first block of the function
 627                              we can rotate the loop.  */
 628
 629                           if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
 630                             {
 631                               if (dump_file)
 632                                 {
 633                                   fprintf (dump_file,
 634                                            "Rotating loop %d - %d\n",
 635                                            best_edge->dest->index, bb->index);
 636                                 }
 637                               bb->aux = best_edge->dest;
 638                               bbd[best_edge->dest->index].in_trace =
 639                                                              (*n_traces) - 1;
 640                               bb = rotate_loop (best_edge, trace, *n_traces);
 641                             }
 642                         }
 643                       else
 644                         {
 645                           /* The loop has less than 4 iterations.  */
 646
 647                           if (single_succ_p (bb)
 648                               && copy_bb_p (best_edge->dest,
 649                                             optimize_edge_for_speed_p (best_edge)))
 650                             {
 651                               bb = copy_bb (best_edge->dest, best_edge, bb,
 652                                             *n_traces);
 653                               trace->length++;
 654                             }
 655                         }
 656                     }
 657
 658                   /* Terminate the trace.  */
 659                   break;
 660                 }
 661               else
 662                 {
 663                   /* Check for a situation
 664
 665                     A
 666                    /|
 667                   B |
 668                    \|
 669                     C
 670
 671                   where
 672                   EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
 673                     >= EDGE_FREQUENCY (AC).
 674                   (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
 675                   Best ordering is then A B C.
 676
 677                   This situation is created for example by:
 678
 679                   if (A) B;
 680                   C;
 681
 682                   */
 683
 684                   FOR_EACH_EDGE (e, ei, bb->succs)
 685                     if (e != best_edge
 686                         && (e->flags & EDGE_CAN_FALLTHRU)
 687                         && !(e->flags & EDGE_COMPLEX)
 688                         && !e->dest->il.rtl->visited
 689                         && single_pred_p (e->dest)
 690                         && !(e->flags & EDGE_CROSSING)
 691                         && single_succ_p (e->dest)
 692                         && (single_succ_edge (e->dest)->flags
 693                             & EDGE_CAN_FALLTHRU)
 694                         && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
 695                         && single_succ (e->dest) == best_edge->dest
 696                         && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
 697                       {
 698                         best_edge = e;
 699                         if (dump_file)
 700                           fprintf (dump_file, "Selecting BB %d\n",
 701                                    best_edge->dest->index);
 702                         break;
 703                       }
 704
 705                   bb->aux = best_edge->dest;
 706                   bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
 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_EACH_EDGE (e, ei, bb->succs)
 720         {
 721           if (e->dest == EXIT_BLOCK_PTR
 722               || e->dest->il.rtl->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, bb);
 761   BB_COPY_PARTITION (new_bb, old_bb);
 762
 763   gcc_assert (e->dest == new_bb);
 764   gcc_assert (!e->dest->il.rtl->visited);
 765
 766   if (dump_file)
 767     fprintf (dump_file,
 768              "Duplicated bb %d (created bb %d)\n",
 769              old_bb->index, new_bb->index);
 770   new_bb->il.rtl->visited = trace;
 771   new_bb->aux = bb->aux;
 772   bb->aux = new_bb;
 773
 774   if (new_bb->index >= array_size || last_basic_block > array_size)
 775     {
 776       int i;
 777       int new_size;
 778
 779       new_size = MAX (last_basic_block, new_bb->index + 1);
 780       new_size = GET_ARRAY_SIZE (new_size);
 781       bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
 782       for (i = array_size; i < new_size; i++)
 783         {
 784           bbd[i].start_of_trace = -1;
 785           bbd[i].in_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   bbd[new_bb->index].in_trace = trace;
 801
 802   return new_bb;
 803 }
 804
 805 /* Compute and return the key (for the heap) of the basic block BB.  */
 806
 807 static fibheapkey_t
 808 bb_to_key (basic_block bb)
 809 {
 810   edge e;
 811   edge_iterator ei;
 812   int priority = 0;
 813
 814   /* Do not start in probably never executed blocks.  */
 815
 816   if (BB_PARTITION (bb) == BB_COLD_PARTITION
 817       || probably_never_executed_bb_p (bb))
 818     return BB_FREQ_MAX;
 819
 820   /* Prefer blocks whose predecessor is an end of some trace
 821      or whose predecessor edge is EDGE_DFS_BACK.  */
 822   FOR_EACH_EDGE (e, ei, bb->preds)
 823     {
 824       if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
 825           || (e->flags & EDGE_DFS_BACK))
 826         {
 827           int edge_freq = EDGE_FREQUENCY (e);
 828
 829           if (edge_freq > priority)
 830             priority = edge_freq;
 831         }
 832     }
 833
 834   if (priority)
 835     /* The block with priority should have significantly lower key.  */
 836     return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
 837   return -bb->frequency;
 838 }
 839
 840 /* Return true when the edge E from basic block BB is better than the temporary
 841    best edge (details are in function).  The probability of edge E is PROB. The
 842    frequency of the successor is FREQ.  The current best probability is
 843    BEST_PROB, the best frequency is BEST_FREQ.
 844    The edge is considered to be equivalent when PROB does not differ much from
 845    BEST_PROB; similarly for frequency.  */
 846
 847 static bool
 848 better_edge_p (const_basic_block bb, const_edge e, int prob, int freq, int best_prob,
 849                int best_freq, const_edge cur_best_edge)
 850 {
 851   bool is_better_edge;
 852
 853   /* The BEST_* values do not have to be best, but can be a bit smaller than
 854      maximum values.  */
 855   int diff_prob = best_prob / 10;
 856   int diff_freq = best_freq / 10;
 857
 858   if (prob > best_prob + diff_prob)
 859     /* The edge has higher probability than the temporary best edge.  */
 860     is_better_edge = true;
 861   else if (prob < best_prob - diff_prob)
 862     /* The edge has lower probability than the temporary best edge.  */
 863     is_better_edge = false;
 864   else if (freq < best_freq - diff_freq)
 865     /* The edge and the temporary best edge  have almost equivalent
 866        probabilities.  The higher frequency of a successor now means
 867        that there is another edge going into that successor.
 868        This successor has lower frequency so it is better.  */
 869     is_better_edge = true;
 870   else if (freq > best_freq + diff_freq)
 871     /* This successor has higher frequency so it is worse.  */
 872     is_better_edge = false;
 873   else if (e->dest->prev_bb == bb)
 874     /* The edges have equivalent probabilities and the successors
 875        have equivalent frequencies.  Select the previous successor.  */
 876     is_better_edge = true;
 877   else
 878     is_better_edge = false;
 879
 880   /* If we are doing hot/cold partitioning, make sure that we always favor
 881      non-crossing edges over crossing edges.  */
 882
 883   if (!is_better_edge
 884       && flag_reorder_blocks_and_partition
 885       && cur_best_edge
 886       && (cur_best_edge->flags & EDGE_CROSSING)
 887       && !(e->flags & EDGE_CROSSING))
 888     is_better_edge = true;
 889
 890   return is_better_edge;
 891 }
 892
 893 /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
 894
 895 static void
 896 connect_traces (int n_traces, struct trace *traces)
 897 {
 898   int i;
 899   bool *connected;
 900   bool two_passes;
 901   int last_trace;
 902   int current_pass;
 903   int current_partition;
 904   int freq_threshold;
 905   gcov_type count_threshold;
 906
 907   freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
 908   if (max_entry_count < INT_MAX / 1000)
 909     count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
 910   else
 911     count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
 912
 913   connected = XCNEWVEC (bool, n_traces);
 914   last_trace = -1;
 915   current_pass = 1;
 916   current_partition = BB_PARTITION (traces[0].first);
 917   two_passes = false;
 918
 919   if (flag_reorder_blocks_and_partition)
 920     for (i = 0; i < n_traces && !two_passes; i++)
 921       if (BB_PARTITION (traces[0].first)
 922           != BB_PARTITION (traces[i].first))
 923         two_passes = true;
 924
 925   for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
 926     {
 927       int t = i;
 928       int t2;
 929       edge e, best;
 930       int best_len;
 931
 932       if (i >= n_traces)
 933         {
 934           gcc_assert (two_passes && current_pass == 1);
 935           i = 0;
 936           t = i;
 937           current_pass = 2;
 938           if (current_partition == BB_HOT_PARTITION)
 939             current_partition = BB_COLD_PARTITION;
 940           else
 941             current_partition = BB_HOT_PARTITION;
 942         }
 943
 944       if (connected[t])
 945         continue;
 946
 947       if (two_passes
 948           && BB_PARTITION (traces[t].first) != current_partition)
 949         continue;
 950
 951       connected[t] = true;
 952
 953       /* Find the predecessor traces.  */
 954       for (t2 = t; t2 > 0;)
 955         {
 956           edge_iterator ei;
 957           best = NULL;
 958           best_len = 0;
 959           FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
 960             {
 961               int si = e->src->index;
 962
 963               if (e->src != ENTRY_BLOCK_PTR
 964                   && (e->flags & EDGE_CAN_FALLTHRU)
 965                   && !(e->flags & EDGE_COMPLEX)
 966                   && bbd[si].end_of_trace >= 0
 967                   && !connected[bbd[si].end_of_trace]
 968                   && (BB_PARTITION (e->src) == current_partition)
 969                   && (!best
 970                       || e->probability > best->probability
 971                       || (e->probability == best->probability
 972                           && traces[bbd[si].end_of_trace].length > best_len)))
 973                 {
 974                   best = e;
 975                   best_len = traces[bbd[si].end_of_trace].length;
 976                 }
 977             }
 978           if (best)
 979             {
 980               best->src->aux = best->dest;
 981               t2 = bbd[best->src->index].end_of_trace;
 982               connected[t2] = true;
 983
 984               if (dump_file)
 985                 {
 986                   fprintf (dump_file, "Connection: %d %d\n",
 987                            best->src->index, best->dest->index);
 988                 }
 989             }
 990           else
 991             break;
 992         }
 993
 994       if (last_trace >= 0)
 995         traces[last_trace].last->aux = traces[t2].first;
 996       last_trace = t;
 997
 998       /* Find the successor traces.  */
 999       while (1)
1000         {
1001           /* Find the continuation of the chain.  */
1002           edge_iterator ei;
1003           best = NULL;
1004           best_len = 0;
1005           FOR_EACH_EDGE (e, ei, traces[t].last->succs)
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                   && (BB_PARTITION (e->dest) == current_partition)
1015                   && (!best
1016                       || e->probability > best->probability
1017                       || (e->probability == best->probability
1018                           && traces[bbd[di].start_of_trace].length > best_len)))
1019                 {
1020                   best = e;
1021                   best_len = traces[bbd[di].start_of_trace].length;
1022                 }
1023             }
1024
1025           if (best)
1026             {
1027               if (dump_file)
1028                 {
1029                   fprintf (dump_file, "Connection: %d %d\n",
1030                            best->src->index, best->dest->index);
1031                 }
1032               t = bbd[best->dest->index].start_of_trace;
1033               traces[last_trace].last->aux = traces[t].first;
1034               connected[t] = true;
1035               last_trace = t;
1036             }
1037           else
1038             {
1039               /* Try to connect the traces by duplication of 1 block.  */
1040               edge e2;
1041               basic_block next_bb = NULL;
1042               bool try_copy = false;
1043
1044               FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1045                 if (e->dest != EXIT_BLOCK_PTR
1046                     && (e->flags & EDGE_CAN_FALLTHRU)
1047                     && !(e->flags & EDGE_COMPLEX)
1048                     && (!best || e->probability > best->probability))
1049                   {
1050                     edge_iterator ei;
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_EACH_EDGE (e2, ei, e->dest->succs)
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                                 && (BB_PARTITION (e2->dest) == current_partition)
1076                                 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1077                                 && (e2->count >= count_threshold)
1078                                 && (!best2
1079                                     || e2->probability > best2->probability
1080                                     || (e2->probability == best2->probability
1081                                         && traces[bbd[di].start_of_trace].length
1082                                            > best2_len))))
1083                           {
1084                             best = e;
1085                             best2 = e2;
1086                             if (e2->dest != EXIT_BLOCK_PTR)
1087                               best2_len = traces[bbd[di].start_of_trace].length;
1088                             else
1089                               best2_len = INT_MAX;
1090                             next_bb = e2->dest;
1091                             try_copy = true;
1092                           }
1093                       }
1094                   }
1095
1096               if (flag_reorder_blocks_and_partition)
1097                 try_copy = false;
1098
1099               /* Copy tiny blocks always; copy larger blocks only when the
1100                  edge is traversed frequently enough.  */
1101               if (try_copy
1102                   && copy_bb_p (best->dest,
1103                                 optimize_edge_for_speed_p (best)
1104                                 && EDGE_FREQUENCY (best) >= freq_threshold
1105                                 && best->count >= count_threshold))
1106                 {
1107                   basic_block new_bb;
1108
1109                   if (dump_file)
1110                     {
1111                       fprintf (dump_file, "Connection: %d %d ",
1112                                traces[t].last->index, best->dest->index);
1113                       if (!next_bb)
1114                         fputc ('\n', dump_file);
1115                       else if (next_bb == EXIT_BLOCK_PTR)
1116                         fprintf (dump_file, "exit\n");
1117                       else
1118                         fprintf (dump_file, "%d\n", next_bb->index);
1119                     }
1120
1121                   new_bb = copy_bb (best->dest, best, traces[t].last, t);
1122                   traces[t].last = new_bb;
1123                   if (next_bb && next_bb != EXIT_BLOCK_PTR)
1124                     {
1125                       t = bbd[next_bb->index].start_of_trace;
1126                       traces[last_trace].last->aux = traces[t].first;
1127                       connected[t] = true;
1128                       last_trace = t;
1129                     }
1130                   else
1131                     break;      /* Stop finding the successor traces.  */
1132                 }
1133               else
1134                 break;  /* Stop finding the successor traces.  */
1135             }
1136         }
1137     }
1138
1139   if (dump_file)
1140     {
1141       basic_block bb;
1142
1143       fprintf (dump_file, "Final order:\n");
1144       for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1145         fprintf (dump_file, "%d ", bb->index);
1146       fprintf (dump_file, "\n");
1147       fflush (dump_file);
1148     }
1149
1150   FREE (connected);
1151 }
1152
1153 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1154    when code size is allowed to grow by duplication.  */
1155
1156 static bool
1157 copy_bb_p (const_basic_block bb, int code_may_grow)
1158 {
1159   int size = 0;
1160   int max_size = uncond_jump_length;
1161   rtx insn;
1162
1163   if (!bb->frequency)
1164     return false;
1165   if (EDGE_COUNT (bb->preds) < 2)
1166     return false;
1167   if (!can_duplicate_block_p (bb))
1168     return false;
1169
1170   /* Avoid duplicating blocks which have many successors (PR/13430).  */
1171   if (EDGE_COUNT (bb->succs) > 8)
1172     return false;
1173
1174   if (code_may_grow && optimize_bb_for_speed_p (bb))
1175     max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1176
1177   FOR_BB_INSNS (bb, insn)
1178     {
1179       if (INSN_P (insn))
1180         size += get_attr_min_length (insn);
1181     }
1182
1183   if (size <= max_size)
1184     return true;
1185
1186   if (dump_file)
1187     {
1188       fprintf (dump_file,
1189                "Block %d can't be copied because its size = %d.\n",
1190                bb->index, size);
1191     }
1192
1193   return false;
1194 }
1195
1196 /* Return the length of unconditional jump instruction.  */
1197
1198 static int
1199 get_uncond_jump_length (void)
1200 {
1201   rtx label, jump;
1202   int length;
1203
1204   label = emit_label_before (gen_label_rtx (), get_insns ());
1205   jump = emit_jump_insn (gen_jump (label));
1206
1207   length = get_attr_min_length (jump);
1208
1209   delete_insn (jump);
1210   delete_insn (label);
1211   return length;
1212 }
1213
1214 /* Find the basic blocks that are rarely executed and need to be moved to
1215    a separate section of the .o file (to cut down on paging and improve
1216    cache locality).  */
1217
1218 static void
1219 find_rarely_executed_basic_blocks_and_crossing_edges (edge **crossing_edges,
1220                                                       int *n_crossing_edges,
1221                                                       int *max_idx)
1222 {
1223   basic_block bb;
1224   edge e;
1225   int i;
1226   edge_iterator ei;
1227
1228   /* Mark which partition (hot/cold) each basic block belongs in.  */
1229
1230   FOR_EACH_BB (bb)
1231     {
1232       if (probably_never_executed_bb_p (bb))
1233         BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1234       else
1235         BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1236     }
1237
1238   /* Mark every edge that crosses between sections.  */
1239
1240   i = 0;
1241   FOR_EACH_BB (bb)
1242     FOR_EACH_EDGE (e, ei, bb->succs)
1243     {
1244       if (e->src != ENTRY_BLOCK_PTR
1245           && e->dest != EXIT_BLOCK_PTR
1246           && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1247         {
1248           e->flags |= EDGE_CROSSING;
1249           if (i == *max_idx)
1250             {
1251               *max_idx *= 2;
1252               *crossing_edges = XRESIZEVEC (edge, *crossing_edges, *max_idx);
1253             }
1254           (*crossing_edges)[i++] = e;
1255         }
1256       else
1257         e->flags &= ~EDGE_CROSSING;
1258     }
1259   *n_crossing_edges = i;
1260 }
1261
1262 /* If any destination of a crossing edge does not have a label, add label;
1263    Convert any fall-through crossing edges (for blocks that do not contain
1264    a jump) to unconditional jumps.  */
1265
1266 static void
1267 add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
1268 {
1269   int i;
1270   basic_block src;
1271   basic_block dest;
1272   rtx label;
1273   rtx barrier;
1274   rtx new_jump;
1275
1276   for (i=0; i < n_crossing_edges; i++)
1277     {
1278       if (crossing_edges[i])
1279         {
1280           src = crossing_edges[i]->src;
1281           dest = crossing_edges[i]->dest;
1282
1283           /* Make sure dest has a label.  */
1284
1285           if (dest && (dest != EXIT_BLOCK_PTR))
1286             {
1287               label = block_label (dest);
1288
1289               /* Make sure source block ends with a jump.  If the
1290                  source block does not end with a jump it might end
1291                  with a call_insn;  this case will be handled in
1292                  fix_up_fall_thru_edges function.  */
1293
1294               if (src && (src != ENTRY_BLOCK_PTR))
1295                 {
1296                   if (!JUMP_P (BB_END (src)) && !block_ends_with_call_p (src))
1297                     /* bb just falls through.  */
1298                     {
1299                       /* make sure there's only one successor */
1300                       gcc_assert (single_succ_p (src));
1301
1302                       /* Find label in dest block.  */
1303                       label = block_label (dest);
1304
1305                       new_jump = emit_jump_insn_after (gen_jump (label),
1306                                                        BB_END (src));
1307                       barrier = emit_barrier_after (new_jump);
1308                       JUMP_LABEL (new_jump) = label;
1309                       LABEL_NUSES (label) += 1;
1310                       src->il.rtl->footer = unlink_insn_chain (barrier, barrier);
1311                       /* Mark edge as non-fallthru.  */
1312                       crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
1313                     } /* end: 'if (GET_CODE ... '  */
1314                 } /* end: 'if (src && src->index...'  */
1315             } /* end: 'if (dest && dest->index...'  */
1316         } /* end: 'if (crossing_edges[i]...'  */
1317     } /* end for loop  */
1318 }
1319
1320 /* Find any bb's where the fall-through edge is a crossing edge (note that
1321    these bb's must also contain a conditional jump or end with a call
1322    instruction; we've already dealt with fall-through edges for blocks
1323    that didn't have a conditional jump or didn't end with call instruction
1324    in the call to add_labels_and_missing_jumps).  Convert the fall-through
1325    edge to non-crossing edge by inserting a new bb to fall-through into.
1326    The new bb will contain an unconditional jump (crossing edge) to the
1327    original fall through destination.  */
1328
1329 static void
1330 fix_up_fall_thru_edges (void)
1331 {
1332   basic_block cur_bb;
1333   basic_block new_bb;
1334   edge succ1;
1335   edge succ2;
1336   edge fall_thru;
1337   edge cond_jump = NULL;
1338   edge e;
1339   bool cond_jump_crosses;
1340   int invert_worked;
1341   rtx old_jump;
1342   rtx fall_thru_label;
1343   rtx barrier;
1344
1345   FOR_EACH_BB (cur_bb)
1346     {
1347       fall_thru = NULL;
1348       if (EDGE_COUNT (cur_bb->succs) > 0)
1349         succ1 = EDGE_SUCC (cur_bb, 0);
1350       else
1351         succ1 = NULL;
1352
1353       if (EDGE_COUNT (cur_bb->succs) > 1)
1354         succ2 = EDGE_SUCC (cur_bb, 1);
1355       else
1356         succ2 = NULL;
1357
1358       /* Find the fall-through edge.  */
1359
1360       if (succ1
1361           && (succ1->flags & EDGE_FALLTHRU))
1362         {
1363           fall_thru = succ1;
1364           cond_jump = succ2;
1365         }
1366       else if (succ2
1367                && (succ2->flags & EDGE_FALLTHRU))
1368         {
1369           fall_thru = succ2;
1370           cond_jump = succ1;
1371         }
1372       else if (!fall_thru && succ1 && block_ends_with_call_p (cur_bb))
1373       {
1374         edge e;
1375         edge_iterator ei;
1376
1377         /* Find EDGE_CAN_FALLTHRU edge.  */
1378         FOR_EACH_EDGE (e, ei, cur_bb->succs)
1379           if (e->flags & EDGE_CAN_FALLTHRU)
1380           {
1381             fall_thru = e;
1382             break;
1383           }
1384       }
1385
1386       if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1387         {
1388           /* Check to see if the fall-thru edge is a crossing edge.  */
1389
1390           if (fall_thru->flags & EDGE_CROSSING)
1391             {
1392               /* The fall_thru edge crosses; now check the cond jump edge, if
1393                  it exists.  */
1394
1395               cond_jump_crosses = true;
1396               invert_worked  = 0;
1397               old_jump = BB_END (cur_bb);
1398
1399               /* Find the jump instruction, if there is one.  */
1400
1401               if (cond_jump)
1402                 {
1403                   if (!(cond_jump->flags & EDGE_CROSSING))
1404                     cond_jump_crosses = false;
1405
1406                   /* We know the fall-thru edge crosses; if the cond
1407                      jump edge does NOT cross, and its destination is the
1408                      next block in the bb order, invert the jump
1409                      (i.e. fix it so the fall thru does not cross and
1410                      the cond jump does).  */
1411
1412                   if (!cond_jump_crosses
1413                       && cur_bb->aux == cond_jump->dest)
1414                     {
1415                       /* Find label in fall_thru block. We've already added
1416                          any missing labels, so there must be one.  */
1417
1418                       fall_thru_label = block_label (fall_thru->dest);
1419
1420                       if (old_jump && JUMP_P (old_jump) && fall_thru_label)
1421                         invert_worked = invert_jump (old_jump,
1422                                                      fall_thru_label,0);
1423                       if (invert_worked)
1424                         {
1425                           fall_thru->flags &= ~EDGE_FALLTHRU;
1426                           cond_jump->flags |= EDGE_FALLTHRU;
1427                           update_br_prob_note (cur_bb);
1428                           e = fall_thru;
1429                           fall_thru = cond_jump;
1430                           cond_jump = e;
1431                           cond_jump->flags |= EDGE_CROSSING;
1432                           fall_thru->flags &= ~EDGE_CROSSING;
1433                         }
1434                     }
1435                 }
1436
1437               if (cond_jump_crosses || !invert_worked)
1438                 {
1439                   /* This is the case where both edges out of the basic
1440                      block are crossing edges. Here we will fix up the
1441                      fall through edge. The jump edge will be taken care
1442                      of later.  The EDGE_CROSSING flag of fall_thru edge
1443                      is unset before the call to force_nonfallthru
1444                      function because if a new basic-block is created
1445                      this edge remains in the current section boundary
1446                      while the edge between new_bb and the fall_thru->dest
1447                      becomes EDGE_CROSSING.  */
1448
1449                   fall_thru->flags &= ~EDGE_CROSSING;
1450                   new_bb = force_nonfallthru (fall_thru);
1451
1452                   if (new_bb)
1453                     {
1454                       new_bb->aux = cur_bb->aux;
1455                       cur_bb->aux = new_bb;
1456
1457                       /* Make sure new fall-through bb is in same
1458                          partition as bb it's falling through from.  */
1459
1460                       BB_COPY_PARTITION (new_bb, cur_bb);
1461                       single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
1462                     }
1463                   else
1464                     {
1465                       /* If a new basic-block was not created; restore
1466                          the EDGE_CROSSING flag.  */
1467                       fall_thru->flags |= EDGE_CROSSING;
1468                     }
1469
1470                   /* Add barrier after new jump */
1471
1472                   if (new_bb)
1473                     {
1474                       barrier = emit_barrier_after (BB_END (new_bb));
1475                       new_bb->il.rtl->footer = unlink_insn_chain (barrier,
1476                                                                barrier);
1477                     }
1478                   else
1479                     {
1480                       barrier = emit_barrier_after (BB_END (cur_bb));
1481                       cur_bb->il.rtl->footer = unlink_insn_chain (barrier,
1482                                                                barrier);
1483                     }
1484                 }
1485             }
1486         }
1487     }
1488 }
1489
1490 /* This function checks the destination block of a "crossing jump" to
1491    see if it has any crossing predecessors that begin with a code label
1492    and end with an unconditional jump.  If so, it returns that predecessor
1493    block.  (This is to avoid creating lots of new basic blocks that all
1494    contain unconditional jumps to the same destination).  */
1495
1496 static basic_block
1497 find_jump_block (basic_block jump_dest)
1498 {
1499   basic_block source_bb = NULL;
1500   edge e;
1501   rtx insn;
1502   edge_iterator ei;
1503
1504   FOR_EACH_EDGE (e, ei, jump_dest->preds)
1505     if (e->flags & EDGE_CROSSING)
1506       {
1507         basic_block src = e->src;
1508
1509         /* Check each predecessor to see if it has a label, and contains
1510            only one executable instruction, which is an unconditional jump.
1511            If so, we can use it.  */
1512
1513         if (LABEL_P (BB_HEAD (src)))
1514           for (insn = BB_HEAD (src);
1515                !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1516                insn = NEXT_INSN (insn))
1517             {
1518               if (INSN_P (insn)
1519                   && insn == BB_END (src)
1520                   && JUMP_P (insn)
1521                   && !any_condjump_p (insn))
1522                 {
1523                   source_bb = src;
1524                   break;
1525                 }
1526             }
1527
1528         if (source_bb)
1529           break;
1530       }
1531
1532   return source_bb;
1533 }
1534
1535 /* Find all BB's with conditional jumps that are crossing edges;
1536    insert a new bb and make the conditional jump branch to the new
1537    bb instead (make the new bb same color so conditional branch won't
1538    be a 'crossing' edge).  Insert an unconditional jump from the
1539    new bb to the original destination of the conditional jump.  */
1540
1541 static void
1542 fix_crossing_conditional_branches (void)
1543 {
1544   basic_block cur_bb;
1545   basic_block new_bb;
1546   basic_block last_bb;
1547   basic_block dest;
1548   edge succ1;
1549   edge succ2;
1550   edge crossing_edge;
1551   edge new_edge;
1552   rtx old_jump;
1553   rtx set_src;
1554   rtx old_label = NULL_RTX;
1555   rtx new_label;
1556   rtx new_jump;
1557   rtx barrier;
1558
1559  last_bb = EXIT_BLOCK_PTR->prev_bb;
1560
1561   FOR_EACH_BB (cur_bb)
1562     {
1563       crossing_edge = NULL;
1564       if (EDGE_COUNT (cur_bb->succs) > 0)
1565         succ1 = EDGE_SUCC (cur_bb, 0);
1566       else
1567         succ1 = NULL;
1568
1569       if (EDGE_COUNT (cur_bb->succs) > 1)
1570         succ2 = EDGE_SUCC (cur_bb, 1);
1571       else
1572         succ2 = NULL;
1573
1574       /* We already took care of fall-through edges, so only one successor
1575          can be a crossing edge.  */
1576
1577       if (succ1 && (succ1->flags & EDGE_CROSSING))
1578         crossing_edge = succ1;
1579       else if (succ2 && (succ2->flags & EDGE_CROSSING))
1580         crossing_edge = succ2;
1581
1582       if (crossing_edge)
1583         {
1584           old_jump = BB_END (cur_bb);
1585
1586           /* Check to make sure the jump instruction is a
1587              conditional jump.  */
1588
1589           set_src = NULL_RTX;
1590
1591           if (any_condjump_p (old_jump))
1592             {
1593               if (GET_CODE (PATTERN (old_jump)) == SET)
1594                 set_src = SET_SRC (PATTERN (old_jump));
1595               else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1596                 {
1597                   set_src = XVECEXP (PATTERN (old_jump), 0,0);
1598                   if (GET_CODE (set_src) == SET)
1599                     set_src = SET_SRC (set_src);
1600                   else
1601                     set_src = NULL_RTX;
1602                 }
1603             }
1604
1605           if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1606             {
1607               if (GET_CODE (XEXP (set_src, 1)) == PC)
1608                 old_label = XEXP (set_src, 2);
1609               else if (GET_CODE (XEXP (set_src, 2)) == PC)
1610                 old_label = XEXP (set_src, 1);
1611
1612               /* Check to see if new bb for jumping to that dest has
1613                  already been created; if so, use it; if not, create
1614                  a new one.  */
1615
1616               new_bb = find_jump_block (crossing_edge->dest);
1617
1618               if (new_bb)
1619                 new_label = block_label (new_bb);
1620               else
1621                 {
1622                   /* Create new basic block to be dest for
1623                      conditional jump.  */
1624
1625                   new_bb = create_basic_block (NULL, NULL, last_bb);
1626                   new_bb->aux = last_bb->aux;
1627                   last_bb->aux = new_bb;
1628                   last_bb = new_bb;
1629                   /* Put appropriate instructions in new bb.  */
1630
1631                   new_label = gen_label_rtx ();
1632                   emit_label_before (new_label, BB_HEAD (new_bb));
1633                   BB_HEAD (new_bb) = new_label;
1634
1635                   if (GET_CODE (old_label) == LABEL_REF)
1636                     {
1637                       old_label = JUMP_LABEL (old_jump);
1638                       new_jump = emit_jump_insn_after (gen_jump
1639                                                        (old_label),
1640                                                        BB_END (new_bb));
1641                     }
1642                   else
1643                     {
1644                       gcc_assert (HAVE_return
1645                                   && GET_CODE (old_label) == RETURN);
1646                       new_jump = emit_jump_insn_after (gen_return (),
1647                                                        BB_END (new_bb));
1648                     }
1649
1650                   barrier = emit_barrier_after (new_jump);
1651                   JUMP_LABEL (new_jump) = old_label;
1652                   new_bb->il.rtl->footer = unlink_insn_chain (barrier,
1653                                                            barrier);
1654
1655                   /* Make sure new bb is in same partition as source
1656                      of conditional branch.  */
1657                   BB_COPY_PARTITION (new_bb, cur_bb);
1658                 }
1659
1660               /* Make old jump branch to new bb.  */
1661
1662               redirect_jump (old_jump, new_label, 0);
1663
1664               /* Remove crossing_edge as predecessor of 'dest'.  */
1665
1666               dest = crossing_edge->dest;
1667
1668               redirect_edge_succ (crossing_edge, new_bb);
1669
1670               /* Make a new edge from new_bb to old dest; new edge
1671                  will be a successor for new_bb and a predecessor
1672                  for 'dest'.  */
1673
1674               if (EDGE_COUNT (new_bb->succs) == 0)
1675                 new_edge = make_edge (new_bb, dest, 0);
1676               else
1677                 new_edge = EDGE_SUCC (new_bb, 0);
1678
1679               crossing_edge->flags &= ~EDGE_CROSSING;
1680               new_edge->flags |= EDGE_CROSSING;
1681             }
1682         }
1683     }
1684 }
1685
1686 /* Find any unconditional branches that cross between hot and cold
1687    sections.  Convert them into indirect jumps instead.  */
1688
1689 static void
1690 fix_crossing_unconditional_branches (void)
1691 {
1692   basic_block cur_bb;
1693   rtx last_insn;
1694   rtx label;
1695   rtx label_addr;
1696   rtx indirect_jump_sequence;
1697   rtx jump_insn = NULL_RTX;
1698   rtx new_reg;
1699   rtx cur_insn;
1700   edge succ;
1701
1702   FOR_EACH_BB (cur_bb)
1703     {
1704       last_insn = BB_END (cur_bb);
1705
1706       if (EDGE_COUNT (cur_bb->succs) < 1)
1707         continue;
1708
1709       succ = EDGE_SUCC (cur_bb, 0);
1710
1711       /* Check to see if bb ends in a crossing (unconditional) jump.  At
1712          this point, no crossing jumps should be conditional.  */
1713
1714       if (JUMP_P (last_insn)
1715           && (succ->flags & EDGE_CROSSING))
1716         {
1717           rtx label2, table;
1718
1719           gcc_assert (!any_condjump_p (last_insn));
1720
1721           /* Make sure the jump is not already an indirect or table jump.  */
1722
1723           if (!computed_jump_p (last_insn)
1724               && !tablejump_p (last_insn, &label2, &table))
1725             {
1726               /* We have found a "crossing" unconditional branch.  Now
1727                  we must convert it to an indirect jump.  First create
1728                  reference of label, as target for jump.  */
1729
1730               label = JUMP_LABEL (last_insn);
1731               label_addr = gen_rtx_LABEL_REF (Pmode, label);
1732               LABEL_NUSES (label) += 1;
1733
1734               /* Get a register to use for the indirect jump.  */
1735
1736               new_reg = gen_reg_rtx (Pmode);
1737
1738               /* Generate indirect the jump sequence.  */
1739
1740               start_sequence ();
1741               emit_move_insn (new_reg, label_addr);
1742               emit_indirect_jump (new_reg);
1743               indirect_jump_sequence = get_insns ();
1744               end_sequence ();
1745
1746               /* Make sure every instruction in the new jump sequence has
1747                  its basic block set to be cur_bb.  */
1748
1749               for (cur_insn = indirect_jump_sequence; cur_insn;
1750                    cur_insn = NEXT_INSN (cur_insn))
1751                 {
1752                   if (!BARRIER_P (cur_insn))
1753                     BLOCK_FOR_INSN (cur_insn) = cur_bb;
1754                   if (JUMP_P (cur_insn))
1755                     jump_insn = cur_insn;
1756                 }
1757
1758               /* Insert the new (indirect) jump sequence immediately before
1759                  the unconditional jump, then delete the unconditional jump.  */
1760
1761               emit_insn_before (indirect_jump_sequence, last_insn);
1762               delete_insn (last_insn);
1763
1764               /* Make BB_END for cur_bb be the jump instruction (NOT the
1765                  barrier instruction at the end of the sequence...).  */
1766
1767               BB_END (cur_bb) = jump_insn;
1768             }
1769         }
1770     }
1771 }
1772
1773 /* Add REG_CROSSING_JUMP note to all crossing jump insns.  */
1774
1775 static void
1776 add_reg_crossing_jump_notes (void)
1777 {
1778   basic_block bb;
1779   edge e;
1780   edge_iterator ei;
1781
1782   FOR_EACH_BB (bb)
1783     FOR_EACH_EDGE (e, ei, bb->succs)
1784       if ((e->flags & EDGE_CROSSING)
1785           && JUMP_P (BB_END (e->src)))
1786         add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
1787 }
1788
1789 /* Hot and cold basic blocks are partitioned and put in separate
1790    sections of the .o file, to reduce paging and improve cache
1791    performance (hopefully).  This can result in bits of code from the
1792    same function being widely separated in the .o file.  However this
1793    is not obvious to the current bb structure.  Therefore we must take
1794    care to ensure that: 1). There are no fall_thru edges that cross
1795    between sections; 2). For those architectures which have "short"
1796    conditional branches, all conditional branches that attempt to
1797    cross between sections are converted to unconditional branches;
1798    and, 3). For those architectures which have "short" unconditional
1799    branches, all unconditional branches that attempt to cross between
1800    sections are converted to indirect jumps.
1801
1802    The code for fixing up fall_thru edges that cross between hot and
1803    cold basic blocks does so by creating new basic blocks containing
1804    unconditional branches to the appropriate label in the "other"
1805    section.  The new basic block is then put in the same (hot or cold)
1806    section as the original conditional branch, and the fall_thru edge
1807    is modified to fall into the new basic block instead.  By adding
1808    this level of indirection we end up with only unconditional branches
1809    crossing between hot and cold sections.
1810
1811    Conditional branches are dealt with by adding a level of indirection.
1812    A new basic block is added in the same (hot/cold) section as the
1813    conditional branch, and the conditional branch is retargeted to the
1814    new basic block.  The new basic block contains an unconditional branch
1815    to the original target of the conditional branch (in the other section).
1816
1817    Unconditional branches are dealt with by converting them into
1818    indirect jumps.  */
1819
1820 static void
1821 fix_edges_for_rarely_executed_code (edge *crossing_edges,
1822                                     int n_crossing_edges)
1823 {
1824   /* Make sure the source of any crossing edge ends in a jump and the
1825      destination of any crossing edge has a label.  */
1826
1827   add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
1828
1829   /* Convert all crossing fall_thru edges to non-crossing fall
1830      thrus to unconditional jumps (that jump to the original fall
1831      thru dest).  */
1832
1833   fix_up_fall_thru_edges ();
1834
1835   /* If the architecture does not have conditional branches that can
1836      span all of memory, convert crossing conditional branches into
1837      crossing unconditional branches.  */
1838
1839   if (!HAS_LONG_COND_BRANCH)
1840     fix_crossing_conditional_branches ();
1841
1842   /* If the architecture does not have unconditional branches that
1843      can span all of memory, convert crossing unconditional branches
1844      into indirect jumps.  Since adding an indirect jump also adds
1845      a new register usage, update the register usage information as
1846      well.  */
1847
1848   if (!HAS_LONG_UNCOND_BRANCH)
1849     fix_crossing_unconditional_branches ();
1850
1851   add_reg_crossing_jump_notes ();
1852 }
1853
1854 /* Verify, in the basic block chain, that there is at most one switch
1855    between hot/cold partitions. This is modelled on
1856    rtl_verify_flow_info_1, but it cannot go inside that function
1857    because this condition will not be true until after
1858    reorder_basic_blocks is called.  */
1859
1860 static void
1861 verify_hot_cold_block_grouping (void)
1862 {
1863   basic_block bb;
1864   int err = 0;
1865   bool switched_sections = false;
1866   int current_partition = 0;
1867
1868   FOR_EACH_BB (bb)
1869     {
1870       if (!current_partition)
1871         current_partition = BB_PARTITION (bb);
1872       if (BB_PARTITION (bb) != current_partition)
1873         {
1874           if (switched_sections)
1875             {
1876               error ("multiple hot/cold transitions found (bb %i)",
1877                      bb->index);
1878               err = 1;
1879             }
1880           else
1881             {
1882               switched_sections = true;
1883               current_partition = BB_PARTITION (bb);
1884             }
1885         }
1886     }
1887
1888   gcc_assert(!err);
1889 }
1890
1891 /* Reorder basic blocks.  The main entry point to this file.  FLAGS is
1892    the set of flags to pass to cfg_layout_initialize().  */
1893
1894 void
1895 reorder_basic_blocks (void)
1896 {
1897   int n_traces;
1898   int i;
1899   struct trace *traces;
1900
1901   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
1902
1903   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
1904     return;
1905
1906   set_edge_can_fallthru_flag ();
1907   mark_dfs_back_edges ();
1908
1909   /* We are estimating the length of uncond jump insn only once since the code
1910      for getting the insn length always returns the minimal length now.  */
1911   if (uncond_jump_length == 0)
1912     uncond_jump_length = get_uncond_jump_length ();
1913
1914   /* We need to know some information for each basic block.  */
1915   array_size = GET_ARRAY_SIZE (last_basic_block);
1916   bbd = XNEWVEC (bbro_basic_block_data, array_size);
1917   for (i = 0; i < array_size; i++)
1918     {
1919       bbd[i].start_of_trace = -1;
1920       bbd[i].in_trace = -1;
1921       bbd[i].end_of_trace = -1;
1922       bbd[i].heap = NULL;
1923       bbd[i].node = NULL;
1924     }
1925
1926   traces = XNEWVEC (struct trace, n_basic_blocks);
1927   n_traces = 0;
1928   find_traces (&n_traces, traces);
1929   connect_traces (n_traces, traces);
1930   FREE (traces);
1931   FREE (bbd);
1932
1933   relink_block_chain (/*stay_in_cfglayout_mode=*/true);
1934
1935   if (dump_file)
1936     dump_flow_info (dump_file, dump_flags);
1937
1938   if (flag_reorder_blocks_and_partition)
1939     verify_hot_cold_block_grouping ();
1940 }
1941
1942 /* Determine which partition the first basic block in the function
1943    belongs to, then find the first basic block in the current function
1944    that belongs to a different section, and insert a
1945    NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1946    instruction stream.  When writing out the assembly code,
1947    encountering this note will make the compiler switch between the
1948    hot and cold text sections.  */
1949
1950 static void
1951 insert_section_boundary_note (void)
1952 {
1953   basic_block bb;
1954   rtx new_note;
1955   int first_partition = 0;
1956
1957   if (flag_reorder_blocks_and_partition)
1958     FOR_EACH_BB (bb)
1959     {
1960       if (!first_partition)
1961         first_partition = BB_PARTITION (bb);
1962       if (BB_PARTITION (bb) != first_partition)
1963         {
1964           new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
1965                                        BB_HEAD (bb));
1966           /* ??? This kind of note always lives between basic blocks,
1967              but add_insn_before will set BLOCK_FOR_INSN anyway.  */
1968           BLOCK_FOR_INSN (new_note) = NULL;
1969           break;
1970         }
1971     }
1972 }
1973
1974 /* Duplicate the blocks containing computed gotos.  This basically unfactors
1975    computed gotos that were factored early on in the compilation process to
1976    speed up edge based data flow.  We used to not unfactoring them again,
1977    which can seriously pessimize code with many computed jumps in the source
1978    code, such as interpreters.  See e.g. PR15242.  */
1979
1980 static bool
1981 gate_duplicate_computed_gotos (void)
1982 {
1983   if (targetm.cannot_modify_jumps_p ())
1984     return false;
1985   return (optimize > 0
1986           && flag_expensive_optimizations
1987           && ! optimize_function_for_size_p (cfun));
1988 }
1989
1990
1991 static unsigned int
1992 duplicate_computed_gotos (void)
1993 {
1994   basic_block bb, new_bb;
1995   bitmap candidates;
1996   int max_size;
1997
1998   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
1999     return 0;
2000
2001   cfg_layout_initialize (0);
2002
2003   /* We are estimating the length of uncond jump insn only once
2004      since the code for getting the insn length always returns
2005      the minimal length now.  */
2006   if (uncond_jump_length == 0)
2007     uncond_jump_length = get_uncond_jump_length ();
2008
2009   max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2010   candidates = BITMAP_ALLOC (NULL);
2011
2012   /* Look for blocks that end in a computed jump, and see if such blocks
2013      are suitable for unfactoring.  If a block is a candidate for unfactoring,
2014      mark it in the candidates.  */
2015   FOR_EACH_BB (bb)
2016     {
2017       rtx insn;
2018       edge e;
2019       edge_iterator ei;
2020       int size, all_flags;
2021
2022       /* Build the reorder chain for the original order of blocks.  */
2023       if (bb->next_bb != EXIT_BLOCK_PTR)
2024         bb->aux = bb->next_bb;
2025
2026       /* Obviously the block has to end in a computed jump.  */
2027       if (!computed_jump_p (BB_END (bb)))
2028         continue;
2029
2030       /* Only consider blocks that can be duplicated.  */
2031       if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
2032           || !can_duplicate_block_p (bb))
2033         continue;
2034
2035       /* Make sure that the block is small enough.  */
2036       size = 0;
2037       FOR_BB_INSNS (bb, insn)
2038         if (INSN_P (insn))
2039           {
2040             size += get_attr_min_length (insn);
2041             if (size > max_size)
2042                break;
2043           }
2044       if (size > max_size)
2045         continue;
2046
2047       /* Final check: there must not be any incoming abnormal edges.  */
2048       all_flags = 0;
2049       FOR_EACH_EDGE (e, ei, bb->preds)
2050         all_flags |= e->flags;
2051       if (all_flags & EDGE_COMPLEX)
2052         continue;
2053
2054       bitmap_set_bit (candidates, bb->index);
2055     }
2056
2057   /* Nothing to do if there is no computed jump here.  */
2058   if (bitmap_empty_p (candidates))
2059     goto done;
2060
2061   /* Duplicate computed gotos.  */
2062   FOR_EACH_BB (bb)
2063     {
2064       if (bb->il.rtl->visited)
2065         continue;
2066
2067       bb->il.rtl->visited = 1;
2068
2069       /* BB must have one outgoing edge.  That edge must not lead to
2070          the exit block or the next block.
2071          The destination must have more than one predecessor.  */
2072       if (!single_succ_p (bb)
2073           || single_succ (bb) == EXIT_BLOCK_PTR
2074           || single_succ (bb) == bb->next_bb
2075           || single_pred_p (single_succ (bb)))
2076         continue;
2077
2078       /* The successor block has to be a duplication candidate.  */
2079       if (!bitmap_bit_p (candidates, single_succ (bb)->index))
2080         continue;
2081
2082       new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
2083       new_bb->aux = bb->aux;
2084       bb->aux = new_bb;
2085       new_bb->il.rtl->visited = 1;
2086     }
2087
2088 done:
2089   cfg_layout_finalize ();
2090
2091   BITMAP_FREE (candidates);
2092   return 0;
2093 }
2094
2095 struct rtl_opt_pass pass_duplicate_computed_gotos =
2096 {
2097  {
2098   RTL_PASS,
2099   "compgotos",                          /* name */
2100   gate_duplicate_computed_gotos,        /* gate */
2101   duplicate_computed_gotos,             /* execute */
2102   NULL,                                 /* sub */
2103   NULL,                                 /* next */
2104   0,                                    /* static_pass_number */
2105   TV_REORDER_BLOCKS,                    /* tv_id */
2106   0,                                    /* properties_required */
2107   0,                                    /* properties_provided */
2108   0,                                    /* properties_destroyed */
2109   0,                                    /* todo_flags_start */
2110   TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
2111  }
2112 };
2113
2114
2115 /* This function is the main 'entrance' for the optimization that
2116    partitions hot and cold basic blocks into separate sections of the
2117    .o file (to improve performance and cache locality).  Ideally it
2118    would be called after all optimizations that rearrange the CFG have
2119    been called.  However part of this optimization may introduce new
2120    register usage, so it must be called before register allocation has
2121    occurred.  This means that this optimization is actually called
2122    well before the optimization that reorders basic blocks (see
2123    function above).
2124
2125    This optimization checks the feedback information to determine
2126    which basic blocks are hot/cold, updates flags on the basic blocks
2127    to indicate which section they belong in.  This information is
2128    later used for writing out sections in the .o file.  Because hot
2129    and cold sections can be arbitrarily large (within the bounds of
2130    memory), far beyond the size of a single function, it is necessary
2131    to fix up all edges that cross section boundaries, to make sure the
2132    instructions used can actually span the required distance.  The
2133    fixes are described below.
2134
2135    Fall-through edges must be changed into jumps; it is not safe or
2136    legal to fall through across a section boundary.  Whenever a
2137    fall-through edge crossing a section boundary is encountered, a new
2138    basic block is inserted (in the same section as the fall-through
2139    source), and the fall through edge is redirected to the new basic
2140    block.  The new basic block contains an unconditional jump to the
2141    original fall-through target.  (If the unconditional jump is
2142    insufficient to cross section boundaries, that is dealt with a
2143    little later, see below).
2144
2145    In order to deal with architectures that have short conditional
2146    branches (which cannot span all of memory) we take any conditional
2147    jump that attempts to cross a section boundary and add a level of
2148    indirection: it becomes a conditional jump to a new basic block, in
2149    the same section.  The new basic block contains an unconditional
2150    jump to the original target, in the other section.
2151
2152    For those architectures whose unconditional branch is also
2153    incapable of reaching all of memory, those unconditional jumps are
2154    converted into indirect jumps, through a register.
2155
2156    IMPORTANT NOTE: This optimization causes some messy interactions
2157    with the cfg cleanup optimizations; those optimizations want to
2158    merge blocks wherever possible, and to collapse indirect jump
2159    sequences (change "A jumps to B jumps to C" directly into "A jumps
2160    to C").  Those optimizations can undo the jump fixes that
2161    partitioning is required to make (see above), in order to ensure
2162    that jumps attempting to cross section boundaries are really able
2163    to cover whatever distance the jump requires (on many architectures
2164    conditional or unconditional jumps are not able to reach all of
2165    memory).  Therefore tests have to be inserted into each such
2166    optimization to make sure that it does not undo stuff necessary to
2167    cross partition boundaries.  This would be much less of a problem
2168    if we could perform this optimization later in the compilation, but
2169    unfortunately the fact that we may need to create indirect jumps
2170    (through registers) requires that this optimization be performed
2171    before register allocation.  */
2172
2173 static void
2174 partition_hot_cold_basic_blocks (void)
2175 {
2176   edge *crossing_edges;
2177   int n_crossing_edges;
2178   int max_edges = 2 * last_basic_block;
2179
2180   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2181     return;
2182
2183   crossing_edges = XCNEWVEC (edge, max_edges);
2184
2185   find_rarely_executed_basic_blocks_and_crossing_edges (&crossing_edges,
2186                                                         &n_crossing_edges,
2187                                                         &max_edges);
2188
2189   if (n_crossing_edges > 0)
2190     fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
2191
2192   free (crossing_edges);
2193 }
2194 \f
2195 static bool
2196 gate_handle_reorder_blocks (void)
2197 {
2198   if (targetm.cannot_modify_jumps_p ())
2199     return false;
2200   return (optimize > 0);
2201 }
2202
2203
2204 /* Reorder basic blocks.  */
2205 static unsigned int
2206 rest_of_handle_reorder_blocks (void)
2207 {
2208   basic_block bb;
2209
2210   /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2211      splitting possibly introduced more crossjumping opportunities.  */
2212   cfg_layout_initialize (CLEANUP_EXPENSIVE);
2213
2214   if ((flag_reorder_blocks || flag_reorder_blocks_and_partition)
2215       /* Don't reorder blocks when optimizing for size because extra jump insns may
2216          be created; also barrier may create extra padding.
2217
2218          More correctly we should have a block reordering mode that tried to
2219          minimize the combined size of all the jumps.  This would more or less
2220          automatically remove extra jumps, but would also try to use more short
2221          jumps instead of long jumps.  */
2222       && optimize_function_for_speed_p (cfun))
2223     {
2224       reorder_basic_blocks ();
2225       cleanup_cfg (CLEANUP_EXPENSIVE);
2226     }
2227
2228   FOR_EACH_BB (bb)
2229     if (bb->next_bb != EXIT_BLOCK_PTR)
2230       bb->aux = bb->next_bb;
2231   cfg_layout_finalize ();
2232
2233   /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes.  */
2234   insert_section_boundary_note ();
2235   return 0;
2236 }
2237
2238 struct rtl_opt_pass pass_reorder_blocks =
2239 {
2240  {
2241   RTL_PASS,
2242   "bbro",                               /* name */
2243   gate_handle_reorder_blocks,           /* gate */
2244   rest_of_handle_reorder_blocks,        /* execute */
2245   NULL,                                 /* sub */
2246   NULL,                                 /* next */
2247   0,                                    /* static_pass_number */
2248   TV_REORDER_BLOCKS,                    /* tv_id */
2249   0,                                    /* properties_required */
2250   0,                                    /* properties_provided */
2251   0,                                    /* properties_destroyed */
2252   0,                                    /* todo_flags_start */
2253   TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
2254  }
2255 };
2256
2257 static bool
2258 gate_handle_partition_blocks (void)
2259 {
2260   /* The optimization to partition hot/cold basic blocks into separate
2261      sections of the .o file does not work well with linkonce or with
2262      user defined section attributes.  Don't call it if either case
2263      arises.  */
2264
2265   return (flag_reorder_blocks_and_partition
2266           && !DECL_ONE_ONLY (current_function_decl)
2267           && !user_defined_section_attribute);
2268 }
2269
2270 /* Partition hot and cold basic blocks.  */
2271 static unsigned int
2272 rest_of_handle_partition_blocks (void)
2273 {
2274   partition_hot_cold_basic_blocks ();
2275   return 0;
2276 }
2277
2278 struct rtl_opt_pass pass_partition_blocks =
2279 {
2280  {
2281   RTL_PASS,
2282   "bbpart",                             /* name */
2283   gate_handle_partition_blocks,         /* gate */
2284   rest_of_handle_partition_blocks,      /* execute */
2285   NULL,                                 /* sub */
2286   NULL,                                 /* next */
2287   0,                                    /* static_pass_number */
2288   TV_REORDER_BLOCKS,                    /* tv_id */
2289   PROP_cfglayout,                       /* properties_required */
2290   0,                                    /* properties_provided */
2291   0,                                    /* properties_destroyed */
2292   0,                                    /* todo_flags_start */
2293   TODO_dump_func | TODO_verify_rtl_sharing/* todo_flags_finish */
2294  }
2295 };