We recompute the per-path stats at every node of the search, which is
rather expensive it turns out. There was a note hidden in the
original code saying we should do this incrementally, and this commit
does so and gives us a 7.8% improvement in the threader.
Tested on ppc64le Linux.
Over a corpus of .ii files from a stage1 bootstrap the assembly is
identical. Also, I instrumented the compiler before and after this
patch, and verified that the path and stats are identical, so
really... a NFC.
gcc/ChangeLog:
* tree-ssa-threadbackward.cc (back_threader_profitability): Add
push_bb, pop_bb, m_loop, unwind_state and m_unwind; add n_insns
to path_stats.
(back_threader_profitability::back_threader_profitability):
Initialize m_loop and m_stats.
(back_threader_profitability::account_bb): Return the number of
insns in the block.
(back_threader_profitability::push_bb): New.
(back_threader_profitability::pop_bb): New.
(back_threader_profitability::possibly_profitable_path_p): Use
the accumulated stats.
(back_threader::find_paths_to_names): Call push_bb/pop_bb.
---
gcc/tree-ssa-threadbackward.cc | 110 ++++++++++++++++++++-------------
1 file changed, 68 insertions(+), 42 deletions(-)
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 1ae32312968..03a7e1db50c 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -62,24 +62,40 @@ class back_threader_profitability
{
public:
back_threader_profitability (bool speed_p, gimple *stmt);
+ void push_bb (const vec<basic_block> &);
+ void pop_bb ();
bool possibly_profitable_path_p (const vec<basic_block> &, bool *);
bool profitable_path_p (const vec<basic_block> &,
edge taken, bool *irreducible_loop);
private:
- void account_bb (basic_block, bool);
+ int account_bb (basic_block, bool);
const bool m_speed_p;
int m_exit_jump_benefit;
bool m_threaded_multiway_branch;
- // The following are computed by possibly_profitable_path_p
+ // The loop the path starts in, i.e. m_path[0]->loop_father.
+ class loop *m_loop;
+ // The following are accumulated by push_bb as the path grows and
+ // restored by pop_bb as it shrinks.
struct path_stats
{
+ int n_insns;
bool threaded_through_latch;
bool multiway_branch_in_path;
bool contains_hot_bb;
bool unprofitable_bb;
};
path_stats m_stats;
+ // Number of insns on the path, less the branch we get to remove.
int m_n_insns;
+ // One entry per push. These are the stats as they stood before that push,
+ // and the insns of the block. Basically the entry pushed for m_path[i]
+ // accounts m_path[i - 1].
+ struct unwind_state
+ {
+ path_stats stats;
+ int bb_insns;
+ };
+ auto_vec<unwind_state, 20> m_unwind;
};
back_threader_profitability::back_threader_profitability (bool speed_p,
@@ -92,15 +108,19 @@ back_threader_profitability::back_threader_profitability
(bool speed_p,
// particular it estimates further DCE from eliminating the exit
// control stmt.
m_exit_jump_benefit = estimate_num_insns (last, &eni_size_weights);
+ m_loop = NULL;
+ m_stats = path_stats ();
}
/* Account for BB in the cumulative stats for the path being threaded.
CHECK_MULTIWAY is true for all blocks except the block whose branch
- we are going to eliminate. */
+ we are going to eliminate. Return the number of insns in BB. */
-void
+int
back_threader_profitability::account_bb (basic_block bb, bool check_multiway)
{
+ int n_insns = 0;
+
if (!m_stats.contains_hot_bb && m_speed_p)
m_stats.contains_hot_bb |= optimize_bb_for_speed_p (bb);
@@ -117,12 +137,12 @@ back_threader_profitability::account_bb (basic_block bb,
bool check_multiway)
|| gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
{
m_stats.unprofitable_bb = true;
- return;
+ return n_insns;
}
/* Do not count empty statements and labels. */
if (gimple_code (stmt) != GIMPLE_NOP
&& !is_gimple_debug (stmt))
- m_n_insns += estimate_num_insns (stmt, &eni_size_weights);
+ n_insns += estimate_num_insns (stmt, &eni_size_weights);
}
/* We do not look at the block with the threaded branch in this loop.
@@ -136,6 +156,42 @@ back_threader_profitability::account_bb (basic_block bb,
bool check_multiway)
|| gimple_code (last) == GIMPLE_GOTO))
m_stats.multiway_branch_in_path = true;
}
+
+ return n_insns;
+}
+
+/* Update the stats after a block has been appended to PATH. */
+
+void
+back_threader_profitability::push_bb (const vec<basic_block> &path)
+{
+ unwind_state state = { m_stats, /*bb_insns=*/0 };
+
+ unsigned n = path.length ();
+ if (n == 1)
+ m_loop = path[0]->loop_father;
+ else
+ {
+ /* Appending a block makes the previous entry block part of the copied
+ path, so that's where to account for now. */
+ unsigned copied = n - 2;
+ bool check_multiway = copied > 0;
+ state.bb_insns = account_bb (path[copied], check_multiway);
+ m_stats.n_insns += state.bb_insns;
+ }
+ m_unwind.safe_push (state);
+
+ /* Note if we thread through the latch, we will want to include the
+ last entry in the array when determining if we thread through the
+ loop latch. */
+ if (m_loop->latch == path[n - 1])
+ m_stats.threaded_through_latch = true;
+}
+
+void
+back_threader_profitability::pop_bb ()
+{
+ m_stats = m_unwind.pop ().stats;
}
// Back threader flags.
@@ -440,6 +496,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
return;
m_path.safe_push (bb);
+ profit.push_bb (m_path);
// Try to resolve the path without looking back. Avoid resolving paths
// we know are large but are not (yet) recognized as Finite State Machine.
@@ -576,6 +633,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
param_max_jump_thread_paths);
// Reset things to their original state.
+ profit.pop_bb ();
m_path.pop ();
m_visited_bbs.remove (bb);
}
@@ -685,42 +743,10 @@ back_threader_profitability::possibly_profitable_path_p
if (m_path.length () <= 1)
return false;
- loop_p loop = m_path[0]->loop_father;
-
- // We recompute the following, when we rewrite possibly_profitable_path_p
- // to work incrementally on added BBs we have to unwind them on backtracking
- m_n_insns = 0;
- m_stats = path_stats ();
+ loop_p loop = m_loop;
- /* Count the number of instructions on the path: as these instructions
- will have to be duplicated, we will not record the path if there
- are too many instructions on the path. Also check that all the
- blocks in the path belong to a single loop. */
- for (unsigned j = 0; j < m_path.length (); j++)
- {
- basic_block bb = m_path[j];
-
- /* Remember, blocks in the path are stored in opposite order in
- the PATH array. The last entry in the array represents the
- block with an outgoing edge that we will redirect to the jump
- threading path. Thus we don't care how many statements are
- in that block because it will not be copied or whether or not
- it ends in a multiway branch. */
- if (j < m_path.length () - 1)
- {
- /* The block in PATH[0] is special, it's the block were we're
- going to be able to eliminate its branch. */
- account_bb (bb, /*check_multiway=*/j > 0);
- if (m_stats.unprofitable_bb)
- return false;
- }
-
- /* Note if we thread through the latch, we will want to include
- the last entry in the array when determining if we thread
- through the loop latch. */
- if (loop->latch == bb)
- m_stats.threaded_through_latch = true;
- }
+ if (m_stats.unprofitable_bb)
+ return false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -736,7 +762,7 @@ back_threader_profitability::possibly_profitable_path_p
/* We are going to remove the control statement at the end of the
last block in the threading path. So don't count it against our
statement count. */
- m_n_insns -= m_exit_jump_benefit;
+ m_n_insns = m_stats.n_insns - m_exit_jump_benefit;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n Control statement insns: %i\n"
--
2.53.0
