quadratic compile time in SUnit::ComputeHeight and SUnit::setHeightDirty

[kcc]

Bugzilla Link	11302
Version	trunk
OS	Linux
CC	@asl,@atrick,@d0k,@lattner,@efriedma-quic,@MattPD

Extended Description

The attached test cases have N calls of the following kind:
bar(16981, 6504, "11844");

compiling a test with 2*N such calls takes 4x more time than compiling N calls.
I am using r143407

% for n in 8 16 32 64; do echo n=${n}000; time ./my_clang++ -c -O2 manycalls$n.cc ; done
n=8000
TIME: real: 2.432; user: 2.300; system: 0.060
n=16000
TIME: real: 11.824; user: 11.570; system: 0.120
n=32000
TIME: real: 59.008; user: 58.650; system: 0.230
n=64000
TIME: real: 151.948; user: 150.950; system: 0.670

Profile looks like this:
45.11% llvm::SUnit::ComputeHeight()
34.51% llvm::SUnit::setHeightDirty()
1.52% llvm::MachineInstr::addRegisterDead(unsigned int, llvm::TargetRegisterInfo const*, bool)
0.75% llvm::SelectionDAG::AssignTopologicalOrder()

gcc is much faster and does not look quadratic

% for n in 8 16 32 64; do echo n=${n}000; time g++ -c -O2 manycalls$n.cc ; done
n=8000
TIME: real: 1.682; user: 1.620; system: 0.060
n=16000
TIME: real: 3.618; user: 3.550; system: 0.060
n=32000
TIME: real: 7.685; user: 7.410; system: 0.250
n=64000
TIME: real: 16.265; user: 15.810; system: 0.380

[llvmbot]

I think you forgot to attach the testcase.

[kcc]

tar file with a few c files
indeed, sorry

[d0k]

*** Bug llvm/llvm-bugzilla-archive#14651 has been marked as a duplicate of this bug. ***

[lattner]

Andy, have you looked at this at all? This is really bad.

[atrick]

In general, the old instruction schedulers (SDSched & PostRA sched) were not designed to handle very long chains of calls. I have fixed some of the cases where behavior was cubic or worse in # of calls, but the overall strategy is to replace the SDSched pass with simple DAG linearization that doesn't build a scheduling DAG at all (or compute heights).

That said, since I'm not yet working on DAG linearization, if I can find some time I'll reinvestigate this and try to come up with a temporary solution.

[lattner]

Thanks Andy. Given that these are "weird" cases, it would be fine to have some sort of arbitrary limit on height and fall back to a simpler heuristic if it is hit.

[llvmbot]

[From duplicate bug: http://llvm.org/bugs/show_bug.cgi?id=14651]

Still exists in a newer version:

$ time /usr/local/gcc/bin/gcc <pan.c flags> -O2 -o files pan.c
real 0m32.881s
user 0m32.114s
sys 0m0.759s

$ cc --version
Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
Target: x86_64-apple-darwin12.4.1
Thread model: posix

$ time cc <pan.c flags> -O2 -o files pan.c
real 4m21.463s
user 4m9.268s
sys 0m12.081s

[d0k]

[From duplicate bug: http://llvm.org/bugs/show_bug.cgi?id=14651]

Still exists in a newer version:

Can you try clang trunk? It has a new scheduler that doesn't use the slow algorithm responsible for the slowness described in this bug.

[llvmbot]

Issue is apparently resolved with trunk build. Performed:

$ svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm; cd llvm
$ ./configure --prefix=/usr/local/llvm --enable-optimized
$ make; make install

Then for my code compilation:

Using Apple clang...

$ time clang -emit-llvm <pan.c flags> -O2 -c -o pan.bc pan.c

real 0m14.576s
user 0m14.244s
sys 0m0.280s

$ /usr/local/llvm/bin/llc --version
LLVM (http://llvm.org/):
LLVM version 3.4svn
Optimized build with assertions.
Built Oct 24 2013 (12:22:08).
Default target: x86_64-apple-darwin12.4.1
Host CPU: core-avx-i

Registered Targets:

$ time /usr/local/llvm/bin/llc pan.bc -o pan.s

real 0m40.823s
user 0m40.013s
sys 0m0.810s

assembling pan.c to executable adds 1sec.

Total time for LLVM is ~55 seconds. For GCC:

$ time /usr/local/gcc/bin/gcc <pan.c flags> -O2 -o foo pan.c

real 0m33.097s
user 0m32.205s
sys 0m0.707s

no longer a factor of 4 or more.

[d0k]

mentioned in issue llvm/llvm-bugzilla-archive#14651

[arsenm]

Comments say fixed