llvm dev - Aug 2010 - [LLVMdev] Optimization pass questions

I have a whole slew of questions about optimization passes.  Answers to any or
all would be extremely helpful:

How important are doInitialization/doFinalization?  I can't detect any
difference if I use them or not.  Why does the function pass manager have
doInitialization/doFinalization, but the global pass manager doesn't?  If I
am applying the function passes to many functions, do I
doInitialization/run/doFinalization for each function I apply the passes to, or
do I initialize/finalize just once?

Where is it documented which passes should be part of the global versus which
should be function passes?  Some *appear* to work with either, some have errors
if you use it wrong.  I haven't found a way to tell without trying, and no
indications that I'm not using it wrong but in a way that's too subtle
to crash or catch it.

Is the best protocol to do function passes first, then global?  After that,
should you do function passes again for good measure, or is that redundant? 
Does inlining go best in function or global?  Does the strategy change if I
really only need to directly call a few functions in the module, the others
existing only in case they are needed by the dynamically-generated code that
I'm JITing?

It seems that the combinatorics of which passes to apply, and in which order
(including doing some multiple times), are pretty daunting.  Other than the
Kaleidescope tutorial (too simple) and the StandardPasses.h (too complex?) I
can't find any other examples, much less pro/con discussion or guidance. 
Does anybody have any pointers to web pages or other docs where people have
shared their experiences walking through the space of possible pass
combinations?

The application of all of this for me is to JIT dynamically-generated code, so
in contrast to a fully offline compiler, I'm fairly sensitive to achieving a
good balance of optimization of the JITed code versus time spent doing the
optimizations.  In case that changes any of your answers.

Thanks, any info would be very appreciated!

--
Larry Gritz
lg at larrygritz.com

On Aug 11, 2010, at 4:55 PM, Larry Gritz wrote:
> I have a whole slew of questions about optimization passes.  Answers to any
or all would be extremely helpful:
> 
> How important are doInitialization/doFinalization?  I can't detect any
difference if I use them or not.  Why does the function pass manager have
doInitialization/doFinalization, but the global pass manager doesn't?  If I
am applying the function passes to many functions, do I
doInitialization/run/doFinalization for each function I apply the passes to, or
do I initialize/finalize just once?
> 
> Where is it documented which passes should be part of the global versus
which should be function passes?  Some *appear* to work with either, some have
errors if you use it wrong.  I haven't found a way to tell without trying,
and no indications that I'm not using it wrong but in a way that's too
subtle to crash or catch it.
> 
Have you read this document?
http://llvm.org/docs/WritingAnLLVMPass.html#passtype

It should explain what doInit and doFinalization means and when they are
executed.. plus tons more good stuff.

-Tanya

> Is the best protocol to do function passes first, then global?  After that,
should you do function passes again for good measure, or is that redundant? 
Does inlining go best in function or global?  Does the strategy change if I
really only need to directly call a few functions in the module, the others
existing only in case they are needed by the dynamically-generated code that
I'm JITing?
> 
> It seems that the combinatorics of which passes to apply, and in which
order (including doing some multiple times), are pretty daunting.  Other than
the Kaleidescope tutorial (too simple) and the StandardPasses.h (too complex?) I
can't find any other examples, much less pro/con discussion or guidance. 
Does anybody have any pointers to web pages or other docs where people have
shared their experiences walking through the space of possible pass
combinations?
> 
> The application of all of this for me is to JIT dynamically-generated code,
so in contrast to a fully offline compiler, I'm fairly sensitive to
achieving a good balance of optimization of the JITed code versus time spent
doing the optimizations.  In case that changes any of your answers.
> 
> Thanks, any info would be very appreciated!
> 
> --
> Larry Gritz
> lg at larrygritz.com
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Aug 11, 2010, at 5:57 PM, Tanya Lattner wrote:
> Have you read this document?
> http://llvm.org/docs/WritingAnLLVMPass.html#passtype
Yes, but I didn't find it as instructive as I'd hoped.  The only two
examples of pass sets I can find are the Kaleidoscope tutorial and
StandardPasses.h (corresponding, I assume, to what llvm-gcc does).  Just looking
at the two of these, some passes are done as function passes in one, but global
passes in the other.  Is that generally ok?  I've experimented and some
passes appear to work either way, others complain if you use it wrong.  I've
found it hard to deduce, from just these examples and the docs, what the precise
rules are, let alone best practices.

