dom_oracle::register_transitives contains an unbound dominator walk
which for the testcase in PR114855 dominates the profile. I've also
noticed odd behavior in the case when set_one_relation returns NULL,
we'd then completely abort processing other relations. The following
fixes the latter by continuing searching and 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 wondered whether instead of having a per-BB bitmap of names
we have a relation for in that BB having a bitmap per SSA name of
which BBs have a relation for it would be a way to avoid all those
walks.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
OK for trunk?
Thanks,
Richard.
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):
Do not stop processing relations when a registration attempt
did not register a new relation. Assing an overall work
budget, bounding the dominator walk and the number of
relations processed.
---
gcc/doc/invoke.texi | 3 +++
gcc/params.opt | 4 ++++
gcc/value-relation.cc | 47 ++++++++++++++++++++++++++-----------------
3 files changed, 35 insertions(+), 19 deletions(-)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index bdbbea53666..bd1208a62ee 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 949b4754498..a08e4c1042d 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 d6ad2dd984f..b01e2953188 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1204,7 +1204,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 +1253,30 @@ 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))
- {
- fprintf (dump_file, " Registering transitive relation ");
- nr.dump (dump_file);
- fputc ('\n', dump_file);
- }
+ // 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)
+ && set_one_relation (root_bb, nr.kind (),
+ nr.op1 (), nr.op2 ()))
+ 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;
}
}
}
--
2.43.0
