Derive GEP index type from Data Layout

[delena]

Summary

In the current version InstCombiner “normalizes” GEPs and extends Index operand to the pointer width.

It works fine if you can convert pointer to integer for address calculation and all registered targets do this.
The target I’m working on has very restricted ISA for the pointer calculation. Hal suggested to retrieve information for GEP index width from Data Layout.
http://lists.llvm.org/pipermail/llvm-dev/2018-January/120416.html

I added the interface to Data Layout and I changed the InstCombiner.
I know that I didn't touch all GEP creation points, but all changes that you see in the review are covered by our internal test system.

[craig.topper]

lib/Transforms/InstCombine/InstructionCombining.cpp

1883–1887

Should this assert message be updated since it not guaranteed to be pointer width now?

1923–1927

Same with this assert.

[delena]

Fixed 2 "assert" messages.

[delena]

Added tests for a data layout, where pointer is wider than the largest supported integer type.

[craig.topper]

lib/Analysis/ConstantFolding.cpp

812

Can you put curly braces after this if and the for loop below it to help with readability? I know the for loop didn't have them before, but I feel like it should have. I tend to think that if the inner scope is curly braced, the outer scope should be too.

[theraven]

I don't like this patch as is, for several reasons.

1. It's adding a hack that assumes that the offset should be the width of the widest integer operation. This is probably true in most cases (it is for us), but if we're going to introduce the idea that an address offset is distinct from the size of the pointer then we should do it properly and add that to the TargetInfo string explicitly (defaulting to the same size, if not specified).
2. We're computing the correct width every time it's requested, which looks expensive. TargetInfo should store the width for each address space and, for non-vector types, not have to do any calculation to determine the kind of integer to return.
3. It fixes only around 20% of the places that we've found that assume that the size and range of the pointer are the same.

[delena]

Updated, following Craig's comments.

[delena]

In D42123#981602, @theraven wrote:

I don't like this patch as is, for several reasons.

1. It's adding a hack that assumes that the offset should be the width of the widest integer operation. This is probably true in most cases (it is for us), but if we're going to introduce the idea that an address offset is distinct from the size of the pointer then we should do it properly and add that to the TargetInfo string explicitly (defaulting to the same size, if not specified).

So you propose to extend Data Layout string and add index size to it, right? It was one of options that Hal suggested. Ok.

2. We're computing the correct width every time it's requested, which looks expensive. TargetInfo should store the width for each address space and, for non-vector types, not have to do any calculation to determine the kind of integer to return.

We calculated getIntPtrType() anyway, getIndexType() is not more expensive. If I extend TargetInfo, the extension will be optional and all other targets will calculate getIntPtrType() anyway.

3. It fixes only around 20% of the places that we've found that assume that the size and range of the pointer are the same.

I can't derive all places from your code. You can show me them all, one-by-one, or we'll fix more places gradually on top of this patch.

[theraven]

In D42123#982063, @delena wrote:

In D42123#981602, @theraven wrote:

I don't like this patch as is, for several reasons.

1. It's adding a hack that assumes that the offset should be the width of the widest integer operation. This is probably true in most cases (it is for us), but if we're going to introduce the idea that an address offset is distinct from the size of the pointer then we should do it properly and add that to the TargetInfo string explicitly (defaulting to the same size, if not specified).

So you propose to extend Data Layout string and add index size to it, right? It was one of options that Hal suggested. Ok.

Yes, if we're going to fix this upstream, let's fix it properly.

2. We're computing the correct width every time it's requested, which looks expensive. TargetInfo should store the width for each address space and, for non-vector types, not have to do any calculation to determine the kind of integer to return.

We calculated getIntPtrType() anyway, getIndexType() is not more expensive. If I extend TargetInfo, the extension will be optional and all other targets will calculate getIntPtrType() anyway.

If you read it from the DataLayout string, you'll either construct it at that parsing time from the specified version or from the default version.

3. It fixes only around 20% of the places that we've found that assume that the size and range of the pointer are the same.

I can't derive all places from your code. You can show me them all, one-by-one, or we'll fix more places gradually on top of this patch.

Greping the code for all uses of getPointerBaseSize should show them all, but I can send you a list.

[delena]

I want to deprecate SCEVs for pointers if the index size is not equal to pointer size.
What do you think?

bool ScalarEvolution::isSCEVable(Type *Ty) const {
  if (Ty->isIntegerTy())
    return true;
  if (Ty->isPointerTy()) {
    // Pointer can't be scevable if index type and pointer type have different
    // width.
    const DataLayout& DL = getDataLayout();
    if (DL.getIndexTypeSizeInBits(Ty) == DL.getPointerTypeSizeInBits(Ty))
      return true;
  }
  return false;

}

[theraven]

In D42123#987589, @delena wrote:

I want to deprecate SCEVs for pointers if the index size is not equal to pointer size.
What do you think?

This will mean that you don't get a load of loop optimisations. I think that's a pretty big hammer. There's no reason why SCEV can't work here - we use it and have a bunch of patches against it to make it work in this context. Please take a look at our code and see how much of it is applicable to you.

[delena]

I looked at your code:
/ Return the size in bits of the specified type, for which isSCEVable must
/ return true.
uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const {

assert(isSCEVable(Ty) && "Type is not SCEVable!");
const DataLayout &DL = getDataLayout();
if (PointerType *PT = dyn_cast<PointerType>(Ty))
  return DL.getPointerBaseSizeInBits(PT->getPointerAddressSpace());
return DL.getTypeSizeInBits(Ty);

}
I can't say that size of pointer is smaller that it is. I can't truncate pointer to integer in order to expand all SCEV expressions.

[delena]

Added index width specification to the DataLayout. Updated the langref.
Fixed Pointer vs Index sizes in the code.
Added more tests.

[sanjoy]

../lib/Analysis/ScalarEvolution.cpp

3667 ↗

(On Diff #131955)

Generally speaking; the SCEV changes need to be tested.

3675 ↗

(On Diff #131955)

I don't think this is a correct place to make this change -- the size of a pointer is the size of a pointer. I think you need to change the SCEV corresponding to GEP(Ptr, Idx) to be "sext(Ptr) + Idx" or "Ptr + sext(Idx)" depending on their relative sizes.

[delena]

../lib/Analysis/ScalarEvolution.cpp

3667 ↗

(On Diff #131955)

I added several tests that go through the SCEV. Looks ok right now. I can't say that I cover all corner cases, but we can do further changes gradually, there is no impact on in-tree targets. If you see something specific that requires more testing now, please let me know.

3675 ↗

(On Diff #131955)

I can't create SCEV expressions with ptr+ind, it will fail with assertion on different types.

[Ayal]

../lib/Analysis/ScalarEvolution.cpp

3675 ↗

(On Diff #131955)

Elena, Sanjoy's thought above to change SCEV to be "sext(Ptr) + Idx" or "Ptr + sext(Idx)" will bring the two addends to be of the same type, i.e., of the larger type. The challenge in your case is lack of target support for integer addition of pointer-sized integers; which seems similar to CHERI's case. Except CHERI pointers (or capabilities) hold in addition to a standard-sized address additional information, such that the latter can be stripped out for SCEV purposes (IIUC - @theraven please correct if needed); whereas in your case the address itself is larger than a standard-sized integer. Perhaps for your case too the pointer can be stripped down to standard-sized integers to leverage SCEV's capabilities on "legal" types, which seems to be what your patch is doing, coupled with separate logic that deals with the stripped out bits(?).

[theraven]

../lib/Analysis/ScalarEvolution.cpp

3675 ↗

(On Diff #131955)

That's pretty much the case for us: our pointers are 128 bits, but have a 64-bit range (64 bits of metadata). We have modified DataLayout to explicitly understand that pointer size and range are different (in a slightly hacky way, which we should improve before we think about upstreaming). In scalar evolution, we always use the pointer's range as the type.

We don't support arbitrary integer operations on pointers and in our back end we have added some new MVTs to represent non-integer pointer types. Our architecture provides pointer + integer addressing modes.

I believe that, in the motivating example for this change, the existing ScalarEvolution code is correct: it should use pointer-sized integers, because otherwise the analyses are likely to be wrong in some exciting corner cases.

We have addressed this by adding explicit PTRADD SelectionDAG nodes, which perform pointer + integer addition. For complex addressing modes, we end up with (ptradd base (some complex integer ops)). This works well as long as the underlying hardware supports address register + integer register addressing, which I presume is the case for Intel (it is for all Harvard architectures that I've come across).

If you are targeting an architecture for which pointer operations and integer operations are not the same, then you should follow the same approach: in the back end, lower pointers to some non-integer type and match pointer operations with different patterns to integer ones. We have a bunch of SelectionDAG and TableGen patches that make this work well, which we'd be happy to upstream.

[delena]

" > We have addressed this by adding explicit PTRADD SelectionDAG nodes, which perform pointer + integer addition. For complex addressing modes, we end up with (ptradd base (some complex integer ops)). This works well as long as the underlying hardware supports address register + integer register addressing, which I presume is the case for Intel (it is for all Harvard architectures that I've come across)."

Yes, we also added ADDPTR node for SelectionDAG and we have more changes related to the special pointer type. Apparently, the codegen does not work with MVT::Ptr.
We can try to upstream the part of DAG builder, that makes ADDPTR from GEP.

[delena]

@theraven , the latest uploaded version is aligned with what you implemented out of the tree. Could you, please, take a look?

[theraven]

Two very small nits (which I'd be happy to see fixed after commit, but might be easier to fix first), but otherwise it looks like a significantly cleaned-up version of what we have.

Thank you very much for working on this! Our next merge will be a little bit painful, but subsequent ones should be a lot easier.

Are you planning on upstreaming your ADDPTR SelectionDAG stuff? We have added PTRADD, INTTOPTR and PTRTOINT nodes and if they're useful to someone apart from us then we can upstream them.

../include/llvm/IR/DataLayout.h

357 ↗

(On Diff #131955)

Please can we not have a default for AS? We've added defaults for other things like this because they were existing APIs and we didn't want to have to update all of the callers at once, but all of the callers of this are already being updated and so should specify the correct AS.

../lib/Analysis/ScalarEvolution.cpp

3675 ↗

(On Diff #131955)

I agree with @sanjoy that this isn't the correct place for this change, but it does happen to be the least disruptive place for the change. The correct solution is probably to rename this method to something like getTypeArithmeticSizeInBits so that it's clear that it's returning a size as a proxy for a range and not a storage size.

[sanjoy]

../lib/Analysis/ScalarEvolution.cpp

3667 ↗

(On Diff #131955)

I don't see these tests in this current version of the patch.

3675 ↗

(On Diff #131955)

Given what you said, the right fix seems to be to truncate 128 bit pointers to 64 bits in getSCEV instead of lying about the pointer's size. SCEV calls into other parts of LLVM like ValueTracking, and other parts of LLVM call into SCEV (invdvars, lsr, scev-aa etc.) and I'm worried that a discrepancy like this (pointer size = 64 in SCEV but 128 elsewhere) will cause bugs.

[delena]

I don't see these tests in this current version of the patch.

All tests that you see *-custom.ll" go through the scev calculations.

[theraven]

../lib/Analysis/ScalarEvolution.cpp

3675 ↗

(On Diff #131955)

Truncating for us would be absolutely the wrong thing, because it changes the semantics (throws away all of the bounds metadata, falls back to some per-environment bounds which may not even allow access to this address). In our case, we have a difference between the size and the range.

All of the places we've seen this used in ScalarEvolution, it cares about the range, not the storage size, it just happens that on most architectures these are the same (because a 32-bit pointer has a range of 2^32 bytes, a 64-bit pointer has a range of 2^64 bytes).

The correct solution is to either rename this method something like getTypeArithmeticSizeInBits and update all of the callers, or add a new getTypeArithmeticSizeInBits method and update all of the callers (I don't believe that there are any that care about the storage size, but I might have missed one).

We've been running with a change that's semantically identical to @delena's for a few years and have not encountered any miscompilations as a result (building a whole of the FreeBSD base system, a bunch of benchmarks, and a few other large programs), so I'm fairly confident that it's safe.

[arichardson]

Thank you very much for working on this. It will make our future upstream merges much easier.

../docs/LangRef.rst

1913 ↗

(On Diff #131955)

fourth parameter

../include/llvm/IR/DataLayout.h

357 ↗

(On Diff #131955)

Yes, please remove the default value here. We have run into lots of issues due to using the size of AS0 instead of the correct one.

../lib/Transforms/InstCombine/InstructionCombining.cpp

1511 ↗

(On Diff #131955)

Index width may not be the same width as pointer width

[delena]

Updated according to the latest comments.

[delena]

Added more tests with custom data layout.

include/llvm/IR/DataLayout.h

Type *getLargestLegalIntType(LLVMContext &C) const {
     unsigned LargestSize = getLargestLegalIntTypeSizeInBits();
     return (LargestSize == 0) ? nullptr : Type::getIntNTy(C, LargestSize);
   }
 
   /// \brief Returns the size of largest legal integer type size, or 0 if none
   /// are set.
   unsigned getLargestLegalIntTypeSizeInBits() const;
 
+  /// \brief Returns the type of a GEP index.
+  /// It is a smaller type between IntPtrType and the largest supported
+  /// integer type. We can't take the IntPtrType for index, since the target may
+  /// not support full arithmetic for it.
+  Type *getIndexType(Type *PtrTy) const;
+
   /// \brief Returns the offset from the beginning of the type for the specified
   /// indices.
   ///
   /// Note that this takes the element type, not the pointer type.
   /// This is used to implement getelementptr.
   int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef<Value *> Indices) const;
 
   /// \brief Returns a StructLayout object, indicating the alignment of the

lib/Analysis/ConstantFolding.cpp

Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, Constant *Op1,
   return nullptr;
 }
 
 /// If array indices are not pointer-sized integers, explicitly cast them so
 /// that they aren't implicitly casted by the getelementptr.
 Constant *CastGEPIndices(Type *SrcElemTy, ArrayRef<Constant *> Ops,
                          Type *ResultTy, Optional<unsigned> InRangeIndex,
                          const DataLayout &DL, const TargetLibraryInfo *TLI) {
-  Type *IntPtrTy = DL.getIntPtrType(ResultTy);
-  Type *IntPtrScalarTy = IntPtrTy->getScalarType();
+  Type *IndexTy = DL.getIndexType(ResultTy);
+  Type *IndexScalarTy = IndexTy->getScalarType();
 
   bool Any = false;
   SmallVector<Constant*, 32> NewIdxs;
   for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
     if ((i == 1 ||
          !isa<StructType>(GetElementPtrInst::getIndexedType(
              SrcElemTy, Ops.slice(1, i - 1)))) &&
-        Ops[i]->getType()->getScalarType() != IntPtrScalarTy) {
+        Ops[i]->getType()->getScalarType() != IndexScalarTy) {
       Any = true;
       Type *NewType = Ops[i]->getType()->isVectorTy()
-                          ? IntPtrTy
-                          : IntPtrTy->getScalarType();
+                          ? IndexTy
+                          : IndexScalarTy;
       NewIdxs.push_back(ConstantExpr::getCast(CastInst::getCastOpcode(Ops[i],
                                                                       true,
                                                                       NewType,
                                                                       true),
                                               Ops[i], NewType));
     } else
       NewIdxs.push_back(Ops[i]);
   }
Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP,
   if (Constant *C = CastGEPIndices(SrcElemTy, Ops, ResTy,
                                    GEP->getInRangeIndex(), DL, TLI))
     return C;
 
   Constant *Ptr = Ops[0];
   if (!Ptr->getType()->isPointerTy())
     return nullptr;
 
+  Type *IndexTy = DL.getIndexType(Ptr->getType());
   Type *IntPtrTy = DL.getIntPtrType(Ptr->getType());
 
   // If this is a constant expr gep that is effectively computing an
   // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12'
-  for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+  // The transformation is legal if GEP index and pointer have the same width. 
+  if (IndexTy->getPrimitiveSizeInBits() == IntPtrTy->getPrimitiveSizeInBits()) {
+    for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
       if (!isa<ConstantInt>(Ops[i])) {
 
         // If this is "gep i8* Ptr, (sub 0, V)", fold this as:
         // "inttoptr (sub (ptrtoint Ptr), V)"
         if (Ops.size() == 2 && ResElemTy->isIntegerTy(8)) {
           auto *CE = dyn_cast<ConstantExpr>(Ops[1]);
           assert((!CE || CE->getType() == IntPtrTy) &&
                  "CastGEPIndices didn't canonicalize index types!");
           if (CE && CE->getOpcode() == Instruction::Sub &&
               CE->getOperand(0)->isNullValue()) {
             Constant *Res = ConstantExpr::getPtrToInt(Ptr, CE->getType());
             Res = ConstantExpr::getSub(Res, CE->getOperand(1));
             Res = ConstantExpr::getIntToPtr(Res, ResTy);
             if (auto *FoldedRes = ConstantFoldConstant(Res, DL, TLI))
               Res = FoldedRes;
             return Res;
           }
         }
         return nullptr;
       }
-
-  unsigned BitWidth = DL.getTypeSizeInBits(IntPtrTy);
+    }
+  }
+  unsigned BitWidth = DL.getTypeSizeInBits(IndexTy);
   APInt Offset =
       APInt(BitWidth,
             DL.getIndexedOffsetInType(
                 SrcElemTy,
                 makeArrayRef((Value * const *)Ops.data() + 1, Ops.size() - 1)));
   Ptr = StripPtrCastKeepAS(Ptr, SrcElemTy);
 
   // If this is a GEP of a GEP, fold it all into a single GEP.
if (!Ty->isStructTy()) {
       }
 
       // Determine which element of the array the offset points into.
       APInt ElemSize(BitWidth, DL.getTypeAllocSize(Ty));
       if (ElemSize == 0) {
         // The element size is 0. This may be [0 x Ty]*, so just use a zero
         // index for this level and proceed to the next level to see if it can
         // accommodate the offset.
-        NewIdxs.push_back(ConstantInt::get(IntPtrTy, 0));
+        NewIdxs.push_back(ConstantInt::get(IndexTy, 0));
       } else {
         // The element size is non-zero divide the offset by the element
         // size (rounding down), to compute the index at this level.
         bool Overflow;
         APInt NewIdx = Offset.sdiv_ov(ElemSize, Overflow);
         if (Overflow)
           break;
         Offset -= NewIdx * ElemSize;
-        NewIdxs.push_back(ConstantInt::get(IntPtrTy, NewIdx));
+        NewIdxs.push_back(ConstantInt::get(IndexTy, NewIdx));
       }
     } else {
       auto *STy = cast<StructType>(Ty);
       // If we end up with an offset that isn't valid for this struct type, we
       // can't re-form this GEP in a regular form, so bail out. The pointer
       // operand likely went through casts that are necessary to make the GEP
       // sensible.
       const StructLayout &SL = *DL.getStructLayout(STy);

lib/IR/DataLayout.cpp

Type *DataLayout::getSmallestLegalIntType(LLVMContext &C, unsigned Width) const {
   return nullptr;
 }
 
 unsigned DataLayout::getLargestLegalIntTypeSizeInBits() const {
   auto Max = std::max_element(LegalIntWidths.begin(), LegalIntWidths.end());
   return Max != LegalIntWidths.end() ? *Max : 0;
 }
 
+Type *DataLayout::getIndexType(Type *Ty) const {
+  assert(Ty->isPtrOrPtrVectorTy() &&
+         "Expected a pointer or pointer vector type.");
+  unsigned PointerSize = getPointerTypeSizeInBits(Ty);
+  unsigned LargestIntSize = getLargestLegalIntTypeSizeInBits();
+  unsigned NumBits =
+      LargestIntSize ? std::min(PointerSize, LargestIntSize) : PointerSize;
+  IntegerType *IntTy = IntegerType::get(Ty->getContext(), NumBits);
+  if (VectorType *VecTy = dyn_cast<VectorType>(Ty))
+    return VectorType::get(IntTy, VecTy->getNumElements());
+  return IntTy;
+}
+
 int64_t DataLayout::getIndexedOffsetInType(Type *ElemTy,
                                            ArrayRef<Value *> Indices) const {
   int64_t Result = 0;
 
   generic_gep_type_iterator<Value* const*>
     GTI = gep_type_begin(ElemTy, Indices),
     GTE = gep_type_end(ElemTy, Indices);
   for (; GTI != GTE; ++GTI) {

lib/Transforms/InstCombine/InstCombineCompares.cpp

static Value *rewriteGEPAsOffset(Value *Start, Value *Base,
                                  SetVector<Value *> &Explored) {
   // Perform all the substitutions. This is a bit tricky because we can
   // have cycles in our use-def chains.
   // 1. Create the PHI nodes without any incoming values.
   // 2. Create all the other values.
   // 3. Add the edges for the PHI nodes.
   // 4. Emit GEPs to get the original pointers.
   // 5. Remove the original instructions.
-  Type *IndexType = IntegerType::get(
-      Base->getContext(), DL.getPointerTypeSizeInBits(Start->getType()));
+  Type *IndexType = DL.getIndexType(Start->getType());
 
   DenseMap<Value *, Value *> NewInsts;
   NewInsts[Base] = ConstantInt::getNullValue(IndexType);
 
   // Create the new PHI nodes, without adding any incoming values.
   for (Value *Val : Explored) {
     if (Val == Base)
       continue;
static Value *rewriteGEPAsOffset(Value *Start, Value *Base,
   return NewInsts[Start];
 }
 
 /// Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express
 /// the input Value as a constant indexed GEP. Returns a pair containing
 /// the GEPs Pointer and Index.
 static std::pair<Value *, Value *>
 getAsConstantIndexedAddress(Value *V, const DataLayout &DL) {
-  Type *IndexType = IntegerType::get(V->getContext(),
-                                     DL.getPointerTypeSizeInBits(V->getType()));
+  Type *IndexType = DL.getIndexType(V->getType());
 
   Constant *Index = ConstantInt::getNullValue(IndexType);
   while (true) {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       // We accept only inbouds GEPs here to exclude the possibility of
       // overflow.
       if (!GEP->isInBounds())
         break;

lib/Transforms/InstCombine/InstructionCombining.cpp

Type *InstCombiner::FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
                                         SmallVectorImpl<Value *> &NewIndices) {
   Type *Ty = PtrTy->getElementType();
   if (!Ty->isSized())
     return nullptr;
 
   // Start with the index over the outer type.  Note that the type size
   // might be zero (even if the offset isn't zero) if the indexed type
   // is something like [0 x {int, int}]
-  Type *IntPtrTy = DL.getIntPtrType(PtrTy);
+  Type *IndexTy = DL.getIndexType(PtrTy);
   int64_t FirstIdx = 0;
   if (int64_t TySize = DL.getTypeAllocSize(Ty)) {
     FirstIdx = Offset/TySize;
     Offset -= FirstIdx*TySize;
 
     // Handle hosts where % returns negative instead of values [0..TySize).
     if (Offset < 0) {
       --FirstIdx;
       Offset += TySize;
       assert(Offset >= 0);
     }
     assert((uint64_t)Offset < (uint64_t)TySize && "Out of range offset");
   }
 
-  NewIndices.push_back(ConstantInt::get(IntPtrTy, FirstIdx));
+  NewIndices.push_back(ConstantInt::get(IndexTy, FirstIdx));
 
   // Index into the types.  If we fail, set OrigBase to null.
   while (Offset) {
     // Indexing into tail padding between struct/array elements.
     if (uint64_t(Offset * 8) >= DL.getTypeSizeInBits(Ty))
       return nullptr;
 
     if (StructType *STy = dyn_cast<StructType>(Ty)) {
       const StructLayout *SL = DL.getStructLayout(STy);
       assert(Offset < (int64_t)SL->getSizeInBytes() &&
              "Offset must stay within the indexed type");
 
       unsigned Elt = SL->getElementContainingOffset(Offset);
       NewIndices.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()),
                                             Elt));
 
       Offset -= SL->getElementOffset(Elt);
       Ty = STy->getElementType(Elt);
     } else if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) {
       uint64_t EltSize = DL.getTypeAllocSize(AT->getElementType());
       assert(EltSize && "Cannot index into a zero-sized array");
-      NewIndices.push_back(ConstantInt::get(IntPtrTy,Offset/EltSize));
+      NewIndices.push_back(ConstantInt::get(IndexTy,Offset/EltSize));
       Offset %= EltSize;
       Ty = AT->getElementType();
     } else {
       // Otherwise, we can't index into the middle of this atomic type, bail.
       return nullptr;
     }
   }
 
if (Value *V = SimplifyGEPInst(GEP.getSourceElementType(), Ops,
                                  SQ.getWithInstruction(&GEP)))
     return replaceInstUsesWith(GEP, V);
 
   Value *PtrOp = GEP.getOperand(0);
 
   // Eliminate unneeded casts for indices, and replace indices which displace
   // by multiples of a zero size type with zero.
   bool MadeChange = false;
-  Type *IntPtrTy =
-    DL.getIntPtrType(GEP.getPointerOperandType()->getScalarType());
+
+  // Index width shouldn't have the same width as pointer. Data layout chooses
+  // the right type based on supported integer types.
+  Type *NewScalarIndexTy =
+      DL.getIndexType(GEP.getPointerOperandType()->getScalarType());
 
   gep_type_iterator GTI = gep_type_begin(GEP);
   for (User::op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E;
        ++I, ++GTI) {
     // Skip indices into struct types.
     if (GTI.isStruct())
       continue;
 
-    // Index type should have the same width as IntPtr
     Type *IndexTy = (*I)->getType();
-    Type *NewIndexType = IndexTy->isVectorTy() ?
-      VectorType::get(IntPtrTy, IndexTy->getVectorNumElements()) : IntPtrTy;
+    Type *NewIndexType =
+        IndexTy->isVectorTy()
+            ? VectorType::get(NewScalarIndexTy, IndexTy->getVectorNumElements())
+            : NewScalarIndexTy;
 
     // If the element type has zero size then any index over it is equivalent
     // to an index of zero, so replace it with zero if it is not zero already.
     Type *EltTy = GTI.getIndexedType();
     if (EltTy->isSized() && DL.getTypeAllocSize(EltTy) == 0)
       if (!isa<Constant>(*I) || !cast<Constant>(*I)->isNullValue()) {
         *I = Constant::getNullValue(NewIndexType);
         MadeChange = true;
if (HasZeroPointerIndex) {
       // Transform things like:
       // %t = getelementptr i32* bitcast ([2 x i32]* %str to i32*), i32 %V
       // into:  %t1 = getelementptr [2 x i32]* %str, i32 0, i32 %V; bitcast
       Type *SrcElTy = StrippedPtrTy->getElementType();
       Type *ResElTy = GEP.getSourceElementType();
       if (SrcElTy->isArrayTy() &&
           DL.getTypeAllocSize(SrcElTy->getArrayElementType()) ==
               DL.getTypeAllocSize(ResElTy)) {
-        Type *IdxType = DL.getIntPtrType(GEP.getType());
+        Type *IdxType = DL.getIndexType(GEP.getType());
         Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) };
         Value *NewGEP =
             GEP.isInBounds()
                 ? Builder.CreateInBoundsGEP(nullptr, StrippedPtr, Idx,
                                             GEP.getName())
                 : Builder.CreateGEP(nullptr, StrippedPtr, Idx, GEP.getName());
 
         // V and GEP are both pointer types --> BitCast
if (HasZeroPointerIndex) {
         // factor.
         uint64_t ResSize = DL.getTypeAllocSize(ResElTy);
         uint64_t SrcSize = DL.getTypeAllocSize(SrcElTy);
         if (ResSize && SrcSize % ResSize == 0) {
           Value *Idx = GEP.getOperand(1);
           unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
           uint64_t Scale = SrcSize / ResSize;
 
-          // Earlier transforms ensure that the index has type IntPtrType, which
-          // considerably simplifies the logic by eliminating implicit casts.
-          assert(Idx->getType() == DL.getIntPtrType(GEP.getType()) &&
-                 "Index not cast to pointer width?");
+          // Earlier transforms ensure that the index has the right type
+          // according to Data Layout, which considerably simplifies the
+          // logic by eliminating implicit casts.
+          assert(Idx->getType() == DL.getIndexType(GEP.getType()) &&
+                 "Index type does not match the Data Layout preferences");
 
           bool NSW;
           if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
             // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
             // If the multiplication NewIdx * Scale may overflow then the new
             // GEP may not be "inbounds".
             Value *NewGEP =
                 GEP.isInBounds() && NSW
if (HasZeroPointerIndex) {
         uint64_t ResSize = DL.getTypeAllocSize(ResElTy);
         uint64_t ArrayEltSize =
             DL.getTypeAllocSize(SrcElTy->getArrayElementType());
         if (ResSize && ArrayEltSize % ResSize == 0) {
           Value *Idx = GEP.getOperand(1);
           unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
           uint64_t Scale = ArrayEltSize / ResSize;
 
-          // Earlier transforms ensure that the index has type IntPtrType, which
-          // considerably simplifies the logic by eliminating implicit casts.
-          assert(Idx->getType() == DL.getIntPtrType(GEP.getType()) &&
-                 "Index not cast to pointer width?");
+          // Earlier transforms ensure that the index has the right type
+          // according to the Data Layout, which considerably simplifies
+          // the logic by eliminating implicit casts.
+          assert(Idx->getType() == DL.getIndexType(GEP.getType()) &&
+                 "Index type does not match the Data Layout preferences");
 
           bool NSW;
           if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
             // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
             // If the multiplication NewIdx * Scale may overflow then the new
             // GEP may not be "inbounds".
-            Value *Off[2] = {
-                Constant::getNullValue(DL.getIntPtrType(GEP.getType())),
-                NewIdx};
+            Type *IndTy = DL.getIndexType(GEP.getType());
+            Value *Off[2] = {Constant::getNullValue(IndTy), NewIdx};
 
             Value *NewGEP = GEP.isInBounds() && NSW
                                 ? Builder.CreateInBoundsGEP(
                                       SrcElTy, StrippedPtr, Off, GEP.getName())
                                 : Builder.CreateGEP(SrcElTy, StrippedPtr, Off,
                                                     GEP.getName());
             // The NewGEP must be pointer typed, so must the old one -> BitCast
             return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP,

test/Transforms/InstCombine/gep-custom-dl.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-m:m-p:40:64:64-i32:32-i16:16-i8:8-n32"
+
+%struct.B = type { double }
+%struct.A = type { %struct.B, i32, i32 }
+%struct.C = type { [7 x i8] }
+
+
+@Global = constant [10 x i8] c"helloworld"
+
+
+; Test that two array indexing geps fold
+define i32* @test1(i32* %I) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr i32, i32* [[I:%.*]], i32 21
+; CHECK-NEXT:    ret i32* [[B]]
+;
+  %A = getelementptr i32, i32* %I, i8 17
+  %B = getelementptr i32, i32* %A, i16 4
+  ret i32* %B
+}
+
+; Test that two getelementptr insts fold
+define i32* @test2({ i32 }* %I) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    [[B:%.*]] = getelementptr { i32 }, { i32 }* [[I:%.*]], i32 1, i32 0
+; CHECK-NEXT:    ret i32* [[B]]
+;
+  %A = getelementptr { i32 }, { i32 }* %I, i32 1
+  %B = getelementptr { i32 }, { i32 }* %A, i32 0, i32 0
+  ret i32* %B
+}
+
+define void @test3(i8 %B) {
+; This should be turned into a constexpr instead of being an instruction
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    store i8 [[B:%.*]], i8* getelementptr inbounds ([10 x i8], [10 x i8]* @Global, i32 0, i32 4), align 1
+; CHECK-NEXT:    ret void
+;
+  %A = getelementptr [10 x i8], [10 x i8]* @Global, i32 0, i32 4
+  store i8 %B, i8* %A
+  ret void
+}
+
+%as1_ptr_struct = type { i32 addrspace(1)* }
+%as2_ptr_struct = type { i32 addrspace(2)* }
+
+@global_as2 = addrspace(2) global i32 zeroinitializer
+@global_as1_as2_ptr = addrspace(1) global %as2_ptr_struct { i32 addrspace(2)* @global_as2 }
+
+; This should be turned into a constexpr instead of being an instruction
+define void @test_evaluate_gep_nested_as_ptrs(i32 addrspace(2)* %B) {
+; CHECK-LABEL: @test_evaluate_gep_nested_as_ptrs(
+; CHECK-NEXT:    store i32 addrspace(2)* [[B:%.*]], i32 addrspace(2)* addrspace(1)* getelementptr inbounds (%as2_ptr_struct, [[AS2_PTR_STRUCT:%.*]] addrspace(1)* @global_as1_as2_ptr, i32 0, i32 0), align 8
+; CHECK-NEXT:    ret void
+;
+  %A = getelementptr %as2_ptr_struct, %as2_ptr_struct addrspace(1)* @global_as1_as2_ptr, i32 0, i32 0
+  store i32 addrspace(2)* %B, i32 addrspace(2)* addrspace(1)* %A
+  ret void
+}
+
+@arst = addrspace(1) global [4 x i8 addrspace(2)*] zeroinitializer
+
+define void @test_evaluate_gep_as_ptrs_array(i8 addrspace(2)* %B) {
+; CHECK-LABEL: @test_evaluate_gep_as_ptrs_array(
+; CHECK-NEXT:    store i8 addrspace(2)* [[B:%.*]], i8 addrspace(2)* addrspace(1)* getelementptr inbounds ([4 x i8 addrspace(2)*], [4 x i8 addrspace(2)*] addrspace(1)* @arst, i32 0, i32 2), align 16
+; CHECK-NEXT:    ret void
+;
+
+  %A = getelementptr [4 x i8 addrspace(2)*], [4 x i8 addrspace(2)*] addrspace(1)* @arst, i16 0, i16 2
+  store i8 addrspace(2)* %B, i8 addrspace(2)* addrspace(1)* %A
+  ret void
+}
+
+define i32* @test4(i32* %I, i32 %C, i32 %D) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    [[A:%.*]] = getelementptr i32, i32* [[I:%.*]], i32 [[C:%.*]]
+; CHECK-NEXT:    [[B:%.*]] = getelementptr i32, i32* [[A]], i32 [[D:%.*]]
+; CHECK-NEXT:    ret i32* [[B]]
+;
+  %A = getelementptr i32, i32* %I, i32 %C
+  %B = getelementptr i32, i32* %A, i32 %D
+  ret i32* %B
+}
+
+
+define i1 @test5({ i32, i32 }* %x, { i32, i32 }* %y) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[TMP_4:%.*]] = icmp eq { i32, i32 }* [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP_4]]
+;
+  %tmp.1 = getelementptr { i32, i32 }, { i32, i32 }* %x, i32 0, i32 1
+  %tmp.3 = getelementptr { i32, i32 }, { i32, i32 }* %y, i32 0, i32 1
+  ;; seteq x, y
+  %tmp.4 = icmp eq i32* %tmp.1, %tmp.3
+  ret i1 %tmp.4
+}
+
+%S = type { i32, [ 100 x i32] }
+
+define <2 x i1> @test6(<2 x i32> %X, <2 x %S*> %P) nounwind {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    ret <2 x i1> [[C]]
+;
+  %A = getelementptr inbounds %S, <2 x %S*> %P, <2 x i32> zeroinitializer, <2 x i32> <i32 1, i32 1>, <2 x i32> %X
+  %B = getelementptr inbounds %S, <2 x %S*> %P, <2 x i32> <i32 0, i32 0>, <2 x i32> <i32 0, i32 0>
+  %C = icmp eq <2 x i32*> %A, %B
+  ret <2 x i1> %C
+}
+
+@G = external global [3 x i8]
+define i8* @test7(i16 %Idx) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    [[ZE_IDX:%.*]] = zext i16 [[IDX:%.*]] to i32
+; CHECK-NEXT:    [[TMP:%.*]] = getelementptr [3 x i8], [3 x i8]* @G, i32 0, i32 [[ZE_IDX]]
+; CHECK-NEXT:    ret i8* [[TMP]]
+;
+  %ZE_Idx = zext i16 %Idx to i32
+  %tmp = getelementptr i8, i8* getelementptr ([3 x i8], [3 x i8]* @G, i32 0, i32 0), i32 %ZE_Idx
+  ret i8* %tmp
+}
+
+
+; Test folding of constantexpr geps into normal geps.
+@Array = external global [40 x i32]
+define i32 *@test8(i32 %X) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    [[A:%.*]] = getelementptr [40 x i32], [40 x i32]* @Array, i32 0, i32 [[X:%.*]]
+; CHECK-NEXT:    ret i32* [[A]]
+;
+  %A = getelementptr i32, i32* getelementptr ([40 x i32], [40 x i32]* @Array, i32 0, i32 0), i32 %X
+  ret i32* %A
+}
+
+define i32 *@test9(i32 *%base, i8 %ind) {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i8 [[IND:%.*]] to i32
+; CHECK-NEXT:    [[RES:%.*]] = getelementptr i32, i32* [[BASE:%.*]], i32 [[TMP1]]
+; CHECK-NEXT:    ret i32* [[RES]]
+;
+  %res = getelementptr i32, i32 *%base, i8 %ind
+  ret i32* %res
+}
+
+define i32 @test10() {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:    ret i32 8
+;
+  %A = getelementptr { i32, double }, { i32, double }* null, i32 0, i32 1
+  %B = ptrtoint double* %A to i32
+  ret i32 %B
+}

test/Transforms/InstCombine/memcmp-constant-fold.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S -data-layout=e-n32 | FileCheck %s --check-prefix=ALL --check-prefix=LE
 ; RUN: opt < %s -instcombine -S -data-layout=E-n32 | FileCheck %s --check-prefix=ALL --check-prefix=BE
 
 declare i32 @memcmp(i8*, i8*, i64)
 
 ; The alignment of this constant does not matter. We constant fold the load.
 
 @charbuf = private unnamed_addr constant [4 x i8] [i8 0, i8 0, i8 0, i8 1], align 1

 }
 
 ; TODO: Any memcmp where all arguments are constants should be constant folded. Currently, we only handle i8 array constants.
 
 @intbuf = private unnamed_addr constant [2 x i32] [i32 0, i32 1], align 4
 
 define i1 @memcmp_3bytes_aligned_constant_i32(i8* align 4 %x) {
 ; ALL-LABEL: @memcmp_3bytes_aligned_constant_i32(
-; ALL-NEXT:    [[CALL:%.*]] = tail call i32 @memcmp(i8* bitcast (i32* getelementptr inbounds ([2 x i32], [2 x i32]* @intbuf, i64 0, i64 1) to i8*), i8* bitcast ([2 x i32]* @intbuf to i8*), i64 3)
+; ALL-NEXT:    [[CALL:%.*]] = tail call i32 @memcmp(i8* bitcast (i32* getelementptr inbounds ([2 x i32], [2 x i32]* @intbuf, i32 0, i32 1) to i8*), i8* bitcast ([2 x i32]* @intbuf to i8*), i64 3)
 ; ALL-NEXT:    [[CMPEQ0:%.*]] = icmp eq i32 [[CALL]], 0
 ; ALL-NEXT:    ret i1 [[CMPEQ0]]
 ;
   %call = tail call i32 @memcmp(i8* bitcast (i32* getelementptr inbounds ([2 x i32], [2 x i32]* @intbuf, i64 0, i64 1) to i8*), i8* bitcast (i32* getelementptr inbounds ([2 x i32], [2 x i32]* @intbuf, i64 0, i64 0) to i8*), i64 3)
   %cmpeq0 = icmp eq i32 %call, 0
   ret i1 %cmpeq0
 }