[Bug tree-optimization/32540] New: Exponential time behavior in PRE

["falk at debian dot org" <gcc-bugzilla at gcc dot gnu dot org>]

int f(void);
void acceptloop_th(int *t) {
    int options = 0;
    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;
    *t = options;
}

takes many minutes to compile with 4.3. No problem with 4.2. Timing report
shows PRE, and -fno-tree-pre makes it go really fast.

Some timings, where the first number is the number of "if"-lines:
10 gcc -c -O3 mini2.c -DN=$n  0.17s user 0.01s system 97% cpu 0.184 total
11 gcc -c -O3 mini2.c -DN=$n  0.20s user 0.02s system 97% cpu 0.221 total
12 gcc -c -O3 mini2.c -DN=$n  0.28s user 0.01s system 95% cpu 0.306 total
13 gcc -c -O3 mini2.c -DN=$n  0.42s user 0.03s system 97% cpu 0.463 total
14 gcc -c -O3 mini2.c -DN=$n  0.76s user 0.02s system 97% cpu 0.805 total
15 gcc -c -O3 mini2.c -DN=$n  1.52s user 0.03s system 97% cpu 1.604 total
16 gcc -c -O3 mini2.c -DN=$n  3.24s user 0.07s system 97% cpu 3.396 total
17 gcc -c -O3 mini2.c -DN=$n  7.00s user 0.12s system 97% cpu 7.314 total
18 gcc -c -O3 mini2.c -DN=$n  15.01s user 0.21s system 96% cpu 15.748 total
19 gcc -c -O3 mini2.c -DN=$n  33.21s user 0.49s system 94% cpu 35.600 total
20 gcc -c -O3 mini2.c -DN=$n  76.29s user 0.87s system 96% cpu 1:19.94 total

I'll also attach the original source this test case was extracted from.


-- 
           Summary: Exponential time behavior in PRE
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: falk at debian dot org


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