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

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

[rguenth at gcc dot 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.

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

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106280

--- Comment #1 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 53300
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53300&action=edit
proposed patch

See if this helps.  

All of the lookup routines check to see first is there is an existing relation
for an SSA_NAME before deciding what to do.  I forgot to do that with the
transitive code.

So, this patch does 2 things. 
1) If a relation is being registered which already exist, the set routine now
returns NULL for the record as there will be no new work to do
2) IF this is a new relation, before calling register_transitives checks if
either operand was in a relation before (its just a quick bitmap check). If
neither was, there is no possibility of a transitive relation, so no need to
look.

This eliminates a lot of unnecessary work, and based on the pass times spits
out at the end, appears to save a lot of time in the various VRP passes (over
50% time reduction) in your test case.  It also makes some marginal
improvements in GCC source files compilation.

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

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106280

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:5e47c9333df6df1aa9da861f07e68f985d7d28fb

commit r13-1737-g5e47c9333df6df1aa9da861f07e68f985d7d28fb
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Jul 14 12:35:55 2022 -0400

    Check if transitives need to be registered.

    Whenever a relation is added, register_transitive is always called.
    If neither operand was in a relation before, or this is not a new
    relation, then there is no need to register transitives.

            PR tree-optimization/106280
            * value-relation.cc (dom_oracle::register_relation): Register
            transitives only when it is possible for there to be one.
            (dom_oracle::set_one_relation): Return NULL if this is an
            existing relation.