On 9/26/24 03:07, Richard Biener wrote:
On Wed, 25 Sep 2024, Andrew MacLeod wrote:
I added a note to the PR before I saw this... we can just disable transitives
when the graph gets too big... I don't think they are worth the expense when
things get large. I've attached that patch if you want to consider it. It
probably should have been included when I added the switchover to fast VRP,
but I wasn't thinking about ranger still being used by the threader.
That said, I'm also OK with your patch if you'd rather to go with it.
To comment here and not in the PR aboud simply disabling feature X when
"the CFG is too large" (or other metric) - I think we should try to be
more nuanced and apply limiting so there isn't a hard border on some
size metric where before GCC get's slower with increasing size and
after we're fast again but lousy to optimize even "cheap" cases.
IM not sure Id categorize it as "lousy" if we miss transitives in a
giant CFG, but sure, I get your point.
That said, my main issue right now is that DOM at -O1 is comparatively
very expensive on those testcases - if you look at a profile 98% of
it's time is spent in ranger code. Fortunately we do have
-fexpensive-optimizations, so we maybe want to use that to default
transitives but I'm also thinking whether it's possible to restrict
DOMs ranger processing to global ranges? DOM does enable_ranger ()
and not just it's range-query so I'm not sure I can easily subsitute
global range query?
Aldy added ranger to DOM as a stopgap on the path of removing EVRP, and
then the ultimate realization of this was to removing DOM itself. There
is very little DOM is doing that isn't taken care of with rangers
infrastructure.. I think the floating point support and some minor
additions to prange were all that stood in the way. Whether that path
will be pursued going forward IM not sure.
It looks like DOM is using GORI exports in
dom_opt_dom_walker::set_global_ranges_from_unreachable_edges () , but
all other uses of ranger appear to use the normal range_query API, so
thats the only ranger specific thing being used.
GORI has already been extracted from ranger and is a stand alone unit,
so instead of gimple-ranger *m_ranger = enable_ranger(), you could use
the global_range_query and a create a gori_ssa unit for it during DOM..
ie something like
range_query *m_ranger = get_global_range_query ();
m_ranger->create_gori ();
then there will be a normnal set of exports calculated as required...
And instead of disable_ranger (), call
m_ranger->destroy_gori ();
All in theory anyway.
Anyway, I'm re-testing the following revised version and will install it.
Thanks,
Richard.
From 48fb0382d23ad6c58ca7573965843509828a07e8 Mon Sep 17 00:00:00 2001
From: Richard Biener <rguent...@suse.de>
Date: Wed, 25 Sep 2024 10:38:12 +0200
Subject: [PATCH] tree-optimization/114855 - speed up
dom_oracle::register_transitives
To: gcc-patches@gcc.gnu.org
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.
---
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 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..d8a2ed920a8 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;
}
}
}
