Passes calling

Hi,

I know when a pass needs other passes, it will use something like this: “AU.addRequired();”. 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?

Thank you
Regards,

Hanbing LI

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.

Instead, your pass should gracefully degrade in the absence of loops being
in simplified form (it is easy to test for this with LoopInfo). Then, you
should ensure that the PassManagerBuilder (or whatever other system you use
to build up a pipeline) puts the loops into simplified form prior to
running your pass.

Dear Hanbing Li,

To the best of my knowledge, the pass dependency mechanism cannot be used to force one transform pass to be run before another pass. You must simply setup the PassManager to ensure that the transform pass runs before your pass.

The reason for this is that adding a transform pass as a dependency can create a situation in which the PassManager cannot schedule the passes to be run (because the transform pass invalidates some analysis pass, creating a chicken-and-egg scheduling problem that PassManager cannot rectify).

Regards,

John Criswell

Just out of curiosity, why is this feature going away? Regards, John Criswell

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.

If I understand what you’re saying, you’re keeping the current functionality of being able to schedule analysis passes using AU.addRequired<>() but removing the ability to schedule transform passes via AU.addRequired<>(), correct? Your original email implied that analysis passes would, in the future, not be scheduled via AU.addRequired<>(). I completely understand not scheduling transform passes that way. Regards, John Criswell

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

If I understand what you're saying, you're keeping the current
functionality of being able to schedule *analysis* passes using
AU.addRequired<>() but removing the ability to schedule *transform* passes
via AU.addRequired<>(), correct?

Correct.

Your original email implied that analysis passes would, in the future, not
be scheduled via AU.addRequired<>(). I completely understand not
scheduling transform passes that way.

Sorry, totally not what I intended to imply!

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

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

Not at all.

The transform has to return a set of preserved analyses. This is more like
the existing system where the assumption is conservative. Again similar to
the existing system, it should be possible (although I've not yet made it
this far) to preserve an abstract set of analyses such as all those only
tied to the CFG.

As for your hypothetical example, I'm not really sure what concrete things
you have in mind, but I'm pretty sure it will be possible based on your
description.

Notably, the analysis actually gets to handle the invalidation event, and
at that time even gets a new reference to the IR. It get's to then *ignore*
the invalidation request by updating its internal state as needed.
Similarly, it gets lots of information about what was invalidated by the
transform.

The thing that doesn't really seem likely to work the way you describe is
that I don't think the *default* behavior will involve mid-transform
invalidation of analyses. The cached analyses are typically invalidated
between transformations. However, there is an explicit API for directly
invalidating, updating, etc. the analysis cache so more things are possible
even if they aren't the default behavior.

Right.

Yes, that’s one of the features I was asking for.

The important thing to me is that the API exists and it is possible. The default behavior can be similar to what we have with the LegacyPassManager.

-Andy

The nice thing (IMO) is that it isn't even that the API exists. It's just
that there is an object which we can add an API to and which the passes
have access to. So we can add whatever APIs we end up wanting here down the
road as we develop a good sense for what is needed.