[Bug tree-optimization/54146] Very slow compile with attribute((flatten))

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54146

--- Comment #28 from Steven Bosscher <steven at gcc dot gnu.org> 2012-08-07 
19:58:00 UTC ---
To illustrate the rewrite_into_closed_loop_ssa problem, consider this test
case:

extern void use1 (int);
extern void use2 (int);
extern int confuse_loop (void);

void
foo (void)
{
  int i, j, k;

  for (i = 0; i < 100; i++)
    {
      for (j = 0; j < 100; j++)
        {
          k = i + j;
          if (j > 2)
            use1 (k);
          if (confuse_loop ())
            break;
        }
      use2 (k);
    }
}

The only PHI needed for loop-closed SSA is one for k before "use2(k)". 

One problem is that GCC ends up inserting two PHI nodes (one on the exit after
confuse_loop(), which is wasteful if the exit block is empty. So problem 1 is
that too many PHIs are inserted.

The second problem is that with multiple loop exits, a large part of the CFG is
walked in compute_global_livein. The CFG for the test case (compiled with
-fno-tree-ch) looks like this:

             +---<------------ 14 ------<-----+
E           /                                  \          E
N          /                                    \         X
T -> 2 -  9 --> 3 --> 4 --> 5 -> 11 ----------> 7 -> 8 -> I
R              / \         / \                 /          T
Y             /   +-> 10 -+   +-> 6 -> 13 ->--+
              \                   /
               +----<-- 12 --<---+

And the following blocks are visited (with a patch I will attach in a minute --
without the patch even more blocks are visited). Block 3 is the block
containing the def, so the CFG walk ends there.

XXX visiting block 7
XXX visiting block 13
XXX visiting block 6
XXX visiting block 5
XXX visiting block 4
XXX visiting block 10
XXX visiting block 11
;; Created LCSSA PHI: k_4 = PHI <k_14(5)>
;; Created LCSSA PHI: k_8 = PHI <k_14(6)>

;; Resulting GIMPLE function IR:

foo ()
{
  int k;
  int j;
  int i;
  int D.1727;

  <bb 2>:
  goto <bb 9>;

  <bb 12>:

  <bb 3>:
  # j_29 = PHI <j_18(12), 0(9)>
  k_14 = i_28 + j_29;
  if (j_29 > 2)
    goto <bb 4>;
  else
    goto <bb 10>;

  <bb 10>:
  goto <bb 5>;

  <bb 4>:
  use1 (k_14);

  <bb 5>:
  D.1727_17 = confuse_loop ();
  if (D.1727_17 != 0)
    goto <bb 11>;
  else
    goto <bb 6>;

  <bb 11>:
  # k_4 = PHI <k_14(5)>
  goto <bb 7>;

  <bb 6>:
  j_18 = j_29 + 1;
  if (j_18 <= 99)
    goto <bb 12>;
  else
    goto <bb 13>;

  <bb 13>:
  # k_8 = PHI <k_14(6)>

  <bb 7>:
  # k_21 = PHI <k_4(11), k_8(13)>
  use2 (k_21);
  i_20 = i_28 + 1;
  if (i_20 <= 99)
    goto <bb 14>;
  else
    goto <bb 8>;

  <bb 8>:
  return;

  <bb 14>:

  <bb 9>:
  # i_28 = PHI <i_20(14), 0(2)>
  goto <bb 3>;

}