[ValueTracking] use nonnull argument attribute to eliminate null checks

[spatel]

Summary

Enhancing value tracking's analysis of null-ness was suggested in D27855, so here's a first attempt at that.

Irony: the ultimate motivation for this change is to make LLVM itself faster by improving the IR for dyn_cast, but we can't do that without adding analysis and transforms that will likely slow us down even more until we have all of the pieces in place.

Ie, this won't solve PR28430 alone:
https://llvm.org/bugs/show_bug.cgi?id=28430

[chandlerc]

Can you add a some negative tests showing that we don't eliminate null checks *before* a call?

Also would be good to test a subtle case but one I think is correct: when CtxtI is the call instruction with the nonnull. I'm imagining something like deducing nonnull for one argument from the attribute on another when the same pointer is passed to both. Not sure what transform pass to use but it seems a good case to document.

Finally, before this goes in, I think we may need to do something to prevent worsening the bugs exposed by newer glibc marking memcpy and friends with nonnull....

[spatel]

Patch updated:
No changes to the code, but added test cases as suggested by Chandler.

[spatel]

In D28204#633198, @chandlerc wrote:

Can you add a some negative tests showing that we don't eliminate null checks *before* a call?

Repurposed the 'caller4' test so that the null check comes before the call. I think this shows a missed opportunity to simplify the check, but let me know if I'm not seeing that correctly. Also, added a 'caller5' test where we can't simplify the check.

Also would be good to test a subtle case but one I think is correct: when CtxtI is the call instruction with the nonnull. I'm imagining something like deducing nonnull for one argument from the attribute on another when the same pointer is passed to both. Not sure what transform pass to use but it seems a good case to document.

Added an instcombine test 'deduce_nonnull_from_another_call' that isn't quite what was suggested, but shows that the value tracking improvement affects an existing transform in InstCombiner::visitCallSite().

Finally, before this goes in, I think we may need to do something to prevent worsening the bugs exposed by newer glibc marking memcpy and friends with nonnull....

If there are required changes for clang/llvm itself, I could use some hints about how to sniff those out. I found this mail from Aug 2015:
http://lists.llvm.org/pipermail/llvm-dev/2015-August/088950.html
and this commit:
rL243927
...we need to add more guard checks around memcpy() and other string.h functions?

[reames]

lib/Analysis/ValueTracking.cpp

3385

Please handle invokes as well. Use CallSite to abstract over both.

3409

Huh, this should really be handling assumes as well. Can you file a separate bug for that?

[spatel]

lib/Analysis/ValueTracking.cpp

3409

I think we can use PR31512 to track this:
https://llvm.org/bugs/show_bug.cgi?id=31512
...but let me know if you think another report is needed.

[spatel]

Patch updated:

1. Changed to use CallSite so we include invokes in the analysis.
2. Added test case with an invoke to show a transform.

[spatel]

Ping.

Like D27114, this isn't adding nonnull where there was none before; it's just using what's already available. So we don't need to hold this up for clang?

PR31512 doesn't represent Philip's request anymore, so I opened PR31929 for that:
https://llvm.org/bugs/show_bug.cgi?id=31929

[reames]

LGTM

test/Analysis/ValueTracking/known-nonnull-at.ll

76

Minor: We can actually fold the null_check on this path because the call dominates the *use*. However, you can happily ignore that. :)

[spatel]

test/Analysis/ValueTracking/known-nonnull-at.ll

76

Nice catch! I think we can't do that with -instsimplify because it requires modifying the ret insts, but -gvn does the job:

$ ./opt -gvn nullch.ll -S
...

define i1 @caller5(i8* %x, i8* %y) {
  %null_check = icmp eq i8* %y, null
  br i1 %null_check, label %t, label %f

t:                                                ; preds = %0
  ret i1 true

f:                                                ; preds = %0
  call void @bar(i8* %x, i8* %y)
  ret i1 false
}

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
                               bool OrZero = false, unsigned Depth = 0,
                               AssumptionCache *AC = nullptr,
                               const Instruction *CxtI = nullptr,
                               const DominatorTree *DT = nullptr);
 
   /// Return true if the given value is known to be non-zero when defined. For
   /// vectors, return true if every element is known to be non-zero when
