Preservation of CallGraph (by BasicBlockPass, FunctionPass)

If I run:

opt -globals-aa -die -inline -debug-pass=Details foo.ll -S

then I will get this pass structure:

Target Library Information

Target Transform Information

Target Pass Configuration

Assumption Cache Tracker

Profile summary info

ModulePass Manager

CallGraph Construction

Globals Alias Analysis

FunctionPass Manager

BasicBlockPass Manager

Dead Instruction Elimination

Call Graph SCC Pass Manager

Function Integration/Inlining

FunctionPass Manager

Module Verifier

Print Module IR

FPPassManager:: getAnalysisUsage is doing setPreservesAll(),

but is it correct that the FunctionPass Manager always preserves the CallGraph?

My real problem is that when I use a foo.ll input that looks like this:

;----------------------------------------------------------------

target triple = “x86_64-unknown-linux-gnu”

@b = external global i16, align 1

; Function Attrs: nounwind readnone

define i16 @f1() #0 {

entry:

ret i16 undef

}

define void @f2() {

entry:

%call = call i16 @f1()

store i16 %call, i16* @b, align 1

%call1 = call i16 @f1()

ret void

}

attributes #0 = { nounwind readnone }

;----------------------------------------------------------------

then %call1 will be removed by the Dead Instruction Elimination pass. I.e. that pass is not preserving the CallGraph!

Dead Instruction Elimination is a BasicBlockPass, and DeadInstElimination::getAnalysisUsage is doing setPreservesCFG() (even though that should be implicit for a BasicBlockPass afaik).

When reading the description of BasicBlockPass it seems to be legal to remove calls, and that should not impact the CFG, right? But it will impact the CallGraph.

I believe that when the FunctionPass Manager is used from within the Call Graph SCC Pass Manager, then the CGPassManager will check the modification status from the FPManager and call RefreshCallGraph() (or set CallGraphUpToDate=false;) in case modification had been done. Thus, it seems to be legit for a FunctionPass (and thereby also the FunctionPassManager) to not always preserve the CallGraph. And I think this is handled within the CGPassManager, but not when FPManager is executed directly from the MPManager

Currently the test case above will end up in an assert, since there is a missing use of @f1 in the CallGraph when doing the inlining.

That will go away if I remove the setPreservesAll from the FPPassManager:: getAnalysisUsage (which I assume is too aggressive).

Would it be correct to change the FPPassManager:: getAnalysisUsage to exclude “CallGraph Construction” from the set of preserved analyses, or am I missing something here?

I assume that DeadInstElimination isn’t preserving the CallGraph. Shouldn’t that (automatically/dynamically) impact which analyses that are preserved from the BBPassManager and the FPPassManager for this pass structure?

Regards,

Björn

I'm not sure about the old pass manager, but I think the new pass
manager solves this issue. See
llvm::updateCGAndAnalysisManagerForFunctionPass where it updates the
call graph to be in sync with edges deleted by function passes. So I
suspect the right fix is to use the new pass manager.

-- Sanjoy

Well, do you have a patch that enables the new pass manager that we can land then?

To be more serious:

1) I don't even know how to run those passes using the new pass manager even if it where enabled by default. I guess that I'm supposed to use -passes. Is there a syntax description for that option somewhere? How do I for example run -die?

2) "Use the new pass manager" does not answer the question if a basic block may destroy the call graph. Or if it is incorrect for the FPPassManager to say that it preserves all analyses.

/Björn

Hi Björn,

  1. The pass pipeline syntax is documented here: https://github.com/llvm-project/llvm/blob/master/include/llvm/Passes/PassBuilder.h#L378
    -die is not implemented, since the new pass manager does not support BasicBlock passes. But you can use dce instead: “-passes=dce”

  2. I don’t have a qualified answer here, but if I recall correctly, the trouble to correctly update the callgraph was the main motivation for the new PM in the first place.

Cheers,
Philip

Thanks Philip!

Based on your input we will stop using/testing -die for our out-of-tree target.

I guess that the DeadInstructionElimination pass will be removed when the new PM is default. But maybe we can get rid of it already before that?

It does not seem to be used (in-tree) except for some lit-tests. If we replace those uses by -dce, then maybe the pass can be removed right away.

And I assume that -print-bb also should be removed (since it is a BasicBlockPass).

/Björn