folding compares for distinct allocations

[anna]

Summary

We can fold compares to false when two distinct allocations within a function are compared for equality.

[anna]

Sanjoy pointed out a case that might cause the comparison of the pointer to itself to be incorrect, basically this check: PI == ICI->getOperand(OtherIndex) is not enough. Will update the diff to take care of such cases

[sanjoy]

For the record, this is the example I was talking about:

%v0 = malloc()
%other = (bitcast (bitcast %v0))
;; two bitcasts to allow bitcasting i8* -> i32* -> i8* or something like that
;; to allow the equality to be properly typed
%result = %other == %v0

Now, as written, I think the above example is fine, since the
traversal order guarantees that we'll visit the %result with PI as
%v0 (and bail out of the loop) before we visit %result with PI
as %other. And I think we _can_ make a general argument that if
isAllocFn returns true for the non PI operand then the non PI
operand is different from AI since if the non PI operand was equal
to AI then we'd have visited the comparison earlier and bailed out
of the loop. However, this argument is somewhat subtle (for instance,
passing in true for LookThroughBitCast to isAllocFn will break
that), so if we go down that path we should add some relevant asserts
and test cases.

[anna]

Added tests to catch cases in future when ordering of optimization changes (or changes to LikeAllocFn with LookThroughBitCast is set to true) which causes LikeAllocFn to return true.
Also, improved the check to see if 2 allocations are actually of the same pointer, by stripping through bitcasts and zero GEPs.

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

1909–1910

I don't think this will do the right thing if %x = allocation is compared with gep(gep(%x, 1), -1).

[anna]

lib/Transforms/InstCombine/InstructionCombining.cpp

1909–1910

Thats true!

I think this would handle all cases of GEP and bitcasts:
PI == ICI->getOperand(OtherIndex)->stripInBoundsOffsets()
Mainly, the GEP indices could be non-contant: gep(gep(%x, y), z) and still point to %x if y and z are 1 and -1 respectively.

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

1909–1910

In that case, what if we have gep(0, %x) ? I am not an expert on the GEP rules but someone else (@sanjoy?) might know.

[sanjoy]

I think the code would be more obviously correct if we pass in AI explicitly to isNeverEqualToUnescapedAlloc, and change the check in isNeverEqualToUnescapedAlloc to isAllocLikeFn(V, TLI) && V != AI. Does that sound better? Then we wouldn't have to worry about comparing an allocation against itself. Might also add a comment stating that we rely on LookThroughBitCast being false.

[anna]

agreed. This would work since GEPs are not considered in isAllocLikeFn.

Also, LookThroughBitCast being true just calls stripPointerCast(), so we can have the check as V->stripPointerCast() != AI && isAllocLikeFn(V, TLI). Does that work?

[sanjoy]

In D19390#409243, @anna wrote:

agreed. This would work since GEPs are not considered in isAllocLikeFn.

Also, LookThroughBitCast being true just calls stripPointerCast(), so we can have the check as V->stripPointerCast() != AI && isAllocLikeFn(V, TLI). Does that work?

That would work, but I think given that we're passing in false for LookThroughBitCast anyway (that's the default), I'd say lets not bother with that.

[sanjoy]

lgtm with some nits inline. I'll check this in for you once you upload the fixed version.

lib/Transforms/InstCombine/InstructionCombining.cpp

1873

I'd one line here on why we have that dependency. Also, it looks like you have a double space here.

test/Transforms/InstCombine/compare-unescaped.ll

89

Needs to be CHECK-NEXT:, not CHECK_NEXT:. The latter is an no-op.

lib/Transforms/InstCombine/InstructionCombining.cpp

if (!isa<BitCastInst>(Operand) &&
         return new BitCastInst(NGEP, GEP.getType());
       }
     }
   }
 
   return nullptr;
 }
 