-  /// defined. Supports values with integer or pointer type and vectors of
-  /// integers.
+  /// defined. For pointers, if the context instruction and dominator tree are
+  /// specified, perform context-sensitive analysis and return true if the
+  /// pointer couldn't possibly be null at the specified instruction.
+  /// Supports values with integer or pointer type and vectors of integers.
   bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
                       AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
                       const DominatorTree *DT = nullptr);
 
   /// Returns true if the give value is known to be non-negative.
   bool isKnownNonNegative(const Value *V, const DataLayout &DL,
                           unsigned Depth = 0,

lib/Analysis/ValueTracking.cpp

ConstantInt *Upper =
         mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
     ConstantRange Range(Lower->getValue(), Upper->getValue());
     if (Range.contains(Value))
       return false;
   }
   return true;
 }
 
-/// Return true if the given value is known to be non-zero when defined.
-/// For vectors return true if every element is known to be non-zero when
-/// defined. Supports values with integer or pointer type and vectors of
-/// integers.
+/// Return true if the given value is known to be non-zero when defined. For
+/// vectors, return true if every element is known to be non-zero when
+/// defined. For pointers, if the context instruction and dominator tree are
+/// specified, perform context-sensitive analysis and return true if the
+/// pointer couldn't possibly be null at the specified instruction.
+/// Supports values with integer or pointer type and vectors of integers.
 bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
   if (auto *C = dyn_cast<Constant>(V)) {
     if (C->isNullValue())
       return false;
     if (isa<ConstantInt>(C))
       // Must be non-zero due to null test above.
       return true;
 
bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
   }
 
   // The remaining tests are all recursive, so bail out if we hit the limit.
   if (Depth++ >= MaxDepth)
     return false;
 
   // Check for pointer simplifications.
   if (V->getType()->isPointerTy()) {
-    if (isKnownNonNull(V))
+    if (isKnownNonNullAt(V, Q.CxtI, Q.DT))
       return true;
     if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V))
       if (isGEPKnownNonNull(GEP, Depth, Q))
         return true;
   }
 
   unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), Q.DL);
 
static bool isKnownNonNullFromDominatingCondition(const Value *V,
   assert(DT && "Dominator tree required for analysis");
 
   unsigned NumUsesExplored = 0;
   for (auto *U : V->users()) {
     // Avoid massive lists
     if (NumUsesExplored >= DomConditionsMaxUses)
       break;
     NumUsesExplored++;
+
+    // If the value is used as an argument to a function call, then argument
+    // attributes may provide an answer about null-ness.
+    if (auto *Call = dyn_cast<CallInst>(U))
+      if (auto *CalledFunc = Call->getCalledFunction())
+        for (Argument &Arg : CalledFunc->args())
+          if (Call->getArgOperand(Arg.getArgNo()) == V &&
+              Arg.hasNonNullAttr() && DT->dominates(Call, CtxI))
+            return true;
+
     // Consider only compare instructions uniquely controlling a branch
     CmpInst::Predicate Pred;
     if (!match(const_cast<User *>(U),
                m_c_ICmp(Pred, m_Specific(V), m_Zero())) ||
         (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE))
       continue;
 
     for (auto *CmpU : U->users()) {
       if (const BranchInst *BI = dyn_cast<BranchInst>(CmpU)) {
         assert(BI->isConditional() && "uses a comparison!");
 
         BasicBlock *NonNullSuccessor =
             BI->getSuccessor(Pred == ICmpInst::ICMP_EQ ? 1 : 0);
         BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
         if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
           return true;
       } else if (Pred == ICmpInst::ICMP_NE &&
                  match(CmpU, m_Intrinsic<Intrinsic::experimental_guard>()) &&
                  DT->dominates(cast<Instruction>(CmpU), CtxI)) {
         return true;
       }
     }
   }
 
   return false;
 }