> It should explain what doInit and doFinalization means and when they are
executed.. plus tons more good stuff.
Well just as an example, let's say you have a bunch of functions in a
module, and you want to apply your function passes to each of them.

* Do you need to construct a separate FPM for each function, or can you
construct it once and use it in succession for each function in the module?

* If the latter, do you doInitialization just once, then run() on each function,
then doFinalization just once?  Or do you have to init/run/final separately for
every function in the module?

I didn't find that WritingAnLLVMPass.html explicitly spelled out this kind
of detail at all, though I I'm prepared to apologize profusely if I just
missed it.

	-- lg

--
Larry Gritz
lg at larrygritz.com

Larry,

On Wed, Aug 11, 2010 at 4:55 PM, Larry Gritz <lg at larrygritz.com> wrote:
> I have a whole slew of questions about optimization passes.  Answers to any
> or all would be extremely helpful:
>
> How important are doInitialization/doFinalization?

Most of the passes do not use them.

>  I can't detect any difference if I use them or not.

Say, if you are writing a pass to operate on a function. Naturally, your
pass is derived from FunctionPass and it is designed to operate on one
function at a time. If you want to prepare the stage or collect some
information from the module (which contains all the functions) before you
modify any function using your pass then you use doInitialization hook. This
is useful because the function passs's runOnFunction only gives you access
to the function and not the module surrounding the function. Typically, if
your function pass MyFP is operating on a Module M1 with two functions F1 ad
F2 in it  then  execution sequence will be

  MyFP->doInitialization(M1);
  MyFP->runOnFunction(F1);
  MyFP->runOnFunction(F2);
  MyFP->doFinalization();


>  Why does the function pass manager have doInitialization/doFinalization,
> but the global pass manager doesn't?

The global pass already receives access to the module in runOnModule. Since
there is not anything that surrounds Module so there is not any thing to
initialize.

> If I am applying the function passes to many functions, do I
> doInitialization/run/doFinalization for each function I apply the passes
to,
> or do I initialize/finalize just once?
>
Initialize/finalize should only do things that are not specific to
individual functions you are going to operate. See above execution sequence
example.

> Where is it documented which passes should be part of the global versus
> which should be function passes?

I assume you're talking about PassManager vs FunctionPassManager here.

At the time of writing a pass it does not matter. The program construct your
pass is operating on usually determines what your pass is derived from. If
your pass operates on entire module then it is derived from ModulePass. If
your pass operates one function at a time then it is derived from
FunctionPass and so on. WritingAnLLVMPass.html explains this.

Once you have a pass, you can run your FunctionPass using either PassManager
or FunctionPassManager. However you can not run a ModulePass using
FunctionPassManager.

>  Some *appear* to work with either, some have errors if you use it wrong.
>  I haven't found a way to tell without trying, and no indications that
I'm
> not using it wrong but in a way that's too subtle to crash or catch it.
>
> Is the best protocol to do function passes first, then global?  After that,
> should you do function passes again for good measure, or is that redundant?
>  Does inlining go best in function or global?

Standard Inlining is a module pass and it can not be run using
FunctionPassManager. The docs explicitly lists limitation of a function
pass. However....

>  Does the strategy change if I really only need to directly call a few
> functions in the module, the others existing only in case they are needed
by
> the dynamically-generated code that I'm JITing?
>
> It seems that the combinatorics of which passes to apply, and in which
> order (including doing some multiple times), are pretty daunting.  Other
> than the Kaleidescope tutorial (too simple) and the StandardPasses.h (too
> complex?) I can't find any other examples, much less pro/con discussion
or
> guidance.  Does anybody have any pointers to web pages or other docs where
> people have shared their experiences walking through the space of possible
> pass combinations?
>
I am afraid, there is not any simple doc or magic that explains how to find
optimal pass sequence for the optimizer. StandardPasses sequences are result
of lot of tuning and analysis of generated code. Your best bet is start
using one of the standard pass sequence and add/remove passes to meet your
needs.

> The application of all of this for me is to JIT dynamically-generated code,
> so in contrast to a fully offline compiler, I'm fairly sensitive to
> achieving a good balance of optimization of the JITed code versus time
spent
> doing the optimizations.  In case that changes any of your answers.
>
>
At least one thing, you may not need traditional inliner which uses call
graph from the entire module. You  may want to take a look at BasicInliner.

