llvm dev - Jun 2017 - An issue with new PM's requirements on call graph changes

I have hit a fairly isolated practical issue deploying the new PM, but it
does point to a latent theoretical issues as well. I see various ways to
address it, but want feedback from others before moving forward.

The issue is that we can introduce out-of-thin-air calls to known library
functions (`SimplifyLibCalls`, etc). These can be introduced in function
passes (`InstCombine` in particular) and that seems highly desirable.

These all look like one of these cases:
1a) Introducing a new call to an LLVM intrinsic
1b) Replacing an existing call with a call to an LLVM intrinsic
2a) Introducing a new call to a declared library function (but not defined)
2b) Replacing an existing call with a call to a declared library function
3a) Introducing a new call to a defined library function
3b) Replacing an existing call with a call to a defined library function

Both #1 and #2 are easy to handle in reality. Intrinsics and declared
functions don't impact the PM's call graph because there is no need to
order the walk over them. But #3 is a real issue.

The only case I have found that actually hits #3 at all hits #3b when
building FORTIFY code with the new pass manager because after inlining we
do a lot of (really nice) optimizations on library calls to remove
unnecessary FORTIFY checks. But this is in *theory* a problem when LTO-ing
with libc. More likely it could be a problem when LTO-ing with a vector
math library.

So what do we do?

My initial idea: find all *defined* library functions in the module, and
every time we create a ref edge to one of them, synthesize a ref edge to
all of them. This should completely solve #3b above. But it doesn't really
address #3a at all.

Is that OK? It would be very convenient to say that if we want to introduce
truly novel and new calls to library functions, we should have an LLVM
intrinsic to model those routines.

But we actually have an example (I think) of #3a, introducing a call to a
library function out of the blue: memset_pattern. =/

The only way I see to reasonably handle #3a is to have *every* function
implicitly contain a reference edge to every defined library function in
the module. This is, needless to say, amazingly wasteful. Hence my email.
How important is this?

If we need to correctly handle this, I think I would probably implement
this by actually changing the *iteration* of reference edges in the graph
to just implicitly walk the list of defined library functions so that we
didn't burn any space on this. But it will make iteration of reference
edges slower and add a reasonable amount of complexity. So I'd like to hear
some other opinions before going down either of these roads.


Thanks,
-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/2223d43e/attachment.html>

Hi Chandler,

On Fri, Jun 30, 2017 at 1:02 AM, Chandler Carruth <chandlerc at gmail.com>
wrote:
> I have hit a fairly isolated practical issue deploying the new PM, but it
> does point to a latent theoretical issues as well. I see various ways to
> address it, but want feedback from others before moving forward.
>
> The issue is that we can introduce out-of-thin-air calls to known library
> functions (`SimplifyLibCalls`, etc). These can be introduced in function
> passes (`InstCombine` in particular) and that seems highly desirable.
>
> These all look like one of these cases:
> 1a) Introducing a new call to an LLVM intrinsic
> 1b) Replacing an existing call with a call to an LLVM intrinsic
> 2a) Introducing a new call to a declared library function (but not defined)
> 2b) Replacing an existing call with a call to a declared library function
> 3a) Introducing a new call to a defined library function
> 3b) Replacing an existing call with a call to a defined library function
An alternate way to model 3b is to say that if a call to X can be
replaced by a call to Y, X needs to have a ref edge to Y (even if X is
a declaration).  The list of these "hidden" ref edges will be provided
by TargetLibraryInfo (or something close).

3a seems logically equivalent to an outliner pass[0] followed by
function commoning to me, so I think we should ask ourselves what the
behavior of an outliner pass needs to be in the new RefSCC world.
Perhaps we're okay not doing 3a from function passes (just like we
would not allow outlining from function passes)?  This would involve
refactoring SimplifyLibCalls though, to create a variant that can only
be invoked from a CGSCC pass.

[0]: Assuming we //want// to apply the PM's post-order traversal rule
-- the rule is less beneficial for outlining though, since the
outlined function will probably be simplified already because we
carved it out of a function that has been simplified.

Thanks!
-- Sanjoy

