[Bug tree-optimization/106280] New: dom_oracle::register_transitives is expensive for deep dominator trees

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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.