[CaptureTracker] Comparisons of allocation pointers do not capture

[jdoerfert]

Summary

If two pointers compared in an ICmp instruction 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.

[hfinkel]

I'm missing something here. If I have two pointers (e.g., returned from malloc), and I compare them so I know they're equal, then I've learned that the pointers are equal -- and, thus, if I know all of the bits of one pointer I now know all of the bits of the other pointer. As a result, I can still reconstruct it later using that information.

[jdoerfert]

In D66461#1639246, @hfinkel wrote:

I'm missing something here. If I have two pointers (e.g., returned from malloc), and I compare them so I know they're equal, then I've learned that the pointers are equal -- and, thus, if I know all of the bits of one pointer I now know all of the bits of the other pointer. As a result, I can still reconstruct it later using that information.

I'll try to explain why I think this is fine:
If you compare the same pointer (or derived from the same), you need to capture at least one from them "explicitly" to learn the bits. You cannot use ICmps between them for that (without leaving the categories specified) so you need an "explicit" capture somehow. The comparison we would allow here might give you the offset of the second pointer, which, assuming you know the bits of the first, tells you the second one. However, I think this is no more information than the captured pointer alone, assuming "capturing" does not only leak the bits of the pointer but the address range of the whole underlying object.

[efriedma]

Yes, you can't capture a pointer that's already captured.

The more interesting scenario is something like this: suppose you have three consecutive 16-byte allocations, laid out one after another. The first and the third are captured; the second is not. Can you capture a pointer to the second allocation using comparisons against the first and third allocations? I think the only reasonable answer here is yes; you've proven the value of every bit of the pointer.

It doesn't really matter if three allocations don't reliably produce this layout; for any particular run of the program, we have to choose some memory layout.

[hfinkel]

If you compare the same pointer (or derived from the same), you need to capture at least one from them "explicitly" to learn the bits.

Yes, but then we'd need some way to account for that. If pointer A is compared to pointer B, and then pointer B is unambiguously captured, then so has been pointer A (at least in the part of the control flow dominated by the true edge of the comparison).

[jdoerfert]

In D66461#1639801, @efriedma wrote:

Yes, you can't capture a pointer that's already captured.

! In D66461#1640565, @hfinkel wrote:
If you compare the same pointer (or derived from the same), you need to capture at least one from them "explicitly" to learn the bits.

Yes, but then we'd need some way to account for that. If pointer A is compared to pointer B, and then pointer B is unambiguously captured, then so has been pointer A (at least in the part of the control flow dominated by the true edge of the comparison).

You can capture A that way if A and B are (basically) equal. Now in the part in which the capture of A through the icmp matters you already have B captured for sure, that is an alias of A is captured so A is captured even if not directly through the expression of A.

The more interesting scenario is something like this: suppose you have three consecutive 16-byte allocations, laid out one after another. The first and the third are captured; the second is not. Can you capture a pointer to the second allocation using comparisons against the first and third allocations? I think the only reasonable answer here is yes; you've proven the value of every bit of the pointer.

It doesn't really matter if three allocations don't reliably produce this layout; for any particular run of the program, we have to choose some memory layout.

I see your point but I think the basic idea is still sound, the patch needs an addition though.
As I described, the compare will capture only if the other pointer was captured. So additionally to the checks in the patch ask the tracker if that is the case, e.g.,

if (IsDerefOrNoAlias0 && IsDerefOrNoAlias1)
  if (!Tracker->capture(Op1))
      break;

Maybe we can even get rid of the categories and say sth along the lines of:

// Op0, the use of V in the ICmp is capturing if Op1 is captured. Otherwise,
// Op1 is opaque and comparing it with another opaque pointer is not going
// to yield information.
if (!Tracker->capture(Op1)
   break;

What do you think?

[efriedma]

As I described, the compare will capture only if the other pointer was captured. So additionally to the checks in the patch ask the tracker if that is the case

You can't actually reconstruct the pointer in that case, but the bits are still significant; if two functions sort a list of pointers, they have to sort the same way. Whether that means the pointer is "captured" depends on the definition of "captured"; I can think of transforms that don't care, and transforms that do care.

[jdoerfert]

In D66461#1641668, @efriedma wrote:

As I described, the compare will capture only if the other pointer was captured. So additionally to the checks in the patch ask the tracker if that is the case

You can't actually reconstruct the pointer in that case, but the bits are still significant; if two functions sort a list of pointers, they have to sort the same way. Whether that means the pointer is "captured" depends on the definition of "captured"; I can think of transforms that don't care, and transforms that do care.

You lost me. When I say "captured" I mean (a bit of) the pointer value is leaked. When I above said you have two pointers, if neither is captured so far a comparison between them doesn't capture either I mean that we do not need to worry about the bits being leaked and later used to access the memory or doing other odd things.

[efriedma]

Thinking about it a bit more, that definition is probably okay.

It would be possible to define a stronger property, that the value of the pointer isn't significant for the operation. So if a pointer points to the value "3", you can replace it with some other pointer that also points to "3". Sort of like unnamed_addr on globals. But that's stronger than you need for alias analysis.

[hfinkel]

As I described, the compare will capture only if the other pointer was captured.

But the other pointer can be captured afterward, no?

[jdoerfert]

In D66461#1642252, @hfinkel wrote:

As I described, the compare will capture only if the other pointer was captured.

But the other pointer can be captured afterward, no?

Yes, but the idea was that because it is captured we would not rule the icmp as "benign".
However, trying to update the patch I realized this is not as simple as the scope in which the other pointer is "not captured" seems important.

I will think about this further and (hopefully) come up with a proposal that might use capture information and the categories I had here as they restrict how a pointer can be "prepared" in the first place.

If anyone has a good idea, let me know, I am almost certain we can do better here and I believe we should as pointer comparisons seem like something that happens frequently.

llvm/include/llvm/Analysis/CaptureTracking.h

struct CaptureTracker {
 
     /// captured - Information about the pointer was captured by the user of
     /// use U. Return true to stop the traversal or false to continue looking
     /// for more capturing instructions.
     virtual bool captured(const Use *U) = 0;
 
     /// 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
   /// find values which appear to be capturing the pointer value. This feeds
   /// results into and is controlled by the CaptureTracker object.
   /// MaxUsesToExplore specifies how many uses should the analysis explore for
   /// one value before giving up due too "too many uses".
   void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker,
                             unsigned MaxUsesToExplore = DefaultMaxUsesToExplore);
 } // end namespace llvm
 
 #endif

