Add some shortcuts in Value Propagation for alloca

[wmi]

Summary

The is the part1 to solve https://llvm.org/bugs/show_bug.cgi?id=10584

Inlining functions called inside of a large loop can introduce many long stretched variables because the alloca instructions inside callee will be promoted to the entry of the caller. Such long stretched variables could increase the compile time of correlated value propagation (CVP) and register allocation significantly (More significantly for value propagation).

The fact that a lot of alloca instructions are promoted can be used to reduce the compile time of CVP. CVP checks non-null for pointer params of each callsite. If we know the def of param is an alloca instruction, we know it is non-null without querying LVI. Similarly, CVP checks constant pointer for each mem access. If the def of the pointer is an alloca instruction, we know it is not a constant pointer without querying LVI. These shortcuts can reduce the cost of CVP significantly.

[davidxl]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

322 ↗

(On Diff #50361)

Maybe add a helper function to make this more readable:

if (mayHaveNullValue(...) && ...

324 ↗

(On Diff #50361)

Have a helper function like:

bool isValueNonNull(V) -- which does simple checks.

So the combined check becomes:

if (mayHaveNullValue(...) && (isValueNonNull(V) || LVI ....)) {
}

Note that isValueNonNull can also handle simple cases with gep:

foo() {

 int a[10];
  ...
  bar(&a[5]);
...

}
we know &a[5] can not be null.

test/Transforms/CorrelatedValuePropagation/alloca.ll

5

not constant --> not null.

[reames]

Really interesting observations and great idea, but the patch is not structured well. In both cases, we're really talking about generic properties of LVI and we should structure it that way. That should help all callers of LVI, not just these two.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

180 ↗

(On Diff #50361)

This should be sunk inside LVI. Specifically, at the top of LazyValueInfo::getConstant.

I'm also not entirely sure this is accurate. I could construct a branch of the form:
if (%alloca == %some_constant_pointer) {
} else { }

Inside the if clause, I could find a constant value for the alloca. It's just that we happen to know that the branch can't be true and thus that we'd only be able to simplify in dead code.

At minimum, we should have a better description here. This is effectively a profitability heuristic more than anything else.

324 ↗

(On Diff #50361)

This is the wrong place. Rather than special casing this particular caller, we should really sink this down into LVI. We could do this in one of two ways:

1. Use the non-context sensative form of isKnownNonNull in getPreciateAt when answering a non-null query.
2. Recognize the fact that the only fact we can infer about a pointer typed value is a constant or non-constant result. The only non-constant we can get - I think - is not-null. We can probably short circuit the search in this case.

[davidxl]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

324 ↗

(On Diff #50361)

I agree with you wrt to the final picture -- but should this be done in stages (to avoid over fixing the problem at hand)? Basically have a local fix now, get it stablized/tested and then move on to a general fix? (I am fine either way)

[wmi]

Addressed David and Philip's comments. Fixed tests under clang/test.

[wmi]

Ping.

[reames]

lib/Analysis/LazyValueInfo.cpp

1381

Use stripPointerCasts

1390

This bail is reasonable. Needs commented and code cleanup, but otherwise ready to go in. (I am purposely *not* saying LGTM yet.)

1512

This check is wrong. Just use ValueTracking

1523

if (V->getType()->isPointerTy() &&
C->isNullValue() && isKnownNonNull(V))

Use isKnownNonNull from ValueTracking.

Comment why this is here. In particular, this is only a fastpath, falling through would be correct.

[wmi]

reames, thanks for the helpful comments. Patch updated as suggested.

[reames]

I just checked in a change which may greatly accelerate LVI for the comparison against null case. Can you check to see if after "267642: [LVI] Reduce compile time by lazily scanning blocks if needed." you're still seeing compile time problems?

The not-constant bypass might still be needed. I'm not entirely sure.

[wmi]

Hi Philip,

I tried r267642 using testcases - Groonga and scribus from PR10584.
The result showed r267642 didn't reduce the compile time much. I
looked at r267642 and found a possible reason was that the first
shortcut of nonnull check took effect only when current BB was the
entry BB so we still needed to iterate CFG, right?

scribus13format.cc (scribus):
r266775: 57.89s
r266775 + r267642: 56.05s
r266775 + patch here: 31.17s

expr.c (Groonga):
r266775: 226.03s
r266775 + r267642: 225.32s
r266775 + patch here: 44.10s

Thanks,
Wei.

[wmi]

Sorry for not visiting the patch for a long time. I just evaluated the original testcase on trunk. The compile time issue was still there, and the patch would still help. Philip, maybe it is still worth to consider the patch since the simple shortcut patch will not bring any harm?

[reames]

Sorry for being unresponsive for so long. This has reached the top of my queue again.

I'm still not entirely happy with this patch, mostly because I don't feel I understand *why* it makes such a huge difference, but I've also held this up for much too long. This is a reasonable approach to a real problem and we can iterate in tree if needed.

LGTM.

lib/Analysis/LazyValueInfo.cpp

1380

Add
/// Returns true if we can statically tell that this value will never be a "useful" constant. In practice, this means we've got something like an alloca or a malloc call for which a comparison against a constant can only be guarding dead code. Note that we are potentially giving up some precision here (a constant result) in favour of avoiding a expensive search for a easily answered common query.

lib/Analysis/LazyValueInfo.cpp

 void LazyValueInfo::releaseMemory() {
   // If the cache was allocated, free it.
   if (PImpl) {
     delete &getCache(PImpl, AC, nullptr);
     PImpl = nullptr;
   }
 }
 
+static bool isKnownNonConstant(Value *V) {
+  BitCastInst *CastInst;
+  if (isa<AllocaInst>(V) || ((CastInst = dyn_cast<BitCastInst>(V)) &&
+                             isa<AllocaInst>(CastInst->getOperand(0))))
+    return true;
+  return false;
+}
+
 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
                                      Instruction *CxtI) {
+  if (isKnownNonConstant(V))
+    return nullptr;
+
   const DataLayout &DL = BB->getModule()->getDataLayout();
   LVILatticeVal Result =
       getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
 
   if (Result.isConstant())
     return Result.getConstant();
   if (Result.isConstantRange()) {
     ConstantRange CR = Result.getConstantRange();
LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
                                   Instruction *CxtI) {
   const DataLayout &DL = FromBB->getModule()->getDataLayout();
   LVILatticeVal Result =
       getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
 
   return getPredicateResult(Pred, C, Result, DL, TLI);
 }
 
+static bool isKnownNonNull(Value *V) {
+  BitCastInst *CastInst;
+  if (isa<AllocaInst>(V) || ((CastInst = dyn_cast<BitCastInst>(V)) &&
+                             isa<AllocaInst>(CastInst->getOperand(0))))
+    return true;
+  if (isa<GetElementPtrInst>(V) ||
+      ((CastInst = dyn_cast<BitCastInst>(V)) &&
+       isa<GetElementPtrInst>(CastInst->getOperand(0))))
+    return true;
+  return false;
+}
+
 LazyValueInfo::Tristate
 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
                               Instruction *CxtI) {
+  PointerType *Type;
+  if ((Type = dyn_cast<PointerType>(V->getType())) &&
+      (C == ConstantPointerNull::get(Type)) && isKnownNonNull(V)) {
+    if (Pred == ICmpInst::ICMP_EQ)
+      return LazyValueInfo::False;
+    else if (Pred == ICmpInst::ICMP_NE)
+      return LazyValueInfo::True;
+  }
   const DataLayout &DL = CxtI->getModule()->getDataLayout();
   LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
   Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
   if (Ret != Unknown)
     return Ret;
 
   // Note: The following bit of code is somewhat distinct from the rest of LVI;
   // LVI as a whole tries to compute a lattice value which is conservatively

test/CodeGen/builtins-arm.c

 // CHECK: call {{.*}} @llvm.arm.rbit(i32 %a)
 
 unsigned rbit(unsigned a) {
   return __builtin_arm_rbit(a);
 }
 
 void prefetch(int i) {
   __builtin_arm_prefetch(&i, 0, 1);
-// CHECK: call {{.*}} @llvm.prefetch(i8* %{{.*}}, i32 0, i32 3, i32 1)
+// CHECK: call {{.*}} @llvm.prefetch(i8* nonnull %{{.*}}, i32 0, i32 3, i32 1)
 
   __builtin_arm_prefetch(&i, 1, 1);
-// CHECK: call {{.*}} @llvm.prefetch(i8* %{{.*}}, i32 1, i32 3, i32 1)
+// CHECK: call {{.*}} @llvm.prefetch(i8* nonnull %{{.*}}, i32 1, i32 3, i32 1)
 
 
   __builtin_arm_prefetch(&i, 1, 0);
-// CHECK: call {{.*}} @llvm.prefetch(i8* %{{.*}}, i32 1, i32 3, i32 0)
+// CHECK: call {{.*}} @llvm.prefetch(i8* nonnull %{{.*}}, i32 1, i32 3, i32 0)
 }
 
 unsigned mrc() {
   // CHECK: define i32 @mrc()
   // CHECK: [[R:%.*]] = {{.*}} call i32 @llvm.arm.mrc(i32 15, i32 0, i32 13, i32 0, i32 3)
   // CHECK-NEXT: ret i32 [[R]]
   return __builtin_arm_mrc(15, 0, 13, 0, 3);
 }

test/CodeGen/cleanup-destslot-simple.c

 // RUN: %clang_cc1 -O1 -triple x86_64-none-linux-gnu -emit-llvm -debug-info-kind=line-tables-only %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=LIFETIME
 
 // We shouldn't have markers at -O0 or with msan.
 // RUN: %clang_cc1 -O0 -triple x86_64-none-linux-gnu -emit-llvm -debug-info-kind=line-tables-only %s -o - | FileCheck %s --check-prefix=CHECK
 // RUN: %clang_cc1 -O1 -triple x86_64-none-linux-gnu -emit-llvm -debug-info-kind=line-tables-only %s -o - -fsanitize=memory | FileCheck %s --check-prefix=CHECK
 
 // There is no exception to handle here, lifetime.end is not a destructor,
 // so there is no need have cleanup dest slot related code
 // CHECK-LABEL: define i32 @test
 int test() {
   int x = 3;
   int *volatile p = &x;
   return *p;
 // CHECK: [[X:%.*]] = alloca i32
 // CHECK: [[P:%.*]] = alloca i32*
-// LIFETIME: call void @llvm.lifetime.start(i64 4, i8* %{{.*}}){{( #[0-9]+)?}}, !dbg
-// LIFETIME: call void @llvm.lifetime.start(i64 8, i8* %{{.*}}){{( #[0-9]+)?}}, !dbg
+// LIFETIME: call void @llvm.lifetime.start(i64 4, i8* nonnull %{{.*}}){{( #[0-9]+)?}}, !dbg
+// LIFETIME: call void @llvm.lifetime.start(i64 8, i8* nonnull %{{.*}}){{( #[0-9]+)?}}, !dbg
 // CHECK-NOT: store i32 %{{.*}}, i32* %cleanup.dest.slot
 // LIFETIME: call void @llvm.lifetime.end(i64 8, {{.*}}){{( #[0-9]+)?}}, !dbg
 // LIFETIME: call void @llvm.lifetime.end(i64 4, {{.*}}){{( #[0-9]+)?}}, !dbg
 }

test/CodeGen/tbaa-struct.cpp

struct B {
   struct A a;
   int ii;
 };
 
 void copy2(struct B *a, struct B *b) {
   *a = *b;
 }
 
-// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %{{.*}}, i8* %{{.*}}, i64 24, i32 4, i1 false), !tbaa.struct [[TS2:!.*]]
+// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull %{{.*}}, i8* nonnull %{{.*}}, i64 24, i32 4, i1 false), !tbaa.struct [[TS2:!.*]]
 
 typedef _Complex int T2;
 typedef _Complex char T5;
 typedef _Complex int T7;
 typedef struct T4 { T5 field0; T7 field1; } T4;
 typedef union T1 { T2 field0; T4 field1; } T1;
 
 void copy3 (T1 *a, T1 *b) {
   *a = *b;
 }
 
-// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %{{.*}}, i8* %{{.*}}, i64 12, i32 4, i1 false), !tbaa.struct [[TS3:!.*]]
+// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull %{{.*}}, i8* nonnull %{{.*}}, i64 12, i32 4, i1 false), !tbaa.struct [[TS3:!.*]]
 
 // Make sure that zero-length bitfield works.
 #define ATTR __attribute__ ((ms_struct))
 struct five {
   char a;
   int :0;        /* ignored; prior field is not a bitfield. */
   char b;
   char c;
 } ATTR;
 void copy4(struct five *a, struct five *b) {
   *a = *b;
 }
-// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %{{.*}}, i8* %{{.*}}, i64 3, i32 1, i1 false), !tbaa.struct [[TS4:!.*]]
+// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull %{{.*}}, i8* nonnull %{{.*}}, i64 3, i32 1, i1 false), !tbaa.struct [[TS4:!.*]]
 
 struct six {
   char a;
   int :0;
   char b;
   char c;
 };
 void copy5(struct six *a, struct six *b) {
   *a = *b;
 }
-// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %{{.*}}, i8* %{{.*}}, i64 6, i32 1, i1 false), !tbaa.struct [[TS5:!.*]]
+// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull %{{.*}}, i8* nonnull %{{.*}}, i64 6, i32 1, i1 false), !tbaa.struct [[TS5:!.*]]
 
 // CHECK: [[TS]] = !{i64 0, i64 2, !{{.*}}, i64 4, i64 4, !{{.*}}, i64 8, i64 1, !{{.*}}, i64 12, i64 4, !{{.*}}}
 // CHECK: [[CHAR:!.*]] = !{!"omnipotent char", !{{.*}}}
 // CHECK: [[TAG_INT:!.*]] = !{[[INT:!.*]], [[INT]], i64 0}
 // CHECK: [[INT]] = !{!"int", [[CHAR]]
 // CHECK: [[TAG_CHAR:!.*]] = !{[[CHAR]], [[CHAR]], i64 0}
 // (offset, size) = (0,1) char; (4,2) short; (8,4) int; (12,1) char; (16,4) int; (20,4) int
 // CHECK: [[TS2]] = !{i64 0, i64 1, !{{.*}}, i64 4, i64 2, !{{.*}}, i64 8, i64 4, !{{.*}}, i64 12, i64 1, !{{.*}}, i64 16, i64 4, {{.*}}, i64 20, i64 4, {{.*}}}
 // (offset, size) = (0,8) char; (0,2) char; (4,8) char
 // CHECK: [[TS3]] = !{i64 0, i64 8, !{{.*}}, i64 0, i64 2, !{{.*}}, i64 4, i64 8, !{{.*}}}
 // CHECK: [[TS4]] = !{i64 0, i64 1, [[TAG_CHAR]], i64 1, i64 4, [[TAG_INT]], i64 1, i64 1, [[TAG_CHAR]], i64 2, i64 1, [[TAG_CHAR]]}
 // CHECK: [[TS5]] = !{i64 0, i64 1, [[TAG_CHAR]], i64 4, i64 4, [[TAG_INT]], i64 4, i64 1, [[TAG_CHAR]], i64 5, i64 1, [[TAG_CHAR]]}

test/CodeGenCXX/microsoft-abi-dynamic-cast.cpp

 T* test2(A* x) { return &dynamic_cast<T&>(*x); }
 // CHECK-LABEL: define %struct.T* @"\01?test2@@YAPAUT@@PAUA@@@Z"(%struct.A* %x)
 // CHECK:        [[CAST:%.*]] = bitcast %struct.A* %x to i8*
 // CHECK-NEXT:   [[VBPTRPTR:%.*]] = getelementptr inbounds %struct.A, %struct.A* %x, i32 0, i32 0
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBPTRPTR]], align 4
 // CHECK-NEXT:   [[VBOFFP:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBOFFS:%.*]] = load i32, i32* [[VBOFFP]], align 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[CAST]], i32 [[VBOFFS]]
-// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* [[ADJ]], i32 [[VBOFFS]], i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUA@@@8" to i8*), i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 1)
+// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* nonnull [[ADJ]], i32 [[VBOFFS]], i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUA@@@8" to i8*), i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 1)
 // CHECK-NEXT:   [[RET:%.*]] = bitcast i8* [[CALL]] to %struct.T*
 // CHECK-NEXT:   ret %struct.T* [[RET]]
 
 T* test3(B* x) { return &dynamic_cast<T&>(*x); }
 // CHECK-LABEL: define %struct.T* @"\01?test3@@YAPAUT@@PAUB@@@Z"(%struct.B* %x)
 // CHECK:        [[VOIDP:%.*]] = getelementptr inbounds %struct.B, %struct.B* %x, i32 0, i32 0, i32 0
 // CHECK-NEXT:   [[VBPTR:%.*]] = getelementptr inbounds i8, i8* [[VOIDP]], i32 4
 // CHECK-NEXT:   [[VBPTRPTR:%.*]] = bitcast i8* [[VBPTR:%.*]] to i32**
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBPTRPTR]], align 4
 // CHECK-NEXT:   [[VBOFFP:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBOFFS:%.*]] = load i32, i32* [[VBOFFP]], align 4
 // CHECK-NEXT:   [[DELTA:%.*]] = add nsw i32 [[VBOFFS]], 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[VOIDP]], i32 [[DELTA]]
-// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* [[ADJ]], i32 [[DELTA]], i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUB@@@8" to i8*), i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 1)
+// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* nonnull [[ADJ]], i32 [[DELTA]], i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUB@@@8" to i8*), i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 1)
 // CHECK-NEXT:   [[RET:%.*]] = bitcast i8* [[CALL]] to %struct.T*
 // CHECK-NEXT:   ret %struct.T* [[RET]]
 
 T* test4(V* x) { return dynamic_cast<T*>(x); }
 // CHECK-LABEL: define %struct.T* @"\01?test4@@YAPAUT@@PAUV@@@Z"(%struct.V* %x)
 // CHECK:        [[CAST:%.*]] = bitcast %struct.V* %x to i8*
 // CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* [[CAST]], i32 0, i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUV@@@8" to i8*), i8* bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 0)
 // CHECK-NEXT:   [[RET:%.*]] = bitcast i8* [[CALL]] to %struct.T*
 // CHECK-NEXT:   ret %struct.T* [[RET]]
 
 T* test5(A* x) { return dynamic_cast<T*>(x); }
 // CHECK-LABEL: define %struct.T* @"\01?test5@@YAPAUT@@PAUA@@@Z"(%struct.A* %x)
 // CHECK:        [[CHECK:%.*]] = icmp eq %struct.A* %x, null
 // CHECK-NEXT:   br i1 [[CHECK]]
 // CHECK:        [[VOIDP:%.*]] = bitcast %struct.A* %x to i8*
 // CHECK-NEXT:   [[VBPTRPTR:%.*]] = getelementptr inbounds %struct.A, %struct.A* %x, i32 0, i32 0
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBPTRPTR]], align 4
 // CHECK-NEXT:   [[VBOFFP:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBOFFS:%.*]] = load i32, i32* [[VBOFFP]], align 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[VOIDP]], i32 [[VBOFFS]]
-// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* [[ADJ]], i32 [[VBOFFS]], i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUA@@@8" to i8*), i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 0)
+// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* nonnull [[ADJ]], i32 [[VBOFFS]], i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUA@@@8" to i8*), i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 0)
 // CHECK-NEXT:   [[RES:%.*]] = bitcast i8* [[CALL]] to %struct.T*
 // CHECK-NEXT:   br label
 // CHECK:        [[RET:%.*]] = phi %struct.T*
 // CHECK-NEXT:   ret %struct.T* [[RET]]
 
 T* test6(B* x) { return dynamic_cast<T*>(x); }
 // CHECK-LABEL: define %struct.T* @"\01?test6@@YAPAUT@@PAUB@@@Z"(%struct.B* %x)
 // CHECK:        [[CHECK:%.*]] = icmp eq %struct.B* %x, null
 // CHECK-NEXT:   br i1 [[CHECK]]
 // CHECK:        [[CAST:%.*]] = getelementptr inbounds %struct.B, %struct.B* %x, i32 0, i32 0, i32 0
 // CHECK-NEXT:   [[VBPTR:%.*]] = getelementptr inbounds i8, i8* [[CAST]], i32 4
 // CHECK-NEXT:   [[VBPTRPTR:%.*]] = bitcast i8* [[VBPTR]] to i32**
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBPTRPTR]], align 4
 // CHECK-NEXT:   [[VBOFFP:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBOFFS:%.*]] = load i32, i32* [[VBOFFP]], align 4
 // CHECK-NEXT:   [[DELTA:%.*]] = add nsw i32 [[VBOFFS]], 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[CAST]], i32 [[DELTA]]
-// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* [[ADJ]], i32 [[DELTA]], i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUB@@@8" to i8*), i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 0)
+// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTDynamicCast(i8* nonnull [[ADJ]], i32 [[DELTA]], i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUB@@@8" to i8*), i8* {{.*}}bitcast (%rtti.TypeDescriptor7* @"\01??_R0?AUT@@@8" to i8*), i32 0)
 // CHECK-NEXT:   [[RES:%.*]] = bitcast i8* [[CALL]] to %struct.T*
 // CHECK-NEXT:   br label
 // CHECK:        [[RET:%.*]] = phi %struct.T*
 // CHECK-NEXT:   ret %struct.T* [[RET]]
 
 void* test7(V* x) { return dynamic_cast<void*>(x); }
 // CHECK-LABEL: define i8* @"\01?test7@@YAPAXPAUV@@@Z"(%struct.V* %x)
 // CHECK:        [[CAST:%.*]] = bitcast %struct.V* %x to i8*
 // CHECK-NEXT:   [[RET:%.*]] = tail call i8* @__RTCastToVoid(i8* [[CAST]])
 // CHECK-NEXT:   ret i8* [[RET]]
 
 void* test8(A* x) { return dynamic_cast<void*>(x); }
 // CHECK-LABEL: define i8* @"\01?test8@@YAPAXPAUA@@@Z"(%struct.A* %x)
 // CHECK:        [[CHECK:%.*]] = icmp eq %struct.A* %x, null
 // CHECK-NEXT:   br i1 [[CHECK]]
 // CHECK:        [[VOIDP:%.*]] = bitcast %struct.A* %x to i8*
 // CHECK-NEXT:   [[VBPTRPTR:%.*]] = getelementptr inbounds %struct.A, %struct.A* %x, i32 0, i32 0
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBPTRPTR]], align 4
 // CHECK-NEXT:   [[VBOFFP:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBOFFS:%.*]] = load i32, i32* [[VBOFFP]], align 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[VOIDP]], i32 [[VBOFFS]]
-// CHECK-NEXT:   [[RES:%.*]] = tail call i8* @__RTCastToVoid(i8* [[ADJ]])
+// CHECK-NEXT:   [[RES:%.*]] = tail call i8* @__RTCastToVoid(i8* nonnull [[ADJ]])
 // CHECK-NEXT:   br label
 // CHECK:        [[RET:%.*]] = phi i8*
 // CHECK-NEXT:   ret i8* [[RET]]
 
 void* test9(B* x) { return dynamic_cast<void*>(x); }
 // CHECK-LABEL: define i8* @"\01?test9@@YAPAXPAUB@@@Z"(%struct.B* %x)
 // CHECK:        [[CHECK:%.*]] = icmp eq %struct.B* %x, null
 // CHECK-NEXT:   br i1 [[CHECK]]
 // CHECK:        [[CAST:%.*]] = getelementptr inbounds %struct.B, %struct.B* %x, i32 0, i32 0, i32 0
 // CHECK-NEXT:   [[VBPTR:%.*]] = getelementptr inbounds i8, i8* [[CAST]], i32 4
 // CHECK-NEXT:   [[VBPTRPTR:%.*]] = bitcast i8* [[VBPTR]] to i32**
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBPTRPTR]], align 4
 // CHECK-NEXT:   [[VBOFFP:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBOFFS:%.*]] = load i32, i32* [[VBOFFP]], align 4
 // CHECK-NEXT:   [[DELTA:%.*]] = add nsw i32 [[VBOFFS]], 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[CAST]], i32 [[DELTA]]
-// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTCastToVoid(i8* [[ADJ]])
+// CHECK-NEXT:   [[CALL:%.*]] = tail call i8* @__RTCastToVoid(i8* nonnull [[ADJ]])
 // CHECK-NEXT:   br label
 // CHECK:        [[RET:%.*]] = phi i8*
 // CHECK-NEXT:   ret i8* [[RET]]
 
 namespace PR25606 {
 struct Cleanup {
   ~Cleanup();
 };

test/CodeGenCXX/microsoft-abi-typeid.cpp

 // CHECK:        tail call i8* @__RTtypeid(i8* null)
 // CHECK-NEXT:   unreachable
 // CHECK:        [[THIS:%.*]] = bitcast %struct.A* [[CALL]] to i8*
 // CHECK-NEXT:   [[VBTBLP:%.*]] = getelementptr inbounds %struct.A, %struct.A* [[CALL]], i32 0, i32 0
 // CHECK-NEXT:   [[VBTBL:%.*]] = load i32*, i32** [[VBTBLP]], align 4
 // CHECK-NEXT:   [[VBSLOT:%.*]] = getelementptr inbounds i32, i32* [[VBTBL]], i32 1
 // CHECK-NEXT:   [[VBASE_OFFS:%.*]] = load i32, i32* [[VBSLOT]], align 4
 // CHECK-NEXT:   [[ADJ:%.*]] = getelementptr inbounds i8, i8* [[THIS]], i32 [[VBASE_OFFS]]
-// CHECK-NEXT:   [[RT:%.*]] = tail call i8* @__RTtypeid(i8* [[ADJ]])
+// CHECK-NEXT:   [[RT:%.*]] = tail call i8* @__RTtypeid(i8* nonnull [[ADJ]])
 // CHECK-NEXT:   [[RET:%.*]] = bitcast i8* [[RT]] to %struct.type_info*
 // CHECK-NEXT:   ret %struct.type_info* [[RET]]
 
 const std::type_info* test4_typeid() { return &typeid(b); }
 // CHECK: define %struct.type_info* @"\01?test4_typeid@@YAPBUtype_info@@XZ"()
 // CHECK:   ret %struct.type_info* bitcast (%rtti.TypeDescriptor2* @"\01??_R0H@8" to %struct.type_info*)
 
 const std::type_info* test5_typeid() { return &typeid(v); }

test/CodeGenCXX/nrvo.cpp

 
 // rdar://problem/10430868
 // CHECK-LABEL: define void @_Z5test6v
 X test6() {
   X a __attribute__((aligned(8)));
   return a;
   // CHECK:      [[A:%.*]] = alloca [[X:%.*]], align 8
   // CHECK-NEXT: [[PTR:%.*]] = getelementptr inbounds %class.X, %class.X* [[A]], i32 0, i32 0
-  // CHECK-NEXT: call void @llvm.lifetime.start(i64 1, i8* [[PTR]])
+  // CHECK-NEXT: call void @llvm.lifetime.start(i64 1, i8* nonnull [[PTR]])
   // CHECK-NEXT: call {{.*}} @_ZN1XC1Ev([[X]]* nonnull [[A]])
   // CHECK-NEXT: call {{.*}} @_ZN1XC1ERKS_([[X]]* {{%.*}}, [[X]]* nonnull dereferenceable({{[0-9]+}}) [[A]])
   // CHECK-NEXT: call {{.*}} @_ZN1XD1Ev([[X]]* nonnull [[A]])
-  // CHECK-NEXT: call void @llvm.lifetime.end(i64 1, i8* [[PTR]])
+  // CHECK-NEXT: call void @llvm.lifetime.end(i64 1, i8* nonnull [[PTR]])
   // CHECK-NEXT: ret void
 }
 
 // CHECK-LABEL: define void @_Z5test7b
 X test7(bool b) {
   // CHECK: tail call {{.*}} @_ZN1XC1Ev
   // CHECK-NEXT: ret
   if (b) {

test/CodeGenObjC/exceptions.m

 // Test that the cleanup destination is saved when entering a finally
 // block.  rdar://problem/8293901
 // CHECK-LABEL: define void @f3()
 void f3() {
   extern void f3_helper(int, int*);
 
   // CHECK:      [[X:%.*]] = alloca i32
   // CHECK:      [[XPTR:%.*]] = bitcast i32* [[X]] to i8*
-  // CHECK:      call void @llvm.lifetime.start(i64 4, i8* [[XPTR]])
+  // CHECK:      call void @llvm.lifetime.start(i64 4, i8* nonnull [[XPTR]])
   // CHECK:      store i32 0, i32* [[X]]
   int x = 0;
 
   // CHECK:      call void @objc_exception_try_enter(
   // CHECK:      call i32 @_setjmp
   // CHECK-NEXT: icmp eq
   // CHECK-NEXT: br i1
 

test/CodeGenObjCXX/exceptions-legacy.mm

@synchronized(obj) {
     foo();
   }
 }
 // CHECK-LABEL:    define void @_Z5test0P11objc_object(
 //   Enter the @synchronized block.
 // CHECK:      call i32 @objc_sync_enter(i8* [[OBJ:%.*]])
 // CHECK:      call void @objc_exception_try_enter([[BUF_T:%.*]]* nonnull [[BUF:%.*]])
 // CHECK-NEXT: [[T0:%.*]] = getelementptr [[BUF_T]], [[BUF_T]]* [[BUF]], i32 0, i32 0, i32 0
-// CHECK-NEXT: [[T1:%.*]] = call i32 @_setjmp(i32* [[T0]])
+// CHECK-NEXT: [[T1:%.*]] = call i32 @_setjmp(i32* nonnull [[T0]])
 // CHECK-NEXT: [[T2:%.*]] = icmp eq i32 [[T1]], 0
 // CHECK-NEXT: br i1 [[T2]],
 
 //   Body.
 // CHECK:      invoke void @_Z3foov()
 
 //   Leave the @synchronized.  The reload of obj here is unnecessary.
 // CHECK:      call void @objc_exception_try_exit([[BUF_T]]* nonnull [[BUF]])
void test1(id obj, bool *failed) {
   } @catch (...) {
     *failed = true;
   }
 }
 // CHECK-LABEL:    define void @_Z5test1P11objc_objectPb(
 //   Enter the @try block.
 // CHECK:      call void @objc_exception_try_enter([[BUF_T]]* nonnull [[BUF:%.*]])
 // CHECK-NEXT: [[T0:%.*]] = getelementptr [[BUF_T]], [[BUF_T]]* [[BUF]], i32 0, i32 0, i32 0
-// CHECK-NEXT: [[T1:%.*]] = call i32 @_setjmp(i32* [[T0]])
+// CHECK-NEXT: [[T1:%.*]] = call i32 @_setjmp(i32* nonnull [[T0]])
 // CHECK-NEXT: [[T2:%.*]] = icmp eq i32 [[T1]], 0
 // CHECK-NEXT: br i1 [[T2]],
 
 //   Body.
 // CHECK:      invoke void @_Z3foov()
 
 //   Leave the @try.
 // CHECK:      call void @objc_exception_try_exit([[BUF_T]]* nonnull [[BUF]])

test/Transforms/CorrelatedValuePropagation/alloca.ll

+; RUN: opt -S -correlated-propagation -debug-only=lazy-value-info <%s 2>&1 | FileCheck %s
+;
+; Shortcut in Correlated Value Propagation ensures not to take Lazy Value Info
+; analysis for %a.i and %tmp because %a.i is defined by alloca and %tmp is
+; defined by alloca + bitcast. We know the ret value of alloca is nonnull.
+; Similarly because %c is defined by getelementptr, we know %c is nonnull.
+;
+; CHECK-NOT: LVI Getting edge value   %a.i = alloca i64, align 8 at 'for.body'
+; CHECK-NOT: LVI Getting edge value   %c = getelementptr inbounds i64, i64* %b, i64 0 from 'for.cond' to 'for.body'
+; CHECK-NOT: LVI Getting edge value   %tmp = bitcast i64* %a.i to i8* from 'for.cond' to 'for.body'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [8 x i8] c"a = %l\0A\00", align 1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+
+declare void @hoo(i64*)
+
+declare i32 @printf(i8* nocapture readonly, ...)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+define void @goo(i32 %N, i64* %b) {
+entry:
+  %a.i = alloca i64, align 8
+  %tmp = bitcast i64* %a.i to i8*
+  %c = getelementptr inbounds i64, i64* %b, i64 0
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  call void @llvm.lifetime.start(i64 8, i8* %tmp)
+  call void @hoo(i64* %a.i)
+  call void @hoo(i64* %c)
+  %tmp1 = load volatile i64, i64* %a.i, align 8
+  %call.i = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0), i64 %tmp1)
+  call void @llvm.lifetime.end(i64 8, i8* %tmp)
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}