Controlling the order of a FunctionPass

Hi,

I would like my FunctionPasses to be invoked in reverse call graph order (callees before callers). However, "Writing an LLVM Pass" notes that "FunctionPass's do not require that they are executed in a particular order." Is there any way at all to specify an ordering?

If this is not possible, I'm thinking of a workaround in which my runOnFunction method does not actually process the function but instead copies the Function object to a "work set". When runOnFunction has been invoked for all functions, I would then perform the analysis on each saved function in the order that I desire. Does this sound like the right approach? (Note that my pass is analysis-only -- it does not modify the functions.)

Thanks,

Trevor

Trevor Harmon wrote:

Hi,

I would like my FunctionPasses to be invoked in reverse call graph order (callees before callers). However, "Writing an LLVM Pass" notes that "FunctionPass's do not require that they are executed in a particular order." Is there any way at all to specify an ordering?

If this is not possible, I'm thinking of a workaround in which my runOnFunction method does not actually process the function but instead copies the Function object to a "work set". When runOnFunction has been invoked for all functions, I would then perform the analysis on each saved function in the order that I desire. Does this sound like the right approach? (Note that my pass is analysis-only -- it does not modify the functions.)
  
If you write your pass as a ModulePass, then you can iterate over the functions in any order that you want.

Unless writing your pass as a CallGraphSCCPass gets you the right iteration order, writing your pass as a ModulePass looks like the proper way to do this. FunctionPass'es are supposed to do only local analysis and are required to be completely independent; a FunctionPass should not record information between invocations of its runOnFunction() method.

-- John T.

I had considered that, but my FunctionPass depends on other passes processing the functions first:

void MyPass::getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addRequired<UnifyFunctionExitNodes>();
     AU.addRequired<LoopInfo>();
     AU.addPreserved<LoopInfo>();
}

bool MyPass::runOnFunction(Function &function) {
     LoopInfo &loopInfo = getAnalysis<LoopInfo>();
     ...
}

I don't know how to convert the above code into its equivalent form for a ModulePass.

Trevor

Trevor Harmon wrote:

If you write your pass as a ModulePass, then you can iterate over the
functions in any order that you want.
    
I had considered that, but my FunctionPass depends on other passes processing the functions first:
  
Two things to consider:

1) The PassManager isn't currently designed to schedule prerequisite *transform* passes (like UnifyFunctionExitNodes). If your pass requires that another transform pass be executed first, then the PassManager must be explicitly told (via the PassManager.add() method) to run that pass first. If you're running your pass via the opt tool, then it means that the user must manually specify the prerequisite passes in the correct order (e.g., opt -load <your pass filename> -mergereturn -<your pass

). If you're building a separate program that schedules the

passes, then it needs to run the prerequisite passes first.

See the sc tool in the SAFECode source code for an example.

2) For prerequisite *analysis* passes (like LoopInfo), your ModulePass can declare them as prerequisites and get access to them using the getAnalysis<PassName>(Function *) method. This is documented in the "Writing an LLVM Pass" manual (http://llvm.org/docs/WritingAnLLVMPass.html#getAnalysis).

-- John T.

John Criswell wrote:

Trevor Harmon wrote:

If you write your pass as a ModulePass, then you can iterate over the
functions in any order that you want.

I had considered that, but my FunctionPass depends on other passes
processing the functions first:

Two things to consider:

1) The PassManager isn't currently designed to schedule prerequisite
*transform* passes (like UnifyFunctionExitNodes). If your pass requires
that another transform pass be executed first, then the PassManager must
be explicitly told (via the PassManager.add() method) to run that pass
first. If you're running your pass via the opt tool, then it means that
the user must manually specify the prerequisite passes in the correct
order (e.g., opt -load<your pass filename> -mergereturn -<your pass
>). If you're building a separate program that schedules the
passes, then it needs to run the prerequisite passes first.

What?? Sure it does. See all the passes which require BreakCritEdges or LCSSA for examples.

Nick Lewycky wrote:

John Criswell wrote:
  

Trevor Harmon wrote:
    

If you write your pass as a ModulePass, then you can iterate over the
functions in any order that you want.

I had considered that, but my FunctionPass depends on other passes
processing the functions first:

Two things to consider:

1) The PassManager isn't currently designed to schedule prerequisite
*transform* passes (like UnifyFunctionExitNodes). If your pass requires
that another transform pass be executed first, then the PassManager must
be explicitly told (via the PassManager.add() method) to run that pass
first. If you're running your pass via the opt tool, then it means that
the user must manually specify the prerequisite passes in the correct
order (e.g., opt -load<your pass filename> -mergereturn -<your pass
>). If you're building a separate program that schedules the
passes, then it needs to run the prerequisite passes first.
    
What?? Sure it does. See all the passes which require BreakCritEdges or LCSSA for examples.
  
Interesting. I was told that PassManager did not (in general) support this feature and had to refactor Automatic Pool Allocation and SAFECode passes to not require transform passes. Perhaps problems only manifest when you have weird passes like Automatic Pool Allocation which act as both a transform and an analysis pass.

-- John T.

Its not recommended. Note, all the interfaces are .. "getAnalysis..."
and never "getTransformation..." :slight_smile:

Yes, I remember trying this before but was unsuccessful. I made a second attempt just now and am again running into the same issue:

bool MyModulePass::runOnModule(Module &M) {
     for (Module::iterator i = M.begin(), e = M.end(); i != e; ++i) {
         Function *function = i;
         LoopInfo &loopInfo = getAnalysis<LoopInfo>(function);
         ...
     }
     ...
}

MyModulePass.cpp: In member function ‘virtual bool MyModulePass::runOnModule(llvm::Module&)’:
MyModulePass.cpp:70: error: no matching function for call to ‘MyModulePass::getAnalysis(llvm::Function*&)’

I believe I'm calling getAnalysis the same way as shown in "Writing an LLVM Pass", so I don't know what I'm doing wrong. (I thought perhaps I needed to call getAnalysis on the module reference, but it has no such member function.)

Any ideas? Thanks,

Trevor

Trevor Harmon wrote:

2) For prerequisite *analysis* passes (like LoopInfo), your ModulePass
can declare them as prerequisites and get access to them using the
getAnalysis<PassName>(Function *) method.
    
Yes, I remember trying this before but was unsuccessful. I made a second attempt just now and am again running into the same issue:

bool MyModulePass::runOnModule(Module &M) {
     for (Module::iterator i = M.begin(), e = M.end(); i != e; ++i) {
         Function *function = i;
         LoopInfo &loopInfo = getAnalysis<LoopInfo>(function);
         ...
     }
     ...
}

MyModulePass.cpp: In member function ‘virtual bool MyModulePass::runOnModule(llvm::Module&)’:
MyModulePass.cpp:70: error: no matching function for call to ‘MyModulePass::getAnalysis(llvm::Function*&)’

I believe I'm calling getAnalysis the same way as shown in "Writing an LLVM Pass", so I don't know what I'm doing wrong. (I thought perhaps I needed to call getAnalysis on the module reference, but it has no such member function.)
  
This form of getAnalysis takes a reference to a function and not a pointer to it. The following should work:

LoopInfo &loopInfo = getAnalysis<LoopInfo>(*function);

-- John T.