[InstCombine] Fold icmp(constants[x]) when the range of x is given

[XChy]

Summary

This patch extends foldCmpLoadFromIndexedGlobal to fold IR below:

define i1 @cmp_load_constant_array0(i64 %x){
entry:
  %cond = icmp ult i64 %x, 2
  br i1 %cond, label %case1, label %case2

case2:
  ret i1 0

case1:
  %isOK_ptr = getelementptr inbounds i32, ptr @CG, i64 %x
  %isOK = load i32, ptr %isOK_ptr
  %cond_inferred = icmp ult i32 %isOK, 3
  ret i1 %cond_inferred
}

Problem still:
Not globally optimized best.
Here I think if D152838 is accepted, that would be better.

Proof:
alive2

Related issue:
issue

[nikic]

This should be handled by the foldCmpLoadFromIndexedGlobal() fold, by first converting the icmp(load(gep(g, idx))) into icmp(idx) and then folding that icmp against the dominating condition.

That fold currently requires a very specific GEP source element type, but should be easy to generalize.

[XChy]

In D156657#4546067, @nikic wrote:

This should be handled by the foldCmpLoadFromIndexedGlobal() fold, by first converting the icmp(load(gep(g, idx))) into icmp(idx) and then folding that icmp against the dominating condition.

That fold currently requires a very specific GEP source element type, but should be easy to generalize.

Sure, I'll have a check.

[XChy]

Extends foldCmpLoadFromIndexedGlobal to fold.

[XChy]

Update tests.

[nikic]

It would be better to base this on collectOffset() and work in offset representation. Especially if you're interested in handling Rust, the type of the global and the GEP / loads will typically not line up (constant globals in Rust are usually i8 arrays, regardless of "real" type.)

[XChy]

In D156657#4547304, @nikic wrote:

It would be better to base this on collectOffset() and work in offset representation. Especially if you're interested in handling Rust, the type of the global and the GEP / loads will typically not line up (constant globals in Rust are usually i8 arrays, regardless of "real" type.)

Yes, such generlization in units of byte is necessary. It seems to be related to ptradd RFC?
Currently, this fold is still in units of array element . I'll try to refactor and generlize it.

llvm/test/Transforms/InstCombine/load-cmp.ll

346

Optimized well locally, but not globally.

[XChy]

Complete basically correct fold.

TODOs:

• Multi-variable testcases, Bitwidth-changed testcases
• Comments
• Performance/optimization to improve. When index is ax + by + .... + C, the longest distance we can step by is gcd(a,b,c,d, ....), not just one. Based on this we fold more precisely.

[nikic]

I think to start with, you should limit this to just the case where there is exactly one variable index (i.e. C*x or C*x+C2). Handling complex expressions is unlikely to be useful.

[XChy]

Already limit it to one variable. But I don't know why it is unlikely to be useful. From my perspective For multi-dimensional arrays, it's possible to have more than one index variable.

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

[XChy]

In D156657#4550996, @XChy wrote:

Already limit it to one variable. But I don't know why it is unlikely to be useful. From my perspective For multi-dimensional arrays, it's possible to have more than one index variable.

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

After trying, I don't think there is any way to do boundary-check (let things out of boundary lead to load poison) without modifying CFG. But InstCombine doesn't modify CFG. I haven't better idea here.

[XChy]

Update tests and FIXME: Boundary-check

[nikic]

Besides, there exists miscompilation, I found just now. Current state-machine doesn't emit the CmpInst/Poison to guarrantee the index/offset is always not negative. Lack of such range-check would lead to something triggering UB not to doing so. I need to check it later.

It's okay for transforms to remove UB (this is called "refinement" and done by many transforms). You just can't introduce new UB / poison that did not exist before.

[XChy]

Eliminate boundary-check.

[XChy]

Simplify LazyGetIndex function, and ready to be reviewed.

[XChy]

ping.

[goldstein.w.n]

In D156657#4639543, @XChy wrote:

ping.

nikic is on vacation for the next week, since he requested changes plan to let him get to it when he comes back.
Might have time to review later in the week, however.

[XChy]

In D156657#4639867, @goldstein.w.n wrote:

In D156657#4639543, @XChy wrote:

ping.

nikic is on vacation for the next week, since he requested changes plan to let him get to it when he comes back.
Might have time to review later in the week, however.

Thanks. That's OK. I hope this patch could be finished before the Phabricator shutdowns.

[XChy]

Polish comments.

llvm/include/llvm/Transforms/InstCombine/InstCombiner.h

class LLVM_LIBRARY_VISIBILITY InstCombiner {
   /// Only used to call target specific intrinsic combining.
   /// It must **NOT** be used for any other purpose, as InstCombine is a
   /// target-independent canonicalization transform.
   TargetTransformInfo &TTI;
 
 public:
   /// Maximum size of array considered when transforming.
   uint64_t MaxArraySizeForCombine = 0;
+  /// Maximum bytes of data considered when transforming.
+  uint64_t MaxDataSizeForCombine = 0;
 
   /// An IRBuilder that automatically inserts new instructions into the
   /// worklist.
   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
   BuilderTy &Builder;
 
 protected:
   /// A worklist of the instructions that need to be simplified.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

 //===- InstCombineCompares.cpp --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitICmp and visitFCmp functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/ConstantRange.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 

 /// this into some simple computation that does not need the load. For example
 /// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3".
 ///
 /// If AndCst is non-null, then the loaded value is masked with that constant
 /// before doing the comparison. This handles cases like "A[i]&4 == 0".
 Instruction *InstCombinerImpl::foldCmpLoadFromIndexedGlobal(
     LoadInst *LI, GetElementPtrInst *GEP, GlobalVariable *GV, CmpInst &ICI,
     ConstantInt *AndCst) {
-  if (LI->isVolatile() || LI->getType() != GEP->getResultElementType() ||
-      GV->getValueType() != GEP->getSourceElementType() ||
-      !GV->isConstant() || !GV->hasDefinitiveInitializer())
+  if (LI->isVolatile() || !GV->isConstant() || !GV->hasDefinitiveInitializer())
     return nullptr;
 
   Constant *Init = GV->getInitializer();
-  if (!isa<ConstantArray>(Init) && !isa<ConstantDataArray>(Init))
-    return nullptr;
+  uint64_t DataSize = DL.getTypeAllocSize(Init->getType());
 
-  uint64_t ArrayElementCount = Init->getType()->getArrayNumElements();
   // Don't blow up on huge arrays.
-  if (ArrayElementCount > MaxArraySizeForCombine)
+  if (DataSize > MaxDataSizeForCombine)
     return nullptr;
 
-  // There are many forms of this optimization we can handle, for now, just do
-  // the simple index into a single-dimensional array.
-  //
-  // Require: GEP GV, 0, i {{, constant indices}}
-  if (GEP->getNumOperands() < 3 ||
-      !isa<ConstantInt>(GEP->getOperand(1)) ||
-      !cast<ConstantInt>(GEP->getOperand(1))->isZero() ||
-      isa<Constant>(GEP->getOperand(2)))
-    return nullptr;
-
-  // Check that indices after the variable are constants and in-range for the
-  // type they index.  Collect the indices.  This is typically for arrays of
-  // structs.
-  SmallVector<unsigned, 4> LaterIndices;
-
-  Type *EltTy = Init->getType()->getArrayElementType();
-  for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) {
-    ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
-    if (!Idx) return nullptr;  // Variable index.
-
-    uint64_t IdxVal = Idx->getZExtValue();
-    if ((unsigned)IdxVal != IdxVal) return nullptr; // Too large array index.
-
-    if (StructType *STy = dyn_cast<StructType>(EltTy))
-      EltTy = STy->getElementType(IdxVal);
-    else if (ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
-      if (IdxVal >= ATy->getNumElements()) return nullptr;
-      EltTy = ATy->getElementType();
-    } else {
-      return nullptr; // Unknown type.
-    }
+  Type *LoadedTy = LI->getType();
+  uint64_t LoadedTySize = DL.getTypeAllocSize(LoadedTy);
+  uint64_t PtrBitwidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace());
+  Type *PtrIdxTy = DL.getIndexType(GEP->getType());
 
-    LaterIndices.push_back(IdxVal);
-  }
+  MapVector<Value *, APInt> VariableOffsets;
+  APInt ConstantOffset(PtrBitwidth, 0);
+  GEP->collectOffset(GEP->getModule()->getDataLayout(), PtrBitwidth,
+                     VariableOffsets, ConstantOffset);
+
+  // Restrict to one variable currently.
+  if (VariableOffsets.size() != 1)
+    return nullptr;
 
+  // There are many forms of this optimization we can handle.
+  // Limit to one variable currently.
+  // Possible TODO: Fold: cmp(A[ax + by + ... + C], Rhs) <=> cmp(ax + by + ....
+  // + C, IndexRhs)
   enum { Overdefined = -3, Undefined = -2 };
 
   // Variables for our state machines.
 
   // FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form
   // "i == 47 | i == 87", where 47 is the first index the condition is true for,
   // and 87 is the second (and last) index.  FirstTrueElement is -2 when
   // undefined, otherwise set to the first true element.  SecondTrueElement is
Instruction *InstCombinerImpl::foldCmpLoadFromIndexedGlobal(
   /// use relative comparisons and don't want 0-1 to match -1.
   int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
 
   // MagicBitvector - This is a magic bitvector where we set a bit if the
   // comparison is true for element 'i'.  If there are 64 elements or less in
   // the array, this will fully represent all the comparison results.
   uint64_t MagicBitvector = 0;
 
+  Value *Idx = nullptr;
+
   // Scan the array and see if one of our patterns matches.
-  Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
-  for (unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
-    Constant *Elt = Init->getAggregateElement(i);
-    if (!Elt) return nullptr;
-
-    // If this is indexing an array of structures, get the structure element.
-    if (!LaterIndices.empty()) {
-      Elt = ConstantFoldExtractValueInstruction(Elt, LaterIndices);
-      if (!Elt)
-        return nullptr;
-    }
+  Constant *ComparedRHS = cast<Constant>(ICI.getOperand(1));
+  APInt OffsetStep = VariableOffsets.front().second;
+  // The longest step we can reach once.
+  uint64_t OffsetStepZExt = OffsetStep.getZExtValue();
+  // Offset from constant pointer where we begin scanning the constant.
+  int64_t BeginOffset = ConstantOffset.getSExtValue();
+
+  // Make BeginOffset the smallest offset >= 0
+  if (BeginOffset % OffsetStepZExt == 0)
+    BeginOffset = 0;
+  else if (BeginOffset < 0)
+    BeginOffset += (-BeginOffset / OffsetStepZExt + 1) * OffsetStepZExt;
+  else if (BeginOffset > 0)
+    BeginOffset -= (BeginOffset / OffsetStepZExt) * OffsetStepZExt;
+
+  uint64_t ElementCountToTraverse = (DataSize - BeginOffset) / OffsetStepZExt;
+
+  // Don't traverse too many times.
+  if (ElementCountToTraverse > MaxArraySizeForCombine)
+    return nullptr;
+
+  for (uint64_t i = 0; i < ElementCountToTraverse; ++i) {
+    APInt CurOffset(i * OffsetStep + BeginOffset);
+    Constant *Elt = ConstantFoldLoadFromConstPtr(GV, LoadedTy, CurOffset, DL);
+
 
     // If the element is masked, handle it.
     if (AndCst) {
       Elt = ConstantFoldBinaryOpOperands(Instruction::And, Elt, AndCst, DL);
       if (!Elt)
         return nullptr;
     }
 
     // Find out if the comparison would be true or false for the i'th element.
     Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt,
-                                                  CompareRHS, DL, &TLI);
+                                                  ComparedRHS, DL, &TLI);
     // If the result is undef for this element, ignore it.
     if (isa<UndefValue>(C)) {
       // Extend range state machines to cover this element in case there is an
       // undef in the middle of the range.
-      if (TrueRangeEnd == (int)i-1)
+      if (TrueRangeEnd == (int)i - 1)
         TrueRangeEnd = i;
-      if (FalseRangeEnd == (int)i-1)
+      if (FalseRangeEnd == (int)i - 1)
         FalseRangeEnd = i;
       continue;
     }
 
     // If we can't compute the result for any of the elements, we have to give
     // up evaluating the entire conditional.
-    if (!isa<ConstantInt>(C)) return nullptr;
+    if (!isa<ConstantInt>(C))
+      return nullptr;
 
     // Otherwise, we know if the comparison is true or false for this element,
     // update our state machines.
     bool IsTrueForElt = !cast<ConstantInt>(C)->isZero();
 
     // State machine for single/double/range index comparison.
     if (IsTrueForElt) {
       // Update the TrueElement state machine.
       if (FirstTrueElement == Undefined)
-        FirstTrueElement = TrueRangeEnd = i;  // First true element.
+        FirstTrueElement = TrueRangeEnd = i; // First true element.
       else {
         // Update double-compare state machine.
         if (SecondTrueElement == Undefined)
           SecondTrueElement = i;
         else
           SecondTrueElement = Overdefined;
 
         // Update range state machine.
-        if (TrueRangeEnd == (int)i-1)
+        if (TrueRangeEnd == (int)i - 1)
           TrueRangeEnd = i;
         else
           TrueRangeEnd = Overdefined;
       }
     } else {
       // Update the FalseElement state machine.
       if (FirstFalseElement == Undefined)
         FirstFalseElement = FalseRangeEnd = i; // First false element.
       else {
         // Update double-compare state machine.
         if (SecondFalseElement == Undefined)
           SecondFalseElement = i;
         else
           SecondFalseElement = Overdefined;
 
         // Update range state machine.
-        if (FalseRangeEnd == (int)i-1)
+        if (FalseRangeEnd == (int)i - 1)
           FalseRangeEnd = i;
         else
           FalseRangeEnd = Overdefined;
       }
     }
 
     // If this element is in range, update our magic bitvector.
     if (i < 64 && IsTrueForElt)
       MagicBitvector |= 1ULL << i;
-
     // If all of our states become overdefined, bail out early.  Since the
     // predicate is expensive, only check it every 8 elements.  This is only
     // really useful for really huge arrays.
     if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
         SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
         FalseRangeEnd == Overdefined)
       return nullptr;
   }
 
   // Now that we've scanned the entire array, emit our new comparison(s).  We
   // order the state machines in complexity of the generated code.