test/Analysis/ValueTracking/known-nonnull-at.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instsimplify < %s | FileCheck %s
 
 declare void @bar(i8* %a, i8* nonnull %b)
 
 ; 'y' must be nonnull.
 
 define i1 @caller1(i8* %x, i8* %y) {
 ; CHECK-LABEL: @caller1(
 ; CHECK-NEXT:    call void @bar(i8* %x, i8* %y)
-; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %y, null
-; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
+; CHECK-NEXT:    ret i1 false
 ;
   call void @bar(i8* %x, i8* %y)
   %null_check = icmp eq i8* %y, null
   ret i1 %null_check
 }
 
 ; Don't know anything about 'y'.
 
 define i1 @caller2(i8* %x, i8* %y) {
 ; CHECK-LABEL: @caller2(
 ; CHECK-NEXT:    call void @bar(i8* %y, i8* %x)
 ; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %y, null
 ; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
 ;
   call void @bar(i8* %y, i8* %x)
   %null_check = icmp eq i8* %y, null
   ret i1 %null_check
 }
 
 ; 'y' must be nonnull.
 
 define i1 @caller3(i8* %x, i8* %y) {
 ; CHECK-LABEL: @caller3(
 ; CHECK-NEXT:    call void @bar(i8* %x, i8* %y)
-; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp ne i8* %y, null
-; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
+; CHECK-NEXT:    ret i1 true
 ;
   call void @bar(i8* %x, i8* %y)
   %null_check = icmp ne i8* %y, null
   ret i1 %null_check
 }
 
-; Don't know anything about 'y'.
+; FIXME: The call is guaranteed to execute, so 'y' must be nonnull throughout.
 
 define i1 @caller4(i8* %x, i8* %y) {
 ; CHECK-LABEL: @caller4(
-; CHECK-NEXT:    call void @bar(i8* %y, i8* %x)
 ; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp ne i8* %y, null
+; CHECK-NEXT:    call void @bar(i8* %x, i8* %y)
 ; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
 ;
-  call void @bar(i8* %y, i8* %x)
   %null_check = icmp ne i8* %y, null
+  call void @bar(i8* %x, i8* %y)
+  ret i1 %null_check
+}
+
+; The call to bar() does not dominate the null check, so no change.
+
+define i1 @caller5(i8* %x, i8* %y) {
+; CHECK-LABEL: @caller5(
+; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %y, null
+; CHECK-NEXT:    br i1 [[NULL_CHECK]], label %t, label %f
+; CHECK:       t:
+; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
+; CHECK:       f:
+; CHECK-NEXT:    call void @bar(i8* %x, i8* %y)
+; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
+;
+  %null_check = icmp eq i8* %y, null
+  br i1 %null_check, label %t, label %f
+t:
+  ret i1 %null_check
+f:
+  call void @bar(i8* %x, i8* %y)
   ret i1 %null_check
 }
 

test/Transforms/InstCombine/call_nonnull_arg.ll

 }
 
 declare void @bar(i8*, i8* nonnull)
 declare void @baz(i8*, i8*)
 
 define void @deduce_nonnull_from_another_call(i8* %a, i8* %b) {
 ; CHECK-LABEL: @deduce_nonnull_from_another_call(
 ; CHECK-NEXT:    call void @bar(i8* %a, i8* %b)
-; CHECK-NEXT:    call void @baz(i8* %b, i8* %b)
+; CHECK-NEXT:    call void @baz(i8* nonnull %b, i8* nonnull %b)
 ; CHECK-NEXT:    ret void
 ;
   call void @bar(i8* %a, i8* %b)
   call void @baz(i8* %b, i8* %b)
   ret void
 }