[CaptureTracking] Do not capture compares of same object

[caojoshua]

Summary

Compares of the same object do not leak any bits.

This patch introduces getUnderlyingObjectLookThrough. It looks at the
output of getUnderlyingObject. If it is a PHI, it looks at all the
incoming underlying objects. If all those objects are the same, or the
original PHI, we determine that there is a new underlying object. This
is similar to getUnderlyingObjects, but provides a more efficient way to
find a single underlying object.

This is an attempt at solving huge compile time regressions in
https://reviews.llvm.org/D152082. First, we only look through a single
PHI, not nested PHIs. Second, we only use one callsite. There are likely
other callsites that could take advantage of this over the vanilla
getUnderlyingObjects. We need to be careful about compile times. Adding
this to BasicAA::aliasCheck increases compile times by 3% on local
builds.

This can hopefully lead to improved rustc generated code in
https://github.com/rust-lang/rust/issues/111603. rustc generates
pointers comparisons that this patch can identify as non capturing.

[caojoshua]

rebase

[caojoshua]

@nikic could you try running compile time on this? Uploaded to https://github.com/caojoshua/llvm-project/tree/underlyingicmp.

I tried a couple runs locally. Last run saw this patch increase mean compile time of CTMark by +0.003%. I trust your runs more than the runs on my local machine.

[caojoshua]

fix typo

[caojoshua]

Update commit msg

[nikic]

In D152241#4398547, @caojoshua wrote:

@nikic could you try running compile time on this? Uploaded to https://github.com/caojoshua/llvm-project/tree/underlyingicmp.

I tried a couple runs locally. Last run saw this patch increase mean compile time of CTMark by +0.003%. I trust your runs more than the runs on my local machine.

I'm not seeing any compile-time impact either. I've also added your LLVM fork to llvm-compile-time-tracker, if you'd like to test patches directly.

[nikic]

Using getUnderlyingObject() here is not quite right: The underlying object is a pure provenance notion, while icmp is a pure address comparison. What we need here is that the icmp can be expressed as Base + Offset1 == Base + Offset2. This is *nearly* what getUnderlyingObject() does in practice, but not quite.

In particular, getUnderlyingObject() can also look through ptrmask intrinsics. However, ptrmask(P, M) == P clearly leaks bits of the pointers.

I think you'll have to implement a separate utility here that only looks through GEP + casts, but not things like ptrmask.

[goldstein.w.n]

In D152241#4402421, @nikic wrote:

Using getUnderlyingObject() here is not quite right: The underlying object is a pure provenance notion, while icmp is a pure address comparison. What we need here is that the icmp can be expressed as Base + Offset1 == Base + Offset2. This is *nearly* what getUnderlyingObject() does in practice, but not quite.

In particular, getUnderlyingObject() can also look through ptrmask intrinsics. However, ptrmask(P, M) == P clearly leaks bits of the pointers.

The case being because depending on M is indicates which bits in P are zero?
If so then I think you can only do this for equality comparisons, otherwise something like:
Base + Offset1 < Base + Offset2 can probably end up leaking some bits (depending on what is known
about Offset1/Offset2) because of overflows.
If that is a concern then you need to also ensure the ICmp is equality (its unchecked at the moment).

I think you'll have to implement a separate utility here that only looks through GEP + casts, but not things like ptrmask.

llvm/lib/Analysis/CaptureTracking.cpp

416

think the "to" is extra.

[nikic]

In D152241#4402472, @goldstein.w.n wrote:

In D152241#4402421, @nikic wrote:

Using getUnderlyingObject() here is not quite right: The underlying object is a pure provenance notion, while icmp is a pure address comparison. What we need here is that the icmp can be expressed as Base + Offset1 == Base + Offset2. This is *nearly* what getUnderlyingObject() does in practice, but not quite.

In particular, getUnderlyingObject() can also look through ptrmask intrinsics. However, ptrmask(P, M) == P clearly leaks bits of the pointers.

The case being because depending on M is indicates which bits in P are zero?
If so then I think you can only do this for equality comparisons, otherwise something like:
Base + Offset1 < Base + Offset2 can probably end up leaking some bits (depending on what is known
about Offset1/Offset2) because of overflows.
If that is a concern then you need to also ensure the ICmp is equality (its unchecked at the moment).

Yes, you are right, this also needs to check for equality comparisons. I believe it can be extended to unsigned predicates if the GEPs are inbounds, but let's start simple here...

[caojoshua]

• Remove getLookthroughUnderlyingObject. Create a utility specifically for non leaking underlying object
• only determine non-capture for equality comparisons

[caojoshua]