-static bool isNeverEqualToUnescapedAlloc(Value *V) {
+static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo *TLI,
+                                         Instruction *AI) {
   if (isa<ConstantPointerNull>(V))
     return true;
   if (auto *LI = dyn_cast<LoadInst>(V))
     return isa<GlobalVariable>(LI->getPointerOperand());
-  return false;
+  // Two distinct allocations will never be equal.
+  // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking
+  // through bitcasts of V can cause
+  // the result statement below to be true, even when AI and V (ex:
+  // i8* ->i32* ->i8* of AI) are the same allocations.
+  return isAllocLikeFn(V, TLI) && V != AI;
 }
 
 static bool
 isAllocSiteRemovable(Instruction *AI, SmallVectorImpl<WeakVH> &Users,
                      const TargetLibraryInfo *TLI) {
   SmallVector<Instruction*, 4> Worklist;
   Worklist.push_back(AI);
 
for (User *U : PI->users()) {
       case Instruction::GetElementPtr:
         Users.emplace_back(I);
         Worklist.push_back(I);
         continue;
 
       case Instruction::ICmp: {
         ICmpInst *ICI = cast<ICmpInst>(I);
         // We can fold eq/ne comparisons with null to false/true, respectively.
-        // We fold comparisons in some conditions provided the alloc has not
+        // We also fold comparisons in some conditions provided the alloc has not
         // escaped.
         if (!ICI->isEquality())
           return false;
         unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0;
-        if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex)))
+        if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI))
           return false;
         Users.emplace_back(I);
         continue;
       }
 
       case Instruction::Call:
         // Ignore no-op and store intrinsics.
         if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
           switch (II->getIntrinsicID()) {

test/Transforms/InstCombine/compare-unescaped.ll

; CHECK-LABEL: compare_and_call_with_deopt
   %bc = bitcast i8* %m to i32*
   %lgp = load i32*, i32** @gp, align 8
   %cmp = icmp eq i32* %bc, %lgp
   %rt = zext i1 %cmp to i32
   tail call void @f() [ "deopt"(i8* %m) ]
   ret i32 %rt 
 ; CHECK: ret i32 %rt
 }
+
+define i1 @compare_distinct_mallocs() {
+  %m = call i8* @malloc(i64 4)
+  %n = call i8* @malloc(i64 4)
+  %cmp = icmp eq i8* %m, %n
+  ret i1 %cmp
+  ; CHECK-LABEL: compare_distinct_mallocs
+  ; CHECK: ret i1 false
+}
+
+; the compare is folded to true since the folding compare looks through bitcasts. 
+; call to malloc and the bitcast instructions are elided after that since there are no uses of the malloc 
+define i1 @compare_samepointer_under_bitcast() {
+  %m = call i8* @malloc(i64 4)
+  %bc = bitcast i8* %m to i32*
+  %bcback = bitcast i32* %bc to i8*
+  %cmp = icmp eq i8* %m, %bcback
+  ret i1 %cmp
+; CHECK-LABEL: compare_samepointer_under_bitcast
+; CHECK: ret i1 true 
+}
+
+; the compare is folded to true since the folding compare looks through bitcasts. 
+; call to malloc and the bitcast instructions are elided after that since there are no uses of the malloc 
+define i1 @compare_samepointer_escaped() {
+  %m = call i8* @malloc(i64 4)
+  %bc = bitcast i8* %m to i32*
+  %bcback = bitcast i32* %bc to i8*
+  %cmp = icmp eq i8* %m, %bcback
+  call void @f() [ "deopt"(i8* %m) ]
+  ret i1 %cmp
+; CHECK-LABEL: compare_samepointer_escaped
+; CHECK-NEXT: %m = call i8* @malloc(i64 4)
+; CHECK-NEXT: call void @f() [ "deopt"(i8* %m) ]
+; CHECK: ret i1 true 
+}
+
+; The malloc call for %m cannot be elided since it is used in the call to function f.
+; However, the cmp can be folded to true as %n doesnt escape and %m, %n are distinct allocations
+define i1 @compare_distinct_pointer_escape() {
+  %m = call i8* @malloc(i64 4)
+  %n = call i8* @malloc(i64 4)
+  tail call void @f() [ "deopt"(i8* %m) ]
+  %cmp = icmp ne i8* %m, %n
+  ret i1 %cmp
+; CHECK-LABEL: compare_distinct_pointer_escape
+; CHECK-NEXT: %m = call i8* @malloc(i64 4)
+; CHECK-NEXT: tail call void @f() [ "deopt"(i8* %m) ]
+; CHECK-NEXT: ret i1 true
+}