Processing functions in call graph SCC "order" with function-level analyses

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

Félix

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

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

I’m not sure what you mean by “manually.” If you use a ModulePass, you can use the getAnalysis(F) method to get a reference to a function pass. The ModulePass’s getAnalysisUsage() method will need to use addRequired() 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

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

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

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.

Have you tried INITIALIZE_PASS_BEGIN and INITIALIZE_PASS_DEPENDENCY?

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.

You haven't used INTIIALIZE_PASS_*

I did it for the CallGraphSCCPass version, and called the initialization function explicitly (with PassRegistry::getPassRegistry() as the parameter; is that correct?). I got this:

Unable to schedule 'Dominator Tree Construction' required by 'My Pass'
Unable to schedule pass
UNREACHABLE executed at LegacyPassManager.cpp:1264!

Is it worth it to try with the pass as a ModulePass? If so, I'll try it tomorrow.

Félix

So yes, for the record, it works with ModulePass.

Any idea why it didn't with CallGraphSCCPass?

Félix