[llvm-dev] An issue with new PM's requirements on call graph changes

[Hal Finkel via llvm-dev]

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