LLVM intrinsic for invariants

[hfinkel]

Summary

Adds void @llvm.invariant(i1 %cond)

[hfinkel]

This adds the basic invariant intrinsic, noop lowering, and some basic properties:

• llvm.invariant(undef) and llvm.invariant(true) are dead
• llvm.invariant(false) is unreachable (this directly corresponds to the documented behavior of MSVC's __assume(0))

The intrinsic is tagged as writing arbitrarily, in order to maintain control dependencies. BasicAA has been updated, however, to return NoModRef for any particular location-based query so that we don't unnecessarily block code motion.

[hfinkel]

Rebased.

[chandlerc]

docs/LangRef.rst

9358

I wonder if this would be more clear spelled "llvm.assume.invariant" or just "llvm.assume".

9375–9378

I think we should provide some minimal guidance for FE authors here that essentially indicates that using this intrinsic is not without cost, and essentially shouldn't be used to either document basic mathematical invariants the compiler could deduce otherwise, or if the invariant holds little or no value to the optimizer.

lib/Transforms/Utils/Local.cpp

305

If the condition is undef, aren't they unreachable?

test/Transforms/InstSimplify/invariant.ll

3–5 ↗

(On Diff #11590)

Indent seems weird here. Use the more common 2-space indent?

[hfinkel]

Updated docs and made invariant(undef) like invariant(false) (instead of like invariant(true)).

[hfinkel]

Renamed to llvm.assume.

[reames]

With a couple of small changes mentioned inline, LGTM.

docs/LangRef.rst

9383

Why? Suggestion:
Please note that ''llvm.assume'' is not free and may impact the effectiveness of the optimizer in hard to predict ways. ''llvm.assume'' should be used to represent high level facts which are not otherwise available to the optimizer and only after careful consideration of the benefit and costs. In particular, 'llvm.assume'' should not be used to...

I'm not sure I really like my wording around 'free' above, but this is a starting point.

include/llvm/IR/Intrinsics.td

282

I understand why you're doing this, but it honestly feels like a bit of a hack. Is it possibly time to introduce a notion of control dependence that is not driven by memory access? This is essentially what you've written, but there might be a better way to factor it.

This doesn't need to be changed before submission, I'm just raising it for consideration and discussion.

lib/Analysis/BasicAliasAnalysis.cpp

799

I've noticed we have multiple isXIntrinsic functions scatter around the code base. We might want to think about - in a separate change - creating an isIntrinsic(IntrinsicID) function on CallSite.

lib/Transforms/Utils/Local.cpp

1199

Adding a comment on this case would be good. Particularly given that it required discussion to arrive at this being the right semantic.

test/CodeGen/Generic/assume.ll

1

This test could be stronger. Could you add a FileCheck here?

[hfinkel]

docs/LangRef.rst

9383

Good idea. Instead of "free", I'll say something like, "The optimizer might limit the transformations performed on values used by the intrinsic in order to preserve the instructions only used to form the intrinsic's input argument, and this might prove undesirable if the extra information provided by that intrinsic does cause sufficient overall improvement."

include/llvm/IR/Intrinsics.td

282

Fixing this is another major infrastructure project. :(

lib/Analysis/BasicAliasAnalysis.cpp

799

Good idea; I'll queue that for later refactoring.

lib/Transforms/Utils/Local.cpp

1199

Will do.

test/CodeGen/Generic/assume.ll

1

No, this is a "generic lowering" test. It runs on all targets to make sure that it does not crash (that the code generator does *something*). You'll find many such tests in that directory.

[hfinkel]

Philip accepted (with minor updates); I'll commit in the near future.

[hfinkel]

r213973, thanks!

docs/LangRef.rst

 a value. The second argument is an expected value, this needs to be a
 constant value, variables are not allowed.
 
 Semantics:
 """"""""""
 
 This intrinsic is lowered to the ``val``.
 
+'``llvm.assume``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare void @llvm.assume(i1 %cond)
+
+Overview:
+"""""""""
+
+The ``llvm.assume`` allows the optimizer to assume that the provided
+condition is true. This information can then be used in simplifying other parts
+of the code.
+
+Arguments:
+""""""""""
+
+The condition which the optimizer may assume is always true.
+
+Semantics:
+""""""""""
+
+The intrinsic allows the optimizer to assume that the provided condition is
+always true whenever the control flow reaches the intrinsic call. No code is
+generated for this intrinsic, and instructions that contribute only to the
+provided condition are not used for code generation. If the condition is
+violated during execution, the behavior is undefined.
+
+Please note that ``llvm.assume`` should not be used to document basic
+mathematical invariants that the optimizer can otherwise deduce or facts that
+are of little use to the optimizer.
+
 '``llvm.donothing``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 

include/llvm/IR/Intrinsics.td

 def int_prefetch      : Intrinsic<[],
                                   [llvm_ptr_ty, llvm_i32_ty, llvm_i32_ty,
                                    llvm_i32_ty],
                                   [IntrReadWriteArgMem, NoCapture<0>]>;
 def int_pcmarker      : Intrinsic<[], [llvm_i32_ty]>;
 
 def int_readcyclecounter : Intrinsic<[llvm_i64_ty]>;
 
+// The assume intrinsic is marked as arbitrarily writing so that proper
+// control dependencies will be maintained.
+def int_assume        : Intrinsic<[], [llvm_i1_ty], []>;
+
 // Stack Protector Intrinsic - The stackprotector intrinsic writes the stack
 // guard to the correct place on the stack frame.
 def int_stackprotector : Intrinsic<[], [llvm_ptr_ty, llvm_ptrptr_ty], []>;
 def int_stackprotectorcheck : Intrinsic<[], [llvm_ptrptr_ty],
                                         [IntrReadWriteArgMem]>;
 
 //===------------------- Standard C Library Intrinsics --------------------===//
 //

lib/Analysis/BasicAliasAnalysis.cpp

AliasResult alias(const Location &LocA, const Location &LocB) override {
       VisitedPhiBBs.clear();
       return Alias;
     }
 
     ModRefResult getModRefInfo(ImmutableCallSite CS,
                                const Location &Loc) override;
 
     ModRefResult getModRefInfo(ImmutableCallSite CS1,
-                               ImmutableCallSite CS2) override {
-      // The AliasAnalysis base class has some smarts, lets use them.
-      return AliasAnalysis::getModRefInfo(CS1, CS2);
-    }
+                               ImmutableCallSite CS2) override;
 
     /// pointsToConstantMemory - Chase pointers until we find a (constant
     /// global) or not.
     bool pointsToConstantMemory(const Location &Loc, bool OrLocal) override;
 
     /// Get the location associated with a pointer argument of a callsite.
     Location getArgLocation(ImmutableCallSite CS, unsigned ArgIdx,
                             ModRefResult &Mask) override;
assert(Loc.Ptr == CS.getArgument(ArgIdx) &&
            "memset_pattern16 location pointer not argument?");
     Mask = ArgIdx ? Ref : Mod;
   }
   // FIXME: Handle memset_pattern4 and memset_pattern8 also.
 
   return Loc;
 }
 
+static bool isAssumeIntrinsic(ImmutableCallSite CS) {
+  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
+  if (II && II->getIntrinsicID() == Intrinsic::assume)
+    return true;
+
+  return false;
+}
+
 /// getModRefInfo - Check to see if the specified callsite can clobber the
 /// specified memory object.  Since we only look at local properties of this
 /// function, we really can't say much about this query.  We do, however, use
 /// simple "address taken" analysis on local objects.
 AliasAnalysis::ModRefResult
 BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
                                   const Location &Loc) {
   assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
         break;
       }
     }
 
     if (!PassedAsArg)
       return NoModRef;
   }
 
+  // While the assume intrinsic is marked as arbitrarily writing so that
+  // proper control dependencies will be maintained, it never aliases any
+  // particular memory location.
+  if (isAssumeIntrinsic(CS))
+    return NoModRef;
+
   // The AliasAnalysis base class has some smarts, lets use them.
   return AliasAnalysis::getModRefInfo(CS, Loc);
 }
 
+AliasAnalysis::ModRefResult
+BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS1,
+                                  ImmutableCallSite CS2) {
+  // While the assume intrinsic is marked as arbitrarily writing so that
+  // proper control dependencies will be maintained, it never aliases any
+  // particular memory location.
+  if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2))
+    return NoModRef;
+
+  // The AliasAnalysis base class has some smarts, lets use them.
+  return AliasAnalysis::getModRefInfo(CS1, CS2);
+}
+
 /// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
 /// against another pointer.  We know that V1 is a GEP, but we don't know
 /// anything about V2.  UnderlyingV1 is GetUnderlyingObject(GEP1, DL),
 /// UnderlyingV2 is the same for V2.
 ///
 AliasAnalysis::AliasResult
 BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
                              const MDNode *V1TBAAInfo,

