[InstSimplify] Fold icmp comparing GEPs with global values

[ParkHanbum]

Summary

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

[nikic]

This needs to be split in two patches, one for the InstSimplify change and one for the ConstantFold change. In InstSimplify, you need to modify the code around the existing haveNonOverlappingStorage() call. What you need to do is subtract the offsets and reason about how the difference relates to the object size. It does not make sense to only handle the case where the offsets are the same.

[ParkHanbum]

I modified it according to nikic's advice.

[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).

[ParkHanbum]

@nikic It looks neatly organized to me. how do you think?

llvm/lib/IR/ConstantFold.cpp

case Instruction::GetElementPtr: {
         }
       } else if (const auto *CE2GEP = dyn_cast<GEPOperator>(V2)) {
         // By far the most common case to handle is when the base pointers are
         // obviously to the same global.
         const Constant *CE2Op0 = cast<Constant>(CE2GEP->getPointerOperand());
         if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
           // Don't know relative ordering, but check for inequality.
           if (CE1Op0 != CE2Op0) {
-            if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
+            DataLayout DL(cast<GlobalValue>(CE1Op0)->getParent());
+            auto CE1Op0Size = DL.getTypeAllocSize(CE1Op0->getType());
+            auto CE2Op0Size = DL.getTypeAllocSize(CE2Op0->getType());
+            unsigned BitWidth = DL.getIndexTypeSizeInBits(CE1Op0->getType());
+            APInt CE1GEPOffset(BitWidth, 0);
+            BitWidth = DL.getIndexTypeSizeInBits(CE2Op0->getType());
+            APInt CE2GEPOffset(BitWidth, 0);
+            CE1GEP->accumulateConstantOffset(DL, CE1GEPOffset);
+            CE2GEP->accumulateConstantOffset(DL, CE2GEPOffset);
+
+            APInt Dist = CE1GEPOffset - CE2GEPOffset;
+            if (Dist.isNonNegative() ? Dist.ult(CE1Op0Size) : (-Dist).ult(CE2Op0Size))
               return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
                                                 cast<GlobalValue>(CE2Op0));
+
             return ICmpInst::BAD_ICMP_PREDICATE;
           }
         }
       }
       break;
     }
     default:
       break;

llvm/test/Transforms/InstSimplify/compare.ll

 define i1 @globals_inequal() {
 ; CHECK-LABEL: @globals_inequal(
 ; CHECK-NEXT:    ret i1 true
 ;
   %res = icmp ne ptr @A, @B
   ret i1 %res
 }
 
-; TODO: Never equal
 define i1 @globals_offset_inequal() {
 ; CHECK-LABEL: @globals_offset_inequal(
-; CHECK-NEXT:    ret i1 icmp ne (ptr getelementptr (i8, ptr @A, i32 1), ptr getelementptr (i8, ptr @B, i32 1))
+; CHECK-NEXT:    ret i1 true
 ;
   %a.off = getelementptr i8, ptr @A, i32 1
   %b.off = getelementptr i8, ptr @B, i32 1
   %res = icmp ne ptr %a.off, %b.off
   ret i1 %res
 }
 
 

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

;
   %t = icmp eq ptr @opte_a, @opte_b
   ret i1 %t
 }
 
 ; Comparing past-the-end addresses of two distinct globals. Never equal.
 
 define zeroext i1 @both_past_the_end() {
 ; CHECK-LABEL: @both_past_the_end(
-; CHECK:         ret i1 icmp eq (ptr getelementptr inbounds (i32, ptr @opte_a, i32 1), ptr getelementptr inbounds (i32, ptr @opte_b, i32 1))
+; CHECK:         ret i1 false
 ;
   %x = getelementptr i32, ptr @opte_a, i32 1
   %y = getelementptr i32, ptr @opte_b, i32 1
   %t = icmp eq ptr %x, %y
   ret i1 %t
-  ; TODO: refine this
 }
 
 ; Comparing past-the-end addresses of one global to the base address
 ; of another. Can't fold this.
 
 define zeroext i1 @just_one_past_the_end() {
 ; CHECK-LABEL: @just_one_past_the_end(
 ; CHECK:         ret i1 icmp eq (ptr getelementptr inbounds (i32, ptr @opte_a, i32 1), ptr @opte_b)