[InstSimplify] Fold icmp comparing GEPs with local allocation

[ParkHanbum]

Summary

alive2 verification : https://alive2.llvm.org/ce/z/Po2nL4

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

2797–2798

Variable names in LLVM start with an uppercase letter.

2800

This condition isn't wrong, but it's also not as accurate as it could be.

Let's say LHSSize = 4, LHSOffset = 0, RHSSize = 2, RHSOffset = 2 with LHSOffset - RHSOffset = -2. These can be equal.

Then consider LHSSize = 4, LHSOffset = 2, RHSSize = 2, RHSOffset = 0 with LHSOffset - RHSOffset = 2. These cannot be equal.

As you can see, the sign of the result matters and we should not just take the absolute value.

I believe the condition should be Dist.isNonNegative() ? Dist.ult(LHSSize) : (-Dist).ult(RHSSize).

[ParkHanbum]

updated the code according to nikic's comment.

This condition isn't wrong, but it's also not as accurate as it could be.

Let's say LHSSize = 4, LHSOffset = 0, RHSSize = 2, RHSOffset = 2 with LHSOffset - RHSOffset = -2. These can be equal.

Then consider LHSSize = 4, LHSOffset = 2, RHSSize = 2, RHSOffset = 0 with LHSOffset - RHSOffset = 2. These cannot be equal.

As you can see, the sign of the result matters and we should not just take the absolute value.

I believe the condition should be Dist.isNonNegative() ? Dist.ult(LHSSize) : (-Dist).ult(RHSSize).

[nikic]

This mostly looks good to me.

As implemented, there was a potential issue here where you would get an assertion failure due to different bit widths if certain address space casts were involved. I've opted to make that impossible in https://github.com/llvm/llvm-project/commit/793eb0c0e4ffadc1cfebcda0c0cb1bcc2311def2 rather than have you introduce extra extensions here.

llvm/lib/Analysis/InstructionSimplify.cpp

2798

Combine declaration and initialization.

llvm/test/Transforms/InstSimplify/cmp-alloca-offsets.ll

219

We should have some additional test cases that work on differently-sized allocas, to show that the check is asymmetric. E.g. allocas with size 2 and 4 with effective diffs 2 and -2.

[ParkHanbum]

there was such a problem. I didn't know!! thanks for letting me.

llvm/lib/Analysis/InstructionSimplify.cpp

2797–2798

shoud I have to declare and assign Dist at the same time?

[ParkHanbum]

add testcases!

[nikic]

LGTM. If you need me to commit this for you, can you please share the Name <email> to use for attribution?

[ParkHanbum]

sure, I use email [e-mail] and name is Hanbum Park!

llvm/test/Transforms/InstSimplify/cmp-alloca-offsets.ll

219

added test cases!

[ParkHanbum]

@nikic thanks you for your review and others!

llvm/lib/Analysis/InstructionSimplify.cpp

if (haveNonOverlappingStorage(LHS, RHS)) {
         if (auto *I = dyn_cast<Instruction>(V))
           return I->getFunction();
         if (auto *A = dyn_cast<Argument>(V))
           return A->getParent();
         return nullptr;
       }(LHS);
       Opts.NullIsUnknownSize = F ? NullPointerIsDefined(F) : true;
       if (getObjectSize(LHS, LHSSize, DL, TLI, Opts) &&
-          getObjectSize(RHS, RHSSize, DL, TLI, Opts) &&
-          !LHSOffset.isNegative() && !RHSOffset.isNegative() &&
-          LHSOffset.ult(LHSSize) && RHSOffset.ult(RHSSize)) {
+          getObjectSize(RHS, RHSSize, DL, TLI, Opts)) {
+        APInt Dist = LHSOffset - RHSOffset;
+        if (Dist.isNonNegative() ? Dist.ult(LHSSize) : (-Dist).ult(RHSSize))
           return ConstantInt::get(getCompareTy(LHS),
                                   !CmpInst::isTrueWhenEqual(Pred));
       }
     }
 
     // If one side of the equality comparison must come from a noalias call
     // (meaning a system memory allocation function), and the other side must
     // come from a pointer that cannot overlap with dynamically-allocated
     // memory within the lifetime of the current function (allocas, byval
     // arguments, globals), then determine the comparison result here.

llvm/test/Transforms/InstSimplify/cmp-alloca-offsets.ll

 ;
   %a = alloca i8, i32 4
   %b = alloca i8, i32 4
   %a.off = getelementptr i8, ptr %a, i64 4
   %res = icmp ne ptr %a.off, %b
   ret i1 %res
 }
 
