diff --git a/llvm/include/llvm/Analysis/CaptureTracking.h b/llvm/include/llvm/Analysis/CaptureTracking.h --- a/llvm/include/llvm/Analysis/CaptureTracking.h +++ b/llvm/include/llvm/Analysis/CaptureTracking.h @@ -87,8 +87,11 @@ /// isDereferenceableOrNull - Overload to allow clients with additional /// knowledge about pointer dereferenceability to provide it and thereby - /// avoid conservative responses when a pointer is compared to null. - virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL); + /// avoid conservative responses when pointers are compared. The flag + /// \p AllowNull indicates if the pointer has to be dereferenceable or + /// if "null" is OK as well. + virtual bool isDereferenceableOrNull(const Value *O, const DataLayout &DL, + bool AllowNull); }; /// PointerMayBeCaptured - Visit the value and the values derived from it and diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp --- a/llvm/lib/Analysis/CaptureTracking.cpp +++ b/llvm/lib/Analysis/CaptureTracking.cpp @@ -33,20 +33,19 @@ bool CaptureTracker::shouldExplore(const Use *U) { return true; } -bool CaptureTracker::isDereferenceableOrNull(Value *O, const DataLayout &DL) { - // An inbounds GEP can either be a valid pointer (pointing into - // or to the end of an allocation), or be null in the default - // address space. So for an inbounds GEP there is no way to let - // the pointer escape using clever GEP hacking because doing so - // would make the pointer point outside of the allocated object - // and thus make the GEP result a poison value. Similarly, other - // dereferenceable pointers cannot be manipulated without producing - // poison. - if (auto *GEP = dyn_cast(O)) - if (GEP->isInBounds()) - return true; +bool CaptureTracker::isDereferenceableOrNull(const Value *O, + const DataLayout &DL, + bool AllowNull) { + if (AllowNull && isa(O)) + return true; + bool CanBeNull; - return O->getPointerDereferenceableBytes(DL, CanBeNull); + if (!O->getPointerDereferenceableBytes(DL, CanBeNull)) + return false; + + // If we have dereferenceable bytes we have to exclude the "_or_null" part if + // it is not allowed. + return AllowNull || !CanBeNull; } namespace { @@ -347,28 +346,44 @@ AddUses(I); break; case Instruction::ICmp: { - unsigned Idx = (I->getOperand(0) == V) ? 0 : 1; - unsigned OtherIdx = 1 - Idx; - if (auto *CPN = dyn_cast(I->getOperand(OtherIdx))) { - // Don't count comparisons of a no-alias return value against null as - // captures. This allows us to ignore comparisons of malloc results - // with null, for example. - if (CPN->getType()->getAddressSpace() == 0) - if (isNoAliasCall(V->stripPointerCasts())) - break; - if (!I->getFunction()->nullPointerIsDefined()) { - auto *O = I->getOperand(Idx)->stripPointerCastsSameRepresentation(); - // Comparing a dereferenceable_or_null pointer against null cannot - // lead to pointer escapes, because if it is not null it must be a - // valid (in-bounds) pointer. - if (Tracker->isDereferenceableOrNull(O, I->getModule()->getDataLayout())) - break; - } - } + unsigned OtherIdx = (I->getOperand(0) == V) ? 1 : 0; + const Value *Op0 = V->stripPointerCastsSameRepresentation(); + const Value *Op1 = I->getOperand(OtherIdx)->stripPointerCastsSameRepresentation(); + const DataLayout &DL = I->getModule()->getDataLayout(); + bool NullIsDefinedOp0 = NullPointerIsDefined( + I->getFunction(), V->getType()->getPointerAddressSpace()); + + // If the two pointers compared are both the result of an allocation or + // pointing into/to the end of an allocation, hence: + // - dereferenceable pointers, + // - noalias return pointers, (including the unique value potentiall + // resulting from a malloc(0) call) + // - null, (if null is not a valid pointer) + // then there are no "bit-tricks" possible to learn about the pointer + // bits. Put differently, one cannot learn about a pointer in these + // category because one cannot manipulate the other pointer freely while + // keeping it in these categories. So the "other pointer" is either + // "fixed" (null or something and special returned by malloc(0)) or for + // the most part not controllable, e.g., the "random" allocation location + // (alloc, malloc, etc.) which only allows manipulation of a few bits up + // to the (log of the) allocation size. + // + // TODO: We should think about moving the isNoAliasCall check into + // Value::getPointerDereferenceableBytes as it implies + // dereferenceable_or_null(1) assuming malloc(0) does return NULL. + bool IsDerefOrNoAlias0 = + isNoAliasCall(Op0) || + Tracker->isDereferenceableOrNull(Op0, DL, !NullIsDefinedOp0); + bool IsDerefOrNoAlias1 = + isNoAliasCall(Op1) || + Tracker->isDereferenceableOrNull(Op1, DL, !NullIsDefinedOp0); + if (IsDerefOrNoAlias0 && IsDerefOrNoAlias1) + break; + // Comparison against value stored in global variable. Given the pointer // does not escape, its value cannot be guessed and stored separately in a // global variable. - auto *LI = dyn_cast(I->getOperand(OtherIdx)); + auto *LI = dyn_cast(Op1); if (LI && isa(LI->getPointerOperand())) break; // Otherwise, be conservative. There are crazy ways to capture pointers diff --git a/llvm/lib/Analysis/Loads.cpp b/llvm/lib/Analysis/Loads.cpp --- a/llvm/lib/Analysis/Loads.cpp +++ b/llvm/lib/Analysis/Loads.cpp @@ -66,15 +66,6 @@ return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size, DL, CtxI, DT, Visited); - bool CheckForNonNull = false; - APInt KnownDerefBytes(Size.getBitWidth(), - V->getPointerDereferenceableBytes(DL, CheckForNonNull)); - if (KnownDerefBytes.getBoolValue()) { - if (KnownDerefBytes.uge(Size)) - if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) - return isAligned(V, Align, DL); - } - // For GEPs, determine if the indexing lands within the allocated object. if (const GEPOperator *GEP = dyn_cast(V)) { const Value *Base = GEP->getPointerOperand(); @@ -97,6 +88,15 @@ DL, CtxI, DT, Visited); } + bool CheckForNonNull = false; + APInt KnownDerefBytes(Size.getBitWidth(), + V->getPointerDereferenceableBytes(DL, CheckForNonNull)); + if (KnownDerefBytes.getBoolValue()) { + if (KnownDerefBytes.uge(Size)) + if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) + return isAligned(V, Align, DL); + } + // For gc.relocate, look through relocations if (const GCRelocateInst *RelocateInst = dyn_cast(V)) return isDereferenceableAndAlignedPointer( diff --git a/llvm/lib/IR/Value.cpp b/llvm/lib/IR/Value.cpp --- a/llvm/lib/IR/Value.cpp +++ b/llvm/lib/IR/Value.cpp @@ -664,6 +664,15 @@ DerefBytes = DL.getTypeStoreSize(AI->getAllocatedType()); CanBeNull = false; } + } else if (auto *GEP = dyn_cast(this)) { + if (GEP->isInBounds()) { + APInt OffsetAPInt(DL.getIndexTypeSizeInBits(GEP->getType()), 0); + GEP->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, false); + if (OffsetAPInt != 0) { + DerefBytes = OffsetAPInt.getZExtValue(); + CanBeNull = false; + } + } } else if (auto *GV = dyn_cast(this)) { if (GV->getValueType()->isSized() && !GV->hasExternalWeakLinkage()) { // TODO: Don't outright reject hasExternalWeakLinkage but set the diff --git a/llvm/test/Analysis/ValueTracking/memory-dereferenceable.ll b/llvm/test/Analysis/ValueTracking/memory-dereferenceable.ll --- a/llvm/test/Analysis/ValueTracking/memory-dereferenceable.ll +++ b/llvm/test/Analysis/ValueTracking/memory-dereferenceable.ll @@ -94,7 +94,7 @@ %within_allocation = getelementptr inbounds %struct.A, %struct.A* @globalstruct, i64 0, i32 0, i64 10 %load11 = load i8, i8* %within_allocation - ; GEP is outside the underlying object size + ; GEP is outside the underlying object size, this is definitively UB (inbounds GEP! and load past an allocation) ; CHECK-NOT: %outside_allocation %outside_allocation = getelementptr inbounds %struct.A, %struct.A* @globalstruct, i64 0, i32 1, i64 10 %load12 = load i8, i8* %outside_allocation diff --git a/llvm/test/Transforms/FunctionAttrs/nocapture.ll b/llvm/test/Transforms/FunctionAttrs/nocapture.ll --- a/llvm/test/Transforms/FunctionAttrs/nocapture.ll +++ b/llvm/test/Transforms/FunctionAttrs/nocapture.ll @@ -295,5 +295,24 @@ ret i1 %2 } +declare noalias i8* @malloc(i32) +declare noalias i32* @malloclike() +; CHECK: define i1 @nocaptureICmp(i32* nocapture readnone dereferenceable(4) %deref) +define i1 @nocaptureICmp(i32* dereferenceable(4) %deref) { + %na1 = call i8* @malloc(i32 2) + %na2 = call i32* @malloclike() + %bc = bitcast i32* %deref to i8* + %cmp1 = icmp sle i8* %bc, %na1 + %cmp2 = icmp ugt i8* %bc, null + %cmp3 = icmp ugt i32* %deref, null + %cmp4 = icmp eq i32* %deref, %na2 + %cmp5 = icmp ne i32* %deref, %deref + %and1 = and i1 %cmp1, %cmp2 + %and2 = and i1 %cmp3, %cmp4 + %and3 = and i1 %and1, %and2 + %and4 = and i1 %and3, %cmp5 + ret i1 %and4 +} + declare i8* @llvm.launder.invariant.group.p0i8(i8*) declare i8* @llvm.strip.invariant.group.p0i8(i8*)