Xinliang David Li via llvm-dev
2016-Jun-17 06:07 UTC
[llvm-dev] Intended behavior of CGSCC pass manager.
On Thu, Jun 16, 2016 at 10:47 PM, Sean Silva <chisophugis at gmail.com> wrote:> > > On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at google.com> > wrote: > >> >> >> On Thu, Jun 16, 2016 at 11:12 AM, Sanjoy Das < >> sanjoy at playingwithpointers.com> wrote: >> >>> Hi Sean, >>> >>> On Thu, Jun 16, 2016 at 4:48 AM, Sean Silva via llvm-dev >>> <llvm-dev at lists.llvm.org> wrote: >>> > One question is what invariants we want to provide for the visitation. >>> > >>> > For example, should a CGSCC pass be able to assume that all "child" >>> SCC's >>> > (SCC's it can reach via direct calls emanating from the SCC being >>> visited) >>> > have already been visited? Currently I don't think it can, and IIRC >>> from the >>> > discussion at the social this is one thing that Chandler is hoping to >>> fix. >>> > The "ref edge" notion in LazyCallGraph ensures that we cannot create a >>> call >>> > edge (devirtualizing a ref edge) that will point at an SCC that has >>> not yet >>> > been visited. >>> > >>> > E.g. consider this graph: >>> > >>> > digraph G { >>> > A -> B; B -> A; // SCC {A,B} >>> > S -> T; T -> S; // SCC {S,T} >>> > X -> Y; Y -> X; // SCC {X,Y} >>> > >>> > B -> X; >>> > B -> S; >>> > T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC >>> > {S,T}",constraint=false,style=dashed] >>> > } >>> > >>> > (can visualize conveniently at http://www.webgraphviz.com/ or I have >>> put an >>> > image at http://reviews.llvm.org/F2073104) >>> > >>> > If we do not consider the ref graph, then it is possible for SCC {S,T} >>> to be >>> >>> I'm not sure why you wouldn't consider the ref graph? I think the >>> general idea is to visit RefSCCs in bottom up order, and when visiting >>> a RefSCC, visiting the SCC's inside the RefSCC in bottom up order. >>> >>> So in your example, given the edges you've shown, we will visit {X,Y} >>> before visiting {S,T}. >>> >>> > A more complicated case is when SCC {S,T} and SCC {X,Y} both call into >>> each >>> > other via function pointers. So eventually after devirtualizing the >>> calls in >>> > both directions there will be a single SCC {S,T,X,Y}. >>> > >>> > digraph G { >>> > A -> B; B -> A; // SCC {A,B} >>> > S -> T; T -> S; // SCC {S,T} >>> > X -> Y; Y -> X; // SCC {X,Y} >>> > >>> > B -> X; >>> > B -> S; >>> > T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC >>> > {S,T}",constraint=false,style=dashed] >>> > X -> S [label="Ref edge that is devirtualized\nwhen visiting SCC >>> > {X,Y}",constraint=false,style=dashed] >>> > } >>> > >>> > (rendering at: http://reviews.llvm.org/F2073479) >>> > >>> > Due to the cyclic dependence there is no SCC visitation order that can >>> > directly provide the invariant above. Indeed, the problem of >>> maintaining the >>> >>> I think the workflow in the above will (roughly) be: >>> >>> Visit the RefSCC {X,Y,S,T} >>> >> >> Are we sure RefSCC has ref edges between {X, Y} and {S, T} in this case? >> I may miss the code handling it. >> > > The ref graph is conservative and so it would have the appropriate edges. > > https://github.com/llvm-project/llvm-project/blob/master/llvm/lib/Analysis/LazyCallGraph.cpp#L90 >That is where the confusion is -- the findReferences's function body only handles constant operands which may be function addresses. Did I miss something obvious? Another point is that it may not be practical to model edges to indirect targets. For virtual calls, without CHA, each virtual callsite will end up referencing all potential address taken functions.> > > >> >> >> >>> Visit the SCC {X,Y} // arbitrary >>> Optimize({X,Y}) >>> // Now there's an edge to {S,T}, invalidate >>> // the analyses cached for {X,Y} and visit {S,T} >>> >> >> I am not sure if this makes sense. If dynamically, the call edge from >> {X, Y} to {S, T} does exist, but not discovered by the analysis, then the >> cached {X, Y} will still be invalid, but who is going to invalidate it? >> > > I assume that if dynamically there was a call from {X,Y} to {S,T}, then > the analysis would have observed an indirect call and would have behaved > conservatively. >See above, I did not see how indirect call is handled. Also if the result for {X, Y} is conservatively correct before the direct call edge is discovered, why bother invalidating its analysis when the call edge is exposed? David> > -- Sean Silva > > >> >> David >> >> >> >> >> >>> Visit the SCC {S,T} >>> Optimize({S,T}) >>> // Now {X,Y,S,T} collapses to form a single SCC >>> Visit the SCC {S,T,X,Y} >>> Optimize({S,T,X,Y}) >>> >>> The difficult bit is to make the inner "// Now.*" bits work well. >>> >>> -- Sanjoy >>> >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/cc067afe/attachment.html>
Sean Silva via llvm-dev
2016-Jun-17 06:51 UTC
[llvm-dev] Intended behavior of CGSCC pass manager.
On Thu, Jun 16, 2016 at 11:07 PM, Xinliang David Li <davidxl at google.com> wrote:> > > On Thu, Jun 16, 2016 at 10:47 PM, Sean Silva <chisophugis at gmail.com> > wrote: > >> >> >> On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at google.com> >> wrote: >> >>> >>> >>> On Thu, Jun 16, 2016 at 11:12 AM, Sanjoy Das < >>> sanjoy at playingwithpointers.com> wrote: >>> >>>> Hi Sean, >>>> >>>> On Thu, Jun 16, 2016 at 4:48 AM, Sean Silva via llvm-dev >>>> <llvm-dev at lists.llvm.org> wrote: >>>> > One question is what invariants we want to provide for the visitation. >>>> > >>>> > For example, should a CGSCC pass be able to assume that all "child" >>>> SCC's >>>> > (SCC's it can reach via direct calls emanating from the SCC being >>>> visited) >>>> > have already been visited? Currently I don't think it can, and IIRC >>>> from the >>>> > discussion at the social this is one thing that Chandler is hoping to >>>> fix. >>>> > The "ref edge" notion in LazyCallGraph ensures that we cannot create >>>> a call >>>> > edge (devirtualizing a ref edge) that will point at an SCC that has >>>> not yet >>>> > been visited. >>>> > >>>> > E.g. consider this graph: >>>> > >>>> > digraph G { >>>> > A -> B; B -> A; // SCC {A,B} >>>> > S -> T; T -> S; // SCC {S,T} >>>> > X -> Y; Y -> X; // SCC {X,Y} >>>> > >>>> > B -> X; >>>> > B -> S; >>>> > T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC >>>> > {S,T}",constraint=false,style=dashed] >>>> > } >>>> > >>>> > (can visualize conveniently at http://www.webgraphviz.com/ or I have >>>> put an >>>> > image at http://reviews.llvm.org/F2073104) >>>> > >>>> > If we do not consider the ref graph, then it is possible for SCC >>>> {S,T} to be >>>> >>>> I'm not sure why you wouldn't consider the ref graph? I think the >>>> general idea is to visit RefSCCs in bottom up order, and when visiting >>>> a RefSCC, visiting the SCC's inside the RefSCC in bottom up order. >>>> >>>> So in your example, given the edges you've shown, we will visit {X,Y} >>>> before visiting {S,T}. >>>> >>>> > A more complicated case is when SCC {S,T} and SCC {X,Y} both call >>>> into each >>>> > other via function pointers. So eventually after devirtualizing the >>>> calls in >>>> > both directions there will be a single SCC {S,T,X,Y}. >>>> > >>>> > digraph G { >>>> > A -> B; B -> A; // SCC {A,B} >>>> > S -> T; T -> S; // SCC {S,T} >>>> > X -> Y; Y -> X; // SCC {X,Y} >>>> > >>>> > B -> X; >>>> > B -> S; >>>> > T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC >>>> > {S,T}",constraint=false,style=dashed] >>>> > X -> S [label="Ref edge that is devirtualized\nwhen visiting SCC >>>> > {X,Y}",constraint=false,style=dashed] >>>> > } >>>> > >>>> > (rendering at: http://reviews.llvm.org/F2073479) >>>> > >>>> > Due to the cyclic dependence there is no SCC visitation order that can >>>> > directly provide the invariant above. Indeed, the problem of >>>> maintaining the >>>> >>>> I think the workflow in the above will (roughly) be: >>>> >>>> Visit the RefSCC {X,Y,S,T} >>>> >>> >>> Are we sure RefSCC has ref edges between {X, Y} and {S, T} in this >>> case? I may miss the code handling it. >>> >> >> The ref graph is conservative and so it would have the appropriate edges. >> >> https://github.com/llvm-project/llvm-project/blob/master/llvm/lib/Analysis/LazyCallGraph.cpp#L90 >> > > > That is where the confusion is -- the findReferences's function body only > handles constant operands which may be function addresses. Did I miss > something obvious? >It is somewhat subtle. There are 3 potential meanings of "call graph" in this thread: 1. The graph of *direct calls* in the current module. (this is mutated during optimization) 2. A supergraph of 1., conservatively chosen such 1. remains a subgraph under arbitrary semantics-preserving function transformations (note: 2. and 1. must be updated in sync during deletion of functions). 3. The conservative graph representing all edges which may exist *at runtime*. LazyCallGraph models 1. (the "call graph") and 2. (the "ref graph"). It does not model 3. The search for constants in findReferences guarantees that we find (a conserative superset of) all call destinations addresses that transformations may add direct calls (and hence update 1.). The existing CallGraph data structure (used by e.g. the old PM CGSCC visitation) only models 1.> Another point is that it may not be practical to model edges to indirect > targets. For virtual calls, without CHA, each virtual callsite will end up > referencing all potential address taken functions. >In this statement, you are thinking in terms of 3. Note that in both 1. and 2. the indirect calls are modeled as calling an external dummy node. This dummy node is *distinct* from a second external dummy node that calls all address-taken functions. (hence the indirect calls do not end up forming a RefSCC with all address taken functions). Note that `opt -dot-callgraph` can produce a graphviz file for the old PM callgraph. I'm not sure if we have one for LazyCallGraph (which has both ref graph and call graph); I'll post a patch adding one if not. -- Sean Silva> >> >> >>> >>> >>> >>>> Visit the SCC {X,Y} // arbitrary >>>> Optimize({X,Y}) >>>> // Now there's an edge to {S,T}, invalidate >>>> // the analyses cached for {X,Y} and visit {S,T} >>>> >>> >>> I am not sure if this makes sense. If dynamically, the call edge from >>> {X, Y} to {S, T} does exist, but not discovered by the analysis, then the >>> cached {X, Y} will still be invalid, but who is going to invalidate it? >>> >> >> I assume that if dynamically there was a call from {X,Y} to {S,T}, then >> the analysis would have observed an indirect call and would have behaved >> conservatively. >> > > See above, I did not see how indirect call is handled. Also if the result > for {X, Y} is conservatively correct before the direct call edge is > discovered, why bother invalidating its analysis when the call edge is > exposed? > > David > > >> >> -- Sean Silva >> >> >>> >>> David >>> >>> >>> >>> >>> >>>> Visit the SCC {S,T} >>>> Optimize({S,T}) >>>> // Now {X,Y,S,T} collapses to form a single SCC >>>> Visit the SCC {S,T,X,Y} >>>> Optimize({S,T,X,Y}) >>>> >>>> The difficult bit is to make the inner "// Now.*" bits work well. >>>> >>>> -- Sanjoy >>>> >>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/9338bceb/attachment-0001.html>
Xinliang David Li via llvm-dev
2016-Jun-17 07:10 UTC
[llvm-dev] Intended behavior of CGSCC pass manager.
On Thu, Jun 16, 2016 at 11:51 PM, Sean Silva <chisophugis at gmail.com> wrote:> > > On Thu, Jun 16, 2016 at 11:07 PM, Xinliang David Li <davidxl at google.com> > wrote: > >> >> >> On Thu, Jun 16, 2016 at 10:47 PM, Sean Silva <chisophugis at gmail.com> >> wrote: >> >>> >>> >>> On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at google.com> >>> wrote: >>> >>>> >>>> >>>> On Thu, Jun 16, 2016 at 11:12 AM, Sanjoy Das < >>>> sanjoy at playingwithpointers.com> wrote: >>>> >>>>> Hi Sean, >>>>> >>>>> On Thu, Jun 16, 2016 at 4:48 AM, Sean Silva via llvm-dev >>>>> <llvm-dev at lists.llvm.org> wrote: >>>>> > One question is what invariants we want to provide for the >>>>> visitation. >>>>> > >>>>> > For example, should a CGSCC pass be able to assume that all "child" >>>>> SCC's >>>>> > (SCC's it can reach via direct calls emanating from the SCC being >>>>> visited) >>>>> > have already been visited? Currently I don't think it can, and IIRC >>>>> from the >>>>> > discussion at the social this is one thing that Chandler is hoping >>>>> to fix. >>>>> > The "ref edge" notion in LazyCallGraph ensures that we cannot create >>>>> a call >>>>> > edge (devirtualizing a ref edge) that will point at an SCC that has >>>>> not yet >>>>> > been visited. >>>>> > >>>>> > E.g. consider this graph: >>>>> > >>>>> > digraph G { >>>>> > A -> B; B -> A; // SCC {A,B} >>>>> > S -> T; T -> S; // SCC {S,T} >>>>> > X -> Y; Y -> X; // SCC {X,Y} >>>>> > >>>>> > B -> X; >>>>> > B -> S; >>>>> > T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC >>>>> > {S,T}",constraint=false,style=dashed] >>>>> > } >>>>> > >>>>> > (can visualize conveniently at http://www.webgraphviz.com/ or I >>>>> have put an >>>>> > image at http://reviews.llvm.org/F2073104) >>>>> > >>>>> > If we do not consider the ref graph, then it is possible for SCC >>>>> {S,T} to be >>>>> >>>>> I'm not sure why you wouldn't consider the ref graph? I think the >>>>> general idea is to visit RefSCCs in bottom up order, and when visiting >>>>> a RefSCC, visiting the SCC's inside the RefSCC in bottom up order. >>>>> >>>>> So in your example, given the edges you've shown, we will visit {X,Y} >>>>> before visiting {S,T}. >>>>> >>>>> > A more complicated case is when SCC {S,T} and SCC {X,Y} both call >>>>> into each >>>>> > other via function pointers. So eventually after devirtualizing the >>>>> calls in >>>>> > both directions there will be a single SCC {S,T,X,Y}. >>>>> > >>>>> > digraph G { >>>>> > A -> B; B -> A; // SCC {A,B} >>>>> > S -> T; T -> S; // SCC {S,T} >>>>> > X -> Y; Y -> X; // SCC {X,Y} >>>>> > >>>>> > B -> X; >>>>> > B -> S; >>>>> > T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC >>>>> > {S,T}",constraint=false,style=dashed] >>>>> > X -> S [label="Ref edge that is devirtualized\nwhen visiting SCC >>>>> > {X,Y}",constraint=false,style=dashed] >>>>> > } >>>>> > >>>>> > (rendering at: http://reviews.llvm.org/F2073479) >>>>> > >>>>> > Due to the cyclic dependence there is no SCC visitation order that >>>>> can >>>>> > directly provide the invariant above. Indeed, the problem of >>>>> maintaining the >>>>> >>>>> I think the workflow in the above will (roughly) be: >>>>> >>>>> Visit the RefSCC {X,Y,S,T} >>>>> >>>> >>>> Are we sure RefSCC has ref edges between {X, Y} and {S, T} in this >>>> case? I may miss the code handling it. >>>> >>> >>> The ref graph is conservative and so it would have the appropriate edges. >>> >>> https://github.com/llvm-project/llvm-project/blob/master/llvm/lib/Analysis/LazyCallGraph.cpp#L90 >>> >> >> >> That is where the confusion is -- the findReferences's function body only >> handles constant operands which may be function addresses. Did I miss >> something obvious? >> > > It is somewhat subtle. There are 3 potential meanings of "call graph" in > this thread: > 1. The graph of *direct calls* in the current module. (this is mutated > during optimization) > 2. A supergraph of 1., conservatively chosen such 1. remains a subgraph > under arbitrary semantics-preserving function transformations (note: 2. and > 1. must be updated in sync during deletion of functions). > 3. The conservative graph representing all edges which may exist *at > runtime*. > > LazyCallGraph models 1. (the "call graph") and 2. (the "ref graph"). It > does not model 3. > The search for constants in findReferences guarantees that we find (a > conserative superset of) all call destinations addresses that > transformations may add direct calls (and hence update 1.). > > The existing CallGraph data structure (used by e.g. the old PM CGSCC > visitation) only models 1. > > > >> Another point is that it may not be practical to model edges to >> indirect targets. For virtual calls, without CHA, each virtual callsite >> will end up referencing all potential address taken functions. >> > > In this statement, you are thinking in terms of 3. > Note that in both 1. and 2. the indirect calls are modeled as calling an > external dummy node. This dummy node is *distinct* from a second external > dummy node that calls all address-taken functions. (hence the indirect > calls do not end up forming a RefSCC with all address taken functions). >For C++ programs, most ref edges are probably from ctors and dtors that reference vtable -- they will have large fan-out of ref edges to virtual member functions they are unlikely to call. In other words, such ref edges mostly do not represent real caller->callee relationship, so I wonder what is the advantage of forming refSCC from SCCs? David> Note that `opt -dot-callgraph` can produce a graphviz file for the old PM > callgraph. I'm not sure if we have one for LazyCallGraph (which has both > ref graph and call graph); I'll post a patch adding one if not. > > -- Sean Silva > > > >> >>> >>> >>>> >>>> >>>> >>>>> Visit the SCC {X,Y} // arbitrary >>>>> Optimize({X,Y}) >>>>> // Now there's an edge to {S,T}, invalidate >>>>> // the analyses cached for {X,Y} and visit {S,T} >>>>> >>>> >>>> I am not sure if this makes sense. If dynamically, the call edge from >>>> {X, Y} to {S, T} does exist, but not discovered by the analysis, then the >>>> cached {X, Y} will still be invalid, but who is going to invalidate it? >>>> >>> >>> I assume that if dynamically there was a call from {X,Y} to {S,T}, then >>> the analysis would have observed an indirect call and would have behaved >>> conservatively. >>> >> >> See above, I did not see how indirect call is handled. Also if the result >> for {X, Y} is conservatively correct before the direct call edge is >> discovered, why bother invalidating its analysis when the call edge is >> exposed? >> >> David >> >> >>> >>> -- Sean Silva >>> >>> >>>> >>>> David >>>> >>>> >>>> >>>> >>>> >>>>> Visit the SCC {S,T} >>>>> Optimize({S,T}) >>>>> // Now {X,Y,S,T} collapses to form a single SCC >>>>> Visit the SCC {S,T,X,Y} >>>>> Optimize({S,T,X,Y}) >>>>> >>>>> The difficult bit is to make the inner "// Now.*" bits work well. >>>>> >>>>> -- Sanjoy >>>>> >>>> >>>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160617/17ad698b/attachment.html>