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

[Xinliang David Li via llvm-dev]

> 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>