-
Devang
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100812/68724b26/attachment.html>

Thanks, Devang, this answer a LOT of my questions.  I really appreciate the
detailed answers.

	-- lg


On Aug 12, 2010, at 4:23 PM, Devang Patel wrote:
> Larry,
> 
> On Wed, Aug 11, 2010 at 4:55 PM, Larry Gritz <lg at larrygritz.com>
wrote:
> I have a whole slew of questions about optimization passes.  Answers to any
or all would be extremely helpful:
> 
> How important are doInitialization/doFinalization?
> 
> Most of the passes do not use them.
>  
>  I can't detect any difference if I use them or not.
> 
> Say, if you are writing a pass to operate on a function. Naturally, your
pass is derived from FunctionPass and it is designed to operate on one function
at a time. If you want to prepare the stage or collect some information from the
module (which contains all the functions) before you modify any function using
your pass then you use doInitialization hook. This is useful because the
function passs's runOnFunction only gives you access to the function and not
the module surrounding the function. Typically, if your function pass MyFP is
operating on a Module M1 with two functions F1 ad F2 in it  then  execution
sequence will be
> 
>   MyFP->doInitialization(M1);
>   MyFP->runOnFunction(F1);
>   MyFP->runOnFunction(F2);
>   MyFP->doFinalization();
> 
>  
>  Why does the function pass manager have doInitialization/doFinalization,
but the global pass manager doesn't?
> 
> The global pass already receives access to the module in runOnModule. Since
there is not anything that surrounds Module so there is not any thing to
initialize.
>  
> If I am applying the function passes to many functions, do I
doInitialization/run/doFinalization for each function I apply the passes to, or
do I initialize/finalize just once?
> 
> Initialize/finalize should only do things that are not specific to
individual functions you are going to operate. See above execution sequence
example.
>  
> Where is it documented which passes should be part of the global versus
which should be function passes?
> 
> I assume you're talking about PassManager vs FunctionPassManager here. 
> 
> At the time of writing a pass it does not matter. The program construct
your pass is operating on usually determines what your pass is derived from. If
your pass operates on entire module then it is derived from ModulePass. If your
pass operates one function at a time then it is derived from FunctionPass and so
on. WritingAnLLVMPass.html explains this.
> 
> Once you have a pass, you can run your FunctionPass using either
PassManager or FunctionPassManager. However you can not run a ModulePass using
FunctionPassManager.
>  
>  Some *appear* to work with either, some have errors if you use it wrong. 
I haven't found a way to tell without trying, and no indications that
I'm not using it wrong but in a way that's too subtle to crash or catch
it.
> 
> Is the best protocol to do function passes first, then global?  After that,
should you do function passes again for good measure, or is that redundant? 
Does inlining go best in function or global?
> 
> Standard Inlining is a module pass and it can not be run using
FunctionPassManager. The docs explicitly lists limitation of a function pass.
However....
>  
>  Does the strategy change if I really only need to directly call a few
functions in the module, the others existing only in case they are needed by the
dynamically-generated code that I'm JITing?
> 
> It seems that the combinatorics of which passes to apply, and in which
order (including doing some multiple times), are pretty daunting.  Other than
the Kaleidescope tutorial (too simple) and the StandardPasses.h (too complex?) I
can't find any other examples, much less pro/con discussion or guidance. 
Does anybody have any pointers to web pages or other docs where people have
shared their experiences walking through the space of possible pass
combinations?
> 
> I am afraid, there is not any simple doc or magic that explains how to find
optimal pass sequence for the optimizer. StandardPasses sequences are result of
lot of tuning and analysis of generated code. Your best bet is start using one
of the standard pass sequence and add/remove passes to meet your needs.
>  
> The application of all of this for me is to JIT dynamically-generated code,
so in contrast to a fully offline compiler, I'm fairly sensitive to
achieving a good balance of optimization of the JITed code versus time spent
doing the optimizations.  In case that changes any of your answers.
> 
> 
> At least one thing, you may not need traditional inliner which uses call
graph from the entire module. You  may want to take a look at BasicInliner.
>  
> -
> Devang
--
Larry Gritz
lg at larrygritz.com


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100813/4a9fb74f/attachment.html>