From c21644704160710a17d1ea6c1cd212e079cd5e36 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 25 May 2021 14:15:50 -0400
Subject: [PATCH 3/8] Add imports and strengthen the export definition in
range_def and gori_map.
All add up to 2 direct dependencies for each ssa-name.
Add gori import/export iterators.
* gimple-range-gori.cc (range_def_chain::range_def_chain): init
bitmap obstack.
(range_def_chain::~range_def_chain): Dispose of obstack rather than
each individual bitmap.
(range_def_chain::set_import): New.
(range_def_chain::get_imports): New.
(range_def_chain::chain_import_p): New.
(range_def_chain::register_dependency): Rename from build_def_chain
and set imports.
(range_def_chain::def_chain_in_bitmap_p): New.
(range_def_chain::add_def_chain_to_bitmap): New.
(range_def_chain::has_def_chain): Just check first depenedence.
(range_def_chain::get_def_chain): Process imports, use generic
register_dependency routine.
(range_def_chain::dump): New.
(gori_map::gori_map): Allocate import list.
(gori_map::~gori_map): Release imports.
(gori_map::exports): Check for past allocated block size.
(gori_map::imports): New.
(gori_map::def_chain_in_export_p): Delete.
(gori_map::is_import_p): New.
(gori_map::maybe_add_gori): Handle imports.
(gori_map::dump): Adjust output, add imports.
(gori_compute::has_edge_range_p): Remove def_chain_in_export call.
(gori_export_iterator::gori_export_iterator): New.
(gori_export_iterator::next): New.
(gori_export_iterator::get_name): New.
* gimple-range-gori.h (range_def_chain): Add imports and direct
dependecies via struct rdc.
(range_def_chain::depend1): New.
(range_def_chain::depend2): New.
(class gori_map): Adjust.
(FOR_EACH_GORI_IMPORT_NAME): New.
(FOR_EACH_GORI_EXPORT_NAME): New.
(class gori_export_iterator): New.
---
gcc/gimple-range-gori.cc | 356 ++++++++++++++++++++++++++++-----------
gcc/gimple-range-gori.h | 77 ++++++++-
2 files changed, 327 insertions(+), 106 deletions(-)
@@ -56,7 +56,7 @@ is_gimple_logical_p (const gimple *gs)
return false;
}
-/* RANGE_DEF_CHAIN is used to determine what SSA names in a block can
+/* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
have range information calculated for them, and what the
dependencies on each other are.
@@ -95,6 +95,7 @@ is_gimple_logical_p (const gimple *gs)
range_def_chain::range_def_chain ()
{
+ bitmap_obstack_initialize (&m_bitmaps);
m_def_chain.create (0);
m_def_chain.safe_grow_cleared (num_ssa_names);
m_logical_depth = 0;
@@ -104,11 +105,8 @@ range_def_chain::range_def_chain ()
range_def_chain::~range_def_chain ()
{
- unsigned x;
- for (x = 0; x < m_def_chain.length (); ++x)
- if (m_def_chain[x])
- BITMAP_FREE (m_def_chain[x]);
m_def_chain.release ();
+ bitmap_obstack_release (&m_bitmaps);
}
// Return true if NAME is in the def chain of DEF. If BB is provided,
@@ -128,26 +126,112 @@ range_def_chain::in_chain_p (tree name, tree def)
return bitmap_bit_p (chain, SSA_NAME_VERSION (name));
}
+// Add either IMP or the import list B to the import set of DATA.
+
+void
+range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
+{
+ // If there are no imports, just return
+ if (imp == NULL_TREE && !b)
+ return;
+ if (!data.m_import)
+ data.m_import = BITMAP_ALLOC (&m_bitmaps);
+ if (imp != NULL_TREE)
+ bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
+ else
+ bitmap_ior_into (data.m_import, b);
+}
+
+// Return the import list for NAME.
+
+bitmap
+range_def_chain::get_imports (tree name)
+{
+ if (!has_def_chain (name))
+ get_def_chain (name);
+ bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
+ // Either this is a default def, OR imports must be a subset of exports.
+ gcc_checking_assert (!get_def_chain (name) || !i
+ || !bitmap_intersect_compl_p (i, get_def_chain (name)));
+ return i;
+}
+
+// Return true if IMPORT is an import to NAMEs def chain.
+
+bool
+range_def_chain::chain_import_p (tree name, tree import)
+{
+ bitmap b = get_imports (name);
+ if (b)
+ return bitmap_bit_p (b, SSA_NAME_VERSION (import));
+ return false;
+}
+
// Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
void
-range_def_chain::build_def_chain (tree name, bitmap result, basic_block bb)
+range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
{
+ if (!gimple_range_ssa_p (dep))
+ return;
+
+ unsigned v = SSA_NAME_VERSION (name);
+ struct rdc &src = m_def_chain[v];
+ gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
+ unsigned dep_v = SSA_NAME_VERSION (dep);
bitmap b;
- gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+ // Set the direct dependency cache entries.
+ if (!src.ssa1)
+ src.ssa1 = dep;
+ else if (!src.ssa2 && src.ssa1 != dep)
+ src.ssa2 = dep;
+
+ // Don't calculate imports or export/dep chains if BB is not provided.
+ // This is usually the case for when the temporal cache wants the direct
+ // dependencies of a stmt.
+ if (!bb)
+ return;
+
+ if (!src.bm)
+ src.bm = BITMAP_ALLOC (&m_bitmaps);
+
// Add this operand into the result.
- bitmap_set_bit (result, SSA_NAME_VERSION (name));
+ bitmap_set_bit (src.bm, dep_v);
if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt))
{
// Get the def chain for the operand.
- b = get_def_chain (name);
+ b = get_def_chain (dep);
// If there was one, copy it into result.
if (b)
- bitmap_ior_into (result, b);
+ bitmap_ior_into (src.bm, b);
+ // And copy the import list.
+ set_import (src, NULL_TREE, get_imports (dep));
}
+ else
+ // Originated outside the block, so it is an import.
+ set_import (src, dep, NULL);
+}
+
+bool
+range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b)
+{
+ bitmap a = get_def_chain (name);
+ if (a && b)
+ return bitmap_intersect_p (a, b);
+ return false;
}
+void
+range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
+{
+ bitmap r = get_def_chain (name);
+ if (r)
+ bitmap_ior_into (b, r);
+}
+
+
// Return TRUE if NAME has been processed for a def_chain.
inline bool
@@ -157,9 +241,11 @@ range_def_chain::has_def_chain (tree name)
unsigned v = SSA_NAME_VERSION (name);
if (v >= m_def_chain.length ())
m_def_chain.safe_grow_cleared (num_ssa_names + 1);
- return (m_def_chain[v] != NULL);
+ return (m_def_chain[v].ssa1 != 0);
}
+
+
// Calculate the def chain for NAME and all of its dependent
// operands. Only using names in the same BB. Return the bitmap of
// all names in the m_def_chain. This only works for supported range
@@ -174,11 +260,15 @@ range_def_chain::get_def_chain (tree name)
// If it has already been processed, just return the cached value.
if (has_def_chain (name))
- return m_def_chain[v];
+ return m_def_chain[v].bm;
// No definition chain for default defs.
if (SSA_NAME_IS_DEFAULT_DEF (name))
- return NULL;
+ {
+ // A Default def is always an import.
+ set_import (m_def_chain[v], name, NULL);
+ return NULL;
+ }
gimple *stmt = SSA_NAME_DEF_STMT (name);
if (gimple_range_handler (stmt))
@@ -205,30 +295,63 @@ range_def_chain::get_def_chain (tree name)
ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st));
}
else
- return NULL;
-
- basic_block bb = gimple_bb (stmt);
-
- m_def_chain[v] = BITMAP_ALLOC (NULL);
+ {
+ // Stmts not understood are always imports.
+ set_import (m_def_chain[v], name, NULL);
+ return NULL;
+ }
- if (ssa1)
- build_def_chain (ssa1, m_def_chain[v], bb);
- if (ssa2)
- build_def_chain (ssa2, m_def_chain[v], bb);
- if (ssa3)
- build_def_chain (ssa3, m_def_chain[v], bb);
+ register_dependency (name, ssa1, gimple_bb (stmt));
+ register_dependency (name, ssa2, gimple_bb (stmt));
+ register_dependency (name, ssa3, gimple_bb (stmt));
+ // Stmts with no understandable operands are also imports.
+ if (!ssa1 && !ssa2 & !ssa3)
+ set_import (m_def_chain[v], name, NULL);
if (is_logical)
m_logical_depth--;
- // If we run into pathological cases where the defintion chains are
- // huge (ie huge basic block fully unrolled) we might be able to limit
- // this by deciding here that if some criteria is satisfied, we change the
- // def_chain back to be just the ssa-names. That will help prevent chains
- // of a_2 = b_6 + a_8 from creating a pathological case.
- return m_def_chain[v];
+ return m_def_chain[v].bm;
+}
+
+// Dump what we know for basic block BB to file F.
+
+void
+range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
+{
+ unsigned x, y;
+ bitmap_iterator bi;
+
+ // Dump the def chain for each SSA_NAME defined in BB.
+ for (x = 1; x < num_ssa_names; x++)
+ {
+ tree name = ssa_name (x);
+ if (!name)
+ continue;
+ gimple *stmt = SSA_NAME_DEF_STMT (name);
+ if (!stmt || (bb && gimple_bb (stmt) != bb))
+ continue;
+ bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
+ if (chain && !bitmap_empty_p (chain))
+ {
+ fprintf (f, prefix);
+ print_generic_expr (f, name, TDF_SLIM);
+ fprintf (f, " : ");
+
+ bitmap imports = get_imports (name);
+ EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
+ {
+ print_generic_expr (f, ssa_name (y), TDF_SLIM);
+ if (imports && bitmap_bit_p (imports, y))
+ fprintf (f, "(I)");
+ fprintf (f, " ");
+ }
+ fprintf (f, "\n");
+ }
+ }
}
+
// -------------------------------------------------------------------
/* GORI_MAP is used to accumulate what SSA names in a block can
@@ -256,7 +379,8 @@ gori_map::gori_map ()
{
m_outgoing.create (0);
m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
- bitmap_obstack_initialize (&m_bitmaps);
+ m_incoming.create (0);
+ m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
}
@@ -264,7 +388,7 @@ gori_map::gori_map ()
gori_map::~gori_map ()
{
- bitmap_obstack_release (&m_bitmaps);
+ m_incoming.release ();
m_outgoing.release ();
}
@@ -273,11 +397,21 @@ gori_map::~gori_map ()
bitmap
gori_map::exports (basic_block bb)
{
- if (!m_outgoing[bb->index])
+ if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
calculate_gori (bb);
return m_outgoing[bb->index];
}
+// Return the bitmap vector of all imports to BB. Calculate if necessary.
+
+bitmap
+gori_map::imports (basic_block bb)
+{
+ if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
+ calculate_gori (bb);
+ return m_incoming[bb->index];
+}
+
// Return true if NAME is can have ranges generated for it from basic
// block BB.
@@ -298,17 +432,13 @@ gori_map::set_range_invariant (tree name)
bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
}
-// Return true if any element in the def chain of NAME is in the
-// export list for BB.
+// Return true if NAME is an import to block BB.
bool
-gori_map::def_chain_in_export_p (tree name, basic_block bb)
+gori_map::is_import_p (tree name, basic_block bb)
{
- bitmap a = exports (bb);
- bitmap b = get_def_chain (name);
- if (a && b)
- return bitmap_intersect_p (a, b);
- return false;
+ // If no BB is specified, test if it is exported anywhere in the IL.
+ return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
}
// If NAME is non-NULL and defined in block BB, calculate the def
@@ -319,11 +449,17 @@ gori_map::maybe_add_gori (tree name, basic_block bb)
{
if (name)
{
- gimple *s = SSA_NAME_DEF_STMT (name);
- bitmap r = get_def_chain (name);
- // Check if there is a def chain, and it is in this block.
- if (r && gimple_bb (s) == bb)
- bitmap_copy (m_outgoing[bb->index], r);
+ // Check if there is a def chain, regardless of the block.
+ add_def_chain_to_bitmap (m_outgoing[bb->index], name);
+ // Check for any imports.
+ bitmap imp = get_imports (name);
+ // If there were imports, add them so we can recompute
+ if (imp)
+ bitmap_ior_into (m_incoming[bb->index], imp);
+ // This name is always an import.
+ if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
+ bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));
+
// Def chain doesn't include itself, and even if there isn't a
// def chain, this name should be added to exports.
bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
@@ -337,9 +473,13 @@ gori_map::calculate_gori (basic_block bb)
{
tree name;
if (bb->index >= (signed int)m_outgoing.length ())
- m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
+ {
+ m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
+ m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
+ }
gcc_checking_assert (m_outgoing[bb->index] == NULL);
m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps);
+ m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps);
// If this block's last statement may generate range informaiton, go
// calculate it.
@@ -368,65 +508,42 @@ gori_map::calculate_gori (basic_block bb)
// Dump the table information for BB to file F.
void
-gori_map::dump (FILE *f, basic_block bb)
+gori_map::dump (FILE *f, basic_block bb, bool verbose)
{
- bool header = false;
- const char *header_string = "bb%-4d ";
- const char *header2 = " ";
- bool printed_something = false;;
- unsigned x, y;
- bitmap_iterator bi;
-
// BB was not processed.
- if (!m_outgoing[bb->index])
+ if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index]))
return;
- // Dump the def chain for each SSA_NAME defined in BB.
- for (x = 1; x < num_ssa_names; x++)
+ tree name;
+
+ bitmap imp = imports (bb);
+ if (!bitmap_empty_p (imp))
{
- tree name = ssa_name (x);
- if (!name)
- continue;
- gimple *stmt = SSA_NAME_DEF_STMT (name);
- bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
- if (stmt && gimple_bb (stmt) == bb && chain && !bitmap_empty_p (chain))
- {
- fprintf (f, header_string, bb->index);
- header_string = header2;
- header = true;
+ if (verbose)
+ fprintf (f, "bb<%u> Imports: ",bb->index);
+ else
+ fprintf (f, "Imports: ");
+ FOR_EACH_GORI_IMPORT_NAME (*this, bb, name)
+ {
print_generic_expr (f, name, TDF_SLIM);
- fprintf (f, " : ");
- EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
- {
- print_generic_expr (f, ssa_name (y), TDF_SLIM);
- fprintf (f, " ");
- }
- fprintf (f, "\n");
+ fprintf (f, " ");
}
+ fputc ('\n', f);
}
- printed_something |= header;
-
- // Now dump the export vector.
- header = false;
- EXECUTE_IF_SET_IN_BITMAP (m_outgoing[bb->index], 0, y, bi)
+ if (verbose)
+ fprintf (f, "bb<%u> Exports: ",bb->index);
+ else
+ fprintf (f, "Exports: ");
+ // Dump the export vector.
+ FOR_EACH_GORI_EXPORT_NAME (*this, bb, name)
{
- if (!header)
- {
- fprintf (f, header_string, bb->index);
- fprintf (f, "exports: ");
- header_string = header2;
- header = true;
- }
- print_generic_expr (f, ssa_name (y), TDF_SLIM);
+ print_generic_expr (f, name, TDF_SLIM);
fprintf (f, " ");
}
- if (header)
- fputc ('\n', f);
+ fputc ('\n', f);
- printed_something |= header;
- if (printed_something)
- fprintf (f, "\n");
+ range_def_chain::dump (f, bb, " ");
}
// Dump the entire GORI map structure to file F.
@@ -436,11 +553,7 @@ gori_map::dump (FILE *f)
{
basic_block bb;
FOR_EACH_BB_FN (bb, cfun)
- {
- dump (f, bb);
- if (m_outgoing[bb->index])
- fprintf (f, "\n");
- }
+ dump (f, bb);
}
DEBUG_FUNCTION void
@@ -960,8 +1073,7 @@ gori_compute::has_edge_range_p (tree name, edge e)
if (!e)
return is_export_p (name);
- return (is_export_p (name, e->src)
- || def_chain_in_export_p (name, e->src));
+ return is_export_p (name, e->src);
}
// Dump what is known to GORI computes to listing file F.
@@ -1006,6 +1118,50 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name)
return false;
}
+
+// ------------------------------------------------------------------------
+// GORI iterator. Although we have bitmap iterators, don't expose that it
+// is currently a bitmap. Use an export iterator to hide future changes.
+
+// Construct a basic iterator over an export bitmap.
+
+gori_export_iterator::gori_export_iterator (bitmap b)
+{
+ bm = b;
+ if (b)
+ bmp_iter_set_init (&bi, b, 1, &y);
+}
+
+
+// Move to the next export bitmap spot.
+
+void
+gori_export_iterator::next ()
+{
+ bmp_iter_next (&bi, &y);
+}
+
+
+// Fetch the name of the next export in the export list. Return NULL if
+// iteration is done.
+
+tree
+gori_export_iterator::get_name ()
+{
+ if (!bm)
+ return NULL_TREE;
+
+ while (bmp_iter_set (&bi, &y))
+ {
+ tree t = ssa_name (y);
+ if (t)
+ return t;
+ next ();
+ }
+ return NULL_TREE;
+}
+
+
// --------------------------------------------------------------------------
// Cache for SSAs that appear on the RHS of a boolean assignment.
@@ -31,15 +31,55 @@ class range_def_chain
public:
range_def_chain ();
~range_def_chain ();
+ tree depend1 (tree name) const;
+ tree depend2 (tree name) const;
+ bool in_chain_p (tree name, tree def);
+ bool chain_import_p (tree name, tree import);
+ void register_dependency (tree name, tree ssa1, basic_block bb = NULL);
+ void dump (FILE *f, basic_block bb, const char *prefix = NULL);
+protected:
bool has_def_chain (tree name);
+ bool def_chain_in_bitmap_p (tree name, bitmap b);
+ void add_def_chain_to_bitmap (bitmap b, tree name);
bitmap get_def_chain (tree name);
- bool in_chain_p (tree name, tree def);
+ bitmap get_imports (tree name);
+ bitmap_obstack m_bitmaps;
private:
- vec<bitmap> m_def_chain; // SSA_NAME : def chain components.
- void build_def_chain (tree name, bitmap result, basic_block bb);
+ struct rdc {
+ tree ssa1; // First direct dependency
+ tree ssa2; // Second direct dependency
+ bitmap bm; // All dependencies
+ bitmap m_import;
+ };
+ vec<rdc> m_def_chain; // SSA_NAME : def chain components.
+ void set_import (struct rdc &data, tree imp, bitmap b);
int m_logical_depth;
};
+// Return the first direct dependency for NAME, if there is one.
+// Direct dependencies are those which occur on the defintion statement.
+// Only the first 2 such names are cached.
+
+inline tree
+range_def_chain::depend1 (tree name) const
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_def_chain.length ())
+ return NULL_TREE;
+ return m_def_chain[v].ssa1;
+}
+
+// Return the second direct dependency for NAME, if there is one.
+
+inline tree
+range_def_chain::depend2 (tree name) const
+{
+ unsigned v = SSA_NAME_VERSION (name);
+ if (v >= m_def_chain.length ())
+ return NULL_TREE;
+ return m_def_chain[v].ssa2;
+}
+
// GORI_MAP is used to accumulate what SSA names in a block can
// generate range information, and provides tools for the block ranger
// to enable it to efficiently calculate these ranges.
@@ -51,15 +91,16 @@ public:
~gori_map ();
bool is_export_p (tree name, basic_block bb = NULL);
- bool def_chain_in_export_p (tree name, basic_block bb);
+ bool is_import_p (tree name, basic_block bb);
bitmap exports (basic_block bb);
+ bitmap imports (basic_block bb);
void set_range_invariant (tree name);
void dump (FILE *f);
- void dump (FILE *f, basic_block bb);
+ void dump (FILE *f, basic_block bb, bool verbose = true);
private:
- bitmap_obstack m_bitmaps;
vec<bitmap> m_outgoing; // BB: Outgoing ranges calculatable on edges
+ vec<bitmap> m_incoming; // BB: Incoming ranges which can affect exports.
bitmap m_maybe_variant; // Names which might have outgoing ranges.
void maybe_add_gori (tree name, basic_block bb);
void calculate_gori (basic_block bb);
@@ -152,6 +193,30 @@ private:
};
+// For each name that is an import into BB's exports..
+#define FOR_EACH_GORI_IMPORT_NAME(gori, bb, name) \
+ for (gori_export_iterator iter ((gori).imports ((bb))); \
+ ((name) = iter.get_name ()); \
+ iter.next ())
+
+// For each name possibly exported from block BB.
+#define FOR_EACH_GORI_EXPORT_NAME(gori, bb, name) \
+ for (gori_export_iterator iter ((gori).exports ((bb))); \
+ ((name) = iter.get_name ()); \
+ iter.next ())
+
+// Used to assist with iterating over the GORI export list in various ways
+class gori_export_iterator {
+public:
+ gori_export_iterator (bitmap b);
+ void next ();
+ tree get_name ();
+protected:
+ bitmap bm;
+ bitmap_iterator bi;
+ unsigned y;
+};
+
// This class adds a cache to gori_computes for logical expressions.
// bool result = x && y
// requires calcuation of both X and Y for both true and false results.
--
2.17.2
This patch introduced imports to range_def, and corrects some minor issues with export calculation. When gori-compute is evaluating sequences in a block: - an "export" is defined as any ssa_name which may have a range calculated on an outgoing edge. If the edge may CHANGE the value of ssa-name from its on-entry/exit value, then it is an export. - an "import" is any ssa name which which may affect the outgoing value of an export. This may be the ssa_anme itself, or and ssa_name used in the calculation of the ssa_name value. bb5: b_6 = a_4 + 5 c_5 = b_6 < z_9 if (c_5 != 0) in this small sample c_5, b_6, z_9 and a_4 are all exports, because we may be able to refine a range for any of them on one of the edges a_4 and z_9 are considered imports because those are the ssa_names which have definitions occurring outside the block which can affect the value of any an exports. This patch introduces imports to both range_def and gori_map, as well as standardizes the dependency chain registration API so we can also cache up to 2 direct dependent names and eventually utilize that for re-computation and the temporal cache. Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed. Andrew