Features Download
From: Hal Finkel <hfinkel <at> anl.gov>
Subject: Re: Probing the complexity of the LLVM's optimizations
Newsgroups: gmane.comp.compilers.llvm.devel
Date: Sunday 12th October 2014 21:18:16 UTC (over 2 years ago)
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.


----- Original Message -----
> From: "Junio Cezar" <[email protected]>
> To: [email protected]
> 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
> [email protected]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
CD: 3ms