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 07E1E385780B; Fri, 30 Oct 2020 12:35:40 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 07E1E385780B
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2
 compile (>>O(n^2))
Date: Fri, 30 Oct 2020 12:35:39 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 9.3.1
X-Bugzilla-Keywords: compile-time-hog
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
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: 
Message-ID: <bug-97623-4-lnSyb1jwEP@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-97623-4@http.gcc.gnu.org/bugzilla/>
References: <bug-97623-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: Fri, 30 Oct 2020 12:35:40 -0000

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, so we have PRE and hoist insertion exposing new opportunities to each
other, making things tickle up the CFG.  Then, the way hoist insertion works
it would be better suited to a bottom-up walk since hoist inserts may
expose new hoist candidates - but a bottom-up walk makes updating AVAIL_OUT
sets harder.

The following pattern requires N hoist insert iterations for example:

void baz();
int tem;
void foo (int a, int b, int c, int d, int e, int x, int y)
{
  if (a)
    {
      if (b)
        {
          if (c)
            {
              tem =3D x + y;
            }
          else
            {
              if (d) baz ();
              tem =3D x + y;
            }
        }
      else
        {
          if (d) baz ();
          tem =3D x + y;
        }
    }
  else
    {
      if (d) baz ();
      tem =3D x + y;
    }
}

now, due to PRE insertion and hoist insertion going in different directions
the cascading cannot be avoided in general.  But I think we can improve
things by first doing hoist insertion backwards (no need to propagate
NEW sets there) and then doing PRE insertion forward, propagating NEW
sets on the fly.  That makes the above testcase take 2 iterations
and your original testcase "only" 94.  As said, the back-to-back cannot
really be avoided but the wrong order hoist insertion can be fixed.=