llvm dev - Jun 2014 - [LLVMdev] Passes calling

On Jun 12, 2014, at 9:41 AM, Chandler Carruth <chandlerc at google.com>
wrote:
> 
> On Thu, Jun 12, 2014 at 5:23 PM, John Criswell <criswell at
illinois.edu> wrote:
> On 6/12/14, 11:03 AM, Chandler Carruth wrote:
>> 
>> On Thu, Jun 12, 2014 at 4:45 PM, Hanbing Li <hanbing.li at
inria.fr> wrote:
>> Hi,
>> 
>> I know when a pass needs other passes, it will use something like this:
"AU.addRequired<LoopInfo>();". But this is usually used for the
analysis passes.
>> When a pass needs another transform pass, can it call it automatically?
>> For example:
>> Some loop optimizations may need loop-simplify, I need add
-loop-simplify before calling these passes manually, or they can call the pass
-loop-simplify automatically?
>> 
>> Currently, the pass manager allows you (somewhat) to use the
addRequired mechanism even with analyses. However, I strongly          
encourage you to not leverage it as it will eventually go away.
> 
> Just out of curiosity, why is this feature going away?
> 
> Because it makes understanding the actual pass sequence horribly complex.
> 
> With analyses, things are simple. Whatever order you run the analyses in
doesn't matter because they don't mutate anything. Each analysis can
depend on other analyses and you either have a cycle (fast to detect and error
on) or you have a DAG and there is a natural walk that produces the set of
desired analyses.
> 
> Now consider when these passes are *transformations*. Now, the relative
order in which you run them can dramatically change the results in unpredictable
ways. There is no way for multiple "required" transformation passes to
be ordered cleanly without a tremendous amount of machinery. All this is what
led to LoopSimplify being run 4x as many times as was necessary for a long time.
=/
> 
> Instead, everyone I've discussed this with (there have bene several
email threads about this) prefers that there is a single place (the builder)
which spells out the exact sequence of transforms applied.
Yes. Thank you!

As for the Analysis passes, why do they need to be “passes”? I don’t think it
should be required for a PassManager to schedule them. The static dependence
between Analysis->Pass is often not what you want. A pass should be able to
conditionally ask for an Analysis only if and when it’s needed. As a compiler
matures, these conceptually stand-alone Analysis end up becoming utilities that
can be invoked on-the-fly anyway. Furthermore, Analysis results can be built up
incrementally as needed, and only valid within some scope.

An Analysis “result” just needs to be registered with the PassManager for reuse.
The hard part of the problem is managing invalidation of the Analysis. I think
it’s a bit crazy for example that when a pass currently invalidates an Analysis,
the analysis remains valid until the pass completes and control returns to the
PassManager. It would be nice to have a better framework for Analysis
invalidation some day.

To be clear, there’s nothing wrong with having an AnalysisPass that can be
explicitly scheduled. That’s useful for testing passes that only use an analysis
“if available”. However, an Analysis should not need to be a pass in order to
register its result with the PassManager.

-Andy

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

On Fri, Jun 13, 2014 at 3:11 AM, Andrew Trick <atrick at apple.com> wrote:
> As for the Analysis passes, why do they need to be “passes”? I don’t think
> it should be required for a PassManager to schedule them. The static
> dependence between Analysis->Pass is often not what you want. A pass
should
> be able to conditionally ask for an Analysis only if and when it’s needed.
> As a compiler matures, these conceptually stand-alone Analysis end up
> becoming utilities that can be invoked on-the-fly anyway. Furthermore,
> Analysis results can be built up incrementally as needed, and only valid
> within some scope.
>
> An Analysis “result” just needs to be registered with the PassManager for
> reuse. The hard part of the problem is managing invalidation of the
> Analysis. I think it’s a bit crazy for example that when a pass currently
> invalidates an Analysis, the analysis remains valid until the pass
> completes and control returns to the PassManager. It would be nice to have
> a better framework for Analysis invalidation some day.
>
> To be clear, there’s nothing wrong with having an AnalysisPass that can be
> explicitly scheduled. That’s useful for testing passes that only use an
> analysis “if available”. However, an Analysis should not need to be a pass
> in order to register its result with the PassManager.
>
So, the design actually makes precisely the distinction you're looking for.
Analyses are different beasts from transformations at a reasonably firm
level.

