[LLVMdev] Probing the complexity of the LLVM's optimizations

[Hal Finkel]

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

----- Original Message -----
> From: "Junio Cezar" <juniocezar.dcc at gmail.com>
> To: llvmdev at cs.uiuc.edu
> Sent: Sunday, October 12, 2014 10:43:21 AM
> Subject: [LLVMdev] 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
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory