[ConstantFold] Make icmp of gep fold offset based

[nikic]

Summary

We can fold an equality or unsigned icmp between base+offset1 and base+offset2 with inbounds offsets by comparison the offsets directly.

This replaces a pair of specialized folds that tried to reason based on the GEP structure instead. One of those folds was plain wrong (because it does not account for negative offsets), while the other is unnecessarily complicated and limited (e.g. it will fail with bitcasts involved).

The disadvantage of this change is that it requires data layout, so the fold is no longer performed by datalayout-independent constant folding. I don't think this is a loss in practice, but it does regress the ConstantExprFold.ll test, which checks folding without running any passes.

[spatel]

llvm/lib/Analysis/ConstantFolding.cpp

1258

Similar to your comment in D116168 - I'm not sure why we specify this parameter as unsigned instead of the actual enum. I see that we are not including any headers via ConstantFolding.h, so maybe there's some compile-time justification for it?

1260

!ICmpInst::isSigned(CmpPred) ?

llvm/test/Transforms/InstSimplify/ConstProp/icmp-global.ll

202

Add a comment for this test to explain that a 'true' result would be a miscompile (unlike the 'inbounds' variation above here)?

[nikic]

Use !isSigned, add comment

[nikic]

llvm/lib/Analysis/ConstantFolding.cpp

1258

Yeah, I believe the reason for the unsigned is that it's impossible to forward-declare a nested type in C++.

What do you think about the new variant that does a cast right at the start of the function?

[spatel]

LGTM

llvm/lib/Analysis/ConstantFolding.cpp

1258

Sure, that's better. That means we could replace the checks for EQ/NE around line 1242 with ICmpInst::isEquality(Predicate) as another small cleanup.

llvm/lib/Analysis/ConstantFolding.cpp

 
 Constant *llvm::ConstantFoldInstOperands(Instruction *I,
                                          ArrayRef<Constant *> Ops,
                                          const DataLayout &DL,
                                          const TargetLibraryInfo *TLI) {
   return ConstantFoldInstOperandsImpl(I, I->getOpcode(), Ops, DL, TLI);
 }
 
-Constant *llvm::ConstantFoldCompareInstOperands(unsigned Predicate,
+Constant *llvm::ConstantFoldCompareInstOperands(unsigned IntPredicate,
                                                 Constant *Ops0, Constant *Ops1,
                                                 const DataLayout &DL,
                                                 const TargetLibraryInfo *TLI) {
+  CmpInst::Predicate Predicate = (CmpInst::Predicate)IntPredicate;
   // fold: icmp (inttoptr x), null         -> icmp x, 0
   // fold: icmp null, (inttoptr x)         -> icmp 0, x
   // fold: icmp (ptrtoint x), 0            -> icmp x, null
   // fold: icmp 0, (ptrtoint x)            -> icmp null, x
   // fold: icmp (inttoptr x), (inttoptr y) -> icmp trunc/zext x, trunc/zext y
   // fold: icmp (ptrtoint x), (ptrtoint y) -> icmp x, y
   //
   // FIXME: The following comment is out of data and the DataLayout is here now.
if ((Predicate == ICmpInst::ICMP_EQ || Predicate == ICmpInst::ICMP_NE) &&
       Constant *LHS = ConstantFoldCompareInstOperands(
           Predicate, CE0->getOperand(0), Ops1, DL, TLI);
       Constant *RHS = ConstantFoldCompareInstOperands(
           Predicate, CE0->getOperand(1), Ops1, DL, TLI);
       unsigned OpC =
         Predicate == ICmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
       return ConstantFoldBinaryOpOperands(OpC, LHS, RHS, DL);
     }
+
+    // Convert pointer comparison (base+offset1) pred (base+offset2) into
+    // offset1 pred offset2, for the case where the offset is inbounds. This
+    // only works for equality and unsigned comparison, as inbounds permits
+    // crossing the sign boundary. However, the offset comparison itself is
+    // signed.
+    if (Ops0->getType()->isPointerTy() && !ICmpInst::isSigned(Predicate)) {
+      unsigned IndexWidth = DL.getIndexTypeSizeInBits(Ops0->getType());
+      APInt Offset0(IndexWidth, 0);
+      Value *Stripped0 =
+          Ops0->stripAndAccumulateInBoundsConstantOffsets(DL, Offset0);
+      APInt Offset1(IndexWidth, 0);
+      Value *Stripped1 =
+          Ops1->stripAndAccumulateInBoundsConstantOffsets(DL, Offset1);
+      if (Stripped0 == Stripped1)
+        return ConstantExpr::getCompare(
+            ICmpInst::getSignedPredicate(Predicate),
+            ConstantInt::get(CE0->getContext(), Offset0),
+            ConstantInt::get(CE0->getContext(), Offset1));
+    }
   } else if (isa<ConstantExpr>(Ops1)) {
     // If RHS is a constant expression, but the left side isn't, swap the
     // operands and try again.
-    Predicate = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)Predicate);
+    Predicate = ICmpInst::getSwappedPredicate(Predicate);
     return ConstantFoldCompareInstOperands(Predicate, Ops1, Ops0, DL, TLI);
   }
 
   return ConstantExpr::getCompare(Predicate, Ops0, Ops1);
 }
 
 Constant *llvm::ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op,
                                            const DataLayout &DL) {

llvm/lib/IR/ConstantFold.cpp

if (StructType *STy = dyn_cast<StructType>(Ty)) {
     return true;
 
   } else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
     return isMaybeZeroSizedType(ATy->getElementType());
   }
   return false;
 }
 
