Page MenuHomePhabricator

[FunctionAttrs] Infer the speculatable attribute
Needs ReviewPublic

Authored by hfinkel on Jul 10 2018, 9:19 AM.

Details

Reviewers
nlopes
efriedma
Summary

This patch adds support for inferring the speculatable attribute in the FunctionAttrs pass.

My assumption here is that we need to assume that any loads performed by the function, and any incoming arguments, might be poison. As a result, we can't have any branches, PHIs, or stores (even to local static allocas) - because doing any of these things with poison values is UB. Is that correct?

Given that the functions for which we can infer this must be structurally simple (and can have no stores), and thus likely to be inlined, it's fair to ask why we should do this at all. I have two reasons:

  1. Especially when optimizing for code size, we do have large straight-line code functions, called from multiple call sites, which are large enough not to be inlined. It is nevertheless useful to hoist calls to these out of loops, etc.
  2. My experience has been that the handling of attributes in LLVM that we don't infer tends to be buggier (because we just have less coverage of the relevant code paths). Thus, I'm in favor of inferring the attributes that we reasonably can.

Diff Detail

Event Timeline

hfinkel created this revision.Jul 10 2018, 9:19 AM
efriedma added inline comments.Jul 10 2018, 11:39 AM
lib/Transforms/IPO/FunctionAttrs.cpp
1207

I don't think we can completely ignore calls to functions within the current SCC: we also have to ensure the call itself is never UB due to violating some attribute on the call (like nonnull; see D49041).

hfinkel added inline comments.Jul 10 2018, 12:49 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1207

Two thoughts:

  1. How we handle calls might not matter at all. Given that the calls can't have any branching, if there's a call in the closed SCC that we would otherwise mark as speculatable, doesn't it need to be infinite recursion (and that, we can't speculate)?
  2. Maybe D49041 is too aggressive? I think that we'd like violating nonnull on an argument to yield a poison value, not hard UB. This would be consistent with how to handle other flags (nsw, etc.)?

In any case, independent of (2), we can't speculate infinite recursion calls, so we should probably ignore the SCC regardless?

My assumption here is that we need to assume that any loads performed by the function, and any incoming arguments, might be poison. As a result, we can't have any branches, PHIs, or stores (even to local static allocas) - because doing any of these things with poison values is UB. Is that correct?

Control flow that might lead to infinite loops might be a problem, but why not allow at least acyclic control flow?

If the value stored to an alloca is thrown away after the ret, why is it a problem to be executed speculatively?

My assumption here is that we need to assume that any loads performed by the function, and any incoming arguments, might be poison. As a result, we can't have any branches, PHIs, or stores (even to local static allocas) - because doing any of these things with poison values is UB. Is that correct?

Control flow that might lead to infinite loops might be a problem, but why not allow at least acyclic control flow?

If the value stored to an alloca is thrown away after the ret, why is it a problem to be executed speculatively?

I first started coding it that way. Even if we branch on a poison value, why does it matter so long as there are no observable side effects? My fear was that, if we do that, and then we hoist the call, and then we inline the function body, we now may have a case where we clearly branch on a poison value and that, as I understand it, is UB. I may be mistaken, and if I am, then we should allow branching and stores to static allocas, etc.

I think marking a function speculatable requires stripping metadata from any loads in that function, to avoid UB. Does that sound reasonable?

I think marking a function speculatable requires stripping metadata from any loads in that function, to avoid UB. Does that sound reasonable?

That seems unfortunate. We could also not mark the function as speculatable, or, we could say that violating the load metadata produces a poison result, or some combination of both. Is there something about poison that won't work?

We currently have transforms which assume violating load metadata produces UB, not poison (see https://reviews.llvm.org/D37216).

hfinkel updated this revision to Diff 155312.Jul 12 2018, 7:35 PM

Updated to not infer speculatable if there are instructions with non-debug metadata, loads with alignment requirements that we can't independently prove, and for functions with value-constraining return-value attributes.

There other change that's here, although I'll split it out into a separate patch with tests if we agree it's the right approach, is an update to isSafeToSpeculativelyExecute: For calls with the speculatable attibute that have function-argument attributes that are value constraining (align in general, nonnull, dereferenceable), we need to independently prove the necessary conditions in order for isSafeToSpeculativelyExecute to return true. I think that this is the right thing to do because the violation of those constraints is currently defined to be UB (not poison). If we don't do this, then we can't infer speculatable on function with arguments with these attributes either.

hfinkel updated this revision to Diff 155390.Jul 13 2018, 8:10 AM

Misc cleanup and try to validate ret attrs instead of disqualifying them all.

hfinkel marked 2 inline comments as done.Jul 13 2018, 8:11 AM
efriedma added inline comments.Jul 13 2018, 2:11 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1251

Do we also need to look for other attributes on the function? For example, a function which reads memory but is marked readnone, or a function which calls itself but is marked norecurse.

hfinkel added inline comments.Jul 13 2018, 7:52 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1251

I looked at them, but I don't think there are any issues in this regard. Because we don't allow branching, there can't be any control dependencies on whether or not memory is read or whether the function recurses. argmemonly, by the current wording, is not allowed to be valid by implicit contract, so even that one is okay.

efriedma added inline comments.Jul 17 2018, 3:12 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1251

It's possible to have a function which has unconditional undefined behavior; that's fine as long as it isn't "speculatable" and never actually gets called.

Or you could have a function like int g; const int c = 10; __attribute((const)) int f(bool b) { return *(b ? &g : &c); }. f(true) is UB, but f(false) is fine.

hfinkel added inline comments.Jul 19 2018, 2:00 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1251

It's possible to have a function which has unconditional undefined behavior; that's fine as long as it isn't "speculatable" and never actually gets called.

I completely agree, but we explicitly check the function bodies. I believe that the current checks rule out any UB in the function, even if all arguments (or loaded data, etc.) are poison. Moreover, I don't think that any current function attributes cause a problem in this regard (not that, in theory, an attribute couldn't be added that might need to be handled, just that none of the current ones need handling here).

Or you could have a function like ...

On the general point, I agree. In this case, we'd need to be able to prove all loads dereferenceable in order to speculate. Are you saying that just loading the uninitialized value is UB? (if that's true, then there's another problem with our use of dereferenceable and C++ references, no?)

efriedma added inline comments.Jul 19 2018, 2:45 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1251

Simpler testcase: in int g; __attribute((const)) int f() { return g; }, it's UB to call the function f, because it returns the value of a mutable global g. So we can't mark it speculatable. At least, that's what D49041 says; we could change LangRef, I guess.

hfinkel added inline comments.Jul 19 2018, 4:57 PM
lib/Transforms/IPO/FunctionAttrs.cpp
1251

Good point. I hadn't thought about this previously, but we should do something here. D49041 talks about "writes memory visible to the program", and that might not be the best way to describe this. Constant memory is okay, and we need to differentiate this from inaccessiblememonly, which also can read or write memory not accessible to the current module, and at least to me, visible and accessible seem very similar. Moreover, calling this function might still be okay if nothing every actually changes g (even if it is mutable)?

Regardless, I agree. If a function is marked as readnone, and contains loads, we should not speculate it.

uenoku added a subscriber: uenoku.Thu, Sep 19, 10:13 AM