https://gcc.gnu.org/g:942bbb2357656019caa3f8ebd2d23b09222f039a
commit r15-3896-g942bbb2357656019caa3f8ebd2d23b09222f039a
Author: Richard Biener <rguent...@suse.de>
Date: Wed Sep 25 10:38:12 2024 +0200
tree-optimization/114855 - speed up dom_oracle::register_transitives
dom_oracle::register_transitives contains an unbound dominator walk
which for the testcase in PR114855 dominates the profile. The following
fixes the unbound work done by assigning a constant work budget to the
loop, bounding the number of dominators visited but also the number of
relations processed. This gets both dom_oracle::register_transitives and
get_immediate_dominator off the profile.
I'll note that we're still doing an unbound dominator walk via
equiv_set in find_equiv_dom at the start of the function and when
we register a relation that also looks up the same way. At least
for the testcase at hand this isn't an issue.
I've also amended the guard to register_transitives with the
per-basic-block limit for the number of relations registered not
being exhausted.
PR tree-optimization/114855
* params.opt (--param transitive-relations-work-bound): New.
* doc/invoke.texi (--param transitive-relations-work-bound):
Document.
* value-relation.cc (dom_oracle::register_transitives):
Assing an overall work budget, bounding the dominator walk and
the number of relations processed.
(dom_oracle::record): Only register_transitives when the
number of already registered relations does not yet exceed
the per-BB limit.
Diff:
---
gcc/doc/invoke.texi | 3 +++
gcc/params.opt | 4 ++++
gcc/value-relation.cc | 55 ++++++++++++++++++++++++++++++++++-----------------
3 files changed, 44 insertions(+), 18 deletions(-)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index bdbbea53666e..bd1208a62ee1 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -17144,6 +17144,9 @@ in the outgoing range calculator.
@item relation-block-limit
Maximum number of relations the oracle will register in a basic block.
+@item transitive-relations-work-bound
+Work bound when discovering transitive relations from existing relations.
+
@item min-pagesize
Minimum page size for warning purposes.
diff --git a/gcc/params.opt b/gcc/params.opt
index 949b47544980..a08e4c1042da 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -924,6 +924,10 @@ outgoing range calculator.
Common Joined UInteger Var(param_relation_block_limit) Init(200)
IntegerRange(0, 9999) Param Optimization
Maximum number of relations the oracle will register in a basic block.
+-param=transitive-relations-work-bound=
+Common Joined UInteger Var(param_transitive_relations_work_bound) Init(256)
IntegerRange(0, 9999) Param Optimization
+Work bound when discovering transitive relations from existing relations.
+
-param=rpo-vn-max-loop-depth=
Common Joined UInteger Var(param_rpo_vn_max_loop_depth) Init(7)
IntegerRange(2, 65536) Param Optimization
Maximum depth of a loop nest to fully value-number optimistically.
diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index d6ad2dd984f6..d8a2ed920a82 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1093,7 +1093,9 @@ dom_oracle::record (basic_block bb, relation_kind k, tree
op1, tree op2)
bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
|| bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
relation_chain *ptr = set_one_relation (bb, k, op1, op2);
- if (ptr && check)
+ if (ptr && check
+ && (m_relations[bb->index].m_num_relations
+ < param_relation_block_limit))
register_transitives (bb, *ptr);
}
}
@@ -1204,7 +1206,13 @@ dom_oracle::register_transitives (basic_block root_bb,
const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
- for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+ const unsigned work_budget = param_transitive_relations_work_bound;
+ unsigned avail_budget = work_budget;
+ for (bb = root_bb; bb;
+ /* Advancing to the next immediate dominator eats from the budget,
+ if none is left after that there's no point to continue. */
+ bb = (--avail_budget > 0
+ ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr))
{
int bbi = bb->index;
if (bbi >= (int)m_relations.length())
@@ -1247,27 +1255,38 @@ dom_oracle::register_transitives (basic_block root_bb,
// Ignore if both NULL (not relevant relation) or the same,
if (r1 == r2)
- continue;
+ ;
- // Any operand not an equivalence, just take the real operand.
- if (!r1)
- r1 = relation.op1 ();
- if (!r2)
- r2 = relation.op2 ();
-
- value_relation nr (relation.kind (), r1, r2);
- if (nr.apply_transitive (*ptr))
+ else
{
- if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()))
- return;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ // Any operand not an equivalence, just take the real operand.
+ if (!r1)
+ r1 = relation.op1 ();
+ if (!r2)
+ r2 = relation.op2 ();
+
+ value_relation nr (relation.kind (), r1, r2);
+ if (nr.apply_transitive (*ptr))
{
- fprintf (dump_file, " Registering transitive relation ");
- nr.dump (dump_file);
- fputc ('\n', dump_file);
+ // If the new relation is already present we know any
+ // further processing is already reflected above it.
+ // When we ran into the limit of relations on root_bb
+ // we can give up as well.
+ if (!set_one_relation (root_bb, nr.kind (),
+ nr.op1 (), nr.op2 ()))
+ return;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ " Registering transitive relation ");
+ nr.dump (dump_file);
+ fputc ('\n', dump_file);
+ }
}
}
-
+ /* Processed one relation, abort if we've eaten up our budget. */
+ if (--avail_budget == 0)
+ return;
}
}
}
