[This is a patch series to improve the back threader performance. With
it the threader is 12% faster.]
The backwards threader marks blocks visited while walking a candidate
path with a hash_set<basic_block>, which costs a hash lookup on both
entry to and exit from every node. The set is only ever used to test
membership of a block of the current function, and the CFG does not
change during the search, so a sbitmap indexed by bb->index is
cleaner.
The function find_paths_to_names clears the bit it set on every exit
path so the per-block reset in maybe_thread_block is redundant.
Measured in perf instructions retired over our stage1 .ii corpus, this
drops back_threader::thread_blocks() by 2.2% (pass_thread_jumps 2.4%,
pass_thread_jumps_full 1.1%, pass_early_thread_jumps 2.2%) and the
whole compile by 0.02% over 806 TUs.
Tested on ppc64le Linux. The assembly is identical over the .ii
files, so this is a NFC.
OK?
gcc/ChangeLog:
* tree-ssa-threadbackward.cc (back_threader::m_visited_bbs):
Turn into an sbitmap.
(back_threader::back_threader): Allocate it.
(back_threader::~back_threader): Free it.
(back_threader::find_paths_to_names): Adjust.
(back_threader::maybe_thread_block): Drop the reset.
---
gcc/tree-ssa-threadbackward.cc | 12 +++++++-----
1 file changed, 7 insertions(+), 5 deletions(-)
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 20bb74c507f..90691ea9612 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -120,8 +120,8 @@ private:
// Current path being analyzed.
auto_vec<basic_block> m_path;
- // Hash to mark visited BBs while analyzing a path.
- hash_set<basic_block> m_visited_bbs;
+ // Bitmap to mark visited BBs while analyzing a path.
+ sbitmap m_visited_bbs;
// The set of SSA names, any of which could potentially change the
// value of the final conditional in a path.
auto_bitmap m_imports;
@@ -163,10 +163,13 @@ back_threader::back_threader (function *fun, unsigned
flags, bool first)
mark_dfs_back_edges ();
m_ranger = new gimple_ranger;
+ m_visited_bbs = sbitmap_alloc (last_basic_block_for_fn (fun));
+ bitmap_clear (m_visited_bbs);
}
back_threader::~back_threader ()
{
+ sbitmap_free (m_visited_bbs);
delete m_ranger;
loop_optimizer_finalize ();
}
@@ -383,7 +386,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
unsigned overall_paths,
back_threader_profitability &profit)
{
- if (m_visited_bbs.add (bb))
+ if (!bitmap_set_bit (m_visited_bbs, bb->index))
return;
m_path.safe_push (bb);
@@ -524,7 +527,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
// Reset things to their original state.
m_path.pop ();
- m_visited_bbs.remove (bb);
+ bitmap_clear_bit (m_visited_bbs, bb->index);
}
// Search backwards from BB looking for paths where the final
@@ -548,7 +551,6 @@ back_threader::maybe_thread_block (basic_block bb)
return;
m_last_stmt = stmt;
- m_visited_bbs.empty ();
m_path.truncate (0);
// We compute imports of the path during discovery starting
--
2.53.0
