This patch simplifies tree-scalar-evolution's expensive_expression_p, but
produces identical results; the replacement implementation is just smaller
(uses less memory), faster and easier to understand.
The current idiom (introduced to fix PR90726) looks like:
hash_map<tree, uint64_t> cache;
uint64_t expanded_size = 0;
return (expression_expensive_p (expr, cache, expanded_size)
|| expanded_size > cache.elements ());
Here the recursive function computes expanded_size, effectively the
number of tree nodes visited, which is then only used in the comparison
against cache.elements(), i.e. to check whether the number of visited
nodes is greater than the number of unique visited nodes. This is
equivalent to instead checking where expression_expensive_p's recursion
visits any node more than once.
Instead of using a map to cache the "cost" of revisited sub-trees, the
same outcome can be determined using a set, and immediately returning
true as soon as encountering a previously seen tree node, avoiding the
unnecessary "cost"/expanded_size computation. [A simplification analogous
to checking STL's empty() instead of comparing size() with zero].
The semantics of expensive_expression_p (both before and after) are
quite reasonable, as calling unshare_expr on a generic tree can result
in an exponential growth in the number of gimple statements, hence
any "shared" nodes are indeed expensive. If shared nodes are to be
allowed, they'll need to be managed explicitly with SAVE_EXPR (or similar
mechanism) that avoids exponential growth.
This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
and make -k check, both with and without --target_board=unix{-m32}, with
no new failures. Is this a reasonable clean-up for mainline?
2022-05-17 Roger Sayle <ro...@nextmovesoftware.com>
gcc/ChangeLog
* tree_scalar_evolution.cc (expression_expensive_p): Change type
of cache from hash_map to hash_set, and remove cost argument.
When expr appears in the hash_set, return true. Calculation of
cost (and updating hash_map) is no longer required.
(expression_expensive_p): Simplify top-level implementation.
Thanks in advance,
Roger
--
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index 72ceb40..347dede 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3352,8 +3352,7 @@ scev_finalize (void)
for scev_const_prop. */
static bool
-expression_expensive_p (tree expr, hash_map<tree, uint64_t> &cache,
- uint64_t &cost)
+expression_expensive_p (tree expr, hash_set<tree> &cache)
{
enum tree_code code;
@@ -3377,19 +3376,11 @@ expression_expensive_p (tree expr, hash_map<tree,
uint64_t> &cache,
return true;
}
- bool visited_p;
- uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
- if (visited_p)
- {
- uint64_t tem = cost + local_cost;
- if (tem < cost)
- return true;
- cost = tem;
- return false;
- }
- local_cost = 1;
+ /* If we've encountered this expression before, it would be duplicated
+ by unshare_expr, which makes this expression expensive. */
+ if (cache.add (expr))
+ return true;
- uint64_t op_cost = 0;
if (code == CALL_EXPR)
{
tree arg;
@@ -3431,16 +3422,14 @@ expression_expensive_p (tree expr, hash_map<tree,
uint64_t> &cache,
}
FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
- if (expression_expensive_p (arg, cache, op_cost))
+ if (expression_expensive_p (arg, cache))
return true;
- *cache.get (expr) += op_cost;
- cost += op_cost + 1;
return false;
}
if (code == COND_EXPR)
{
- if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost)
+ if (expression_expensive_p (TREE_OPERAND (expr, 0), cache)
|| (EXPR_P (TREE_OPERAND (expr, 1))
&& EXPR_P (TREE_OPERAND (expr, 2)))
/* If either branch has side effects or could trap. */
@@ -3448,13 +3437,9 @@ expression_expensive_p (tree expr, hash_map<tree,
uint64_t> &cache,
|| generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
|| TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
|| generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
- || expression_expensive_p (TREE_OPERAND (expr, 1),
- cache, op_cost)
- || expression_expensive_p (TREE_OPERAND (expr, 2),
- cache, op_cost))
+ || expression_expensive_p (TREE_OPERAND (expr, 1), cache)
+ || expression_expensive_p (TREE_OPERAND (expr, 2), cache))
return true;
- *cache.get (expr) += op_cost;
- cost += op_cost + 1;
return false;
}
@@ -3462,15 +3447,13 @@ expression_expensive_p (tree expr, hash_map<tree,
uint64_t> &cache,
{
case tcc_binary:
case tcc_comparison:
- if (expression_expensive_p (TREE_OPERAND (expr, 1), cache, op_cost))
+ if (expression_expensive_p (TREE_OPERAND (expr, 1), cache))
return true;
/* Fallthru. */
case tcc_unary:
- if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost))
+ if (expression_expensive_p (TREE_OPERAND (expr, 0), cache))
return true;
- *cache.get (expr) += op_cost;
- cost += op_cost + 1;
return false;
default:
@@ -3481,10 +3464,8 @@ expression_expensive_p (tree expr, hash_map<tree,
uint64_t> &cache,
bool
expression_expensive_p (tree expr)
{
- hash_map<tree, uint64_t> cache;
- uint64_t expanded_size = 0;
- return (expression_expensive_p (expr, cache, expanded_size)
- || expanded_size > cache.elements ());
+ hash_set<tree> cache;
+ return expression_expensive_p (expr, cache);
}
/* Do final value replacement for LOOP, return true if we did anything. */
