llvm dev - May 2015 - [LLVMdev] Processing functions in call graph SCC "order" with function-level analyses

Thanks John.

Does this solve the problem of analysis availability though? If I still have to
run the function analyses manually, I might as well keep rolling with the
CallGraphSCCPass. (I probably should have mentioned that this is what I’m using
right now.)

Félix
> Le 2015-05-19 à 10:12:32, John Criswell <jtcriswel at gmail.com> a
écrit :
> 
> On 5/18/15 10:45 PM, Félix Cloutier wrote:
>> Hi all,
>> 
>> I have one analysis pass that I want to perform on call graph SCCs.
However, for each function in the SCC, I need function-level analyses, like the
dominator tree and the memory dependency analysis.
>> 
>> I’ve been told before
<http://stackoverflow.com/questions/30059622/using-dominatortreewrapperpass-in-callgraphsccpass>
that these were not available from a CallGraphSCCPass. What would be the best
approach for me to access this information? Should I run the passes manually, or
is there another, more pass-scheduler-friendly approach?
> 
> I would write a ModulePass that simply iterates over the call graph.  LLVM
provides a CallGraph analysis which one can use to find SCCs; DSA has an
analysis called CallTargets which does "real" CallGraph analysis
(which means that it tries to reason about function pointers, though I cannot
guarantee that its reasoning will be as accurate as you want).
> 
> If you use a ModulePass, can you analyze any part of the program you like,
and you can use FunctionPasses.
> 
> Regards,
> 
> John Criswell
> 
>> 
>> Félix
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
> 
> 
> -- 
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell
<http://www.cs.rochester.edu/u/criswell>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/3928b0eb/attachment.html>

On 5/19/15 10:04 AM, Félix Cloutier wrote:
> Thanks John.
>
> Does this solve the problem of analysis availability though? If I 
> still have to run the function analyses manually, I might as well keep 
> rolling with the CallGraphSCCPass. (I probably should have mentioned 
> that this is what I’m using right now.)
I'm not sure what you mean by "manually."  If you use a
ModulePass, you
can use the getAnalysis<FunctionPassName>(F) method to get a reference 
to a function pass.  The ModulePass's getAnalysisUsage() method will 
need to use addRequired<FunctionPass>() to require each FunctionPass, 
but I think the PassManager will run the passes automatically as needed.

Note that you cannot use the PassManager to ensure that certain 
optimization passes are run before your pass is run.  If you need to run 
an optimization pass before your pass (e.g., UnifyExitNodes), then you 
need to tell the PassManager to run it before your pass explicitly.

Regards,

John Criswell
>
> Félix
>
>> Le 2015-05-19 à 10:12:32, John Criswell <jtcriswel at gmail.com 
>> <mailto:jtcriswel at gmail.com>> a écrit :
>>
>> On 5/18/15 10:45 PM, Félix Cloutier wrote:
>>> Hi all,
>>>
>>> I have one analysis pass that I want to perform on call graph SCCs.
>>> However, for each function in the SCC, I need function-level 
>>> analyses, like the dominator tree and the memory dependency
analysis.
>>>
>>> I’ve been told before 
>>>
<http://stackoverflow.com/questions/30059622/using-dominatortreewrapperpass-in-callgraphsccpass>
that
>>> these were not available from a CallGraphSCCPass. What would be the
>>> best approach for me to access this information? Should I run the 
>>> passes manually, or is there another, more pass-scheduler-friendly 
>>> approach?
>>
>> I would write a ModulePass that simply iterates over the call graph.  
>> LLVM provides a CallGraph analysis which one can use to find SCCs; 
>> DSA has an analysis called CallTargets which does "real"
CallGraph
>> analysis (which means that it tries to reason about function 
>> pointers, though I cannot guarantee that its reasoning will be as 
>> accurate as you want).
>>
>> If you use a ModulePass, can you analyze any part of the program you 
>> like, and you can use FunctionPasses.
>>
>> Regards,
>>
>> John Criswell
>>
>>>
>>> Félix
>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu          http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>> -- 
>> John Criswell
>> Assistant Professor
>> Department of Computer Science, University of Rochester
>> http://www.cs.rochester.edu/u/criswell
>

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/b4b98d5d/attachment.html>

