/* Thread edges through blocks and update the control flow and SSA graphs.
- Copyright (C) 2004-2015 Free Software Foundation, Inc.
+ Copyright (C) 2004-2019 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "alias.h"
#include "backend.h"
-#include "cfghooks.h"
#include "tree.h"
#include "gimple.h"
-#include "hard-reg-set.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
#include "ssa.h"
-#include "options.h"
#include "fold-const.h"
-#include "flags.h"
#include "cfganal.h"
-#include "internal-fn.h"
#include "gimple-iterator.h"
#include "tree-ssa.h"
#include "tree-ssa-threadupdate.h"
-#include "dumpfile.h"
#include "cfgloop.h"
#include "dbgcnt.h"
#include "tree-cfg.h"
-#include "tree-pass.h"
+#include "tree-vectorizer.h"
/* Given a block B, update the CFG and SSA graph to reflect redirecting
one or more in-edges to B to instead reach the destination of an
and sharing a template for that block is considerably more difficult. */
basic_block template_block;
- /* TRUE if we thread one or more jumps, FALSE otherwise. */
- bool jumps_threaded;
+ /* 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;
+
+ /* TRUE if we thread one or more jumps, FALSE otherwise. */
+ bool jumps_threaded;
+
+ /* When we have multiple paths through a joiner which reach different
+ final destinations, then we may need to correct for potential
+ profile insanities. */
+ bool need_profile_correction;
};
/* Passes which use the jump threading code register jump threading
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e->dest != dest_bb)
- remove_edge (e);
+ {
+ free_dom_edge_info (e);
+ remove_edge (e);
+ }
else
- ei_next (&ei);
+ {
+ e->probability = profile_probability::always ();
+ ei_next (&ei);
+ }
}
/* If the remaining edge is a loop exit, there must have
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 = 0;
+ rd->dup_blocks[count]->count = profile_count::uninitialized ();
if (duplicate_blocks)
bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
}
struct redirection_data *elt;
vec<jump_thread_edge *> *path = THREAD_PATH (e);
- /* Build a hash table element so we can see if E is already
+ /* Build a hash table element so we can see if E is already
in the table. */
elt = XNEW (struct redirection_data);
elt->path = path;
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)))
create_edge_and_update_destination_phis (struct redirection_data *rd,
basic_block bb, int idx)
{
- edge e = make_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
+ edge e = make_single_succ_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
rescan_loop_exit (e, true, false);
- e->probability = REG_BR_PROB_BASE;
- e->count = bb->count;
/* We used to copy the thread path here. That was added in 2007
and dutifully updated through the representation changes in 2013.
}
-/* 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.
are not part of any jump threading path, but add profile counts along
the path.
- In the aboe example, after all jump threading is complete, we will
+ In the above example, after all jump threading is complete, we will
end up with the following control flow:
- A B C
- | | |
- Ea| |Eb |Ec
- | | |
- v v v
- Ja J Jc
- / \ / \Eon' / \
+ A B C
+ | | |
+ Ea| |Eb |Ec
+ | | |
+ v v v
+ Ja J Jc
+ / \ / \Eon' / \
Eona/ \ ---/---\-------- \Eonc
- / \ / / \ \
+ / \ / / \ \
v v v v v
Sona Soff Son Sonc
- \ /\ /
+ \ /\ /
\___________ / \ _____/
\ / \/
vv v
static bool
compute_path_counts (struct redirection_data *rd,
ssa_local_info_t *local_info,
- gcov_type *path_in_count_ptr,
- gcov_type *path_out_count_ptr,
- int *path_in_freq_ptr)
+ profile_count *path_in_count_ptr,
+ profile_count *path_out_count_ptr)
{
edge e = rd->incoming_edges->e;
vec<jump_thread_edge *> *path = THREAD_PATH (e);
edge elast = path->last ()->e;
- gcov_type nonpath_count = 0;
+ profile_count nonpath_count = profile_count::zero ();
bool has_joiner = false;
- gcov_type path_in_count = 0;
- int path_in_freq = 0;
+ profile_count path_in_count = profile_count::zero ();
/* Start by accumulating incoming edge counts to the path's first bb
into a couple buckets:
below to add up the counts of the other edges not included in this jump
threading path. */
struct el *next, *el;
- bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
+ auto_bitmap in_edge_srcs;
for (el = rd->incoming_edges; el; el = next)
{
next = el->next;
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;
-
- BITMAP_FREE (in_edge_srcs);
-
/* Now compute the fraction of the total count coming into the first
path bb that is from the current threading path. */
- gcov_type total_count = e->dest->count;
+ 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 = GCOV_COMPUTE_SCALE (path_in_count, total_count);
+ 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
nonpath_count with any additional counts coming into the path. Other
blocks along the path may have additional predecessors from outside
the path. */
- gcov_type path_out_count = path_in_count;
- gcov_type min_path_count = path_in_count;
+ profile_count path_out_count = path_in_count;
+ profile_count min_path_count = path_in_count;
for (unsigned int i = 1; i < path->length (); i++)
{
edge epath = (*path)[i]->e;
- gcov_type cur_count = epath->count;
+ profile_count cur_count = epath->count ();
if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
{
has_joiner = true;
- cur_count = apply_probability (cur_count, onpath_scale);
+ cur_count = cur_count.apply_probability (onpath_scale);
}
/* In the joiner case we need to update nonpath_count for any edges
coming into the path that will contribute to the count flowing
into the path successor. */
if (has_joiner && epath != elast)
- {
- /* Look for other incoming edges after joiner. */
- FOR_EACH_EDGE (ein, ei, epath->dest->preds)
- {
- if (ein != epath
- /* Ignore in edges from blocks we have duplicated for a
- threading path, which have duplicated edge counts until
- they are redirected by an invocation of this routine. */
- && !bitmap_bit_p (local_info->duplicate_blocks,
- ein->src->index))
- nonpath_count += ein->count;
- }
- }
+ {
+ /* Look for other incoming edges after joiner. */
+ FOR_EACH_EDGE (ein, ei, epath->dest->preds)
+ {
+ if (ein != epath
+ /* Ignore in edges from blocks we have duplicated for a
+ threading path, which have duplicated edge counts until
+ they are redirected by an invocation of this routine. */
+ && !bitmap_bit_p (local_info->duplicate_blocks,
+ ein->src->index))
+ 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 (has_joiner && 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. */
- if (path_out_count > min_path_count)
- path_out_count = min_path_count;
- }
+ if (local_info->need_profile_correction
+ && has_joiner && 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. */
+ if (path_out_count > min_path_count)
+ path_out_count = min_path_count;
+ }
*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, gcov_type path_in_count,
- gcov_type path_out_count, int path_in_freq)
+update_profile (edge epath, edge edup, profile_count path_in_count,
+ 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;
- gcc_assert (dup_block->count == 0);
- gcc_assert (dup_block->frequency == 0);
+
+ /* 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 ());
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;
- if (epath->src->count < 0)
- epath->src->count = 0;
- 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;
- gcc_assert (epath->count >= 0);
-}
-
-/* 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)
- continue;
-
- /* Prevent overflow computation due to insane profiles. */
- if (esucc->count < bb->count)
- esucc->probability = GCOV_COMPUTE_SCALE (esucc->count,
- 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 = REG_BR_PROB_BASE;
- }
-}
-
-
-/* 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,
- gcov_type path_in_count,
- gcov_type 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). */
- gcov_type total_orig_off_path_count = 0;
- 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. */
- gcov_type 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 = GCOV_COMPUTE_SCALE (enonpath->count,
- total_orig_off_path_count);
- /* Give the duplicated offpath edge a portion of the duplicated
- total. */
- enonpathdup->count = apply_scale (scale,
- total_dup_off_path_count);
- /* Now update the original offpath edge count, handling underflow
- due to rounding errors. */
- enonpath->count -= enonpathdup->count;
- if (enonpath->count < 0)
- enonpath->count = 0;
- }
-}
-
-
-/* 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)
- 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)
- return false;
- non_zero_freq |= epath->src->frequency != 0;
- edge esucc;
- FOR_EACH_EDGE (esucc, ei, epath->src->succs)
- {
- if (esucc->count)
- 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. */
- ein->count = apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
- ein->probability);
- }
+ 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 = epath->src->frequency * REG_BR_PROB_BASE;
- FOR_EACH_EDGE (esucc, ei, epath->src->succs)
- esucc->count = apply_probability (esucc->src->count,
- 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;
- FOR_EACH_EDGE (ein, ei, e->dest->preds)
- ein->count = 0;
-
- /* 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 = 0;
- epath->src->count = 0;
- }
- /* 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 = 0;
- dup->count = 0;
+ 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 e = rd->incoming_edges->e;
vec<jump_thread_edge *> *path = THREAD_PATH (e);
edge elast = path->last ()->e;
- gcov_type path_in_count = 0;
- gcov_type path_out_count = 0;
- 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);
+ profile_count path_in_count = profile_count::zero ();
+ profile_count path_out_count = profile_count::zero ();
/* 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
a duplicated block. */
if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
|| (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
- {
+ {
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;
}
fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
e->src->index, e->dest->index, rd->dup_blocks[0]->index);
- /* If we redirect a loop latch edge cancel its loop. */
- if (e->src == e->src->loop_father->latch)
- mark_loop_for_removal (e->src->loop_father);
-
/* Redirect the incoming edge (possibly to the joiner block) to the
appropriate duplicate block. */
e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
ssa_local_info_t local_info;
local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
+ local_info.need_profile_correction = false;
/* To avoid scanning a linear array for the element we need we instead
use a hash table. For normal code there should be no noticeable
/* Record each unique threaded destination into a hash table for
efficient lookups. */
+ edge last = NULL;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->aux == NULL)
threading path that crosses loop boundaries. We do not try
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))
- || (e2->src->loop_father != e2->dest->loop_father
- && !loop_exit_edge_p (e2->src->loop_father, e2)))
+ if (bb->loop_father != e2->src->loop_father
+ && (!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
already in the hash table. */
lookup_redirection_data (e, INSERT);
+
+ /* When we have thread paths through a common joiner with different
+ final destinations, then we may need corrections to deal with
+ profile insanities. See the big comment before compute_path_counts. */
+ if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ {
+ if (!last)
+ last = e2;
+ else if (e2 != last)
+ local_info.need_profile_correction = true;
+ }
}
/* We do not update dominance info. */
return retval;
}
-
-/* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the
- copy of E->dest created during threading, or E->dest if it was not necessary
- to copy it (E is its single predecessor). */
-
-static basic_block
-thread_single_edge (edge e)
-{
- basic_block bb = e->dest;
- struct redirection_data rd;
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- edge eto = (*path)[1]->e;
-
- delete_jump_thread_path (path);
- e->aux = NULL;
-
- thread_stats.num_threaded_edges++;
-
- if (single_pred_p (bb))
- {
- /* If BB has just a single predecessor, we should only remove the
- control statements at its end, and successors except for ETO. */
- remove_ctrl_stmt_and_useless_edges (bb, eto->dest);
-
- /* And fixup the flags on the single remaining edge. */
- eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
- eto->flags |= EDGE_FALLTHRU;
-
- return bb;
- }
-
- /* Otherwise, we need to create a copy. */
- if (e->dest == eto->src)
- update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
-
- vec<jump_thread_edge *> *npath = new vec<jump_thread_edge *> ();
- jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
- npath->safe_push (x);
-
- x = new jump_thread_edge (eto, EDGE_COPY_SRC_BLOCK);
- npath->safe_push (x);
- rd.path = npath;
-
- create_block_for_threading (bb, &rd, 0, NULL);
- remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
- create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 0);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
- e->src->index, e->dest->index, rd.dup_blocks[0]->index);
-
- rd.dup_blocks[0]->count = e->count;
- rd.dup_blocks[0]->frequency = EDGE_FREQUENCY (e);
- single_succ_edge (rd.dup_blocks[0])->count = e->count;
- redirect_edge_and_branch (e, rd.dup_blocks[0]);
- flush_pending_stmts (e);
-
- delete_jump_thread_path (npath);
- return rd.dup_blocks[0];
-}
-
/* Callback for dfs_enumerate_from. Returns true if BB is different
from STOP and DBDS_CE_STOP. */
returns the state. */
enum bb_dom_status
-{
- /* BB does not dominate latch of the LOOP. */
- DOMST_NONDOMINATING,
- /* The LOOP is broken (there is no path from the header to its latch. */
- DOMST_LOOP_BROKEN,
- /* BB dominates the latch of the LOOP. */
- DOMST_DOMINATING
-};
-
-static enum bb_dom_status
determine_bb_domination_status (struct loop *loop, basic_block bb)
{
basic_block *bblocks;
return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
}
-/* Return true if BB is part of the new pre-header that is created
- when threading the latch to DATA. */
-
-static bool
-def_split_header_continue_p (const_basic_block bb, const void *data)
-{
- const_basic_block new_header = (const_basic_block) data;
- const struct loop *l;
-
- if (bb == new_header
- || loop_depth (bb->loop_father) < loop_depth (new_header->loop_father))
- return false;
- for (l = bb->loop_father; l; l = loop_outer (l))
- if (l == new_header->loop_father)
- return true;
- return false;
-}
-
/* Thread jumps through the header of LOOP. Returns true if cfg changes.
If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
to the inside of the loop. */
if (single_succ_p (header))
goto fail;
- /* If we threaded the latch using a joiner block, we cancel the
- threading opportunity out of an abundance of caution. However,
- still allow threading from outside to inside the loop. */
- if (latch->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (latch);
- if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
- {
- delete_jump_thread_path (path);
- latch->aux = NULL;
- }
- }
-
- if (latch->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (latch);
- tgt_edge = (*path)[1]->e;
- tgt_bb = tgt_edge->dest;
- }
- else if (!may_peel_loop_headers
- && !redirection_block_p (loop->header))
+ if (!may_peel_loop_headers && !redirection_block_p (loop->header))
goto fail;
else
{
tgt_bb = split_edge (tgt_edge);
}
- if (latch->aux)
- {
- basic_block *bblocks;
- unsigned nblocks, i;
-
- /* First handle the case latch edge is redirected. We are copying
- the loop header but not creating a multiple entry loop. Make the
- cfg manipulation code aware of that fact. */
- set_loop_copy (loop, loop);
- loop->latch = thread_single_edge (latch);
- set_loop_copy (loop, NULL);
- gcc_assert (single_succ (loop->latch) == tgt_bb);
- loop->header = tgt_bb;
-
- /* Remove the new pre-header blocks from our loop. */
- bblocks = XCNEWVEC (basic_block, loop->num_nodes);
- nblocks = dfs_enumerate_from (header, 0, def_split_header_continue_p,
- bblocks, loop->num_nodes, tgt_bb);
- for (i = 0; i < nblocks; i++)
- if (bblocks[i]->loop_father == loop)
- {
- remove_bb_from_loops (bblocks[i]);
- add_bb_to_loop (bblocks[i], loop_outer (loop));
- }
- free (bblocks);
-
- /* If the new header has multiple latches mark it so. */
- FOR_EACH_EDGE (e, ei, loop->header->preds)
- if (e->src->loop_father == loop
- && e->src != loop->latch)
- {
- loop->latch = NULL;
- loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
- }
-
- /* Cancel remaining threading requests that would make the
- loop a multiple entry loop. */
- FOR_EACH_EDGE (e, ei, header->preds)
- {
- edge e2;
-
- if (e->aux == NULL)
- continue;
-
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- e2 = path->last ()->e;
-
- if (e->src->loop_father != e2->dest->loop_father
- && e2->dest != loop->header)
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- }
- }
+ basic_block new_preheader;
- /* Thread the remaining edges through the former header. */
- thread_block (header, false);
- }
- else
+ /* Now consider the case entry edges are redirected to the new entry
+ block. Remember one entry edge, so that we can find the new
+ preheader (its destination after threading). */
+ FOR_EACH_EDGE (e, ei, header->preds)
{
- basic_block new_preheader;
-
- /* Now consider the case entry edges are redirected to the new entry
- block. Remember one entry edge, so that we can find the new
- preheader (its destination after threading). */
- FOR_EACH_EDGE (e, ei, header->preds)
- {
- if (e->aux)
- break;
- }
-
- /* The duplicate of the header is the new preheader of the loop. Ensure
- that it is placed correctly in the loop hierarchy. */
- set_loop_copy (loop, loop_outer (loop));
-
- thread_block (header, false);
- set_loop_copy (loop, NULL);
- new_preheader = e->dest;
-
- /* Create the new latch block. This is always necessary, as the latch
- must have only a single successor, but the original header had at
- least two successors. */
- loop->latch = NULL;
- mfb_kj_edge = single_succ_edge (new_preheader);
- loop->header = mfb_kj_edge->dest;
- latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
- loop->header = latch->dest;
- loop->latch = latch->src;
+ if (e->aux)
+ break;
}
+ /* The duplicate of the header is the new preheader of the loop. Ensure
+ that it is placed correctly in the loop hierarchy. */
+ set_loop_copy (loop, loop_outer (loop));
+
+ thread_block (header, false);
+ set_loop_copy (loop, NULL);
+ new_preheader = e->dest;
+
+ /* Create the new latch block. This is always necessary, as the latch
+ must have only a single successor, but the original header had at
+ least two successors. */
+ loop->latch = NULL;
+ mfb_kj_edge = single_succ_edge (new_preheader);
+ loop->header = mfb_kj_edge->dest;
+ latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
+ loop->header = latch->dest;
+ loop->latch = latch->src;
return true;
fail:
return true;
}
-/* Walk through the registered jump threads and convert them into a
- form convenient for this pass.
+/* Return the number of non-debug statements and non-virtual PHIs in a
+ block. */
- Any block which has incoming edges threaded to outgoing edges
- will have its entry in THREADED_BLOCK set.
+static unsigned int
+count_stmts_and_phis_in_block (basic_block bb)
+{
+ unsigned int num_stmts = 0;
- Any threaded edge will have its new outgoing edge stored in the
- original edge's AUX field.
+ 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++;
- This form avoids the need to walk all the edges in the CFG to
- discover blocks which need processing and avoids unnecessary
- hash table lookups to map from threaded edge to new target. */
+ 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.
+
+ Any block which has incoming edges threaded to outgoing edges
+ will have its entry in THREADED_BLOCK set.
+
+ Any threaded edge will have its new outgoing edge stored in the
+ original edge's AUX field.
+
+ This form avoids the need to walk all the edges in the CFG to
+ discover blocks which need processing and avoids unnecessary
+ hash table lookups to map from threaded edge to new target. */
static void
mark_threaded_blocks (bitmap threaded_blocks)
{
unsigned int i;
bitmap_iterator bi;
- bitmap tmp = BITMAP_ALLOC (NULL);
+ auto_bitmap tmp;
basic_block bb;
edge e;
edge_iterator ei;
{
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. */
- 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);
- }
- }
- else
- bitmap_copy (threaded_blocks, tmp);
+ /* When optimizing for size, prune all thread paths where statement
+ duplication is necessary.
- /* Look for jump threading paths which cross multiple loop headers.
+ We walk the jump thread path looking for copied blocks. There's
+ two types of copied blocks.
- The code to thread through loop headers will change the CFG in ways
- that break assumptions made by the loop optimization code.
+ EDGE_COPY_SRC_JOINER_BLOCK is always copied and thus we will
+ cancel the jump threading request when optimizing for size.
- We don't want to blindly cancel the requests. We can instead do better
- by trimming off the end of the jump thread path. */
- EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
+ 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))
{
- basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
- FOR_EACH_EDGE (e, ei, bb->preds)
+ EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
{
- if (e->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, i)->preds)
+ if (e->aux)
+ {
+ vec<jump_thread_edge *> *path = THREAD_PATH (e);
- for (unsigned int i = 0, crossed_headers = 0;
- i < path->length ();
- i++)
- {
- basic_block dest = (*path)[i]->e->dest;
- crossed_headers += (dest == dest->loop_father->header);
- if (crossed_headers > 1)
- {
- /* Trim from entry I onwards. */
- for (unsigned int j = i; j < path->length (); j++)
- delete (*path)[j];
- path->truncate (i);
-
- /* Now that we've truncated the path, make sure
- what's left is still valid. We need at least
- two edges on the path and the last edge can not
- be a joiner. This should never happen, but let's
- be safe. */
- if (path->length () < 2
- || (path->last ()->type
- == EDGE_COPY_SRC_JOINER_BLOCK))
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- }
+ 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
+ bitmap_copy (threaded_blocks, tmp);
/* If we have a joiner block (J) which has two successors S1 and S2 and
we are threading though S1 and the final destination of the thread
}
}
- BITMAP_FREE (tmp);
-}
+ /* Look for jump threading paths which cross multiple loop headers.
+ The code to thread through loop headers will change the CFG in ways
+ that invalidate the cached loop iteration information. So we must
+ detect that case and wipe the cached information. */
+ EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (e->aux)
+ {
+ vec<jump_thread_edge *> *path = THREAD_PATH (e);
-/* Return TRUE if BB ends with a switch statement or a computed goto.
- Otherwise return false. */
-static bool
-bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED)
-{
- gimple *stmt = last_stmt (bb);
- if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
- return true;
- if (stmt && gimple_code (stmt) == GIMPLE_GOTO
- && TREE_CODE (gimple_goto_dest (stmt)) == SSA_NAME)
- return true;
- return false;
+ for (unsigned int i = 0, crossed_headers = 0;
+ i < path->length ();
+ i++)
+ {
+ basic_block dest = (*path)[i]->e->dest;
+ basic_block src = (*path)[i]->e->src;
+ /* If we enter a loop. */
+ if (flow_loop_nested_p (src->loop_father, dest->loop_father))
+ ++crossed_headers;
+ /* If we step from a block outside an irreducible region
+ to a block inside an irreducible region, then we have
+ crossed into a loop. */
+ else if (! (src->flags & BB_IRREDUCIBLE_LOOP)
+ && (dest->flags & BB_IRREDUCIBLE_LOOP))
+ ++crossed_headers;
+ if (crossed_headers > 1)
+ {
+ vect_free_loop_info_assumptions
+ ((*path)[path->length () - 1]->e->dest->loop_father);
+ break;
+ }
+ }
+ }
+ }
+ }
}
+
/* Verify that the REGION is a valid jump thread. A jump thread is a special
case of SEME Single Entry Multiple Exits region in which all nodes in the
REGION have exactly one incoming edge. The only exception is the first block
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 total_freq = 0, entry_freq = 0;
- gcov_type total_count = 0, entry_count = 0;
+ 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;
- }
-
- if (entry->dest->count)
- {
- total_count = entry->dest->count;
- entry_count = entry->count;
- /* Fix up corner cases, to avoid division by zero or creation of negative
- frequencies. */
- if (entry_count > total_count)
- entry_count = total_count;
- }
- else
- {
- total_freq = entry->dest->frequency;
- entry_freq = EDGE_FREQUENCY (entry);
- /* Fix up corner cases, to avoid division by zero or creation of negative
- frequencies. */
- if (total_freq == 0)
- total_freq = 1;
- else if (entry_freq > total_freq)
- entry_freq = total_freq;
- }
-
+ 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 ();
+
for (i = 0; i < n_region; i++)
{
edge e;
edge_iterator ei;
basic_block bb = region_copy[i];
+ /* Watch inconsistent profile. */
+ if (curr_count > region[i]->count)
+ curr_count = region[i]->count;
+ /* Scale current BB. */
+ 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
+ because we know which one is taken at the threaded path. */
+ if (i + 1 != n_region)
+ scale_bbs_frequencies_profile_count (region + i, 1,
+ region[i]->count - curr_count,
+ region[i]->count);
+ else
+ update_bb_profile_for_threading (region[i],
+ curr_count,
+ exit);
+ scale_bbs_frequencies_profile_count (region_copy + i, 1, curr_count,
+ region_copy[i]->count);
+ }
+
if (single_succ_p (bb))
{
/* Make sure the successor is the next node in the path. */
gcc_assert (i + 1 == n_region
|| region_copy[i + 1] == single_succ_edge (bb)->dest);
+ if (i + 1 != n_region)
+ {
+ curr_count = single_succ_edge (bb)->count ();
+ }
continue;
}
/* Special case the last block on the path: make sure that it does not
- jump back on the copied path. */
+ jump back on the copied path, including back to itself. */
if (i + 1 == n_region)
{
FOR_EACH_EDGE (e, ei, bb->succs)
- if (bb_in_bbs (e->dest, region_copy, n_region - 1))
+ if (bb_in_bbs (e->dest, region_copy, n_region))
{
basic_block orig = get_bb_original (e->dest);
if (orig)
if (orig)
redirect_edge_and_branch_force (e, orig);
}
+ else
+ {
+ curr_count = e->count ();
+ }
}
- if (total_count)
- {
- scale_bbs_frequencies_gcov_type (region, n_region,
- total_count - entry_count,
- total_count);
- scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
- total_count);
- }
- else
- {
- scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
- total_freq);
- scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
- }
-#ifdef ENABLE_CHECKING
- verify_jump_thread (region_copy, n_region);
-#endif
+ if (flag_checking)
+ verify_jump_thread (region_copy, n_region);
/* Remove the last branch in the jump thread path. */
remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU);
- if (e) {
- rescan_loop_exit (e, true, false);
- e->probability = REG_BR_PROB_BASE;
- e->count = region_copy[n_region - 1]->count;
- }
+ if (e)
+ {
+ rescan_loop_exit (e, true, false);
+ e->probability = profile_probability::always ();
+ }
/* Redirect the entry and add the phi node arguments. */
if (entry->dest == loop->header)
/* 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;
/* Check that the path is connected. */
for (unsigned int j = 0; j < len - 1; j++)
- if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
- return false;
-
+ {
+ edge e = (*path)[j]->e;
+ if (e->dest != (*path)[j+1]->e->src)
+ return false;
+ }
return true;
}
{
bool retval = false;
unsigned int i;
- bitmap_iterator bi;
- bitmap threaded_blocks;
struct loop *loop;
+ auto_bitmap threaded_blocks;
+ hash_set<edge> visited_starting_edges;
if (!paths.exists ())
{
goto out;
}
- threaded_blocks = BITMAP_ALLOC (NULL);
memset (&thread_stats, 0, sizeof (thread_stats));
/* Remove any paths that referenced removed edges. */
continue;
}
- /* Do not jump-thread twice from the same block. */
- if (bitmap_bit_p (threaded_blocks, entry->src->index)
- /* Verify that the jump thread path is still valid: a
- previous jump-thread may have changed the CFG, and
- invalidated the current path. */
+ /* 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++;
}
delete_jump_thread_path (path);
paths.unordered_remove (i);
+ free (region);
}
/* Remove from PATHS all the jump-threads starting with an edge already
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.
- if (EDGE_COUNT (bb->preds) > 0)
- retval |= thread_block (bb, true);
+ 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 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
retval |= thread_through_loop_header (loop, may_peel_loop_headers);
}
- /* Any jump threading paths that are still attached to edges at this
- point must be one of two cases.
-
- First, we could have a jump threading path which went from outside
- a loop to inside a loop that was ignored because a prior jump thread
- across a backedge was realized (which indirectly causes the loop
- above to ignore the latter thread). We can detect these because the
- loop structures will be different and we do not currently try to
- optimize this case.
-
- Second, we could be threading across a backedge to a point within the
- same loop. This occurrs for the FSA/FSM optimization and we would
- like to optimize it. However, we have to be very careful as this
- may completely scramble the loop structures, with the result being
- irreducible loops causing us to throw away our loop structure.
-
- As a compromise for the latter case, if the thread path ends in
- a block where the last statement is a multiway branch, then go
- ahead and thread it, else ignore it. */
+ /* All jump threading paths should have been resolved at this
+ point. Verify that is the case. */
basic_block bb;
- edge e;
FOR_EACH_BB_FN (bb, cfun)
{
- /* If we do end up threading here, we can remove elements from
- BB->preds. Thus we can not use the FOR_EACH_EDGE iterator. */
- for (edge_iterator ei = ei_start (bb->preds);
- (e = ei_safe_edge (ei));)
- if (e->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
-
- /* Case 1, threading from outside to inside the loop
- after we'd already threaded through the header. */
- if ((*path)[0]->e->dest->loop_father
- != path->last ()->e->src->loop_father)
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- ei_next (&ei);
- }
- else if (bb_ends_with_multiway_branch (path->last ()->e->src))
- {
- /* The code to thread through loop headers may have
- split a block with jump threads attached to it.
-
- We can identify this with a disjoint jump threading
- path. If found, just remove it. */
- for (unsigned int i = 0; i < path->length () - 1; i++)
- if ((*path)[i]->e->dest != (*path)[i + 1]->e->src)
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- ei_next (&ei);
- break;
- }
-
- /* Our path is still valid, thread it. */
- if (e->aux)
- {
- if (thread_block ((*path)[0]->e->dest, false))
- e->aux = NULL;
- else
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- ei_next (&ei);
- }
- }
- }
- else
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- ei_next (&ei);
- }
- }
- else
- ei_next (&ei);
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ gcc_assert (e->aux == NULL);
}
statistics_counter_event (cfun, "Jumps threaded",
free_original_copy_tables ();
- BITMAP_FREE (threaded_blocks);
- threaded_blocks = NULL;
paths.release ();
if (retval)
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
/* First make sure there are no NULL outgoing edges on the jump threading
path. That can happen for jumping to a constant address. */
for (unsigned int i = 0; i < path->length (); i++)
- if ((*path)[i]->e == NULL)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "Found NULL edge in jump threading path. Cancelling jump thread:\n");
- dump_jump_thread_path (dump_file, *path, false);
- }
+ {
+ if ((*path)[i]->e == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Found NULL edge in jump threading path. Cancelling jump thread:\n");
+ dump_jump_thread_path (dump_file, *path, false);
+ }
- delete_jump_thread_path (path);
- return;
- }
+ delete_jump_thread_path (path);
+ return;
+ }
+
+ /* Only the FSM threader is allowed to thread across
+ backedges in the CFG. */
+ if (flag_checking
+ && (*path)[0]->type != EDGE_FSM_THREAD)
+ gcc_assert (((*path)[i]->e->flags & EDGE_DFS_BACK) == 0);
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
dump_jump_thread_path (dump_file, *path, true);
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