From a6e94287d31525b3ad0963ad22a92e9f3dbcd3cf Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 25 May 2021 14:59:54 -0400
Subject: [PATCH 8/8] Remove the logical stmt cache for now.
With the depth limiting, we are not currently using the logical stmt cache.
* gimple-range-gori.cc (class logical_stmt_cache): Delete
(logical_stmt_cache::logical_stmt_cache ): Delete.
(logical_stmt_cache::~logical_stmt_cache): Delete.
(logical_stmt_cache::cache_entry::dump): Delete.
(logical_stmt_cache::get_range): Delete.
(logical_stmt_cache::cached_name ): Delete.
(logical_stmt_cache::same_cached_name): Delete.
(logical_stmt_cache::cacheable_p): Delete.
(logical_stmt_cache::slot_diagnostics ): Delete.
(logical_stmt_cache::dump): Delete.
(gori_compute_cache::gori_compute_cache): Delete.
(gori_compute_cache::~gori_compute_cache): Delete.
(gori_compute_cache::compute_operand_range): Delete.
(gori_compute_cache::cache_stmt): Delete.
* gimple-range-gori.h (gori_compute::compute_operand_range): Remove
virtual.
(class gori_compute_cache): Delete.
---
gcc/gimple-range-gori.cc | 311 ---------------------------------------
gcc/gimple-range-gori.h | 31 +---
2 files changed, 2 insertions(+), 340 deletions(-)
@@ -1160,314 +1160,3 @@ gori_export_iterator::get_name ()
}
return NULL_TREE;
}
-
-
-// --------------------------------------------------------------------------
-
-// Cache for SSAs that appear on the RHS of a boolean assignment.
-//
-// Boolean assignments of logical expressions (i.e. LHS = j_5 > 999)
-// have SSA operands whose range depend on the LHS of the assigment.
-// That is, the range of j_5 when LHS is true is different than when
-// LHS is false.
-//
-// This class caches the TRUE/FALSE ranges of such SSAs to avoid
-// recomputing.
-
-class logical_stmt_cache
-{
-public:
- logical_stmt_cache ();
- ~logical_stmt_cache ();
- void set_range (tree lhs, tree name, const tf_range &);
- bool get_range (tf_range &r, tree lhs, tree name) const;
- bool cacheable_p (gimple *, const irange *lhs_range = NULL) const;
- void dump (FILE *, gimple *stmt) const;
- tree same_cached_name (tree lhs1, tree lh2) const;
-private:
- tree cached_name (tree lhs) const;
- void slot_diagnostics (tree lhs, const tf_range &range) const;
- struct cache_entry
- {
- cache_entry (tree name, const irange &t_range, const irange &f_range);
- void dump (FILE *out) const;
- tree name;
- tf_range range;
- };
- vec<cache_entry *> m_ssa_cache;
-};
-
-logical_stmt_cache::cache_entry::cache_entry (tree name,
- const irange &t_range,
- const irange &f_range)
- : name (name), range (t_range, f_range)
-{
-}
-
-logical_stmt_cache::logical_stmt_cache ()
-{
- m_ssa_cache.create (num_ssa_names + num_ssa_names / 10);
- m_ssa_cache.safe_grow_cleared (num_ssa_names);
-}
-
-logical_stmt_cache::~logical_stmt_cache ()
-{
- for (unsigned i = 0; i < m_ssa_cache.length (); ++i)
- if (m_ssa_cache[i])
- delete m_ssa_cache[i];
- m_ssa_cache.release ();
-}
-
-// Dump cache_entry to OUT.
-
-void
-logical_stmt_cache::cache_entry::dump (FILE *out) const
-{
- fprintf (out, "name=");
- print_generic_expr (out, name, TDF_SLIM);
- fprintf (out, " ");
- range.true_range.dump (out);
- fprintf (out, ", ");
- range.false_range.dump (out);
- fprintf (out, "\n");
-}
-
-// Update range for cache entry of NAME as it appears in the defining
-// statement of LHS.
-
-void
-logical_stmt_cache::set_range (tree lhs, tree name, const tf_range &range)
-{
- unsigned version = SSA_NAME_VERSION (lhs);
- if (version >= m_ssa_cache.length ())
- m_ssa_cache.safe_grow_cleared (num_ssa_names + num_ssa_names / 10);
-
- cache_entry *slot = m_ssa_cache[version];
- slot_diagnostics (lhs, range);
- if (slot)
- {
- // The IL must have changed. Update the carried SSA name for
- // consistency. Testcase is libgomp.fortran/doacross1.f90.
- if (slot->name != name)
- slot->name = name;
- return;
- }
- m_ssa_cache[version]
- = new cache_entry (name, range.true_range, range.false_range);
-}
-
-// If there is a cached entry of NAME, set it in R and return TRUE,
-// otherwise return FALSE. LHS is the defining statement where NAME
-// appeared.
-
-bool
-logical_stmt_cache::get_range (tf_range &r, tree lhs, tree name) const
-{
- gcc_checking_assert (cacheable_p (SSA_NAME_DEF_STMT (lhs)));
- if (cached_name (lhs) == name)
- {
- unsigned version = SSA_NAME_VERSION (lhs);
- if (m_ssa_cache[version])
- {
- r = m_ssa_cache[version]->range;
- return true;
- }
- }
- return false;
-}
-
-// If the defining statement of LHS is in the cache, return the SSA
-// operand being cached. That is, return SSA for LHS = SSA .RELOP. OP2.
-
-tree
-logical_stmt_cache::cached_name (tree lhs) const
-{
- unsigned version = SSA_NAME_VERSION (lhs);
-
- if (version >= m_ssa_cache.length ())
- return NULL;
-
- if (m_ssa_cache[version])
- return m_ssa_cache[version]->name;
- return NULL;
-}
-
-// Return TRUE if the cached name for LHS1 is the same as the
-// cached name for LHS2.
-
-tree
-logical_stmt_cache::same_cached_name (tree lhs1, tree lhs2) const
-{
- tree name = cached_name (lhs1);
- if (name && name == cached_name (lhs2))
- return name;
- return NULL;
-}
-
-// Return TRUE if STMT is a statement we are interested in caching.
-// LHS_RANGE is any known range for the LHS of STMT.
-
-bool
-logical_stmt_cache::cacheable_p (gimple *stmt, const irange *lhs_range) const
-{
- if (gimple_code (stmt) == GIMPLE_ASSIGN
- && types_compatible_p (TREE_TYPE (gimple_assign_lhs (stmt)),
- boolean_type_node)
- && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
- {
- switch (gimple_expr_code (stmt))
- {
- case TRUTH_AND_EXPR:
- case BIT_AND_EXPR:
- case TRUTH_OR_EXPR:
- case BIT_IOR_EXPR:
- return !lhs_range || range_is_either_true_or_false (*lhs_range);
- default:
- return false;
- }
- }
- return false;
-}
-
-// Output debugging diagnostics for the cache entry for LHS. RANGE is
-// the new range that is being cached.
-
-void
-logical_stmt_cache::slot_diagnostics (tree lhs, const tf_range &range) const
-{
- gimple *stmt = SSA_NAME_DEF_STMT (lhs);
- unsigned version = SSA_NAME_VERSION (lhs);
- cache_entry *slot = m_ssa_cache[version];
-
- if (!slot)
- {
- if (DEBUG_RANGE_CACHE)
- {
- fprintf (dump_file ? dump_file : stderr, "registering range for: ");
- dump (dump_file ? dump_file : stderr, stmt);
- }
- return;
- }
- if (DEBUG_RANGE_CACHE)
- fprintf (dump_file ? dump_file : stderr,
- "reusing range for SSA #%d\n", version);
- if (CHECKING_P && (slot->range.true_range != range.true_range
- || slot->range.false_range != range.false_range))
- {
- fprintf (stderr, "FATAL: range altered for cached: ");
- dump (stderr, stmt);
- fprintf (stderr, "Attempt to change to:\n");
- fprintf (stderr, "TRUE=");
- range.true_range.dump (stderr);
- fprintf (stderr, ", FALSE=");
- range.false_range.dump (stderr);
- fprintf (stderr, "\n");
- gcc_unreachable ();
- }
-}
-
-// Dump the cache information for STMT.
-
-void
-logical_stmt_cache::dump (FILE *out, gimple *stmt) const
-{
- tree lhs = gimple_assign_lhs (stmt);
- cache_entry *entry = m_ssa_cache[SSA_NAME_VERSION (lhs)];
-
- print_gimple_stmt (out, stmt, 0, TDF_SLIM);
- if (entry)
- {
- fprintf (out, "\tname = ");
- print_generic_expr (out, entry->name);
- fprintf (out, " lhs(%d)= ", SSA_NAME_VERSION (lhs));
- print_generic_expr (out, lhs);
- fprintf (out, "\n\tTRUE=");
- entry->range.true_range.dump (out);
- fprintf (out, ", FALSE=");
- entry->range.false_range.dump (out);
- fprintf (out, "\n");
- }
- else
- fprintf (out, "[EMPTY]\n");
-}
-
-gori_compute_cache::gori_compute_cache ()
-{
- m_cache = new logical_stmt_cache;
-}
-
-gori_compute_cache::~gori_compute_cache ()
-{
- delete m_cache;
-}
-
-// Caching version of compute_operand_range. If NAME, as it appears
-// in STMT, has already been cached return it from the cache,
-// otherwise compute the operand range as normal and cache it.
-
-bool
-gori_compute_cache::compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs_range, tree name)
-{
- bool cacheable = m_cache->cacheable_p (stmt, &lhs_range);
- if (cacheable)
- {
- tree lhs = gimple_assign_lhs (stmt);
- tf_range range;
- if (m_cache->get_range (range, lhs, name))
- {
- if (lhs_range.zero_p ())
- r = range.false_range;
- else
- r = range.true_range;
- return true;
- }
- }
- if (super::compute_operand_range (r, stmt, lhs_range, name))
- {
- if (cacheable)
- cache_stmt (stmt);
- return true;
- }
- return false;
-}
-
-// Cache STMT if possible.
-
-void
-gori_compute_cache::cache_stmt (gimple *stmt)
-{
- gcc_checking_assert (m_cache->cacheable_p (stmt));
- enum tree_code code = gimple_expr_code (stmt);
- tree lhs = gimple_assign_lhs (stmt);
- tree op1 = gimple_range_operand1 (stmt);
- tree op2 = gimple_range_operand2 (stmt);
- int_range_max r_true_side, r_false_side;
-
- // LHS = s_5 && 999.
- if (TREE_CODE (op2) == INTEGER_CST)
- {
- range_operator *handler = range_op_handler (code, TREE_TYPE (lhs));
- int_range_max op2_range;
- expr_range_at_stmt (op2_range, op2, stmt);
- tree type = TREE_TYPE (op1);
- handler->op1_range (r_true_side, type, m_bool_one, op2_range);
- handler->op1_range (r_false_side, type, m_bool_zero, op2_range);
- m_cache->set_range (lhs, op1, tf_range (r_true_side, r_false_side));
- }
- // LHS = s_5 && b_8.
- else if (tree cached_name = m_cache->same_cached_name (op1, op2))
- {
- tf_range op1_range, op2_range;
- bool ok = m_cache->get_range (op1_range, op1, cached_name);
- ok = ok && m_cache->get_range (op2_range, op2, cached_name);
- ok = ok && logical_combine (r_true_side, code, m_bool_one,
- op1_range, op2_range);
- ok = ok && logical_combine (r_false_side, code, m_bool_zero,
- op1_range, op2_range);
- gcc_checking_assert (ok);
- if (ok)
- m_cache->set_range (lhs, cached_name,
- tf_range (r_true_side, r_false_side));
- }
-}
@@ -158,8 +158,8 @@ public:
void dump (FILE *f);
protected:
virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb);
- virtual bool compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs, tree name);
+ bool compute_operand_range (irange &r, gimple *stmt,
+ const irange &lhs, tree name);
void expr_range_at_stmt (irange &r, tree expr, gimple *s);
bool compute_logical_operands (irange &r, gimple *stmt,
@@ -217,31 +217,4 @@ protected:
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.
-// There are 4 combinations [0,0][0,0] [0,0][1,1] [1,1][0,0] and [1,1][1,1].
-// Note that each pair of possible results for X and Y are used twice, and
-// the calcuation of those results are the same each time.
-//
-// The cache simply checks if a stmt is cachable, and if so, saves both the
-// true and false results for the next time the query is made.
-//
-// This is used to speed up long chains of logical operations which
-// quickly become exponential.
-
-class gori_compute_cache : public gori_compute
-{
-public:
- gori_compute_cache ();
- ~gori_compute_cache ();
-protected:
- virtual bool compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs, tree name);
-private:
- void cache_stmt (gimple *);
- typedef gori_compute super;
- class logical_stmt_cache *m_cache;
-};
-
#endif // GCC_GIMPLE_RANGE_GORI_H
--
2.17.2