[gcc r17-2517] Recompute relations during a relation query walk.

https://gcc.gnu.org/g:3bf0224b877c2975e02330de88165a94c7ece16f

commit r17-2517-g3bf0224b877c2975e02330de88165a94c7ece16f
Author: Andrew MacLeod <[email protected]>
Date:   Thu Jul 16 11:56:17 2026 -0400

    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.

Diff:
---
 gcc/testsuite/gcc.dg/pr126212.c |  25 +++++++
 gcc/value-relation.cc           | 148 ++++++++++++++++++++++++++++++++++++++--
 gcc/value-relation.h            |   2 +-
 3 files changed, 169 insertions(+), 6 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/pr126212.c b/gcc/testsuite/gcc.dg/pr126212.c
new file mode 100644
index 000000000000..7d0da397bc2a
--- /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 3ad522ccf646..e8c7a7320de4 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 f80533007993..598d601344fa 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