You’ll excuse me if I got mixed up somewhere.

The initial problem I had is that adding a required analysis in my
CallGraphSCCPass’s getAnalysisUsage caused a runtime error:
> Unable to schedule 'Dominator Tree Construction' required by ‘My
Pass'
> Unable to schedule pass
> UNREACHABLE executed at LegacyPassManager.cpp:1264!

My pass is declared in the same program that links against LLVM. The correct way
to register these passes appears to use the RegisterPass<T> template,
however it does not appear to allow declaring pass dependencies.

At the time, I was advised to bypass the DomTreeWrapperPass and just use
DominatorTree::recalculate when I needed it.

It’s with this background that I was saying that the passes are run
"manually".

Félix
> Le 2015-05-19 à 12:47:32, John Criswell <jtcriswel at gmail.com> a
écrit :
> 
> On 5/19/15 10:04 AM, Félix Cloutier wrote:
>> Thanks John.
>> 
>> Does this solve the problem of analysis availability though? If I still
have to run the function analyses manually, I might as well keep rolling with
the CallGraphSCCPass. (I probably should have mentioned that this is what I’m
using right now.)
> 
> I'm not sure what you mean by "manually."  If you use a
ModulePass, you can use the getAnalysis<FunctionPassName>(F) method to get
a reference to a function pass.  The ModulePass's getAnalysisUsage() method
will need to use addRequired<FunctionPass>() to require each FunctionPass,
but I think the PassManager will run the passes automatically as needed.
> 
> Note that you cannot use the PassManager to ensure that certain
optimization passes are run before your pass is run.  If you need to run an
optimization pass before your pass (e.g., UnifyExitNodes), then you need to tell
the PassManager to run it before your pass explicitly.
> 
> Regards,
> 
> John Criswell
> 
>> 
>> Félix
>> 
>>> Le 2015-05-19 à 10:12:32, John Criswell <jtcriswel at gmail.com
<mailto:jtcriswel at gmail.com>> a écrit :
>>> 
>>> On 5/18/15 10:45 PM, Félix Cloutier wrote:
>>>> Hi all,
>>>> 
>>>> I have one analysis pass that I want to perform on call graph
SCCs. However, for each function in the SCC, I need function-level analyses,
like the dominator tree and the memory dependency analysis.
>>>> 
>>>> I’ve been told before
<http://stackoverflow.com/questions/30059622/using-dominatortreewrapperpass-in-callgraphsccpass>
that these were not available from a CallGraphSCCPass. What would be the best
approach for me to access this information? Should I run the passes manually, or
is there another, more pass-scheduler-friendly approach?
>>> 
>>> I would write a ModulePass that simply iterates over the call
graph.  LLVM provides a CallGraph analysis which one can use to find SCCs; DSA
has an analysis called CallTargets which does "real" CallGraph
analysis (which means that it tries to reason about function pointers, though I
cannot guarantee that its reasoning will be as accurate as you want).
>>> 
>>> If you use a ModulePass, can you analyze any part of the program
you like, and you can use FunctionPasses.
>>> 
>>> Regards,
>>> 
>>> John Criswell
>>> 
>>>> 
>>>> Félix
>>>> 
>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>   
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>>> 
>>> 
>>> -- 
>>> John Criswell
>>> Assistant Professor
>>> Department of Computer Science, University of Rochester
>>> http://www.cs.rochester.edu/u/criswell
<http://www.cs.rochester.edu/u/criswell>
> 
> 
> -- 
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell
<http://www.cs.rochester.edu/u/criswell>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/0b394d83/attachment.html>

So I got very mixed results.

With the CallGraphSCCPass, both `addRequired<DominatorTreeWrapperPass>`
and `addRequired<MemoryDependenceAnalysis>` fail at runtime. The LLVM core
has just two CallGraphSCCPasses and neither uses neither analyses, so it's
hard to find a valid example.

I transformed the pass into a ModulePass, using scc_iterator as shown in
CGPassManager to process functions in order, and the situation isn't a whole
lot better.

Interestingly, `addRequired<CallGraphWrapperPass>()` failed on me, even
though at first glance, CGPassManager doesn't seem to be doing anything that
I'm not doing. This is relatively easily bypassed by creating the CallGraph
from runOnModule.