-/// Compare the two constants as though they were getelementptr indices.
-/// This allows coercion of the types to be the same thing.
-///
-/// If the two constants are the "same" (after coercion), return 0.  If the
-/// first is less than the second, return -1, if the second is less than the
-/// first, return 1.  If the constants are not integral, return -2.
-///
-static int IdxCompare(Constant *C1, Constant *C2, Type *ElTy) {
-  if (C1 == C2) return 0;
-
-  // Ok, we found a different index.  If they are not ConstantInt, we can't do
-  // anything with them.
-  if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
-    return -2; // don't know!
-
-  // We cannot compare the indices if they don't fit in an int64_t.
-  if (cast<ConstantInt>(C1)->getValue().getActiveBits() > 64 ||
-      cast<ConstantInt>(C2)->getValue().getActiveBits() > 64)
-    return -2; // don't know!
-
-  // Ok, we have two differing integer indices.  Sign extend them to be the same
-  // type.
-  int64_t C1Val = cast<ConstantInt>(C1)->getSExtValue();
-  int64_t C2Val = cast<ConstantInt>(C2)->getSExtValue();
-
-  if (C1Val == C2Val) return 0;  // They are equal
-
-  // If the type being indexed over is really just a zero sized type, there is
-  // no pointer difference being made here.
-  if (isMaybeZeroSizedType(ElTy))
-    return -2; // dunno.
-
-  // If they are really different, now that they are the same type, then we
-  // found a difference!
-  if (C1Val < C2Val)
-    return -1;
-  else
-    return 1;
-}
-
 /// This function determines if there is anything we can decide about the two
 /// constants provided. This doesn't need to handle simple things like
 /// ConstantFP comparisons, but should instead handle ConstantExprs.
 /// If we can determine that the two constants have a particular relation to
 /// each other, we should return the corresponding FCmpInst predicate,
 /// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in
 /// ConstantFoldCompareInstruction.
 ///