-  Value *Idx = GEP->getOperand(2);
-
-  // If the index is larger than the pointer offset size of the target, truncate
-  // the index down like the GEP would do implicitly.  We don't have to do this
-  // for an inbounds GEP because the index can't be out of range.
-  if (!GEP->isInBounds()) {
-    Type *PtrIdxTy = DL.getIndexType(GEP->getType());
-    unsigned OffsetSize = PtrIdxTy->getIntegerBitWidth();
-    if (Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > OffsetSize)
-      Idx = Builder.CreateTrunc(Idx, PtrIdxTy);
-  }
 
-  // If inbounds keyword is not present, Idx * ElementSize can overflow.
-  // Let's assume that ElementSize is 2 and the wanted value is at offset 0.
+  // If inbounds keyword is not present, Idx * LongestStep can overflow.
+  // Let's assume that LongestStep is 2 and the wanted value is at offset 0.
   // Then, there are two possible values for Idx to match offset 0:
   // 0x00..00, 0x80..00.
   // Emitting 'icmp eq Idx, 0' isn't correct in this case because the
   // comparison is false if Idx was 0x80..00.
   // We need to erase the highest countTrailingZeros(ElementSize) bits of Idx.
-  unsigned ElementSize =
-      DL.getTypeAllocSize(Init->getType()->getArrayElementType());
   auto MaskIdx = [&](Value *Idx) {
-    if (!GEP->isInBounds() && llvm::countr_zero(ElementSize) != 0) {
+    if (!GEP->isInBounds() && llvm::countr_zero(OffsetStepZExt) != 0) {
       Value *Mask = ConstantInt::get(Idx->getType(), -1);
-      Mask = Builder.CreateLShr(Mask, llvm::countr_zero(ElementSize));
+      Mask = Builder.CreateLShr(Mask, llvm::countr_zero(OffsetStepZExt));
       Idx = Builder.CreateAnd(Idx, Mask);
     }
     return Idx;
   };
 
+  // Build the index expression lazily.
+  auto LazyGetIndex = [&](Value *CurIdx) {
+    if (CurIdx)
+      return CurIdx;
+
+    // Initial bias for index. For example, when we fold C[x + 3] into
+    // x < 2, we actually regard it as x < 5 - 3
+    Value *Idx =
+        ConstantInt::get(PtrIdxTy->getContext(),
+                         (BeginOffset - ConstantOffset).sdiv(OffsetStepZExt));
+    for (auto [Var, Coefficient] : VariableOffsets) {
+      uint64_t VarBitWidth = Var->getType()->getScalarSizeInBits();
+      uint64_t IdxBitWidth = Idx->getType()->getScalarSizeInBits();
+      Type *WiderType =
+          VarBitWidth > IdxBitWidth ? Var->getType() : Idx->getType();
+
+      Var = Builder.CreateSExtOrTrunc(Var, WiderType);
+      Idx = Builder.CreateSExtOrTrunc(Idx, WiderType);
+      APInt MinCoeffi = Coefficient.sdiv(OffsetStep)
+                            .sextOrTrunc(WiderType->getScalarSizeInBits());
+      Value *Mul =
+          Builder.CreateMul(Var, ConstantInt::get(WiderType, MinCoeffi));
+      Idx = Builder.CreateAdd(Idx, Mul);
+    }
+
+    // If the index is larger than the pointer offset size of the target,
+    // truncate the index down like the GEP would do implicitly.  We don't have
+    // to do this for an inbounds GEP because the index can't be out of range.
+    if (!GEP->isInBounds() &&
+        Idx->getType()->getScalarSizeInBits() > PtrBitwidth)
+      Idx = Builder.CreateTrunc(Idx, PtrIdxTy);
+
+    return MaskIdx(Idx);
+  };
+
   // If the comparison is only true for one or two elements, emit direct
   // comparisons.
   if (SecondTrueElement != Overdefined) {
-    Idx = MaskIdx(Idx);
+    Idx = LazyGetIndex(Idx);
     // None true -> false.
     if (FirstTrueElement == Undefined)
       return replaceInstUsesWith(ICI, Builder.getFalse());
 
     Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement);
 
     // True for one element -> 'i == 47'.
     if (SecondTrueElement == Undefined)
       return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx);
 
     // True for two elements -> 'i == 47 | i == 72'.
     Value *C1 = Builder.CreateICmpEQ(Idx, FirstTrueIdx);
     Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement);
     Value *C2 = Builder.CreateICmpEQ(Idx, SecondTrueIdx);
     return BinaryOperator::CreateOr(C1, C2);
   }
 
   // If the comparison is only false for one or two elements, emit direct
   // comparisons.
   if (SecondFalseElement != Overdefined) {
-    Idx = MaskIdx(Idx);
+    Idx = LazyGetIndex(Idx);
     // None false -> true.
     if (FirstFalseElement == Undefined)
       return replaceInstUsesWith(ICI, Builder.getTrue());
 
     Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement);
 
     // False for one element -> 'i != 47'.
     if (SecondFalseElement == Undefined)
       return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx);
 
     // False for two elements -> 'i != 47 & i != 72'.
     Value *C1 = Builder.CreateICmpNE(Idx, FirstFalseIdx);
