llvm dev - May 2018 - 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180507/d60b5721/attachment.html>

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

On Mon, May 7, 2018 at 7:32 AM, Björn Pettersson A via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 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
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

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
> -----Original Message-----
> From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com]
> Sent: den 7 maj 2018 20:22
> To: Björn Pettersson A <bjorn.a.pettersson at ericsson.com>; Chandler
> Carruth <chandlerc at google.com>
> Cc: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Preservation of CallGraph (by BasicBlockPass,
> FunctionPass)
> 
> 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
> 
> On Mon, May 7, 2018 at 7:32 AM, Björn Pettersson A via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > 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
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >