[WIP] Adjust the users of dereferenceable wrt. dereferenceable_globally

[jdoerfert]

Summary

Prototype how we can make use of dereferenceable and
dereferenceable_globally at the same time. This depends on attributes
not in tree yet. This has not been tested nor have I updated the test
cases yet.

[reames]

llvm/include/llvm/IR/Value.h

583

An API suggestion. Instead of adding a context pointer here, add a boolean OnlyAtDef out param. Then introduce a helper function in ValueTracking which does the inference over the IR. (i.e. leave this as returning basic facts about the value, and move the analysis into an analysis.)

Or if you want, call the param AssumeNoFree, or whatever..

[jdoerfert]

Update according to API suggestion

llvm/include/llvm/IR/Value.h

583

I like it, done. Though, I do need the location of the definition, so I made it an Instruction *& not a bool &, what do you think?

[jdoerfert]

Update all uses of isDereferenceablePointer

[courbet]

llvm/lib/Transforms/Scalar/MergeICmps.cpp

165

I don't see where in the patch (or the rest of the stack of changes) the signature of isDereferenceablePointer is changed to non-const Instruction.

[reames]

llvm/include/llvm/IR/Value.h

583

I'd prefer the boolean given there's only two options: 1) on def, and 2) globally. I'm willing to defer to you on this if you feel strongly though.

[jdoerfert]

llvm/include/llvm/IR/Value.h

583

My problem is that for option 1) "on def", the information that is returned would not be sufficient for most users. In the "on def" case you also need the "definition" to query maybeFreedInBetween. If I would return a boolean, I would need to implement a second traversal that does the same just to find the definition. Does this make sense?

llvm/lib/Transforms/Scalar/MergeICmps.cpp

165

True, I remove the const_cast. That was my bad.

[reames]

llvm/include/llvm/IR/Value.h

583

No, not really. You can only ask this question on a particularly value. (i.e. argument or return value or load) That is the definition. If you have the instruction to query the property, you have the def, so I really don't understand your point.

[jdoerfert]

llvm/include/llvm/IR/Value.h

583

No, not really. You can only ask this question on a particularly value. (i.e. argument or return value or load) That is the definition. If you have the instruction to query the property, you have the def, so I really don't understand your point.

I'm also confused.

Let me try to explain again what I think we should do/need and why:

We call getPointerDereferenceableBytes on a pointer (llvm::Value) to get the "known dereferenceable bytes". This method determines that by traversing the operands until a "definition" is found. If the definition is natively dereferenceable, e.g., stack or global allocations, Instruction *&DerefKnownBefore is null and there is no change to the behavior we had. If the definition is "known dereferenceable" because of attributes or metadata that says _globally, Instruction *&DerefKnownBefore is null and there is no change to the behavior we had. Finally, if the definition is "known dereferenceable" because of attributes or metadata that does not end in _globally, Instruction *&DerefKnownBefore is set to the llvm:Instruction right after the "definition" with the attribute/metadata. This means that the number of dereferenceable bytes is known for that position but not necessarily any other position in the CFG. The caller can then use maybeFreedInBetween to determine if it holds for the position it is interested in. To have a tight "is potentially freed", one needs to know where it is "known dereferenceable" and where we are interested in "is dereferenceable".

[jdoerfert]

@reames ping?

[reames]

Happy to talk offline (call, chat, etc..) since we seem to be talking past each other again.

llvm/lib/IR/Value.cpp

689

Same point as before, but explained differently in the hopes this makes sense.

DerefKnownBefore only ever takes one of two values: the first instruction within the function, or the one after the instruction we invoked this function on. As such, the return value adds no information which can't be easily determined from a single boolean.

[jdoerfert]

llvm/lib/IR/Value.cpp

689

I think I get it know and I hope that means I can convince you we need more than a boolean, at least in the future and if we want to make it easier for the clients.

First, in the future we could handle any subset of the following cases which would make the boolean insufficient:

• casts
• select/phi
• gep with constant offsets and dereferenceable base pointer
• inbound geps with positive offsets w/ or w/o dereferenceabl base pointer

Second, the clients would need to do "more" in the boolean case as they have to check, cast, and advance the pointer value before they can call maybeFreedInbetween. Checked, means isa<Argument>(ptr) || isa<Instruction>(ptr) as we otherwise have an implicit contract that the bool is only set for instructions and arguments. Casted into the right thing, instruction or argument, and advanced in case of the former. I'd argue that will more easily to errors or wrong usage.

[reames]

llvm/lib/IR/Value.cpp

689

No, I'm not convinced.

I think what your describing is a need for two layers of APIs. There's the "raw" API on value which returns properties *of that value*, and then there's a more holistic API which returns *analysis results* and should live in Analysis/Something.h.

I'll also point out that future proofing code is a specific *anti-pattern* that we try very strongly to avoid. Choosing good abstractions is encouraged, but writing code which is not required by the current patch is not.

llvm/include/llvm/Analysis/ValueTracking.h

 
 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
 #define LLVM_ANALYSIS_VALUETRACKING_H
 
 #include "llvm/ADT/ArrayRef.h"
 #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"
 #include <cassert>
 #include <cstdint>
 
 namespace llvm {
 
Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
                                     const DataLayout &DL, bool LHSIsTrue = true,
                                     unsigned Depth = 0);
 
   /// Return the boolean condition value in the context of the given instruction
   /// if it is known based on dominating conditions.
   Optional<bool> 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

llvm/include/llvm/IR/Value.h

return const_cast<Value *>(
                       static_cast<const Value *>(this)->stripInBoundsOffsets());
   }
 
   /// Returns the number of bytes known to be dereferenceable for the
   /// pointer value.
   ///
   /// 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.
   ///
   /// Returns an alignment which is either specified explicitly, e.g. via
   /// align attribute of a function argument, or guaranteed by DataLayout.
   unsigned getPointerAlignment(const DataLayout &DL) const;
 
   /// Translate PHI node to its predecessor from the given basic block.

llvm/lib/Analysis/CaptureTracking.cpp

case Instruction::ICmp: {
           // 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.
           if (auto *GEP = dyn_cast<GetElementPtrInst>(O))
             if (GEP->isInBounds())
               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))
+          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
       // does not escape, its value cannot be guessed and stored separately in a
       // global variable.
       unsigned OtherIndex = (I->getOperand(0) == V) ? 1 : 0;
       auto *LI = dyn_cast<LoadInst>(I->getOperand(OtherIndex));
       if (LI && isa<GlobalVariable>(LI->getPointerOperand()))

llvm/lib/Analysis/Loads.cpp

static bool isDereferenceableAndAlignedPointer(
   // Note that it is not safe to speculate into a malloc'd region because
   // malloc may return null.
 
   // bitcast instructions are no-ops as far as dereferenceability is concerned.
   if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V))
     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))
+        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.
   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
     const Value *Base = GEP->getPointerOperand();
 
     APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0);
     if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||

llvm/lib/Analysis/MemDerefPrinter.cpp

FunctionPass *llvm::createMemDerefPrinter() {
   return new MemDerefPrinter();
 }
 
 bool MemDerefPrinter::runOnFunction(Function &F) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   for (auto &I: instructions(F)) {
     if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
       Value *PO = LI->getPointerOperand();
-      if (isDereferenceablePointer(PO, DL))
+      if (isDereferenceablePointer(PO, DL, LI))
         Deref.push_back(PO);
-      if (isDereferenceableAndAlignedPointer(PO, LI->getAlignment(), DL))
+      if (isDereferenceableAndAlignedPointer(PO, LI->getAlignment(), DL, LI))
         DerefAndAligned.insert(PO);
     }
   }
   return false;
 }
 
 void MemDerefPrinter::print(raw_ostream &OS, const Module *M) const {
   OS << "The following are dereferenceable:\n";

llvm/lib/Analysis/ValueTracking.cpp

switch (I->getOpcode()) {
     case Instruction::URem:
     case Instruction::SRem:
       return I->getOperand(1);
 
     default:
       // 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;
   }
 }
 
 bool llvm::mustTriggerUB(const Instruction *I,
                          const SmallSet<const Value *, 16>& KnownPoison) {
   auto *NotPoison = getGuaranteedNonFullPoisonOp(I);
   return (NotPoison && KnownPoison.count(NotPoison));
ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo) {
   ConstantRange CR = ConstantRange::getNonEmpty(Lower, Upper);
 
   if (auto *I = dyn_cast<Instruction>(V))
     if (auto *Range = IIQ.getMetadata(I, LLVMContext::MD_range))
       CR = CR.intersectWith(getConstantRangeFromMetadata(*Range));
 
   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<const Instruction *, 32> Worklist;
+  SmallPtrSet<const Instruction *, 32> 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;
+}
+

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitLoad(const LoadInst &I) {
 
   SDValue Ptr = getValue(SV);
 
   Type *Ty = I.getType();
 
   bool isVolatile = I.isVolatile();
   bool isNonTemporal = I.getMetadata(LLVMContext::MD_nontemporal) != nullptr;
   bool isInvariant = I.getMetadata(LLVMContext::MD_invariant_load) != nullptr;
-  bool isDereferenceable = isDereferenceablePointer(SV, DAG.getDataLayout());
+  bool isDereferenceable =
+      isDereferenceablePointer(SV, DAG.getDataLayout(), &I);
   unsigned Alignment = I.getAlignment();
 
   AAMDNodes AAInfo;
   I.getAAMetadata(AAInfo);
   const MDNode *Ranges = I.getMetadata(LLVMContext::MD_range);
 
   SmallVector<EVT, 4> ValueVTs, MemVTs;
   SmallVector<uint64_t, 4> Offsets;
if (!TLI.supportsUnalignedAtomics() &&
       I.getAlignment() < MemVT.getSizeInBits() / 8)
     report_fatal_error("Cannot generate unaligned atomic load");
 
   auto Flags = MachineMemOperand::MOLoad;
   if (I.isVolatile())
     Flags |= MachineMemOperand::MOVolatile;
   if (I.getMetadata(LLVMContext::MD_invariant_load) != nullptr)
     Flags |= MachineMemOperand::MOInvariant;
-  if (isDereferenceablePointer(I.getPointerOperand(), DAG.getDataLayout()))
+  if (isDereferenceablePointer(I.getPointerOperand(), DAG.getDataLayout(), &I))
     Flags |= MachineMemOperand::MODereferenceable;
 
   Flags |= TLI.getMMOFlags(I);
 
   MachineMemOperand *MMO =
       DAG.getMachineFunction().
       getMachineMemOperand(MachinePointerInfo(I.getPointerOperand()),
                            Flags, MemVT.getStoreSize(),

llvm/lib/IR/Value.cpp

Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
 
   return V;
 }
 
 const Value *Value::stripInBoundsOffsets() const {
   return stripPointerCastsAndOffsets<PSK_InBounds>(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<Argument>(this)) {
-    DerefBytes = A->getDereferenceableBytes();
+    DerefBytes = A->getDereferenceableGloballyBytes();
     if (DerefBytes == 0 && (A->hasByValAttr() || A->hasStructRetAttr())) {
       Type *PT = cast<PointerType>(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<CallBase>(this)) {
-    DerefBytes = Call->getDereferenceableBytes(AttributeList::ReturnIndex);
-    if (DerefBytes == 0) {
-      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->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<LoadInst>(this)) {
+    if (MDNode *MD =
+            LI->getMetadata(LLVMContext::MD_dereferenceable_globally)) {
+      ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
+      DerefBytes = CI->getLimitedValue();
+    }
+    if (CtxI && DerefBytes == 0) {
       if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
         ConstantInt *CI = mdconst::extract<ConstantInt>(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<ConstantInt>(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<ConstantInt>(MD->getOperand(0));
         DerefBytes = CI->getLimitedValue();
+        DerefKnownBefore = LI->getNextNode();
       }
       CanBeNull = true;
     }
   } else if (auto *AI = dyn_cast<AllocaInst>(this)) {
     if (!AI->isArrayAllocation()) {
       DerefBytes = DL.getTypeStoreSize(AI->getAllocatedType());
       CanBeNull = false;
     }

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

static bool allCallersPassInValidPointerForArgument(Argument *Arg) {
   unsigned ArgNo = Arg->getArgNo();
 
   // Look at all call sites of the function.  At this point we know we only have
   // direct callees.
   for (User *U : Callee->users()) {
     CallSite CS(U);
     assert(CS && "Should only have direct calls!");
 
-    if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL))
+    if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL,
+                                  CS.getInstruction()))
       return false;
   }
   return true;
 }
 
 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size
 /// that is greater than or equal to the size of prefix, and each of the
 /// elements in Prefix is the same as the corresponding elements in Longer.

llvm/lib/Transforms/Scalar/MergeICmps.cpp

BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) {
   if (!GEP)
     return {};
   LLVM_DEBUG(dbgs() << "GEP\n");
   if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) {
     LLVM_DEBUG(dbgs() << "used outside of block\n");
     return {};
   }
   const auto &DL = GEP->getModule()->getDataLayout();
-  if (!isDereferenceablePointer(GEP, DL)) {
+  if (!isDereferenceablePointer(GEP, DL, const_cast<LoadInst *>(LoadI))) {
     LLVM_DEBUG(dbgs() << "not dereferenceable\n");
     // We need to make sure that we can do comparison in any order, so we
     // require memory to be unconditionnally dereferencable.
     return {};
   }
   APInt Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
   if (!GEP->accumulateConstantOffset(DL, Offset))
     return {};