Pass Manager Restriction?

Having a ModulePass that requires a FunctionPass that in turn requires
another ModulePass results in an assertion being fired. Is this
expected behavior (that seems to be undocumented), or a bug?

Specifically, the following code will emit the assertion:
[VMCore/PassManager.cpp:1597: virtual void
llvm::ModulePass::assignPassManager(llvm::PMStack&,
llvm::PassManagerType): Assertion `!PMS.empty() && "Unable to find
appropriate Pass Manager"' failed]

Joseph,

I had a similar problem a while back...

Our solution was twofold:
(1) To the degree possible, make everything a pass of the same level
(e.g. all FunctionPasses, all ModulePasses, etc).
(2) The order in which .addRequired<Foo>() are called within
getAnalysisUsage() matters, try a different ordering.

Beyond that, I don't know (no one responded to my post).

Good luck,
Nick

"A module pass can use function level passes (e.g. dominators) using getAnalysis interfacegetAnalysis<DominatorTree>(Function), if the function pass does not require any module passes."

http://llvm.org/docs/WritingAnLLVMPass.html

In your case, A module pass (ModPass2) is trying tu use function level pass (FunPass1) which uses module level pass (ModPass1). This is not supported.

Good to know. I was referencing a local copy of 2.3 docs which didn't
include the "does not require any module passes" statement. It appears
the docs were changed two days before 2.4 was released in November. I
suppose I should update my docs more often.

Are there any plans to change this restriction, or any best practices
to get similar behavior? Since immutable pass is a subclass of module
pass, this problem extends to immutable passes as well. In particular,
any function pass that requires AliasAnalysis or
MemoryDependenceAnalysis (which in turn requires AliasAnalysis) can no
longer be used in a following module pass (even if the basic alias
analysis is used, which is an immutable pass). This makes
inter-procedural transformations/analysis that depends on memory
dependence information difficult to achieve. I've worked around the
problem by partitioning my passes into two sets which are run serially
and share relevant information through an external structure on the
heap, but that completely kills the benefit of the pass manager and
having LLVM manage the lifetime of analysis information automatically.

In short, I'm just surprised this type of chaining doesn't appear in
the existing set of LLVM passes. Is there an obvious way to
restructure passes that I'm missing?

Good to know. I was referencing a local copy of 2.3 docs which didn't
include the "does not require any module passes" statement. It appears
the docs were changed two days before 2.4 was released in November. I
suppose I should update my docs more often.

Are there any plans to change this restriction, or any best practices
to get similar behavior?

There are any any plans to change this restriction at the moment. The best option is to avoid writing a module pass that requires function pass.

Since immutable pass is a subclass of module
pass, this problem extends to immutable passes as well. In particular,
any function pass that requires AliasAnalysis or
MemoryDependenceAnalysis (which in turn requires AliasAnalysis) can no
longer be used in a following module pass (even if the basic alias
analysis is used, which is an immutable pass). This makes
inter-procedural transformations/analysis that depends on memory
dependence information difficult to achieve. I've worked around the
problem by partitioning my passes into two sets which are run serially
and share relevant information through an external structure on the
heap, but that completely kills the benefit of the pass manager and
having LLVM manage the lifetime of analysis information automatically.

In short, I'm just surprised this type of chaining doesn't appear in
the existing set of LLVM passes. Is there an obvious way to
restructure passes that I'm missing?

... because usually a module pass operates on entire module (e.g. inliner) and it does not require information specific to a function. If your pass need info collected by a function pass then why not structure your pass as a function pass and run it for all function in a module ?

I very much disagree with this reasoning. The ``level'' of a
pass---module, loop, function, whatever---should have more to do with
making the algorithm legible than with restricting its scope.

We often write a FunctionPass or a LoopPass because it is the most
natural way to express the analysis or transformation, not because the
information gathered are localized. My research group has many
function-level transformations which are loosely-coupled with
loop-level analyses. For example, multi-threaded code generation (1)
splits an arbitrary *function* into multiple threads, but requires a
partition. Decoupled software pipelining (2) generates such a
partition by analyzing a *loop*. At the moment, we implement
decoupled software pipelining as a function pass, even though we think
the code would be more maintainable as a loop pass.

And what about Immutable passes, such as TargetData? They are
technically ModulePasses. But if you schedule passes in the incorrect
order, llvm will try to instantiate a new TargetData in a private pass
manager, causing an assert.

I think the notion of ``levels'' of passes is artificial, unintuitive,
and unnecessary.

Hi Nick,

I meant to say "there are not any immediate plans", I did not mean to say "never ever". The facility to use function pass, in a limited scope, from a module pass was introduced recently (IIRC, after 2.0 release).

... because usually a module pass operates on entire module (e.g.
inliner) and it does not require information specific to a function.
If your pass need info collected by a function pass then why not
structure your pass as a function pass and run it for all function in
a module ?

I very much disagree with this reasoning. The ``level'' of a
pass---module, loop, function, whatever---should have more to do with
making the algorithm legible than with restricting its scope.

We often write a FunctionPass or a LoopPass because it is the most
natural way to express the analysis or transformation, not because the
information gathered are localized.

It has to do with how analysis information is managed. The pass manager itself does not store any info. The analysis information is collected and maintained by respective passes.

Normally, if a function pass FP1 requires inform from function pass FP0 then all pass manager does is ensure that for each function FP0 is run before FP1. Simple. Now, FP1 can query FP0 for the function it is operating on.

However when the module pass request such information, the pass manager MP1 asks function pass FPO to generate this information on the fly for the given function. There is not any mechanism to maintain function analysis info generated by FP0 for all functions. MemoryDependenceAnalysis will only keep info for the last function it analyzed.

My research group has many
function-level transformations which are loosely-coupled with
loop-level analyses.

Are your pass using loop info or manipulating loops ? If they are manipulating loops then they are loop-level transformations. Otherwise, they can request LoopInfo, which is a function pass.