That said, they still are "passes" in some very vague sense -- they
still
benefit (sometimes) from having a phase where the run over the given unit
of IR to build up the datastructure / information that they intend to vend.

The current design has two different but similar concepts: transformation
passes and analysis passes. You can see the difference in the interface: a
transformation pass returns the set of invalidated analyses, an analysis
pass returns the results of that analysis which should be cached, queried,
and (eventually) invalidated by the pass manager infrastructure.

And yes, the invalidation is already *much* more precise and I think we can
make it even better. I still need to document some of this, but want to
hold off on doing tons of documentation of guarantees and invariants until
I have more things converted over (but not enabled of course) so that I'm
more confident that the invariants promised can be upheld. =]

-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140613/23f2a7e6/attachment.html>

On Jun 13, 2014, at 2:41 AM, Chandler Carruth <chandlerc at google.com>
wrote:
> 
> On Fri, Jun 13, 2014 at 3:11 AM, Andrew Trick <atrick at apple.com>
wrote:
> As for the Analysis passes, why do they need to be “passes”? I don’t think
it should be required for a PassManager to schedule them. The static dependence
between Analysis->Pass is often not what you want. A pass should be able to
conditionally ask for an Analysis only if and when it’s needed. As a compiler
matures, these conceptually stand-alone Analysis end up becoming utilities that
can be invoked on-the-fly anyway. Furthermore, Analysis results can be built up
incrementally as needed, and only valid within some scope.
> 
> An Analysis “result” just needs to be registered with the PassManager for
reuse. The hard part of the problem is managing invalidation of the Analysis. I
think it’s a bit crazy for example that when a pass currently invalidates an
Analysis, the analysis remains valid until the pass completes and control
returns to the PassManager. It would be nice to have a better framework for
Analysis invalidation some day.
> 
> To be clear, there’s nothing wrong with having an AnalysisPass that can be
explicitly scheduled. That’s useful for testing passes that only use an analysis
“if available”. However, an Analysis should not need to be a pass in order to
register its result with the PassManager.
> 
> So, the design actually makes precisely the distinction you're looking
for. Analyses are different beasts from transformations at a reasonably firm
level.
> 
> That said, they still are "passes" in some very vague sense --
they still benefit (sometimes) from having a phase where the run over the given
unit of IR to build up the datastructure / information that they intend to vend.
> 
> The current design has two different but similar concepts: transformation
passes and analysis passes. You can see the difference in the interface: a
transformation pass returns the set of invalidated analyses, an analysis pass
returns the results of that analysis which should be cached, queried, and
(eventually) invalidated by the pass manager infrastructure.
> 
> And yes, the invalidation is already *much* more precise and I think we can
make it even better. I still need to document some of this, but want to hold off
on doing tons of documentation of guarantees and invariants until I have more
things converted over (but not enabled of course) so that I'm more confident
that the invariants promised can be upheld. =]
Sure, I’m just gently floating some ideas without spending much time
understanding how the new design works.

The part that seems limiting to me is that a transform has to return a set of
invalidated analysis. I supposed that set by default contains all the cached
analyses and the transform selectively prunes what it preserves?

Here is a simple example of my ideal model—just a rough idea:

1. DomTree and LoopInfo analyses run. They register with the PassManager as CFG
dependents.
2. Transform1 runs and acquires a reference to this function’s DomTree
3. Transform1 adds a CFG edge
4. Transform1 immediately notifies the PassManager that all analyses depending
on the CFG must be invalidated
5. PassManager invalidates its reference to the DomTree and LoopInfo
6. Transform1 incrementally updates its copy of the DomTree and reregisters it
with the PassManager.
7. Transform2 runs and reuses the DomTree but must recompute LoopInfo.

You could imagine other kinds of Analysis being dependent on the call graph or
SSA values. You could also imagine that an analyses knows how to partially
invalidate itself for example when a specific function, block, or value changes.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140613/eda5fd0d/attachment.html>