lib/Analysis/TargetTransformInfo.cpp

unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Type *> ParamTys) const override {
     switch (IID) {
     default:
       // Intrinsics rarely (if ever) have normal argument setup constraints.
       // Model them as having a basic instruction cost.
       // FIXME: This is wrong for libc intrinsics.
       return TCC_Basic;
 
+    case Intrinsic::assume:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::objectsize:
     case Intrinsic::ptr_annotation:

lib/CodeGen/BasicTargetTransformInfo.cpp

unsigned BasicTTI::getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
   case Intrinsic::trunc:   ISD = ISD::FTRUNC; break;
   case Intrinsic::nearbyint:
                            ISD = ISD::FNEARBYINT; break;
   case Intrinsic::rint:    ISD = ISD::FRINT;  break;
   case Intrinsic::round:   ISD = ISD::FROUND; break;
   case Intrinsic::pow:     ISD = ISD::FPOW;   break;
   case Intrinsic::fma:     ISD = ISD::FMA;    break;
   case Intrinsic::fmuladd: ISD = ISD::FMA;    break;
+  // FIXME: We should return 0 whenever getIntrinsicCost == TCC_Free.
   case Intrinsic::lifetime_start:
   case Intrinsic::lifetime_end:
     return 0;
   }
 
   const TargetLoweringBase *TLI = getTLI();
   std::pair<unsigned, MVT> LT = TLI->getTypeLegalizationCost(RetTy);
 

lib/CodeGen/IntrinsicLowering.cpp

case Intrinsic::eh_typeid_for:
     break;
 
   case Intrinsic::annotation:
   case Intrinsic::ptr_annotation:
     // Just drop the annotation, but forward the value
     CI->replaceAllUsesWith(CI->getOperand(0));
     break;
 
+  case Intrinsic::assume:
   case Intrinsic::var_annotation:
-    break;   // Strip out annotate intrinsic
-    
+    break;   // Strip out these intrinsics
   case Intrinsic::memcpy: {
     Type *IntPtr = DL.getIntPtrType(Context);
     Value *Size = Builder.CreateIntCast(CI->getArgOperand(2), IntPtr,
                                         /* isSigned */ false);
     Value *Ops[3];
     Ops[0] = CI->getArgOperand(0);
     Ops[1] = CI->getArgOperand(1);
     Ops[2] = Size;

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::objectsize: {
     setValue(&I, Res);
     return nullptr;
   }
   case Intrinsic::annotation:
   case Intrinsic::ptr_annotation:
     // Drop the intrinsic, but forward the value
     setValue(&I, getValue(I.getOperand(0)));
     return nullptr;
+  case Intrinsic::assume:
   case Intrinsic::var_annotation:
-    // Discard annotate attributes
+    // Discard annotate attributes and assumptions
     return nullptr;
 
   case Intrinsic::init_trampoline: {
     const Function *F = cast<Function>(I.getArgOperand(1)->stripPointerCasts());
 
     SDValue Ops[6];
     Ops[0] = getRoot();
     Ops[1] = getValue(I.getArgOperand(0));

lib/Transforms/Utils/Local.cpp

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     // Safe to delete llvm.stacksave if dead.
     if (II->getIntrinsicID() == Intrinsic::stacksave)
       return true;
 
     // Lifetime intrinsics are dead when their right-hand is undef.
     if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
         II->getIntrinsicID() == Intrinsic::lifetime_end)
       return isa<UndefValue>(II->getArgOperand(1));
+
+    // Assumptions are dead if their condition is trivially true.
+    if (II->getIntrinsicID() == Intrinsic::assume) {
+      if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
+        return !Cond->isZero();
+
+      return false;
+    }
   }
 
   if (isAllocLikeFn(I, TLI)) return true;
 
   if (CallInst *CI = isFreeCall(I, TLI))
     if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
       return C->isNullValue() || isa<UndefValue>(C);
 
static bool markAliveBlocks(BasicBlock *BB,
   bool Changed = false;
   do {
     BB = Worklist.pop_back_val();
 
     // Do a quick scan of the basic block, turning any obviously unreachable
     // instructions into LLVM unreachable insts.  The instruction combining pass
     // canonicalizes unreachable insts into stores to null or undef.
     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
+      // Assumptions that are known to be false are equivalent to unreachable.
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
+        if (II->getIntrinsicID() == Intrinsic::assume) {
+          bool MakeUnreachable = false;
+          if (isa<UndefValue>(II->getArgOperand(0)))
+            MakeUnreachable = true;
+          else if (ConstantInt *Cond =
+                   dyn_cast<ConstantInt>(II->getArgOperand(0)))
+            MakeUnreachable = Cond->isZero();
+
+          if (MakeUnreachable) { 
+            // Don't insert a call to llvm.trap right before the unreachable.
+            changeToUnreachable(BBI, false);
+            Changed = true;
+            break;
+          }
+        }
+
       if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
         if (CI->doesNotReturn()) {
           // If we found a call to a no-return function, insert an unreachable
           // instruction after it.  Make sure there isn't *already* one there
           // though.
           ++BBI;
           if (!isa<UnreachableInst>(BBI)) {
             // Don't insert a call to llvm.trap right before the unreachable.

test/Analysis/BasicAA/assume.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:32:64-v128:32:128-a0:0:32-n32"
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) #0
+declare void @llvm.assume(i1) #0
+
+define void @test1(i8* %P, i8* %Q) nounwind ssp {
+  tail call void @llvm.assume(i1 true)
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
+  ret void
+
+; CHECK-LABEL: Function: test1:
+
+; CHECK: MayAlias:  i8* %P, i8* %Q
+; CHECK: NoModRef:  Ptr: i8* %P <->  tail call void @llvm.assume(i1 true)
+; CHECK: NoModRef:  Ptr: i8* %Q <->  tail call void @llvm.assume(i1 true)
+; CHECK: Both ModRef:  Ptr: i8* %P  <->  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
+; CHECK: Both ModRef:  Ptr: i8* %Q  <->  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
+; CHECK: NoModRef:   tail call void @llvm.assume(i1 true) <->   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false)
+; CHECK: NoModRef:   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) <->   tail call void @llvm.assume(i1 true)
+}
+
+attributes #0 = { nounwind }

test/CodeGen/Generic/assume.ll

+; RUN: llc < %s
+
+define void @main() {
+        call void @llvm.assume(i1 1)
+        ret void
+}
+
+declare void @llvm.assume(i1) nounwind
+

test/Transforms/InstSimplify/assume.ll

+; RUN: opt -instsimplify -S < %s | FileCheck %s
+
+define void @test1() {
+  call void @llvm.assume(i1 1)
+  ret void
+
+; CHECK-LABEL: @test1
+; CHECK-NOT: llvm.assume
+; CHECK: ret void
+}
+
+declare void @llvm.assume(i1) nounwind
+

test/Transforms/SimplifyCFG/assume.ll

+; RUN: opt -simplifycfg -S < %s | FileCheck %s
+
+define void @test1() {
+        call void @llvm.assume(i1 0)
+        ret void
+
+; CHECK-LABEL: @test1
+; CHECK-NOT: llvm.assume
+; CHECK: unreachable
+}
+
+define void @test2() {
+        call void @llvm.assume(i1 undef)
+        ret void
+
+; CHECK-LABEL: @test2
+; CHECK-NOT: llvm.assume
+; CHECK: unreachable
+}
+
+declare void @llvm.assume(i1) nounwind
+