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

Thu Jun 16 21:43:19 PDT 2016

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>