[LLVMdev] Controlling the order of a FunctionPass

[Trevor Harmon]

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

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[John Criswell]

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.

[Trevor Harmon]

On Jul 22, 2010, at 2:05 PM, John Criswell 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:

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.

[John Criswell]

Trevor Harmon wrote:
> On Jul 22, 2010, at 2:05 PM, John Criswell 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
name>). 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.

[Nick Lewycky]

John Criswell wrote:
> Trevor Harmon wrote:
>> On Jul 22, 2010, at 2:05 PM, John Criswell 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
> name>). 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.

>
> 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.
>

>> void MyPass::getAnalysisUsage(AnalysisUsage&AU) const {

>> AU.addRequired<UnifyFunctionExitNodes>();
>> AU.addRequired<LoopInfo>();
>> AU.addPreserved<LoopInfo>();
>> }
>>
>> bool MyPass::runOnFunction(Function&function) {

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

[John Criswell]

Nick Lewycky wrote:
> John Criswell wrote:
>
>> Trevor Harmon wrote:
>>
>>> On Jul 22, 2010, at 2:05 PM, John Criswell 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
>> name>). 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.

[Devang Patel]

On Fri, Jul 23, 2010 at 9:26 PM, Nick Lewycky <nich...@mxc.ca> wrote:
> John Criswell wrote:
>> Trevor Harmon wrote:
>>> On Jul 22, 2010, at 2:05 PM, John Criswell 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
>> name>).  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.

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

[Trevor Harmon]

On Jul 23, 2010, at 7:36 AM, John Criswell 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.)

Any ideas? Thanks,

[John Criswell]

Trevor Harmon wrote:
> On Jul 23, 2010, at 7:36 AM, John Criswell 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.