[instsimplify] Generalize offset handling when compare pointers derived from allocas

[reames]

Summary

This generalizes the offset check used when figuring out if two pointers derived from two different allocas (or one alloca and one global) can be equal.

Specifically, it handles the following cases:

• Both offsets are positive, but one or more crosses into the second object, but by less than the offset on the other pointer. (i.e. offset b is strictly greater than the offset a can obtain into object b.)
• Both negative offsets
• Mix of negative and positive offsets

I vaguely think there should be a more concise way to write these checks. Anyone see one?

[nikic]

I vaguely think there should be a more concise way to write these checks. Anyone see one?

As we're dealing with equality comparisons here, we can subtract a common offset from both sides. So rather than dealing with LHS + LHSOffset == RHS + RHSOffset, we can instead deal with LHS + Offset == RHS, where Offset = LHSOffset - RHSOffset. We should be able to fold that if and only if Offset > -MinSize(RHS) and Offset < MinSize(LHS).

Does that sound about right?

[durin42]

In D120083#3330734, @nikic wrote:

I vaguely think there should be a more concise way to write these checks. Anyone see one?

As we're dealing with equality comparisons here, we can subtract a common offset from both sides. So rather than dealing with LHS + LHSOffset == RHS + RHSOffset, we can instead deal with LHS + Offset == RHS, where Offset = LHSOffset - RHSOffset. We should be able to fold that if and only if Offset > -MinSize(RHS) and Offset < MinSize(LHS).

Does that sound about right?

It took some work to convince myself, but I think that's right.

[nikic]

I like the general improvement here, but I think this will be a lot clearer if restructured as discussed above.

[reames]

Closing review I'm not currently working on, and am unlikely to get back to in near future. Will reopen if priorities change.

llvm/lib/Analysis/InstructionSimplify.cpp

if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
     if (isa<AllocaInst>(LHS) &&
         (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
       uint64_t LHSSize, RHSSize;
       ObjectSizeOpts Opts;
       Opts.EvalMode = ObjectSizeOpts::Mode::Min;
       Opts.NullIsUnknownSize =
           NullPointerIsDefined(cast<AllocaInst>(LHS)->getFunction());
       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)) {
+        auto CanNotOverlap = [&]() -> bool {
+          if (!LHSOffset.isNegative() && !RHSOffset.isNegative()) {
+            return ((LHSOffset.ult(LHSSize) ||
+                     (LHSOffset - LHSSize).ult(RHSOffset)) &&
+                    (RHSOffset.ult(RHSSize) ||
+                     (RHSOffset - RHSSize).ult(LHSOffset)));
+          }
+          auto LAbs = LHSOffset.sext(LHSOffset.getBitWidth() + 1).abs();
+          auto RAbs = RHSOffset.sext(RHSOffset.getBitWidth() + 1).abs();
+          if (LHSOffset.isNegative() && RHSOffset.isNegative())
+            // TODO: Add corresponding max offset in other case (inverse
+            // of the positive version)
+            return (LAbs.ult(RHSSize) && RAbs.ult(LHSSize));
+          if (!LHSOffset.isNegative() && RHSOffset.isNegative())
+            return (LAbs + RAbs).ult(LHSSize);
+          if (LHSOffset.isNegative() && !RHSOffset.isNegative())
+            return (LAbs + RAbs).ult(RHSSize);
+          llvm_unreachable("");
+        };
+        if (CanNotOverlap())
           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, i8* %a, i64 4
   %b.off = getelementptr i8, i8* %b, i64 0
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
+; 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, i8* [[A]], i64 4
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, i8* [[B]], i64 4
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i8* [[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, i8* %a, i64 4
   %b.off = getelementptr i8, i8* %b, i64 4
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
;
   %a = alloca i8, i32 4
   %b = alloca i8, i32 4
   %a.off = getelementptr i8, i8* %a, i64 -4
   %b.off = getelementptr i8, i8* %b, i64 -8
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
+; 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, i8* [[A]], i64 -1
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, i8* [[B]], i64 2
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i8* [[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, i8* %a, i64 -1
   %b.off = getelementptr i8, i8* %b, i64 2
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
+; 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, i8* [[A]], i64 1
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, i8* [[B]], i64 -2
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i8* [[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, i8* %a, i64 1
   %b.off = getelementptr i8, i8* %b, i64 -2
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
 
-; FIXME: Can't be equal
+; Can't be equal
 define i1 @negative_in_other() {
 ; CHECK-LABEL: @negative_in_other(
-; CHECK-NEXT:    [[A:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[B:%.*]] = alloca i8, i32 4, align 1
-; CHECK-NEXT:    [[A_OFF:%.*]] = getelementptr i8, i8* [[A]], i64 -3
-; CHECK-NEXT:    [[B_OFF:%.*]] = getelementptr i8, i8* [[B]], i64 -2
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i8* [[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, i8* %a, i64 -3
   %b.off = getelementptr i8, i8* %b, i64 -2
   %res = icmp ne i8* %a.off, %b.off
   ret i1 %res
 }
 
 
 attributes #0 = { null_pointer_is_valid }

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

;
   %t = icmp eq i32* %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, i32* [[M]], i32 1
-; CHECK-NEXT:    [[Y:%.*]] = getelementptr i32, i32* [[N]], i32 1
-; CHECK-NEXT:    [[T:%.*]] = icmp eq i32* [[X]], [[Y]]
-; CHECK-NEXT:    ret i1 [[T]]
+; CHECK-NEXT:    ret i1 false
 ;
   %m = alloca i32
   %n = alloca i32
   %x = getelementptr i32, i32* %m, i32 1
   %y = getelementptr i32, i32* %n, i32 1
   %t = icmp eq i32* %x, %y
   ret i1 %t
   ; TODO: refine this