On Fri, Jun 30, 2017 at 1:02 AM, Chandler Carruth via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I have hit a fairly isolated practical issue deploying the new PM, but it
> does point to a latent theoretical issues as well. I see various ways to
> address it, but want feedback from others before moving forward.
>
> The issue is that we can introduce out-of-thin-air calls to known library
> functions (`SimplifyLibCalls`, etc). These can be introduced in function
> passes (`InstCombine` in particular) and that seems highly desirable.
>
> These all look like one of these cases:
> 1a) Introducing a new call to an LLVM intrinsic
> 1b) Replacing an existing call with a call to an LLVM intrinsic
> 2a) Introducing a new call to a declared library function (but not defined)
> 2b) Replacing an existing call with a call to a declared library function
> 3a) Introducing a new call to a defined library function
> 3b) Replacing an existing call with a call to a defined library function
>
> Both #1 and #2 are easy to handle in reality. Intrinsics and declared
> functions don't impact the PM's call graph because there is no need
to
> order the walk over them. But #3 is a real issue.
>
> The only case I have found that actually hits #3 at all hits #3b when
> building FORTIFY code with the new pass manager because after inlining we
> do a lot of (really nice) optimizations on library calls to remove
> unnecessary FORTIFY checks. But this is in *theory* a problem when LTO-ing
> with libc. More likely it could be a problem when LTO-ing with a vector
> math library.
>
> So what do we do?
>
> My initial idea: find all *defined* library functions in the module, and
> every time we create a ref edge to one of them, synthesize a ref edge to
> all of them. This should completely solve #3b above. But it doesn't
really
> address #3a at all.
>
> Is that OK? It would be very convenient to say that if we want to
> introduce truly novel and new calls to library functions, we should have an
> LLVM intrinsic to model those routines.
>
That seems reasonable, though it would in theory block inlining of, say,
memset_pattern if we have a definition available when LTO'ing but that
seems acceptable (and we already live with similar restrictions with other
memory intrinsics anyway and I don't hear anyone complaining).

>
> But we actually have an example (I think) of #3a, introducing a call to a
> library function out of the blue: memset_pattern. =/
>
> The only way I see to reasonably handle #3a is to have *every* function
> implicitly contain a reference edge to every defined library function in
> the module. This is, needless to say, amazingly wasteful. Hence my email.
> How important is this?
>
This seems like the simplest and most natural solution overall. Can you get
some numbers on how wasteful it actually is? (and for the alternative
approach)

Even if it ends up not being that wasteful and worth doing just for
simplicity's sake, I do like the idea of "out-of-thin-air calls must be
intrinsics".

-- Sean Silva

>
> If we need to correctly handle this, I think I would probably implement
> this by actually changing the *iteration* of reference edges in the graph
> to just implicitly walk the list of defined library functions so that we
> didn't burn any space on this. But it will make iteration of reference
> edges slower and add a reasonable amount of complexity. So I'd like to
hear
> some other opinions before going down either of these roads.
>
>
> Thanks,
> -Chandler
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/a2c94e53/attachment.html>

On 06/30/2017 01:02 AM, Chandler Carruth via llvm-dev
wrote:
> I have hit a fairly isolated practical issue deploying the new PM, but 
> it does point to a latent theoretical issues as well. I see various 
> ways to address it, but want feedback from others before moving forward.
>
> The issue is that we can introduce out-of-thin-air calls to known 
> library functions (`SimplifyLibCalls`, etc). These can be introduced 
> in function passes (`InstCombine` in particular) and that seems highly 
> desirable.
>
> These all look like one of these cases:
> 1a) Introducing a new call to an LLVM intrinsic
> 1b) Replacing an existing call with a call to an LLVM intrinsic
> 2a) Introducing a new call to a declared library function (but not 
> defined)
> 2b) Replacing an existing call with a call to a declared library function
> 3a) Introducing a new call to a defined library function
> 3b) Replacing an existing call with a call to a defined library function
>
> Both #1 and #2 are easy to handle in reality. Intrinsics and declared 
> functions don't impact the PM's call graph because there is no need
to
> order the walk over them. But #3 is a real issue.
>
> The only case I have found that actually hits #3 at all hits #3b when 
> building FORTIFY code with the new pass manager because after inlining 
> we do a lot of (really nice) optimizations on library calls to remove 
> unnecessary FORTIFY checks. But this is in *theory* a problem when 
> LTO-ing with libc. More likely it could be a problem when LTO-ing with 
> a vector math library.
>
> So what do we do?
>
> My initial idea: find all *defined* library functions in the module, 
> and every time we create a ref edge to one of them, synthesize a ref 
> edge to all of them. This should completely solve #3b above. But it 
> doesn't really address #3a at all.
>
> Is that OK? It would be very convenient to say that if we want to 
> introduce truly novel and new calls to library functions, we should 
> have an LLVM intrinsic to model those routines.
>
> But we actually have an example (I think) of #3a, introducing a call 
> to a library function out of the blue: memset_pattern. =/
Out of curiosity, is this the only example we have?  In the context of 
https://reviews.llvm.org/D34885, I was thinking about whether it might 
make sense to have intrinsic form of memset_pattern anyways. If we did 
that, could we disallow such cases in practice?  On the other hand, it 
does seem less than desirable to prevent inlining of such cases when we 
do in fact have the implementation linked in.
>
> The only way I see to reasonably handle #3a is to have *every* 
> function implicitly contain a reference edge to every defined library 
> function in the module. This is, needless to say, amazingly wasteful. 
> Hence my email. How important is this?
>
> If we need to correctly handle this, I think I would probably 
> implement this by actually changing the *iteration* of reference edges 
> in the graph to just implicitly walk the list of defined library 
> functions so that we didn't burn any space on this. But it will make 
> iteration of reference edges slower and add a reasonable amount of 
> complexity. So I'd like to hear some other opinions before going down 
> either of these roads.
>
>
> Thanks,
> -Chandler
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170701/61892485/attachment.html>

