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