`addRequired<MemoryDependenceAnalysis>()` fails with this error message:
> Pass 'My Pass' is not initialized.
> Verify if there is a pass dependency cycle.
> Required Passes:
> 	Dominator Tree Construction
> Assertion failed: (PI && "Expected required passes to be
initialized"), function schedulePass, file LegacyPassManager.cpp, line 641.
"Dominator Tree Construction" disappears from the error message
(leaving an empty list of required passes) if I move its `addRequired` *after*
MemDep's.

`addRequired<DominatorTreeWrapperPass>()` worked instantly, so there's
that, I suppose.

This all looks like rather basic things to do with the pass architecture, and I
can't seem to find documentation explaining which analyses can be used in
which types of passes. As I can only find examples of MemDep in FunctionPasses,
I'll probably switch over to that, but this is going to be frustrating when
I'll need call graph SCC information. Anyone has a better idea?

I should note that I'm not using the INITIALIZE_PASS macros because I have
no idea how they mesh with RegisterPass. I'm seeing that the passes that use
these have INITIALIZE_PASS_DEPENDENCY macros and it makes me a little nervous,
but the resulting function for my pass is seemingly never called.

Félix
> Le 2015-05-19 à 12:47:32, John Criswell <jtcriswel at gmail.com> a
écrit :
> 
> On 5/19/15 10:04 AM, Félix Cloutier wrote:
>> Thanks John.
>> 
>> Does this solve the problem of analysis availability though? If I still
have to run the function analyses manually, I might as well keep rolling with
the CallGraphSCCPass. (I probably should have mentioned that this is what I’m
using right now.)
> 
> I'm not sure what you mean by "manually."  If you use a
ModulePass, you can use the getAnalysis<FunctionPassName>(F) method to get
a reference to a function pass.  The ModulePass's getAnalysisUsage() method
will need to use addRequired<FunctionPass>() to require each FunctionPass,
but I think the PassManager will run the passes automatically as needed.
> 
> Note that you cannot use the PassManager to ensure that certain
optimization passes are run before your pass is run.  If you need to run an
optimization pass before your pass (e.g., UnifyExitNodes), then you need to tell
the PassManager to run it before your pass explicitly.
> 
> Regards,
> 
> John Criswell
> 
>> 
>> Félix
>> 
>>> Le 2015-05-19 à 10:12:32, John Criswell <jtcriswel at gmail.com
<mailto:jtcriswel at gmail.com>> a écrit :
>>> 
>>> On 5/18/15 10:45 PM, Félix Cloutier wrote:
>>>> Hi all,
>>>> 
>>>> I have one analysis pass that I want to perform on call graph
SCCs. However, for each function in the SCC, I need function-level analyses,
like the dominator tree and the memory dependency analysis.
>>>> 
>>>> I’ve been told before
<http://stackoverflow.com/questions/30059622/using-dominatortreewrapperpass-in-callgraphsccpass>
that these were not available from a CallGraphSCCPass. What would be the best
approach for me to access this information? Should I run the passes manually, or
is there another, more pass-scheduler-friendly approach?
>>> 
>>> I would write a ModulePass that simply iterates over the call
graph.  LLVM provides a CallGraph analysis which one can use to find SCCs; DSA
has an analysis called CallTargets which does "real" CallGraph
analysis (which means that it tries to reason about function pointers, though I
cannot guarantee that its reasoning will be as accurate as you want).
>>> 
>>> If you use a ModulePass, can you analyze any part of the program
you like, and you can use FunctionPasses.
>>> 
>>> Regards,
>>> 
>>> John Criswell
>>> 
>>>> 
>>>> Félix
>>>> 
>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>   
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>>> 
>>> 
>>> -- 
>>> John Criswell
>>> Assistant Professor
>>> Department of Computer Science, University of Rochester
>>> http://www.cs.rochester.edu/u/criswell
<http://www.cs.rochester.edu/u/criswell>
> 
> 
> -- 
> John Criswell
> Assistant Professor
> Department of Computer Science, University of Rochester
> http://www.cs.rochester.edu/u/criswell
<http://www.cs.rochester.edu/u/criswell>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/7678156c/attachment.html>