[FunctionAttrs] Infer the speculatable attribute

[hfinkel]

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.

[efriedma]

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]

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?

[Meinersbur]

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?

[hfinkel]

In D49144#1158047, @Meinersbur wrote:

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.

[efriedma]

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

[hfinkel]

In D49144#1158138, @efriedma wrote:

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?

[efriedma]

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

[hfinkel]

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]

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

[efriedma]

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]

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]

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]

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]

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]

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.

lib/Analysis/ValueTracking.cpp

return isDereferenceableAndAlignedPointer(LI->getPointerOperand(),
                                               LI->getAlignment(), DL, CtxI, DT);
   }
   case Instruction::Call: {
     auto *CI = cast<const CallInst>(Inst);
     const Function *Callee = CI->getCalledFunction();
 
     // The called function could have undefined behavior or side-effects, even
     // if marked readnone nounwind.
-    return Callee && Callee->isSpeculatable();
+    if (Callee && Callee->isSpeculatable()) {
+      const DataLayout &DL = CI->getModule()->getDataLayout();
+      auto CS = ImmutableCallSite(CI);
+
+      // Function arguments can have constraints, such as nonnull, the violation of
+      // which yield undefined behavior (not just a poison value). Functions with
+      // such attributed arguments cannot be speculated unless we can validate the
+      // conditions at the point of speculation.
+      for (auto &A : CS.args()) {
+        unsigned AIdx = A.getOperandNo();
+        if (CS.paramHasAttr(AIdx, Attribute::NonNull) &&
+            // FIXME: Pass AC here.
+            !isKnownNonZero(&*A, DL, 0, nullptr, CtxI, DT))
+          return false;
+
+        if (uint64_t B = CS.getDereferenceableBytes(AIdx)) {
+          bool CanBeNull;
+          if (B && (B < A->getPointerDereferenceableBytes(DL, CanBeNull) ||
+              CanBeNull))
+            return false;
+        }
+
+        if (uint64_t B = CS.getDereferenceableOrNullBytes(AIdx)) {
+          bool CanBeNull;
+          if (B && B < A->getPointerDereferenceableBytes(DL, CanBeNull))
+            return false;
+        }
+
+        if (!CS.isByValOrInAllocaArgument(AIdx)) {
+          unsigned Align = CS.getParamAlignment(AIdx);
+          if (Align > 1 && Align < A->getPointerAlignment(DL))
+            return false;
+        }
+      }
+
+      return true;
+    }
   }
   case Instruction::VAArg:
   case Instruction::Alloca:
   case Instruction::Invoke:
   case Instruction::PHI:
   case Instruction::Store:
   case Instruction::Ret:
   case Instruction::Br:

lib/Transforms/IPO/FunctionAttrs.cpp

 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
 STATISTIC(NumReturned, "Number of arguments marked returned");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
+STATISTIC(NumSpeculatable, "Number of functions marked as speculatable");
 
 // FIXME: This is disabled by default to avoid exposing security vulnerabilities
 // in C/C++ code compiled by clang:
 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
 static cl::opt<bool> EnableNonnullArgPropagation(
     "enable-nonnull-arg-prop", cl::Hidden,
     cl::desc("Try to propagate nonnull argument attributes from callsites to "
              "caller functions."));
 
 static cl::opt<bool> DisableNoUnwindInference(
     "disable-nounwind-inference", cl::Hidden,
     cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
 
+static cl::opt<bool> DisableSpeculatableInference(
+    "disable-speculatable-inference", cl::Hidden,
+    cl::desc("Stop inferring speculatable attribute during function-attrs pass"));
+
 namespace {
 
 using SCCNodeSet = SmallSetVector<Function *, 8>;
 
 } // end anonymous namespace
 
 /// Returns the memory access attribute for function F using AAR for AA results,
 /// where SCCNodes is the current SCC.
if (Function *Callee = CI->getCalledFunction()) {
       // just have to scan that other function.
       if (SCCNodes.count(Callee) > 0)
         return false;
     }
   }
   return true;
 }
 
+/// Helper for Speculatable inference predicate InstrBreaksAttribute.
+static bool InstrBreaksSpeculatable(Instruction &I) {
+  // Note that we don't bother to check here for calls to functions within the
+  // current SCC for two reasons:
+  //   1. It wouldn't clearly be useful. As we don't allow functions with
+  //      branches any call would be called unconditionally, and we shouldn't
+  //      speculate infinite recursion.
+  //   2. We'd need to avoid triggering UB by passing poison values, or
+  //      otherwise invalid values, to function arguments with constraints (e.g.,
+  //      nonnull).
+
+  // If instructions have metadata that can't be speculated, then a call to the
+  // function can't be speculated. Generally, if we speculate an instruction
+  // with metadata we can just drop the metadata. However, if we speculate a
+  // call, then we can't drop the metadata inside the called function.
+  if (I.hasMetadataOtherThanDebugLoc())
+    return true;
+
+  auto &DL = I.getParent()->getParent()->getParent()->getDataLayout();
+
+  // If a load has an alignment requirement, we need to make sure that we can
+  // justify this constraint using only function-argument attributes or global
+  // information (otherwise, this requirement might be violated when the call
+  // is executed speculatively).
+  if (auto *LI = dyn_cast<LoadInst>(&I)) {
+    unsigned Align = LI->getAlignment();
+    if (!Align)
+      Align = DL.getABITypeAlignment(LI->getType());
+    if (Align < LI->getPointerOperand()->getPointerAlignment(DL))
+      return true;
+  }
+
+  // Note that we need to assume here that any inputs to the function might be
+  // poison, and in response, we can generate more poison, but not undefined
+  // behavior. This means no branching (and essentially no stores).
+
+  // Returns are okay in this context.
+  if (isa<ReturnInst>(I))
+    return false;
+
+  return !isSafeToSpeculativelyExecute(&I);
+}
+
+static bool FuncHasNonSpecRetAttrs(const Function &F) {
+  // If the function has return-value attributes that impose value constraints
+  // then we cannot speculate the execution of the function (as the violation
+  // of those constraints is UB, and they might not be true when the execution
+  // is speculative).
+
+  if (F.returnDoesNotAlias())
+    return true;
+  if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
+                                     Attribute::NonNull))
+    return true;
+  if (F.getDereferenceableBytes(AttributeList::ReturnIndex) > 0 ||
+      F.getDereferenceableOrNullBytes(AttributeList::ReturnIndex) > 0)
+    return true;
+  if (F.getAttributes().getRetAlignment() > 0)
+    return true;
+
+  return false;
+}
+
 /// Infer attributes from all functions in the SCC by scanning every
 /// instruction for compliance to the attribute assumptions. Currently it
 /// does:
 ///   - removal of Convergent attribute
 ///   - addition of NoUnwind attribute
 ///
 /// Returns true if any changes to function attributes were made.
 static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
         [](Function &F) {
           LLVM_DEBUG(dbgs()
                      << "Adding nounwind attr to fn " << F.getName() << "\n");
           F.setDoesNotThrow();
           ++NumNoUnwind;
         },
         /* RequiresExactDefinition= */ true});
 
+  if (!DisableSpeculatableInference)
+    // Request to infer speculatable attribute for all the functions in the SCC if
+    // every instruction within the SCC is safe to speculatively execute (except
+    // for calls to functions within the SCC). Note that the speculatable attribute
+    // suffers from derefinement - results may change depending on how functions are
+    // optimized. Thus it can be inferred only from exact definitions.
+    AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
+        Attribute::Speculatable,
+        // Skip speculatable functions.
+        [](const Function &F) { return F.isSpeculatable() ||
+                                       FuncHasNonSpecRetAttrs(F); },
+        // Instructions that break non-throwing assumption.
+        [](Instruction &I) {
+          return InstrBreaksSpeculatable(I);
+        },
+        [](Function &F) {
+          LLVM_DEBUG(dbgs()
+                     << "Adding speculatable attr to fn " << F.getName() << "\n");
+          F.setSpeculatable();
+          ++NumSpeculatable;
+        },
+        /* RequiresExactDefinition= */ true});
+
   // Perform all the requested attribute inference actions.
   return AI.run(SCCNodes);
 }
 
 static bool setDoesNotRecurse(Function &F) {
   if (F.doesNotRecurse())
     return false;
   F.setDoesNotRecurse();

test/CodeGen/AMDGPU/inline-attr.ll

 ; RUN: opt -mtriple=amdgcn--amdhsa -S -O3 -enable-unsafe-fp-math %s  | FileCheck -check-prefix=GCN -check-prefix=UNSAFE %s
 ; RUN: opt -mtriple=amdgcn--amdhsa -S -O3 -enable-no-nans-fp-math %s | FileCheck -check-prefix=GCN -check-prefix=NONANS %s
 ; RUN: opt -mtriple=amdgcn--amdhsa -S -O3 -enable-no-infs-fp-math %s | FileCheck -check-prefix=GCN -check-prefix=NOINFS %s
 
 ; GCN: define float @foo(float %x) local_unnamed_addr #0 {
 ; GCN: define amdgpu_kernel void @caller(float addrspace(1)* nocapture %p) local_unnamed_addr #1 {
 ; GCN: %mul.i = fmul float %load, 1.500000e+01
 
-; UNSAFE: attributes #0 = { norecurse nounwind readnone "less-precise-fpmad"="true" "no-infs-fp-math"="true" "no-nans-fp-math"="true" "unsafe-fp-math"="true" }
+; UNSAFE: attributes #0 = { norecurse nounwind readnone speculatable "less-precise-fpmad"="true" "no-infs-fp-math"="true" "no-nans-fp-math"="true" "unsafe-fp-math"="true" }
 ; UNSAFE: attributes #1 = { norecurse nounwind "less-precise-fpmad"="true" "no-infs-fp-math"="true" "no-nans-fp-math"="true" "unsafe-fp-math"="true" }
 
-; NOINFS: attributes #0 = { norecurse nounwind readnone "no-infs-fp-math"="true" }
+; NOINFS: attributes #0 = { norecurse nounwind readnone speculatable "no-infs-fp-math"="true" }
 ; NOINFS: attributes #1 = { norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="true" "no-nans-fp-math"="false" "unsafe-fp-math"="false" }
 
-; NONANS: attributes #0 = { norecurse nounwind readnone "no-nans-fp-math"="true" }
+; NONANS: attributes #0 = { norecurse nounwind readnone speculatable "no-nans-fp-math"="true" }
 ; NONANS: attributes #1 = { norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="true" "unsafe-fp-math"="false" }
 
 define float @foo(float %x) #0 {
 entry:
   %mul = fmul float %x, 1.500000e+01
   ret float %mul
 }
 

test/Transforms/FunctionAttrs/atomic.ll

 ; A function with an Acquire load is not readonly.
 define i32 @test2(i32* %x) uwtable ssp {
 ; CHECK: define i32 @test2(i32* nocapture readonly %x) #1 {
 entry:
   %r = load atomic i32, i32* %x seq_cst, align 4
   ret i32 %r
 }
 
+define i32 @test3(i32* align 4 %x) uwtable ssp {
+; CHECK: define i32 @test3(i32* nocapture readonly align 4 %x) #2 {
+entry:
+  %r = load i32, i32* %x, align 4
+  ret i32 %r
+}
+
+define i32 @test4(i32* align 4 dereferenceable(4) %x) uwtable ssp {
+; CHECK: define i32 @test4(i32* nocapture readonly align 4 dereferenceable(4) %x) #3 {
+entry:
+  %r = load i32, i32* %x, align 4
+  ret i32 %r
+}
+
+define i32* @test5(i32** align 4 dereferenceable(4) %x) uwtable ssp {
+; CHECK: define nonnull i32* @test5(i32** nocapture readonly align 4 dereferenceable(4) %x) #2 {
+entry:
+  %r = load i32*, i32** %x, align 4, !nonnull !0
+  ret i32* %r
+}
+
+define i32 @test6(i32* align 4 dereferenceable(4) %x) uwtable ssp {
+; CHECK: define i32 @test6(i32* nocapture readonly align 4 dereferenceable(4) %x) #2 {
+entry:
+  %r = load i32, i32* %x, align 4, !range !1
+  ret i32 %r
+}
+
+define noalias i32* @test7(i32** align 4 dereferenceable(4) %x) uwtable ssp {
+; CHECK: define noalias i32* @test7(i32** nocapture readonly align 4 dereferenceable(4) %x) #2 {
+entry:
+  %r = load i32*, i32** %x, align 4
+  ret i32* %r
+}
+
+!0 = !{}
+!1 = !{ i32 0, i32 2000 }
+
 ; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable }
 ; CHECK: attributes #1 = { norecurse nounwind ssp uwtable }
+; CHECK: attributes #2 = { norecurse nounwind readonly ssp uwtable }
+; CHECK: attributes #3 = { norecurse nounwind readonly speculatable ssp uwtable }

test/Transforms/FunctionAttrs/optnone.ll

; CHECK: (i8* %p) #1 {
   ret void
 }
 
 declare i8 @strlen(i8*) noinline optnone
 ; CHECK-LABEL: @strlen
 ; CHECK: (i8*) #1
 
 ; CHECK-LABEL: attributes #0
-; CHECK: = { norecurse nounwind readnone }
+; CHECK: = { norecurse nounwind readnone speculatable }
 ; CHECK-LABEL: attributes #1
 ; CHECK: = { noinline optnone }

test/Transforms/Reassociate/reassociate-deadinst.ll

-; RUN: opt < %s -inline -functionattrs -reassociate -S | FileCheck %s
+; RUN: opt < %s -inline -functionattrs -reassociate -disable-speculatable-inference -S | FileCheck %s
+; Note: We disable inference of the speculatable attribute here so that the
+; call to @func1 ends up in the ValueRankMap (requiring mayBeMemoryDependent to
+; return true) so that the call will be removed after its uses are removed.
 
 ; CHECK-NOT: func1
 ; CHECK-LABEL: main
 ; CHECK-NEXT: ret void
 
 define internal i16 @func1() noinline #0 {
   ret i16 0
 }
 
 define void @main(i16 %argc, i16** %argv) #0 {
   %_tmp0 = call i16 @func1()
   %_tmp2 = zext i16 %_tmp0 to i32
   ret void
 }
 attributes #0 = { minsize nounwind optsize }