https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106280
Bug ID: 106280
Summary: dom_oracle::register_transitives is expensive for deep
dominator trees
Product: gcc
Version: 13.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: rguenth at gcc dot gnu.org
Target Milestone: ---
For testcases like
extern int foo (int);
int bar(int flag)
{
int res = 0;
#define A \
for (int i = 0; i < 1024; ++i) if (flag) res ^= foo(i);
#define B A A A A A A A A A A
#define C B B B B B B B B B B
#define D C C C C C C C C C C
D D D D
return res;
}
the function shows high up in the profiles even at -O1 (via the DOM pass
I guess which also has its own share of issues with this).
The
for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
...
}
walk visits a lot of blocks and I suppose it does that for each block
in the dominator chain when that ends in something useful. Another
testcase might be of the CFG structure
if (a)
if (b)
if (c)
if (d)
...
where for each if () we'd walk up the dominator tree.
I suggest to limit the walking depth to a constant depth (there is for example
--param max-hoist-depth with similar limiting, but for children).
There might be similar walks elsewhere in the relation/ranger code.