If so then I think you can only do this for equality comparisons, otherwise something like:
Base + Offset1 < Base + Offset2 can probably end up leaking some bits (depending on what is known
about Offset1/Offset2) because of overflows.
If that is a concern then you need to also ensure the ICmp is equality (its unchecked at the moment).

Thats a great point. I added a check to make sure its only equality comparisons.

Does not have to be part of this patch, but could we extend this to cover non-equality comparisons if all the GEPs are inbounds? From https://llvm.org/docs/LangRef.html#id234, inbounds GEPs are poison if there is wrapping

The multiplication of an index by the type size does not wrap the pointer index type in a signed sense (nsw).
The successive addition of offsets (without adding the base address) does not wrap the pointer index type in a signed sense (nsw).
The successive addition of the current address, interpreted as an unsigned number, and an offset, interpreted as a signed number, does not wrap the unsigned address space and remains in bounds of the allocated object. As a corollary, if the added offset is non-negative, the addition does not wrap in an unsigned sense (nuw).

[goldstein.w.n]

In D152241#4411708, @caojoshua wrote:

If so then I think you can only do this for equality comparisons, otherwise something like:
Base + Offset1 < Base + Offset2 can probably end up leaking some bits (depending on what is known
about Offset1/Offset2) because of overflows.
If that is a concern then you need to also ensure the ICmp is equality (its unchecked at the moment).

Thats a great point. I added a check to make sure its only equality comparisons.

Does not have to be part of this patch, but could we extend this to cover non-equality comparisons if all the GEPs are inbounds? From https://llvm.org/docs/LangRef.html#id234, inbounds GEPs are poison if there is wrapping

If inbounds is present then comparison of two pointers that are products of GEP from the same base an entirely remove base and make the comparison entirely depend on the offsets
so it should be safe to include nocapture even for non-eq comparisons. That being said, something like:

define i1 @src_gep(ptr %p, i64 %off) {
  %p_gep = getelementptr inbounds i64, ptr %p, i64 %off
  %cmp = icmp ugt ptr %p_gep, %p
  ret i1 %cmp
}

Already folds out the GEP entirely (and as a result makes %p unused) so not sure if you actually need to change anything to get the desired behavior.

The multiplication of an index by the type size does not wrap the pointer index type in a signed sense (nsw).
The successive addition of offsets (without adding the base address) does not wrap the pointer index type in a signed sense (nsw).
The successive addition of the current address, interpreted as an unsigned number, and an offset, interpreted as a signed number, does not wrap the unsigned address space and remains in bounds of the allocated object. As a corollary, if the added offset is non-negative, the addition does not wrap in an unsigned sense (nuw).

[nikic]

I just realized that my comment on getUnderlyingObject() wasn't right in the following sense: While generally we can't assume that a comparison with the same underlying object is non-capturing, in this particular context, if the value were used in something like ptrmask, we would already report a capture at that point, so it would actually be fine to just use getUnderlyingObject() here.

The purpose of the getUnderlyingObject() check is effectively only to make sure that we don't handle cases like (c ? alloca : other) == ..., where the other contribution does not go through CaptureTracking. Everything else is already handled by the other CaptureTracking checks.

So I think your previous version was fine in that respect, though if you also want to handle inbounds GEP chains you'll need the separate helper anyway.

In D152241#4411708, @caojoshua wrote:

Does not have to be part of this patch, but could we extend this to cover non-equality comparisons if all the GEPs are inbounds? From https://llvm.org/docs/LangRef.html#id234, inbounds GEPs are poison if there is wrapping

It's safe to handle inbounds GEP if the predicate is unsigned. Signed predicates can not be handled.

In D152241#4411731, @goldstein.w.n wrote:

That being said, something like:

define i1 @src_gep(ptr %p, i64 %off) {
  %p_gep = getelementptr inbounds i64, ptr %p, i64 %off
  %cmp = icmp ugt ptr %p_gep, %p
  ret i1 %cmp
}

Already folds out the GEP entirely (and as a result makes %p unused) so not sure if you actually need to change anything to get the desired behavior.

I think the main interest here is in cases involving loop phis, in which case we don't reliably do this, I believe. (Though there is the "indexed compare" fold that does try.)

llvm/lib/Analysis/CaptureTracking.cpp

81

Unnecessary?

84

Don't use std::function

90

If we handle phis, we should also handle selects.

[nikic]

llvm/lib/Analysis/CaptureTracking.cpp

90

We also need to limit recursion.

[caojoshua]

A PR was submitted to rust to change pointer inductions to index inductions for array allocations, which if merged, eliminates my main motivation for this patch.

