gcc/bb-reorder.c

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