llvm dev - Jun 2016 - Intended behavior of CGSCC pass manager.

On Wed, Jun 8, 2016 at 3:10 PM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
>
> On Jun 8, 2016, at 2:54 PM, Sean Silva <chisophugis at gmail.com>
wrote:
>
>
>
> On Wed, Jun 8, 2016 at 9:39 AM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>
>>
>>
>> On Wed, Jun 8, 2016 at 4:19 AM, Sean Silva <chisophugis at
gmail.com> wrote:
>>
>>> Hi Chandler, Philip, Mehdi, (and llvm-dev,)
>>>
>>> (this is partially a summary of some discussions that happened at
the
>>> last LLVM bay area social, and partially a discussion about the
direction
>>> of the CGSCC pass manager)
>>>
>>>
>>> A the last LLVM social we discussed the progress on the CGSCC pass
>>> manager. It seems like Chandler has a CGSCC pass manager working,
but it is
>>> still unresolved exactly which semantics we want (more about this
below)
>>> that are reasonably implementable.
>>>
>>> AFAICT, there has been no public discussion about what exact
semantics
>>> we ultimately want to have. We should figure that out.
>>>
>>> The main difficulty which Chandler described is the apparently
quite
>>> complex logic surrounding needing to run function passes nested
within an
>>> SCC pass manager, while providing some guarantees about exactly
what order
>>> the function passes are run. The existing CGSCC pass manager just
punts on
>>> some of the problems that arise (look in
CGPassManager::runOnModule,
>>> CGPassManager::RunAllPassesOnSCC, and CGPassManager::RunPassOnSCC
in
>>> llvm/lib/Analysis/CallGraphSCCPass.cpp), and these are the problems
that
>>> Chandler has been trying to solve.
>>>
>>> (
>>> Why is this "function passes inside CGSCC passes" stuff
interesting?
>>> Because LLVM can do inlining on an SCC (often just a single
function) and
>>> then run function passes to simplify the function(s) in the SCC
before it
>>> tries to inline into a parent SCC. (the SCC visitation order is
post-order)
>>> For example, we may inline a bunch of code, but after inlining we
can
>>> tremendously simplify the function, and we want to do so before
considering
>>> this function for inlining into its callers so that we get an
accurate
>>> evaluation of the inline cost.
>>> Based on what Chandler said, it seems that LLVM is fairly unique in
this
>>> regard and other compilers don't do this (which is why we
can't just look
>>> at how other compilers solve this problem; they don't have this
problem
>>> (maybe they should? or maybe we shouldn't?)). For example, he
described
>>> that GCC uses different inlining "phases"; e.g. it does
early inlining on
>>> the entire module, then does simplifications on the entire module,
then
>>> does late inlining on the entire module; so it is not able to
incrementally
>>> simplify as it inlines like LLVM does.
>>> )
>>>
>>> As background for what is below, the LazyCallGraph tracks two
graphs:
>>> the "call graph" and the "ref graph".
>>> Conceptually, the call graph is the graph of direct calls, where
>>> indirect calls and calls to external functions do not appear (or
are
>>> connected to dummy nodes). The ref graph is basically the graph of
all
>>> functions transitively accessible based on the
globals/constants/etc.
>>> referenced by a function (e.g. if a function `foo` references a
vtable that
>>> is defined in the module, there is an edge in the ref graph from
`foo` to
>>> every function in the vtable).
>>> The call graph is a strict subset of the ref graph.
>>>
>>> Chandler described that he had a major breakthrough in that the
CGSCC
>>> pass manager only had to deal with 3 classes of modifications that
can
>>> occur:
>>> - a pass may e.g. propagate a load of a function pointer into an
>>> indirect call, turning it into an direct call. This requires adding
an edge
>>> in the CG but not in the ref graph.
>>> - a pass may take a direct call and turn it into an indirect call.
This
>>> requires removing an edge from the CG, but not in the ref graph.
>>> - a pass may delete a direct call. This removes an edge in the CG
and
>>> also in the ref graph.
>>>
>>> From the perspective of the CGSCC pass manager, these operations
can
>>> affect the SCC structure. Adding an edge might merge SCC's and
deleting an
>>> edge might split SCC's. Chandler mentioned that apparently the
issues of
>>> splitting and merging SCC's within the current infrastructure
are actually
>>> quite challenging and lead to e.g. iterator invalidation issues,
and that
>>> is what he is working on.
>>>
>>> (
>>> The ref graph is important to guide the overall SCC visitation
order
>>> because it basically represents "the largest graph that the CG
may turn
>>> into due to our static analysis of this module". I.e. no
transformation we
>>> can statically make in the CGSCC passes can ever cause us to need
to merge
>>> SCC's in the ref graph.
>>> )
>>>
>>>
>>>
>>> I have a couple overall questions/concerns:
>>>
>>>
>>> 1. The ref graph can easily go quadratic. E.g.
>>>
>>> typedef void (*fp)();
>>> fp funcs[] = {
>>>   &foo1,
>>>   &foo2,
>>>   ...
>>>   &fooN
>>> }
>>> void foo1() { funcs[something](); }
>>> void foo2() { funcs[something](); }
>>> ...
>>> void fooN() { funcs[something](); }
>>>
>>> One real-world case where this might come about is in the presence
of
>>> vtables.
>>>
>>> The existing CGSCC pass manager does not have this issue AFAIK
because
>>> it does not consider the ref graph.
>>>
>>> Does anybody have any info/experience about how densely connected
the
>>> ref graph can get in programs that might reasonably be fed to the
compiler?
>>>
>>
>>
>> I can state that almost all call graphs of compilers include edges for
>> indirect calls and external functions, so they are already quadratic in
>> this sense.
>>
>> if what you state is correct, and we don't have a conservatively
correct
>> call graph, that would be ... interesting.
>>
>
> Mehdi clarified downthread the situation (at least for me).
>
> Now that I look more closely at the comments in
>
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/LazyCallGraph.h
>  it intentionally does not model a call graph in this sense. I.e.
> - in a traditional CG, an edge means something like "at runtime there
may
> be a call from A->B"
> - in the LazyCallGraph an edge (a "ref edge" as it calls it)
represents
> something like "during optimization of this module, we may discover
the
> existence of a direct call from A->B". There is also a
distinguished
> subgraph of the ref graph (which I think LazyCallGraph calls just the
"call
> graph") which represents the actual direct calls that are present in
the
> module currently.
>
> The comments in LazyCallGraph.h are quite good, but the existing
> CallGraph.h doesn't seem to touch on this up front in its comments in
quite
> the same way, but it does at least say that it models with two external
> nodes like Mehdi mentioned:
>
>
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/CallGraph.h#L30
> So its edges don't represent "at runtime there may be a call from
A->B".
> But since it doesn't maintain a "ref graph" I'm not sure
what the edges
> exactly represent.
>
>
>
> I thought of it as the edges are "there is a direct call from A ->
B".
> Which is a subset of "at runtime there may be a call from
A->B".
>
> I think that with all this discussion, it is important to distinguish that
> (I think) there is no "correctness" issue at stance (we won't
miscompile
> anything)
>
This is a good point worth explicitly noting (and hopefully there are in
fact no passes relying on it to mean "at runtime there may be a call from
A->B").

> , but there may be missing optimization in some cases. I think the current
> scheme catches most cases and when it does not we are just missing
> potential inlining. The question may be how much (more) cases we really
> need to catch with the new pass manager?
>
I think this only affects inlining of mutually recursive functions. Most
functions are not mutually recursive [citation needed] so I'm not too
worried.
(The main performance-critical case that I can think of using mutual
recursion would be parsers).

-- Sean Silva


> And could a first implementation not catch everything and be improved
> incrementally? This comes back somehow to what Hal was mentioning
> (reproducing the current behavior before improving it).
>
> --
> Mehdi
>
>
>
>
>
>
>
>> The solution to most issues (large sccs, etc) that exist here that most
>> other compilers take is to try to make the call graph more precise, not
to
>> avoid indirect/external calls in the call graph.
>>
>> In turn, this means the solution often take is to not have two graphs
at
>> all.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160608/793d0aff/attachment.html>

Sent from my iPhone
> On Jun 8, 2016, at 4:48 PM, Sean Silva <chisophugis at gmail.com>
wrote:
> 
> 
> 
>> On Wed, Jun 8, 2016 at 3:10 PM, Mehdi Amini <mehdi.amini at
apple.com> wrote:
>> 
>>> On Jun 8, 2016, at 2:54 PM, Sean Silva <chisophugis at
gmail.com> wrote:
>>> 
>>> 
>>> 
>>> On Wed, Jun 8, 2016 at 9:39 AM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>>>> 
>>>> 
>>>>> On Wed, Jun 8, 2016 at 4:19 AM, Sean Silva <chisophugis
at gmail.com> wrote:
>>>>> Hi Chandler, Philip, Mehdi, (and llvm-dev,)
>>>>> 
>>>>> (this is partially a summary of some discussions that
happened at the last LLVM bay area social, and partially a discussion about the
direction of the CGSCC pass manager)
>>>>> 
>>>>> 
>>>>> A the last LLVM social we discussed the progress on the
CGSCC pass manager. It seems like Chandler has a CGSCC pass manager working, but
it is still unresolved exactly which semantics we want (more about this below)
that are reasonably implementable.
>>>>> 
>>>>> AFAICT, there has been no public discussion about what
exact semantics we ultimately want to have. We should figure that out.
>>>>> 
>>>>> The main difficulty which Chandler described is the
apparently quite complex logic surrounding needing to run function passes nested
within an SCC pass manager, while providing some guarantees about exactly what
order the function passes are run. The existing CGSCC pass manager just punts on
some of the problems that arise (look in CGPassManager::runOnModule,
CGPassManager::RunAllPassesOnSCC, and CGPassManager::RunPassOnSCC in
llvm/lib/Analysis/CallGraphSCCPass.cpp), and these are the problems that
Chandler has been trying to solve.
>>>>> 
>>>>> (
>>>>> Why is this "function passes inside CGSCC passes"
stuff interesting? Because LLVM can do inlining on an SCC (often just a single
function) and then run function passes to simplify the function(s) in the SCC
before it tries to inline into a parent SCC. (the SCC visitation order is
post-order)
>>>>> For example, we may inline a bunch of code, but after
inlining we can tremendously simplify the function, and we want to do so before
considering this function for inlining into its callers so that we get an
accurate evaluation of the inline cost.
>>>>> Based on what Chandler said, it seems that LLVM is fairly
unique in this regard and other compilers don't do this (which is why we
can't just look at how other compilers solve this problem; they don't
have this problem (maybe they should? or maybe we shouldn't?)). For example,
he described that GCC uses different inlining "phases"; e.g. it does
early inlining on the entire module, then does simplifications on the entire
module, then does late inlining on the entire module; so it is not able to
incrementally simplify as it inlines like LLVM does.
>>>>> )
>>>>> 
>>>>> As background for what is below, the LazyCallGraph tracks
two graphs: the "call graph" and the "ref graph".
>>>>> Conceptually, the call graph is the graph of direct calls,
where indirect calls and calls to external functions do not appear (or are
connected to dummy nodes). The ref graph is basically the graph of all functions
transitively accessible based on the globals/constants/etc. referenced by a
function (e.g. if a function `foo` references a vtable that is defined in the
module, there is an edge in the ref graph from `foo` to every function in the
vtable).
>>>>> The call graph is a strict subset of the ref graph.
>>>>> 
>>>>> Chandler described that he had a major breakthrough in that
the CGSCC pass manager only had to deal with 3 classes of modifications that can
occur:
>>>>> - a pass may e.g. propagate a load of a function pointer
into an indirect call, turning it into an direct call. This requires adding an
edge in the CG but not in the ref graph.
>>>>> - a pass may take a direct call and turn it into an
indirect call. This requires removing an edge from the CG, but not in the ref
graph.
>>>>> - a pass may delete a direct call. This removes an edge in
the CG and also in the ref graph.
>>>>> 
>>>>> From the perspective of the CGSCC pass manager, these
operations can affect the SCC structure. Adding an edge might merge SCC's
and deleting an edge might split SCC's. Chandler mentioned that apparently
the issues of splitting and merging SCC's within the current infrastructure
are actually quite challenging and lead to e.g. iterator invalidation issues,
and that is what he is working on.
>>>>> 
>>>>> (
>>>>> The ref graph is important to guide the overall SCC
visitation order because it basically represents "the largest graph that
the CG may turn into due to our static analysis of this module". I.e. no
transformation we can statically make in the CGSCC passes can ever cause us to
need to merge SCC's in the ref graph.
>>>>> )
>>>>> 
>>>>> 
>>>>> 
>>>>> I have a couple overall questions/concerns:
>>>>> 
>>>>> 
>>>>> 1. The ref graph can easily go quadratic. E.g.
>>>>> 
>>>>> typedef void (*fp)();
>>>>> fp funcs[] = {
>>>>>   &foo1,
>>>>>   &foo2,
>>>>>   ...
>>>>>   &fooN
>>>>> }
>>>>> void foo1() { funcs[something](); }
>>>>> void foo2() { funcs[something](); }
>>>>> ...
>>>>> void fooN() { funcs[something](); }
>>>>> 
>>>>> One real-world case where this might come about is in the
presence of vtables.
>>>>> 
>>>>> The existing CGSCC pass manager does not have this issue
AFAIK because it does not consider the ref graph.
>>>>> 
>>>>> Does anybody have any info/experience about how densely
connected the ref graph can get in programs that might reasonably be fed to the
compiler?
>>>> 
>>>> 
>>>> I can state that almost all call graphs of compilers include
edges for indirect calls and external functions, so they are already quadratic
in this sense.
>>>> 
>>>> if what you state is correct, and we don't have a
conservatively correct call graph, that would be ... interesting.
>>> 
>>> Mehdi clarified downthread the situation (at least for me).
>>> 
>>> Now that I look more closely at the comments in
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/LazyCallGraph.h
it intentionally does not model a call graph in this sense. I.e.
>>> - in a traditional CG, an edge means something like "at
runtime there may be a call from A->B"
>>> - in the LazyCallGraph an edge (a "ref edge" as it calls
it) represents something like "during optimization of this module, we may
discover the existence of a direct call from A->B". There is also a
distinguished subgraph of the ref graph (which I think LazyCallGraph calls just
the "call graph") which represents the actual direct calls that are
present in the module currently.
>>> 
>>> The comments in LazyCallGraph.h are quite good, but the existing
CallGraph.h doesn't seem to touch on this up front in its comments in quite
the same way, but it does at least say that it models with two external nodes
like Mehdi mentioned:
>>>
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/CallGraph.h#L30
>>> So its edges don't represent "at runtime there may be a
call from A->B". But since it doesn't maintain a "ref
graph" I'm not sure what the edges exactly represent.
>> 
>> 
>> I thought of it as the edges are "there is a direct call from A
-> B". Which is a subset of "at runtime there may be a call from
A->B".
>> 
>> I think that with all this discussion, it is important to distinguish
that (I think) there is no "correctness" issue at stance (we won't
miscompile anything)
> 
> This is a good point worth explicitly noting (and hopefully there are in
fact no passes relying on it to mean "at runtime there may be a call from
A->B").
>  
>> , but there may be missing optimization in some cases. I think the
current scheme catches most cases and when it does not we are just missing
potential inlining. The question may be how much (more) cases we really need to
catch with the new pass manager?
> 
> I think this only affects inlining of mutually recursive functions. Most
functions are not mutually recursive [citation needed] so I'm not too
worried.
> (The main performance-critical case that I can think of using mutual
recursion would be parsers).
What about devirtualization? Or even simply cases where an indirect call can be
folded to a direct call?
Now you are processing the caller without having processed the callee. 
I think the current way of handling this is to add the new callee to the SCC
(even though it is not actually participating into it) and continue to iterate
on this SCC. Sounds like a hack, but seems to works in practice.

Mehdi


> 
> -- Sean Silva
> 
>  
>> And could a first implementation not catch everything and be improved
incrementally? This comes back somehow to what Hal was mentioning (reproducing
the current behavior before improving it).
>> 
>> -- 
>> Mehdi
>> 
>> 
>> 
>> 
>>> 
>>>  
>>>> The solution to most issues (large sccs, etc) that exist here
that most other compilers take is to try to make the call graph more precise,
not to avoid indirect/external calls in the call graph.
>>>> 
>>>> In turn, this means the solution often take is to not have two
graphs at all.
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160608/c4ce8bd7/attachment.html>

On Wed, Jun 8, 2016 at 5:11 PM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
>
>
> Sent from my iPhone
>
> On Jun 8, 2016, at 4:48 PM, Sean Silva <chisophugis at gmail.com>
wrote:
>
>
>
> On Wed, Jun 8, 2016 at 3:10 PM, Mehdi Amini <mehdi.amini at
apple.com> wrote:
>
>>
>> On Jun 8, 2016, at 2:54 PM, Sean Silva <chisophugis at gmail.com>
wrote:
>>
>>
>>
>> On Wed, Jun 8, 2016 at 9:39 AM, Daniel Berlin <dberlin at
dberlin.org>
>> wrote:
>>
>>>
>>>
>>> On Wed, Jun 8, 2016 at 4:19 AM, Sean Silva <chisophugis at
gmail.com>
>>> wrote:
>>>
>>>> Hi Chandler, Philip, Mehdi, (and llvm-dev,)
>>>>
>>>> (this is partially a summary of some discussions that happened
at the
>>>> last LLVM bay area social, and partially a discussion about the
direction
>>>> of the CGSCC pass manager)
>>>>
>>>>
>>>> A the last LLVM social we discussed the progress on the CGSCC
pass
>>>> manager. It seems like Chandler has a CGSCC pass manager
working, but it is
>>>> still unresolved exactly which semantics we want (more about
this below)
>>>> that are reasonably implementable.
>>>>
>>>> AFAICT, there has been no public discussion about what exact
semantics
>>>> we ultimately want to have. We should figure that out.
>>>>
>>>> The main difficulty which Chandler described is the apparently
quite
>>>> complex logic surrounding needing to run function passes nested
within an
>>>> SCC pass manager, while providing some guarantees about exactly
what order
>>>> the function passes are run. The existing CGSCC pass manager
just punts on
>>>> some of the problems that arise (look in
CGPassManager::runOnModule,
>>>> CGPassManager::RunAllPassesOnSCC, and
CGPassManager::RunPassOnSCC in
>>>> llvm/lib/Analysis/CallGraphSCCPass.cpp), and these are the
problems that
>>>> Chandler has been trying to solve.
>>>>
>>>> (
>>>> Why is this "function passes inside CGSCC passes"
stuff interesting?
>>>> Because LLVM can do inlining on an SCC (often just a single
function) and
>>>> then run function passes to simplify the function(s) in the SCC
before it
>>>> tries to inline into a parent SCC. (the SCC visitation order is
post-order)
>>>> For example, we may inline a bunch of code, but after inlining
we can
>>>> tremendously simplify the function, and we want to do so before
considering
>>>> this function for inlining into its callers so that we get an
accurate
>>>> evaluation of the inline cost.
>>>> Based on what Chandler said, it seems that LLVM is fairly
unique in
>>>> this regard and other compilers don't do this (which is why
we can't just
>>>> look at how other compilers solve this problem; they don't
have this
>>>> problem (maybe they should? or maybe we shouldn't?)). For
example, he
>>>> described that GCC uses different inlining "phases";
e.g. it does early
>>>> inlining on the entire module, then does simplifications on the
entire
>>>> module, then does late inlining on the entire module; so it is
not able to
>>>> incrementally simplify as it inlines like LLVM does.
>>>> )
>>>>
>>>> As background for what is below, the LazyCallGraph tracks two
graphs:
>>>> the "call graph" and the "ref graph".
>>>> Conceptually, the call graph is the graph of direct calls,
where
>>>> indirect calls and calls to external functions do not appear
(or are
>>>> connected to dummy nodes). The ref graph is basically the graph
of all
>>>> functions transitively accessible based on the
globals/constants/etc.
>>>> referenced by a function (e.g. if a function `foo` references a
vtable that
>>>> is defined in the module, there is an edge in the ref graph
from `foo` to
>>>> every function in the vtable).
>>>> The call graph is a strict subset of the ref graph.
>>>>
>>>> Chandler described that he had a major breakthrough in that the
CGSCC
>>>> pass manager only had to deal with 3 classes of modifications
that can
>>>> occur:
>>>> - a pass may e.g. propagate a load of a function pointer into
an
>>>> indirect call, turning it into an direct call. This requires
adding an edge
>>>> in the CG but not in the ref graph.
>>>> - a pass may take a direct call and turn it into an indirect
call. This
>>>> requires removing an edge from the CG, but not in the ref
graph.
>>>> - a pass may delete a direct call. This removes an edge in the
CG and
>>>> also in the ref graph.
>>>>
>>>> From the perspective of the CGSCC pass manager, these
operations can
>>>> affect the SCC structure. Adding an edge might merge SCC's
and deleting an
>>>> edge might split SCC's. Chandler mentioned that apparently
the issues of
>>>> splitting and merging SCC's within the current
infrastructure are actually
>>>> quite challenging and lead to e.g. iterator invalidation
issues, and that
>>>> is what he is working on.
>>>>
>>>> (
>>>> The ref graph is important to guide the overall SCC visitation
order
>>>> because it basically represents "the largest graph that
the CG may turn
>>>> into due to our static analysis of this module". I.e. no
transformation we
>>>> can statically make in the CGSCC passes can ever cause us to
need to merge
>>>> SCC's in the ref graph.
>>>> )
>>>>
>>>>
>>>>
>>>> I have a couple overall questions/concerns:
>>>>
>>>>
>>>> 1. The ref graph can easily go quadratic. E.g.
>>>>
>>>> typedef void (*fp)();
>>>> fp funcs[] = {
>>>>   &foo1,
>>>>   &foo2,
>>>>   ...
>>>>   &fooN
>>>> }
>>>> void foo1() { funcs[something](); }
>>>> void foo2() { funcs[something](); }
>>>> ...
>>>> void fooN() { funcs[something](); }
>>>>
>>>> One real-world case where this might come about is in the
presence of
>>>> vtables.
>>>>
>>>> The existing CGSCC pass manager does not have this issue AFAIK
because
>>>> it does not consider the ref graph.
>>>>
>>>> Does anybody have any info/experience about how densely
connected the
>>>> ref graph can get in programs that might reasonably be fed to
the compiler?
>>>>
>>>
>>>
>>> I can state that almost all call graphs of compilers include edges
for
>>> indirect calls and external functions, so they are already
quadratic in
>>> this sense.
>>>
>>> if what you state is correct, and we don't have a
conservatively correct
>>> call graph, that would be ... interesting.
>>>
>>
>> Mehdi clarified downthread the situation (at least for me).
>>
>> Now that I look more closely at the comments in
>>
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/LazyCallGraph.h
>>  it intentionally does not model a call graph in this sense. I.e.
>> - in a traditional CG, an edge means something like "at runtime
there may
>> be a call from A->B"
>> - in the LazyCallGraph an edge (a "ref edge" as it calls it)
represents
>> something like "during optimization of this module, we may
discover the
>> existence of a direct call from A->B". There is also a
distinguished
>> subgraph of the ref graph (which I think LazyCallGraph calls just the
"call
>> graph") which represents the actual direct calls that are present
in the
>> module currently.
>>
>> The comments in LazyCallGraph.h are quite good, but the existing
>> CallGraph.h doesn't seem to touch on this up front in its comments
in quite
>> the same way, but it does at least say that it models with two external
>> nodes like Mehdi mentioned:
>>
>>
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/CallGraph.h#L30
>> So its edges don't represent "at runtime there may be a call
from A->B".
>> But since it doesn't maintain a "ref graph" I'm not
sure what the edges
>> exactly represent.
>>
>>
>>
>> I thought of it as the edges are "there is a direct call from A
-> B".
>> Which is a subset of "at runtime there may be a call from
A->B".
>>
>> I think that with all this discussion, it is important to distinguish
>> that (I think) there is no "correctness" issue at stance (we
won't
>> miscompile anything)
>>
>
> This is a good point worth explicitly noting (and hopefully there are in
> fact no passes relying on it to mean "at runtime there may be a call
from
> A->B").
>
>
>> , but there may be missing optimization in some cases. I think the
>> current scheme catches most cases and when it does not we are just
missing
>> potential inlining. The question may be how much (more) cases we really
>> need to catch with the new pass manager?
>>
>
> I think this only affects inlining of mutually recursive functions. Most
> functions are not mutually recursive [citation needed] so I'm not too
> worried.
> (The main performance-critical case that I can think of using mutual
> recursion would be parsers).
>
>
> What about devirtualization? Or even simply cases where an indirect call
> can be folded to a direct call?
> Now you are processing the caller without having processed the callee.
> I think the current way of handling this is to add the new callee to the
> SCC (even though it is not actually participating into it) and continue to
> iterate on this SCC. Sounds like a hack, but seems to works in practice.
>
Ah, yeah. Having a more principled solution to this is one of the main
motivations Chandler mentioned. I forgot about this when writing the OP.
I think this is precisely the thing that the "ref graph" solves. I.e.
you
are constrained by the ref graph SCC's and so this kind of unordered
visition cannot occur (pending closer study of Sanjoy's counterexamples).

-- Sean Silva

>
> Mehdi
>
>
>
>
> -- Sean Silva
>
>
>
>> And could a first implementation not catch everything and be improved
>> incrementally? This comes back somehow to what Hal was mentioning
>> (reproducing the current behavior before improving it).
>>
>> --
>> Mehdi
>>
>>
>>
>>
>>
>>
>>
>>> The solution to most issues (large sccs, etc) that exist here that
most
>>> other compilers take is to try to make the call graph more precise,
not to
>>> avoid indirect/external calls in the call graph.
>>>
>>> In turn, this means the solution often take is to not have two
graphs at
>>> all.
>>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160608/395156b5/attachment.html>