On 06/30/2017 03:02 AM, Chandler Carruth wrote:
> I have hit a fairly isolated practical issue deploying the new PM, but 
> it does point to a latent theoretical issues as well. I see various 
> ways to address it, but want feedback from others before moving forward.
>
> The issue is that we can introduce out-of-thin-air calls to known 
> library functions (`SimplifyLibCalls`, etc). These can be introduced 
> in function passes (`InstCombine` in particular) and that seems highly 
> desirable.
>
> These all look like one of these cases:
> 1a) Introducing a new call to an LLVM intrinsic
> 1b) Replacing an existing call with a call to an LLVM intrinsic
> 2a) Introducing a new call to a declared library function (but not 
> defined)
> 2b) Replacing an existing call with a call to a declared library function
> 3a) Introducing a new call to a defined library function
> 3b) Replacing an existing call with a call to a defined library function
>
> Both #1 and #2 are easy to handle in reality. Intrinsics and declared 
> functions don't impact the PM's call graph because there is no need
to
> order the walk over them. But #3 is a real issue.
>
> The only case I have found that actually hits #3 at all hits #3b when 
> building FORTIFY code with the new pass manager because after inlining 
> we do a lot of (really nice) optimizations on library calls to remove 
> unnecessary FORTIFY checks. But this is in *theory* a problem when 
> LTO-ing with libc. More likely it could be a problem when LTO-ing with 
> a vector math library.
This latter case concerns me most. When the vectorizer creates the 
vectorized version of a loop, that's new code (the original code for the 
loop stays in place as a fall back). Further, the vectorizer can (today) 
create calls to vector math library functions, and a setup where we LTO 
with the definitions of those functions is certainly possible (and 
desirable). As a result, this issue does not seem all that theoretical 
to me.

Moreover, once we have support for OpenMP simd functions, we'll end up 
in exactly this situation on a regular basis, and we can't have 
intrinsics for all of the possible user-defined functions (unless the 
intrinsic just takes a function pointer and we clean it up afterwards 
somehow). In short, I think we do need to correctly handle this situation.

FWIW, I can also see this situation come up in other instrumentation 
cases as well. There are plenty of cases where it is useful to LTO with 
a runtime library.

Thanks again,
Hal
>
> So what do we do?
>
> My initial idea: find all *defined* library functions in the module, 
> and every time we create a ref edge to one of them, synthesize a ref 
> edge to all of them. This should completely solve #3b above. But it 
> doesn't really address #3a at all.
>
> Is that OK? It would be very convenient to say that if we want to 
> introduce truly novel and new calls to library functions, we should 
> have an LLVM intrinsic to model those routines.
>
> But we actually have an example (I think) of #3a, introducing a call 
> to a library function out of the blue: memset_pattern. =/
>
> The only way I see to reasonably handle #3a is to have *every* 
> function implicitly contain a reference edge to every defined library 
> function in the module. This is, needless to say, amazingly wasteful. 
> Hence my email. How important is this?
>
> If we need to correctly handle this, I think I would probably 
> implement this by actually changing the *iteration* of reference edges 
> in the graph to just implicitly walk the list of defined library 
> functions so that we didn't burn any space on this. But it will make 
> iteration of reference edges slower and add a reasonable amount of 
> complexity. So I'd like to hear some other opinions before going down 
> either of these roads.
>
>
> Thanks,
> -Chandler
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

