[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2007-11-01 15:26 -------
That is, the following testcase:

int f(void);
void acceptloop_th(int *t, int options) {
    if (f()) options |= 0x1 << 0;
    if (f()) options |= 0x1 << 1;
    if (f()) options |= 0x1 << 2;
    if (f()) options |= 0x1 << 3;
    if (f()) options |= 0x1 << 4;
    if (f()) options |= 0x1 << 5;
    if (f()) options |= 0x1 << 6;
    if (f()) options |= 0x1 << 7;
    if (f()) options |= 0x1 << 8;
    if (f()) options |= 0x1 << 9;
    if (f()) options |= 0x1 << 10;
    if (f()) options |= 0x1 << 11;
    if (f()) options |= 0x1 << 12;
    if (f()) options |= 0x1 << 13;
    if (f()) options |= 0x1 << 14;
    if (f()) options |= 0x1 << 15;
    if (f()) options |= 0x1 << 16;
    if (f()) options |= 0x1 << 17;
    if (f()) options |= 0x1 << 18;
    if (f()) options |= 0x1 << 19;
    if (f()) options |= 0x1 << 20;
    if (f()) options |= 0x1 << 21;
    if (f()) options |= 0x1 << 22;
    if (f()) options |= 0x1 << 23;
    if (f()) options |= 0x1 << 24;
    if (f()) options |= 0x1 << 25;
    if (f()) options |= 0x1 << 26;
    if (f()) *t = options;
}

it's interesting that this one is not different from the zero-initialized
options case just because PHIOPT which runs before PRE changes

<bb 2>:
  D.1179_5 = f ();
  if (D.1179_5 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:

<bb 4>:
  # options_1 = PHI <0(2), 1(3)>

to

<bb 2>:
  D.1179_5 = f ();
  options_1 = D.1179_5 != 0;

which then causes PHI translation to not be able to figure out the constants
(but create value expressions).  With PHIOPT disabled we even perform PRE
on this testcase ;)  So, take the following modified testcase as well:

int f(void);
void acceptloop_th(int *t) {
    int options = 0;
    if (f()) options |= 0x1 << 1;
    if (f()) options |= 0x1 << 2;
    if (f()) options |= 0x1 << 3;
    if (f()) options |= 0x1 << 4;
    if (f()) options |= 0x1 << 5;
    if (f()) options |= 0x1 << 6;
    if (f()) options |= 0x1 << 7;
    if (f()) options |= 0x1 << 8;
    if (f()) options |= 0x1 << 9;
    if (f()) options |= 0x1 << 10;
    if (f()) options |= 0x1 << 11;
    if (f()) options |= 0x1 << 12;
    if (f()) options |= 0x1 << 13;
    if (f()) options |= 0x1 << 14;
    if (f()) options |= 0x1 << 15;
    if (f()) options |= 0x1 << 16;
    if (f()) options |= 0x1 << 17;
    if (f()) options |= 0x1 << 18;
    if (f()) options |= 0x1 << 19;
    if (f()) options |= 0x1 << 20;
    if (f()) options |= 0x1 << 21;
    if (f()) options |= 0x1 << 22;
    if (f()) options |= 0x1 << 23;
    if (f()) options |= 0x1 << 24;
    if (f()) options |= 0x1 << 25;
    if (f()) options |= 0x1 << 26;
    if (f()) *t = options;
}

which causes an exponential number of PHI nodes to be inserted.  Like for
example (shortened testcase):

<bb 4>:
  # prephitmp.9_30 = PHI <16(13), 18(3)>
  # prephitmp.9_29 = PHI <24(13), 26(3)>
  # prephitmp.9_28 = PHI <8(13), 10(3)>
  # prephitmp.9_27 = PHI <20(13), 22(3)>
  # prephitmp.9_26 = PHI <28(13), 30(3)>
  # prephitmp.9_25 = PHI <12(13), 14(3)>
  # prephitmp.9_24 = PHI <4(13), 6(3)>
  # options_1 = PHI <0(13), 2(3)>
  # SMT.4_18 = VDEF <SMT.4_17>
  D.1180_8 = f ();
  if (D.1180_8 != 0)
    goto <bb 5>;
  else
    goto <bb 14>;

where all the computed constants materialize! :)

How interesting.


-- 


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