llvm/lib/Analysis/CaptureTracking.cpp

 #include "llvm/IR/IntrinsicInst.h"
 
 using namespace llvm;
 
 CaptureTracker::~CaptureTracker() {}
 
 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<GetElementPtrInst>(O))
-    if (GEP->isInBounds())
-      return true;
+bool CaptureTracker::isDereferenceableOrNull(const Value *O,
+                                             const DataLayout &DL,
+                                             bool AllowNull) {
+  if (AllowNull && isa<ConstantPointerNull>(O))
+
   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 {
   struct SimpleCaptureTracker : public CaptureTracker {
     explicit SimpleCaptureTracker(bool ReturnCaptures)
       : ReturnCaptures(ReturnCaptures), Captured(false) {}
 
     void tooManyUses() override { Captured = true; }
while (!Worklist.empty()) {
     case Instruction::GetElementPtr:
     case Instruction::PHI:
     case Instruction::Select:
     case Instruction::AddrSpaceCast:
       // The original value is not captured via this if the new value isn't.
       AddUses(I);
       break;
     case Instruction::ICmp: {
-      unsigned Idx = (I->getOperand(0) == V) ? 0 : 1;
-      unsigned OtherIdx = 1 - Idx;
-      if (auto *CPN = dyn_cast<ConstantPointerNull>(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)
+
       // 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<LoadInst>(I->getOperand(OtherIdx));
+      auto *LI = dyn_cast<LoadInst>(Op1);
       if (LI && isa<GlobalVariable>(LI->getPointerOperand()))
         break;
       // Otherwise, be conservative. There are crazy ways to capture pointers
       // using comparisons.
       if (Tracker->captured(U))
         return;
       break;
     }

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);
 
-  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<GEPOperator>(V)) {
     const Value *Base = GEP->getPointerOperand();
 
     APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0);
     if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||
         !Offset.urem(APInt(Offset.getBitWidth(), Align)).isMinValue())
       return false;
 
     // If the base pointer is dereferenceable for Offset+Size bytes, then the
     // GEP (== Base + Offset) is dereferenceable for Size bytes.  If the base
     // pointer is aligned to Align bytes, and the Offset is divisible by Align
     // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
     // aligned to Align bytes.
 
     // Offset and Size may have different bit widths if we have visited an
     // addrspacecast, so we can't do arithmetic directly on the APInt values.
     return isDereferenceableAndAlignedPointer(
         Base, Align, Offset + Size.sextOrTrunc(Offset.getBitWidth()),
         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<GCRelocateInst>(V))
     return isDereferenceableAndAlignedPointer(
         RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited);
 
   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
                                               DL, CtxI, DT, Visited);

llvm/lib/IR/Value.cpp

if (DerefBytes == 0) {
       }
       CanBeNull = true;
     }
   } else if (auto *AI = dyn_cast<AllocaInst>(this)) {
     if (!AI->isArrayAllocation()) {
       DerefBytes = DL.getTypeStoreSize(AI->getAllocatedType());
       CanBeNull = false;
     }
+  } else if (auto *GEP = dyn_cast<GEPOperator>(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<GlobalVariable>(this)) {
     if (GV->getValueType()->isSized() && !GV->hasExternalWeakLinkage()) {
       // TODO: Don't outright reject hasExternalWeakLinkage but set the
       // CanBeNull flag.
       DerefBytes = DL.getTypeStoreSize(GV->getValueType());
       CanBeNull = false;
     }
   }

llvm/test/Analysis/ValueTracking/memory-dereferenceable.ll

; CHECK: %d_or_null_non_null_load{{.*}}(aligned)
     %d_or_null_non_null_load = load i32*, i32** @globali32ptr, !nonnull !2, !dereferenceable_or_null !0
     %load10 = load i32, i32* %d_or_null_non_null_load
 
     ; It's OK to overrun static array size as long as we stay within underlying object size
 ; CHECK: %within_allocation{{.*}}(aligned)
     %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
 
     ; Loads from aligned globals
 ; CHECK: @globalptr.align1{{.*}}(unaligned)
 ; CHECK: @globalptr.align16{{.*}}(aligned)
     %load13 = load i8, i8* @globalptr.align1, align 16

llvm/test/Transforms/FunctionAttrs/nocapture.ll

 
 ; CHECK: define i1 @captureDereferenceableOrNullICmp(i32* readnone dereferenceable_or_null(4) %x)
 define i1 @captureDereferenceableOrNullICmp(i32* dereferenceable_or_null(4) %x) "null-pointer-is-valid"="true" {
   %1 = bitcast i32* %x to i8*
   %2 = icmp eq i8* %1, null
   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*)