[llvm-dev] Intended behavior of CGSCC pass manager.

[Hal Finkel via llvm-dev]

----- Original Message -----

> From: "Xinliang David Li" <davidxl at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Sean Silva" <chisophugis at gmail.com>, "llvm-dev"
> <llvm-dev at lists.llvm.org>
> Sent: Thursday, June 16, 2016 12:45:50 PM
> Subject: Re: [llvm-dev] Intended behavior of CGSCC pass manager.

> > To clarify, we're trying to provide this invariant on the "ref"
> > graph
> > or on the graph with direct calls only? I think the invariant need
> > only apply to the former
> 
> More clarification needed :) What do you mean by 'invariant need only
> apply to the former'?
;) 

I mean that we only need to visit children in the "ref" graph before their parents. Furthermore, I'm not even sure that we need an invariant on the SCC level, but rather on the functions themselves. Meaning that I don't think we need to specify an invariant that requires revisiting once we split an SCC (it might be useful to do so, but nothing comes to mind that would require that for correctness). 

> > if we're relying on this for correctness (i.e. an analysis must
> > visit
> > all callees before visiting the callers).
> 

> Not necessarily. Due to lost edges (from caller to indirect callees),
> a callee node may be visited later. The analysis will just have to
> punt when a special edge to 'external' node is seen.
Yes, but my impression is that the "ref" graph has no lost edges (it is the conservative over-approximation). Is that right? 

-Hal 

> David

> > -Hal
> 

> > > Consider the pipeline `cgscc(function(...simplifications that can
> > > devirtualize...),foo-cgscc-pass)`. A possible visitation is as
> > > follows:
> > 
> 

> > > 1. Visit SCC {S,T} and run `function(...simplifications that can
> > > devirtualize...)`. This reveals the call edge T->Y.
> > 
> 
> > > 2. We continue visiting SCC {S,T} and run foo-cgscc-pass on SCC
> > > {S,T}.
> > 
> 
> > > 3. Visit SCC {X,Y} and run `function(...simplifications that can
> > > devirtualize...)`. This reveals the call edge X->S.
> > 
> 
> > > 4. ??? what do we do now.
> > 
> 
> > > Alternative 4.a) Should we continue the visitation and call
> > > foo-cgscc-pass on "SCC" {X,Y}?
> > 
> 
> > > Alternative 4.b) Should foo-cgscc-pass now run on SCC {S,T,X,Y}?
> > 
> 
> > > Alternative 4.c) Should we restart the entire outer `cgscc(...)`
> > > visitation on SCC {S,T,X,Y}?
> > 
> 

> > > (Without a cap both 4.b and 4.c could become quadratic on a graph
> > > like http://reviews.llvm.org/F2073607 )
> > 
> 

> > > -- Sean Silva
> > 
> 

> > > > thanks,
> > > 
> > 
> 

> > > > David
> > > 
> > 
> 

> > > > > Sean:~/pg/llvm % git grep 'public CallGraphSCCPass'
> > > > 
> > > 
> > 
> 
> > > > > include/llvm/Transforms/IPO/InlinerPass.h:struct Inliner :
> > > > > public
> > > > > CallGraphSCCPass {
> > > > 
> > > 
> > 
> 
> > > > > lib/Transforms/IPO/ArgumentPromotion.cpp: struct ArgPromotion
> > > > > :
> > > > > public CallGraphSCCPass {
> > > > 
> > > 
> > 
> 
> > > > > lib/Transforms/IPO/FunctionAttrs.cpp:struct
> > > > > PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
> > > > 
> > > 
> > 
> 
> > > > > lib/Transforms/IPO/PruneEH.cpp: struct PruneEH : public
> > > > > CallGraphSCCPass {
> > > > 
> > > 
> > 
> 
> > > > > lib/Analysis/CallGraphSCCPass.cpp: class PrintCallGraphPass :
> > > > > public
> > > > > CallGraphSCCPass {
> > > > 
> > > 
> > 
> 

> > > > > tools/opt/PassPrinters.cpp:struct CallGraphSCCPassPrinter :
> > > > > public
> > > > > CallGraphSCCPass {
> > > > 
> > > 
> > 
> 

> > > > > CGSCC passes seem to have been added in what is now SVN r8247
> > > > > (~Aug
> > > > > 2003)
> > > > > http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20030825/006619.html
> > > > > (LLVM appears to have been in CVS at the time).
> > > > 
> > > 
> > 
> 

> > > > > Chris, do you remember the motivation for doing the CGSCC
> > > > > visitation
> > > > > instead of a pure post-order function visitation like David
> > > > > is
> > > > > mentioning? (or was it just an oversight / hindsight-20-20
> > > > > thing?)
> > > > > Do you think it would make sense to replace CGSCC visitation
> > > > > with
> > > > > post-order function visitation in the current LLVM?
> > > > 
> > > 
> > 
> 

> > > > > -- Sean Silva
> > > > 
> > > 
> > 
> 

> > > > > > David
> > > > > 
> > > > 
> > > 
> > 
> 

> > > > > > > -- Sean Silva
> > > > > > 
> > > > > 
> > > > 
> > > 
> > 
> 

> > > > > > > > David
> > > > > > > 
> > > > > > 
> > > > > 
> > > > 
> > > 
> > 
> 

> > > > > > > > > Sorry for the wall of text.
> > > > > > > > 
> > > > > > > 
> > > > > > 
> > > > > 
> > > > 
> > > 
> > 
> 

> > > > > > > > > -- Sean Silva
> > > > > > > > 
> > > > > > > 
> > > > > > 
> > > > > 
> > > > 
> > > 
> > 
> 
> > > _______________________________________________
> > 
> 
> > > LLVM Developers mailing list
> > 
> 
> > > llvm-dev at lists.llvm.org
> > 
> 
> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> > 
> 

> > --
> 

> > Hal Finkel
> 
> > Assistant Computational Scientist
> 
> > Leadership Computing Facility
> 
> > Argonne National Laboratory
> 

-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/ead9a84b/attachment.html>