LCOV - code coverage report
Current view: top level - gcc - bb-reorder.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 86.0 % 1292 1111
Test Date: 2026-11-14 16:39:50 Functions: 91.5 % 47 43
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Basic block reordering routines for the GNU compiler.
       2              :    Copyright (C) 2000-2026 Free Software Foundation, Inc.
       3              : 
       4              :    This file is part of GCC.
       5              : 
       6              :    GCC is free software; you can redistribute it and/or modify it
       7              :    under the terms of the GNU General Public License as published by
       8              :    the Free Software Foundation; either version 3, or (at your option)
       9              :    any later version.
      10              : 
      11              :    GCC is distributed in the hope that it will be useful, but WITHOUT
      12              :    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
      13              :    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
      14              :    License for more details.
      15              : 
      16              :    You should have received a copy of the GNU General Public License
      17              :    along with GCC; see the file COPYING3.  If not see
      18              :    <http://www.gnu.org/licenses/>.  */
      19              : 
      20              : /* This file contains the "reorder blocks" pass, which changes the control
      21              :    flow of a function to encounter fewer branches; the "partition blocks"
      22              :    pass, which divides the basic blocks into "hot" and "cold" partitions,
      23              :    which are kept separate; and the "duplicate computed gotos" pass, which
      24              :    duplicates blocks ending in an indirect jump.
      25              : 
      26              :    There are two algorithms for "reorder blocks": the "simple" algorithm,
      27              :    which just rearranges blocks, trying to minimize the number of executed
      28              :    unconditional branches; and the "software trace cache" algorithm, which
      29              :    also copies code, and in general tries a lot harder to have long linear
      30              :    pieces of machine code executed.  This algorithm is described next.  */
      31              : 
      32              : /* This (greedy) algorithm constructs traces in several rounds.
      33              :    The construction starts from "seeds".  The seed for the first round
      34              :    is the entry point of the function.  When there are more than one seed,
      35              :    the one with the lowest key in the heap is selected first (see bb_to_key).
      36              :    Then the algorithm repeatedly adds the most probable successor to the end
      37              :    of a trace.  Finally it connects the traces.
      38              : 
      39              :    There are two parameters: Branch Threshold and Exec Threshold.
      40              :    If the probability of an edge to a successor of the current basic block is
      41              :    lower than Branch Threshold or its count is lower than Exec Threshold,
      42              :    then the successor will be the seed in one of the next rounds.
      43              :    Each round has these parameters lower than the previous one.
      44              :    The last round has to have these parameters set to zero so that the
      45              :    remaining blocks are picked up.
      46              : 
      47              :    The algorithm selects the most probable successor from all unvisited
      48              :    successors and successors that have been added to this trace.
      49              :    The other successors (that has not been "sent" to the next round) will be
      50              :    other seeds for this round and the secondary traces will start from them.
      51              :    If the successor has not been visited in this trace, it is added to the
      52              :    trace (however, there is some heuristic for simple branches).
      53              :    If the successor has been visited in this trace, a loop has been found.
      54              :    If the loop has many iterations, the loop is rotated so that the source
      55              :    block of the most probable edge going out of the loop is the last block
      56              :    of the trace.
      57              :    If the loop has few iterations and there is no edge from the last block of
      58              :    the loop going out of the loop, the loop header is duplicated.
      59              : 
      60              :    When connecting traces, the algorithm first checks whether there is an edge
      61              :    from the last block of a trace to the first block of another trace.
      62              :    When there are still some unconnected traces it checks whether there exists
      63              :    a basic block BB such that BB is a successor of the last block of a trace
      64              :    and BB is a predecessor of the first block of another trace.  In this case,
      65              :    BB is duplicated, added at the end of the first trace and the traces are
      66              :    connected through it.
      67              :    The rest of traces are simply connected so there will be a jump to the
      68              :    beginning of the rest of traces.
      69              : 
      70              :    The above description is for the full algorithm, which is used when the
      71              :    function is optimized for speed.  When the function is optimized for size,
      72              :    in order to reduce long jumps and connect more fallthru edges, the
      73              :    algorithm is modified as follows:
      74              :    (1) Break long traces to short ones.  A trace is broken at a block that has
      75              :    multiple predecessors/ successors during trace discovery.  When connecting
      76              :    traces, only connect Trace n with Trace n + 1.  This change reduces most
      77              :    long jumps compared with the above algorithm.
      78              :    (2) Ignore the edge probability and count for fallthru edges.
      79              :    (3) Keep the original order of blocks when there is no chance to fall
      80              :    through.  We rely on the results of cfg_cleanup.
      81              : 
      82              :    To implement the change for code size optimization, block's index is
      83              :    selected as the key and all traces are found in one round.
      84              : 
      85              :    References:
      86              : 
      87              :    "Software Trace Cache"
      88              :    A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
      89              :    http://citeseer.nj.nec.com/15361.html
      90              : 
      91              : */
      92              : 
      93              : #include "config.h"
      94              : #include "system.h"
      95              : #include "coretypes.h"
      96              : #include "backend.h"
      97              : #include "target.h"
      98              : #include "rtl.h"
      99              : #include "tree.h"
     100              : #include "cfghooks.h"
     101              : #include "df.h"
     102              : #include "memmodel.h"
     103              : #include "optabs.h"
     104              : #include "regs.h"
     105              : #include "emit-rtl.h"
     106              : #include "output.h"
     107              : #include "insn-attr.h"
     108              : #include "expr.h"
     109              : #include "tree-pass.h"
     110              : #include "cfgrtl.h"
     111              : #include "cfganal.h"
     112              : #include "cfgbuild.h"
     113              : #include "cfgcleanup.h"
     114              : #include "bb-reorder.h"
     115              : #include "except.h"
     116              : #include "alloc-pool.h"
     117              : #include "fibonacci_heap.h"
     118              : #include "stringpool.h"
     119              : #include "attribs.h"
     120              : #include "common/common-target.h"
     121              : 
     122              : /* The number of rounds.  In most cases there will only be 4 rounds, but
     123              :    when partitioning hot and cold basic blocks into separate sections of
     124              :    the object file there will be an extra round.  */
     125              : #define N_ROUNDS 5
     126              : 
     127              : struct target_bb_reorder default_target_bb_reorder;
     128              : #if SWITCHABLE_TARGET
     129              : struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
     130              : #endif
     131              : 
     132              : #define uncond_jump_length \
     133              :   (this_target_bb_reorder->x_uncond_jump_length)
     134              : 
     135              : /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.  */
     136              : static const int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
     137              : 
     138              : /* Exec thresholds in thousandths (per mille) of the count of bb 0.  */
     139              : static const int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
     140              : 
     141              : /* If edge count is lower than DUPLICATION_THRESHOLD per mille of entry
     142              :    block the edge destination is not duplicated while connecting traces.  */
     143              : #define DUPLICATION_THRESHOLD 100
     144              : 
     145              : typedef fibonacci_heap <long, basic_block_def> bb_heap_t;
     146              : typedef fibonacci_node <long, basic_block_def> bb_heap_node_t;
     147              : 
     148              : /* Structure to hold needed information for each basic block.  */
     149              : struct bbro_basic_block_data
     150              : {
     151              :   /* Which trace is the bb start of (-1 means it is not a start of any).  */
     152              :   int start_of_trace;
     153              : 
     154              :   /* Which trace is the bb end of (-1 means it is not an end of any).  */
     155              :   int end_of_trace;
     156              : 
     157              :   /* Which trace is the bb in?  */
     158              :   int in_trace;
     159              : 
     160              :   /* Which trace was this bb visited in?  */
     161              :   int visited;
     162              : 
     163              :   /* Cached maximum frequency of interesting incoming edges.
     164              :      Minus one means not yet computed.  */
     165              :   int priority;
     166              : 
     167              :   /* Which heap is BB in (if any)?  */
     168              :   bb_heap_t *heap;
     169              : 
     170              :   /* Which heap node is BB in (if any)?  */
     171              :   bb_heap_node_t *node;
     172              : };
     173              : 
     174              : /* The current size of the following dynamic array.  */
     175              : static int array_size;
     176              : 
     177              : /* The array which holds needed information for basic blocks.  */
     178              : static bbro_basic_block_data *bbd;
     179              : 
     180              : /* To avoid frequent reallocation the size of arrays is greater than needed,
     181              :    the number of elements is (not less than) 1.25 * size_wanted.  */
     182              : #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
     183              : 
     184              : /* Free the memory and set the pointer to NULL.  */
     185              : #define FREE(P) (gcc_assert (P), free (P), P = 0)
     186              : 
     187              : /* Structure for holding information about a trace.  */
     188              : struct trace
     189              : {
     190              :   /* First and last basic block of the trace.  */
     191              :   basic_block first, last;
     192              : 
     193              :   /* The round of the STC creation which this trace was found in.  */
     194              :   int round;
     195              : 
     196              :   /* The length (i.e. the number of basic blocks) of the trace.  */
     197              :   int length;
     198              : };
     199              : 
     200              : /* Maximum count of one of the entry blocks.  */
     201              : static profile_count max_entry_count;
     202              : 
     203              : /* Local function prototypes.  */
     204              : static void find_traces_1_round (int, profile_count, struct trace *, int *,
     205              :                                  int, bb_heap_t **, int);
     206              : static basic_block copy_bb (basic_block, edge, basic_block, int);
     207              : static long bb_to_key (basic_block);
     208              : static bool better_edge_p (const_basic_block, const_edge, profile_probability,
     209              :                            profile_count, profile_probability, profile_count,
     210              :                            const_edge);
     211              : static bool copy_bb_p (const_basic_block, int);
     212              : 
     213              : /* Return the trace number in which BB was visited.  */
     214              : 
     215              : static int
     216     38513232 : bb_visited_trace (const_basic_block bb)
     217              : {
     218     38513232 :   gcc_assert (bb->index < array_size);
     219     38513232 :   return bbd[bb->index].visited;
     220              : }
     221              : 
     222              : /* This function marks BB that it was visited in trace number TRACE.  */
     223              : 
     224              : static void
     225     10244252 : mark_bb_visited (basic_block bb, int trace)
     226              : {
     227     10244252 :   bbd[bb->index].visited = trace;
     228     10244252 :   if (bbd[bb->index].heap)
     229              :     {
     230       388520 :       bbd[bb->index].heap->delete_node (bbd[bb->index].node);
     231       388520 :       bbd[bb->index].heap = NULL;
     232       388520 :       bbd[bb->index].node = NULL;
     233              :     }
     234     10244252 : }
     235              : 
     236              : /* Check to see if bb should be pushed into the next round of trace
     237              :    collections or not.  Reasons for pushing the block forward are 1).
     238              :    If the block is cold, we are doing partitioning, and there will be
     239              :    another round (cold partition blocks are not supposed to be
     240              :    collected into traces until the very last round); or 2). There will
     241              :    be another round, and the basic block is not "hot enough" for the
     242              :    current round of trace collection.  */
     243              : 
     244              : static bool
     245      8933824 : push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
     246              :                       profile_count count_th)
     247              : {
     248      8933824 :   bool there_exists_another_round;
     249      8933824 :   bool block_not_hot_enough;
     250              : 
     251      8933824 :   there_exists_another_round = round < number_of_rounds - 1;
     252              : 
     253      8933824 :   block_not_hot_enough = (bb->count < count_th
     254      8933824 :                           || probably_never_executed_bb_p (cfun, bb));
     255              : 
     256      4304815 :   if (there_exists_another_round
     257              :       && block_not_hot_enough)
     258              :     return true;
     259              :   else
     260      5445279 :     return false;
     261              : }
     262              : 
     263              : /* Find the traces for Software Trace Cache.  Chain each trace through
     264              :    RBI()->next.  Store the number of traces to N_TRACES and description of
     265              :    traces to TRACES.  */
     266              : 
     267              : static void
     268       607561 : find_traces (int *n_traces, struct trace *traces)
     269              : {
     270       607561 :   int i;
     271       607561 :   int number_of_rounds;
     272       607561 :   edge e;
     273       607561 :   edge_iterator ei;
     274       607561 :   bb_heap_t *heap = new bb_heap_t (LONG_MIN);
     275              : 
     276              :   /* Add one extra round of trace collection when partitioning hot/cold
     277              :      basic blocks into separate sections.  The last round is for all the
     278              :      cold blocks (and ONLY the cold blocks).  */
     279              : 
     280       607561 :   number_of_rounds = N_ROUNDS - 1;
     281              : 
     282              :   /* Insert entry points of function into heap.  */
     283       607561 :   max_entry_count = profile_count::zero ();
     284      1215122 :   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
     285              :     {
     286       607561 :       bbd[e->dest->index].heap = heap;
     287       607561 :       bbd[e->dest->index].node = heap->insert (bb_to_key (e->dest), e->dest);
     288       607561 :       if (e->dest->count > max_entry_count)
     289       606398 :         max_entry_count = e->dest->count;
     290              :     }
     291              : 
     292              :   /* Find the traces.  */
     293      3037805 :   for (i = 0; i < number_of_rounds; i++)
     294              :     {
     295      2430244 :       profile_count count_threshold;
     296              : 
     297      2430244 :       if (dump_file)
     298           92 :         fprintf (dump_file, "STC - round %d\n", i + 1);
     299              : 
     300      2430244 :       count_threshold = max_entry_count.apply_scale (exec_threshold[i], 1000);
     301              : 
     302      2430244 :       find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
     303              :                            count_threshold, traces, n_traces, i, &heap,
     304              :                            number_of_rounds);
     305              :     }
     306       607561 :   delete heap;
     307              : 
     308       607561 :   if (dump_file)
     309              :     {
     310          115 :       for (i = 0; i < *n_traces; i++)
     311              :         {
     312           92 :           basic_block bb;
     313           92 :           fprintf (dump_file, "Trace %d (round %d):  ", i + 1,
     314           92 :                    traces[i].round + 1);
     315           92 :           for (bb = traces[i].first;
     316          188 :                bb != traces[i].last;
     317           96 :                bb = (basic_block) bb->aux)
     318              :             {
     319           96 :               fprintf (dump_file, "%d [", bb->index);
     320           96 :               bb->count.dump (dump_file);
     321           96 :               fprintf (dump_file, "] ");
     322              :             }
     323           92 :           fprintf (dump_file, "%d [", bb->index);
     324           92 :           bb->count.dump (dump_file);
     325           92 :           fprintf (dump_file, "]\n");
     326              :         }
     327           23 :       fflush (dump_file);
     328              :     }
     329       607561 : }
     330              : 
     331              : /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
     332              :    (with sequential number TRACE_N).  */
     333              : 
     334              : static basic_block
     335       166174 : rotate_loop (edge back_edge, struct trace *trace, int trace_n)
     336              : {
     337       166174 :   basic_block bb;
     338              : 
     339              :   /* Information about the best end (end after rotation) of the loop.  */
     340       166174 :   basic_block best_bb = NULL;
     341       166174 :   edge best_edge = NULL;
     342       166174 :   profile_count best_count = profile_count::uninitialized ();
     343              :   /* The best edge is preferred when its destination is not visited yet
     344              :      or is a start block of some trace.  */
     345       166174 :   bool is_preferred = false;
     346              : 
     347              :   /* Find the most frequent edge that goes out from current trace.  */
     348       166174 :   bb = back_edge->dest;
     349       638786 :   do
     350              :     {
     351       638786 :       edge e;
     352       638786 :       edge_iterator ei;
     353              : 
     354      1794644 :       FOR_EACH_EDGE (e, ei, bb->succs)
     355      1155858 :         if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     356      1155858 :             && bb_visited_trace (e->dest) != trace_n
     357       466304 :             && (e->flags & EDGE_CAN_FALLTHRU)
     358      1585761 :             && !(e->flags & EDGE_COMPLEX))
     359              :         {
     360       429903 :           if (is_preferred)
     361              :             {
     362              :               /* The best edge is preferred.  */
     363       261007 :               if (!bb_visited_trace (e->dest)
     364       261007 :                   || bbd[e->dest->index].start_of_trace >= 0)
     365              :                 {
     366              :                   /* The current edge E is also preferred.  */
     367       257096 :                   if (e->count () > best_count)
     368              :                     {
     369        65184 :                       best_count = e->count ();
     370        65184 :                       best_edge = e;
     371        65184 :                       best_bb = bb;
     372              :                     }
     373              :                 }
     374              :             }
     375              :           else
     376              :             {
     377       168896 :               if (!bb_visited_trace (e->dest)
     378       168896 :                   || bbd[e->dest->index].start_of_trace >= 0)
     379              :                 {
     380              :                   /* The current edge E is preferred.  */
     381       164846 :                   is_preferred = true;
     382       164846 :                   best_count = e->count ();
     383       164846 :                   best_edge = e;
     384       164846 :                   best_bb = bb;
     385              :                 }
     386              :               else
     387              :                 {
     388         4050 :                   if (!best_edge || e->count () > best_count)
     389              :                     {
     390         3378 :                       best_count = e->count ();
     391         3378 :                       best_edge = e;
     392         3378 :                       best_bb = bb;
     393              :                     }
     394              :                 }
     395              :             }
     396              :         }
     397       638786 :       bb = (basic_block) bb->aux;
     398              :     }
     399       638786 :   while (bb != back_edge->dest);
     400              : 
     401       166174 :   if (best_bb)
     402              :     {
     403              :       /* Rotate the loop so that the BEST_EDGE goes out from the last block of
     404              :          the trace.  */
     405       166082 :       if (back_edge->dest == trace->first)
     406              :         {
     407         6172 :           trace->first = (basic_block) best_bb->aux;
     408              :         }
     409              :       else
     410              :         {
     411              :           basic_block prev_bb;
     412              : 
     413              :           for (prev_bb = trace->first;
     414       483698 :                prev_bb->aux != back_edge->dest;
     415              :                prev_bb = (basic_block) prev_bb->aux)
     416              :             ;
     417       159910 :           prev_bb->aux = best_bb->aux;
     418              : 
     419              :           /* Try to get rid of uncond jump to cond jump.  */
     420       159910 :           if (single_succ_p (prev_bb))
     421              :             {
     422       136963 :               basic_block header = single_succ (prev_bb);
     423              : 
     424              :               /* Duplicate HEADER if it is a small block containing cond jump
     425              :                  in the end.  */
     426       264838 :               if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
     427       136963 :                   && !CROSSING_JUMP_P (BB_END (header)))
     428            0 :                 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
     429              :             }
     430              :         }
     431              :     }
     432              :   else
     433              :     {
     434              :       /* We have not found suitable loop tail so do no rotation.  */
     435           92 :       best_bb = back_edge->src;
     436              :     }
     437       166174 :   best_bb->aux = NULL;
     438       166174 :   return best_bb;
     439              : }
     440              : 
     441              : /* One round of finding traces.  Find traces for BRANCH_TH and EXEC_TH i.e. do
     442              :    not include basic blocks whose probability is lower than BRANCH_TH or whose
     443              :    count is lower than EXEC_TH into traces (or whose count is lower than
     444              :    COUNT_TH).  Store the new traces into TRACES and modify the number of
     445              :    traces *N_TRACES.  Set the round (which the trace belongs to) to ROUND.
     446              :    The function expects starting basic blocks to be in *HEAP and will delete
     447              :    *HEAP and store starting points for the next round into new *HEAP.  */
     448              : 
     449              : static void
     450      2430244 : find_traces_1_round (int branch_th, profile_count count_th,
     451              :                      struct trace *traces, int *n_traces, int round,
     452              :                      bb_heap_t **heap, int number_of_rounds)
     453              : {
     454              :   /* Heap for discarded basic blocks which are possible starting points for
     455              :      the next round.  */
     456      2430244 :   bb_heap_t *new_heap = new bb_heap_t (LONG_MIN);
     457      2430244 :   bool for_size = optimize_function_for_size_p (cfun);
     458              : 
     459      8483444 :   while (!(*heap)->empty ())
     460              :     {
     461      6053200 :       basic_block bb;
     462      6053200 :       struct trace *trace;
     463      6053200 :       edge best_edge, e;
     464      6053200 :       long key;
     465      6053200 :       edge_iterator ei;
     466              : 
     467      6053200 :       bb = (*heap)->extract_min ();
     468      6053200 :       bbd[bb->index].heap = NULL;
     469      6053200 :       bbd[bb->index].node = NULL;
     470              : 
     471      6053200 :       if (dump_file)
     472          108 :         fprintf (dump_file, "Getting bb %d\n", bb->index);
     473              : 
     474              :       /* If the BB's count is too low, send BB to the next round.  When
     475              :          partitioning hot/cold blocks into separate sections, make sure all
     476              :          the cold blocks (and ONLY the cold blocks) go into the (extra) final
     477              :          round.  When optimizing for size, do not push to next round.  */
     478              : 
     479      6053200 :       if (!for_size
     480      6053200 :           && push_to_next_round_p (bb, round, number_of_rounds,
     481              :                                    count_th))
     482              :         {
     483      1513712 :           int key = bb_to_key (bb);
     484      1513712 :           bbd[bb->index].heap = new_heap;
     485      1513712 :           bbd[bb->index].node = new_heap->insert (key, bb);
     486              : 
     487      1513712 :           if (dump_file)
     488           16 :             fprintf (dump_file,
     489              :                      "  Possible start point of next round: %d (key: %d)\n",
     490              :                      bb->index, key);
     491      1513712 :           continue;
     492      1513712 :         }
     493              : 
     494      4539488 :       trace = traces + *n_traces;
     495      4539488 :       trace->first = bb;
     496      4539488 :       trace->round = round;
     497      4539488 :       trace->length = 0;
     498      4539488 :       bbd[bb->index].in_trace = *n_traces;
     499      4539488 :       (*n_traces)++;
     500              : 
     501      9982793 :       do
     502              :         {
     503      9982793 :           bool ends_in_call;
     504              : 
     505              :           /* The probability and count of the best edge.  */
     506      9982793 :           profile_probability best_prob = profile_probability::uninitialized ();
     507      9982793 :           profile_count best_count = profile_count::uninitialized ();
     508              : 
     509      9982793 :           best_edge = NULL;
     510      9982793 :           mark_bb_visited (bb, *n_traces);
     511      9982793 :           trace->length++;
     512              : 
     513      9982793 :           if (dump_file)
     514          188 :             fprintf (dump_file, "Basic block %d was visited in trace %d\n",
     515              :                      bb->index, *n_traces);
     516              : 
     517      9982793 :           ends_in_call = block_ends_with_call_p (bb);
     518              : 
     519              :           /* Select the successor that will be placed after BB.  */
     520     25027654 :           FOR_EACH_EDGE (e, ei, bb->succs)
     521              :             {
     522     15044861 :               gcc_assert (!(e->flags & EDGE_FAKE));
     523              : 
     524     15044861 :               if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
     525      8328941 :                 continue;
     526              : 
     527     14334993 :               if (bb_visited_trace (e->dest)
     528     14334993 :                   && bb_visited_trace (e->dest) != *n_traces)
     529      2662378 :                 continue;
     530              : 
     531              :               /* If partitioning hot/cold basic blocks, don't consider edges
     532              :                  that cross section boundaries.  */
     533     11672615 :               if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
     534       410181 :                 continue;
     535              : 
     536     11262434 :               profile_probability prob = e->probability;
     537     11262434 :               profile_count count = e->dest->count;
     538              : 
     539              :               /* The only sensible preference for a call instruction is the
     540              :                  fallthru edge.  Don't bother selecting anything else.  */
     541     11262434 :               if (ends_in_call)
     542              :                 {
     543      1070205 :                   if (e->flags & EDGE_CAN_FALLTHRU)
     544              :                     {
     545       555591 :                       best_edge = e;
     546       555591 :                       best_prob = prob;
     547       555591 :                       best_count = count;
     548              :                     }
     549      1070205 :                   continue;
     550              :                 }
     551              : 
     552              :               /* Edge that cannot be fallthru or improbable or infrequent
     553              :                  successor (i.e. it is unsuitable successor).  When optimizing
     554              :                  for size, ignore the probability and count.  */
     555      9997576 :               if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
     556      9935015 :                   || !prob.initialized_p ()
     557     20125693 :                   || ((prob.to_reg_br_prob_base () < branch_th
     558     10192229 :                       || e->count () < count_th) && (!for_size)))
     559      3476309 :                 continue;
     560              : 
     561      6715920 :               if (better_edge_p (bb, e, prob, count, best_prob, best_count,
     562              :                                  best_edge))
     563              :                 {
     564      6150368 :                   best_edge = e;
     565      6150368 :                   best_prob = prob;
     566      6150368 :                   best_count = count;
     567              :                 }
     568              :             }
     569              : 
     570              :           /* If the best destination has multiple predecessors and can be
     571              :              duplicated cheaper than a jump, don't allow it to be added to
     572              :              a trace; we'll duplicate it when connecting the traces later.
     573              :              However, we need to check that this duplication wouldn't leave
     574              :              the best destination with only crossing predecessors, because
     575              :              this would change its effective partition from hot to cold.  */
     576      9982793 :           if (best_edge
     577      6152310 :               && EDGE_COUNT (best_edge->dest->preds) >= 2
     578     12598773 :               && copy_bb_p (best_edge->dest, 0))
     579              :             {
     580        72543 :               bool only_crossing_preds = true;
     581        72543 :               edge e;
     582        72543 :               edge_iterator ei;
     583        98810 :               FOR_EACH_EDGE (e, ei, best_edge->dest->preds)
     584        98789 :                 if (e != best_edge && !(e->flags & EDGE_CROSSING))
     585              :                   {
     586              :                     only_crossing_preds = false;
     587              :                     break;
     588              :                   }
     589        72543 :               if (!only_crossing_preds)
     590        72522 :                 best_edge = NULL;
     591              :             }
     592              : 
     593              :           /* If the best destination has multiple successors or predecessors,
     594              :              don't allow it to be added when optimizing for size.  This makes
     595              :              sure predecessors with smaller index are handled before the best
     596              :              destination.  It breaks long trace and reduces long jumps.
     597              : 
     598              :              Take if-then-else as an example.
     599              :                 A
     600              :                / \
     601              :               B   C
     602              :                \ /
     603              :                 D
     604              :              If we do not remove the best edge B->D/C->D, the final order might
     605              :              be A B D ... C.  C is at the end of the program.  If D's successors
     606              :              and D are complicated, might need long jumps for A->C and C->D.
     607              :              Similar issue for order: A C D ... B.
     608              : 
     609              :              After removing the best edge, the final result will be ABCD/ ACBD.
     610              :              It does not add jump compared with the previous order.  But it
     611              :              reduces the possibility of long jumps.  */
     612      9982793 :           if (best_edge && for_size
     613      9982793 :               && (EDGE_COUNT (best_edge->dest->succs) > 1
     614       138420 :                  || EDGE_COUNT (best_edge->dest->preds) > 1))
     615              :             best_edge = NULL;
     616              : 
     617              :           /* Add all non-selected successors to the heaps.  */
     618     25027654 :           FOR_EACH_EDGE (e, ei, bb->succs)
     619              :             {
     620     24341973 :               if (e == best_edge
     621      9167597 :                   || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
     622     23502590 :                   || bb_visited_trace (e->dest))
     623      9297112 :                 continue;
     624              : 
     625      5747749 :               key = bb_to_key (e->dest);
     626              : 
     627      5747749 :               if (bbd[e->dest->index].heap)
     628              :                 {
     629              :                   /* E->DEST is already in some heap.  */
     630      1427302 :                   if (key != bbd[e->dest->index].node->get_key ())
     631              :                     {
     632            0 :                       if (dump_file)
     633              :                         {
     634            0 :                           fprintf (dump_file,
     635              :                                    "Changing key for bb %d from %ld to %ld.\n",
     636              :                                    e->dest->index,
     637            0 :                                    (long) bbd[e->dest->index].node->get_key (),
     638              :                                    key);
     639              :                         }
     640            0 :                       bbd[e->dest->index].heap->replace_key
     641            0 :                         (bbd[e->dest->index].node, key);
     642              :                     }
     643              :                 }
     644              :               else
     645              :                 {
     646      4320447 :                   bb_heap_t *which_heap = *heap;
     647              : 
     648      4320447 :                   profile_probability prob = e->probability;
     649              : 
     650      4320447 :                   if (!(e->flags & EDGE_CAN_FALLTHRU)
     651      4001483 :                       || (e->flags & EDGE_COMPLEX)
     652      3939872 :                       || !prob.initialized_p ()
     653      3938494 :                       || prob.to_reg_br_prob_base () < branch_th
     654      8321930 :                       || e->count () < count_th)
     655              :                     {
     656              :                       /* When partitioning hot/cold basic blocks, make sure
     657              :                          the cold blocks (and only the cold blocks) all get
     658              :                          pushed to the last round of trace collection.  When
     659              :                          optimizing for size, do not push to next round.  */
     660              : 
     661      3243071 :                       if (!for_size && push_to_next_round_p (e->dest, round,
     662              :                                                              number_of_rounds,
     663              :                                                              count_th))
     664              :                         which_heap = new_heap;
     665              :                     }
     666              : 
     667      4320447 :                   bbd[e->dest->index].heap = which_heap;
     668      4320447 :                   bbd[e->dest->index].node = which_heap->insert (key, e->dest);
     669              : 
     670      4320447 :                   if (dump_file)
     671              :                     {
     672           87 :                       fprintf (dump_file,
     673              :                                "  Possible start of %s round: %d (key: %ld)\n",
     674              :                                (which_heap == new_heap) ? "next" : "this",
     675           87 :                                e->dest->index, (long) key);
     676              :                     }
     677              : 
     678              :                 }
     679              :             }
     680              : 
     681      9982793 :           if (best_edge) /* Suitable successor was found.  */
     682              :             {
     683      5877264 :               if (bb_visited_trace (best_edge->dest) == *n_traces)
     684              :                 {
     685              :                   /* We do nothing with one basic block loops.  */
     686       433959 :                   if (best_edge->dest != bb)
     687              :                     {
     688       622653 :                       if (best_edge->count ()
     689       207551 :                           > best_edge->dest->count.apply_scale (4, 5))
     690              :                         {
     691              :                           /* The loop has at least 4 iterations.  If the loop
     692              :                              header is not the first block of the function
     693              :                              we can rotate the loop.  */
     694              : 
     695       166231 :                           if (best_edge->dest
     696       166231 :                               != ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
     697              :                             {
     698       166174 :                               if (dump_file)
     699              :                                 {
     700            0 :                                   fprintf (dump_file,
     701              :                                            "Rotating loop %d - %d\n",
     702              :                                            best_edge->dest->index, bb->index);
     703              :                                 }
     704       166174 :                               bb->aux = best_edge->dest;
     705       166174 :                               bbd[best_edge->dest->index].in_trace =
     706       166174 :                                                              (*n_traces) - 1;
     707       166174 :                               bb = rotate_loop (best_edge, trace, *n_traces);
     708              :                             }
     709              :                         }
     710              :                       else
     711              :                         {
     712              :                           /* The loop has less than 4 iterations.  */
     713              : 
     714        41320 :                           if (single_succ_p (bb)
     715        54082 :                               && copy_bb_p (best_edge->dest,
     716              :                                             optimize_edge_for_speed_p
     717        12762 :                                             (best_edge)))
     718              :                             {
     719         7059 :                               bb = copy_bb (best_edge->dest, best_edge, bb,
     720              :                                             *n_traces);
     721         7059 :                               trace->length++;
     722              :                             }
     723              :                         }
     724              :                     }
     725              : 
     726              :                   /* Terminate the trace.  */
     727       433959 :                   break;
     728              :                 }
     729              :               else
     730              :                 {
     731              :                   /* Check for a situation
     732              : 
     733              :                     A
     734              :                    /|
     735              :                   B |
     736              :                    \|
     737              :                     C
     738              : 
     739              :                   where
     740              :                   AB->count () + BC->count () >= AC->count ().
     741              :                   (i.e. 2 * B->count >= AC->count )
     742              :                   Best ordering is then A B C.
     743              : 
     744              :                   When optimizing for size, A B C is always the best order.
     745              : 
     746              :                   This situation is created for example by:
     747              : 
     748              :                   if (A) B;
     749              :                   C;
     750              : 
     751              :                   */
     752              : 
     753     14978923 :                   FOR_EACH_EDGE (e, ei, bb->succs)
     754      9549694 :                     if (e != best_edge
     755      4118217 :                         && (e->flags & EDGE_CAN_FALLTHRU)
     756      3607746 :                         && !(e->flags & EDGE_COMPLEX)
     757      3607746 :                         && !bb_visited_trace (e->dest)
     758     11222220 :                         && single_pred_p (e->dest)
     759      1686602 :                         && !(e->flags & EDGE_CROSSING)
     760      1640516 :                         && single_succ_p (e->dest)
     761      1001225 :                         && (single_succ_edge (e->dest)->flags
     762      1001225 :                             & EDGE_CAN_FALLTHRU)
     763       881146 :                         && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
     764       881146 :                         && single_succ (e->dest) == best_edge->dest
     765      9846639 :                         && (e->dest->count * 2
     766      9846639 :                             >= best_edge->count () || for_size))
     767              :                       {
     768        14076 :                         best_edge = e;
     769        14076 :                         if (dump_file)
     770            0 :                           fprintf (dump_file, "Selecting BB %d\n",
     771            0 :                                    best_edge->dest->index);
     772              :                         break;
     773              :                       }
     774              : 
     775      5443305 :                   bb->aux = best_edge->dest;
     776      5443305 :                   bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
     777      5443305 :                   bb = best_edge->dest;
     778              :                 }
     779              :             }
     780              :         }
     781      9548834 :       while (best_edge);
     782      4539488 :       trace->last = bb;
     783      4539488 :       bbd[trace->first->index].start_of_trace = *n_traces - 1;
     784      4539488 :       if (bbd[trace->last->index].end_of_trace != *n_traces - 1)
     785              :         {
     786      4539488 :           bbd[trace->last->index].end_of_trace = *n_traces - 1;
     787              :           /* Update the cached maximum frequency for interesting predecessor
     788              :              edges for successors of the new trace end.  */
     789     10067539 :           FOR_EACH_EDGE (e, ei, trace->last->succs)
     790      5528051 :             if (EDGE_FREQUENCY (e) > bbd[e->dest->index].priority)
     791      4208707 :               bbd[e->dest->index].priority = EDGE_FREQUENCY (e);
     792              :         }
     793              : 
     794              :       /* The trace is terminated so we have to recount the keys in heap
     795              :          (some block can have a lower key because now one of its predecessors
     796              :          is an end of the trace).  */
     797     10067539 :       FOR_EACH_EDGE (e, ei, bb->succs)
     798              :         {
     799      8987085 :           if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
     800      5528051 :               || bb_visited_trace (e->dest))
     801      3459034 :             continue;
     802              : 
     803      2069017 :           if (bbd[e->dest->index].heap)
     804              :             {
     805      2069017 :               key = bb_to_key (e->dest);
     806      2069017 :               if (key != bbd[e->dest->index].node->get_key ())
     807              :                 {
     808      1331755 :                   if (dump_file)
     809              :                     {
     810           45 :                       fprintf (dump_file,
     811              :                                "Changing key for bb %d from %ld to %ld.\n",
     812              :                                e->dest->index,
     813           45 :                                (long) bbd[e->dest->index].node->get_key (), key);
     814              :                     }
     815      1331755 :                   bbd[e->dest->index].heap->replace_key
     816      1331755 :                     (bbd[e->dest->index].node, key);
     817              :                 }
     818              :             }
     819              :         }
     820              :     }
     821              : 
     822      2430244 :   delete (*heap);
     823              : 
     824              :   /* "Return" the new heap.  */
     825      2430244 :   *heap = new_heap;
     826      2430244 : }
     827              : 
     828              : /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
     829              :    it to trace after BB, mark OLD_BB visited and update pass' data structures
     830              :    (TRACE is a number of trace which OLD_BB is duplicated to).  */
     831              : 
     832              : static basic_block
     833       261459 : copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
     834              : {
     835       261459 :   basic_block new_bb;
     836              : 
     837       261459 :   new_bb = duplicate_block (old_bb, e, bb);
     838       261459 :   BB_COPY_PARTITION (new_bb, old_bb);
     839              : 
     840       261459 :   gcc_assert (e->dest == new_bb);
     841              : 
     842       261459 :   if (dump_file)
     843            0 :     fprintf (dump_file,
     844              :              "Duplicated bb %d (created bb %d)\n",
     845              :              old_bb->index, new_bb->index);
     846              : 
     847       261459 :   if (new_bb->index >= array_size
     848       261142 :       || last_basic_block_for_fn (cfun) > array_size)
     849              :     {
     850          317 :       int i;
     851          317 :       int new_size;
     852              : 
     853          317 :       new_size = MAX (last_basic_block_for_fn (cfun), new_bb->index + 1);
     854          317 :       new_size = GET_ARRAY_SIZE (new_size);
     855          317 :       bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
     856        23542 :       for (i = array_size; i < new_size; i++)
     857              :         {
     858        23225 :           bbd[i].start_of_trace = -1;
     859        23225 :           bbd[i].end_of_trace = -1;
     860        23225 :           bbd[i].in_trace = -1;
     861        23225 :           bbd[i].visited = 0;
     862        23225 :           bbd[i].priority = -1;
     863        23225 :           bbd[i].heap = NULL;
     864        23225 :           bbd[i].node = NULL;
     865              :         }
     866          317 :       array_size = new_size;
     867              : 
     868          317 :       if (dump_file)
     869              :         {
     870            0 :           fprintf (dump_file,
     871              :                    "Growing the dynamic array to %d elements.\n",
     872              :                    array_size);
     873              :         }
     874              :     }
     875              : 
     876       261459 :   gcc_assert (!bb_visited_trace (e->dest));
     877       261459 :   mark_bb_visited (new_bb, trace);
     878       261459 :   new_bb->aux = bb->aux;
     879       261459 :   bb->aux = new_bb;
     880              : 
     881       261459 :   bbd[new_bb->index].in_trace = trace;
     882              : 
     883       261459 :   return new_bb;
     884              : }
     885              : 
     886              : /* Compute and return the key (for the heap) of the basic block BB.  */
     887              : 
     888              : static long
     889      9938039 : bb_to_key (basic_block bb)
     890              : {
     891      9938039 :   edge e;
     892      9938039 :   edge_iterator ei;
     893              : 
     894              :   /* Use index as key to align with its original order.  */
     895      9938039 :   if (optimize_function_for_size_p (cfun))
     896       621616 :     return bb->index;
     897              : 
     898              :   /* Do not start in probably never executed blocks.  */
     899              : 
     900      9316423 :   if (BB_PARTITION (bb) == BB_COLD_PARTITION
     901      9316423 :       || probably_never_executed_bb_p (cfun, bb))
     902              :     return BB_FREQ_MAX;
     903              : 
     904              :   /* Prefer blocks whose predecessor is an end of some trace
     905              :      or whose predecessor edge is EDGE_DFS_BACK.  */
     906      7231079 :   int priority = bbd[bb->index].priority;
     907      7231079 :   if (priority == -1)
     908              :     {
     909      4099729 :       priority = 0;
     910      9998850 :       FOR_EACH_EDGE (e, ei, bb->preds)
     911              :         {
     912      5899121 :           if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     913      5328250 :                && bbd[e->src->index].end_of_trace >= 0)
     914      5899121 :               || (e->flags & EDGE_DFS_BACK))
     915              :             {
     916        62377 :               int edge_freq = EDGE_FREQUENCY (e);
     917              : 
     918        62377 :               if (edge_freq > priority)
     919      5899121 :                 priority = edge_freq;
     920              :             }
     921              :         }
     922      4099729 :       bbd[bb->index].priority = priority;
     923              :     }
     924              : 
     925      7231079 :   if (priority)
     926              :     /* The block with priority should have significantly lower key.  */
     927      1602938 :     return -(100 * BB_FREQ_MAX + 100 * priority + bb->count.to_frequency (cfun));
     928              : 
     929      5628141 :   return -bb->count.to_frequency (cfun);
     930              : }
     931              : 
     932              : /* Return true when the edge E from basic block BB is better than the temporary
     933              :    best edge (details are in function).  The probability of edge E is PROB. The
     934              :    count of the successor is COUNT.  The current best probability is
     935              :    BEST_PROB, the best count is BEST_COUNT.
     936              :    The edge is considered to be equivalent when PROB does not differ much from
     937              :    BEST_PROB; similarly for count.  */
     938              : 
     939              : static bool
     940      6715920 : better_edge_p (const_basic_block bb, const_edge e, profile_probability prob,
     941              :                profile_count count, profile_probability best_prob,
     942              :                profile_count best_count, const_edge cur_best_edge)
     943              : {
     944      6715920 :   bool is_better_edge;
     945              : 
     946              :   /* The BEST_* values do not have to be best, but can be a bit smaller than
     947              :      maximum values.  */
     948      6715920 :   profile_probability diff_prob = best_prob / 10;
     949              : 
     950              :   /* The smaller one is better to keep the original order.  */
     951      6715920 :   if (optimize_function_for_size_p (cfun))
     952       406820 :     return !cur_best_edge
     953       406820 :            || cur_best_edge->dest->index > e->dest->index;
     954              : 
     955              :   /* Those edges are so expensive that continuing a trace is not useful
     956              :      performance wise.  */
     957      6309100 :   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
     958              :     return false;
     959              : 
     960     12618200 :   if (prob > best_prob + diff_prob
     961      5968384 :       || (!best_prob.initialized_p ()
     962     10634454 :           && prob > profile_probability::guessed_never ()))
     963              :     /* The edge has higher probability than the temporary best edge.  */
     964              :     is_better_edge = true;
     965       989645 :   else if (prob < best_prob - diff_prob)
     966              :     /* The edge has lower probability than the temporary best edge.  */
     967              :     is_better_edge = false;
     968              :   else
     969              :     {
     970       319261 :       profile_count diff_count = best_count / 10;
     971       380520 :       if (count < best_count - diff_count
     972       319261 :           || (!best_count.initialized_p ()
     973         1179 :               && count.nonzero_p ()))
     974              :         /* The edge and the temporary best edge  have almost equivalent
     975              :            probabilities.  The higher countuency of a successor now means
     976              :            that there is another edge going into that successor.
     977              :            This successor has lower countuency so it is better.  */
     978              :         is_better_edge = true;
     979       256823 :       else if (count > best_count + diff_count)
     980              :         /* This successor has higher countuency so it is worse.  */
     981              :         is_better_edge = false;
     982       155554 :       else if (e->dest->prev_bb == bb)
     983              :         /* The edges have equivalent probabilities and the successors
     984              :            have equivalent frequencies.  Select the previous successor.  */
     985              :         is_better_edge = true;
     986              :       else
     987       319261 :         is_better_edge = false;
     988              :     }
     989              : 
     990              :   return is_better_edge;
     991              : }
     992              : 
     993              : /* Return true when the edge E is better than the temporary best edge
     994              :    CUR_BEST_EDGE.  If SRC_INDEX_P is true, the function compares the src bb of
     995              :    E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
     996              :    BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
     997              :    TRACES record the information about traces.
     998              :    When optimizing for size, the edge with smaller index is better.
     999              :    When optimizing for speed, the edge with bigger probability or longer trace
    1000              :    is better.  */
    1001              : 
    1002              : static bool
    1003      1921832 : connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
    1004              :                        const_edge cur_best_edge, struct trace *traces)
    1005              : {
    1006      1921832 :   int e_index;
    1007      1921832 :   int b_index;
    1008      1921832 :   bool is_better_edge;
    1009              : 
    1010      1921832 :   if (!cur_best_edge)
    1011              :     return true;
    1012              : 
    1013       486583 :   if (optimize_function_for_size_p (cfun))
    1014              :     {
    1015        48788 :       e_index = src_index_p ? e->src->index : e->dest->index;
    1016        48788 :       b_index = src_index_p ? cur_best_edge->src->index
    1017        46274 :                               : cur_best_edge->dest->index;
    1018              :       /* The smaller one is better to keep the original order.  */
    1019        48788 :       return b_index > e_index;
    1020              :     }
    1021              : 
    1022       437795 :   if (src_index_p)
    1023              :     {
    1024        42099 :       e_index = e->src->index;
    1025              : 
    1026              :       /* We are looking for predecessor, so probabilities are not that
    1027              :          informative.  We do not want to connect A to B because A has
    1028              :          only one successor (probability is 100%) while there is edge
    1029              :          A' to B where probability is 90% but which is much more frequent.  */
    1030        42099 :       if (e->count () > cur_best_edge->count ())
    1031              :         /* The edge has higher probability than the temporary best edge.  */
    1032              :         is_better_edge = true;
    1033        33634 :       else if (e->count () < cur_best_edge->count ())
    1034              :         /* The edge has lower probability than the temporary best edge.  */
    1035              :         is_better_edge = false;
    1036        19127 :       else if (e->probability > cur_best_edge->probability)
    1037              :         /* The edge has higher probability than the temporary best edge.  */
    1038              :         is_better_edge = true;
    1039        18301 :       else if (e->probability < cur_best_edge->probability)
    1040              :         /* The edge has lower probability than the temporary best edge.  */
    1041              :         is_better_edge = false;
    1042        16308 :       else if (traces[bbd[e_index].end_of_trace].length > best_len)
    1043              :         /* The edge and the temporary best edge have equivalent probabilities.
    1044              :            The edge with longer trace is better.  */
    1045              :         is_better_edge = true;
    1046              :       else
    1047              :         is_better_edge = false;
    1048              :     }
    1049              :   else
    1050              :     {
    1051       395696 :       e_index = e->dest->index;
    1052              : 
    1053       395696 :       if (e->probability > cur_best_edge->probability)
    1054              :         /* The edge has higher probability than the temporary best edge.  */
    1055              :         is_better_edge = true;
    1056       251534 :       else if (e->probability < cur_best_edge->probability)
    1057              :         /* The edge has lower probability than the temporary best edge.  */
    1058              :         is_better_edge = false;
    1059       118830 :       else if (traces[bbd[e_index].start_of_trace].length > best_len)
    1060              :         /* The edge and the temporary best edge have equivalent probabilities.
    1061              :            The edge with longer trace is better.  */
    1062              :         is_better_edge = true;
    1063              :       else
    1064              :         is_better_edge = false;
    1065              :     }
    1066              : 
    1067              :   return is_better_edge;
    1068              : }
    1069              : 
    1070              : /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
    1071              : 
    1072              : static void
    1073       607561 : connect_traces (int n_traces, struct trace *traces)
    1074              : {
    1075       607561 :   int i;
    1076       607561 :   bool *connected;
    1077       607561 :   bool two_passes;
    1078       607561 :   int last_trace;
    1079       607561 :   int current_pass;
    1080       607561 :   int current_partition;
    1081       607561 :   profile_count count_threshold;
    1082       607561 :   bool for_size = optimize_function_for_size_p (cfun);
    1083              : 
    1084       607561 :   count_threshold = max_entry_count.apply_scale (DUPLICATION_THRESHOLD, 1000);
    1085              : 
    1086       607561 :   connected = XCNEWVEC (bool, n_traces);
    1087       607561 :   last_trace = -1;
    1088       607561 :   current_pass = 1;
    1089       607561 :   current_partition = BB_PARTITION (traces[0].first);
    1090       607561 :   two_passes = false;
    1091              : 
    1092       607561 :   if (crtl->has_bb_partition)
    1093       581530 :     for (i = 0; i < n_traces && !two_passes; i++)
    1094       516168 :       if (BB_PARTITION (traces[0].first)
    1095       516168 :           != BB_PARTITION (traces[i].first))
    1096        65362 :         two_passes = true;
    1097              : 
    1098      5833980 :   for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
    1099              :     {
    1100      5226419 :       int t = i;
    1101      5226419 :       int t2;
    1102      5226419 :       edge e, best;
    1103      5226419 :       int best_len;
    1104              : 
    1105      5226419 :       if (i >= n_traces)
    1106              :         {
    1107        65362 :           gcc_assert (two_passes && current_pass == 1);
    1108        65362 :           i = 0;
    1109        65362 :           t = i;
    1110        65362 :           current_pass = 2;
    1111        65362 :           if (current_partition == BB_HOT_PARTITION)
    1112              :             current_partition = BB_COLD_PARTITION;
    1113              :           else
    1114            0 :             current_partition = BB_HOT_PARTITION;
    1115              :         }
    1116              : 
    1117      5226419 :       if (connected[t])
    1118      2156567 :         continue;
    1119              : 
    1120      3251525 :       if (two_passes
    1121       664621 :           && BB_PARTITION (traces[t].first) != current_partition)
    1122       181673 :         continue;
    1123              : 
    1124      3069852 :       connected[t] = true;
    1125              : 
    1126              :       /* Find the predecessor traces.  */
    1127      3176802 :       for (t2 = t; t2 > 0;)
    1128              :         {
    1129      2569241 :           edge_iterator ei;
    1130      2569241 :           best = NULL;
    1131      2569241 :           best_len = 0;
    1132      6466267 :           FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
    1133              :             {
    1134      3897026 :               int si = e->src->index;
    1135              : 
    1136      3897026 :               if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1137      3897026 :                   && (e->flags & EDGE_CAN_FALLTHRU)
    1138      3106392 :                   && !(e->flags & EDGE_COMPLEX)
    1139      3050419 :                   && bbd[si].end_of_trace >= 0
    1140       539042 :                   && !connected[bbd[si].end_of_trace]
    1141       151580 :                   && (BB_PARTITION (e->src) == current_partition)
    1142      4048589 :                   && connect_better_edge_p (e, true, best_len, best, traces))
    1143              :                 {
    1144       117144 :                   best = e;
    1145       117144 :                   best_len = traces[bbd[si].end_of_trace].length;
    1146              :                 }
    1147              :             }
    1148      2569241 :           if (best)
    1149              :             {
    1150       106950 :               best->src->aux = best->dest;
    1151       106950 :               t2 = bbd[best->src->index].end_of_trace;
    1152       106950 :               connected[t2] = true;
    1153              : 
    1154       106950 :               if (dump_file)
    1155              :                 {
    1156            2 :                   fprintf (dump_file, "Connection: %d %d\n",
    1157              :                            best->src->index, best->dest->index);
    1158              :                 }
    1159              :             }
    1160              :           else
    1161              :             break;
    1162              :         }
    1163              : 
    1164      3069852 :       if (last_trace >= 0)
    1165      2462291 :         traces[last_trace].last->aux = traces[t2].first;
    1166      3069852 :       last_trace = t;
    1167              : 
    1168              :       /* Find the successor traces.  */
    1169      5795224 :       while (1)
    1170              :         {
    1171              :           /* Find the continuation of the chain.  */
    1172      4432538 :           edge_iterator ei;
    1173      4432538 :           best = NULL;
    1174      4432538 :           best_len = 0;
    1175      9812932 :           FOR_EACH_EDGE (e, ei, traces[t].last->succs)
    1176              :             {
    1177      5380394 :               int di = e->dest->index;
    1178              : 
    1179      5380394 :               if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
    1180      4670526 :                   && (e->flags & EDGE_CAN_FALLTHRU)
    1181      4364458 :                   && !(e->flags & EDGE_COMPLEX)
    1182      4296523 :                   && bbd[di].start_of_trace >= 0
    1183      2331395 :                   && !connected[bbd[di].start_of_trace]
    1184      1789238 :                   && (BB_PARTITION (e->dest) == current_partition)
    1185      7150663 :                   && connect_better_edge_p (e, false, best_len, best, traces))
    1186              :                 {
    1187      1542224 :                   best = e;
    1188      1542224 :                   best_len = traces[bbd[di].start_of_trace].length;
    1189              :                 }
    1190              :             }
    1191              : 
    1192      4432538 :           if (for_size)
    1193              :             {
    1194       279150 :               if (!best)
    1195              :                 /* Stop finding the successor traces.  */
    1196              :                 break;
    1197              : 
    1198              :               /* It is OK to connect block n with block n + 1 or a block
    1199              :                  before n.  For others, only connect to the loop header.  */
    1200       198183 :               if (best->dest->index > (traces[t].last->index + 1))
    1201              :                 {
    1202        22952 :                   int count = EDGE_COUNT (best->dest->preds);
    1203              : 
    1204       128327 :                   FOR_EACH_EDGE (e, ei, best->dest->preds)
    1205       105375 :                     if (e->flags & EDGE_DFS_BACK)
    1206         5966 :                       count--;
    1207              : 
    1208              :                   /* If dest has multiple predecessors, skip it.  We expect
    1209              :                      that one predecessor with smaller index connects with it
    1210              :                      later.  */
    1211        22952 :                   if (count != 1)
    1212              :                     break;
    1213              :                 }
    1214              : 
    1215              :               /* Only connect Trace n with Trace n + 1.  It is conservative
    1216              :                  to keep the order as close as possible to the original order.
    1217              :                  It also helps to reduce long jumps.  */
    1218       182724 :               if (last_trace != bbd[best->dest->index].start_of_trace - 1)
    1219              :                 break;
    1220              : 
    1221       178818 :               if (dump_file)
    1222            5 :                 fprintf (dump_file, "Connection: %d %d\n",
    1223            5 :                          best->src->index, best->dest->index);
    1224              : 
    1225       178818 :               t = bbd[best->dest->index].start_of_trace;
    1226       178818 :               traces[last_trace].last->aux = traces[t].first;
    1227       178818 :               connected[t] = true;
    1228       178818 :               last_trace = t;
    1229              :             }
    1230      4153388 :           else if (best)
    1231              :             {
    1232      1130116 :               if (dump_file)
    1233              :                 {
    1234           45 :                   fprintf (dump_file, "Connection: %d %d\n",
    1235           45 :                            best->src->index, best->dest->index);
    1236              :                 }
    1237      1130116 :               t = bbd[best->dest->index].start_of_trace;
    1238      1130116 :               traces[last_trace].last->aux = traces[t].first;
    1239      1130116 :               connected[t] = true;
    1240      1130116 :               last_trace = t;
    1241              :             }
    1242              :           else
    1243              :             {
    1244              :               /* Try to connect the traces by duplication of 1 block.  */
    1245      3023272 :               edge e2;
    1246      3023272 :               basic_block next_bb = NULL;
    1247      3023272 :               bool try_copy = false;
    1248              : 
    1249      5923689 :               FOR_EACH_EDGE (e, ei, traces[t].last->succs)
    1250      2900417 :                 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
    1251      2228711 :                     && (e->flags & EDGE_CAN_FALLTHRU)
    1252      1928353 :                     && !(e->flags & EDGE_COMPLEX)
    1253      6991138 :                     && (!best || e->probability > best->probability))
    1254              :                   {
    1255      1848628 :                     edge_iterator ei;
    1256      1848628 :                     edge best2 = NULL;
    1257      1848628 :                     int best2_len = 0;
    1258              : 
    1259              :                     /* If the destination is a start of a trace which is only
    1260              :                        one block long, then no need to search the successor
    1261              :                        blocks of the trace.  Accept it.  */
    1262      1848628 :                     if (bbd[e->dest->index].start_of_trace >= 0
    1263       394465 :                         && traces[bbd[e->dest->index].start_of_trace].length
    1264              :                            == 1)
    1265              :                       {
    1266       262680 :                         best = e;
    1267       262680 :                         try_copy = true;
    1268       262680 :                         continue;
    1269              :                       }
    1270              : 
    1271      4048813 :                     FOR_EACH_EDGE (e2, ei, e->dest->succs)
    1272              :                       {
    1273      2462865 :                         int di = e2->dest->index;
    1274              : 
    1275      2462865 :                         if (e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
    1276      2462865 :                             || ((e2->flags & EDGE_CAN_FALLTHRU)
    1277      2051789 :                                 && !(e2->flags & EDGE_COMPLEX)
    1278      2051787 :                                 && bbd[di].start_of_trace >= 0
    1279       730385 :                                 && !connected[bbd[di].start_of_trace]
    1280       253559 :                                 && BB_PARTITION (e2->dest) == current_partition
    1281      2579204 :                                 && e2->count () >= count_threshold
    1282       116636 :                                 && (!best2
    1283         1322 :                                     || e2->probability > best2->probability
    1284          728 :                                     || (e2->probability == best2->probability
    1285           61 :                                         && traces[bbd[di].start_of_trace].length
    1286              :                                            > best2_len))))
    1287              :                           {
    1288       394630 :                             best = e;
    1289       394630 :                             best2 = e2;
    1290       394630 :                             if (e2->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1291       115934 :                               best2_len = traces[bbd[di].start_of_trace].length;
    1292              :                             else
    1293              :                               best2_len = INT_MAX;
    1294              :                             next_bb = e2->dest;
    1295              :                             try_copy = true;
    1296              :                           }
    1297              :                       }
    1298              :                   }
    1299              : 
    1300              :               /* Copy tiny blocks always; copy larger blocks only when the
    1301              :                  edge is traversed frequently enough.  */
    1302      3023272 :               if (try_copy
    1303       651338 :                   && BB_PARTITION (best->src) == BB_PARTITION (best->dest)
    1304      3672335 :                   && copy_bb_p (best->dest,
    1305       649063 :                                 optimize_edge_for_speed_p (best)
    1306      1071305 :                                 && (!best->count ().initialized_p ()
    1307      3191000 :                                     || best->count () >= count_threshold)))
    1308              :                 {
    1309       254400 :                   basic_block new_bb;
    1310              : 
    1311       254400 :                   if (dump_file)
    1312              :                     {
    1313            0 :                       fprintf (dump_file, "Connection: %d %d ",
    1314            0 :                                traces[t].last->index, best->dest->index);
    1315            0 :                       if (!next_bb)
    1316            0 :                         fputc ('\n', dump_file);
    1317            0 :                       else if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1318            0 :                         fprintf (dump_file, "exit\n");
    1319              :                       else
    1320            0 :                         fprintf (dump_file, "%d\n", next_bb->index);
    1321              :                     }
    1322              : 
    1323       254400 :                   new_bb = copy_bb (best->dest, best, traces[t].last, t);
    1324       254400 :                   traces[t].last = new_bb;
    1325       254400 :                   if (next_bb && next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1326              :                     {
    1327        53752 :                       t = bbd[next_bb->index].start_of_trace;
    1328        53752 :                       traces[last_trace].last->aux = traces[t].first;
    1329        53752 :                       connected[t] = true;
    1330        53752 :                       last_trace = t;
    1331              :                     }
    1332              :                   else
    1333              :                     break;      /* Stop finding the successor traces.  */
    1334              :                 }
    1335              :               else
    1336              :                 break;  /* Stop finding the successor traces.  */
    1337              :             }
    1338      1362686 :         }
    1339              :     }
    1340              : 
    1341       607561 :   if (dump_file)
    1342              :     {
    1343           23 :       basic_block bb;
    1344              : 
    1345           23 :       fprintf (dump_file, "Final order:\n");
    1346          211 :       for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
    1347          188 :         fprintf (dump_file, "%d ", bb->index);
    1348           23 :       fprintf (dump_file, "\n");
    1349           23 :       fflush (dump_file);
    1350              :     }
    1351              : 
    1352       607561 :   FREE (connected);
    1353       607561 : }
    1354              : 
    1355              : /* Return true when BB can and should be copied. CODE_MAY_GROW is true
    1356              :    when code size is allowed to grow by duplication.  */
    1357              : 
    1358              : static bool
    1359      3405680 : copy_bb_p (const_basic_block bb, int code_may_grow)
    1360              : {
    1361      3405680 :   unsigned int size = 0;
    1362      3405680 :   unsigned int max_size = uncond_jump_length;
    1363      3405680 :   rtx_insn *insn;
    1364              : 
    1365      3405680 :   if (EDGE_COUNT (bb->preds) < 2)
    1366              :     return false;
    1367      3402720 :   if (!can_duplicate_block_p (bb))
    1368              :     return false;
    1369              : 
    1370              :   /* Avoid duplicating blocks which have many successors (PR/13430).  */
    1371      3402503 :   if (EDGE_COUNT (bb->succs) > 8)
    1372              :     return false;
    1373              : 
    1374      3402496 :   if (code_may_grow && optimize_bb_for_speed_p (bb))
    1375       310917 :     max_size *= param_max_grow_copy_bb_insns;
    1376              : 
    1377     24758237 :   FOR_BB_INSNS (bb, insn)
    1378              :     {
    1379     24424235 :       if (INSN_P (insn))
    1380              :         {
    1381     16681071 :           size += get_attr_min_length (insn);
    1382     16681071 :           if (size > max_size)
    1383              :             break;
    1384              :         }
    1385              :     }
    1386              : 
    1387      3402496 :   if (size <= max_size)
    1388              :     return true;
    1389              : 
    1390      3068494 :   if (dump_file)
    1391              :     {
    1392           59 :       fprintf (dump_file,
    1393              :                "Block %d can't be copied because its size = %u.\n",
    1394           59 :                bb->index, size);
    1395              :     }
    1396              : 
    1397              :   return false;
    1398              : }
    1399              : 
    1400              : /* Return the length of unconditional jump instruction.  */
    1401              : 
    1402              : int
    1403       787688 : get_uncond_jump_length (void)
    1404              : {
    1405       787688 :   unsigned int length;
    1406              : 
    1407       787688 :   start_sequence ();
    1408       787688 :   rtx_code_label *label = emit_label (gen_label_rtx ());
    1409       787688 :   rtx_insn *jump = emit_jump_insn (targetm.gen_jump (label));
    1410       787688 :   length = get_attr_min_length (jump);
    1411       787688 :   end_sequence ();
    1412              : 
    1413       787688 :   gcc_assert (length < INT_MAX);
    1414       787688 :   return length;
    1415              : }
    1416              : 
    1417              : /* Create a forwarder block to OLD_BB starting with NEW_LABEL and in the
    1418              :    other partition wrt OLD_BB.  */
    1419              : 
    1420              : static basic_block
    1421         6660 : create_eh_forwarder_block (rtx_code_label *new_label, basic_block old_bb)
    1422              : {
    1423              :   /* Split OLD_BB, so that EH pads have always only incoming EH edges,
    1424              :      bb_has_eh_pred bbs are treated specially by DF infrastructure.  */
    1425         6660 :   old_bb = split_block_after_labels (old_bb)->dest;
    1426              : 
    1427              :   /* Put the new label and a jump in the new basic block.  */
    1428         6660 :   rtx_insn *label = emit_label (new_label);
    1429         6660 :   rtx_code_label *old_label = block_label (old_bb);
    1430         6660 :   rtx_insn *jump = emit_jump_insn (targetm.gen_jump (old_label));
    1431         6660 :   JUMP_LABEL (jump) = old_label;
    1432              : 
    1433              :   /* Create the new basic block and put it in last position.  */
    1434         6660 :   basic_block last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
    1435         6660 :   basic_block new_bb = create_basic_block (label, jump, last_bb);
    1436         6660 :   new_bb->aux = last_bb->aux;
    1437         6660 :   new_bb->count = old_bb->count;
    1438         6660 :   last_bb->aux = new_bb;
    1439              : 
    1440         6660 :   emit_barrier_after_bb (new_bb);
    1441              : 
    1442         6660 :   make_single_succ_edge (new_bb, old_bb, 0);
    1443              : 
    1444              :   /* Make sure the new basic block is in the other partition.  */
    1445         6660 :   unsigned new_partition = BB_PARTITION (old_bb);
    1446         6660 :   new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
    1447         6660 :   BB_SET_PARTITION (new_bb, new_partition);
    1448              : 
    1449         6660 :   return new_bb;
    1450              : }
    1451              : 
    1452              : /* The common landing pad in block OLD_BB has edges from both partitions.
    1453              :    Add a new landing pad that will just jump to the old one and split the
    1454              :    edges so that no EH edge crosses partitions.  */
    1455              : 
    1456              : static void
    1457            0 : sjlj_fix_up_crossing_landing_pad (basic_block old_bb)
    1458              : {
    1459            0 :   const unsigned lp_len = cfun->eh->lp_array->length ();
    1460            0 :   edge_iterator ei;
    1461            0 :   edge e;
    1462              : 
    1463              :   /* Generate the new common landing-pad label.  */
    1464            0 :   rtx_code_label *new_label = gen_label_rtx ();
    1465            0 :   LABEL_PRESERVE_P (new_label) = 1;
    1466              : 
    1467              :   /* Create the forwarder block.  */
    1468            0 :   basic_block new_bb = create_eh_forwarder_block (new_label, old_bb);
    1469              : 
    1470              :   /* Create the map from old to new lp index and initialize it.  */
    1471            0 :   unsigned *index_map = (unsigned *) alloca (lp_len * sizeof (unsigned));
    1472            0 :   memset (index_map, 0, lp_len * sizeof (unsigned));
    1473              : 
    1474              :   /* Fix up the edges.  */
    1475            0 :   for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
    1476            0 :     if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
    1477              :       {
    1478            0 :         rtx_insn *insn = BB_END (e->src);
    1479            0 :         rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
    1480              : 
    1481            0 :         gcc_assert (note != NULL);
    1482            0 :         const unsigned old_index = INTVAL (XEXP (note, 0));
    1483              : 
    1484              :         /* Generate the new landing-pad structure.  */
    1485            0 :         if (index_map[old_index] == 0)
    1486              :           {
    1487            0 :             eh_landing_pad old_lp = (*cfun->eh->lp_array)[old_index];
    1488            0 :             eh_landing_pad new_lp = gen_eh_landing_pad (old_lp->region);
    1489            0 :             new_lp->post_landing_pad = old_lp->post_landing_pad;
    1490            0 :             new_lp->landing_pad = new_label;
    1491            0 :             index_map[old_index] = new_lp->index;
    1492              :           }
    1493            0 :         XEXP (note, 0) = GEN_INT (index_map[old_index]);
    1494              : 
    1495              :         /* Adjust the edge to the new destination.  */
    1496            0 :         redirect_edge_succ (e, new_bb);
    1497            0 :       }
    1498              :     else
    1499            0 :       ei_next (&ei);
    1500            0 : }
    1501              : 
    1502              : /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
    1503              :    Add a new landing pad that will just jump to the old one and split the
    1504              :    edges so that no EH edge crosses partitions.  */
    1505              : 
    1506              : static void
    1507         6660 : dw2_fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
    1508              : {
    1509         6660 :   eh_landing_pad new_lp;
    1510         6660 :   edge_iterator ei;
    1511         6660 :   edge e;
    1512              : 
    1513              :   /* Generate the new landing-pad structure.  */
    1514         6660 :   new_lp = gen_eh_landing_pad (old_lp->region);
    1515         6660 :   new_lp->post_landing_pad = old_lp->post_landing_pad;
    1516         6660 :   new_lp->landing_pad = gen_label_rtx ();
    1517         6660 :   LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
    1518              : 
    1519              :   /* Create the forwarder block.  */
    1520         6660 :   basic_block new_bb = create_eh_forwarder_block (new_lp->landing_pad, old_bb);
    1521              : 
    1522              :   /* Fix up the edges.  */
    1523        52221 :   for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
    1524        45561 :     if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
    1525              :       {
    1526        34205 :         rtx_insn *insn = BB_END (e->src);
    1527        34205 :         rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
    1528              : 
    1529        34205 :         gcc_assert (note != NULL);
    1530        34205 :         gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
    1531        34205 :         XEXP (note, 0) = GEN_INT (new_lp->index);
    1532              : 
    1533              :         /* Adjust the edge to the new destination.  */
    1534        34205 :         redirect_edge_succ (e, new_bb);
    1535        34205 :       }
    1536              :     else
    1537        11356 :       ei_next (&ei);
    1538         6660 : }
    1539              : 
    1540              : 
    1541              : /* Ensure that all hot bbs are included in a hot path through the
    1542              :    procedure. This is done by calling this function twice, once
    1543              :    with WALK_UP true (to look for paths from the entry to hot bbs) and
    1544              :    once with WALK_UP false (to look for paths from hot bbs to the exit).
    1545              :    Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
    1546              :    to BBS_IN_HOT_PARTITION.  */
    1547              : 
    1548              : static unsigned int
    1549       131528 : sanitize_hot_paths (bool walk_up, unsigned int cold_bb_count,
    1550              :                     vec<basic_block> *bbs_in_hot_partition)
    1551              : {
    1552              :   /* Callers check this.  */
    1553       131528 :   gcc_checking_assert (cold_bb_count);
    1554              : 
    1555              :   /* Keep examining hot bbs while we still have some left to check
    1556              :      and there are remaining cold bbs.  */
    1557       131528 :   vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy ();
    1558       131528 :   while (! hot_bbs_to_check.is_empty ()
    1559      5984787 :          && cold_bb_count)
    1560              :     {
    1561      2926514 :       basic_block bb = hot_bbs_to_check.pop ();
    1562      2926514 :       vec<edge, va_gc> *edges = walk_up ? bb->preds : bb->succs;
    1563      2926514 :       edge e;
    1564      2926514 :       edge_iterator ei;
    1565      2926514 :       profile_probability highest_probability
    1566      2926514 :                                  = profile_probability::uninitialized ();
    1567      2926514 :       profile_count highest_count = profile_count::uninitialized ();
    1568      2926514 :       bool found = false;
    1569              : 
    1570              :       /* Walk the preds/succs and check if there is at least one already
    1571              :          marked hot. Keep track of the most frequent pred/succ so that we
    1572              :          can mark it hot if we don't find one.  */
    1573      3455901 :       FOR_EACH_EDGE (e, ei, edges)
    1574              :         {
    1575      3408629 :           basic_block reach_bb = walk_up ? e->src : e->dest;
    1576              : 
    1577      3408629 :           if (e->flags & EDGE_DFS_BACK)
    1578       136178 :             continue;
    1579              : 
    1580              :           /* Do not expect profile insanities when profile was not adjusted.  */
    1581      3272451 :           if (e->probability == profile_probability::never ()
    1582      6176616 :               || e->count () == profile_count::zero ())
    1583       372886 :             continue;
    1584              : 
    1585      2899565 :           if (BB_PARTITION (reach_bb) != BB_COLD_PARTITION)
    1586              :           {
    1587              :             found = true;
    1588              :             break;
    1589              :           }
    1590              :           /* The following loop will look for the hottest edge via
    1591              :              the edge count, if it is non-zero, then fallback to
    1592              :              the edge probability.  */
    1593        20323 :           if (!(e->count () > highest_count))
    1594        20259 :             highest_count = e->count ();
    1595        20323 :           if (!highest_probability.initialized_p ()
    1596       549710 :               || e->probability > highest_probability)
    1597        20259 :             highest_probability = e->probability;
    1598              :         }
    1599              : 
    1600              :       /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
    1601              :          block (or unpartitioned, e.g. the entry block) then it is ok. If not,
    1602              :          then the most frequent pred (or succ) needs to be adjusted.  In the
    1603              :          case where multiple preds/succs have the same frequency (e.g. a
    1604              :          50-50 branch), then both will be adjusted.  */
    1605      2926514 :       if (found)
    1606      2879242 :         continue;
    1607              : 
    1608        92152 :       FOR_EACH_EDGE (e, ei, edges)
    1609              :         {
    1610        44880 :           if (e->flags & EDGE_DFS_BACK)
    1611        39479 :             continue;
    1612              :           /* Do not expect profile insanities when profile was not adjusted.  */
    1613        24272 :           if (e->probability == profile_probability::never ()
    1614        30559 :               || e->count () == profile_count::zero ())
    1615        18871 :             continue;
    1616              :           /* Select the hottest edge using the edge count, if it is non-zero,
    1617              :              then fallback to the edge probability.  */
    1618         5401 :           if (highest_count.initialized_p ())
    1619              :             {
    1620         5401 :               if (!(e->count () >= highest_count))
    1621            0 :                 continue;
    1622              :             }
    1623            0 :           else if (!(e->probability >= highest_probability))
    1624            0 :             continue;
    1625              : 
    1626         5401 :           basic_block reach_bb = walk_up ? e->src : e->dest;
    1627              : 
    1628              :           /* We have a hot bb with an immediate dominator that is cold.
    1629              :              The dominator needs to be re-marked hot.  */
    1630         5401 :           BB_SET_PARTITION (reach_bb, BB_HOT_PARTITION);
    1631         5401 :           if (dump_file)
    1632            0 :             fprintf (dump_file, "Promoting bb %i to hot partition to sanitize "
    1633              :                      "profile of bb %i in %s walk\n", reach_bb->index,
    1634              :                      bb->index, walk_up ? "backward" : "forward");
    1635         5401 :           cold_bb_count--;
    1636              : 
    1637              :           /* Now we need to examine newly-hot reach_bb to see if it is also
    1638              :              dominated by a cold bb.  */
    1639         5401 :           bbs_in_hot_partition->safe_push (reach_bb);
    1640         5401 :           hot_bbs_to_check.safe_push (reach_bb);
    1641              :         }
    1642              :     }
    1643       131528 :   hot_bbs_to_check.release ();
    1644              : 
    1645       131528 :   return cold_bb_count;
    1646              : }
    1647              : 
    1648              : 
    1649              : /* Find the basic blocks that are rarely executed and need to be moved to
    1650              :    a separate section of the .o file (to cut down on paging and improve
    1651              :    cache locality).  Return a vector of all edges that cross.  */
    1652              : 
    1653              : static vec<edge>
    1654       270447 : find_rarely_executed_basic_blocks_and_crossing_edges (void)
    1655              : {
    1656       270447 :   vec<edge> crossing_edges = vNULL;
    1657       270447 :   basic_block bb;
    1658       270447 :   edge e;
    1659       270447 :   edge_iterator ei;
    1660       270447 :   unsigned int cold_bb_count = 0;
    1661       270447 :   auto_vec<basic_block> bbs_in_hot_partition;
    1662              : 
    1663       270447 :   propagate_unlikely_bbs_forward ();
    1664              : 
    1665              :   /* Mark which partition (hot/cold) each basic block belongs in.  */
    1666      4943276 :   FOR_EACH_BB_FN (bb, cfun)
    1667              :     {
    1668      4672829 :       bool cold_bb = false;
    1669              : 
    1670      4672829 :       if (probably_never_executed_bb_p (cfun, bb))
    1671              :         {
    1672       285346 :           cold_bb = true;
    1673              : 
    1674              :           /* Handle profile insanities created by upstream optimizations
    1675              :              by also checking the incoming edge weights. If there is a non-cold
    1676              :              incoming edge, conservatively prevent this block from being split
    1677              :              into the cold section.  */
    1678       285346 :           if (!bb->count.precise_p ())
    1679          341 :             FOR_EACH_EDGE (e, ei, bb->preds)
    1680          195 :               if (!probably_never_executed_edge_p (cfun, e))
    1681              :                 {
    1682              :                   cold_bb = false;
    1683              :                   break;
    1684              :                 }
    1685              :         }
    1686          146 :       if (cold_bb)
    1687              :         {
    1688       285346 :           BB_SET_PARTITION (bb, BB_COLD_PARTITION);
    1689       285346 :           cold_bb_count++;
    1690              :         }
    1691              :       else
    1692              :         {
    1693      4387483 :           BB_SET_PARTITION (bb, BB_HOT_PARTITION);
    1694      4387483 :           bbs_in_hot_partition.safe_push (bb);
    1695              :         }
    1696              :     }
    1697              : 
    1698              :   /* Ensure that hot bbs are included along a hot path from the entry to exit.
    1699              :      Several different possibilities may include cold bbs along all paths
    1700              :      to/from a hot bb. One is that there are edge weight insanities
    1701              :      due to optimization phases that do not properly update basic block profile
    1702              :      counts. The second is that the entry of the function may not be hot, because
    1703              :      it is entered fewer times than the number of profile training runs, but there
    1704              :      is a loop inside the function that causes blocks within the function to be
    1705              :      above the threshold for hotness. This is fixed by walking up from hot bbs
    1706              :      to the entry block, and then down from hot bbs to the exit, performing
    1707              :      partitioning fixups as necessary.  */
    1708       270447 :   if (cold_bb_count)
    1709              :     {
    1710        65764 :       mark_dfs_back_edges ();
    1711        65764 :       cold_bb_count = sanitize_hot_paths (true, cold_bb_count,
    1712              :                                           &bbs_in_hot_partition);
    1713        65764 :       if (cold_bb_count)
    1714        65764 :         sanitize_hot_paths (false, cold_bb_count, &bbs_in_hot_partition);
    1715              : 
    1716        65764 :       hash_set <basic_block> set;
    1717        65764 :       find_bbs_reachable_by_hot_paths (&set);
    1718      1814683 :       FOR_EACH_BB_FN (bb, cfun)
    1719      1748919 :         if (!set.contains (bb))
    1720       279945 :           BB_SET_PARTITION (bb, BB_COLD_PARTITION);
    1721        65764 :     }
    1722              : 
    1723              :   /* The format of .gcc_except_table does not allow landing pads to
    1724              :      be in a different partition as the throw.  Fix this by either
    1725              :      moving the landing pads or inserting forwarder landing pads.  */
    1726       270447 :   if (cfun->eh->lp_array)
    1727              :     {
    1728       270447 :       const bool sjlj
    1729       270447 :         = (targetm_common.except_unwind_info (&global_options) == UI_SJLJ);
    1730       270447 :       unsigned i;
    1731       270447 :       eh_landing_pad lp;
    1732              : 
    1733      1143450 :       FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
    1734              :         {
    1735       602556 :           bool all_same, all_diff;
    1736              : 
    1737       602556 :           if (lp == NULL
    1738        82681 :               || lp->landing_pad == NULL_RTX
    1739        82681 :               || !LABEL_P (lp->landing_pad))
    1740       519934 :             continue;
    1741              : 
    1742        82622 :           all_same = all_diff = true;
    1743        82622 :           bb = BLOCK_FOR_INSN (lp->landing_pad);
    1744       277799 :           FOR_EACH_EDGE (e, ei, bb->preds)
    1745              :             {
    1746       195177 :               gcc_assert (e->flags & EDGE_EH);
    1747       195177 :               if (BB_PARTITION (bb) == BB_PARTITION (e->src))
    1748              :                 all_diff = false;
    1749              :               else
    1750       134153 :                 all_same = false;
    1751              :             }
    1752              : 
    1753        82622 :           if (all_same)
    1754              :             ;
    1755        63230 :           else if (all_diff)
    1756              :             {
    1757        56570 :               int which = BB_PARTITION (bb);
    1758        56570 :               which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
    1759        56570 :               BB_SET_PARTITION (bb, which);
    1760              :             }
    1761         6660 :           else if (sjlj)
    1762            0 :             sjlj_fix_up_crossing_landing_pad (bb);
    1763              :           else
    1764         6660 :             dw2_fix_up_crossing_landing_pad (lp, bb);
    1765              : 
    1766              :           /* There is a single, common landing pad in SJLJ mode.  */
    1767        82622 :           if (sjlj)
    1768              :             break;
    1769              :         }
    1770              :     }
    1771              : 
    1772              :   /* Mark every edge that crosses between sections.  */
    1773      4956596 :   FOR_EACH_BB_FN (bb, cfun)
    1774     11819867 :     FOR_EACH_EDGE (e, ei, bb->succs)
    1775              :       {
    1776      7133718 :         unsigned int flags = e->flags;
    1777              : 
    1778              :         /* We should never have EDGE_CROSSING set yet.  */
    1779      7133718 :         gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
    1780              : 
    1781      7133718 :         if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1782      7133718 :             && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
    1783      6827926 :             && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
    1784              :           {
    1785       437434 :             crossing_edges.safe_push (e);
    1786       437434 :             flags |= EDGE_CROSSING;
    1787              :           }
    1788              : 
    1789              :         /* Now that we've split eh edges as appropriate, allow landing pads
    1790              :            to be merged with the post-landing pads.  */
    1791      7133718 :         flags &= ~EDGE_PRESERVE;
    1792              : 
    1793      7133718 :         e->flags = flags;
    1794              :       }
    1795              : 
    1796       270447 :   return crossing_edges;
    1797       270447 : }
    1798              : 
    1799              : /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */
    1800              : 
    1801              : static void
    1802       643480 : set_edge_can_fallthru_flag (void)
    1803              : {
    1804       643480 :   basic_block bb;
    1805              : 
    1806     11169574 :   FOR_EACH_BB_FN (bb, cfun)
    1807              :     {
    1808     10526094 :       edge e;
    1809     10526094 :       edge_iterator ei;
    1810              : 
    1811     26303329 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1812              :         {
    1813     15777235 :           e->flags &= ~EDGE_CAN_FALLTHRU;
    1814              : 
    1815              :           /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
    1816     15777235 :           if (e->flags & EDGE_FALLTHRU)
    1817      9098711 :             e->flags |= EDGE_CAN_FALLTHRU;
    1818              :         }
    1819              : 
    1820              :       /* If the BB ends with an invertible condjump all (2) edges are
    1821              :          CAN_FALLTHRU edges.  */
    1822     10526094 :       if (EDGE_COUNT (bb->succs) != 2)
    1823      5425806 :         continue;
    1824      5683406 :       if (!any_condjump_p (BB_END (bb)))
    1825       583118 :         continue;
    1826              : 
    1827      5100288 :       rtx_jump_insn *bb_end_jump = as_a <rtx_jump_insn *> (BB_END (bb));
    1828      5100288 :       if (!invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0))
    1829            0 :         continue;
    1830      5100288 :       invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0);
    1831      5100288 :       EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
    1832      5100288 :       EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
    1833              :     }
    1834       643480 : }
    1835              : 
    1836              : /* If any destination of a crossing edge does not have a label, add label;
    1837              :    Convert any easy fall-through crossing edges to unconditional jumps.  */
    1838              : 
    1839              : static void
    1840        65368 : add_labels_and_missing_jumps (vec<edge> crossing_edges)
    1841              : {
    1842        65368 :   size_t i;
    1843        65368 :   edge e;
    1844              : 
    1845       502802 :   FOR_EACH_VEC_ELT (crossing_edges, i, e)
    1846              :     {
    1847       437434 :       basic_block src = e->src;
    1848       437434 :       basic_block dest = e->dest;
    1849       437434 :       rtx_jump_insn *new_jump;
    1850              : 
    1851       437434 :       if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1852            0 :         continue;
    1853              : 
    1854              :       /* Make sure dest has a label.  */
    1855       437434 :       rtx_code_label *label = block_label (dest);
    1856              : 
    1857              :       /* Nothing to do for non-fallthru edges.  */
    1858       437434 :       if (src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1859            0 :         continue;
    1860       437434 :       if ((e->flags & EDGE_FALLTHRU) == 0)
    1861       257838 :         continue;
    1862              : 
    1863              :       /* If the block does not end with a control flow insn, then we
    1864              :          can trivially add a jump to the end to fixup the crossing.
    1865              :          Otherwise the jump will have to go in a new bb, which will
    1866              :          be handled by fix_up_fall_thru_edges function.  */
    1867       179596 :       if (control_flow_insn_p (BB_END (src)))
    1868       117416 :         continue;
    1869              : 
    1870              :       /* Make sure there's only one successor.  */
    1871        62180 :       gcc_assert (single_succ_p (src));
    1872              : 
    1873        62180 :       new_jump = emit_jump_insn_after (targetm.gen_jump (label), BB_END (src));
    1874        62180 :       BB_END (src) = new_jump;
    1875        62180 :       JUMP_LABEL (new_jump) = label;
    1876        62180 :       LABEL_NUSES (label) += 1;
    1877              : 
    1878        62180 :       emit_barrier_after_bb (src);
    1879              : 
    1880              :       /* Mark edge as non-fallthru.  */
    1881        62180 :       e->flags &= ~EDGE_FALLTHRU;
    1882              :     }
    1883        65368 : }
    1884              : 
    1885              : /* Find any bb's where the fall-through edge is a crossing edge (note that
    1886              :    these bb's must also contain a conditional jump or end with a call
    1887              :    instruction; we've already dealt with fall-through edges for blocks
    1888              :    that didn't have a conditional jump or didn't end with call instruction
    1889              :    in the call to add_labels_and_missing_jumps).  Convert the fall-through
    1890              :    edge to non-crossing edge by inserting a new bb to fall-through into.
    1891              :    The new bb will contain an unconditional jump (crossing edge) to the
    1892              :    original fall through destination.  */
    1893              : 
    1894              : static void
    1895        65368 : fix_up_fall_thru_edges (void)
    1896              : {
    1897        65368 :   basic_block cur_bb;
    1898              : 
    1899      1821063 :   FOR_EACH_BB_FN (cur_bb, cfun)
    1900              :     {
    1901      1755695 :       edge succ1;
    1902      1755695 :       edge succ2;
    1903      1755695 :       edge fall_thru = NULL;
    1904      1755695 :       edge cond_jump = NULL;
    1905              : 
    1906      1755695 :       fall_thru = NULL;
    1907      1755695 :       if (EDGE_COUNT (cur_bb->succs) > 0)
    1908      1649182 :         succ1 = EDGE_SUCC (cur_bb, 0);
    1909              :       else
    1910              :         succ1 = NULL;
    1911              : 
    1912      1755695 :       if (EDGE_COUNT (cur_bb->succs) > 1)
    1913      1042466 :         succ2 = EDGE_SUCC (cur_bb, 1);
    1914              :       else
    1915              :         succ2 = NULL;
    1916              : 
    1917              :       /* Find the fall-through edge.  */
    1918              : 
    1919      1755695 :       if (succ1
    1920      1649182 :           && (succ1->flags & EDGE_FALLTHRU))
    1921              :         {
    1922              :           fall_thru = succ1;
    1923              :           cond_jump = succ2;
    1924              :         }
    1925       867888 :       else if (succ2
    1926       667805 :                && (succ2->flags & EDGE_FALLTHRU))
    1927              :         {
    1928              :           fall_thru = succ2;
    1929              :           cond_jump = succ1;
    1930              :         }
    1931      1756600 :       else if (succ2 && EDGE_COUNT (cur_bb->succs) > 2)
    1932          905 :         fall_thru = find_fallthru_edge (cur_bb->succs);
    1933              : 
    1934      1555570 :       if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
    1935              :         {
    1936              :           /* Check to see if the fall-thru edge is a crossing edge.  */
    1937              : 
    1938      1494103 :           if (fall_thru->flags & EDGE_CROSSING)
    1939              :             {
    1940              :               /* The fall_thru edge crosses; now check the cond jump edge, if
    1941              :                  it exists.  */
    1942              : 
    1943       117416 :               bool cond_jump_crosses = true;
    1944       117416 :               int invert_worked = 0;
    1945       117416 :               rtx_insn *old_jump = BB_END (cur_bb);
    1946              : 
    1947              :               /* Find the jump instruction, if there is one.  */
    1948              : 
    1949       117416 :               if (cond_jump)
    1950              :                 {
    1951       117326 :                   if (!(cond_jump->flags & EDGE_CROSSING))
    1952       116720 :                     cond_jump_crosses = false;
    1953              : 
    1954              :                   /* We know the fall-thru edge crosses; if the cond
    1955              :                      jump edge does NOT cross, and its destination is the
    1956              :                      next block in the bb order, invert the jump
    1957              :                      (i.e. fix it so the fall through does not cross and
    1958              :                      the cond jump does).  */
    1959              : 
    1960       116720 :                   if (!cond_jump_crosses)
    1961              :                     {
    1962              :                       /* Find label in fall_thru block. We've already added
    1963              :                          any missing labels, so there must be one.  */
    1964              : 
    1965       116720 :                       rtx_code_label *fall_thru_label
    1966       116720 :                         = block_label (fall_thru->dest);
    1967              : 
    1968       116720 :                       if (old_jump && fall_thru_label)
    1969              :                         {
    1970       116720 :                           rtx_jump_insn *old_jump_insn
    1971       231731 :                             = dyn_cast <rtx_jump_insn *> (old_jump);
    1972       114315 :                           if (old_jump_insn)
    1973       114315 :                             invert_worked = invert_jump (old_jump_insn,
    1974              :                                                          fall_thru_label, 0);
    1975              :                         }
    1976              : 
    1977       114315 :                       if (invert_worked)
    1978              :                         {
    1979       114305 :                           fall_thru->flags &= ~EDGE_FALLTHRU;
    1980       114305 :                           cond_jump->flags |= EDGE_FALLTHRU;
    1981       114305 :                           update_br_prob_note (cur_bb);
    1982       114305 :                           std::swap (fall_thru, cond_jump);
    1983       114305 :                           cond_jump->flags |= EDGE_CROSSING;
    1984       114305 :                           fall_thru->flags &= ~EDGE_CROSSING;
    1985              :                         }
    1986              :                     }
    1987              :                 }
    1988              : 
    1989       117416 :               if (cond_jump_crosses || !invert_worked)
    1990              :                 {
    1991              :                   /* This is the case where both edges out of the basic
    1992              :                      block are crossing edges. Here we will fix up the
    1993              :                      fall through edge. The jump edge will be taken care
    1994              :                      of later.  The EDGE_CROSSING flag of fall_thru edge
    1995              :                      is unset before the call to force_nonfallthru
    1996              :                      function because if a new basic-block is created
    1997              :                      this edge remains in the current section boundary
    1998              :                      while the edge between new_bb and the fall_thru->dest
    1999              :                      becomes EDGE_CROSSING.  */
    2000              : 
    2001         3111 :                   fall_thru->flags &= ~EDGE_CROSSING;
    2002         3111 :                   unsigned old_count = EDGE_COUNT (cur_bb->succs);
    2003         3111 :                   basic_block new_bb = force_nonfallthru (fall_thru);
    2004              : 
    2005         3111 :                   if (new_bb)
    2006              :                     {
    2007         3111 :                       new_bb->aux = cur_bb->aux;
    2008         3111 :                       cur_bb->aux = new_bb;
    2009              : 
    2010              :                       /* This is done by force_nonfallthru_and_redirect.  */
    2011         3111 :                       gcc_assert (BB_PARTITION (new_bb)
    2012              :                                   == BB_PARTITION (cur_bb));
    2013              : 
    2014         3111 :                       edge e = single_succ_edge (new_bb);
    2015         3111 :                       e->flags |= EDGE_CROSSING;
    2016         3111 :                       if (EDGE_COUNT (cur_bb->succs) > old_count)
    2017              :                         {
    2018              :                           /* If asm goto has a crossing fallthrough edge
    2019              :                              and at least one of the labels to the same bb,
    2020              :                              force_nonfallthru can result in the fallthrough
    2021              :                              edge being redirected and a new edge added for the
    2022              :                              label or more labels to e->dest.  As we've
    2023              :                              temporarily cleared EDGE_CROSSING flag on the
    2024              :                              fallthrough edge, we need to restore it again.
    2025              :                              See PR108596.  */
    2026            0 :                           rtx_insn *j = BB_END (cur_bb);
    2027            0 :                           gcc_checking_assert (JUMP_P (j)
    2028              :                                                && (asm_noperands (PATTERN (j))
    2029              :                                                    > 0));
    2030            0 :                           edge e2 = find_edge (cur_bb, e->dest);
    2031            0 :                           if (e2)
    2032            0 :                             e2->flags |= EDGE_CROSSING;
    2033              :                         }
    2034              :                     }
    2035              :                   else
    2036              :                     {
    2037              :                       /* If a new basic-block was not created; restore
    2038              :                          the EDGE_CROSSING flag.  */
    2039            0 :                       fall_thru->flags |= EDGE_CROSSING;
    2040              :                     }
    2041              : 
    2042              :                   /* Add barrier after new jump */
    2043         3111 :                   emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
    2044              :                 }
    2045              :             }
    2046              :         }
    2047              :     }
    2048        65368 : }
    2049              : 
    2050              : /* This function checks the destination block of a "crossing jump" to
    2051              :    see if it has any crossing predecessors that begin with a code label
    2052              :    and end with an unconditional jump.  If so, it returns that predecessor
    2053              :    block.  (This is to avoid creating lots of new basic blocks that all
    2054              :    contain unconditional jumps to the same destination).  */
    2055              : 
    2056              : static basic_block
    2057            0 : find_jump_block (basic_block jump_dest)
    2058              : {
    2059            0 :   basic_block source_bb = NULL;
    2060            0 :   edge e;
    2061            0 :   rtx_insn *insn;
    2062            0 :   edge_iterator ei;
    2063              : 
    2064            0 :   FOR_EACH_EDGE (e, ei, jump_dest->preds)
    2065            0 :     if (e->flags & EDGE_CROSSING)
    2066              :       {
    2067            0 :         basic_block src = e->src;
    2068              : 
    2069              :         /* Check each predecessor to see if it has a label, and contains
    2070              :            only one executable instruction, which is an unconditional jump.
    2071              :            If so, we can use it.  */
    2072              : 
    2073            0 :         if (LABEL_P (BB_HEAD (src)))
    2074            0 :           for (insn = BB_HEAD (src);
    2075            0 :                !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
    2076            0 :                insn = NEXT_INSN (insn))
    2077              :             {
    2078            0 :               if (INSN_P (insn)
    2079              :                   && insn == BB_END (src)
    2080              :                   && JUMP_P (insn)
    2081              :                   && !any_condjump_p (insn))
    2082              :                 {
    2083              :                   source_bb = src;
    2084              :                   break;
    2085              :                 }
    2086              :             }
    2087              : 
    2088              :         if (source_bb)
    2089              :           break;
    2090              :       }
    2091              : 
    2092            0 :   return source_bb;
    2093              : }
    2094              : 
    2095              : /* Find all BB's with conditional jumps that are crossing edges;
    2096              :    insert a new bb and make the conditional jump branch to the new
    2097              :    bb instead (make the new bb same color so conditional branch won't
    2098              :    be a 'crossing' edge).  Insert an unconditional jump from the
    2099              :    new bb to the original destination of the conditional jump.  */
    2100              : 
    2101              : static void
    2102            0 : fix_crossing_conditional_branches (void)
    2103              : {
    2104            0 :   basic_block cur_bb;
    2105            0 :   basic_block new_bb;
    2106            0 :   basic_block dest;
    2107            0 :   edge succ1;
    2108            0 :   edge succ2;
    2109            0 :   edge crossing_edge;
    2110            0 :   edge new_edge;
    2111            0 :   rtx set_src;
    2112            0 :   rtx old_label = NULL_RTX;
    2113            0 :   rtx_code_label *new_label;
    2114              : 
    2115            0 :   FOR_EACH_BB_FN (cur_bb, cfun)
    2116              :     {
    2117            0 :       crossing_edge = NULL;
    2118            0 :       if (EDGE_COUNT (cur_bb->succs) > 0)
    2119            0 :         succ1 = EDGE_SUCC (cur_bb, 0);
    2120              :       else
    2121              :         succ1 = NULL;
    2122              : 
    2123            0 :       if (EDGE_COUNT (cur_bb->succs) > 1)
    2124            0 :         succ2 = EDGE_SUCC (cur_bb, 1);
    2125              :       else
    2126              :         succ2 = NULL;
    2127              : 
    2128              :       /* We already took care of fall-through edges, so only one successor
    2129              :          can be a crossing edge.  */
    2130              : 
    2131            0 :       if (succ1 && (succ1->flags & EDGE_CROSSING))
    2132              :         crossing_edge = succ1;
    2133            0 :       else if (succ2 && (succ2->flags & EDGE_CROSSING))
    2134              :         crossing_edge = succ2;
    2135              : 
    2136              :       if (crossing_edge)
    2137              :         {
    2138            0 :           rtx_insn *old_jump = BB_END (cur_bb);
    2139              : 
    2140              :           /* Check to make sure the jump instruction is a
    2141              :              conditional jump.  */
    2142              : 
    2143            0 :           set_src = NULL_RTX;
    2144              : 
    2145            0 :           if (any_condjump_p (old_jump))
    2146              :             {
    2147            0 :               if (GET_CODE (PATTERN (old_jump)) == SET)
    2148            0 :                 set_src = SET_SRC (PATTERN (old_jump));
    2149            0 :               else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
    2150              :                 {
    2151            0 :                   set_src = XVECEXP (PATTERN (old_jump), 0,0);
    2152            0 :                   if (GET_CODE (set_src) == SET)
    2153            0 :                     set_src = SET_SRC (set_src);
    2154              :                   else
    2155              :                     set_src = NULL_RTX;
    2156              :                 }
    2157              :             }
    2158              : 
    2159            0 :           if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
    2160              :             {
    2161            0 :               rtx_jump_insn *old_jump_insn =
    2162            0 :                         as_a <rtx_jump_insn *> (old_jump);
    2163              : 
    2164            0 :               if (GET_CODE (XEXP (set_src, 1)) == PC)
    2165            0 :                 old_label = XEXP (set_src, 2);
    2166            0 :               else if (GET_CODE (XEXP (set_src, 2)) == PC)
    2167            0 :                 old_label = XEXP (set_src, 1);
    2168              : 
    2169              :               /* Check to see if new bb for jumping to that dest has
    2170              :                  already been created; if so, use it; if not, create
    2171              :                  a new one.  */
    2172              : 
    2173            0 :               new_bb = find_jump_block (crossing_edge->dest);
    2174              : 
    2175            0 :               if (new_bb)
    2176              :                 new_label = block_label (new_bb);
    2177              :               else
    2178              :                 {
    2179            0 :                   basic_block last_bb;
    2180            0 :                   rtx_code_label *old_jump_target;
    2181            0 :                   rtx_jump_insn *new_jump;
    2182              : 
    2183              :                   /* Create new basic block to be dest for
    2184              :                      conditional jump.  */
    2185              : 
    2186              :                   /* Put appropriate instructions in new bb.  */
    2187              : 
    2188            0 :                   new_label = gen_label_rtx ();
    2189            0 :                   emit_label (new_label);
    2190              : 
    2191            0 :                   gcc_assert (GET_CODE (old_label) == LABEL_REF);
    2192            0 :                   old_jump_target = old_jump_insn->jump_target ();
    2193            0 :                   new_jump = as_a <rtx_jump_insn *>
    2194            0 :                     (emit_jump_insn (targetm.gen_jump (old_jump_target)));
    2195            0 :                   new_jump->set_jump_target (old_jump_target);
    2196              : 
    2197            0 :                   last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
    2198            0 :                   new_bb = create_basic_block (new_label, new_jump, last_bb);
    2199            0 :                   new_bb->aux = last_bb->aux;
    2200            0 :                   last_bb->aux = new_bb;
    2201              : 
    2202            0 :                   emit_barrier_after_bb (new_bb);
    2203              : 
    2204              :                   /* Make sure new bb is in same partition as source
    2205              :                      of conditional branch.  */
    2206            0 :                   BB_COPY_PARTITION (new_bb, cur_bb);
    2207              :                 }
    2208              : 
    2209              :               /* Make old jump branch to new bb.  */
    2210              : 
    2211            0 :               redirect_jump (old_jump_insn, new_label, 0);
    2212              : 
    2213              :               /* Remove crossing_edge as predecessor of 'dest'.  */
    2214              : 
    2215            0 :               dest = crossing_edge->dest;
    2216              : 
    2217            0 :               redirect_edge_succ (crossing_edge, new_bb);
    2218              : 
    2219              :               /* Make a new edge from new_bb to old dest; new edge
    2220              :                  will be a successor for new_bb and a predecessor
    2221              :                  for 'dest'.  */
    2222              : 
    2223            0 :               if (EDGE_COUNT (new_bb->succs) == 0)
    2224            0 :                 new_edge = make_single_succ_edge (new_bb, dest, 0);
    2225              :               else
    2226            0 :                 new_edge = EDGE_SUCC (new_bb, 0);
    2227              : 
    2228            0 :               crossing_edge->flags &= ~EDGE_CROSSING;
    2229            0 :               new_edge->flags |= EDGE_CROSSING;
    2230              :             }
    2231              :         }
    2232              :     }
    2233            0 : }
    2234              : 
    2235              : /* Find any unconditional branches that cross between hot and cold
    2236              :    sections.  Convert them into indirect jumps instead.  */
    2237              : 
    2238              : static void
    2239            0 : fix_crossing_unconditional_branches (void)
    2240              : {
    2241            0 :   basic_block cur_bb;
    2242            0 :   rtx_insn *last_insn;
    2243            0 :   rtx label;
    2244            0 :   rtx label_addr;
    2245            0 :   rtx_insn *indirect_jump_sequence;
    2246            0 :   rtx_insn *jump_insn = NULL;
    2247            0 :   rtx new_reg;
    2248            0 :   rtx_insn *cur_insn;
    2249            0 :   edge succ;
    2250              : 
    2251            0 :   FOR_EACH_BB_FN (cur_bb, cfun)
    2252              :     {
    2253            0 :       last_insn = BB_END (cur_bb);
    2254              : 
    2255            0 :       if (EDGE_COUNT (cur_bb->succs) < 1)
    2256            0 :         continue;
    2257              : 
    2258            0 :       succ = EDGE_SUCC (cur_bb, 0);
    2259              : 
    2260              :       /* Check to see if bb ends in a crossing (unconditional) jump.  At
    2261              :          this point, no crossing jumps should be conditional.  */
    2262              : 
    2263            0 :       if (JUMP_P (last_insn)
    2264            0 :           && (succ->flags & EDGE_CROSSING))
    2265              :         {
    2266            0 :           gcc_assert (!any_condjump_p (last_insn));
    2267              : 
    2268              :           /* Make sure the jump is not already an indirect or table jump.  */
    2269              : 
    2270            0 :           if (!computed_jump_p (last_insn)
    2271            0 :               && !tablejump_p (last_insn, NULL, NULL)
    2272            0 :               && asm_noperands (PATTERN (last_insn)) < 0)
    2273              :             {
    2274              :               /* We have found a "crossing" unconditional branch.  Now
    2275              :                  we must convert it to an indirect jump.  First create
    2276              :                  reference of label, as target for jump.  */
    2277              : 
    2278            0 :               label = JUMP_LABEL (last_insn);
    2279            0 :               label_addr = gen_rtx_LABEL_REF (Pmode, label);
    2280            0 :               LABEL_NUSES (label) += 1;
    2281              : 
    2282              :               /* Get a register to use for the indirect jump.  */
    2283              : 
    2284            0 :               new_reg = gen_reg_rtx (Pmode);
    2285              : 
    2286              :               /* Generate indirect the jump sequence.  */
    2287              : 
    2288            0 :               start_sequence ();
    2289            0 :               emit_move_insn (new_reg, label_addr);
    2290            0 :               emit_indirect_jump (new_reg);
    2291            0 :               indirect_jump_sequence = end_sequence ();
    2292              : 
    2293              :               /* Make sure every instruction in the new jump sequence has
    2294              :                  its basic block set to be cur_bb.  */
    2295              : 
    2296            0 :               for (cur_insn = indirect_jump_sequence; cur_insn;
    2297            0 :                    cur_insn = NEXT_INSN (cur_insn))
    2298              :                 {
    2299            0 :                   if (!BARRIER_P (cur_insn))
    2300            0 :                     BLOCK_FOR_INSN (cur_insn) = cur_bb;
    2301            0 :                   if (JUMP_P (cur_insn))
    2302            0 :                     jump_insn = cur_insn;
    2303              :                 }
    2304              : 
    2305              :               /* Insert the new (indirect) jump sequence immediately before
    2306              :                  the unconditional jump, then delete the unconditional jump.  */
    2307              : 
    2308            0 :               emit_insn_before (indirect_jump_sequence, last_insn);
    2309            0 :               delete_insn (last_insn);
    2310              : 
    2311            0 :               JUMP_LABEL (jump_insn) = label;
    2312            0 :               LABEL_NUSES (label)++;
    2313              : 
    2314              :               /* Make BB_END for cur_bb be the jump instruction (NOT the
    2315              :                  barrier instruction at the end of the sequence...).  */
    2316              : 
    2317            0 :               BB_END (cur_bb) = jump_insn;
    2318              :             }
    2319              :         }
    2320              :     }
    2321            0 : }
    2322              : 
    2323              : /* Update CROSSING_JUMP_P flags on all jump insns.  */
    2324              : 
    2325              : static void
    2326        65368 : update_crossing_jump_flags (void)
    2327              : {
    2328        65368 :   basic_block bb;
    2329        65368 :   edge e;
    2330        65368 :   edge_iterator ei;
    2331              : 
    2332      1821063 :   FOR_EACH_BB_FN (bb, cfun)
    2333      3735548 :     FOR_EACH_EDGE (e, ei, bb->succs)
    2334      2417102 :       if (e->flags & EDGE_CROSSING)
    2335              :         {
    2336       437249 :           if (JUMP_P (BB_END (bb)))
    2337       437152 :             set_crossing_jump (BB_END (bb), true);
    2338              :           break;
    2339              :         }
    2340        65368 : }
    2341              : 
    2342              : /* Reorder basic blocks using the software trace cache (STC) algorithm.  */
    2343              : 
    2344              : static void
    2345       607561 : reorder_basic_blocks_software_trace_cache (void)
    2346              : {
    2347       607561 :   if (dump_file)
    2348           23 :     fprintf (dump_file, "\nReordering with the STC algorithm.\n\n");
    2349              : 
    2350       607561 :   int n_traces;
    2351       607561 :   int i;
    2352       607561 :   struct trace *traces;
    2353              : 
    2354              :   /* We are estimating the length of uncond jump insn only once since the code
    2355              :      for getting the insn length always returns the minimal length now.  */
    2356       607561 :   if (uncond_jump_length == 0)
    2357         9506 :     uncond_jump_length = get_uncond_jump_length ();
    2358              : 
    2359              :   /* We need to know some information for each basic block.  */
    2360       607561 :   array_size = GET_ARRAY_SIZE (last_basic_block_for_fn (cfun));
    2361       607561 :   bbd = XNEWVEC (bbro_basic_block_data, array_size);
    2362     17352041 :   for (i = 0; i < array_size; i++)
    2363              :     {
    2364     16744480 :       bbd[i].start_of_trace = -1;
    2365     16744480 :       bbd[i].end_of_trace = -1;
    2366     16744480 :       bbd[i].in_trace = -1;
    2367     16744480 :       bbd[i].visited = 0;
    2368     16744480 :       bbd[i].priority = -1;
    2369     16744480 :       bbd[i].heap = NULL;
    2370     16744480 :       bbd[i].node = NULL;
    2371              :     }
    2372              : 
    2373       607561 :   traces = XNEWVEC (struct trace, n_basic_blocks_for_fn (cfun));
    2374       607561 :   n_traces = 0;
    2375       607561 :   find_traces (&n_traces, traces);
    2376       607561 :   connect_traces (n_traces, traces);
    2377       607561 :   FREE (traces);
    2378       607561 :   FREE (bbd);
    2379       607561 : }
    2380              : 
    2381              : /* Order edges by execution frequency, higher first.
    2382              :    Return:
    2383              :        1 iff frequency (VE1) < frequency (VE2)
    2384              :        0 iff frequency (VE1) == frequency (VE2)
    2385              :        -1 iff frequency (VE1) > frequency (VE2)  */
    2386              : 
    2387              : static int
    2388     21174815 : edge_order (const void *ve1, const void *ve2)
    2389              : {
    2390     21174815 :   edge e1 = *(const edge *) ve1;
    2391     21174815 :   edge e2 = *(const edge *) ve2;
    2392     21174815 :   profile_count c1 = e1->count ();
    2393     21174815 :   profile_count c2 = e2->count ();
    2394              :   /* Since profile_count::operator< does not establish a strict weak order
    2395              :      in presence of uninitialized counts, use 'max': this makes them appear
    2396              :      as if having execution frequency less than any initialized count.  */
    2397     21174815 :   gcov_type gc1 = c1.initialized_p () ? c1.to_gcov_type () : 0;
    2398     21174815 :   gcov_type gc2 = c2.initialized_p () ? c2.to_gcov_type () : 0;
    2399     21174815 :   gcov_type m = MAX (gc1, gc2);
    2400     21174815 :   int low_to_high_cmp = (m == gc1) - (m == gc2);
    2401              :   /* gcc_stablesort sorts values in low-to-high order.  But edges should
    2402              :      be sorted in the opposite order - with highest execution frequency first.
    2403              :      So return an inverted comparison to trick gcc_stablesort into
    2404              :      performing a reversed sorting order.  */
    2405     21174815 :   return -1 * low_to_high_cmp;
    2406              : }
    2407              : 
    2408              : /* Reorder basic blocks using the "simple" algorithm.  This tries to
    2409              :    maximize the dynamic number of branches that are fallthrough, without
    2410              :    copying instructions.  The algorithm is greedy, looking at the most
    2411              :    frequently executed branch first.  */
    2412              : 
    2413              : static void
    2414        35919 : reorder_basic_blocks_simple (void)
    2415              : {
    2416        35919 :   if (dump_file)
    2417            8 :     fprintf (dump_file, "\nReordering with the \"simple\" algorithm.\n\n");
    2418              : 
    2419        35919 :   edge *edges = new edge[2 * n_basic_blocks_for_fn (cfun)];
    2420              : 
    2421              :   /* First, collect all edges that can be optimized by reordering blocks:
    2422              :      simple jumps and conditional jumps, as well as the function entry edge.  */
    2423              : 
    2424        35919 :   int n = 0;
    2425        35919 :   edges[n++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
    2426              : 
    2427        35919 :   basic_block bb;
    2428       579220 :   FOR_EACH_BB_FN (bb, cfun)
    2429              :     {
    2430       543301 :       rtx_insn *end = BB_END (bb);
    2431              : 
    2432       543301 :       if (computed_jump_p (end) || tablejump_p (end, NULL, NULL))
    2433          417 :         continue;
    2434              : 
    2435              :       /* We cannot optimize asm goto.  */
    2436       542884 :       if (JUMP_P (end) && extract_asm_operands (end))
    2437            0 :         continue;
    2438              : 
    2439       542884 :       if (single_succ_p (bb))
    2440       165453 :         edges[n++] = EDGE_SUCC (bb, 0);
    2441       377431 :       else if (any_condjump_p (end))
    2442              :         {
    2443       276542 :           edge e0 = EDGE_SUCC (bb, 0);
    2444       276542 :           edge e1 = EDGE_SUCC (bb, 1);
    2445              :           /* When optimizing for size it is best to keep the original
    2446              :              fallthrough edges.  */
    2447       276542 :           if (e1->flags & EDGE_FALLTHRU)
    2448       149557 :             std::swap (e0, e1);
    2449       276542 :           edges[n++] = e0;
    2450       276542 :           edges[n++] = e1;
    2451              :         }
    2452              :     }
    2453              : 
    2454              :   /* Sort the edges, the most desirable first.  When optimizing for size
    2455              :      all edges are equally desirable.  */
    2456              : 
    2457        35919 :   if (optimize_function_for_speed_p (cfun))
    2458        35754 :     gcc_stablesort (edges, n, sizeof *edges, edge_order);
    2459              : 
    2460              :   /* Now decide which of those edges to make fallthrough edges.  We set
    2461              :      BB_VISITED if a block already has a fallthrough successor assigned
    2462              :      to it.  We make ->AUX of an endpoint point to the opposite endpoint
    2463              :      of a sequence of blocks that fall through, and ->AUX will be NULL
    2464              :      for a block that is in such a sequence but not an endpoint anymore.
    2465              : 
    2466              :      To start with, everything points to itself, nothing is assigned yet.  */
    2467              : 
    2468       651058 :   FOR_ALL_BB_FN (bb, cfun)
    2469              :     {
    2470       615139 :       bb->aux = bb;
    2471       615139 :       bb->flags &= ~BB_VISITED;
    2472              :     }
    2473              : 
    2474        35919 :   EXIT_BLOCK_PTR_FOR_FN (cfun)->aux = 0;
    2475              : 
    2476              :   /* Now for all edges, the most desirable first, see if that edge can
    2477              :      connect two sequences.  If it can, update AUX and BB_VISITED; if it
    2478              :      cannot, zero out the edge in the table.  */
    2479              : 
    2480       790375 :   for (int j = 0; j < n; j++)
    2481              :     {
    2482       754456 :       edge e = edges[j];
    2483              : 
    2484       754456 :       basic_block tail_a = e->src;
    2485       754456 :       basic_block head_b = e->dest;
    2486       754456 :       basic_block head_a = (basic_block) tail_a->aux;
    2487       754456 :       basic_block tail_b = (basic_block) head_b->aux;
    2488              : 
    2489              :       /* An edge cannot connect two sequences if:
    2490              :          - it crosses partitions;
    2491              :          - its src is not a current endpoint;
    2492              :          - its dest is not a current endpoint;
    2493              :          - or, it would create a loop.  */
    2494              : 
    2495       754456 :       if (e->flags & EDGE_CROSSING
    2496       754446 :           || tail_a->flags & BB_VISITED
    2497       518934 :           || !tail_b
    2498       440091 :           || (!(head_b->flags & BB_VISITED) && head_b != tail_b)
    2499       413334 :           || tail_a == tail_b)
    2500              :         {
    2501       380868 :           edges[j] = 0;
    2502       380868 :           continue;
    2503              :         }
    2504              : 
    2505       373588 :       tail_a->aux = 0;
    2506       373588 :       head_b->aux = 0;
    2507       373588 :       head_a->aux = tail_b;
    2508       373588 :       tail_b->aux = head_a;
    2509       373588 :       tail_a->flags |= BB_VISITED;
    2510              :     }
    2511              : 
    2512              :   /* Put the pieces together, in the same order that the start blocks of
    2513              :      the sequences already had.  The hot/cold partitioning gives a little
    2514              :      complication: as a first pass only do this for blocks in the same
    2515              :      partition as the start block, and (if there is anything left to do)
    2516              :      in a second pass handle the other partition.  */
    2517              : 
    2518        35919 :   basic_block last_tail = (basic_block) ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
    2519              : 
    2520        35919 :   int current_partition
    2521        35919 :     = BB_PARTITION (last_tail == ENTRY_BLOCK_PTR_FOR_FN (cfun)
    2522              :                     ? EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest
    2523              :                     : last_tail);
    2524        35919 :   bool need_another_pass = true;
    2525              : 
    2526        71844 :   for (int pass = 0; pass < 2 && need_another_pass; pass++)
    2527              :     {
    2528        35925 :       need_another_pass = false;
    2529              : 
    2530       579269 :       FOR_EACH_BB_FN (bb, cfun)
    2531       543344 :         if ((bb->flags & BB_VISITED && bb->aux) || bb->aux == bb)
    2532              :           {
    2533       169727 :             if (BB_PARTITION (bb) != current_partition)
    2534              :               {
    2535           14 :                 need_another_pass = true;
    2536           14 :                 continue;
    2537              :               }
    2538              : 
    2539       169713 :             last_tail->aux = bb;
    2540       169713 :             last_tail = (basic_block) bb->aux;
    2541              :           }
    2542              : 
    2543        35925 :       current_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
    2544              :     }
    2545              : 
    2546        35919 :   last_tail->aux = 0;
    2547              : 
    2548              :   /* Finally, link all the chosen fallthrough edges.  */
    2549              : 
    2550       790375 :   for (int j = 0; j < n; j++)
    2551       754456 :     if (edges[j])
    2552       373588 :       edges[j]->src->aux = edges[j]->dest;
    2553              : 
    2554        35919 :   delete[] edges;
    2555              : 
    2556              :   /* If the entry edge no longer falls through we have to make a new
    2557              :      block so it can do so again.  */
    2558              : 
    2559        35919 :   edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
    2560        35919 :   if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux)
    2561              :     {
    2562            8 :       force_nonfallthru (e);
    2563            8 :       e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
    2564              :     }
    2565        35919 : }
    2566              : 
    2567              : /* Reorder basic blocks.  The main entry point to this file.  */
    2568              : 
    2569              : static void
    2570      1064962 : reorder_basic_blocks (void)
    2571              : {
    2572      1064962 :   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
    2573              : 
    2574      1064962 :   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
    2575              :     return;
    2576              : 
    2577       643480 :   set_edge_can_fallthru_flag ();
    2578       643480 :   mark_dfs_back_edges ();
    2579              : 
    2580       643480 :   switch (flag_reorder_blocks_algorithm)
    2581              :     {
    2582        35919 :     case REORDER_BLOCKS_ALGORITHM_SIMPLE:
    2583        35919 :       reorder_basic_blocks_simple ();
    2584        35919 :       break;
    2585              : 
    2586       607561 :     case REORDER_BLOCKS_ALGORITHM_STC:
    2587       607561 :       reorder_basic_blocks_software_trace_cache ();
    2588       607561 :       break;
    2589              : 
    2590            0 :     default:
    2591            0 :       gcc_unreachable ();
    2592              :     }
    2593              : 
    2594       643480 :   relink_block_chain (/*stay_in_cfglayout_mode=*/true);
    2595              : 
    2596       643480 :   if (dump_file)
    2597              :     {
    2598           31 :       if (dump_flags & TDF_DETAILS)
    2599            0 :         dump_reg_info (dump_file);
    2600           31 :       dump_flow_info (dump_file, dump_flags);
    2601              :     }
    2602              : 
    2603              :   /* Signal that rtl_verify_flow_info_1 can now verify that there
    2604              :      is at most one switch between hot/cold sections.  */
    2605       643480 :   crtl->bb_reorder_complete = true;
    2606              : }
    2607              : 
    2608              : /* Determine which partition the first basic block in the function
    2609              :    belongs to, then find the first basic block in the current function
    2610              :    that belongs to a different section, and insert a
    2611              :    NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
    2612              :    instruction stream.  When writing out the assembly code,
    2613              :    encountering this note will make the compiler switch between the
    2614              :    hot and cold text sections.  */
    2615              : 
    2616              : void
    2617        65368 : insert_section_boundary_note (void)
    2618              : {
    2619        65368 :   basic_block bb;
    2620        65368 :   bool switched_sections = false;
    2621        65368 :   int current_partition = 0;
    2622              : 
    2623        65368 :   if (!crtl->has_bb_partition)
    2624              :     return;
    2625              : 
    2626      1871810 :   FOR_EACH_BB_FN (bb, cfun)
    2627              :     {
    2628      1806442 :       if (!current_partition)
    2629        65368 :         current_partition = BB_PARTITION (bb);
    2630      1806442 :       if (BB_PARTITION (bb) != current_partition)
    2631              :         {
    2632        65368 :           gcc_assert (!switched_sections);
    2633        65368 :           switched_sections = true;
    2634        65368 :           emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, BB_HEAD (bb));
    2635        65368 :           current_partition = BB_PARTITION (bb);
    2636              :         }
    2637              :     }
    2638              : 
    2639              :   /* Make sure crtl->has_bb_partition matches reality even if bbpart finds
    2640              :      some hot and some cold basic blocks, but later one of those kinds is
    2641              :      optimized away.  */
    2642        65368 :   crtl->has_bb_partition = switched_sections;
    2643              : }
    2644              : 
    2645              : namespace {
    2646              : 
    2647              : const pass_data pass_data_reorder_blocks =
    2648              : {
    2649              :   RTL_PASS, /* type */
    2650              :   "bbro", /* name */
    2651              :   OPTGROUP_NONE, /* optinfo_flags */
    2652              :   TV_REORDER_BLOCKS, /* tv_id */
    2653              :   0, /* properties_required */
    2654              :   0, /* properties_provided */
    2655              :   0, /* properties_destroyed */
    2656              :   0, /* todo_flags_start */
    2657              :   0, /* todo_flags_finish */
    2658              : };
    2659              : 
    2660              : class pass_reorder_blocks : public rtl_opt_pass
    2661              : {
    2662              : public:
    2663       297180 :   pass_reorder_blocks (gcc::context *ctxt)
    2664       594360 :     : rtl_opt_pass (pass_data_reorder_blocks, ctxt)
    2665              :   {}
    2666              : 
    2667              :   /* opt_pass methods: */
    2668      1517135 :   bool gate (function *) final override
    2669              :     {
    2670      1517135 :       if (targetm.cannot_modify_jumps_p ())
    2671              :         return false;
    2672      1517135 :       return (optimize > 0
    2673      1517135 :               && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
    2674              :     }
    2675              : 
    2676              :   unsigned int execute (function *) final override;
    2677              : 
    2678              : }; // class pass_reorder_blocks
    2679              : 
    2680              : unsigned int
    2681      1064962 : pass_reorder_blocks::execute (function *fun)
    2682              : {
    2683      1064962 :   basic_block bb;
    2684              : 
    2685              :   /* Last attempt to optimize CFG, as scheduling, peepholing and insn
    2686              :      splitting possibly introduced more crossjumping opportunities.  */
    2687      1064962 :   cfg_layout_initialize (CLEANUP_EXPENSIVE);
    2688              : 
    2689      1064962 :   reorder_basic_blocks ();
    2690      1064962 :   cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_NO_PARTITIONING);
    2691              : 
    2692     11987840 :   FOR_EACH_BB_FN (bb, fun)
    2693     10922878 :     if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
    2694      9857916 :       bb->aux = bb->next_bb;
    2695      1064962 :   cfg_layout_finalize ();
    2696              : 
    2697     12176903 :   FOR_EACH_BB_FN (bb, fun)
    2698     11111941 :     df_recompute_luids (bb);
    2699      1064962 :   return 0;
    2700              : }
    2701              : 
    2702              : } // anon namespace
    2703              : 
    2704              : rtl_opt_pass *
    2705       297180 : make_pass_reorder_blocks (gcc::context *ctxt)
    2706              : {
    2707       297180 :   return new pass_reorder_blocks (ctxt);
    2708              : }
    2709              : 
    2710              : /* Return the unit of --param=max-goto-duplication-insns: the length of an
    2711              :    unconditional jump, or 1 if the target has no length attribute.  */
    2712              : 
    2713              : static int
    2714       924404 : duplication_unit (void)
    2715              : {
    2716       924404 :   if (!HAVE_ATTR_length)
    2717              :     return 1;
    2718              : 
    2719              :   /* We are estimating the length of uncond jump insn only once
    2720              :      since the code for getting the insn length always returns
    2721              :      the minimal length now.  */
    2722       924404 :   if (uncond_jump_length == 0)
    2723       112997 :     uncond_jump_length = get_uncond_jump_length ();
    2724              : 
    2725              :   /* A target with insn lengths gives a jump a nonzero length.  A zero unit
    2726              :      would make every budget 0, whatever the parameter says.  */
    2727       924404 :   gcc_checking_assert (uncond_jump_length > 0);
    2728       924404 :   return uncond_jump_length;
    2729              : }
    2730              : 
    2731              : /* Return the size of INSN in the units of duplication_unit: its minimum
    2732              :    length, or 1 for an active insn if the target has no length attribute.
    2733              :    Debug insns never count, so they cannot change the decision.  */
    2734              : 
    2735              : static int
    2736        82782 : duplication_size (rtx_insn *insn)
    2737              : {
    2738        82782 :   if (HAVE_ATTR_length)
    2739            0 :     return get_attr_min_length (insn);
    2740              :   return active_insn_p (insn);
    2741              : }
    2742              : 
    2743              : /* Return true if INSN is a jump whose predecessors are worth giving a copy
    2744              :    of their own.  Every transition through such a jump uses the same indirect
    2745              :    branch instruction, which can make indirect target prediction less
    2746              :    effective.  */
    2747              : 
    2748              : static bool
    2749     10615574 : dispatch_jump_p (rtx_insn *insn)
    2750              : {
    2751     10615574 :   if (computed_jump_p (insn))
    2752              :     return true;
    2753              : 
    2754              :   /* A switch lowered to a jump table dispatches exactly like a factored
    2755              :      computed goto.  Copying such a block makes the copies share the one
    2756              :      table, so only the branch is replicated, not the table.  The target
    2757              :      decides whether the dispatch can share its table.  Sharing a table in a
    2758              :      partitioned function would require explicit ownership of the section of
    2759              :      the base of the table entries.  */
    2760     10621752 :   if (!(flag_duplicate_switch_dispatch
    2761     10614675 :         && !crtl->has_bb_partition
    2762      8703392 :         && tablejump_p (insn, NULL, NULL)
    2763         6945 :         && targetm.can_share_jump_table_p (insn)))
    2764              :     return false;
    2765              : 
    2766              : #ifdef STACK_REGS
    2767              :   /* Stack-register conversion can split outgoing edges to reconcile stack
    2768              :      layouts.  Such edges cannot be redirected for one shared-table user.  */
    2769        59633 :   for (int regno = FIRST_STACK_REG; regno <= LAST_STACK_REG; ++regno)
    2770        53047 :     if (df_regs_ever_live_p (regno))
    2771              :       return false;
    2772              : #endif
    2773              : 
    2774              :   return true;
    2775              : }
    2776              : 
    2777              : /* Return true if a copy of the dispatch can be attached to the source of E,
    2778              :    taking over that edge.  */
    2779              : 
    2780              : static bool
    2781        18541 : can_attach_dispatch_copy_p (edge e)
    2782              : {
    2783        18541 :   basic_block pred = e->src;
    2784              : 
    2785        18541 :   return (single_succ_p (pred)
    2786         2488 :           && !(e->flags & EDGE_COMPLEX)
    2787         2488 :           && pred->index >= NUM_FIXED_BLOCKS
    2788        20513 :           && (!JUMP_P (BB_END (pred))
    2789          987 :               || (simplejump_p (BB_END (pred))
    2790          981 :                   && !CROSSING_JUMP_P (BB_END (pred)))));
    2791              : }
    2792              : 
    2793              : /* Return true if the fall-through edge E also stands for a branch, that is
    2794              :    if the jump at the end of its source names its destination as well.
    2795              :    Such an edge cannot move to a copy of its destination without changing
    2796              :    the jump.  */
    2797              : 
    2798              : static bool
    2799         9903 : fallthru_unified_with_branch_p (edge e)
    2800              : {
    2801         9903 :   rtx_insn *end = BB_END (e->src);
    2802         9903 :   return JUMP_P (end) && label_is_jump_target_p (BB_HEAD (e->dest), end);
    2803              : }
    2804              : 
    2805              : /* Collect into CHAIN the blocks that have to be copied together with the
    2806              :    dispatch block BB, innermost first, and return the head of the chain: the
    2807              :    block whose predecessors the copies are attached to.  Anything above the
    2808              :    dispatch is reached only through the chain, so copying the lot into a
    2809              :    predecessor of the head is sound.  The chain is what makes a jump table
    2810              :    dispatch reachable at all, since the range check that guards it sits in a
    2811              :    block of its own.  Return NULL if the chain is larger than MAX_SIZE, which
    2812              :    is in units of duplication_unit.  */
    2813              : 
    2814              : static basic_block
    2815         9315 : find_dispatch_chain (basic_block bb, int max_size,
    2816              :                      vec<basic_block> *chain)
    2817              : {
    2818         9315 :   int size = 0;
    2819              : 
    2820              :   /* Count a tablejump as one instruction.  Its target sequence is an
    2821              :      indivisible part of every copy, while the budget still bounds the work
    2822              :      copied with it.  */
    2823         9315 :   rtx_insn *dispatch = NULL;
    2824         9315 :   if (tablejump_p (BB_END (bb), NULL, NULL))
    2825         8323 :     dispatch = BB_END (bb);
    2826              : 
    2827        17546 :   for (basic_block b = bb; ; b = single_pred (b))
    2828              :     {
    2829        17546 :       rtx_insn *insn;
    2830       140897 :       FOR_BB_INSNS (b, insn)
    2831       128451 :         if (INSN_P (insn))
    2832              :           {
    2833       181604 :             size += (insn == dispatch
    2834        90802 :                      ? duplication_unit () : duplication_size (insn));
    2835        90802 :             if (size > max_size)
    2836         5100 :               return NULL;
    2837              :           }
    2838              : 
    2839        12446 :       chain->safe_push (b);
    2840              : 
    2841              :       /* Stop at the block the copies attach to, and at anything we may not
    2842              :          copy.  Only a jump table dispatch needs more than its own block, and
    2843              :          only a plain fall-through predecessor can be taken along: the copies
    2844              :          are laid out one after the other, so any other edge into the chain
    2845              :          would need a jump of its own, and a jump that also targets the next
    2846              :          block would still name the original block.  */
    2847        12446 :       if (!dispatch || !single_pred_p (b))
    2848              :         break;
    2849         9359 :       edge in = single_pred_edge (b);
    2850         9359 :       if (can_attach_dispatch_copy_p (in)
    2851         9356 :           || !(in->flags & EDGE_FALLTHRU)
    2852         8699 :           || in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
    2853         8237 :           || !can_duplicate_block_p (in->src)
    2854        17596 :           || fallthru_unified_with_branch_p (in))
    2855              :         break;
    2856         8231 :     }
    2857              : 
    2858         4215 :   return chain->last ();
    2859              : }
    2860              : 
    2861              : /* Duplicate the dispatch block BB, along with the blocks it can only be
    2862              :    reached through, into the predecessors of that chain, where possible.
    2863              :    MAX_SIZE limits the size of the chain, in units of duplication_unit.
    2864              :    If REQUIRE_BACK_EDGE is true, first require a DFS back edge into the head
    2865              :    of the chain.  Return whether anything is changed.  */
    2866              : static bool
    2867         9315 : maybe_duplicate_dispatch (basic_block bb, int max_size,
    2868              :                           bool require_back_edge)
    2869              : {
    2870         9315 :   auto_vec<basic_block, 4> chain;
    2871         9315 :   basic_block head = find_dispatch_chain (bb, max_size, &chain);
    2872         9315 :   if (!head)
    2873              :     return false;
    2874              : 
    2875         4215 :   if (require_back_edge)
    2876              :     {
    2877         3224 :       bool found = false;
    2878         3224 :       edge e;
    2879         3224 :       edge_iterator ei;
    2880        14938 :       FOR_EACH_EDGE (e, ei, head->preds)
    2881        12680 :         if (e->flags & EDGE_DFS_BACK)
    2882              :           {
    2883              :             found = true;
    2884              :             break;
    2885              :           }
    2886         3224 :       if (!found)
    2887         2258 :         return false;
    2888              :     }
    2889              : 
    2890         1957 :   bool changed = false;
    2891         1957 :   edge e;
    2892         1957 :   edge_iterator ei;
    2893        11139 :   for (ei = ei_start (head->preds); (e = ei_safe_edge (ei)); )
    2894              :     {
    2895         9182 :       basic_block pred = e->src;
    2896              : 
    2897              :       /* Do not duplicate the chain into PRED if we cannot merge a copy of
    2898              :          its head with PRED.  */
    2899         9182 :       if (!can_attach_dispatch_copy_p (e))
    2900              :         {
    2901         7220 :           ei_next (&ei);
    2902         7220 :           continue;
    2903              :         }
    2904              : 
    2905         1962 :       if (dump_file)
    2906           83 :         fprintf (dump_file, "Duplicating dispatch bb %d into bb %d\n",
    2907              :                  bb->index, pred->index);
    2908              : 
    2909              :       /* Remember if PRED can be duplicated; if so, the copy of the chain
    2910              :          merged with PRED can be duplicated as well.  */
    2911         1962 :       bool can_dup_more = can_duplicate_block_p (pred);
    2912              : 
    2913              :       /* Copy the chain head first, so that the copies end up in the
    2914              :          instruction stream in the order they are executed in.  Only the head
    2915              :          takes over the edge from PRED; the edges inside the chain are
    2916              :          fall-through and so are moved onto the copies directly.  */
    2917         1962 :       auto_vec<basic_block, 4> copies;
    2918         7552 :       for (unsigned i = chain.length (); i-- > 0; )
    2919              :         {
    2920         3628 :           basic_block copy;
    2921         3628 :           if (copies.is_empty ())
    2922         1962 :             copy = duplicate_block (chain[i], e, NULL);
    2923              :           else
    2924              :             {
    2925         1666 :               edge in = find_edge (copies.last (), chain[i]);
    2926         1666 :               gcc_checking_assert (!fallthru_unified_with_branch_p (in));
    2927         1666 :               profile_count count = in->count ();
    2928         1666 :               if (chain[i]->count < count)
    2929           15 :                 count = chain[i]->count;
    2930         1666 :               copy = duplicate_block (chain[i], NULL, NULL);
    2931         1666 :               copy->count = count;
    2932         1666 :               chain[i]->count -= count;
    2933         1666 :               redirect_edge_succ (in, copy);
    2934              :             }
    2935         3628 :           copies.safe_push (copy);
    2936              :         }
    2937              : 
    2938         1962 :       basic_block first = copies[0];
    2939         1962 :       basic_block last = copies.last ();
    2940              : 
    2941              :       /* Move the copies after PRED and fold the head into it.  */
    2942         1962 :       emit_barrier_after_bb (last);
    2943         1962 :       reorder_insns_nobb (BB_HEAD (first), BB_END (last), BB_END (pred));
    2944         1962 :       merge_blocks (pred, first);
    2945              : 
    2946              :       /* The rest of the chain stays as separate blocks that PRED falls
    2947              :          through to, so put them in the block order to match.  */
    2948         1962 :       basic_block after = pred;
    2949         5590 :       for (unsigned i = 1; i < copies.length (); i++)
    2950              :         {
    2951         1666 :           unlink_block (copies[i]);
    2952         1666 :           link_block (copies[i], after);
    2953         1666 :           after = copies[i];
    2954              :         }
    2955              : 
    2956         1962 :       changed = true;
    2957              : 
    2958              :       /* Try to merge the resulting dispatch block into further
    2959              :          predecessors.  */
    2960         1962 :       if (can_dup_more)
    2961         3593 :         maybe_duplicate_dispatch (first == last ? pred : last, max_size, false);
    2962         1962 :     }
    2963              : 
    2964              :   return changed;
    2965         9315 : }
    2966              : 
    2967              : /* Duplicate the blocks containing computed gotos.  This basically unfactors
    2968              :    computed gotos that were factored early on in the compilation process to
    2969              :    speed up edge based data flow.  We used to not unfactor them again, which
    2970              :    can seriously pessimize code with many computed jumps in the source code,
    2971              :    such as interpreters.  See e.g. PR15242.
    2972              : 
    2973              :    With -fduplicate-switch-dispatch the same is done for a switch lowered to
    2974              :    a jump table, which an interpreter written without the labels-as-values
    2975              :    extension ends up with.  See PR126236.  */
    2976              : static void
    2977       916384 : duplicate_computed_gotos (function *fun)
    2978              : {
    2979              :   /* Never copy a block larger than this.  */
    2980       916384 :   int max_size = duplication_unit () * param_max_goto_duplication_insns;
    2981              : 
    2982       916384 :   bool changed = false;
    2983       916384 :   bool back_edges_marked = false;
    2984              : 
    2985       916384 :   gcc_checking_assert (!(fun->curr_properties
    2986              :                          & PROP_rtl_allow_tablejump_duplication));
    2987       916384 :   fun->curr_properties |= PROP_rtl_allow_tablejump_duplication;
    2988              : 
    2989              :   /* Try to duplicate all blocks that end in a dispatching jump and that
    2990              :      can be duplicated at all.  */
    2991       916384 :   basic_block bb;
    2992     11531958 :   FOR_EACH_BB_FN (bb, fun)
    2993              :     {
    2994     10615574 :       if (!dispatch_jump_p (BB_END (bb))
    2995     10615574 :           || !can_duplicate_block_p (bb))
    2996     10608221 :         continue;
    2997              : 
    2998         7353 :       bool tablejump = tablejump_p (BB_END (bb), NULL, NULL);
    2999         7353 :       if (tablejump && !back_edges_marked)
    3000              :         {
    3001         4491 :           mark_dfs_back_edges ();
    3002         4491 :           back_edges_marked = true;
    3003              :         }
    3004              : 
    3005         7353 :       changed |= maybe_duplicate_dispatch (bb, max_size, tablejump);
    3006              :     }
    3007              : 
    3008       916384 :   fun->curr_properties &= ~PROP_rtl_allow_tablejump_duplication;
    3009              : 
    3010              :   /* Some blocks may have become unreachable.  */
    3011       916384 :   if (changed)
    3012          990 :     cleanup_cfg (0);
    3013              : 
    3014              :   /* Duplicating blocks will redirect edges and may cause hot blocks
    3015              :     previously reached by both hot and cold blocks to become dominated
    3016              :     only by cold blocks.  */
    3017          990 :   if (changed)
    3018          990 :     fixup_partitions ();
    3019       916384 : }
    3020              : 
    3021              : namespace {
    3022              : 
    3023              : const pass_data pass_data_duplicate_computed_gotos =
    3024              : {
    3025              :   RTL_PASS, /* type */
    3026              :   "compgotos", /* name */
    3027              :   OPTGROUP_NONE, /* optinfo_flags */
    3028              :   TV_DUP_COMPGOTO, /* tv_id */
    3029              :   0, /* properties_required */
    3030              :   0, /* properties_provided */
    3031              :   0, /* properties_destroyed */
    3032              :   0, /* todo_flags_start */
    3033              :   0, /* todo_flags_finish */
    3034              : };
    3035              : 
    3036              : class pass_duplicate_computed_gotos : public rtl_opt_pass
    3037              : {
    3038              : public:
    3039       297180 :   pass_duplicate_computed_gotos (gcc::context *ctxt)
    3040       594360 :     : rtl_opt_pass (pass_data_duplicate_computed_gotos, ctxt)
    3041              :   {}
    3042              : 
    3043              :   /* opt_pass methods: */
    3044              :   bool gate (function *) final override;
    3045              :   unsigned int execute (function *) final override;
    3046              : 
    3047              : }; // class pass_duplicate_computed_gotos
    3048              : 
    3049              : bool
    3050      1517135 : pass_duplicate_computed_gotos::gate (function *fun)
    3051              : {
    3052      1517135 :   if (targetm.cannot_modify_jumps_p ())
    3053              :     return false;
    3054      1517135 :   return (optimize > 0
    3055      1064964 :           && flag_expensive_optimizations
    3056      2499833 :           && ! optimize_function_for_size_p (fun));
    3057              : }
    3058              : 
    3059              : unsigned int
    3060       916384 : pass_duplicate_computed_gotos::execute (function *fun)
    3061              : {
    3062       916384 :   duplicate_computed_gotos (fun);
    3063              : 
    3064       916384 :   return 0;
    3065              : }
    3066              : 
    3067              : } // anon namespace
    3068              : 
    3069              : rtl_opt_pass *
    3070       297180 : make_pass_duplicate_computed_gotos (gcc::context *ctxt)
    3071              : {
    3072       297180 :   return new pass_duplicate_computed_gotos (ctxt);
    3073              : }
    3074              : 
    3075              : /* This function is the main 'entrance' for the optimization that
    3076              :    partitions hot and cold basic blocks into separate sections of the
    3077              :    .o file (to improve performance and cache locality).  Ideally it
    3078              :    would be called after all optimizations that rearrange the CFG have
    3079              :    been called.  However part of this optimization may introduce new
    3080              :    register usage, so it must be called before register allocation has
    3081              :    occurred.  This means that this optimization is actually called
    3082              :    well before the optimization that reorders basic blocks (see
    3083              :    function above).
    3084              : 
    3085              :    This optimization checks the feedback information to determine
    3086              :    which basic blocks are hot/cold, updates flags on the basic blocks
    3087              :    to indicate which section they belong in.  This information is
    3088              :    later used for writing out sections in the .o file.  Because hot
    3089              :    and cold sections can be arbitrarily large (within the bounds of
    3090              :    memory), far beyond the size of a single function, it is necessary
    3091              :    to fix up all edges that cross section boundaries, to make sure the
    3092              :    instructions used can actually span the required distance.  The
    3093              :    fixes are described below.
    3094              : 
    3095              :    Fall-through edges must be changed into jumps; it is not safe or
    3096              :    legal to fall through across a section boundary.  Whenever a
    3097              :    fall-through edge crossing a section boundary is encountered, a new
    3098              :    basic block is inserted (in the same section as the fall-through
    3099              :    source), and the fall through edge is redirected to the new basic
    3100              :    block.  The new basic block contains an unconditional jump to the
    3101              :    original fall-through target.  (If the unconditional jump is
    3102              :    insufficient to cross section boundaries, that is dealt with a
    3103              :    little later, see below).
    3104              : 
    3105              :    In order to deal with architectures that have short conditional
    3106              :    branches (which cannot span all of memory) we take any conditional
    3107              :    jump that attempts to cross a section boundary and add a level of
    3108              :    indirection: it becomes a conditional jump to a new basic block, in
    3109              :    the same section.  The new basic block contains an unconditional
    3110              :    jump to the original target, in the other section.
    3111              : 
    3112              :    For those architectures whose unconditional branch is also
    3113              :    incapable of reaching all of memory, those unconditional jumps are
    3114              :    converted into indirect jumps, through a register.
    3115              : 
    3116              :    IMPORTANT NOTE: This optimization causes some messy interactions
    3117              :    with the cfg cleanup optimizations; those optimizations want to
    3118              :    merge blocks wherever possible, and to collapse indirect jump
    3119              :    sequences (change "A jumps to B jumps to C" directly into "A jumps
    3120              :    to C").  Those optimizations can undo the jump fixes that
    3121              :    partitioning is required to make (see above), in order to ensure
    3122              :    that jumps attempting to cross section boundaries are really able
    3123              :    to cover whatever distance the jump requires (on many architectures
    3124              :    conditional or unconditional jumps are not able to reach all of
    3125              :    memory).  Therefore tests have to be inserted into each such
    3126              :    optimization to make sure that it does not undo stuff necessary to
    3127              :    cross partition boundaries.  This would be much less of a problem
    3128              :    if we could perform this optimization later in the compilation, but
    3129              :    unfortunately the fact that we may need to create indirect jumps
    3130              :    (through registers) requires that this optimization be performed
    3131              :    before register allocation.
    3132              : 
    3133              :    Hot and cold basic blocks are partitioned and put in separate
    3134              :    sections of the .o file, to reduce paging and improve cache
    3135              :    performance (hopefully).  This can result in bits of code from the
    3136              :    same function being widely separated in the .o file.  However this
    3137              :    is not obvious to the current bb structure.  Therefore we must take
    3138              :    care to ensure that: 1). There are no fall_thru edges that cross
    3139              :    between sections; 2). For those architectures which have "short"
    3140              :    conditional branches, all conditional branches that attempt to
    3141              :    cross between sections are converted to unconditional branches;
    3142              :    and, 3). For those architectures which have "short" unconditional
    3143              :    branches, all unconditional branches that attempt to cross between
    3144              :    sections are converted to indirect jumps.
    3145              : 
    3146              :    The code for fixing up fall_thru edges that cross between hot and
    3147              :    cold basic blocks does so by creating new basic blocks containing
    3148              :    unconditional branches to the appropriate label in the "other"
    3149              :    section.  The new basic block is then put in the same (hot or cold)
    3150              :    section as the original conditional branch, and the fall_thru edge
    3151              :    is modified to fall into the new basic block instead.  By adding
    3152              :    this level of indirection we end up with only unconditional branches
    3153              :    crossing between hot and cold sections.
    3154              : 
    3155              :    Conditional branches are dealt with by adding a level of indirection.
    3156              :    A new basic block is added in the same (hot/cold) section as the
    3157              :    conditional branch, and the conditional branch is retargeted to the
    3158              :    new basic block.  The new basic block contains an unconditional branch
    3159              :    to the original target of the conditional branch (in the other section).
    3160              : 
    3161              :    Unconditional branches are dealt with by converting them into
    3162              :    indirect jumps.  */
    3163              : 
    3164              : namespace {
    3165              : 
    3166              : const pass_data pass_data_partition_blocks =
    3167              : {
    3168              :   RTL_PASS, /* type */
    3169              :   "bbpart", /* name */
    3170              :   OPTGROUP_NONE, /* optinfo_flags */
    3171              :   TV_REORDER_BLOCKS, /* tv_id */
    3172              :   PROP_cfglayout, /* properties_required */
    3173              :   0, /* properties_provided */
    3174              :   0, /* properties_destroyed */
    3175              :   0, /* todo_flags_start */
    3176              :   0, /* todo_flags_finish */
    3177              : };
    3178              : 
    3179              : class pass_partition_blocks : public rtl_opt_pass
    3180              : {
    3181              : public:
    3182       297180 :   pass_partition_blocks (gcc::context *ctxt)
    3183       594360 :     : rtl_opt_pass (pass_data_partition_blocks, ctxt)
    3184              :   {}
    3185              : 
    3186              :   /* opt_pass methods: */
    3187              :   bool gate (function *) final override;
    3188              :   unsigned int execute (function *) final override;
    3189              : 
    3190              : }; // class pass_partition_blocks
    3191              : 
    3192              : bool
    3193      1517135 : pass_partition_blocks::gate (function *fun)
    3194              : {
    3195              :   /* The optimization to partition hot/cold basic blocks into separate
    3196              :      sections of the .o file does not work well with linkonce or with
    3197              :      user defined section attributes or with naked attribute.  Don't call
    3198              :      it if either case arises.  */
    3199      1517135 :   return (flag_reorder_blocks_and_partition
    3200       742154 :           && optimize
    3201              :           /* See pass_reorder_blocks::gate.  We should not partition if
    3202              :              we are going to omit the reordering.  */
    3203       742122 :           && optimize_function_for_speed_p (fun)
    3204       691353 :           && !DECL_COMDAT_GROUP (current_function_decl)
    3205       582463 :           && !lookup_attribute ("section", DECL_ATTRIBUTES (fun->decl))
    3206       582417 :           && !lookup_attribute ("naked", DECL_ATTRIBUTES (fun->decl))
    3207              :           /* Workaround a bug in GDB where read_partial_die doesn't cope
    3208              :              with DIEs with DW_AT_ranges, see PR81115.  */
    3209      2099503 :           && !(in_lto_p && MAIN_NAME_P (DECL_NAME (fun->decl))));
    3210              : }
    3211              : 
    3212              : unsigned
    3213       572432 : pass_partition_blocks::execute (function *fun)
    3214              : {
    3215       572432 :   vec<edge> crossing_edges;
    3216              : 
    3217       572432 :   if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
    3218              :     return 0;
    3219              : 
    3220       270447 :   df_set_flags (DF_DEFER_INSN_RESCAN);
    3221              : 
    3222       270447 :   crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
    3223       270447 :   if (!crossing_edges.exists ())
    3224              :     /* Make sure to process deferred rescans and clear changeable df flags.  */
    3225              :     return TODO_df_finish;
    3226              : 
    3227        65368 :   crtl->has_bb_partition = true;
    3228              : 
    3229              :   /* Make sure the source of any crossing edge ends in a jump and the
    3230              :      destination of any crossing edge has a label.  */
    3231        65368 :   add_labels_and_missing_jumps (crossing_edges);
    3232              : 
    3233              :   /* Convert all crossing fall_thru edges to non-crossing fall
    3234              :      thrus to unconditional jumps (that jump to the original fall
    3235              :      through dest).  */
    3236        65368 :   fix_up_fall_thru_edges ();
    3237              : 
    3238              :   /* If the architecture does not have conditional branches that can
    3239              :      span all of memory, convert crossing conditional branches into
    3240              :      crossing unconditional branches.  */
    3241        65368 :   if (!HAS_LONG_COND_BRANCH)
    3242              :     fix_crossing_conditional_branches ();
    3243              : 
    3244              :   /* If the architecture does not have unconditional branches that
    3245              :      can span all of memory, convert crossing unconditional branches
    3246              :      into indirect jumps.  Since adding an indirect jump also adds
    3247              :      a new register usage, update the register usage information as
    3248              :      well.  */
    3249        65368 :   if (!HAS_LONG_UNCOND_BRANCH)
    3250              :     fix_crossing_unconditional_branches ();
    3251              : 
    3252        65368 :   update_crossing_jump_flags ();
    3253              : 
    3254              :   /* Clear bb->aux fields that the above routines were using.  */
    3255        65368 :   clear_aux_for_blocks ();
    3256              : 
    3257        65368 :   crossing_edges.release ();
    3258              : 
    3259              :   /* ??? FIXME: DF generates the bb info for a block immediately.
    3260              :      And by immediately, I mean *during* creation of the block.
    3261              : 
    3262              :         #0  df_bb_refs_collect
    3263              :         #1  in df_bb_refs_record
    3264              :         #2  in create_basic_block_structure
    3265              : 
    3266              :      Which means that the bb_has_eh_pred test in df_bb_refs_collect
    3267              :      will *always* fail, because no edges can have been added to the
    3268              :      block yet.  Which of course means we don't add the right
    3269              :      artificial refs, which means we fail df_verify (much) later.
    3270              : 
    3271              :      Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
    3272              :      that we also shouldn't grab data from the new blocks those new
    3273              :      insns are in either.  In this way one can create the block, link
    3274              :      it up properly, and have everything Just Work later, when deferred
    3275              :      insns are processed.
    3276              : 
    3277              :      In the meantime, we have no other option but to throw away all
    3278              :      of the DF data and recompute it all.  */
    3279        65368 :   if (fun->eh->lp_array)
    3280              :     {
    3281        65368 :       df_finish_pass (true);
    3282        65368 :       df_scan_alloc (NULL);
    3283        65368 :       df_scan_blocks ();
    3284              :       /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
    3285              :          data.  We blindly generated all of them when creating the new
    3286              :          landing pad.  Delete those assignments we don't use.  */
    3287        65368 :       df_set_flags (DF_LR_RUN_DCE);
    3288        65368 :       df_analyze ();
    3289              :     }
    3290              : 
    3291              :   /* Make sure to process deferred rescans and clear changeable df flags.  */
    3292              :   return TODO_df_finish;
    3293              : }
    3294              : 
    3295              : } // anon namespace
    3296              : 
    3297              : rtl_opt_pass *
    3298       297180 : make_pass_partition_blocks (gcc::context *ctxt)
    3299              : {
    3300       297180 :   return new pass_partition_blocks (ctxt);
    3301              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.