I'm questioning the benefits of this patch. GEP inductions are certainly common, but comparisons against a GEP with (start, end) pointers are much less common when you can just iterate over indices. I don't have another real world example that supports this patch. @nikic any opinions, do you think this patch is a good enhancement to LLVM?

[caojoshua]

Go back to the original version with getUnderlyingObjectLookthrough(). Only no-capture for equality compares. Add tests to make sure we don't escape comparisons against captured objects like ptrmask.

[caojoshua]

I just realized that my comment on getUnderlyingObject() wasn't right in the following sense: While generally we can't assume that a comparison with the same underlying object is non-capturing, in this particular context, if the value were used in something like ptrmask, we would already report a capture at that point, so it would actually be fine to just use getUnderlyingObject() here.

Yes. Can confirm this with newly added tests. Compare object against ptrmask of itself still does not capture.

llvm/include/llvm/Analysis/ValueTracking.h

 /// and it only captures pointer by returning it.
 /// These intrinsics are not marked as nocapture, because returning is
 /// considered as capture. The arguments are not marked as returned neither,
 /// because it would make it useless. If \p MustPreserveNullness is true,
 /// the intrinsic must preserve the nullness of the pointer.
 bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
     const CallBase *Call, bool MustPreserveNullness);
 
+/// This method is a wrapper around getUnderlyingObject to look through PHI
+/// nodes. This method will attempt to build a new underlying object based on
+/// the incoming values. This method can have high compile time implications and
+/// cannot be used as a direct replacement for getUnderlyingObject.
+const Value *getUnderlyingObjectLookThrough(const Value *V,
+                                            unsigned MaxLookup = 6);
+
 /// This method strips off any GEP address adjustments and pointer casts from
 /// the specified value, returning the original object being addressed. Note
 /// that the returned value has pointer type if the specified value does. If
 /// the MaxLookup value is non-zero, it limits the number of instructions to
 /// be stripped off.
 const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
 inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
   // Force const to avoid infinite recursion.

llvm/lib/Analysis/CaptureTracking.cpp

bool CaptureTracker::isDereferenceableOrNull(Value *O, const DataLayout &DL) {
   return O->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
 }
 
 namespace {
   struct SimpleCaptureTracker : public CaptureTracker {
     explicit SimpleCaptureTracker(
 
         const SmallPtrSetImpl<const Value *> &EphValues, bool ReturnCaptures)
         : EphValues(EphValues), ReturnCaptures(ReturnCaptures) {}
 
     void tooManyUses() override {
       LLVM_DEBUG(dbgs() << "Captured due to too many uses\n");
       Captured = true;
     }
 
     bool captured(const Use *U) override {
       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
         return false;
 
       if (EphValues.contains(U->getUser()))
         return false;
 
       LLVM_DEBUG(dbgs() << "Captured by: " << *U->getUser() << "\n");
 
       Captured = true;
       return true;
if (auto *CPN = dyn_cast<ConstantPointerNull>(I->getOperand(OtherIdx))) {
         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.
         const DataLayout &DL = I->getModule()->getDataLayout();
         if (IsDereferenceableOrNull && IsDereferenceableOrNull(O, DL))
           return UseCaptureKind::NO_CAPTURE;
       }
-    }
+    } else if (cast<ICmpInst>(I)->isEquality() &&
+               getUnderlyingObjectLookThrough(I->getOperand(Idx)) ==
+                   getUnderlyingObjectLookThrough(I->getOperand(OtherIdx)))
+      // Equality comparisons against the same pointer do not capture.
+      return UseCaptureKind::NO_CAPTURE;
 
     // Otherwise, be conservative. There are crazy ways to capture pointers
     // using comparisons.
     return UseCaptureKind::MAY_CAPTURE;
   }
   default:
     // Something else - be conservative and say it is captured.
     return UseCaptureKind::MAY_CAPTURE;

llvm/lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   //       int *p = a[i];
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
+const Value *llvm::getUnderlyingObjectLookThrough(const Value *V, unsigned MaxLookup) {
+  V = getUnderlyingObject(V, MaxLookup);
+
+  const PHINode *PN = dyn_cast<PHINode>(V);
+  if (!PN)
+    return V;
+
+  // We can look through PHIs if each underlying value has the same underlying
+  // object, or is the phi itself.
+  const Value *NewUnderlying = PN;
+  for (const Value *Incoming : PN->incoming_values()) {
+    const Value *IncomingUnderlying = getUnderlyingObject(Incoming, MaxLookup);
+    if (IncomingUnderlying == PN || IncomingUnderlying == NewUnderlying)
+      continue;
+    if (NewUnderlying == PN)
+      // Found a new possible underlying object.
+      NewUnderlying = IncomingUnderlying;
+    else
+      // There are >= 2 possible underlying objects. We cannot determine a new
+      // underlying object.
+      return V;
+  }
+  return NewUnderlying;
+}
+
 const Value *llvm::getUnderlyingObject(const Value *V, unsigned MaxLookup) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {

llvm/test/Transforms/FunctionAttrs/nocapture.ll

 }
 
 ; FNATTR: define void @readnone_indirec(ptr nocapture readonly %f, ptr readnone %p)
 define void @readnone_indirec(ptr %f, ptr %p) {
   call void %f(ptr %p) readnone
   ret void
 }
 
