diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -18,6 +18,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallSet.h" #include "llvm/IR/CallSite.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Intrinsics.h" @@ -644,6 +645,18 @@ Optional isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL); + + /// Return true if there cannot be a memory deallocation (aka. free) + /// in-between \p SrcI and \p DstI. Thus, check if there is no direct or + /// transitive "free" call in-between. If \p IsGloballyKnown is true, this + /// method will additionally check if there is the potential for + /// synchronization in-between \p SrcI and \p DstI as a globally known pointer + /// could be passed to a memory deallocation function by another thread. + /// The \p MaxCheckedInstructions limits the number of instructions that are + /// inspected to prove the absence of a memory deallocation. + bool maybeFreedInBetween(const Instruction *SrcI, const Instruction *DstI, + unsigned MaxCheckedInstructions, + bool IsGloballyKnown); } // end namespace llvm #endif // LLVM_ANALYSIS_VALUETRACKING_H diff --git a/llvm/include/llvm/IR/Value.h b/llvm/include/llvm/IR/Value.h --- a/llvm/include/llvm/IR/Value.h +++ b/llvm/include/llvm/IR/Value.h @@ -576,8 +576,12 @@ /// /// If CanBeNull is set by this function the pointer can either be null or be /// dereferenceable up to the returned number of bytes. - uint64_t getPointerDereferenceableBytes(const DataLayout &DL, - bool &CanBeNull) const; + /// + /// If \p DerefKnownBefore is set by this function the dereferenceability + /// information is only known to be valid prior to the \p DerefKnownBefore + /// instructions. + uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, + Instruction *&DerefKnownBefore) const; /// Returns an alignment of the pointer value. /// 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 @@ -350,10 +350,20 @@ break; // Comparing a dereferenceable_or_null argument against null // cannot lead to pointer escapes, because if it is not null it - // must be a valid (in-bounds) pointer. + // must be a valid (in-bounds) pointer. Note that we do care if + // the pointer was freed. bool CanBeNull; - if (O->getPointerDereferenceableBytes(I->getModule()->getDataLayout(), CanBeNull)) - break; + Instruction *DerefKnownBefore; + // TODO: Determine IsGloballyKnown for the maybeFreedInBetween call. + // TODO: Determine a good value for MaxCheckedInstructions in the + // maybeFreedInBetween call. + if (O->getPointerDereferenceableBytes(I->getModule()->getDataLayout(), + CanBeNull, DerefKnownBefore)) + if (!DerefKnownBefore || + !maybeFreedInBetween(DerefKnownBefore, I, + /* MaxCheckedInstructions */ 0, + /* IsGloballyKnown */ true)) + break; } } // Comparison against value stored in global variable. Given the pointer 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,13 +66,22 @@ return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size, DL, CtxI, DT, Visited); + // TODO: Determine IsGloballyKnown for the maybeFreedInBetween call. + // TODO: Determine a good value for MaxCheckedInstructions in the + // maybeFreedInBetween call. + Instruction *DerefKnownBefore; bool CheckForNonNull = false; - APInt KnownDerefBytes(Size.getBitWidth(), - V->getPointerDereferenceableBytes(DL, CheckForNonNull)); + APInt KnownDerefBytes( + Size.getBitWidth(), + V->getPointerDereferenceableBytes(DL, CheckForNonNull, DerefKnownBefore)); if (KnownDerefBytes.getBoolValue()) { if (KnownDerefBytes.uge(Size)) if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) - return isAligned(V, Align, DL); + if (!DerefKnownBefore || + (CtxI && !maybeFreedInBetween(DerefKnownBefore, CtxI, + /* MaxCheckedInstructions */ 0, + /* IsGloballyKnown */ true))) + return isAligned(V, Align, DL); } // For GEPs, determine if the indexing lands within the allocated object. diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -4393,7 +4393,7 @@ // Note: It's really tempting to think that a conditional branch or // switch should be listed here, but that's incorrect. It's not // branching off of poison which is UB, it is executing a side effecting - // instruction which follows the branch. + // instruction which follows the branch. return nullptr; } } @@ -5728,3 +5728,60 @@ return CR; } + +bool llvm::maybeFreedInBetween(const Instruction *SrcI, const Instruction *DstI, + unsigned MaxCheckedInstructions, + bool IsGloballyKnown) { + const Function *F = SrcI->getFunction(); + // If the function is no-free, and no-sync if necessary, there cannot be a + // deallocation. + if (F->hasFnAttribute(Attribute::NoFree) && + (!IsGloballyKnown || F->hasFnAttribute(Attribute::NoSync))) + return false; + + // If we do not want to check any instructions we give up now. + if (MaxCheckedInstructions == 0) + return true; + + SmallVector Worklist; + SmallPtrSet Visited; + Worklist.push_back(DstI); + + // Lookup all instructions on all paths from SrcI to DstI and + // determine if there is a conflicting call in-between or not. + // We do so by exploring the paths in reverse order from DstI. + do { + const Instruction *CurI = Worklist.pop_back_val(); + + // Never visit an instruction twice. + if (!Visited.insert(CurI).second) + continue; + + // Make sure we do not waste too much time trying to prove this. + if (Visited.size() > MaxCheckedInstructions) + return true; + + // Only calls can deallocate, aka. free, memory or synchronize. + if (ImmutableCallSite ICS = ImmutableCallSite(CurI)) { + if (!ICS.hasFnAttr(Attribute::NoFree) || + (IsGloballyKnown && !ICS.hasFnAttr(Attribute::NoSync))) + return true; + } + + // Once SrcI is reached we are done traversing for this instruction. + if (CurI == SrcI) + continue; + + // If we reached the beginning of a block, look at the predecessors. + if (!CurI->getPrevNode()) { + const BasicBlock *CurBB = CurI->getParent(); + for (const BasicBlock *PredBB : predecessors(CurBB)) + Worklist.push_back(&PredBB->back()); + } + + } while (!Worklist.empty()); + + // No possible free found. + return false; +} + 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 @@ -601,40 +601,92 @@ return stripPointerCastsAndOffsets(this); } -uint64_t Value::getPointerDereferenceableBytes(const DataLayout &DL, - bool &CanBeNull) const { +uint64_t +Value::getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, + Instruction *&DerefKnownBefore) const { assert(getType()->isPointerTy() && "must be pointer"); uint64_t DerefBytes = 0; CanBeNull = false; + DerefKnownBefore = nullptr; if (const Argument *A = dyn_cast(this)) { - DerefBytes = A->getDereferenceableBytes(); + DerefBytes = A->getDereferenceableGloballyBytes(); if (DerefBytes == 0 && (A->hasByValAttr() || A->hasStructRetAttr())) { Type *PT = cast(A->getType())->getElementType(); if (PT->isSized()) DerefBytes = DL.getTypeStoreSize(PT); } + if (CtxI && DerefBytes == 0) { + uint64_t DerefBytesAtDef = A->getDereferenceableBytes(); + if (DerefBytesAtDef) { + DerefBytes = DerefBytesAtDef; + DerefKnownBefore = &A->getParent()->getEntryBlock().front(); + } + } if (DerefBytes == 0) { - DerefBytes = A->getDereferenceableOrNullBytes(); + DerefBytes = A->getDereferenceableOrNullBytesGlobally(); CanBeNull = true; } + if (CtxI && DerefBytes == 0) { + uint64_t DerefBytesAtDef = A->getDereferenceableOrNullBytes(); + if (DerefBytesAtDef) { + DerefBytes = DerefBytesAtDef; + DerefKnownBefore = &A->getParent()->getEntryBlock().front(); + CanBeNull = true; + } + } } else if (const auto *Call = dyn_cast(this)) { - DerefBytes = Call->getDereferenceableBytes(AttributeList::ReturnIndex); + DerefBytes = + Call->getDereferenceableGloballyBytes(AttributeList::ReturnIndex); + if (CtxI && DerefBytes == 0) { + uint64_t DerefBytesAtDef = + Call->getDereferenceableBytes(AttributeList::ReturnIndex); + if (DerefBytesAtDef) { + DerefBytes = DerefBytesAtDef; + DerefKnownBefore = Call->getNextNode(); + } + } if (DerefBytes == 0) { - DerefBytes = - Call->getDereferenceableOrNullBytes(AttributeList::ReturnIndex); + DerefBytes = Call->getDereferenceableOrNullBytesGlobally( + AttributeList::ReturnIndex); CanBeNull = true; } + if (CtxI && DerefBytes == 0) { + uint64_t DerefBytesAtDef = + Call->getDereferenceableOrNullBytes(AttributeList::ReturnIndex); + if (DerefBytesAtDef) { + DerefBytes = DerefBytesAtDef; + DerefKnownBefore = Call->getNextNode(); + CanBeNull = true; + } + } } else if (const LoadInst *LI = dyn_cast(this)) { - if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) { + if (MDNode *MD = + LI->getMetadata(LLVMContext::MD_dereferenceable_globally)) { ConstantInt *CI = mdconst::extract(MD->getOperand(0)); DerefBytes = CI->getLimitedValue(); } + if (CtxI && DerefBytes == 0) { + if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) { + ConstantInt *CI = mdconst::extract(MD->getOperand(0)); + DerefBytes = CI->getLimitedValue(); + DerefKnownBefore = LI->getNextNode(); + } + } if (DerefBytes == 0) { + if (MDNode *MD = LI->getMetadata( + LLVMContext::MD_dereferenceable_or_null_globally)) { + ConstantInt *CI = mdconst::extract(MD->getOperand(0)); + DerefBytes = CI->getLimitedValue(); + } + CanBeNull = true; + } + if (CtxI && DerefBytes == 0) { if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) { ConstantInt *CI = mdconst::extract(MD->getOperand(0)); DerefBytes = CI->getLimitedValue(); + DerefKnownBefore = LI->getNextNode(); } CanBeNull = true; } diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp --- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -49,6 +49,7 @@ #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" @@ -493,7 +494,17 @@ CallSite CS(U); assert(CS && "Should only have direct calls!"); - if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL)) + Instruction *DerefKnownBefore; + if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL, DerefKnownBefore)) + return false; + + // TODO: Determine IsGloballyKnown for the maybeFreedInBetween call. + // TODO: Determine a good value for MaxCheckedInstructions in the + // maybeFreedInBetween call. + if (DerefKnownBefore && + maybeFreedInBetween(DerefKnownBefore, CS.getInstruction(), + /* MaxCheckedInstructions */ 0, + /* IsGloballyKnown */ true)) return false; } return true;