-    Value *SecondFalseIdx = ConstantInt::get(Idx->getType(),SecondFalseElement);
+    Value *SecondFalseIdx =
+        ConstantInt::get(Idx->getType(), SecondFalseElement);
     Value *C2 = Builder.CreateICmpNE(Idx, SecondFalseIdx);
     return BinaryOperator::CreateAnd(C1, C2);
   }
 
   // If the comparison can be replaced with a range comparison for the elements
   // where it is true, emit the range check.
   if (TrueRangeEnd != Overdefined) {
     assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare");
-    Idx = MaskIdx(Idx);
+    Idx = LazyGetIndex(Idx);
 
     // Generate (i-FirstTrue) <u (TrueRangeEnd-FirstTrue+1).
     if (FirstTrueElement) {
       Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement);
       Idx = Builder.CreateAdd(Idx, Offs);
     }
 
-    Value *End = ConstantInt::get(Idx->getType(),
-                                  TrueRangeEnd-FirstTrueElement+1);
+    Value *End =
+        ConstantInt::get(PtrIdxTy, TrueRangeEnd - FirstTrueElement + 1);
     return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End);
   }
 
   // False range check.
   if (FalseRangeEnd != Overdefined) {
     assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare");
-    Idx = MaskIdx(Idx);
+    Idx = LazyGetIndex(Idx);
     // Generate (i-FirstFalse) >u (FalseRangeEnd-FirstFalse).
     if (FirstFalseElement) {
       Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement);
       Idx = Builder.CreateAdd(Idx, Offs);
     }
 
