From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
 id DF6413858418; Wed, 13 Jul 2022 08:29:42 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DF6413858418
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/106280] New: dom_oracle::register_transitives
 is expensive for deep dominator trees
Date: Wed, 13 Jul 2022 08:29:42 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 13.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-106280-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-BeenThere: gcc-bugs@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-bugs mailing list <gcc-bugs.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Wed, 13 Jul 2022 08:29:43 -0000

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

            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 =3D 0;
#define A \
  for (int i =3D 0; i < 1024; ++i) if (flag) res ^=3D 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 =3D root_bb; bb; bb =3D 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 exam=
ple
--param max-hoist-depth with similar limiting, but for children).

There might be similar walks elsewhere in the relation/ranger code.=