This is a very compelling patch to me. It integrates many of rangers
components to accomplish something relatively easily. I think it makes
a good educational example of some of the features available.
Ranger already records relations discovered during normal range
propagation, but there are cases where no explicit relation is ever
created even though one is implied by an outgoing edge based on
information discovered later.
This patch teaches the dominator relation query to reconstruct those
missing relations on demand. When a promising outgoing edge is
encountered (both names are exported, meaning they have potential ranges
generated on the edge) , the query walks backward through the dependency
chain using Ranger's inverse operator framework. Starting from the range
implied by the edge, each operator recomputes the range of the dependent
operand using the known range of the other operand at the original query
block. If the walk reaches a statement containing both requested SSA
names, the operator is asked to derive the relation directly from the
recomputed operand ranges.
For example, given:
|_1 = (p == q); _2 = (flag != 0); _3 = _1 & _2; if (_3 != 0) return; if
(flag == 0) return; /* We are now dominated by flag != 0. */ ... if (p != q)|
On the false edge from the |_3|test, Ranger knows |_3 == 0|. At the
later query point, the dominating |flag == 0|test tells us |flag != 0|,
so therefore |_2 == 1|. Walking backward through the dependency chain,
the inverse evaluation of the logical AND yields |_1 == 0|. Since
|_1|represents |(p == q)|, Ranger can conclude |p != q|, even though no
explicit relation was ever recorded.
The implementation is almost entirely composed from existing Ranger
infrastructure: GORI edge ranges, dependency-chain queries, inverse
operator evaluation (|calc_op1| / |calc_op2|), range queries at
arbitrary program points, and operator relation generation. No new
propagation machinery is required; the existing components are simply
combined to answer a more sophisticated query.
Along the way I also found that the set _one_relation routine was
checking for existing relations in the start block twice. oops. fixed
that too.
Performance impact is pretty minimal. .017% slower in VRP, 0.01% overall.
Bootstrapped on x86_64-pc-linux-gnu with no new regressions. pushed.
Andrew
From 66ee46ec21e8ef2b131fb4e9d04c4e6aaa57f5a4 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Thu, 16 Jul 2026 11:56:17 -0400
Subject: [PATCH 2/3] Recompute relations during a relation query walk.
While querying relations we do a DOM walk. This patch adds a query that
will recompute potential relations on edges which look promising.
PR tree-optimization/126212
gcc/
* value-relation.cc (dom_oracle::set_one_relation): Start with
first dominator in the dominator search.
(dom_oracle::recomputed_relation): New.
(dom_oracle::find_relation_dom): query recomputed_relation.
* value-relation.h (dom_oracle::recomputed_relation): New prototype.
gcc/testsuite/
* gcc.dg/pr126212.c: New.
---
gcc/testsuite/gcc.dg/pr126212.c | 25 ++++++
gcc/value-relation.cc | 148 ++++++++++++++++++++++++++++++--
gcc/value-relation.h | 2 +-
3 files changed, 169 insertions(+), 6 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr126212.c
diff --git a/gcc/testsuite/gcc.dg/pr126212.c b/gcc/testsuite/gcc.dg/pr126212.c
new file mode 100644
index 00000000000..7d0da397bc2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr126212.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+extern void keep (void);
+extern void kill (void);
+void
+f (void *p, void *q, int flag, int x)
+{
+ int eq = p == q;
+ int nz = flag != 0;
+ int both = eq & nz;
+
+ if (both)
+ return;
+
+ if (!nz)
+ return;
+
+ if (p == q)
+ kill ();
+ else
+ keep ();
+}
+
+/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */
diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index 3ad522ccf64..e8c7a7320de 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1227,7 +1227,8 @@ dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
// Check for an existing relation further up the DOM chain.
// By including dominating relations, The first one found in any search
// will be the aggregate of all the previous ones.
- curr = find_relation_dom (bb, v1, v2);
+ curr = find_relation_dom (get_immediate_dominator (CDI_DOMINATORS, bb),
+ v1, v2);
if (curr != VREL_VARYING)
k = relation_intersect (curr, k);
@@ -1437,25 +1438,162 @@ dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
return VREL_VARYING;
}
+// See if a relation can be found between SSA1 and SSA2 in basic block BB based
+// on values as they exist in basic block ORIG. This will only occur
+// if SSA1 and SSA2 occur in the same statement together.
+
+relation_kind
+dom_oracle::recomputed_relation (basic_block orig_bb, edge e, tree ssa1,
+ tree ssa2) const
+{
+ if (ssa1 == ssa2)
+ return VREL_EQ;
+ gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
+ if (!gori_ssa)
+ return VREL_VARYING;
+
+ // If SSA1 and SSA2 are not BOTH exported from the block, theres no relation.
+ basic_block bb = e->src;
+ if (!gori_ssa->is_export_p (ssa1, bb) || !gori_ssa->is_export_p (ssa2, bb))
+ return VREL_VARYING;
+
+ // Verify the edge is a range generating edge.
+ gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
+ int_range_max edge_range;
+ gimple *stmt = gori.edge_range_p (edge_range, e);
+ if (!stmt)
+ return VREL_VARYING;
+
+ // Scan back thru the dependency chain recalculating values as if they are
+ // in ORIG_BB, and see if we can find a statement with both op1 and op2
+ // which generates a relation.
+
+ value_range lhs_range (edge_range);
+
+ while (stmt)
+ {
+ bool ret;
+ gimple_range_op_handler handler (stmt);
+ if (!handler)
+ return VREL_VARYING;
+
+ tree op1 = handler.operand1 ();
+ tree op2 = handler.operand2 ();
+ value_range op1_range (TREE_TYPE (op1));
+ value_range op2_range;
+
+ // Check if this is the statment we are looking for!
+ bool match = (op1 == ssa1 && op2 == ssa2);
+ bool match_rev = (op2 == ssa1 && op1 == ssa2);
+ if (match || match_rev)
+ {
+ gcc_checking_assert (op2);
+ op2_range.set_range_class (TREE_TYPE (op2));
+ // Pick up the ranges at ORIG_BB, and see if a relation is generated.
+ get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
+ get_range_query (cfun)->range_on_entry (op2_range, orig_bb, op2);
+ relation_kind relation = handler.op1_op2_relation (lhs_range,
+ op1_range,
+ op2_range);
+ // If the operands are reversed, swap the relation.
+ if (match_rev)
+ relation = relation_swap (relation);
+ return relation;
+ }
+
+ // Now determine if one of the operands has both SSA1 and SSA2 in
+ // the dependency chain. Thats the path we want to follow.
+ bool op1_dep = gimple_range_ssa_p (op1)
+ && gori_ssa->in_chain_p (ssa1, op1)
+ && gori_ssa->in_chain_p (ssa2, op1);
+ bool op2_dep = gimple_range_ssa_p (op2)
+ && gori_ssa->in_chain_p (ssa1, op2)
+ && gori_ssa->in_chain_p (ssa2, op2);
+ // If there are no dependencies with both names, or both sides have
+ // both names, simply bail.
+ if (op1_dep == op2_dep)
+ return VREL_VARYING;
+
+ if (op1_dep)
+ {
+ // If operand 1 is the chain we are interested in, calcualte its
+ // range based on LHS_RANGE.
+ if (!op2)
+ ret = handler.calc_op1 (op1_range, lhs_range);
+ else
+ {
+ // Pick up the range of op2 as it occurs in the original block.
+ // and calculate a range for op1.
+ op2_range.set_range_class (TREE_TYPE (op2));
+ get_range_query (cfun)->range_on_entry (op2_range, orig_bb, op2);
+ ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
+ }
+ // If we failed to calculate a range for op1, bail.
+ if (!ret)
+ return VREL_VARYING;
+
+ // op1_range will now become the LHS_RANGE for the def statement.
+ lhs_range = op1_range;
+ stmt = SSA_NAME_DEF_STMT (op1);
+ }
+ else if (op2_dep)
+ {
+ // Pick up the range of op1 as it occurs in the original block.
+ // and calcalute a range for op2.
+ op2_range.set_range_class (TREE_TYPE (op2));
+ get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
+ ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
+ // If we failed to calculate a range for op1, bail.
+ if (!ret)
+ return VREL_VARYING;
+
+ // op2_range will now become the LHS_RANGE for the def statement.
+ lhs_range = op2_range;
+ stmt = SSA_NAME_DEF_STMT (op2);
+ }
+ else
+ gcc_unreachable ();
+
+ // Bail if this ssa-name is defined outside this block.
+ if (!stmt || gimple_bb (stmt) != e->src)
+ return VREL_VARYING;
+ }
+ return VREL_VARYING;
+}
+
// Find a relation between SSA version V1 and V2 in the dominator tree
// starting with block BB
relation_kind
-dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
+dom_oracle::find_relation_dom (basic_block start_bb, unsigned v1, unsigned v2) const
{
relation_kind r;
// IF either name does not occur in a relation anywhere, there isn't one.
if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
return VREL_VARYING;
-
- for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+ edge outgoing_edge = NULL;
+ tree ssa1 = ssa_name (v1);
+ tree ssa2 = ssa_name (v2);
+ for (basic_block bb = start_bb;
+ bb;
+ bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
r = find_relation_block (bb->index, v1, v2);
+ // Now check if recomputed values on the outgoing edge might create
+ // a relation.
+ if (r == VREL_VARYING && outgoing_edge)
+ {
+ gcc_checking_assert (outgoing_edge->src == bb);
+ r = recomputed_relation (start_bb, outgoing_edge, ssa1, ssa2);
+ }
if (r != VREL_VARYING)
return r;
+
+ // If the dominator is not the only predecessor to this block, there is
+ // unlikely to be a viable relation available.
+ outgoing_edge = single_pred_p (bb) ? single_pred_edge (bb) : NULL;
}
return VREL_VARYING;
-
}
// Query if there is a relation between SSA1 and SS2 in block BB or a
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index f8053300799..598d601344f 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -251,7 +251,7 @@ protected:
relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
tree op2);
void register_transitives (basic_block, const class value_relation &);
-
+ relation_kind recomputed_relation (basic_block, edge, tree, tree) const;
};
// A path_oracle implements relations in a list. The only sense of ordering
--
2.45.0
