[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org via Gcc-bugs]

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

--- 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 = x + y;
            }
          else
            {
              if (d) baz ();
              tem = x + y;
            }
        }
      else
        {
          if (d) baz ();
          tem = x + y;
        }
    }
  else
    {
      if (d) baz ();
      tem = 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.