On Mon, Jul 3, 2017 at 4:43 PM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> On 06/30/2017 03:02 AM, Chandler Carruth wrote:
>
>> I have hit a fairly isolated practical issue deploying the new PM, but
it
>> does point to a latent theoretical issues as well. I see various ways
to
>> address it, but want feedback from others before moving forward.
>>
>> The issue is that we can introduce out-of-thin-air calls to known
library
>> functions (`SimplifyLibCalls`, etc). These can be introduced in
function
>> passes (`InstCombine` in particular) and that seems highly desirable.
>>
>> These all look like one of these cases:
>> 1a) Introducing a new call to an LLVM intrinsic
>> 1b) Replacing an existing call with a call to an LLVM intrinsic
>> 2a) Introducing a new call to a declared library function (but not
>> defined)
>> 2b) Replacing an existing call with a call to a declared library
function
>> 3a) Introducing a new call to a defined library function
>> 3b) Replacing an existing call with a call to a defined library
function
>>
>> Both #1 and #2 are easy to handle in reality. Intrinsics and declared
>> functions don't impact the PM's call graph because there is no
need to
>> order the walk over them. But #3 is a real issue.
>>
>> The only case I have found that actually hits #3 at all hits #3b when
>> building FORTIFY code with the new pass manager because after inlining
we
>> do a lot of (really nice) optimizations on library calls to remove
>> unnecessary FORTIFY checks. But this is in *theory* a problem when
LTO-ing
>> with libc. More likely it could be a problem when LTO-ing with a vector
>> math library.
>>
>
> This latter case concerns me most. When the vectorizer creates the
> vectorized version of a loop, that's new code (the original code for
the
> loop stays in place as a fall back). Further, the vectorizer can (today)
> create calls to vector math library functions, and a setup where we LTO
> with the definitions of those functions is certainly possible (and
> desirable). As a result, this issue does not seem all that theoretical to
> me.
> Moreover, once we have support for OpenMP simd functions, we'll end up
in
> exactly this situation on a regular basis, and we can't have intrinsics
for
> all of the possible user-defined functions

Can you clarify how OpenMP simd would require introducing out-of-thin-air
references to an open-ended set of user-defined functions?


> (unless the intrinsic just takes a function pointer and we clean it up
> afterwards somehow).

Note that simply referencing a function pointer out-of-thin-air would still
run afoul of the same issue. It would constitute a ref edge and have
similar implications as a direct call, at least as far as the fundamental
problem here is concerned (guaranteeing bottom-up iteration order). So an
intrinsic taking a function pointer wouldn't really circumvent the issue
(if I understand correctly what you're saying).

-- Sean Silva

> In short, I think we do need to correctly handle this situation.
>
> FWIW, I can also see this situation come up in other instrumentation cases
> as well. There are plenty of cases where it is useful to LTO with a runtime
> library.
>
> Thanks again,
> Hal
>
>
>> So what do we do?
>>
>> My initial idea: find all *defined* library functions in the module,
and
>> every time we create a ref edge to one of them, synthesize a ref edge
to
>> all of them. This should completely solve #3b above. But it doesn't
really
>> address #3a at all.
>>
>> Is that OK? It would be very convenient to say that if we want to
>> introduce truly novel and new calls to library functions, we should
have an
>> LLVM intrinsic to model those routines.
>>
>> But we actually have an example (I think) of #3a, introducing a call to
a
>> library function out of the blue: memset_pattern. =/
>>
>> The only way I see to reasonably handle #3a is to have *every* function
>> implicitly contain a reference edge to every defined library function
in
>> the module. This is, needless to say, amazingly wasteful. Hence my
email.
>> How important is this?
>>
>> If we need to correctly handle this, I think I would probably implement
>> this by actually changing the *iteration* of reference edges in the
graph
>> to just implicitly walk the list of defined library functions so that
we
>> didn't burn any space on this. But it will make iteration of
reference
>> edges slower and add a reasonable amount of complexity. So I'd like
to hear
>> some other opinions before going down either of these roads.
>>
>>
>> Thanks,
>> -Chandler
>>
>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170703/0ff500f9/attachment-0001.html>