https://gcc.gnu.org/g:15d3b2dab9182eff036a604169b5e6f4ab3b2a40
commit r15-2223-g15d3b2dab9182eff036a604169b5e6f4ab3b2a40
Author: Richard Biener <rguent...@suse.de>
Date: Tue Jul 23 10:29:58 2024 +0200
tree-optimization/116002 - PTA solving slow with degenerate graph
When the constraint graph consists of N nodes with only complex
constraints and no copy edges we have to be lucky to arrive at
a constraint solving order that requires the optimal number of
iterations. What happens in the testcase is that we bottle-neck
on computing the visitation order but propagate changes only
very slowly. Luckily the testcase complex constraints are
all copy-with-offset and those do provide a way to order
visitation. The following adds this which reduces the iteration
count to one.
PR tree-optimization/116002
* tree-ssa-structalias.cc (topo_visit): Also consider
SCALAR = SCALAR complex constraints as edges.
Diff:
---
gcc/tree-ssa-structalias.cc | 12 ++++++++++++
1 file changed, 12 insertions(+)
diff --git a/gcc/tree-ssa-structalias.cc b/gcc/tree-ssa-structalias.cc
index 330e64e65da1..65f9132a94fd 100644
--- a/gcc/tree-ssa-structalias.cc
+++ b/gcc/tree-ssa-structalias.cc
@@ -1908,6 +1908,18 @@ topo_visit (constraint_graph_t graph, vec<unsigned>
&topo_order,
topo_visit (graph, topo_order, visited, k);
}
+ /* Also consider copy with offset complex constraints as implicit edges. */
+ for (auto c : graph->complex[n])
+ {
+ /* Constraints are ordered so that SCALAR = SCALAR appear first. */
+ if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
+ break;
+ gcc_checking_assert (c->rhs.var == n);
+ unsigned k = find (c->lhs.var);
+ if (!bitmap_bit_p (visited, k))
+ topo_visit (graph, topo_order, visited, k);
+ }
+
topo_order.quick_push (n);
}