case Instruction::GetElementPtr: {
         // Otherwise, we can't really say if the first operand is null or not.
       } else if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) {
         if (isa<ConstantPointerNull>(CE1Op0)) {
           // If its not weak linkage, the GVal must have a non-zero address
           // so the result is less-than
           if (!GV2->hasExternalWeakLinkage())
             return ICmpInst::ICMP_ULT;
         } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
-          if (GV == GV2) {
-            // If this is a getelementptr of the same global, then it must be
-            // different.  Because the types must match, the getelementptr could
-            // only have at most one index, and because we fold getelementptr's
-            // with a single zero index, it must be nonzero.
-            assert(CE1->getNumOperands() == 2 &&
-                   !CE1->getOperand(1)->isNullValue() &&
-                   "Surprising getelementptr!");
-            return ICmpInst::ICMP_UGT;
-          } else {
+          if (GV != GV2) {
             if (CE1GEP->hasAllZeroIndices())
               return areGlobalsPotentiallyEqual(GV, GV2);
             return ICmpInst::BAD_ICMP_PREDICATE;
           }
         }
       } else {
         ConstantExpr *CE2 = cast<ConstantExpr>(V2);
         Constant *CE2Op0 = CE2->getOperand(0);
case Instruction::GetElementPtr: {
             // Don't know relative ordering, but check for inequality.
             if (CE1Op0 != CE2Op0) {
               GEPOperator *CE2GEP = cast<GEPOperator>(CE2);
               if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
                 return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
                                                   cast<GlobalValue>(CE2Op0));
               return ICmpInst::BAD_ICMP_PREDICATE;
             }
-            // Ok, we know that both getelementptr instructions are based on the
-            // same global.  From this, we can precisely determine the relative
-            // ordering of the resultant pointers.
-            unsigned i = 1;
-
-            // The logic below assumes that the result of the comparison
-            // can be determined by finding the first index that differs.
-            // This doesn't work if there is over-indexing in any
-            // subsequent indices, so check for that case first.
-            if (!CE1->isGEPWithNoNotionalOverIndexing() ||
-                !CE2->isGEPWithNoNotionalOverIndexing())
-               return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
-
-            // Compare all of the operands the GEP's have in common.
-            gep_type_iterator GTI = gep_type_begin(CE1);
-            for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
-                 ++i, ++GTI)
-              switch (IdxCompare(CE1->getOperand(i),
-                                 CE2->getOperand(i), GTI.getIndexedType())) {
-              case -1: return ICmpInst::ICMP_ULT;
-              case 1:  return ICmpInst::ICMP_UGT;
-              case -2: return ICmpInst::BAD_ICMP_PREDICATE;
-              }
-
-            // Ok, we ran out of things they have in common.  If any leftovers
-            // are non-zero then we have a difference, otherwise we are equal.
-            for (; i < CE1->getNumOperands(); ++i)
-              if (!CE1->getOperand(i)->isNullValue()) {
-                if (isa<ConstantInt>(CE1->getOperand(i)))
-                  return ICmpInst::ICMP_UGT;
-                else
-                  return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
-              }
-
-            for (; i < CE2->getNumOperands(); ++i)
-              if (!CE2->getOperand(i)->isNullValue()) {
-                if (isa<ConstantInt>(CE2->getOperand(i)))
-                  return ICmpInst::ICMP_ULT;
-                else
-                  return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
-              }
-            return ICmpInst::ICMP_EQ;
           }
         }
       }
       break;
     }
     default:
       break;
     }

llvm/test/Assembler/ConstantExprFold.ll

 @5 = global i64* inttoptr (i64 and (i64 ptrtoint (i64* @A to i64), i64 0) to i64*) ; X & 0 == 0
 @6 = global i64* inttoptr (i64 and (i64 ptrtoint (i64* @A to i64), i64 -1) to i64*) ; X & -1 == X
 @7 = global i64 or (i64 ptrtoint (i64* @A to i64), i64 -1)  ; X | -1 == -1
 @8 = global i64* inttoptr (i64 xor (i64 ptrtoint (i64* @A to i64), i64 0) to i64*) ; X ^ 0 == X
 
 %Ty = type { i32, i32 }
 @B = external global %Ty
 
