llvm dev - Feb 2016 - Metadata and compile time performance

Dear LLVMers,

I’m investigating the response time of my JIT, and according to profiling,
optimization takes 85% of the compile time, while the rest is being split evenly
between the front-end and machine code generation. Much of the optimizer time is
spent in various alias analysis passes.

I’m happy with the generated code quality and wouldn’t like to lower the
optimization level (O2).

Would generating alias metadata from the front-end help and speed up
optimization?

If so, what kind of AA would have the best return on investment in terms of
compile time? TBAA is not applicable to my language, but I could provide C99
restrict and related semantics fairly easily.

Thanks!!

Vesa Norilo
Lecturer
Centre for Music and Technology
University of Arts Helsinki

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160219/2b9cb48d/attachment.html>

On 2/19/16 7:47 AM, Norilo Vesa-Petri via llvm-dev
wrote:
>
> Dear LLVMers,
>
> I’m investigating the response time of my JIT, and according to 
> profiling, optimization takes 85% of the compile time, while the rest 
> is being split evenly between the front-end and machine code 
> generation. Much of the optimizer time is spent in various alias 
> analysis passes.
>
One thing you might want to do is look at the pass pipeline and see if 
the alias analysis passes are being re-run multiple times.  If they are, 
then maybe the issue is getting alias analysis to run fewer times 
instead of trying to get it to run faster.

There could be two culprits for running analysis passes over and over 
again.  First, it's possible that an analysis pass (or passes) are 
invalidated over and over again by optimizations.  Changing the ordering 
of the optimizations or having key optimizations update the analysis 
information might fix that problem.

Second, unless it's been changed, using a FunctionPass from within a 
ModulePass forces the FunctionPass to be re-run from scratch whenever 
the getAnalysisUsage<FunctionPass>() method is called.  A poorly written 
ModulePass may cause a FunctionPass to be run over and over again 
needlessly.  I doubt that the in-tree optimizations make this sort of 
mistake, but it is conceivably possible.

To be clear, I don't know that this is the cause of your overhead, but 
if it were me, I'd check this first before trying to make alias analysis 
run faster.

Regards,

John Criswell
> I’m happy with the generated code quality and wouldn’t like to lower 
> the optimization level (O2).
>
> Would generating alias metadata from the front-end help and speed up 
> optimization?
>
> If so, what kind of AA would have the best return on investment in 
> terms of compile time? TBAA is not applicable to my language, but I 
> could provide C99 restrict and related semantics fairly easily.
>
> Thanks!!
>
> Vesa Norilo
> Lecturer
> Centre for Music and Technology
> University of Arts Helsinki
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160219/1f830c50/attachment.html>

----- Original Message -----
> From: "John Criswell via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "Norilo Vesa-Petri" <vesa-petri.norilo at uniarts.fi>,
> llvm-dev at lists.llvm.org
> Sent: Friday, February 19, 2016 7:54:30 AM
> Subject: Re: [llvm-dev] Metadata and compile time performance
> On 2/19/16 7:47 AM, Norilo Vesa-Petri via llvm-dev wrote:
> > Dear LLVMers,
> 
> > I’m investigating the response time of my JIT, and according to
> > profiling, optimization takes 85% of the compile time, while the
> > rest is being split evenly between the front-end and machine code
> > generation. Much of the optimizer time is spent in various alias
> > analysis passes.
> 
> One thing you might want to do is look at the pass pipeline and see
> if the alias analysis passes are being re-run multiple times. If
> they are, then maybe the issue is getting alias analysis to run
> fewer times instead of trying to get it to run faster.
Unfortunately, our AA is mostly stateless, so this is not really going to be an
issue. "Running" BasicAA, which is the most-expensive one, does not
really do anything. Every time to make an AA query it walks use/def chains to
determine an answer.

Counterintuitively, using TBAA metadata also won't really help because the
BasicAA query is always done first regardless. This is because for its primary
use case (modeling C/C++ TBAA rules), we need to catch cases of disallowed
aliasing from common type-punning idioms and still do what the user expects
(i.e. recognize the aliasing). Adding restrict (noalias) on function arguments
where you can should help (that will make the associated BasicAA logic cheaper).

Depending on what you're doing, generating fewer GEPs that BasicAA needs to
look through will also speed things up.

-Hal 
> There could be two culprits for running analysis passes over and over
> again. First, it's possible that an analysis pass (or passes) are
> invalidated over and over again by optimizations. Changing the
> ordering of the optimizations or having key optimizations update the
> analysis information might fix that problem.
> Second, unless it's been changed, using a FunctionPass from within a
> ModulePass forces the FunctionPass to be re-run from scratch
> whenever the getAnalysisUsage<FunctionPass>() method is called. A
> poorly written ModulePass may cause a FunctionPass to be run over
> and over again needlessly. I doubt that the in-tree optimizations
> make this sort of mistake, but it is conceivably possible.
> To be clear, I don't know that this is the cause of your overhead,
> but if it were me, I'd check this first before trying to make alias
> analysis run faster.
> Regards,
> John Criswell
> > I’m happy with the generated code quality and wouldn’t like to
> > lower
> > the optimization level (O2).
> 
> > Would generating alias metadata from the front-end help and speed
> > up
> > optimization?
> 
> > If so, what kind of AA would have the best return on investment in
> > terms of compile time? TBAA is not applicable to my language, but I
> > could provide C99 restrict and related semantics fairly easily.
> 
> > Thanks!!
> 
> > Vesa Norilo
> 
> > Lecturer
> 
> > Centre for Music and Technology
> 
> > University of Arts Helsinki
> 
> > _______________________________________________
> 
> > LLVM Developers mailing list
> 
> > llvm-dev at lists.llvm.org
> 
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> --
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160219/befe56fb/attachment.html>

On 02/19/2016 04:47 AM, Norilo Vesa-Petri via llvm-dev
wrote:
>
> Dear LLVMers,
>
> I’m investigating the response time of my JIT, and according to 
> profiling, optimization takes 85% of the compile time, while the rest 
> is being split evenly between the front-end and machine code 
> generation. Much of the optimizer time is spent in various alias 
> analysis passes.
>
Could you share more detailed profiling information?  It's possible 
you're tripping across a compile time bug or that seeing what sections 
are hot would given insights into how to tweak your code to avoid the 
problem.
>
> I’m happy with the generated code quality and wouldn’t like to lower 
> the optimization level (O2).
>
> Would generating alias metadata from the front-end help and speed up 
> optimization?
>
> If so, what kind of AA would have the best return on investment in 
> terms of compile time? TBAA is not applicable to my language, but I 
> could provide C99 restrict and related semantics fairly easily.
>
In general, if you can give "easier" answers, that's always a good
thing.  If you're using LLVM for inlining, you may find that
"noalias"
attributes are quite useful for controlling compile time (i.e. enable 
optimizations of callee before inlining).  Without knowing more about 
your source language and where you're currently spending time, I can't 
really help more than that.
>
> Thanks!!
>
> Vesa Norilo
> Lecturer
> Centre for Music and Technology
> University of Arts Helsinki
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160222/53f42050/attachment.html>