OK,removing the call to vec::contains() is clearly the right move.
Rather than go with the extra bitmap to track whats in the vector, I
have done a couple of things.
1 - Abstracted the update list into its own class, making it easier
to change the underlying mechaism from a stack to a breadth first queue
or whatever else.
2 - Changed the implementation to not use vec::contains, and moved
away from using the vector push/pop API.
It is now implemented as a single vector over the basic blocks, in which
a value of 0 indicates the block is not in the list, and otherwise it
points to the next index in the list. The list is terminated with a -1.
m_head points to the head of the list, and -1 if there is no list.
empty_p() is O(1), check if m_head == -1
in_list_p(BB) is O(1), check is vec[bb] != 0
pop() is O(1), return m_head after vec[bb] = 0, move to the next element,
push() is O(1). if (vec[bb] != 0) { vec[bb] = m_head, m_head = bb; }
so at the expense of a single vector over BBs, we have an O(1) solution
to everything.
This provides some nominal improvements over all compilations, and has
similar performance characteristics to the bitmap solution.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From 98244c68e77cf75f93b66ee02df059f718c3fbc0 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Thu, 4 Nov 2021 15:08:06 -0400
Subject: [PATCH 1/2] Abstract ranger cache update list.
Make it more efficient by removing the call to vec::contains.
PR tree-optimization/102943
* gimple-range-cache.cc (class update_list): New.
(update_list::add): Replace add_to_update.
(update_list::pop): New.
(ranger_cache::ranger_cache): Adjust.
(ranger_cache::~ranger_cache): Adjust.
(ranger_cache::add_to_update): Delete.
(ranger_cache::propagate_cache): Adjust to new class.
(ranger_cache::propagate_updated_value): Ditto.
(ranger_cache::fill_block_cache): Ditto.
* gimple-range-cache.h (class ranger_cache): Adjust to update class.
---
gcc/gimple-range-cache.cc | 129 +++++++++++++++++++++++++++++---------
gcc/gimple-range-cache.h | 4 +-
2 files changed, 100 insertions(+), 33 deletions(-)
@@ -754,14 +754,96 @@ temporal_cache::set_always_current (tree name)
// --------------------------------------------------------------------------
+// This class provides an abstraction of a list of blocks to be updated
+// by the cache. It is currently a stack but could be changed. It also
+// maintains a list of blocks which have failed propagation, and does not
+// enter any of those blocks into the list.
+
+// A vector over the BBs is maintained, and an entry of 0 means it is not in
+// a list. Otherwise, the entry is the next block in the list. -1 terminates
+// the list. m_head points to the top of the list, -1 if the list is empty.
+
+class update_list
+{
+public:
+ update_list ();
+ ~update_list ();
+ void add (basic_block bb);
+ basic_block pop ();
+ inline bool empty_p () { return m_update_head == -1; }
+ inline void clear_failures () { bitmap_clear (m_propfail); }
+ inline void propagation_failed (basic_block bb)
+ { bitmap_set_bit (m_propfail, bb->index); }
+private:
+ vec<int> m_update_list;
+ int m_update_head;
+ bitmap m_propfail;
+};
+
+// Create an update list.
+
+update_list::update_list ()
+{
+ m_update_list.create (0);
+ m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
+ m_update_head = -1;
+ m_propfail = BITMAP_ALLOC (NULL);
+}
+
+// Destroy an update list.
+
+update_list::~update_list ()
+{
+ m_update_list.release ();
+ BITMAP_FREE (m_propfail);
+}
+
+// Add BB to the list of blocks to update, unless it's already in the list.
+
+void
+update_list::add (basic_block bb)
+{
+ int i = bb->index;
+ // If propagation has failed for BB, or its already in the list, don't
+ // add it again.
+ if ((unsigned)i >= m_update_list.length ())
+ m_update_list.safe_grow_cleared (i + 64);
+ if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
+ {
+ if (empty_p ())
+ {
+ m_update_head = i;
+ m_update_list[i] = -1;
+ }
+ else
+ {
+ gcc_checking_assert (m_update_head > 0);
+ m_update_list[i] = m_update_head;
+ m_update_head = i;
+ }
+ }
+}
+
+// Remove a block from the list.
+
+basic_block
+update_list::pop ()
+{
+ gcc_checking_assert (!empty_p ());
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
+ int pop = m_update_head;
+ m_update_head = m_update_list[pop];
+ m_update_list[pop] = 0;
+ return bb;
+}
+
+// --------------------------------------------------------------------------
+
ranger_cache::ranger_cache (int not_executable_flag)
: m_gori (not_executable_flag)
{
m_workback.create (0);
m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
- m_update_list.create (0);
- m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun));
- m_update_list.truncate (0);
m_temporal = new temporal_cache;
// If DOM info is available, spawn an oracle as well.
if (dom_info_available_p (CDI_DOMINATORS))
@@ -779,17 +861,16 @@ ranger_cache::ranger_cache (int not_executable_flag)
if (bb)
m_gori.exports (bb);
}
- m_propfail = BITMAP_ALLOC (NULL);
+ m_update = new update_list ();
}
ranger_cache::~ranger_cache ()
{
- BITMAP_FREE (m_propfail);
+ delete m_update;
if (m_oracle)
delete m_oracle;
delete m_temporal;
m_workback.release ();
- m_update_list.release ();
}
// Dump the global caches to file F. if GORI_DUMP is true, dump the
@@ -1029,17 +1110,6 @@ ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc)
return m_on_entry.get_bb_range (r, name, bb);
}
-// Add BB to the list of blocks to update, unless it's already in the list.
-
-void
-ranger_cache::add_to_update (basic_block bb)
-{
- // If propagation has failed for BB, or its already in the list, don't
- // add it again.
- if (!bitmap_bit_p (m_propfail, bb->index) && !m_update_list.contains (bb))
- m_update_list.quick_push (bb);
-}
-
// If there is anything in the propagation update_list, continue
// processing NAME until the list of blocks is empty.
@@ -1053,16 +1123,15 @@ ranger_cache::propagate_cache (tree name)
int_range_max current_range;
int_range_max e_range;
- gcc_checking_assert (bitmap_empty_p (m_propfail));
// Process each block by seeing if its calculated range on entry is
// the same as its cached value. If there is a difference, update
// the cache to reflect the new value, and check to see if any
// successors have cache entries which may need to be checked for
// updates.
- while (m_update_list.length () > 0)
+ while (!m_update->empty_p ())
{
- bb = m_update_list.pop ();
+ bb = m_update->pop ();
gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
m_on_entry.get_bb_range (current_range, name, bb);
@@ -1097,7 +1166,7 @@ ranger_cache::propagate_cache (tree name)
bool ok_p = m_on_entry.set_bb_range (name, bb, new_range);
// If the cache couldn't set the value, mark it as failed.
if (!ok_p)
- bitmap_set_bit (m_propfail, bb->index);
+ m_update->propagation_failed (bb);
if (DEBUG_RANGE_CACHE)
{
if (!ok_p)
@@ -1119,7 +1188,7 @@ ranger_cache::propagate_cache (tree name)
{
if (DEBUG_RANGE_CACHE)
fprintf (dump_file, " bb%d",e->dest->index);
- add_to_update (e->dest);
+ m_update->add (e->dest);
}
if (DEBUG_RANGE_CACHE)
fprintf (dump_file, "\n");
@@ -1131,7 +1200,7 @@ ranger_cache::propagate_cache (tree name)
print_generic_expr (dump_file, name, TDF_SLIM);
fprintf (dump_file, "\n");
}
- bitmap_clear (m_propfail);
+ m_update->clear_failures ();
}
// Check to see if an update to the value for NAME in BB has any effect
@@ -1146,7 +1215,7 @@ ranger_cache::propagate_updated_value (tree name, basic_block bb)
edge_iterator ei;
// The update work list should be empty at this point.
- gcc_checking_assert (m_update_list.length () == 0);
+ gcc_checking_assert (m_update->empty_p ());
gcc_checking_assert (bb);
if (DEBUG_RANGE_CACHE)
@@ -1160,12 +1229,12 @@ ranger_cache::propagate_updated_value (tree name, basic_block bb)
// Only update active cache entries.
if (m_on_entry.bb_range_p (name, e->dest))
{
- add_to_update (e->dest);
+ m_update->add (e->dest);
if (DEBUG_RANGE_CACHE)
fprintf (dump_file, " UPDATE: bb%d", e->dest->index);
}
}
- if (m_update_list.length () != 0)
+ if (!m_update->empty_p ())
{
if (DEBUG_RANGE_CACHE)
fprintf (dump_file, "\n");
@@ -1205,7 +1274,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
m_workback.quick_push (bb);
undefined.set_undefined ();
m_on_entry.set_bb_range (name, bb, undefined);
- gcc_checking_assert (m_update_list.length () == 0);
+ gcc_checking_assert (m_update->empty_p ());
if (DEBUG_RANGE_CACHE)
{
@@ -1235,7 +1304,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
// If the pred block is the def block add this BB to update list.
if (pred == def_bb)
{
- add_to_update (node);
+ m_update->add (node);
continue;
}
@@ -1255,7 +1324,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
{
if (DEBUG_RANGE_CACHE)
fprintf (dump_file, "nonnull: update ");
- add_to_update (node);
+ m_update->add (node);
}
// If the pred block already has a range, or if it can contribute
@@ -1270,7 +1339,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
}
if (!r.undefined_p () || m_gori.has_edge_range_p (name, e))
{
- add_to_update (node);
+ m_update->add (node);
if (DEBUG_RANGE_CACHE)
fprintf (dump_file, "update. ");
}
@@ -114,7 +114,6 @@ private:
ssa_global_cache m_globals;
block_range_cache m_on_entry;
class temporal_cache *m_temporal;
- void add_to_update (basic_block bb);
void fill_block_cache (tree name, basic_block bb, basic_block def_bb);
void propagate_cache (tree name);
@@ -122,9 +121,8 @@ private:
void entry_range (irange &r, tree expr, basic_block bb);
void exit_range (irange &r, tree expr, basic_block bb);
- bitmap m_propfail;
vec<basic_block> m_workback;
- vec<basic_block> m_update_list;
+ class update_list *m_update;
};
#endif // GCC_SSA_RANGE_CACHE_H
--
2.17.2