-; FIXME: Can't be equal
 define i1 @positive_non_equal_end() {
 ; CHECK-LABEL: @positive_non_equal_end(
-; CHECK-NEXT:    [[A:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 4
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 4
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne ptr [[A_OFF]], [[B_OFF]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %a = alloca i8, i32 4
   %b = alloca i8, i32 4
   %a.off = getelementptr i8, ptr %a, i64 4
   %b.off = getelementptr i8, ptr %b, i64 4
   %res = icmp ne ptr %a.off, %b.off
   ret i1 %res
 }
;
   %a = alloca i8, i32 4
   %b = alloca i8, i32 4
   %a.off = getelementptr i8, ptr %a, i64 -4
   %b.off = getelementptr i8, ptr %b, i64 -8
   %res = icmp ne ptr %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
 define i1 @mixed_offsets1() {
 ; CHECK-LABEL: @mixed_offsets1(
-; CHECK-NEXT:    [[A:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 -1
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 2
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne ptr [[A_OFF]], [[B_OFF]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %a = alloca i8, i32 4
   %b = alloca i8, i32 4
   %a.off = getelementptr i8, ptr %a, i64 -1
   %b.off = getelementptr i8, ptr %b, i64 2
   %res = icmp ne ptr %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
 define i1 @mixed_offsets2() {
 ; CHECK-LABEL: @mixed_offsets2(
-; CHECK-NEXT:    [[A:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 1
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 -2
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne ptr [[A_OFF]], [[B_OFF]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %a = alloca i8, i32 4
   %b = alloca i8, i32 4
   %a.off = getelementptr i8, ptr %a, i64 1
   %b.off = getelementptr i8, ptr %b, i64 -2
   %res = icmp ne ptr %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
 define i1 @negative_in_other() {
 ; CHECK-LABEL: @negative_in_other(
+; CHECK-NEXT:    ret i1 true
+;
+  %a = alloca i8, i32 4
+  %b = alloca i8, i32 4
+  %a.off = getelementptr i8, ptr %a, i64 -3
+  %b.off = getelementptr i8, ptr %b, i64 -2
+  %res = icmp ne ptr %a.off, %b.off
+  ret i1 %res
+}
+
+define i1 @mixed_alloca_size1() {
+; CHECK-LABEL: @mixed_alloca_size1(
+; CHECK-NEXT:    ret i1 true
+;
+  %a = alloca i8, i32 2
+  %b = alloca i8, i32 4
+  %a.off = getelementptr i8, ptr %a, i64 1
+  %b.off = getelementptr i8, ptr %b, i64 3
+  %res = icmp ne ptr %a.off, %b.off
+  ret i1 %res
+}
+
+define i1 @mixed_alloca_size2() {
+; CHECK-LABEL: @mixed_alloca_size2(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 -3
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 -2
+; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 2, align 1
+; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 1
+; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 3
 ; CHECK-NEXT:    [[RES:%.*]] = icmp ne ptr [[A_OFF]], [[B_OFF]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = alloca i8, i32 4
+  %b = alloca i8, i32 2
+  %a.off = getelementptr i8, ptr %a, i64 1
+  %b.off = getelementptr i8, ptr %b, i64 3
+  %res = icmp ne ptr %a.off, %b.off
+  ret i1 %res
+}
+
+define i1 @mixed_alloca_size3() {
+; CHECK-LABEL: @mixed_alloca_size3(
+; CHECK-NEXT:    [[A:%.*]] = alloca i8, i32 2, align 1
+; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 4, align 1
+; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, ptr [[A]], i64 -1
+; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, ptr [[B]], i64 -3
+; CHECK-NEXT:    [[RES:%.*]] = icmp ne ptr [[A_OFF]], [[B_OFF]]
+; CHECK-NEXT:    ret i1 [[RES]]
+;
+  %a = alloca i8, i32 2
   %b = alloca i8, i32 4
-  %a.off = getelementptr i8, ptr %a, i64 -3
-  %b.off = getelementptr i8, ptr %b, i64 -2
+  %a.off = getelementptr i8, ptr %a, i64 -1
+  %b.off = getelementptr i8, ptr %b, i64 -3
   %res = icmp ne ptr %a.off, %b.off
   ret i1 %res
 }
 
+define i1 @mixed_alloca_size4() {
+; CHECK-LABEL: @mixed_alloca_size4(
+; CHECK-NEXT:    ret i1 true
+;
+  %a = alloca i8, i32 4
+  %b = alloca i8, i32 2
+  %a.off = getelementptr i8, ptr %a, i64 -1
+  %b.off = getelementptr i8, ptr %b, i64 -3
+  %res = icmp ne ptr %a.off, %b.off
+  ret i1 %res
+}
 
 attributes #0 = { null_pointer_is_valid }

llvm/test/Transforms/InstSimplify/past-the-end.ll

;
   %t = icmp eq ptr %m, %n
   ret i1 %t
 }
 
 ; Comparing past-the-end addresses of two distinct allocas. Never equal.
 
 define zeroext i1 @both_past_the_end_alloca() {
 ; CHECK-LABEL: @both_past_the_end_alloca(
-; CHECK:         [[M:%.*]] = alloca i32
-; CHECK-NEXT:    [[N:%.*]] = alloca i32
-; CHECK-NEXT:    [[X:%.*]] = getelementptr i32, ptr [[M]], i32 1
-; CHECK-NEXT:    [[Y:%.*]] = getelementptr i32, ptr [[N]], i32 1
-; CHECK-NEXT:    [[T:%.*]] = icmp eq ptr [[X]], [[Y]]
-; CHECK-NEXT:    ret i1 [[T]]
+; CHECK-NEXT:    ret i1 false
 ;
   %m = alloca i32
   %n = alloca i32
   %x = getelementptr i32, ptr %m, i32 1
   %y = getelementptr i32, ptr %n, i32 1
   %t = icmp eq ptr %x, %y
   ret i1 %t
-  ; TODO: refine this
 }
 
 ; Comparing past-the-end addresses of one alloca to the base address
 ; of another. Can't fold this.
 
 define zeroext i1 @just_one_past_the_end_alloca() {
 ; CHECK-LABEL: @just_one_past_the_end_alloca(
 ; CHECK:         [[M:%.*]] = alloca i32