-    Value *End = ConstantInt::get(Idx->getType(),
-                                  FalseRangeEnd-FirstFalseElement);
+    Value *End =
+        ConstantInt::get(Idx->getType(), FalseRangeEnd - FirstFalseElement);
     return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End);
   }
 
   // If a magic bitvector captures the entire comparison state
   // of this load, replace it with computation that does:
   //   ((magic_cst >> i) & 1) != 0
   {
     Type *Ty = nullptr;
 
     // Look for an appropriate type:
     // - The type of Idx if the magic fits
     // - The smallest fitting legal type
-    if (ArrayElementCount <= Idx->getType()->getIntegerBitWidth())
-      Ty = Idx->getType();
+
+    if (ElementCountToTraverse <= PtrIdxTy->getIntegerBitWidth())
+      Ty = PtrIdxTy;
     else
-      Ty = DL.getSmallestLegalIntType(Init->getContext(), ArrayElementCount);
+      Ty = DL.getSmallestLegalIntType(Init->getContext(),
+                                      ElementCountToTraverse);
 
     if (Ty) {
-      Idx = MaskIdx(Idx);
+      Idx = LazyGetIndex(Idx);
       Value *V = Builder.CreateIntCast(Idx, Ty, false);
       V = Builder.CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
       V = Builder.CreateAnd(ConstantInt::get(Ty, 1), V);
       return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
     }
   }
 
   return nullptr;

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

while (true) {
 
     ++NumWorklistIterations;
     LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
                       << F.getName() << "\n");
 
     InstCombinerImpl IC(Worklist, Builder, F.hasMinSize(), AA, AC, TLI, TTI, DT,
                         ORE, BFI, PSI, DL, LI);
     IC.MaxArraySizeForCombine = MaxArraySize;
