Probing the complexity of the LLVM's optimizations

Hello guys,

I am a student from UFMG, Brazil, and I am doing a research project in
LLVM. I am running some experiments to estimate the complexity of the
LLVM’s optimizations. To do this, I run the optimizations over
hundreds of different bytecode files, and collect the time spent by
each optimization.

To get a large number of samples, I use CSmith, the random C program
generator of Utah (from John Regehr’s group). So, I can get hundreds
of C files with different sizes. I also use the benchmarks available
in the LLVM test suite.

The results of these experiments are available in my page:
http://homepages.dcc.ufmg.br/~juniocezar/llvm/. You will find plots
for all the optimizations there. They are mostly linear, but there are
a few weird ones. You are all welcome to give me suggestions or point
out mistakes in my report.

Regards

Hi Junio,

This is interesting, thanks for sharing this with us.

A few comments/questions:

- Exactly what version of LLVM did you use?

- Are you measuring the time reported by -time-passes?

- When looking at the different optimization levels, you should note that at least one of the transformation passes is more aggressive at higher optimization levels. For example, if you look in lib/Transforms/IPO/PassManagerBuilder.cpp, you'll see:
  MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));

- There are lots of passes that run during CodeGen, some of which are not cheap, and you might want to measure those as well.

- With a few exceptions, most of these passes operate on one function (or loop) at a time. If you're generating a file with many small functions, you're unlikely to see anything like the asymptotic behavior. This seems suspicious, for example: http://homepages.dcc.ufmg.br/~juniocezar/llvm/img/Analysis/Big/domtree.png (compared to http://homepages.dcc.ufmg.br/~juniocezar/llvm/img/testsuite/analysis/Big/domtree.png for the "real" test programs).

- Furthermore, you're unlikely to see non-trivial computational complexity simply by increasing the number of instructions. You'll want to increase the complexity of the control flow, the nesting depth of the loops, the depth of the instruction dependency chains, etc. Especially with CSmith, it would be interesting to see how much of that can be varied.

- It would be interesting to see the different (most significant) passes on the same plot, so that their relative expense can be compared.

-Hal