Xinliang David Li via llvm-dev
2016-Jun-16 17:45 UTC
[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'?> 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. 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 >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/4c04ea97/attachment.html>
Hal Finkel via llvm-dev
2016-Jun-16 17:52 UTC
[llvm-dev] Intended behavior of CGSCC pass manager.
----- 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>
Xinliang David Li via llvm-dev
2016-Jun-17 04:43 UTC
[llvm-dev] Intended behavior of CGSCC pass manager.
On Thu, Jun 16, 2016 at 10:52 AM, Hal Finkel <hfinkel at anl.gov> wrote:> > ------------------------------ > > *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? >I am not sure. By looking at the code 'findReferences', it does not actually look at an indirect callsites -- the references are purely from referenced globals to function addresses -- so at least the edges from caller to indirect call targets are lost, right? On the other hand, if that is modeled, the memory consumption will be quadratic. David> > > -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/57bf9f7c/attachment.html>