+    IC.MaxDataSizeForCombine = MaxArraySize * 8;
+
     bool MadeChangeInThisIteration = IC.prepareWorklist(F, RPOT);
     MadeChangeInThisIteration |= IC.run();
     if (!MadeChangeInThisIteration)
       break;
 
     MadeIRChange = true;
     if (Iteration > MaxIterations) {
       report_fatal_error(

llvm/test/Transforms/InstCombine/load-cmp.ll

;
   %p = getelementptr inbounds %Foo, ptr @GS, i32 %x, i32 0
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_noinbounds(i32 %x) {
 ; CHECK-LABEL: @test10_struct_noinbounds(
-; CHECK-NEXT:    [[P:%.*]] = getelementptr [[FOO:%.*]], ptr @GS, i32 [[X:%.*]], i32 0
-; CHECK-NEXT:    [[Q:%.*]] = load i32, ptr [[P]], align 8
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[Q]], 9
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %p = getelementptr %Foo, ptr @GS, i32 %x, i32 0
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 ; Test that the GEP indices are converted before we ever get here
;
   %p = getelementptr inbounds %Foo, ptr @GS, i64 %x, i32 0
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 0
   ret i1 %r
 }
 
 define i1 @test10_struct_noinbounds_i16(i16 %x) {
 ; CHECK-LABEL: @test10_struct_noinbounds_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i16 [[X:%.*]] to i32
-; CHECK-NEXT:    [[P:%.*]] = getelementptr [[FOO:%.*]], ptr @GS, i32 [[TMP1]], i32 0
-; CHECK-NEXT:    [[Q:%.*]] = load i32, ptr [[P]], align 8
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[Q]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %p = getelementptr %Foo, ptr @GS, i16 %x, i32 0
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 0
   ret i1 %r
 }
 
 define i1 @test10_struct_arr(i32 %x) {
 ; CHECK-LABEL: @test10_struct_arr(
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], -3
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %p = getelementptr inbounds [4 x %Foo], ptr @GStructArr, i32 0, i32 %x, i32 2
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_arr_noinbounds(i32 %x) {
 ; CHECK-LABEL: @test10_struct_arr_noinbounds(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 268435455
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 268435453
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %p = getelementptr [4 x %Foo], ptr @GStructArr, i32 0, i32 %x, i32 2
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_arr_i16(i16 %x) {
 ; CHECK-LABEL: @test10_struct_arr_i16(
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i16 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X:%.*]], -3
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %p = getelementptr inbounds [4 x %Foo], ptr @GStructArr, i16 0, i16 %x, i32 2
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_arr_i64(i64 %x) {
 ; CHECK-LABEL: @test10_struct_arr_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 4294967295
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i64 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 4294967293
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %p = getelementptr inbounds [4 x %Foo], ptr @GStructArr, i64 0, i64 %x, i32 2
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_arr_noinbounds_i16(i16 %x) {
 ; CHECK-LABEL: @test10_struct_arr_noinbounds_i16(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i16 [[X:%.*]] to i32
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 268435455
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 268435453
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP2]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %p = getelementptr [4 x %Foo], ptr @GStructArr, i32 0, i16 %x, i32 2
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 define i1 @test10_struct_arr_noinbounds_i64(i64 %x) {
 ; CHECK-LABEL: @test10_struct_arr_noinbounds_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 268435455
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i64 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 268435453
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %p = getelementptr [4 x %Foo], ptr @GStructArr, i32 0, i64 %x, i32 2
   %q = load i32, ptr %p
   %r = icmp eq i32 %q, 9
   ret i1 %r
 }
 
 
 @CG = constant [4 x i32] [i32 1, i32 2, i32 3, i32 4]
 
+; TODO: Fold it globally.
 define i1 @cmp_load_constant_array0(i64 %x){
 ; CHECK-LABEL: @cmp_load_constant_array0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i64 [[X:%.*]], 2
 ; CHECK-NEXT:    br i1 [[COND]], label [[CASE1:%.*]], label [[CASE2:%.*]]
 ; CHECK:       case2:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       case1:
-; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[X]] to i32
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr inbounds i32, ptr @CG, i32 [[TMP0]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i32, ptr [[ISOK_PTR]], align 4
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ult i32 [[ISOK]], 3
+; CHECK-NEXT:    [[TMP0:%.*]] = and i64 [[X]], 4294967294
+; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp eq i64 [[TMP0]], 0
 ; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
 ;
 entry:
   %cond = icmp ult i64 %x, 2
   br i1 %cond, label %case1, label %case2
 
 case2:
   ret i1 0
 
 case1:
   %isOK_ptr = getelementptr inbounds i32, ptr @CG, i64 %x
   %isOK = load i32, ptr %isOK_ptr
   %cond_inferred = icmp ult i32 %isOK, 3
   ret i1 %cond_inferred
 }
 
 define i1 @cmp_load_constant_array1(i64 %x){
 ; CHECK-LABEL: @cmp_load_constant_array1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i64 [[X:%.*]], 2
 ; CHECK-NEXT:    br i1 [[COND]], label [[CASE1:%.*]], label [[CASE2:%.*]]
 ; CHECK:       case2:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       case1:
-; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[X]] to i32
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr inbounds i32, ptr @CG, i32 [[TMP0]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i32, ptr [[ISOK_PTR]], align 4
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ugt i32 [[ISOK]], 10
-; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cond = icmp ult i64 %x, 2
   br i1 %cond, label %case1, label %case2
 
 case2:
   ret i1 0
 

 ; CHECK-LABEL: @cmp_load_constant_array_messy(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i64 [[X:%.*]], 6
 ; CHECK-NEXT:    br i1 [[COND]], label [[CASE1:%.*]], label [[CASE2:%.*]]
 ; CHECK:       case2:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       case1:
 ; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[X]] to i32
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr i32, ptr @CG_MESSY, i32 [[TMP0]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i32, ptr [[ISOK_PTR]], align 4
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp slt i32 [[ISOK]], 5
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[TMP0]], 1073741823
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 373, [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], 1
+; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ne i32 [[TMP3]], 0
 ; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
 ;
 entry:
   %cond = icmp slt i64 %x, 6
   br i1 %cond, label %case1, label %case2
 
 case2:
   ret i1 0
 
 case1:
   %isOK_ptr = getelementptr i32, ptr @CG_MESSY, i64 %x
   %isOK = load i32, ptr %isOK_ptr
   %cond_inferred = icmp slt i32 %isOK, 5
   ret i1 %cond_inferred
 }
 
 define i1 @cmp_diff_load_constant_array_messy0(i64 %x){
 ; CHECK-LABEL: @cmp_diff_load_constant_array_messy0(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[X:%.*]] to i32
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr i32, ptr @CG_MESSY, i32 [[TMP1]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i16, ptr [[ISOK_PTR]], align 4
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp slt i16 [[ISOK]], 5
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 1073741823
+; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 373, [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 1
+; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ne i32 [[TMP4]], 0
 ; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
 ;
   %isOK_ptr = getelementptr i32, ptr @CG_MESSY, i64 %x
   %isOK = load i16, ptr %isOK_ptr
   %cond_inferred = icmp slt i16 %isOK, 5
   ret i1 %cond_inferred
 }
 
 define i1 @cmp_diff_load_constant_array_messy1(i64 %x){
 ; CHECK-LABEL: @cmp_diff_load_constant_array_messy1(
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[X:%.*]] to i32
-; CHECK-NEXT:    [[ISOK_PTR:%.*]] = getelementptr i6, ptr @CG_MESSY, i32 [[TMP1]]
-; CHECK-NEXT:    [[ISOK:%.*]] = load i16, ptr [[ISOK_PTR]], align 2
-; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp slt i16 [[ISOK]], 5
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 4294967295
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr i64 66160388071, [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i64 [[TMP2]], 1
+; CHECK-NEXT:    [[COND_INFERRED:%.*]] = icmp ne i64 [[TMP3]], 0
 ; CHECK-NEXT:    ret i1 [[COND_INFERRED]]
 ;
   %isOK_ptr = getelementptr i6, ptr @CG_MESSY, i64 %x
   %isOK = load i16, ptr %isOK_ptr
   %cond_inferred = icmp slt i16 %isOK, 5
   ret i1 %cond_inferred
 }
 
 define i1 @cmp_load_constant_array_fail0(i64 %x, i32 %y) {
 ; CHECK-LABEL: @cmp_load_constant_array_fail0(
 ; CHECK-NEXT:  entry:
case2:
   ret i1 0
 
 case1:
   %isOK_ptr = getelementptr inbounds i32, ptr @CG, i64 %x
   %isOK = load i32, ptr %isOK_ptr
   %cond_inferred = icmp ult i32 %isOK, %y
   ret i1 %cond_inferred
 }
-

llvm/test/Transforms/InstCombine/opaque-ptr.ll

;
   %gep = getelementptr [4 x i8], ptr @ary, i64 0, i64 %idx
   %load = load i8, ptr %gep
   %cmp = icmp eq i8 %load, 3
   ret i1 %cmp
 }
 
 define i1 @cmp_load_gep_global_different_load_type(i64 %idx) {
 ; CHECK-LABEL: @cmp_load_gep_global_different_load_type(
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [4 x i8], ptr @ary, i64 0, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[LOAD:%.*]] = load i16, ptr [[GEP]], align 2
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[LOAD]], 3
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %gep = getelementptr [4 x i8], ptr @ary, i64 0, i64 %idx
   %load = load i16, ptr %gep
   %cmp = icmp eq i16 %load, 3
   ret i1 %cmp
 }
 
 define i1 @cmp_load_gep_global_different_gep_type(i64 %idx) {
 ; CHECK-LABEL: @cmp_load_gep_global_different_gep_type(
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [4 x i16], ptr @ary, i64 0, i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[LOAD:%.*]] = load i16, ptr [[GEP]], align 2
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[LOAD]], 3
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %gep = getelementptr [4 x i16], ptr @ary, i64 0, i64 %idx
   %load = load i16, ptr %gep
   %cmp = icmp eq i16 %load, 3
   ret i1 %cmp
 }
 
 define ptr @phi_of_gep(i1 %c, ptr %p) {