[LLVMdev] Function Pass Manager

[John Criswell]

On 6/5/12 10:39 AM, Ralf Karrenberg wrote:
> Hi John,
>
> On 6/5/12 4:31 PM, John Criswell wrote:
>> On 4/12/12 3:32 AM, Ivan Llopard wrote:
>>> Hi again,
>>>
>>> I come back to this issue with an example. It's a pass which does
>>> nothing but throw the 'Unable to schedule' error.
>>>
>>> namespace {
>>>      struct MyPass : public FunctionPass {
>>>        static char ID; // Pass identification, replacement for typeid
>>>        MyPass() : FunctionPass(ID) {
>>>          initializeMyPassPass(*PassRegistry::getPassRegistry());
>>>        }
>>>        virtual void getAnalysisUsage(AnalysisUsage&AU) const {
>>>          AU.addRequiredID(LoopSimplifyID);
>>>          AU.addPreservedID(LoopSimplifyID);
>>>        }
>>>        virtual bool runOnFunction(Function&F);
>>>      };
>>> }
>>
>> Is LoopSimplifyID an analysis pass or a transform (optimization) pass?
>
> It is a transform pass (it can alter the CFG).
>
>> You cannot reliably use the addRequired() method to force a transform
>> pass to run before another pass; there are cases in which the
>> PassManager cannot schedule the required passes.  You must simply ensure
>> that LoopSimplify is executed before your pass.
>
> I am afraid I do not understand this. What is the purpose of 
> addRequired() if not ensuring that the pass is run before execution of 
> my own pass?

The addRequired method is designed to tell the PassManager which 
*analysis* passes to run before your pass.  This allows the PassManager 
to optimize the pass schedule so that analysis passes are only re-run 
when needed.  Analysis passes don't modify the IR so PassManager can 
always find a way to schedule the passes.

The reason why you can't require a transform pass is because you can get 
impossible-to-schedule pass schedules (or, at least, schedules that 
PassManager isn't smart enough to schedule because it assumes that all 
required passes are analysis passes) .  For example, assume Pass C 
requires Passes A and B.  Passes A and B invalidate all other passes 
because they are transform passes.  There's no possible schedule for 
these passes.

>
> I would be perfectly happy with *any* solution that allows me to 
> ensure that LoopSimplify is executed before my FunctionPass.

Sadly, there isn't such a feature.  It is the job of the person (or 
program) putting together the pass schedule to ensure that transform 
passes are run in the correct order relative to other transform passes.  
Only analysis passes are scheduled automatically by PassManager.

What you could do to catch bugs is to write an analysis pass that 
verifies that the loops have the structure that you need; this pass 
would assert out if the loops aren't in canonical form.  Your pass could 
require this new analysis pass.  If someone forgets to run the pass that 
puts loops into canonical form, this analysis pass would catch the error.

-- John T.

>
> Thanks,
> Ralf