/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2000-2014 Free Software Foundation, Inc.
This file is part of GCC.
/* This (greedy) algorithm constructs traces in several rounds.
The construction starts from "seeds". The seed for the first round
- is the entry point of function. When there are more than one seed
- that one is selected first that has the lowest key in the heap
- (see function bb_to_key). Then the algorithm repeatedly adds the most
- probable successor to the end of a trace. Finally it connects the traces.
+ is the entry point of the function. When there are more than one seed,
+ the one with the lowest key in the heap is selected first (see bb_to_key).
+ Then the algorithm repeatedly adds the most probable successor to the end
+ of a trace. Finally it connects the traces.
There are two parameters: Branch Threshold and Exec Threshold.
- If the edge to a successor of the actual basic block is lower than
- Branch Threshold or the frequency of the successor is lower than
- Exec Threshold the successor will be the seed in one of the next rounds.
+ If the probability of an edge to a successor of the current basic block is
+ lower than Branch Threshold or its frequency is lower than Exec Threshold,
+ then the successor will be the seed in one of the next rounds.
Each round has these parameters lower than the previous one.
- The last round has to have these parameters set to zero
- so that the remaining blocks are picked up.
+ The last round has to have these parameters set to zero so that the
+ remaining blocks are picked up.
The algorithm selects the most probable successor from all unvisited
successors and successors that have been added to this trace.
The other successors (that has not been "sent" to the next round) will be
- other seeds for this round and the secondary traces will start in them.
- If the successor has not been visited in this trace it is added to the trace
- (however, there is some heuristic for simple branches).
- If the successor has been visited in this trace the loop has been found.
- If the loop has many iterations the loop is rotated so that the
- source block of the most probable edge going out from the loop
- is the last block of the trace.
+ other seeds for this round and the secondary traces will start from them.
+ If the successor has not been visited in this trace, it is added to the
+ trace (however, there is some heuristic for simple branches).
+ If the successor has been visited in this trace, a loop has been found.
+ If the loop has many iterations, the loop is rotated so that the source
+ block of the most probable edge going out of the loop is the last block
+ of the trace.
If the loop has few iterations and there is no edge from the last block of
- the loop going out from loop the loop header is duplicated.
- Finally, the construction of the trace is terminated.
+ the loop going out of the loop, the loop header is duplicated.
- When connecting traces it first checks whether there is an edge from the
- last block of one trace to the first block of another trace.
+ When connecting traces, the algorithm first checks whether there is an edge
+ from the last block of a trace to the first block of another trace.
When there are still some unconnected traces it checks whether there exists
- a basic block BB such that BB is a successor of the last bb of one trace
- and BB is a predecessor of the first block of another trace. In this case,
- BB is duplicated and the traces are connected through this duplicate.
+ a basic block BB such that BB is a successor of the last block of a trace
+ and BB is a predecessor of the first block of another trace. In this case,
+ BB is duplicated, added at the end of the first trace and the traces are
+ connected through it.
The rest of traces are simply connected so there will be a jump to the
- beginning of the rest of trace.
-
+ beginning of the rest of traces.
+
+ The above description is for the full algorithm, which is used when the
+ function is optimized for speed. When the function is optimized for size,
+ in order to reduce long jumps and connect more fallthru edges, the
+ algorithm is modified as follows:
+ (1) Break long traces to short ones. A trace is broken at a block that has
+ multiple predecessors/ successors during trace discovery. When connecting
+ traces, only connect Trace n with Trace n + 1. This change reduces most
+ long jumps compared with the above algorithm.
+ (2) Ignore the edge probability and frequency for fallthru edges.
+ (3) Keep the original order of blocks when there is no chance to fall
+ through. We rely on the results of cfg_cleanup.
+
+ To implement the change for code size optimization, block's index is
+ selected as the key and all traces are found in one round.
References:
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "tree.h"
#include "rtl.h"
#include "regs.h"
#include "flags.h"
-#include "timevar.h"
#include "output.h"
-#include "cfglayout.h"
#include "fibheap.h"
#include "target.h"
#include "function.h"
/* The number of rounds. In most cases there will only be 4 rounds, but
when partitioning hot and cold basic blocks into separate sections of
- the .o file there will be an extra round.*/
+ the object file there will be an extra round. */
#define N_ROUNDS 5
/* Stubs in case we don't have a return insn.
- We have to check at runtime too, not only compiletime. */
+ We have to check at run time too, not only compile time. */
#ifndef HAVE_return
#define HAVE_return 0
(this_target_bb_reorder->x_uncond_jump_length)
/* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
-static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
+static const int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
/* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
-static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
+static const int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
/* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
block the edge destination is not duplicated while connecting traces. */
/* Structure to hold needed information for each basic block. */
typedef struct bbro_basic_block_data_def
{
- /* Which trace is the bb start of (-1 means it is not a start of a trace). */
+ /* Which trace is the bb start of (-1 means it is not a start of any). */
int start_of_trace;
- /* Which trace is the bb end of (-1 means it is not an end of a trace). */
+ /* Which trace is the bb end of (-1 means it is not an end of any). */
int end_of_trace;
/* Which trace is the bb in? */
int in_trace;
+ /* Which trace was this bb visited in? */
+ int visited;
+
/* Which heap is BB in (if any)? */
fibheap_t heap;
int, fibheap_t *, int);
static basic_block copy_bb (basic_block, edge, basic_block, int);
static fibheapkey_t bb_to_key (basic_block);
-static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge);
+static bool better_edge_p (const_basic_block, const_edge, int, int, int, int,
+ const_edge);
+static bool connect_better_edge_p (const_edge, bool, int, const_edge,
+ struct trace *);
static void connect_traces (int, struct trace *);
static bool copy_bb_p (const_basic_block, int);
-static int get_uncond_jump_length (void);
static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
\f
+/* Return the trace number in which BB was visited. */
+
+static int
+bb_visited_trace (const_basic_block bb)
+{
+ gcc_assert (bb->index < array_size);
+ return bbd[bb->index].visited;
+}
+
+/* This function marks BB that it was visited in trace number TRACE. */
+
+static void
+mark_bb_visited (basic_block bb, int trace)
+{
+ bbd[bb->index].visited = trace;
+ if (bbd[bb->index].heap)
+ {
+ fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
+ bbd[bb->index].heap = NULL;
+ bbd[bb->index].node = NULL;
+ }
+}
+
/* Check to see if bb should be pushed into the next round of trace
collections or not. Reasons for pushing the block forward are 1).
If the block is cold, we are doing partitioning, and there will be
block_not_hot_enough = (bb->frequency < exec_th
|| bb->count < count_th
- || probably_never_executed_bb_p (bb));
+ || probably_never_executed_bb_p (cfun, bb));
if (there_exists_another_round
&& block_not_hot_enough)
heap = fibheap_new ();
max_entry_frequency = 0;
max_entry_count = 0;
- FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
{
bbd[e->dest->index].heap = heap;
bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
basic_block bb;
fprintf (dump_file, "Trace %d (round %d): ", i + 1,
traces[i].round + 1);
- for (bb = traces[i].first; bb != traces[i].last; bb = (basic_block) bb->aux)
+ for (bb = traces[i].first;
+ bb != traces[i].last;
+ bb = (basic_block) bb->aux)
fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
}
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->dest != EXIT_BLOCK_PTR
- && e->dest->il.rtl->visited != trace_n
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
+ && bb_visited_trace (e->dest) != trace_n
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX))
{
if (is_preferred)
{
/* The best edge is preferred. */
- if (!e->dest->il.rtl->visited
+ if (!bb_visited_trace (e->dest)
|| bbd[e->dest->index].start_of_trace >= 0)
{
/* The current edge E is also preferred. */
}
else
{
- if (!e->dest->il.rtl->visited
+ if (!bb_visited_trace (e->dest)
|| bbd[e->dest->index].start_of_trace >= 0)
{
/* The current edge E is preferred. */
return best_bb;
}
-/* This function marks BB that it was visited in trace number TRACE. */
-
-static void
-mark_bb_visited (basic_block bb, int trace)
-{
- bb->il.rtl->visited = trace;
- if (bbd[bb->index].heap)
- {
- fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
- bbd[bb->index].heap = NULL;
- bbd[bb->index].node = NULL;
- }
-}
-
-/* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
- not include basic blocks their probability is lower than BRANCH_TH or their
- frequency is lower than EXEC_TH into traces (or count is lower than
- COUNT_TH). It stores the new traces into TRACES and modifies the number of
- traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
- expects that starting basic blocks are in *HEAP and at the end it deletes
- *HEAP and stores starting points for the next round into new *HEAP. */
+/* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
+ not include basic blocks whose probability is lower than BRANCH_TH or whose
+ frequency is lower than EXEC_TH into traces (or whose count is lower than
+ COUNT_TH). Store the new traces into TRACES and modify the number of
+ traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
+ The function expects starting basic blocks to be in *HEAP and will delete
+ *HEAP and store starting points for the next round into new *HEAP. */
static void
find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
/* Heap for discarded basic blocks which are possible starting points for
the next round. */
fibheap_t new_heap = fibheap_new ();
+ bool for_size = optimize_function_for_size_p (cfun);
while (!fibheap_empty (*heap))
{
if (dump_file)
fprintf (dump_file, "Getting bb %d\n", bb->index);
- /* If the BB's frequency is too low send BB to the next round. When
+ /* If the BB's frequency is too low, send BB to the next round. When
partitioning hot/cold blocks into separate sections, make sure all
the cold blocks (and ONLY the cold blocks) go into the (extra) final
- round. */
+ round. When optimizing for size, do not push to next round. */
- if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
- count_th))
+ if (!for_size
+ && push_to_next_round_p (bb, round, number_of_rounds, exec_th,
+ count_th))
{
int key = bb_to_key (bb);
bbd[bb->index].heap = new_heap;
{
gcc_assert (!(e->flags & EDGE_FAKE));
- if (e->dest == EXIT_BLOCK_PTR)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
- if (e->dest->il.rtl->visited
- && e->dest->il.rtl->visited != *n_traces)
+ if (bb_visited_trace (e->dest)
+ && bb_visited_trace (e->dest) != *n_traces)
continue;
if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
}
/* Edge that cannot be fallthru or improbable or infrequent
- successor (i.e. it is unsuitable successor). */
+ successor (i.e. it is unsuitable successor). When optimizing
+ for size, ignore the probability and frequency. */
if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
- || prob < branch_th || EDGE_FREQUENCY (e) < exec_th
- || e->count < count_th)
+ || ((prob < branch_th || EDGE_FREQUENCY (e) < exec_th
+ || e->count < count_th) && (!for_size)))
continue;
/* If partitioning hot/cold basic blocks, don't consider edges
&& copy_bb_p (best_edge->dest, 0))
best_edge = NULL;
+ /* If the best destination has multiple successors or predecessors,
+ don't allow it to be added when optimizing for size. This makes
+ sure predecessors with smaller index are handled before the best
+ destinarion. It breaks long trace and reduces long jumps.
+
+ Take if-then-else as an example.
+ A
+ / \
+ B C
+ \ /
+ D
+ If we do not remove the best edge B->D/C->D, the final order might
+ be A B D ... C. C is at the end of the program. If D's successors
+ and D are complicated, might need long jumps for A->C and C->D.
+ Similar issue for order: A C D ... B.
+
+ After removing the best edge, the final result will be ABCD/ ACBD.
+ It does not add jump compared with the previous order. But it
+ reduces the possibility of long jumps. */
+ if (best_edge && for_size
+ && (EDGE_COUNT (best_edge->dest->succs) > 1
+ || EDGE_COUNT (best_edge->dest->preds) > 1))
+ best_edge = NULL;
+
/* Add all non-selected successors to the heaps. */
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e == best_edge
- || e->dest == EXIT_BLOCK_PTR
- || e->dest->il.rtl->visited)
+ || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
+ || bb_visited_trace (e->dest))
continue;
key = bb_to_key (e->dest);
{
/* When partitioning hot/cold basic blocks, make sure
the cold blocks (and only the cold blocks) all get
- pushed to the last round of trace collection. */
+ pushed to the last round of trace collection. When
+ optimizing for size, do not push to next round. */
- if (push_to_next_round_p (e->dest, round,
- number_of_rounds,
- exec_th, count_th))
+ if (!for_size && push_to_next_round_p (e->dest, round,
+ number_of_rounds,
+ exec_th, count_th))
which_heap = new_heap;
}
if (best_edge) /* Suitable successor was found. */
{
- if (best_edge->dest->il.rtl->visited == *n_traces)
+ if (bb_visited_trace (best_edge->dest) == *n_traces)
{
/* We do nothing with one basic block loops. */
if (best_edge->dest != bb)
header is not the first block of the function
we can rotate the loop. */
- if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
+ if (best_edge->dest
+ != ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
{
if (dump_file)
{
if (single_succ_p (bb)
&& copy_bb_p (best_edge->dest,
- optimize_edge_for_speed_p (best_edge)))
+ optimize_edge_for_speed_p
+ (best_edge)))
{
bb = copy_bb (best_edge->dest, best_edge, bb,
*n_traces);
(i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
Best ordering is then A B C.
+ When optimizing for size, A B C is always the best order.
+
This situation is created for example by:
if (A) B;
if (e != best_edge
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
- && !e->dest->il.rtl->visited
+ && !bb_visited_trace (e->dest)
&& single_pred_p (e->dest)
&& !(e->flags & EDGE_CROSSING)
&& single_succ_p (e->dest)
& EDGE_CAN_FALLTHRU)
&& !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
&& single_succ (e->dest) == best_edge->dest
- && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
+ && (2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge)
+ || for_size))
{
best_edge = e;
if (dump_file)
is an end of the trace). */
FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (e->dest == EXIT_BLOCK_PTR
- || e->dest->il.rtl->visited)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
+ || bb_visited_trace (e->dest))
continue;
if (bbd[e->dest->index].heap)
BB_COPY_PARTITION (new_bb, old_bb);
gcc_assert (e->dest == new_bb);
- gcc_assert (!e->dest->il.rtl->visited);
if (dump_file)
fprintf (dump_file,
"Duplicated bb %d (created bb %d)\n",
old_bb->index, new_bb->index);
- new_bb->il.rtl->visited = trace;
- new_bb->aux = bb->aux;
- bb->aux = new_bb;
- if (new_bb->index >= array_size || last_basic_block > array_size)
+ if (new_bb->index >= array_size
+ || last_basic_block_for_fn (cfun) > array_size)
{
int i;
int new_size;
- new_size = MAX (last_basic_block, new_bb->index + 1);
+ new_size = MAX (last_basic_block_for_fn (cfun), new_bb->index + 1);
new_size = GET_ARRAY_SIZE (new_size);
bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
for (i = array_size; i < new_size; i++)
{
bbd[i].start_of_trace = -1;
- bbd[i].in_trace = -1;
bbd[i].end_of_trace = -1;
+ bbd[i].in_trace = -1;
+ bbd[i].visited = 0;
bbd[i].heap = NULL;
bbd[i].node = NULL;
}
}
}
+ gcc_assert (!bb_visited_trace (e->dest));
+ mark_bb_visited (new_bb, trace);
+ new_bb->aux = bb->aux;
+ bb->aux = new_bb;
+
bbd[new_bb->index].in_trace = trace;
return new_bb;
edge_iterator ei;
int priority = 0;
+ /* Use index as key to align with its original order. */
+ if (optimize_function_for_size_p (cfun))
+ return bb->index;
+
/* Do not start in probably never executed blocks. */
if (BB_PARTITION (bb) == BB_COLD_PARTITION
- || probably_never_executed_bb_p (bb))
+ || probably_never_executed_bb_p (cfun, bb))
return BB_FREQ_MAX;
/* Prefer blocks whose predecessor is an end of some trace
or whose predecessor edge is EDGE_DFS_BACK. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
- if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
+ if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ && bbd[e->src->index].end_of_trace >= 0)
|| (e->flags & EDGE_DFS_BACK))
{
int edge_freq = EDGE_FREQUENCY (e);
if (priority)
/* The block with priority should have significantly lower key. */
return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
+
return -bb->frequency;
}
BEST_PROB; similarly for frequency. */
static bool
-better_edge_p (const_basic_block bb, const_edge e, int prob, int freq, int best_prob,
- int best_freq, const_edge cur_best_edge)
+better_edge_p (const_basic_block bb, const_edge e, int prob, int freq,
+ int best_prob, int best_freq, const_edge cur_best_edge)
{
bool is_better_edge;
int diff_prob = best_prob / 10;
int diff_freq = best_freq / 10;
+ /* The smaller one is better to keep the original order. */
+ if (optimize_function_for_size_p (cfun))
+ return !cur_best_edge
+ || cur_best_edge->dest->index > e->dest->index;
+
if (prob > best_prob + diff_prob)
/* The edge has higher probability than the temporary best edge. */
is_better_edge = true;
return is_better_edge;
}
+/* Return true when the edge E is better than the temporary best edge
+ CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
+ E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
+ BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
+ TRACES record the information about traces.
+ When optimizing for size, the edge with smaller index is better.
+ When optimizing for speed, the edge with bigger probability or longer trace
+ is better. */
+
+static bool
+connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
+ const_edge cur_best_edge, struct trace *traces)
+{
+ int e_index;
+ int b_index;
+ bool is_better_edge;
+
+ if (!cur_best_edge)
+ return true;
+
+ if (optimize_function_for_size_p (cfun))
+ {
+ e_index = src_index_p ? e->src->index : e->dest->index;
+ b_index = src_index_p ? cur_best_edge->src->index
+ : cur_best_edge->dest->index;
+ /* The smaller one is better to keep the original order. */
+ return b_index > e_index;
+ }
+
+ if (src_index_p)
+ {
+ e_index = e->src->index;
+
+ if (e->probability > cur_best_edge->probability)
+ /* The edge has higher probability than the temporary best edge. */
+ is_better_edge = true;
+ else if (e->probability < cur_best_edge->probability)
+ /* The edge has lower probability than the temporary best edge. */
+ is_better_edge = false;
+ else if (traces[bbd[e_index].end_of_trace].length > best_len)
+ /* The edge and the temporary best edge have equivalent probabilities.
+ The edge with longer trace is better. */
+ is_better_edge = true;
+ else
+ is_better_edge = false;
+ }
+ else
+ {
+ e_index = e->dest->index;
+
+ if (e->probability > cur_best_edge->probability)
+ /* The edge has higher probability than the temporary best edge. */
+ is_better_edge = true;
+ else if (e->probability < cur_best_edge->probability)
+ /* The edge has lower probability than the temporary best edge. */
+ is_better_edge = false;
+ else if (traces[bbd[e_index].start_of_trace].length > best_len)
+ /* The edge and the temporary best edge have equivalent probabilities.
+ The edge with longer trace is better. */
+ is_better_edge = true;
+ else
+ is_better_edge = false;
+ }
+
+ return is_better_edge;
+}
+
/* Connect traces in array TRACES, N_TRACES is the count of traces. */
static void
int current_partition;
int freq_threshold;
gcov_type count_threshold;
+ bool for_size = optimize_function_for_size_p (cfun);
freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
if (max_entry_count < INT_MAX / 1000)
current_partition = BB_PARTITION (traces[0].first);
two_passes = false;
- if (flag_reorder_blocks_and_partition)
+ if (crtl->has_bb_partition)
for (i = 0; i < n_traces && !two_passes; i++)
if (BB_PARTITION (traces[0].first)
!= BB_PARTITION (traces[i].first))
{
int si = e->src->index;
- if (e->src != ENTRY_BLOCK_PTR
+ if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
&& bbd[si].end_of_trace >= 0
&& !connected[bbd[si].end_of_trace]
&& (BB_PARTITION (e->src) == current_partition)
- && (!best
- || e->probability > best->probability
- || (e->probability == best->probability
- && traces[bbd[si].end_of_trace].length > best_len)))
+ && connect_better_edge_p (e, true, best_len, best, traces))
{
best = e;
best_len = traces[bbd[si].end_of_trace].length;
{
int di = e->dest->index;
- if (e->dest != EXIT_BLOCK_PTR
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
&& bbd[di].start_of_trace >= 0
&& !connected[bbd[di].start_of_trace]
&& (BB_PARTITION (e->dest) == current_partition)
- && (!best
- || e->probability > best->probability
- || (e->probability == best->probability
- && traces[bbd[di].start_of_trace].length > best_len)))
+ && connect_better_edge_p (e, false, best_len, best, traces))
{
best = e;
best_len = traces[bbd[di].start_of_trace].length;
}
}
- if (best)
+ if (for_size)
+ {
+ if (!best)
+ /* Stop finding the successor traces. */
+ break;
+
+ /* It is OK to connect block n with block n + 1 or a block
+ before n. For others, only connect to the loop header. */
+ if (best->dest->index > (traces[t].last->index + 1))
+ {
+ int count = EDGE_COUNT (best->dest->preds);
+
+ FOR_EACH_EDGE (e, ei, best->dest->preds)
+ if (e->flags & EDGE_DFS_BACK)
+ count--;
+
+ /* If dest has multiple predecessors, skip it. We expect
+ that one predecessor with smaller index connects with it
+ later. */
+ if (count != 1)
+ break;
+ }
+
+ /* Only connect Trace n with Trace n + 1. It is conservative
+ to keep the order as close as possible to the original order.
+ It also helps to reduce long jumps. */
+ if (last_trace != bbd[best->dest->index].start_of_trace - 1)
+ break;
+
+ if (dump_file)
+ fprintf (dump_file, "Connection: %d %d\n",
+ best->src->index, best->dest->index);
+
+ t = bbd[best->dest->index].start_of_trace;
+ traces[last_trace].last->aux = traces[t].first;
+ connected[t] = true;
+ last_trace = t;
+ }
+ else if (best)
{
if (dump_file)
{
bool try_copy = false;
FOR_EACH_EDGE (e, ei, traces[t].last->succs)
- if (e->dest != EXIT_BLOCK_PTR
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
&& (!best || e->probability > best->probability))
{
int di = e2->dest->index;
- if (e2->dest == EXIT_BLOCK_PTR
+ if (e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
|| ((e2->flags & EDGE_CAN_FALLTHRU)
&& !(e2->flags & EDGE_COMPLEX)
&& bbd[di].start_of_trace >= 0
&& !connected[bbd[di].start_of_trace]
- && (BB_PARTITION (e2->dest) == current_partition)
- && (EDGE_FREQUENCY (e2) >= freq_threshold)
- && (e2->count >= count_threshold)
+ && BB_PARTITION (e2->dest) == current_partition
+ && EDGE_FREQUENCY (e2) >= freq_threshold
+ && e2->count >= count_threshold
&& (!best2
|| e2->probability > best2->probability
|| (e2->probability == best2->probability
{
best = e;
best2 = e2;
- if (e2->dest != EXIT_BLOCK_PTR)
+ if (e2->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
best2_len = traces[bbd[di].start_of_trace].length;
else
best2_len = INT_MAX;
}
}
- if (flag_reorder_blocks_and_partition)
+ if (crtl->has_bb_partition)
try_copy = false;
/* Copy tiny blocks always; copy larger blocks only when the
traces[t].last->index, best->dest->index);
if (!next_bb)
fputc ('\n', dump_file);
- else if (next_bb == EXIT_BLOCK_PTR)
+ else if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
fprintf (dump_file, "exit\n");
else
fprintf (dump_file, "%d\n", next_bb->index);
new_bb = copy_bb (best->dest, best, traces[t].last, t);
traces[t].last = new_bb;
- if (next_bb && next_bb != EXIT_BLOCK_PTR)
+ if (next_bb && next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
{
t = bbd[next_bb->index].start_of_trace;
traces[last_trace].last->aux = traces[t].first;
/* Return the length of unconditional jump instruction. */
-static int
+int
get_uncond_jump_length (void)
{
rtx label, jump;
return length;
}
-/* Emit a barrier into the footer of BB. */
-
-static void
-emit_barrier_after_bb (basic_block bb)
-{
- rtx barrier = emit_barrier_after (BB_END (bb));
- bb->il.rtl->footer = unlink_insn_chain (barrier, barrier);
-}
-
/* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
Duplicate the landing pad and split the edges so that no EH edge
crosses partitions. */
JUMP_LABEL (jump) = post_label;
/* Create new basic block to be dest for lp. */
- last_bb = EXIT_BLOCK_PTR->prev_bb;
+ last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
new_bb = create_basic_block (new_label, jump, last_bb);
new_bb->aux = last_bb->aux;
last_bb->aux = new_bb;
ei_next (&ei);
}
+
+/* Ensure that all hot bbs are included in a hot path through the
+ procedure. This is done by calling this function twice, once
+ with WALK_UP true (to look for paths from the entry to hot bbs) and
+ once with WALK_UP false (to look for paths from hot bbs to the exit).
+ Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
+ to BBS_IN_HOT_PARTITION. */
+
+static unsigned int
+sanitize_hot_paths (bool walk_up, unsigned int cold_bb_count,
+ vec<basic_block> *bbs_in_hot_partition)
+{
+ /* Callers check this. */
+ gcc_checking_assert (cold_bb_count);
+
+ /* Keep examining hot bbs while we still have some left to check
+ and there are remaining cold bbs. */
+ vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy ();
+ while (! hot_bbs_to_check.is_empty ()
+ && cold_bb_count)
+ {
+ basic_block bb = hot_bbs_to_check.pop ();
+ vec<edge, va_gc> *edges = walk_up ? bb->preds : bb->succs;
+ edge e;
+ edge_iterator ei;
+ int highest_probability = 0;
+ int highest_freq = 0;
+ gcov_type highest_count = 0;
+ bool found = false;
+
+ /* Walk the preds/succs and check if there is at least one already
+ marked hot. Keep track of the most frequent pred/succ so that we
+ can mark it hot if we don't find one. */
+ FOR_EACH_EDGE (e, ei, edges)
+ {
+ basic_block reach_bb = walk_up ? e->src : e->dest;
+
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+
+ if (BB_PARTITION (reach_bb) != BB_COLD_PARTITION)
+ {
+ found = true;
+ break;
+ }
+ /* The following loop will look for the hottest edge via
+ the edge count, if it is non-zero, then fallback to the edge
+ frequency and finally the edge probability. */
+ if (e->count > highest_count)
+ highest_count = e->count;
+ int edge_freq = EDGE_FREQUENCY (e);
+ if (edge_freq > highest_freq)
+ highest_freq = edge_freq;
+ if (e->probability > highest_probability)
+ highest_probability = e->probability;
+ }
+
+ /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
+ block (or unpartitioned, e.g. the entry block) then it is ok. If not,
+ then the most frequent pred (or succ) needs to be adjusted. In the
+ case where multiple preds/succs have the same frequency (e.g. a
+ 50-50 branch), then both will be adjusted. */
+ if (found)
+ continue;
+
+ FOR_EACH_EDGE (e, ei, edges)
+ {
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+ /* Select the hottest edge using the edge count, if it is non-zero,
+ then fallback to the edge frequency and finally the edge
+ probability. */
+ if (highest_count)
+ {
+ if (e->count < highest_count)
+ continue;
+ }
+ else if (highest_freq)
+ {
+ if (EDGE_FREQUENCY (e) < highest_freq)
+ continue;
+ }
+ else if (e->probability < highest_probability)
+ continue;
+
+ basic_block reach_bb = walk_up ? e->src : e->dest;
+
+ /* We have a hot bb with an immediate dominator that is cold.
+ The dominator needs to be re-marked hot. */
+ BB_SET_PARTITION (reach_bb, BB_HOT_PARTITION);
+ cold_bb_count--;
+
+ /* Now we need to examine newly-hot reach_bb to see if it is also
+ dominated by a cold bb. */
+ bbs_in_hot_partition->safe_push (reach_bb);
+ hot_bbs_to_check.safe_push (reach_bb);
+ }
+ }
+
+ return cold_bb_count;
+}
+
+
/* Find the basic blocks that are rarely executed and need to be moved to
a separate section of the .o file (to cut down on paging and improve
cache locality). Return a vector of all edges that cross. */
-static VEC(edge, heap) *
+static vec<edge>
find_rarely_executed_basic_blocks_and_crossing_edges (void)
{
- VEC(edge, heap) *crossing_edges = NULL;
+ vec<edge> crossing_edges = vNULL;
basic_block bb;
edge e;
edge_iterator ei;
+ unsigned int cold_bb_count = 0;
+ vec<basic_block> bbs_in_hot_partition = vNULL;
/* Mark which partition (hot/cold) each basic block belongs in. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- if (probably_never_executed_bb_p (bb))
- BB_SET_PARTITION (bb, BB_COLD_PARTITION);
+ bool cold_bb = false;
+
+ if (probably_never_executed_bb_p (cfun, bb))
+ {
+ /* Handle profile insanities created by upstream optimizations
+ by also checking the incoming edge weights. If there is a non-cold
+ incoming edge, conservatively prevent this block from being split
+ into the cold section. */
+ cold_bb = true;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!probably_never_executed_edge_p (cfun, e))
+ {
+ cold_bb = false;
+ break;
+ }
+ }
+ if (cold_bb)
+ {
+ BB_SET_PARTITION (bb, BB_COLD_PARTITION);
+ cold_bb_count++;
+ }
else
- BB_SET_PARTITION (bb, BB_HOT_PARTITION);
+ {
+ BB_SET_PARTITION (bb, BB_HOT_PARTITION);
+ bbs_in_hot_partition.safe_push (bb);
+ }
+ }
+
+ /* Ensure that hot bbs are included along a hot path from the entry to exit.
+ Several different possibilities may include cold bbs along all paths
+ to/from a hot bb. One is that there are edge weight insanities
+ due to optimization phases that do not properly update basic block profile
+ counts. The second is that the entry of the function may not be hot, because
+ it is entered fewer times than the number of profile training runs, but there
+ is a loop inside the function that causes blocks within the function to be
+ above the threshold for hotness. This is fixed by walking up from hot bbs
+ to the entry block, and then down from hot bbs to the exit, performing
+ partitioning fixups as necessary. */
+ if (cold_bb_count)
+ {
+ mark_dfs_back_edges ();
+ cold_bb_count = sanitize_hot_paths (true, cold_bb_count,
+ &bbs_in_hot_partition);
+ if (cold_bb_count)
+ sanitize_hot_paths (false, cold_bb_count, &bbs_in_hot_partition);
}
/* The format of .gcc_except_table does not allow landing pads to
unsigned i;
eh_landing_pad lp;
- FOR_EACH_VEC_ELT (eh_landing_pad, cfun->eh->lp_array, i, lp)
+ FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
{
bool all_same, all_diff;
- if (lp == NULL)
+ if (lp == NULL
+ || lp->landing_pad == NULL_RTX
+ || !LABEL_P (lp->landing_pad))
continue;
all_same = all_diff = true;
/* Mark every edge that crosses between sections. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
FOR_EACH_EDGE (e, ei, bb->succs)
{
unsigned int flags = e->flags;
-
+
/* We should never have EDGE_CROSSING set yet. */
gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
- if (e->src != ENTRY_BLOCK_PTR
- && e->dest != EXIT_BLOCK_PTR
+ if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
&& BB_PARTITION (e->src) != BB_PARTITION (e->dest))
{
- VEC_safe_push (edge, heap, crossing_edges, e);
+ crossing_edges.safe_push (e);
flags |= EDGE_CROSSING;
}
return crossing_edges;
}
+/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
+
+static void
+set_edge_can_fallthru_flag (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ e->flags &= ~EDGE_CAN_FALLTHRU;
+
+ /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
+ if (e->flags & EDGE_FALLTHRU)
+ e->flags |= EDGE_CAN_FALLTHRU;
+ }
+
+ /* If the BB ends with an invertible condjump all (2) edges are
+ CAN_FALLTHRU edges. */
+ if (EDGE_COUNT (bb->succs) != 2)
+ continue;
+ if (!any_condjump_p (BB_END (bb)))
+ continue;
+ if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
+ continue;
+ invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
+ EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
+ EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
+ }
+}
+
/* If any destination of a crossing edge does not have a label, add label;
Convert any easy fall-through crossing edges to unconditional jumps. */
static void
-add_labels_and_missing_jumps (VEC(edge, heap) *crossing_edges)
+add_labels_and_missing_jumps (vec<edge> crossing_edges)
{
size_t i;
edge e;
- FOR_EACH_VEC_ELT (edge, crossing_edges, i, e)
+ FOR_EACH_VEC_ELT (crossing_edges, i, e)
{
basic_block src = e->src;
basic_block dest = e->dest;
rtx label, new_jump;
- if (dest == EXIT_BLOCK_PTR)
+ if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
/* Make sure dest has a label. */
label = block_label (dest);
/* Nothing to do for non-fallthru edges. */
- if (src == ENTRY_BLOCK_PTR)
+ if (src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
if ((e->flags & EDGE_FALLTHRU) == 0)
continue;
rtx old_jump;
rtx fall_thru_label;
- FOR_EACH_BB (cur_bb)
+ FOR_EACH_BB_FN (cur_bb, cfun)
{
fall_thru = NULL;
if (EDGE_COUNT (cur_bb->succs) > 0)
}
}
- if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
+ if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
{
/* Check to see if the fall-thru edge is a crossing edge. */
/* We know the fall-thru edge crosses; if the cond
jump edge does NOT cross, and its destination is the
next block in the bb order, invert the jump
- (i.e. fix it so the fall thru does not cross and
+ (i.e. fix it so the fall through does not cross and
the cond jump does). */
- if (!cond_jump_crosses
- && cur_bb->aux == cond_jump->dest)
+ if (!cond_jump_crosses)
{
/* Find label in fall_thru block. We've already added
any missing labels, so there must be one. */
block are crossing edges. Here we will fix up the
fall through edge. The jump edge will be taken care
of later. The EDGE_CROSSING flag of fall_thru edge
- is unset before the call to force_nonfallthru
- function because if a new basic-block is created
- this edge remains in the current section boundary
- while the edge between new_bb and the fall_thru->dest
- becomes EDGE_CROSSING. */
+ is unset before the call to force_nonfallthru
+ function because if a new basic-block is created
+ this edge remains in the current section boundary
+ while the edge between new_bb and the fall_thru->dest
+ becomes EDGE_CROSSING. */
- fall_thru->flags &= ~EDGE_CROSSING;
+ fall_thru->flags &= ~EDGE_CROSSING;
new_bb = force_nonfallthru (fall_thru);
if (new_bb)
new_bb->aux = cur_bb->aux;
cur_bb->aux = new_bb;
- /* Make sure new fall-through bb is in same
- partition as bb it's falling through from. */
+ /* This is done by force_nonfallthru_and_redirect. */
+ gcc_assert (BB_PARTITION (new_bb)
+ == BB_PARTITION (cur_bb));
- BB_COPY_PARTITION (new_bb, cur_bb);
single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
}
- else
- {
- /* If a new basic-block was not created; restore
- the EDGE_CROSSING flag. */
- fall_thru->flags |= EDGE_CROSSING;
- }
+ else
+ {
+ /* If a new basic-block was not created; restore
+ the EDGE_CROSSING flag. */
+ fall_thru->flags |= EDGE_CROSSING;
+ }
/* Add barrier after new jump */
emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
rtx old_label = NULL_RTX;
rtx new_label;
- FOR_EACH_BB (cur_bb)
+ FOR_EACH_BB_FN (cur_bb, cfun)
{
crossing_edge = NULL;
if (EDGE_COUNT (cur_bb->succs) > 0)
new_jump = emit_jump_insn (gen_jump (old_label));
JUMP_LABEL (new_jump) = old_label;
- last_bb = EXIT_BLOCK_PTR->prev_bb;
+ last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
new_bb = create_basic_block (new_label, new_jump, last_bb);
new_bb->aux = last_bb->aux;
last_bb->aux = new_bb;
rtx cur_insn;
edge succ;
- FOR_EACH_BB (cur_bb)
+ FOR_EACH_BB_FN (cur_bb, cfun)
{
last_insn = BB_END (cur_bb);
if (JUMP_P (last_insn)
&& (succ->flags & EDGE_CROSSING))
{
- rtx label2, table;
-
gcc_assert (!any_condjump_p (last_insn));
/* Make sure the jump is not already an indirect or table jump. */
if (!computed_jump_p (last_insn)
- && !tablejump_p (last_insn, &label2, &table))
+ && !tablejump_p (last_insn, NULL, NULL))
{
/* We have found a "crossing" unconditional branch. Now
we must convert it to an indirect jump. First create
emit_insn_before (indirect_jump_sequence, last_insn);
delete_insn (last_insn);
+ JUMP_LABEL (jump_insn) = label;
+ LABEL_NUSES (label)++;
+
/* Make BB_END for cur_bb be the jump instruction (NOT the
barrier instruction at the end of the sequence...). */
edge e;
edge_iterator ei;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
FOR_EACH_EDGE (e, ei, bb->succs)
if ((e->flags & EDGE_CROSSING)
- && JUMP_P (BB_END (e->src)))
+ && JUMP_P (BB_END (e->src))
+ /* Some notes were added during fix_up_fall_thru_edges, via
+ force_nonfallthru_and_redirect. */
+ && !find_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX))
add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
}
-/* Verify, in the basic block chain, that there is at most one switch
- between hot/cold partitions. This is modelled on
- rtl_verify_flow_info_1, but it cannot go inside that function
- because this condition will not be true until after
- reorder_basic_blocks is called. */
-
-static void
-verify_hot_cold_block_grouping (void)
-{
- basic_block bb;
- int err = 0;
- bool switched_sections = false;
- int current_partition = 0;
-
- FOR_EACH_BB (bb)
- {
- if (!current_partition)
- current_partition = BB_PARTITION (bb);
- if (BB_PARTITION (bb) != current_partition)
- {
- if (switched_sections)
- {
- error ("multiple hot/cold transitions found (bb %i)",
- bb->index);
- err = 1;
- }
- else
- {
- switched_sections = true;
- current_partition = BB_PARTITION (bb);
- }
- }
- }
-
- gcc_assert(!err);
-}
-
/* Reorder basic blocks. The main entry point to this file. FLAGS is
the set of flags to pass to cfg_layout_initialize(). */
-void
+static void
reorder_basic_blocks (void)
{
int n_traces;
gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
- if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
+ if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
return;
set_edge_can_fallthru_flag ();
uncond_jump_length = get_uncond_jump_length ();
/* We need to know some information for each basic block. */
- array_size = GET_ARRAY_SIZE (last_basic_block);
+ array_size = GET_ARRAY_SIZE (last_basic_block_for_fn (cfun));
bbd = XNEWVEC (bbro_basic_block_data, array_size);
for (i = 0; i < array_size; i++)
{
bbd[i].start_of_trace = -1;
- bbd[i].in_trace = -1;
bbd[i].end_of_trace = -1;
+ bbd[i].in_trace = -1;
+ bbd[i].visited = 0;
bbd[i].heap = NULL;
bbd[i].node = NULL;
}
- traces = XNEWVEC (struct trace, n_basic_blocks);
+ traces = XNEWVEC (struct trace, n_basic_blocks_for_fn (cfun));
n_traces = 0;
find_traces (&n_traces, traces);
connect_traces (n_traces, traces);
relink_block_chain (/*stay_in_cfglayout_mode=*/true);
if (dump_file)
- dump_flow_info (dump_file, dump_flags);
+ {
+ if (dump_flags & TDF_DETAILS)
+ dump_reg_info (dump_file);
+ dump_flow_info (dump_file, dump_flags);
+ }
- if (flag_reorder_blocks_and_partition)
- verify_hot_cold_block_grouping ();
+ /* Signal that rtl_verify_flow_info_1 can now verify that there
+ is at most one switch between hot/cold sections. */
+ crtl->bb_reorder_complete = true;
}
/* Determine which partition the first basic block in the function
encountering this note will make the compiler switch between the
hot and cold text sections. */
-static void
+void
insert_section_boundary_note (void)
{
basic_block bb;
- rtx new_note;
- int first_partition = 0;
+ bool switched_sections = false;
+ int current_partition = 0;
+
+ if (!crtl->has_bb_partition)
+ return;
- if (flag_reorder_blocks_and_partition)
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- if (!first_partition)
- first_partition = BB_PARTITION (bb);
- if (BB_PARTITION (bb) != first_partition)
+ if (!current_partition)
+ current_partition = BB_PARTITION (bb);
+ if (BB_PARTITION (bb) != current_partition)
{
- new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
- BB_HEAD (bb));
- /* ??? This kind of note always lives between basic blocks,
- but add_insn_before will set BLOCK_FOR_INSN anyway. */
- BLOCK_FOR_INSN (new_note) = NULL;
- break;
+ gcc_assert (!switched_sections);
+ switched_sections = true;
+ emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, BB_HEAD (bb));
+ current_partition = BB_PARTITION (bb);
}
}
}
+static bool
+gate_handle_reorder_blocks (void)
+{
+ if (targetm.cannot_modify_jumps_p ())
+ return false;
+ return (optimize > 0
+ && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
+}
+
+static unsigned int
+rest_of_handle_reorder_blocks (void)
+{
+ basic_block bb;
+
+ /* Last attempt to optimize CFG, as scheduling, peepholing and insn
+ splitting possibly introduced more crossjumping opportunities. */
+ cfg_layout_initialize (CLEANUP_EXPENSIVE);
+
+ reorder_basic_blocks ();
+ cleanup_cfg (CLEANUP_EXPENSIVE);
+
+ FOR_EACH_BB_FN (bb, cfun)
+ if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
+ bb->aux = bb->next_bb;
+ cfg_layout_finalize ();
+
+ return 0;
+}
+
+namespace {
+
+const pass_data pass_data_reorder_blocks =
+{
+ RTL_PASS, /* type */
+ "bbro", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_REORDER_BLOCKS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_verify_rtl_sharing, /* todo_flags_finish */
+};
+
+class pass_reorder_blocks : public rtl_opt_pass
+{
+public:
+ pass_reorder_blocks (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_reorder_blocks, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate () { return gate_handle_reorder_blocks (); }
+ unsigned int execute () { return rest_of_handle_reorder_blocks (); }
+
+}; // class pass_reorder_blocks
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_reorder_blocks (gcc::context *ctxt)
+{
+ return new pass_reorder_blocks (ctxt);
+}
+
/* Duplicate the blocks containing computed gotos. This basically unfactors
computed gotos that were factored early on in the compilation process to
speed up edge based data flow. We used to not unfactoring them again,
basic_block bb, new_bb;
bitmap candidates;
int max_size;
+ bool changed = false;
- if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
+ if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
return 0;
+ clear_bb_flags ();
cfg_layout_initialize (0);
/* We are estimating the length of uncond jump insn only once
if (uncond_jump_length == 0)
uncond_jump_length = get_uncond_jump_length ();
- max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
+ max_size
+ = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
candidates = BITMAP_ALLOC (NULL);
/* Look for blocks that end in a computed jump, and see if such blocks
are suitable for unfactoring. If a block is a candidate for unfactoring,
mark it in the candidates. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
rtx insn;
edge e;
int size, all_flags;
/* Build the reorder chain for the original order of blocks. */
- if (bb->next_bb != EXIT_BLOCK_PTR)
+ if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
bb->aux = bb->next_bb;
/* Obviously the block has to end in a computed jump. */
goto done;
/* Duplicate computed gotos. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- if (bb->il.rtl->visited)
+ if (bb->flags & BB_VISITED)
continue;
- bb->il.rtl->visited = 1;
+ bb->flags |= BB_VISITED;
/* BB must have one outgoing edge. That edge must not lead to
the exit block or the next block.
The destination must have more than one predecessor. */
if (!single_succ_p (bb)
- || single_succ (bb) == EXIT_BLOCK_PTR
+ || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
|| single_succ (bb) == bb->next_bb
|| single_pred_p (single_succ (bb)))
continue;
if (!bitmap_bit_p (candidates, single_succ (bb)->index))
continue;
+ /* Don't duplicate a partition crossing edge, which requires difficult
+ fixup. */
+ if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX))
+ continue;
+
new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
new_bb->aux = bb->aux;
bb->aux = new_bb;
- new_bb->il.rtl->visited = 1;
+ new_bb->flags |= BB_VISITED;
+ changed = true;
}
done:
+ /* Duplicating blocks above will redirect edges and may cause hot blocks
+ previously reached by both hot and cold blocks to become dominated only
+ by cold blocks. */
+ if (changed)
+ fixup_partitions ();
cfg_layout_finalize ();
BITMAP_FREE (candidates);
return 0;
}
-struct rtl_opt_pass pass_duplicate_computed_gotos =
+namespace {
+
+const pass_data pass_data_duplicate_computed_gotos =
{
- {
- RTL_PASS,
- "compgotos", /* name */
- gate_duplicate_computed_gotos, /* gate */
- duplicate_computed_gotos, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_REORDER_BLOCKS, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_rtl_sharing,/* todo_flags_finish */
- }
+ RTL_PASS, /* type */
+ "compgotos", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_REORDER_BLOCKS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_verify_rtl_sharing, /* todo_flags_finish */
};
+class pass_duplicate_computed_gotos : public rtl_opt_pass
+{
+public:
+ pass_duplicate_computed_gotos (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_duplicate_computed_gotos, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate () { return gate_duplicate_computed_gotos (); }
+ unsigned int execute () { return duplicate_computed_gotos (); }
+
+}; // class pass_duplicate_computed_gotos
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_duplicate_computed_gotos (gcc::context *ctxt)
+{
+ return new pass_duplicate_computed_gotos (ctxt);
+}
+
+static bool
+gate_handle_partition_blocks (void)
+{
+ /* The optimization to partition hot/cold basic blocks into separate
+ sections of the .o file does not work well with linkonce or with
+ user defined section attributes. Don't call it if either case
+ arises. */
+ return (flag_reorder_blocks_and_partition
+ && optimize
+ /* See gate_handle_reorder_blocks. We should not partition if
+ we are going to omit the reordering. */
+ && optimize_function_for_speed_p (cfun)
+ && !DECL_ONE_ONLY (current_function_decl)
+ && !user_defined_section_attribute);
+}
/* This function is the main 'entrance' for the optimization that
partitions hot and cold basic blocks into separate sections of the
static unsigned
partition_hot_cold_basic_blocks (void)
{
- VEC(edge, heap) *crossing_edges;
+ vec<edge> crossing_edges;
- if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
+ if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
return 0;
df_set_flags (DF_DEFER_INSN_RESCAN);
crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
- if (crossing_edges == NULL)
+ if (!crossing_edges.exists ())
return 0;
+ crtl->has_bb_partition = true;
+
/* Make sure the source of any crossing edge ends in a jump and the
destination of any crossing edge has a label. */
add_labels_and_missing_jumps (crossing_edges);
/* Convert all crossing fall_thru edges to non-crossing fall
thrus to unconditional jumps (that jump to the original fall
- thru dest). */
+ through dest). */
fix_up_fall_thru_edges ();
/* If the architecture does not have conditional branches that can
add_reg_crossing_jump_notes ();
- VEC_free (edge, heap, crossing_edges);
+ /* Clear bb->aux fields that the above routines were using. */
+ clear_aux_for_blocks ();
+
+ crossing_edges.release ();
/* ??? FIXME: DF generates the bb info for a block immediately.
And by immediately, I mean *during* creation of the block.
return TODO_verify_flow | TODO_verify_rtl_sharing;
}
-\f
-static bool
-gate_handle_reorder_blocks (void)
-{
- if (targetm.cannot_modify_jumps_p ())
- return false;
- return (optimize > 0);
-}
+namespace {
-/* Reorder basic blocks. */
-static unsigned int
-rest_of_handle_reorder_blocks (void)
+const pass_data pass_data_partition_blocks =
{
- basic_block bb;
-
- /* Last attempt to optimize CFG, as scheduling, peepholing and insn
- splitting possibly introduced more crossjumping opportunities. */
- cfg_layout_initialize (CLEANUP_EXPENSIVE);
+ RTL_PASS, /* type */
+ "bbpart", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_REORDER_BLOCKS, /* tv_id */
+ PROP_cfglayout, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
- if ((flag_reorder_blocks || flag_reorder_blocks_and_partition)
- /* Don't reorder blocks when optimizing for size because extra jump insns may
- be created; also barrier may create extra padding.
+class pass_partition_blocks : public rtl_opt_pass
+{
+public:
+ pass_partition_blocks (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_partition_blocks, ctxt)
+ {}
- More correctly we should have a block reordering mode that tried to
- minimize the combined size of all the jumps. This would more or less
- automatically remove extra jumps, but would also try to use more short
- jumps instead of long jumps. */
- && optimize_function_for_speed_p (cfun))
- {
- reorder_basic_blocks ();
- cleanup_cfg (CLEANUP_EXPENSIVE);
- }
+ /* opt_pass methods: */
+ bool gate () { return gate_handle_partition_blocks (); }
+ unsigned int execute () { return partition_hot_cold_basic_blocks (); }
- FOR_EACH_BB (bb)
- if (bb->next_bb != EXIT_BLOCK_PTR)
- bb->aux = bb->next_bb;
- cfg_layout_finalize ();
+}; // class pass_partition_blocks
- /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
- insert_section_boundary_note ();
- return 0;
-}
+} // anon namespace
-struct rtl_opt_pass pass_reorder_blocks =
+rtl_opt_pass *
+make_pass_partition_blocks (gcc::context *ctxt)
{
- {
- RTL_PASS,
- "bbro", /* name */
- gate_handle_reorder_blocks, /* gate */
- rest_of_handle_reorder_blocks, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_REORDER_BLOCKS, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_rtl_sharing, /* todo_flags_finish */
- }
-};
-
-static bool
-gate_handle_partition_blocks (void)
-{
- /* The optimization to partition hot/cold basic blocks into separate
- sections of the .o file does not work well with linkonce or with
- user defined section attributes. Don't call it if either case
- arises. */
- return (flag_reorder_blocks_and_partition
- && optimize
- && !DECL_ONE_ONLY (current_function_decl)
- && !user_defined_section_attribute);
+ return new pass_partition_blocks (ctxt);
}
-
-struct rtl_opt_pass pass_partition_blocks =
-{
- {
- RTL_PASS,
- "bbpart", /* name */
- gate_handle_partition_blocks, /* gate */
- partition_hot_cold_basic_blocks, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_REORDER_BLOCKS, /* tv_id */
- PROP_cfglayout, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0 /* todo_flags_finish */
- }
-};
git://gcc.gnu.org / gcc.git / blobdiff