/* Thread edges through blocks and update the control flow and SSA graphs.
- Copyright (C) 2004-2017 Free Software Foundation, Inc.
+ Copyright (C) 2004-2019 Free Software Foundation, Inc.
This file is part of GCC.
and sharing a template for that block is considerably more difficult. */
basic_block template_block;
+ /* If we append debug stmts to the template block after creating it,
+ this iterator won't be the last one in the block, and further
+ copies of the template block shouldn't get debug stmts after
+ it. */
+ gimple_stmt_iterator template_last_to_copy;
+
/* Blocks duplicated for the thread. */
bitmap duplicate_blocks;
else
{
e->probability = profile_probability::always ();
- e->count = bb->count;
ei_next (&ei);
}
}
rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
- e->aux = NULL;
+ {
+ e->aux = NULL;
+
+ /* If we duplicate a block with an outgoing edge marked as
+ EDGE_IGNORE, we must clear EDGE_IGNORE so that it doesn't
+ leak out of the current pass.
+
+ It would be better to simplify switch statements and remove
+ the edges before we get here, but the sequencing is nontrivial. */
+ e->flags &= ~EDGE_IGNORE;
+ }
/* Zero out the profile, since the block is unreachable for now. */
- rd->dup_blocks[count]->frequency = 0;
rd->dup_blocks[count]->count = profile_count::uninitialized ();
if (duplicate_blocks)
bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
gphi *src_phi = gsi.phi ();
gphi *dest_phi = gsi2.phi ();
tree val = gimple_phi_arg_def (src_phi, src_idx);
- source_location locus = gimple_phi_arg_location (src_phi, src_idx);
+ location_t locus = gimple_phi_arg_location (src_phi, src_idx);
SET_PHI_ARG_DEF (dest_phi, tgt_idx, val);
gimple_phi_arg_set_location (dest_phi, tgt_idx, locus);
static tree
get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
- basic_block bb, int idx, source_location *locus)
+ basic_block bb, int idx, location_t *locus)
{
tree arg;
gphi *def_phi;
{
gphi *phi = gsi.phi ();
tree def = gimple_phi_arg_def (phi, src_indx);
- source_location locus = gimple_phi_arg_location (phi, src_indx);
+ location_t locus = gimple_phi_arg_location (phi, src_indx);
if (TREE_CODE (def) == SSA_NAME
&& !virtual_operand_p (gimple_phi_result (phi)))
}
-/* Compute the amount of profile count/frequency coming into the jump threading
+/* Compute the amount of profile count coming into the jump threading
path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
edges that need to be ignored in the analysis. Return true if path contains
a joiner, false otherwise.
- In the non-joiner case, this is straightforward - all the counts/frequency
+ In the non-joiner case, this is straightforward - all the counts
flowing into the jump threading path should flow through the duplicated
block and out of the duplicated path.
compute_path_counts (struct redirection_data *rd,
ssa_local_info_t *local_info,
profile_count *path_in_count_ptr,
- profile_count *path_out_count_ptr,
- int *path_in_freq_ptr)
+ profile_count *path_out_count_ptr)
{
edge e = rd->incoming_edges->e;
vec<jump_thread_edge *> *path = THREAD_PATH (e);
profile_count nonpath_count = profile_count::zero ();
bool has_joiner = false;
profile_count path_in_count = profile_count::zero ();
- int path_in_freq = 0;
/* Start by accumulating incoming edge counts to the path's first bb
into a couple buckets:
same last path edge in the case where the last edge has a nocopy
source block. */
gcc_assert (ein_path->last ()->e == elast);
- path_in_count += ein->count;
- path_in_freq += EDGE_FREQUENCY (ein);
+ path_in_count += ein->count ();
}
else if (!ein_path)
{
/* Keep track of the incoming edges that are not on any jump-threading
path. These counts will still flow out of original path after all
jump threading is complete. */
- nonpath_count += ein->count;
+ nonpath_count += ein->count ();
}
}
- /* This is needed due to insane incoming frequencies. */
- if (path_in_freq > BB_FREQ_MAX)
- path_in_freq = BB_FREQ_MAX;
-
/* Now compute the fraction of the total count coming into the first
path bb that is from the current threading path. */
profile_count total_count = e->dest->count;
/* Handle incoming profile insanities. */
if (total_count < path_in_count)
path_in_count = total_count;
- int onpath_scale
- = path_in_count.probability_in (total_count).to_reg_br_prob_base ();
+ profile_probability onpath_scale = path_in_count.probability_in (total_count);
/* Walk the entire path to do some more computation in order to estimate
how much of the path_in_count will flow out of the duplicated threading
for (unsigned int i = 1; i < path->length (); i++)
{
edge epath = (*path)[i]->e;
- profile_count cur_count = epath->count;
+ profile_count cur_count = epath->count ();
if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
{
has_joiner = true;
they are redirected by an invocation of this routine. */
&& !bitmap_bit_p (local_info->duplicate_blocks,
ein->src->index))
- nonpath_count += ein->count;
+ nonpath_count += ein->count ();
}
}
if (cur_count < path_out_count)
path_out_count = cur_count;
- if (epath->count < min_path_count)
- min_path_count = epath->count;
+ if (epath->count () < min_path_count)
+ min_path_count = epath->count ();
}
/* We computed path_out_count above assuming that this path targeted
(since any path through the joiner with a different elast will not
include a copy of this elast in its duplicated path).
So ensure that this path's path_out_count is at least the
- difference between elast->count and nonpath_count. Otherwise the edge
+ difference between elast->count () and nonpath_count. Otherwise the edge
counts after threading will not be sane. */
if (local_info->need_profile_correction
- && has_joiner && path_out_count < elast->count - nonpath_count)
+ && has_joiner && path_out_count < elast->count () - nonpath_count)
{
- path_out_count = elast->count - nonpath_count;
+ path_out_count = elast->count () - nonpath_count;
/* But neither can we go above the minimum count along the path
we are duplicating. This can be an issue due to profile
insanities coming in to this pass. */
*path_in_count_ptr = path_in_count;
*path_out_count_ptr = path_out_count;
- *path_in_freq_ptr = path_in_freq;
return has_joiner;
}
/* Update the counts and frequencies for both an original path
edge EPATH and its duplicate EDUP. The duplicate source block
- will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
+ will get a count of PATH_IN_COUNT and PATH_IN_FREQ,
and the duplicate edge EDUP will have a count of PATH_OUT_COUNT. */
static void
update_profile (edge epath, edge edup, profile_count path_in_count,
- profile_count path_out_count, int path_in_freq)
+ profile_count path_out_count)
{
- /* First update the duplicated block's count / frequency. */
+ /* First update the duplicated block's count. */
if (edup)
{
basic_block dup_block = edup->src;
+
+ /* Edup's count is reduced by path_out_count. We need to redistribute
+ probabilities to the remaining edges. */
+
+ edge esucc;
+ edge_iterator ei;
+ profile_probability edup_prob
+ = path_out_count.probability_in (path_in_count);
+
+ /* Either scale up or down the remaining edges.
+ probabilities are always in range <0,1> and thus we can't do
+ both by same loop. */
+ if (edup->probability > edup_prob)
+ {
+ profile_probability rev_scale
+ = (profile_probability::always () - edup->probability)
+ / (profile_probability::always () - edup_prob);
+ FOR_EACH_EDGE (esucc, ei, dup_block->succs)
+ if (esucc != edup)
+ esucc->probability /= rev_scale;
+ }
+ else if (edup->probability < edup_prob)
+ {
+ profile_probability scale
+ = (profile_probability::always () - edup_prob)
+ / (profile_probability::always () - edup->probability);
+ FOR_EACH_EDGE (esucc, ei, dup_block->succs)
+ if (esucc != edup)
+ esucc->probability *= scale;
+ }
+ if (edup_prob.initialized_p ())
+ edup->probability = edup_prob;
+
gcc_assert (!dup_block->count.initialized_p ());
- gcc_assert (dup_block->frequency == 0);
dup_block->count = path_in_count;
- dup_block->frequency = path_in_freq;
}
- /* Now update the original block's count and frequency in the
+ if (path_in_count == profile_count::zero ())
+ return;
+
+ profile_count final_count = epath->count () - path_out_count;
+
+ /* Now update the original block's count in the
opposite manner - remove the counts/freq that will flow
into the duplicated block. Handle underflow due to precision/
rounding issues. */
epath->src->count -= path_in_count;
- epath->src->frequency -= path_in_freq;
- if (epath->src->frequency < 0)
- epath->src->frequency = 0;
/* Next update this path edge's original and duplicated counts. We know
that the duplicated path will have path_out_count flowing
out of it (in the joiner case this is the count along the duplicated path
out of the duplicated joiner). This count can then be removed from the
original path edge. */
- if (edup)
- edup->count = path_out_count;
- epath->count -= path_out_count;
- /* FIXME: can epath->count be legally uninitialized here? */
-}
-
-/* The duplicate and original joiner blocks may end up with different
- probabilities (different from both the original and from each other).
- Recompute the probabilities here once we have updated the edge
- counts and frequencies. */
-
-static void
-recompute_probabilities (basic_block bb)
-{
edge esucc;
edge_iterator ei;
- FOR_EACH_EDGE (esucc, ei, bb->succs)
- {
- if (!(bb->count > 0))
- continue;
-
- /* Prevent overflow computation due to insane profiles. */
- if (esucc->count < bb->count)
- esucc->probability = esucc->count.probability_in (bb->count);
- else
- /* Can happen with missing/guessed probabilities, since we
- may determine that more is flowing along duplicated
- path than joiner succ probabilities allowed.
- Counts and freqs will be insane after jump threading,
- at least make sure probability is sane or we will
- get a flow verification error.
- Not much we can do to make counts/freqs sane without
- redoing the profile estimation. */
- esucc->probability = profile_probability::guessed_always ();
- }
-}
-
-
-/* Update the counts of the original and duplicated edges from a joiner
- that go off path, given that we have already determined that the
- duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
- outgoing count along the path PATH_OUT_COUNT. The original (on-)path
- edge from joiner is EPATH. */
-
-static void
-update_joiner_offpath_counts (edge epath, basic_block dup_bb,
- profile_count path_in_count,
- profile_count path_out_count)
-{
- /* Compute the count that currently flows off path from the joiner.
- In other words, the total count of joiner's out edges other than
- epath. Compute this by walking the successors instead of
- subtracting epath's count from the joiner bb count, since there
- are sometimes slight insanities where the total out edge count is
- larger than the bb count (possibly due to rounding/truncation
- errors). */
- profile_count total_orig_off_path_count = profile_count::zero ();
- edge enonpath;
- edge_iterator ei;
- FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
- {
- if (enonpath == epath)
- continue;
- total_orig_off_path_count += enonpath->count;
- }
-
- /* For the path that we are duplicating, the amount that will flow
- off path from the duplicated joiner is the delta between the
- path's cumulative in count and the portion of that count we
- estimated above as flowing from the joiner along the duplicated
- path. */
- profile_count total_dup_off_path_count = path_in_count - path_out_count;
-
- /* Now do the actual updates of the off-path edges. */
- FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
- {
- /* Look for edges going off of the threading path. */
- if (enonpath == epath)
- continue;
-
- /* Find the corresponding edge out of the duplicated joiner. */
- edge enonpathdup = find_edge (dup_bb, enonpath->dest);
- gcc_assert (enonpathdup);
-
- /* We can't use the original probability of the joiner's out
- edges, since the probabilities of the original branch
- and the duplicated branches may vary after all threading is
- complete. But apportion the duplicated joiner's off-path
- total edge count computed earlier (total_dup_off_path_count)
- among the duplicated off-path edges based on their original
- ratio to the full off-path count (total_orig_off_path_count).
- */
- int scale = enonpath->count.probability_in (total_orig_off_path_count)
- .to_reg_br_prob_base ();
- /* Give the duplicated offpath edge a portion of the duplicated
- total. */
- enonpathdup->count = total_dup_off_path_count.apply_probability (scale);
- /* Now update the original offpath edge count, handling underflow
- due to rounding errors. */
- enonpath->count -= enonpathdup->count;
- }
-}
-
-
-/* Check if the paths through RD all have estimated frequencies but zero
- profile counts. This is more accurate than checking the entry block
- for a zero profile count, since profile insanities sometimes creep in. */
-
-static bool
-estimated_freqs_path (struct redirection_data *rd)
-{
- edge e = rd->incoming_edges->e;
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- edge ein;
- edge_iterator ei;
- bool non_zero_freq = false;
- FOR_EACH_EDGE (ein, ei, e->dest->preds)
- {
- if (ein->count > 0)
- return false;
- non_zero_freq |= ein->src->frequency != 0;
- }
-
- for (unsigned int i = 1; i < path->length (); i++)
- {
- edge epath = (*path)[i]->e;
- if (epath->src->count > 0)
- return false;
- non_zero_freq |= epath->src->frequency != 0;
- edge esucc;
- FOR_EACH_EDGE (esucc, ei, epath->src->succs)
- {
- if (esucc->count > 0)
- return false;
- non_zero_freq |= esucc->src->frequency != 0;
- }
- }
- return non_zero_freq;
-}
-
-
-/* Invoked for routines that have guessed frequencies and no profile
- counts to record the block and edge frequencies for paths through RD
- in the profile count fields of those blocks and edges. This is because
- ssa_fix_duplicate_block_edges incrementally updates the block and
- edge counts as edges are redirected, and it is difficult to do that
- for edge frequencies which are computed on the fly from the source
- block frequency and probability. When a block frequency is updated
- its outgoing edge frequencies are affected and become difficult to
- adjust. */
-
-static void
-freqs_to_counts_path (struct redirection_data *rd)
-{
- edge e = rd->incoming_edges->e;
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- edge ein;
- edge_iterator ei;
- FOR_EACH_EDGE (ein, ei, e->dest->preds)
- {
- /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
- errors applying the probability when the frequencies are very
- small. */
- if (ein->probability.initialized_p ())
- ein->count = profile_count::from_gcov_type
- (apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
- ein->probability.to_reg_br_prob_base ()));
- else
- /* FIXME: this is hack; we should track uninitialized values. */
- ein->count = profile_count::zero ();
- }
+ profile_probability epath_prob = final_count.probability_in (epath->src->count);
- for (unsigned int i = 1; i < path->length (); i++)
+ if (epath->probability > epath_prob)
{
- edge epath = (*path)[i]->e;
- edge esucc;
- /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
- errors applying the edge probability when the frequencies are very
- small. */
- epath->src->count =
- profile_count::from_gcov_type
- (epath->src->frequency * REG_BR_PROB_BASE);
- FOR_EACH_EDGE (esucc, ei, epath->src->succs)
- esucc->count =
- esucc->src->count.apply_probability (esucc->probability);
+ profile_probability rev_scale
+ = (profile_probability::always () - epath->probability)
+ / (profile_probability::always () - epath_prob);
+ FOR_EACH_EDGE (esucc, ei, epath->src->succs)
+ if (esucc != epath)
+ esucc->probability /= rev_scale;
}
-}
-
-
-/* For routines that have guessed frequencies and no profile counts, where we
- used freqs_to_counts_path to record block and edge frequencies for paths
- through RD, we clear the counts after completing all updates for RD.
- The updates in ssa_fix_duplicate_block_edges are based off the count fields,
- but the block frequencies and edge probabilities were updated as well,
- so we can simply clear the count fields. */
-
-static void
-clear_counts_path (struct redirection_data *rd)
-{
- edge e = rd->incoming_edges->e;
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- edge ein, esucc;
- edge_iterator ei;
- profile_count val = profile_count::uninitialized ();
- if (profile_status_for_fn (cfun) == PROFILE_READ)
- val = profile_count::zero ();
-
- FOR_EACH_EDGE (ein, ei, e->dest->preds)
- ein->count = val;
-
- /* First clear counts along original path. */
- for (unsigned int i = 1; i < path->length (); i++)
+ else if (epath->probability < epath_prob)
{
- edge epath = (*path)[i]->e;
+ profile_probability scale
+ = (profile_probability::always () - epath_prob)
+ / (profile_probability::always () - epath->probability);
FOR_EACH_EDGE (esucc, ei, epath->src->succs)
- esucc->count = val;
- epath->src->count = val;
- }
- /* Also need to clear the counts along duplicated path. */
- for (unsigned int i = 0; i < 2; i++)
- {
- basic_block dup = rd->dup_blocks[i];
- if (!dup)
- continue;
- FOR_EACH_EDGE (esucc, ei, dup->succs)
- esucc->count = val;
- dup->count = val;
+ if (esucc != epath)
+ esucc->probability *= scale;
}
+ if (epath_prob.initialized_p ())
+ epath->probability = epath_prob;
}
/* Wire up the outgoing edges from the duplicate blocks and
edge elast = path->last ()->e;
profile_count path_in_count = profile_count::zero ();
profile_count path_out_count = profile_count::zero ();
- int path_in_freq = 0;
-
- /* This routine updates profile counts, frequencies, and probabilities
- incrementally. Since it is difficult to do the incremental updates
- using frequencies/probabilities alone, for routines without profile
- data we first take a snapshot of the existing block and edge frequencies
- by copying them into the empty profile count fields. These counts are
- then used to do the incremental updates, and cleared at the end of this
- routine. If the function is marked as having a profile, we still check
- to see if the paths through RD are using estimated frequencies because
- the routine had zero profile counts. */
- bool do_freqs_to_counts = (profile_status_for_fn (cfun) != PROFILE_READ
- || estimated_freqs_path (rd));
- if (do_freqs_to_counts)
- freqs_to_counts_path (rd);
/* First determine how much profile count to move from original
path to the duplicate path. This is tricky in the presence of
non-joiner case the path_in_count and path_out_count should be the
same. */
bool has_joiner = compute_path_counts (rd, local_info,
- &path_in_count, &path_out_count,
- &path_in_freq);
+ &path_in_count, &path_out_count);
- int cur_path_freq = path_in_freq;
for (unsigned int count = 0, i = 1; i < path->length (); i++)
{
edge epath = (*path)[i]->e;
}
}
- /* Update the counts and frequency of both the original block
+ /* Update the counts of both the original block
and path edge, and the duplicates. The path duplicate's
- incoming count and frequency are the totals for all edges
+ incoming count are the totals for all edges
incoming to this jump threading path computed earlier.
And we know that the duplicated path will have path_out_count
flowing out of it (i.e. along the duplicated path out of the
duplicated joiner). */
- update_profile (epath, e2, path_in_count, path_out_count,
- path_in_freq);
-
- /* Next we need to update the counts of the original and duplicated
- edges from the joiner that go off path. */
- update_joiner_offpath_counts (epath, e2->src, path_in_count,
- path_out_count);
-
- /* Finally, we need to set the probabilities on the duplicated
- edges out of the duplicated joiner (e2->src). The probabilities
- along the original path will all be updated below after we finish
- processing the whole path. */
- recompute_probabilities (e2->src);
-
- /* Record the frequency flowing to the downstream duplicated
- path blocks. */
- cur_path_freq = EDGE_FREQUENCY (e2);
+ update_profile (epath, e2, path_in_count, path_out_count);
}
else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
{
if (count == 1)
single_succ_edge (rd->dup_blocks[1])->aux = NULL;
- /* Update the counts and frequency of both the original block
+ /* Update the counts of both the original block
and path edge, and the duplicates. Since we are now after
any joiner that may have existed on the path, the count
flowing along the duplicated threaded path is path_out_count.
been updated at the end of that handling to the edge frequency
along the duplicated joiner path edge. */
update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
- path_out_count, path_out_count,
- cur_path_freq);
+ path_out_count, path_out_count);
}
else
{
thread path (path_in_freq). If we had a joiner, it would have
been updated at the end of that handling to the edge frequency
along the duplicated joiner path edge. */
- update_profile (epath, NULL, path_out_count, path_out_count,
- cur_path_freq);
+ update_profile (epath, NULL, path_out_count, path_out_count);
}
/* Increment the index into the duplicated path when we processed
count++;
}
}
-
- /* Now walk orig blocks and update their probabilities, since the
- counts and freqs should be updated properly by above loop. */
- for (unsigned int i = 1; i < path->length (); i++)
- {
- edge epath = (*path)[i]->e;
- recompute_probabilities (epath->src);
- }
-
- /* Done with all profile and frequency updates, clear counts if they
- were copied. */
- if (do_freqs_to_counts)
- clear_counts_path (rd);
}
/* Hash table traversal callback routine to create duplicate blocks. */
create_block_for_threading ((*path)[1]->e->src, rd, 0,
&local_info->duplicate_blocks);
local_info->template_block = rd->dup_blocks[0];
+ local_info->template_last_to_copy
+ = gsi_last_bb (local_info->template_block);
/* We do not create any outgoing edges for the template. We will
take care of that in a later traversal. That way we do not
}
else
{
+ gimple_seq seq = NULL;
+ if (gsi_stmt (local_info->template_last_to_copy)
+ != gsi_stmt (gsi_last_bb (local_info->template_block)))
+ {
+ if (gsi_end_p (local_info->template_last_to_copy))
+ {
+ seq = bb_seq (local_info->template_block);
+ set_bb_seq (local_info->template_block, NULL);
+ }
+ else
+ seq = gsi_split_seq_after (local_info->template_last_to_copy);
+ }
create_block_for_threading (local_info->template_block, rd, 0,
&local_info->duplicate_blocks);
+ if (seq)
+ {
+ if (gsi_end_p (local_info->template_last_to_copy))
+ set_bb_seq (local_info->template_block, seq);
+ else
+ gsi_insert_seq_after (&local_info->template_last_to_copy,
+ seq, GSI_SAME_STMT);
+ }
/* Go ahead and wire up outgoing edges and update PHIs for the duplicate
block. */
ssa_fix_duplicate_block_edges (rd, local_info);
}
+ if (MAY_HAVE_DEBUG_STMTS)
+ {
+ /* Copy debug stmts from each NO_COPY src block to the block
+ that would have been its predecessor, if we can append to it
+ (we can't add stmts after a block-ending stmt), or prepending
+ to the duplicate of the successor, if there is one. If
+ there's no duplicate successor, we'll mostly drop the blocks
+ on the floor; propagate_threaded_block_debug_into, called
+ elsewhere, will consolidate and preserve the effects of the
+ binds, but none of the markers. */
+ gimple_stmt_iterator copy_to = gsi_last_bb (rd->dup_blocks[0]);
+ if (!gsi_end_p (copy_to))
+ {
+ if (stmt_ends_bb_p (gsi_stmt (copy_to)))
+ {
+ if (rd->dup_blocks[1])
+ copy_to = gsi_after_labels (rd->dup_blocks[1]);
+ else
+ copy_to = gsi_none ();
+ }
+ else
+ gsi_next (©_to);
+ }
+ for (unsigned int i = 2, j = 0; i < path->length (); i++)
+ if ((*path)[i]->type == EDGE_NO_COPY_SRC_BLOCK
+ && gsi_bb (copy_to))
+ {
+ for (gimple_stmt_iterator gsi = gsi_start_bb ((*path)[i]->e->src);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ if (!is_gimple_debug (gsi_stmt (gsi)))
+ continue;
+ gimple *stmt = gsi_stmt (gsi);
+ gimple *copy = gimple_copy (stmt);
+ gsi_insert_before (©_to, copy, GSI_SAME_STMT);
+ }
+ }
+ else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
+ || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ {
+ j++;
+ gcc_assert (j < 2);
+ copy_to = gsi_last_bb (rd->dup_blocks[j]);
+ if (!gsi_end_p (copy_to))
+ {
+ if (stmt_ends_bb_p (gsi_stmt (copy_to)))
+ copy_to = gsi_none ();
+ else
+ gsi_next (©_to);
+ }
+ }
+ }
+
/* Keep walking the hash table. */
return 1;
}
and thread this elsewhere, so just cancel the jump threading
request by clearing the AUX field now. */
if (bb->loop_father != e2->src->loop_father
- && !loop_exit_edge_p (e2->src->loop_father, e2))
+ && (!loop_exit_edge_p (e2->src->loop_father, e2)
+ || flow_loop_nested_p (bb->loop_father,
+ e2->dest->loop_father)))
{
/* Since this case is not handled by our special code
to thread through a loop header, we must explicitly
if (i != path->length ())
continue;
+
+ /* Loop parallelization can be confused by the result of
+ threading through the loop exit test back into the loop.
+ However, theading those jumps seems to help other codes.
+
+ I have been unable to find anything related to the shape of
+ the CFG, the contents of the affected blocks, etc which would
+ allow a more sensible test than what we're using below which
+ merely avoids the optimization when parallelizing loops. */
+ if (flag_tree_parallelize_loops > 1)
+ {
+ for (i = 1; i < path->length (); i++)
+ if (bb->loop_father == e2->src->loop_father
+ && loop_exits_from_bb_p (bb->loop_father,
+ (*path)[i]->e->src)
+ && !loop_exit_edge_p (bb->loop_father, e2))
+ break;
+
+ if (i != path->length ())
+ {
+ delete_jump_thread_path (path);
+ e->aux = NULL;
+ continue;
+ }
+ }
}
/* Insert the outgoing edge into the hash table if it is not
return true;
}
+/* Return the number of non-debug statements and non-virtual PHIs in a
+ block. */
+
+static unsigned int
+count_stmts_and_phis_in_block (basic_block bb)
+{
+ unsigned int num_stmts = 0;
+
+ gphi_iterator gpi;
+ for (gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next (&gpi))
+ if (!virtual_operand_p (PHI_RESULT (gpi.phi ())))
+ num_stmts++;
+
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (!is_gimple_debug (stmt))
+ num_stmts++;
+ }
+
+ return num_stmts;
+}
+
+
/* Walk through the registered jump threads and convert them into a
form convenient for this pass.
{
vec<jump_thread_edge *> *path = paths[i];
- if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
+ if (path->length () > 1
+ && (*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
{
edge e = (*path)[0]->e;
e->aux = (void *)path;
{
vec<jump_thread_edge *> *path = paths[i];
- if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ if (path->length () > 1
+ && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
{
/* Attach the path to the starting edge if none is yet recorded. */
if ((*path)[0]->e->aux == NULL)
vec<jump_thread_edge *> *path = paths[i];
edge e = (*path)[0]->e;
- if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
+ if (path->length () > 1
+ && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
{
unsigned int j;
for (j = 1; j < path->length (); j++)
}
}
- /* If optimizing for size, only thread through block if we don't have
- to duplicate it or it's an otherwise empty redirection block. */
+ /* When optimizing for size, prune all thread paths where statement
+ duplication is necessary.
+
+ We walk the jump thread path looking for copied blocks. There's
+ two types of copied blocks.
+
+ EDGE_COPY_SRC_JOINER_BLOCK is always copied and thus we will
+ cancel the jump threading request when optimizing for size.
+
+ EDGE_COPY_SRC_BLOCK which is copied, but some of its statements
+ will be killed by threading. If threading does not kill all of
+ its statements, then we should cancel the jump threading request
+ when optimizing for size. */
if (optimize_function_for_size_p (cfun))
{
EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
{
- bb = BASIC_BLOCK_FOR_FN (cfun, i);
- if (EDGE_COUNT (bb->preds) > 1
- && !redirection_block_p (bb))
- {
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (e->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- delete_jump_thread_path (path);
- e->aux = NULL;
- }
- }
- }
- else
- bitmap_set_bit (threaded_blocks, i);
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, i)->preds)
+ if (e->aux)
+ {
+ vec<jump_thread_edge *> *path = THREAD_PATH (e);
+
+ unsigned int j;
+ for (j = 1; j < path->length (); j++)
+ {
+ bb = (*path)[j]->e->src;
+ if (redirection_block_p (bb))
+ ;
+ else if ((*path)[j]->type == EDGE_COPY_SRC_JOINER_BLOCK
+ || ((*path)[j]->type == EDGE_COPY_SRC_BLOCK
+ && (count_stmts_and_phis_in_block (bb)
+ != estimate_threading_killed_stmts (bb))))
+ break;
+ }
+
+ if (j != path->length ())
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ dump_jump_thread_path (dump_file, *path, 0);
+ delete_jump_thread_path (path);
+ e->aux = NULL;
+ }
+ else
+ bitmap_set_bit (threaded_blocks, i);
+ }
}
}
else
return false;
}
+DEBUG_FUNCTION void
+debug_path (FILE *dump_file, int pathno)
+{
+ vec<jump_thread_edge *> *p = paths[pathno];
+ fprintf (dump_file, "path: ");
+ for (unsigned i = 0; i < p->length (); ++i)
+ fprintf (dump_file, "%d -> %d, ",
+ (*p)[i]->e->src->index, (*p)[i]->e->dest->index);
+ fprintf (dump_file, "\n");
+}
+
+DEBUG_FUNCTION void
+debug_all_paths ()
+{
+ for (unsigned i = 0; i < paths.length (); ++i)
+ debug_path (stderr, i);
+}
+
+/* Rewire a jump_thread_edge so that the source block is now a
+ threaded source block.
+
+ PATH_NUM is an index into the global path table PATHS.
+ EDGE_NUM is the jump thread edge number into said path.
+
+ Returns TRUE if we were able to successfully rewire the edge. */
+
+static bool
+rewire_first_differing_edge (unsigned path_num, unsigned edge_num)
+{
+ vec<jump_thread_edge *> *path = paths[path_num];
+ edge &e = (*path)[edge_num]->e;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "rewiring edge candidate: %d -> %d\n",
+ e->src->index, e->dest->index);
+ basic_block src_copy = get_bb_copy (e->src);
+ if (src_copy == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ignoring candidate: there is no src COPY\n");
+ return false;
+ }
+ edge new_edge = find_edge (src_copy, e->dest);
+ /* If the previously threaded paths created a flow graph where we
+ can no longer figure out where to go, give up. */
+ if (new_edge == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ignoring candidate: we lost our way\n");
+ return false;
+ }
+ e = new_edge;
+ return true;
+}
+
+/* After an FSM path has been jump threaded, adjust the remaining FSM
+ paths that are subsets of this path, so these paths can be safely
+ threaded within the context of the new threaded path.
+
+ For example, suppose we have just threaded:
+
+ 5 -> 6 -> 7 -> 8 -> 12 => 5 -> 6' -> 7' -> 8' -> 12'
+
+ And we have an upcoming threading candidate:
+ 5 -> 6 -> 7 -> 8 -> 15 -> 20
+
+ This function adjusts the upcoming path into:
+ 8' -> 15 -> 20
+
+ CURR_PATH_NUM is an index into the global paths table. It
+ specifies the path that was just threaded. */
+
+static void
+adjust_paths_after_duplication (unsigned curr_path_num)
+{
+ vec<jump_thread_edge *> *curr_path = paths[curr_path_num];
+ gcc_assert ((*curr_path)[0]->type == EDGE_FSM_THREAD);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "just threaded: ");
+ debug_path (dump_file, curr_path_num);
+ }
+
+ /* Iterate through all the other paths and adjust them. */
+ for (unsigned cand_path_num = 0; cand_path_num < paths.length (); )
+ {
+ if (cand_path_num == curr_path_num)
+ {
+ ++cand_path_num;
+ continue;
+ }
+ /* Make sure the candidate to adjust starts with the same path
+ as the recently threaded path and is an FSM thread. */
+ vec<jump_thread_edge *> *cand_path = paths[cand_path_num];
+ if ((*cand_path)[0]->type != EDGE_FSM_THREAD
+ || (*cand_path)[0]->e != (*curr_path)[0]->e)
+ {
+ ++cand_path_num;
+ continue;
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "adjusting candidate: ");
+ debug_path (dump_file, cand_path_num);
+ }
+
+ /* Chop off from the candidate path any prefix it shares with
+ the recently threaded path. */
+ unsigned minlength = MIN (curr_path->length (), cand_path->length ());
+ unsigned j;
+ for (j = 0; j < minlength; ++j)
+ {
+ edge cand_edge = (*cand_path)[j]->e;
+ edge curr_edge = (*curr_path)[j]->e;
+
+ /* Once the prefix no longer matches, adjust the first
+ non-matching edge to point from an adjusted edge to
+ wherever it was going. */
+ if (cand_edge != curr_edge)
+ {
+ gcc_assert (cand_edge->src == curr_edge->src);
+ if (!rewire_first_differing_edge (cand_path_num, j))
+ goto remove_candidate_from_list;
+ break;
+ }
+ }
+ if (j == minlength)
+ {
+ /* If we consumed the max subgraph we could look at, and
+ still didn't find any different edges, it's the
+ last edge after MINLENGTH. */
+ if (cand_path->length () > minlength)
+ {
+ if (!rewire_first_differing_edge (cand_path_num, j))
+ goto remove_candidate_from_list;
+ }
+ else if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "adjusting first edge after MINLENGTH.\n");
+ }
+ if (j > 0)
+ {
+ /* If we are removing everything, delete the entire candidate. */
+ if (j == cand_path->length ())
+ {
+ remove_candidate_from_list:
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "adjusted candidate: [EMPTY]\n");
+ delete_jump_thread_path (cand_path);
+ paths.unordered_remove (cand_path_num);
+ continue;
+ }
+ /* Otherwise, just remove the redundant sub-path. */
+ cand_path->block_remove (0, j);
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "adjusted candidate: ");
+ debug_path (dump_file, cand_path_num);
+ }
+ ++cand_path_num;
+ }
+}
+
/* Duplicates a jump-thread path of N_REGION basic blocks.
The ENTRY edge is redirected to the duplicate of the region.
and create a single fallthru edge pointing to the same destination as the
EXIT edge.
- The new basic blocks are stored to REGION_COPY in the same order as they had
- in REGION, provided that REGION_COPY is not NULL.
+ CURRENT_PATH_NO is an index into the global paths[] table
+ specifying the jump-thread path.
Returns false if it is unable to copy the region, true otherwise. */
static bool
-duplicate_thread_path (edge entry, edge exit,
- basic_block *region, unsigned n_region,
- basic_block *region_copy)
+duplicate_thread_path (edge entry, edge exit, basic_block *region,
+ unsigned n_region, unsigned current_path_no)
{
unsigned i;
- bool free_region_copy = false;
struct loop *loop = entry->dest->loop_father;
edge exit_copy;
edge redirected;
- int curr_freq;
profile_count curr_count;
if (!can_copy_bbs_p (region, n_region))
return false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nabout to thread: ");
+ debug_path (dump_file, current_path_no);
+ }
+
/* Some sanity checking. Note that we do not check for all possible
missuses of the functions. I.e. if you ask to copy something weird,
it will work, but the state of structures probably will not be
set_loop_copy (loop, loop);
- if (!region_copy)
- {
- region_copy = XNEWVEC (basic_block, n_region);
- free_region_copy = true;
- }
-
+ basic_block *region_copy = XNEWVEC (basic_block, n_region);
copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
split_edge_bb_loc (entry), false);
invalidating the property that is propagated by executing all the blocks of
the jump-thread path in order. */
- curr_count = entry->count;
- curr_freq = EDGE_FREQUENCY (entry);
+ curr_count = entry->count ();
for (i = 0; i < n_region; i++)
{
/* Watch inconsistent profile. */
if (curr_count > region[i]->count)
curr_count = region[i]->count;
- if (curr_freq > region[i]->frequency)
- curr_freq = region[i]->frequency;
/* Scale current BB. */
- if (region[i]->count > 0 && curr_count.initialized_p ())
+ if (region[i]->count.nonzero_p () && curr_count.initialized_p ())
{
/* In the middle of the path we only scale the frequencies.
In last BB we need to update probabilities of outgoing edges
region[i]->count);
else
update_bb_profile_for_threading (region[i],
- curr_freq, curr_count,
+ curr_count,
exit);
scale_bbs_frequencies_profile_count (region_copy + i, 1, curr_count,
region_copy[i]->count);
}
- else if (region[i]->frequency)
- {
- if (i + 1 != n_region)
- scale_bbs_frequencies_int (region + i, 1,
- region[i]->frequency - curr_freq,
- region[i]->frequency);
- else
- update_bb_profile_for_threading (region[i],
- curr_freq, curr_count,
- exit);
- scale_bbs_frequencies_int (region_copy + i, 1, curr_freq,
- region_copy[i]->frequency);
- }
if (single_succ_p (bb))
{
|| region_copy[i + 1] == single_succ_edge (bb)->dest);
if (i + 1 != n_region)
{
- curr_freq = EDGE_FREQUENCY (single_succ_edge (bb));
- curr_count = single_succ_edge (bb)->count;
+ curr_count = single_succ_edge (bb)->count ();
}
continue;
}
}
else
{
- curr_freq = EDGE_FREQUENCY (e);
- curr_count = e->count;
+ curr_count = e->count ();
}
}
{
rescan_loop_exit (e, true, false);
e->probability = profile_probability::always ();
- e->count = region_copy[n_region - 1]->count;
}
/* Redirect the entry and add the phi node arguments. */
/* Add the other PHI node arguments. */
add_phi_args_after_copy (region_copy, n_region, NULL);
- if (free_region_copy)
- free (region_copy);
+ free (region_copy);
+
+ adjust_paths_after_duplication (current_path_no);
free_original_copy_tables ();
return true;
{
bool retval = false;
unsigned int i;
- bitmap_iterator bi;
struct loop *loop;
auto_bitmap threaded_blocks;
+ hash_set<edge> visited_starting_edges;
if (!paths.exists ())
{
continue;
}
- /* Do not jump-thread twice from the same block. */
- if (bitmap_bit_p (threaded_blocks, entry->src->index)
- /* We may not want to realize this jump thread path
- for various reasons. So check it first. */
+ /* Do not jump-thread twice from the same starting edge.
+
+ Previously we only checked that we weren't threading twice
+ from the same BB, but that was too restrictive. Imagine a
+ path that starts from GIMPLE_COND(x_123 == 0,...), where both
+ edges out of this conditional yield paths that can be
+ threaded (for example, both lead to an x_123==0 or x_123!=0
+ conditional further down the line. */
+ if (visited_starting_edges.contains (entry)
+ /* We may not want to realize this jump thread path for
+ various reasons. So check it first. */
|| !valid_jump_thread_path (path))
{
/* Remove invalid FSM jump-thread paths. */
for (unsigned int j = 0; j < len - 1; j++)
region[j] = (*path)[j]->e->dest;
- if (duplicate_thread_path (entry, exit, region, len - 1, NULL))
+ if (duplicate_thread_path (entry, exit, region, len - 1, i))
{
/* We do not update dominance info. */
free_dominance_info (CDI_DOMINATORS);
- bitmap_set_bit (threaded_blocks, entry->src->index);
+ visited_starting_edges.add (entry);
retval = true;
thread_stats.num_threaded_edges++;
}
edge entry = (*path)[0]->e;
/* Do not jump-thread twice from the same block. */
- if (bitmap_bit_p (threaded_blocks, entry->src->index))
+ if (visited_starting_edges.contains (entry))
{
delete_jump_thread_path (path);
paths.unordered_remove (i);
i++;
}
- bitmap_clear (threaded_blocks);
-
mark_threaded_blocks (threaded_blocks);
initialize_original_copy_tables ();
- /* First perform the threading requests that do not affect
- loop structure. */
- EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
- {
- basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+ /* The order in which we process jump threads can be important.
+
+ Consider if we have two jump threading paths A and B. If the
+ target edge of A is the starting edge of B and we thread path A
+ first, then we create an additional incoming edge into B->dest that
+ we cannot discover as a jump threading path on this iteration.
- if (EDGE_COUNT (bb->preds) > 0)
- retval |= thread_block (bb, true);
+ If we instead thread B first, then the edge into B->dest will have
+ already been redirected before we process path A and path A will
+ natually, with no further work, target the redirected path for B.
+
+ An post-order is sufficient here. Compute the ordering first, then
+ process the blocks. */
+ if (!bitmap_empty_p (threaded_blocks))
+ {
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ unsigned int postorder_num = post_order_compute (postorder, false, false);
+ for (unsigned int i = 0; i < postorder_num; i++)
+ {
+ unsigned int indx = postorder[i];
+ if (bitmap_bit_p (threaded_blocks, indx))
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, indx);
+ retval |= thread_block (bb, true);
+ }
+ }
+ free (postorder);
}
/* Then perform the threading through loop headers. We start with the
return retval;
}
-/* Delete the jump threading path PATH. We have to explcitly delete
+/* Delete the jump threading path PATH. We have to explicitly delete
each entry in the vector, then the container. */
void
paths.safe_push (path);
}
+
+/* Return how many uses of T there are within BB, as long as there
+ aren't any uses outside BB. If there are any uses outside BB,
+ return -1 if there's at most one use within BB, or -2 if there is
+ more than one use within BB. */
+
+static int
+uses_in_bb (tree t, basic_block bb)
+{
+ int uses = 0;
+ bool outside_bb = false;
+
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, t)
+ {
+ if (is_gimple_debug (USE_STMT (use_p)))
+ continue;
+
+ if (gimple_bb (USE_STMT (use_p)) != bb)
+ outside_bb = true;
+ else
+ uses++;
+
+ if (outside_bb && uses > 1)
+ return -2;
+ }
+
+ if (outside_bb)
+ return -1;
+
+ return uses;
+}
+
+/* Starting from the final control flow stmt in BB, assuming it will
+ be removed, follow uses in to-be-removed stmts back to their defs
+ and count how many defs are to become dead and be removed as
+ well. */
+
+unsigned int
+estimate_threading_killed_stmts (basic_block bb)
+{
+ int killed_stmts = 0;
+ hash_map<tree, int> ssa_remaining_uses;
+ auto_vec<gimple *, 4> dead_worklist;
+
+ /* If the block has only two predecessors, threading will turn phi
+ dsts into either src, so count them as dead stmts. */
+ bool drop_all_phis = EDGE_COUNT (bb->preds) == 2;
+
+ if (drop_all_phis)
+ for (gphi_iterator gsi = gsi_start_phis (bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ tree dst = gimple_phi_result (phi);
+
+ /* We don't count virtual PHIs as stmts in
+ record_temporary_equivalences_from_phis. */
+ if (virtual_operand_p (dst))
+ continue;
+
+ killed_stmts++;
+ }
+
+ if (gsi_end_p (gsi_last_bb (bb)))
+ return killed_stmts;
+
+ gimple *stmt = gsi_stmt (gsi_last_bb (bb));
+ if (gimple_code (stmt) != GIMPLE_COND
+ && gimple_code (stmt) != GIMPLE_GOTO
+ && gimple_code (stmt) != GIMPLE_SWITCH)
+ return killed_stmts;
+
+ /* The control statement is always dead. */
+ killed_stmts++;
+ dead_worklist.quick_push (stmt);
+ while (!dead_worklist.is_empty ())
+ {
+ stmt = dead_worklist.pop ();
+
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree t = USE_FROM_PTR (use_p);
+ gimple *def = SSA_NAME_DEF_STMT (t);
+
+ if (gimple_bb (def) == bb
+ && (gimple_code (def) != GIMPLE_PHI
+ || !drop_all_phis)
+ && !gimple_has_side_effects (def))
+ {
+ int *usesp = ssa_remaining_uses.get (t);
+ int uses;
+
+ if (usesp)
+ uses = *usesp;
+ else
+ uses = uses_in_bb (t, bb);
+
+ gcc_assert (uses);
+
+ /* Don't bother recording the expected use count if we
+ won't find any further uses within BB. */
+ if (!usesp && (uses < -1 || uses > 1))
+ {
+ usesp = &ssa_remaining_uses.get_or_insert (t);
+ *usesp = uses;
+ }
+
+ if (uses < 0)
+ continue;
+
+ --uses;
+ if (usesp)
+ *usesp = uses;
+
+ if (!uses)
+ {
+ killed_stmts++;
+ if (usesp)
+ ssa_remaining_uses.remove (t);
+ if (gimple_code (def) != GIMPLE_PHI)
+ dead_worklist.safe_push (def);
+ }
+ }
+ }
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "threading bb %i kills %i stmts\n",
+ bb->index, killed_stmts);
+
+ return killed_stmts;
+}
projects / thirdparty / gcc.git / blobdiff