-; FNATTR: define i1 @identity_icmp(ptr readnone %p)
+; FNATTR: define i1 @identity_icmp(ptr nocapture readnone %p)
 define i1 @identity_icmp(ptr %p) {
   %r = icmp eq ptr %p, %p
   ret i1 %r
 }
 
-; FNATTR: define i1 @compare_against_offset(ptr readnone %p)
+; FNATTR: define i1 @compare_against_offset(ptr nocapture readnone %p)
 define i1 @compare_against_offset(ptr %p) {
   %offset = getelementptr inbounds i32, ptr %p, i64 1
   %r = icmp eq ptr %p, %offset
   ret i1 %r
 }
 
-; FNATTR: define i1 @compare_offsets(ptr readnone %p)
+; FNATTR: define i1 @compare_offsets(ptr nocapture readnone %p)
 define i1 @compare_offsets(ptr %p) {
   %offset1 = getelementptr inbounds i32, ptr %p, i64 1
   %offset2 = getelementptr inbounds i32, ptr %p, i64 2
   %r = icmp eq ptr %offset1, %offset2
   ret i1 %r
 }
 
-; FNATTR: define void @phi_induction(ptr writeonly %p, i64 %n, i32 %x)
+; FNATTR: define void @phi_induction(ptr nocapture writeonly %p, i64 %n, i32 %x)
 define void @phi_induction(ptr %p, i64 %n, i32 %x) {
 start:
   %end = getelementptr inbounds i32, ptr %p, i64 %n
   br label %repeat_loop_body
 
 repeat_loop_body:                                 ; preds = %start, %repeat_loop_body
   %induct = phi ptr [ %p, %start ], [ %induct.next, %repeat_loop_body ]
   store i32 %x, ptr %induct, align 4

llvm/unittests/Analysis/CaptureTrackingTest.cpp

TEST(CaptureTracking, MultipleUsesInSameInstruction) {
   auto M = parseAssemblyString(Assembly, Error, Context);
   ASSERT_TRUE(M) << "Bad assembly?";
 
   Function *F = M->getFunction("test");
   Value *Arg = &*F->arg_begin();
   BasicBlock *BB = &F->getEntryBlock();
   Instruction *Call = &*BB->begin();
   Instruction *CmpXChg = Call->getNextNode();
-  Instruction *ICmp = CmpXChg->getNextNode();
 
   CollectingCaptureTracker CT;
   PointerMayBeCaptured(Arg, &CT);
-  EXPECT_EQ(7u, CT.Captures.size());
+  EXPECT_EQ(5u, CT.Captures.size());
   // Call arg 1
   EXPECT_EQ(Call, CT.Captures[0]->getUser());
   EXPECT_EQ(0u, CT.Captures[0]->getOperandNo());
   // Call arg 3
   EXPECT_EQ(Call, CT.Captures[1]->getUser());
   EXPECT_EQ(2u, CT.Captures[1]->getOperandNo());
   // Operand bundle arg
   EXPECT_EQ(Call, CT.Captures[2]->getUser());
   EXPECT_EQ(3u, CT.Captures[2]->getOperandNo());
   // Cmpxchg compare operand
   EXPECT_EQ(CmpXChg, CT.Captures[3]->getUser());
   EXPECT_EQ(1u, CT.Captures[3]->getOperandNo());
   // Cmpxchg new value operand
   EXPECT_EQ(CmpXChg, CT.Captures[4]->getUser());
   EXPECT_EQ(2u, CT.Captures[4]->getOperandNo());
-  // ICmp first operand
-  EXPECT_EQ(ICmp, CT.Captures[5]->getUser());
-  EXPECT_EQ(0u, CT.Captures[5]->getOperandNo());
-  // ICmp second operand
-  EXPECT_EQ(ICmp, CT.Captures[6]->getUser());
-  EXPECT_EQ(1u, CT.Captures[6]->getOperandNo());
 }