The code presented at the time wrestrict was invoking ranger has a basic
block with about 7200 statements, all of them calculations which fed
into 2614 logical ORs and 1480 logical ANDs.
the GORI component which calculates outgoing ranges starts at the exit
of the block and works it way back thru the basic block to the ssa_name
requested, solving the equations along the way.
Logical expressions require a TRUE and FALSE results to be calculated
for the ssa_name for each of two condition register operands on the
logical expression. Sometimes we can shortcut it, but frequently it its
requires all 4 to properly evaluate.
When logical operations feed each other, this can become exponential..
and that was the situation here.
We had introduced a logical cache to attempt to reduce the number of
calculations, but it was insufficient. We had previously discussed
among ourselves that limiting the depth was probably suifficient, since
the odds of being able to extract a meaningful range thru a large series
of logical operations becomes highly unlikely.
THis patch implements the depth limiter for logical statements and sets
it at 6. so more than 6 logical statements feeding each other, and we
decide its not worth looking back any further and say this edge does not
compute a range.
This passes bootstrap and regression testing on x86_64-pc-linux-gnu. I
also ran it against the unlimited depth version on a full set of GCC
source files, and there was 0 difference between this and the original.
I also disable the logical cache since it isn't really doing anything
any more.
OK for trunk?
Andrew
PS. first mail from a new mailer system... hopefully it formats ok......
commit 9d04ed1ca8c2acddd89a398d0dd96e3924dd15cb
Author: Andrew MacLeod <amacl...@redhat.com>
Date: Fri Apr 16 17:08:51 2021 -0400
Limit depth of logical expression windback.
Limit how many exponentially expanded logical expressions GORI will look
back thru when evaluating outgoing edge range.
PR tree-optimization/100081
* gimple-range-cache.h (ranger_cache): Inherit from gori_compute
not gori_compute_cache.
* gimple_range_gori.cc (gori_compute::gori_compute): Initialize
m_logical_depth.
(gori_compute::compute_logical_operands): Limit depth to 6.
* gimple_range_gori.h (gori_compute): Add m_logical_depth member.
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index c98e9871734..2b36a02654b 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -87,7 +87,7 @@ private:
// them available for gori-computes to query so outgoing edges can be
// properly calculated.
-class ranger_cache : public gori_compute_cache
+class ranger_cache : public gori_compute
{
public:
ranger_cache (class gimple_ranger &q);
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 7f7f3dc0d69..6e0bd0fe6a5 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -464,6 +464,7 @@ gori_compute::gori_compute ()
if (bb)
m_gori_map->exports (bb);
}
+ m_logical_depth = 0;
}
// Destruct a gori_compute_object.
@@ -851,6 +852,9 @@ gori_compute::compute_logical_operands_in_chain (tf_range
&range,
expr_range_in_bb (range.false_range, name, bb);
}
+// Set the maximum depth we will analyze logical combinations.
+#define LOGICAL_LIMIT 6
+
// Given a logical STMT, calculate true and false for each potential
// path using NAME, and resolve the outcome based on the logical
// operator.
@@ -875,11 +879,17 @@ gori_compute::compute_logical_operands (irange &r, gimple
*stmt,
if (!op1_in_chain && !op2_in_chain)
return false;
+ if (m_logical_depth > LOGICAL_LIMIT)
+ return false;
+ m_logical_depth++;
+
tf_range op1_range, op2_range;
compute_logical_operands_in_chain (op1_range, stmt, lhs,
name, op1, op1_in_chain);
compute_logical_operands_in_chain (op2_range, stmt, lhs,
name, op2, op2_in_chain);
+ m_logical_depth--;
+
return logical_combine (r, gimple_expr_code (stmt), lhs,
op1_range, op2_range);
}
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 48c746d1f37..513c0acd11f 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -94,6 +94,7 @@ protected:
const class tf_range &op2_range);
int_range<2> m_bool_zero; // Boolean false cached.
int_range<2> m_bool_one; // Boolean true cached.
+ int m_logical_depth;
private:
bool compute_operand_range_switch (irange &r, gswitch *stmt,
