llvm dev - Oct 2014 - [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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141012/95e71f47/attachment.html>

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