folding compares if pointers do not escape

[anna]

Summary

This is the first change in a series of changes to fold away comparisons when the pointer does not escape.

If we know that the pointer allocated within a function does not escape, we can fold away comparisons that are done with global pointers

[sanjoy]

Minor nits inline.

lib/Transforms/InstCombine/InstructionCombining.cpp

1865

I'd make this more specific: isNeverEqualToUnescapedAlloc (unless you want to extend this in ways that the compare would fold to false).

1871

Nit: Capitalization in comment.

1873

This could be return isa<GlobalVariable>(LI->getPointerOperand());

1907

I'm not sure you need a dyn_cast<> here. Have you tried just having CmpOp0 be a Value *?

1908

LHS and OtherOp may be slightly better names than CmpOp0 and CmpOp1. Personally, I'd even elide LHS altogether, and use a ternary to compute the index of the "other" operand.

1913

Nit: capitalize comment

[mcrosier]

lib/Transforms/InstCombine/InstructionCombining.cpp

1871

Please include a period as well.

1913

Please include a period as well.

[mgrang]

test/Transforms/InstCombine/compare-unescaped.ll

27

Extra newline.

[anna]

lib/Transforms/InstCombine/InstructionCombining.cpp

1907

cast not needed anymore, direct comparison in ternary condition with PI

[anna]

revised diff with minor changes

[sanjoy]

lgtm with one minor nit

lib/Transforms/InstCombine/InstructionCombining.cpp

1865

Nit: I'd rename CmpOp to just I -- the fact that it is a icmp operand is not pertinent here.

[majnemer]

lib/Transforms/InstCombine/InstructionCombining.cpp

1906

Could you handle this case in isNeverEqualToUnescapedAlloc by changing it's prototype to be a Value * instead of an Instruction *?

1907

Please clang-format this line.

[majnemer]

LGTM with nits.

lib/Transforms/InstCombine/InstructionCombining.cpp

1868

Please use auto * on the left hand side if the code makes it easy to figure out what the type is from the right hand side.

test/Transforms/InstCombine/compared-unescaped.ll

1 ↗

(On Diff #54434)

I'd recommend rewriting the pipeline to redirect %s into opt like so:

opt -instcombine -S < %s | FileCheck %s

Paths make their way into opt's output sometimes and you could get confusing results if folks stick their LLVM checkout in weird places.

3 ↗

(On Diff #54434)

space before the equals token.

17 ↗

(On Diff #54434)

space before the curly brace.

[reames]

test/Transforms/InstCombine/compared-unescaped.ll

35 ↗

(On Diff #54434)

This test case is a great example of what I mentioned to you on the phone the other day. Regardless of whether we can elide the call to malloc, we should be able to fold this comparison to false.

To be clear, I am not suggesting you change the current change (LGTM as well). This would be useful future work though.

[majnemer]

test/Transforms/InstCombine/compared-unescaped.ll

35 ↗

(On Diff #54434)

Perhaps a FIXME should get added?

[anna]

test/Transforms/InstCombine/compared-unescaped.ll

35 ↗

(On Diff #54434)

Agreed. We already have the check for nocapture operands in PointerMayBeCaptured. This specific case may be ok to add in the icmp case in PointerMayBeCaptured.

Also, I think the call to malloc cannot be elided in this case (since it may actually be leveraging the functionality of malloc + the function f deopt call). The malloc call will be elided if the IR is such that the call to function f is dce'd based on %cmp .

[anna]

We cannot see the latest comments about the test file in the current diff, because I changed the file name to 'compare-unescaped.ll' instead of 'compared-unescaped.ll' :(
I have marked all comments as done in diff 4.

lib/Transforms/InstCombine/InstructionCombining.cpp

if (!isa<BitCastInst>(Operand) &&
         return new BitCastInst(NGEP, GEP.getType());
       }
     }
   }
 
   return nullptr;
 }
 
+static bool isFoldableCmpForUnescapedAlloc(Instruction *CmpOp) {
+  switch (CmpOp->getOpcode()) {
+  default:
+    return false;
+  case Instruction::Load: {
+    LoadInst *LI = cast<LoadInst>(CmpOp);
+    // comparison to global pointer
+    if (isa<GlobalVariable>(LI->getPointerOperand()))
+      return true;
+    return false;
+  }
+  }
+}
+
 static bool
 isAllocSiteRemovable(Instruction *AI, SmallVectorImpl<WeakVH> &Users,
                      const TargetLibraryInfo *TLI) {
   SmallVector<Instruction*, 4> Worklist;
   Worklist.push_back(AI);
 
   do {
     Instruction *PI = Worklist.pop_back_val();
     for (User *U : PI->users()) {
       Instruction *I = cast<Instruction>(U);
       switch (I->getOpcode()) {
       default:
         // Give up the moment we see something we can't handle.
         return false;
 
       case Instruction::BitCast:
       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.
-        if (!ICI->isEquality() || !isa<ConstantPointerNull>(ICI->getOperand(1)))
+        if (!ICI->isEquality())
+          return false;
+
+        if (!isa<ConstantPointerNull>(ICI->getOperand(1))) {
+          Instruction *CmpOp0 = dyn_cast<Instruction>(ICI->getOperand(0));
+          Instruction *CmpOp1;
+          if (CmpOp0 == PI)
+            CmpOp1 = dyn_cast<Instruction>(ICI->getOperand(1));
+          else
+            CmpOp1 = CmpOp0;
+          // we fold comparisons in some conditions provided the alloc has not
+          // escaped
+          if (!CmpOp1 || !isFoldableCmpForUnescapedAlloc(CmpOp1))
             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

+; RUN: opt -instcombine -S %s | FileCheck %s
+
+@gp= global i32* null, align 8
+
+declare i8* @malloc(i64) #1
+
+define i1 @compare_global_trivialeq() {
+  %m = call i8* @malloc(i64 4)
+  %bc = bitcast i8* %m to i32*
+  %lgp = load i32*, i32** @gp, align 8
+  %cmp = icmp eq i32* %bc, %lgp
+  ret i1 %cmp
+; CHECK-LABEL: compare_global_trivialeq
+; CHECK: ret i1 false
+}
+
+define i1 @compare_global_trivialne(){
+  %m = call i8* @malloc(i64 4)
+  %bc = bitcast i8* %m to i32*
+  %lgp = load i32*, i32** @gp, align 8
+  %cmp = icmp ne i32* %bc, %lgp
+  ret i1 %cmp
+; CHECK-LABEL: compare_global_trivialne
+; CHECK: ret i1 true 
+}
+
+
+; Although the %m is marked nocapture in the deopt operand in call to function f,
+; we cannot remove the alloc site: call to malloc 
+declare void @f()
+define i32 @compare_and_call_with_deopt(){
+; CHECK-LABEL: compare_and_call_with_deopt
+  %m = call i8* @malloc(i64 24)
+  %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
+}