+; @9 and @11 will be folded by the target-dependent constant folder instead.
 @9 = global i1 icmp ult (i64* @A, i64* getelementptr (i64, i64* @A, i64 1))        ; true
 @10 = global i1 icmp slt (i64* @A, i64* getelementptr (i64, i64* @A, i64 0))        ; false
 @11 = global i1 icmp ult (i32* getelementptr (%Ty, %Ty* @B, i64 0, i32 0),
   i32* getelementptr (%Ty, %Ty* @B, i64 0, i32 1))            ; true
 ;global i1 icmp ne (i64* @A, i64* bitcast (%Ty* @B to i64*))                 ; true
 
 ; PR2206
 @cons = weak global i32 0, align 8              ; <i32*> [#uses=1]

 ; CHECK: @[[GLOB2:[0-9]+]] = global i64* null
 ; CHECK: @[[GLOB3:[0-9]+]] = global i64* @A
 ; CHECK: @[[GLOB4:[0-9]+]] = global i64* null
 ; CHECK: @[[GLOB5:[0-9]+]] = global i64* null
 ; CHECK: @[[GLOB6:[0-9]+]] = global i64* @A
 ; CHECK: @[[GLOB7:[0-9]+]] = global i64 -1
 ; CHECK: @[[GLOB8:[0-9]+]] = global i64* @A
 ; CHECK: @[[B:[a-zA-Z0-9_$"\\.-]+]] = external global [[TY:%.*]]
-; CHECK: @[[GLOB9:[0-9]+]] = global i1 true
+; CHECK: @[[GLOB9:[0-9]+]] = global i1 icmp ugt (i64* getelementptr inbounds (i64, i64* @A, i64 1), i64* @A)
 ; CHECK: @[[GLOB10:[0-9]+]] = global i1 false
-; CHECK: @[[GLOB11:[0-9]+]] = global i1 true
+; CHECK: @[[GLOB11:[0-9]+]] = global i1 icmp ult (i32* getelementptr inbounds ([[TY:%.*]], %Ty* @B, i64 0, i32 0), i32* getelementptr inbounds ([[TY]], %Ty* @B, i64 0, i32 1))
 ; CHECK: @[[CONS:[a-zA-Z0-9_$"\\.-]+]] = weak global i32 0, align 8
 ; CHECK: @[[GLOB12:[0-9]+]] = global i64 0
 ; CHECK: @[[GLOB13:[0-9]+]] = global <2 x i8*> undef
 ; CHECK: @[[GLOB14:[0-9]+]] = global <2 x i8*> undef
 ; CHECK: @[[GLOB15:[0-9]+]] = global <2 x i8*> zeroinitializer
 ; CHECK: @[[GLOB16:[0-9]+]] = global <2 x i8*> zeroinitializer
 ;.
 define void @dummy() {
 ; CHECK-LABEL: @dummy(
 ; CHECK-NEXT:    ret void
 ;
   ret void
 }

llvm/test/Transforms/InstSimplify/ConstProp/icmp-global.ll

 ; CHECK-LABEL: @global_gep_sgt_global(
 ; CHECK-NEXT:    ret i1 icmp sgt ([2 x i32]* getelementptr inbounds ([2 x i32], [2 x i32]* @g, i64 1), [2 x i32]* @g)
 ;
   %gep = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 1
   %cmp = icmp sgt [2 x i32]* %gep, @g
   ret i1 %cmp
 }
 
+; This should not fold to true, as the offset is negative.
 define i1 @global_gep_ugt_global_neg_offset() {
 ; CHECK-LABEL: @global_gep_ugt_global_neg_offset(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 icmp ugt ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* @g, i64 -1), [2 x i32]* @g)
 ;
   %gep = getelementptr [2 x i32], [2 x i32]* @g, i64 -1
   %cmp = icmp ugt [2 x i32]* %gep, @g
   ret i1 %cmp
 }
 
 define i1 @global_gep_sgt_global_neg_offset() {
 ; CHECK-LABEL: @global_gep_sgt_global_neg_offset(
;
   %gep1 = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 0, i64 0
   %gep2 = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 0, i64 1
   %cmp = icmp sgt i32* %gep2, %gep1
   ret i1 %cmp
 }
 
 define i1 @global_gep_ugt_global_gep_complex() {
 ; CHECK-LABEL: @global_gep_ugt_global_gep_complex(
-; CHECK-NEXT:    ret i1 icmp ugt (i32* bitcast (i8* getelementptr inbounds (i8, i8* bitcast ([2 x i32]* @g to i8*), i64 2) to i32*), i32* getelementptr inbounds ([2 x i32], [2 x i32]* @g, i64 0, i64 0))
+; CHECK-NEXT:    ret i1 true
 ;
   %gep1 = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 0, i64 0
   %gep2 = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 0, i64 0
   %gep2.cast = bitcast i32* %gep2 to i8*
   %gep3 = getelementptr inbounds i8, i8* %gep2.cast, i64 2
   %gep3.cast = bitcast i8* %gep3 to i32*
   %cmp = icmp ugt i32* %gep3.cast, %gep1
   ret i1 %cmp
 }