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 in this case. We had previously
discussed among ourselves that limiting the depth was probably
sufficient, 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. If there are more than 6 logical statements feeding each
other we decide its not worth looking back any further... and say this
edge does not compute a range for that SSA_NAME.
This is different than the original patch I proposed in the PR, but
accomplishes the same thing. The original patch did the depth limit
check at the time of evaluating an outgoing range. This patch moves the
check earlier when building the def chains, so the names never even
appear as possible exports. The previous patch was still building these
def chains a few thousand SSA names deep, but never using them due to
the cutoff. This patch will also therefore reduce the size of those
dependency bitmaps which are not going to be used in either case.
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
in the cases ranger gets.
OK for trunk?
Andrew
PS. Second try with a new mailer system... hopefully this time...
commit a36a130a1305bc2c103e47955354c0f0edda47f4
Author: Andrew MacLeod <amacl...@redhat.com>
Date: Fri Apr 16 17:08:51 2021 -0400
Limit depth of logical expression windback.
Limit how many logical expressions GORI will look back through when
evaluating outgoing edge range.
PR tree-optimization/100081
* gimple_range_gori.cc (LOGICAL_LIMIT): New local definition.
(is_gimple_logical_p): Move to top of file.
(range_def_chain::m_logical_depth): New member.
(range_def_chain::range_def_chain): Initialize m_logical_depth.
(range_def_chain::get_def_chain): Don't build defchains through more
than LOGICAL_LIMIT logical expressions.
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 7f7f3dc0d69..4be49369bbd 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -29,6 +29,36 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-pretty-print.h"
#include "gimple-range.h"
+// Limit the nested depth thru logical expressions which GORI will build
+// def chains.
+#define LOGICAL_LIMIT 6
+
+// Return TRUE if GS is a logical && or || expression.
+
+static inline bool
+is_gimple_logical_p (const gimple *gs)
+{
+ // Look for boolean and/or condition.
+ if (gimple_code (gs) == GIMPLE_ASSIGN)
+ switch (gimple_expr_code (gs))
+ {
+ case TRUTH_AND_EXPR:
+ case TRUTH_OR_EXPR:
+ return true;
+
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ // Bitwise operations on single bits are logical too.
+ if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
+ boolean_type_node))
+ return true;
+ break;
+
+ default:
+ break;
+ }
+ return false;
+}
/* RANGE_DEF_CHAIN is used to determine what SSA names in a block can
have range information calculated for them, and what the
@@ -76,6 +106,7 @@ public:
private:
vec<bitmap> m_def_chain; // SSA_NAME : def chain components.
void build_def_chain (tree name, bitmap result, basic_block bb);
+ int m_logical_depth;
};
@@ -85,6 +116,7 @@ range_def_chain::range_def_chain ()
{
m_def_chain.create (0);
m_def_chain.safe_grow_cleared (num_ssa_names);
+ m_logical_depth = 0;
}
// Destruct a range_def_chain.
@@ -157,6 +189,7 @@ range_def_chain::get_def_chain (tree name)
{
tree ssa1, ssa2, ssa3;
unsigned v = SSA_NAME_VERSION (name);
+ bool is_logical = false;
// If it has already been processed, just return the cached value.
if (has_def_chain (name))
@@ -169,6 +202,15 @@ range_def_chain::get_def_chain (tree name)
gimple *stmt = SSA_NAME_DEF_STMT (name);
if (gimple_range_handler (stmt))
{
+ is_logical = is_gimple_logical_p (stmt);
+ // Terminate the def chains if we see too many cascading logical stmts.
+ if (is_logical)
+ {
+ if (m_logical_depth == LOGICAL_LIMIT)
+ return NULL;
+ m_logical_depth++;
+ }
+
ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
ssa3 = NULL_TREE;
@@ -195,6 +237,9 @@ range_def_chain::get_def_chain (tree name)
if (ssa3)
build_def_chain (ssa3, m_def_chain[v], bb);
+ 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
@@ -562,32 +607,6 @@ gori_compute::compute_operand_range_switch (irange &r, gswitch *s,
return false;
}
-// Return TRUE if GS is a logical && or || expression.
-
-static inline bool
-is_gimple_logical_p (const gimple *gs)
-{
- // Look for boolean and/or condition.
- if (gimple_code (gs) == GIMPLE_ASSIGN)
- switch (gimple_expr_code (gs))
- {
- case TRUTH_AND_EXPR:
- case TRUTH_OR_EXPR:
- return true;
-
- case BIT_AND_EXPR:
- case BIT_IOR_EXPR:
- // Bitwise operations on single bits are logical too.
- if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
- boolean_type_node))
- return true;
- break;
-
- default:
- break;
- }
- return false;
-}
// Return an evaluation for NAME as it would appear in STMT when the
// statement's lhs evaluates to LHS. If successful, return TRUE and
