[IR] `GetElementPtrInst`: per-index `inrange` support

[lebedev.ri]

Summary

This is a follow-up for D22793, and the [llvm-dev] [RFC] Adding range metadata to array subscripts.: https://groups.google.com/g/llvm-dev/c/T9o51zB1JHY

As per C 6.5.6p9 / http://eel.is/c++draft/expr.add#4, given

struct S {
    int a[3];
    int b[3];
    int c[3];
};

void bar(int*);

void foo(S* s) {
  bar(&s.b[1]);
}

even though the pointer the bar receives has 4 ints to the left of it and 4 to the right of it,
the only ints it can access are one to the left and one to the right.
I.e. it can not go outside of the S::b.

But, there is currently no way to represent this in LLVM IR,
and this makes some optimizations impossible.
In my case, i'd like to improve alloca splitting,
but this also affects alias analysis.

While that RFC proposed a number of implementation variants,
i think it is obvious that the inrange approach is superiour,
because constant expr GEP's already support that,
and because encoding such knowledge via assumes will make it impossible to make use of it.

Now, GEP's can have a large number of indices,
so even though we have (7-1)+(16-1)=21 vacant bits total in SubclassOptionalData and SubclassData,
we have to support storing the arbitary number of is index inrange bits,
so we have to allocate additional trailing objects.
(I suspect there are bugs in this logic, will add better tests.)

I will add clang support in later changes.

[nikic]

While I support the general goal of exposing GEP offset restrictions to IR, I am quite strongly opposed to the implementation approach of extending inrange. The core issue is that this is strongly tied to LLVM struct types and structural GEP indexing. This will be a blow to opaque pointer usefulness and future offset canonicalization for GEPs.

I think the correct approach to inrange-like information is to restrict the range of GEP indices without relying on the underlying structure type. Think inrange(0, 4) i32 %x for %x between 0 and 4. This naturally integrates in purely offset-based alias analysis, and can be more generally preserved under transformation. For example, if you have gep %base, inrange (%x + 1), if this is transformed into gep (gep %base, 1), %x there is no way to preserve inrange information under the current proposal, while a proper offset-based approach could easily retain information under simple transformations.

[lebedev.ri]

In D114988#3167963, @nikic wrote:

While I support the general goal of exposing GEP offset restrictions to IR,
I am quite strongly opposed to the implementation approach of extending inrange.
The core issue is that this is strongly tied to LLVM struct types and structural GEP indexing.
This will be a blow to opaque pointer usefulness and future offset canonicalization for GEPs.

While i'm certainly sympathetic to the opaque pointer future,
i'd also like to remind that they are just a tool.

Concretely, can you quote anything that says that in the opaque pointer future,
the only GEP that will remain will only be able to apply a byte offset to the pointer,
i.e. there won't be GEP's into structs/multiple indices?

I think the correct approach to inrange-like information is to restrict the range of GEP indices
without relying on the underlying structure type. Think inrange(0, 4) i32 %x for %x between 0 and 4.
This naturally integrates in purely offset-based alias analysis, and can be more generally preserved under transformation.
For example, if you have gep %base, inrange (%x + 1), if this is transformed into gep (gep %base, 1), %x
there is no way to preserve inrange information under the current proposal,
while a proper offset-based approach could easily retain information under simple transformations.

I think you are missing the whole point there. It is explicitly NOT the point of this patch
to be able encode that some index must take values in range of [x, y). So if that is your proposal,
while it may be interesting, it's explicitly inferior, and does not solve the motivational case.

The reason being, it encodes *VERY* different semantics.
If we've encoded that in

struct S {
    int a[3];
    int b[3];
    int c[3];
};

void bar(int*);

void foo(S* s, int i) {
  int* p = &s.b[i];
  bar(p);
  int* p2 = p + 4; // UB!
  bar(p);
}

the variable i of function foo must be [0, 3),
that only tells us that p is pointing somewhere in (int*)s + 3 + [0, 3).
What it does not encode is that, given that pointer, we can not go outside of that array,
i.e. that auto* p2 = p + 4; is UB.

[nikic]

I think you are missing the whole point there. It is explicitly NOT the point of this patch
to be able encode that some index must take values in range of [x, y). So if that is your proposal,
while it may be interesting, it's explicitly inferior, and does not solve the motivational case.

Right, sorry. I thought you wanted to solve the same issue discussed in the llvm-dev thread, but I see that you're more interested in SROA than AA here. I don't think this materially changes my point though. Rather than restricting the range of an offset, you are instead restricting which offsets of the GEP base can be accessed (either through this GEP, or a later one). That's still something that can be expressed in terms of explicit offsets rather than basing it on struct types. One could argue that this is really a "restrict object" operation that is largely independent from the GEP arithematic and could e.g. be represented as an intrinsic returning a restricted pointer. But I understand that encoding this in the GEP makes this more viable.

Concretely, can you quote anything that says that in the opaque pointer future,
the only GEP that will remain will only be able to apply a byte offset to the pointer,
i.e. there won't be GEP's into structs/multiple indices?

See this thread: https://groups.google.com/g/llvm-dev/c/U7D6z7ZnKy8/m/2-xy5zPcBAAJ Under opaque pointers, we are currently representing constant offset GEPs as i8 GEPs, because this makes things a lot simpler -- with opaque pointers type information tends to not be preserved naturally, and you have to go out of your way, and in some cases use heuristics, to preserve type information. And apart from inrange, doing so is entirely wasted effort. For example, SROA will just generate i8 GEPs instead of doing a complicated dance trying to find a minimal natural-looking GEP.

[lebedev.ri]

In D114988#3168197, @nikic wrote:

I think you are missing the whole point there. It is explicitly NOT the point of this patch
to be able encode that some index must take values in range of [x, y). So if that is your proposal,
while it may be interesting, it's explicitly inferior, and does not solve the motivational case.

Right, sorry. I thought you wanted to solve the same issue discussed in the llvm-dev thread, but I see that you're more interested in SROA than AA here.

Yup.

I don't think this materially changes my point though. Rather than restricting the range of an offset,
you are instead restricting which offsets of the GEP base can be accessed (either through this GEP,
or a later one). That's still something that can be expressed in terms of explicit offsets rather than
basing it on struct types.

I agree that we can express a number of cases with explicit offsets.
Presumably, we'd even be fine with having a number of these inrange(C0, C1) in a single GEP.
But, what happens for e.g.

struct S {
  int array[4][4];
};
int& foo(S*s, int i, int j) {
  return s.array[i][j];
}

?
We can annotate that we don't escape from the entire array (i.e. [0, 128)),
but if i is not a constant, how are we going to annotate the inner GEP?
Should we require that there be two GEP's there, and forbid their fusion?

One could argue that this is really a "restrict object" operation
that is largely independent from the GEP arithematic and could e.g. be represented as
an intrinsic returning a restricted pointer. But I understand that encoding this in the GEP makes this more viable.

Concretely, can you quote anything that says that in the opaque pointer future,
the only GEP that will remain will only be able to apply a byte offset to the pointer,
i.e. there won't be GEP's into structs/multiple indices?

See this thread: https://groups.google.com/g/llvm-dev/c/U7D6z7ZnKy8/m/2-xy5zPcBAAJ Under opaque pointers,
we are currently representing constant offset GEPs as i8 GEPs, because this makes things
a lot simpler -- with opaque pointers type information tends to not be preserved naturally,
and you have to go out of your way, and in some cases use heuristics, to preserve type information.
And apart from inrange, doing so is entirely wasted effort.
For example, SROA will just generate i8 GEPs instead of doing a complicated dance trying to find a minimal natural-looking GEP.

Note that i'm mostly interested in annotating the outermost variable GEP,
since that is what will limit the alloca splitting. Constant indices are obvious,
and any indices after the first variable indice won't be relevant.

[lebedev.ri]

Ok, i guess i have a rather more general and radical, invasive solution, let's see if that works out first.

[efriedma]

Consider the following:

struct S {
    int a[3], b[3], c[3];
};

int foo(S* s) {
  return &s.a[3] == &s.b[0];
}

The C standard says this returns 1; if you lower the address computation using inrange, it returns poison. I think? Maybe you can apply inrange markings in some cases, e.g. you can be more aggressive if you prove the address is used by a load/store operations. But it's not trivial.

Also, it's not obvious inrange is sound; nobody has tried to formally model the pointer provenance or pointer comparison rules specified for inrange.

[nlopes]

(thinking out loud)
The main issue seems to be that C's memory model allows field-sensitive AA, while LLVM does not. But each field is not an object on its own, it's more like a sub-object. In C, you can memcpy a whole struct, as it's an object, but once you index into a specific filed you can't dereference another field.
It's as if the struct is an object and each field is a sub-object.

Re inrange, currently it doesn't disallow OOB pointers; it just says that dereferencing such pointers triggers UB. Eli's example is actually fine with the current wording. It's just that the current wording is not consistent with the rest of LangRef; it requires additional machinery in the memory model.
Other 2 possibilities that come to mind are TBAA and the proposal to handle C's restrict that pushes provenance information to memory operations rather than having it in GEPs. Though it's unclear to me whether tagging memory operations is even possible.

In the past, Johannes proposed using range information for the variables in GEP (using the assumptions machinery already available). That could work, but we need to make sure it doesn't block optimizations. We don't LLVM to trigger UB if an array index is OOB; we just need it to turn poison. The current ranges trigger UB AFAIR.

IMHO, we need a group of people to commit to studying the different features that are needed and make a consistent design to avoid the current patchwork we have. Not an easy feat, though.

[courbet]

In D114988#3172161, @nlopes wrote:

In the past, Johannes proposed using range information for the variables in GEP (using the assumptions machinery already available). That could work, but we need to make sure it doesn't block optimizations. We don't LLVM to trigger UB if an array index is OOB; we just need it to turn poison.

Note that since D109746, BasicAA already uses ranges information to derive NoAlias. This is an example where the range information can help independently of proving UB. For now this only works when the compiler can otherwise prove the range, e.g. for

struct Histogram {
  int buckets[4];
  int count;

  void f(unsigned i) {
    ++buckets[i & 3];
    ++count;
    // buckets[i&3] and count are noalias.
  }
};

When clang starts emitting range information (in any form recognizable by ValueTracking, I don't have a strong opinion on which for is best), we can start having buckets[i & 3] and count be NoAlias more generally.

[lebedev.ri]

This patch isn't going anywhere, the proper solution will be along the lines of D115274.

[brunodf]

Sorry, I'm late to read this diff.

In D114988#3171000, @efriedma wrote:

Consider the following:

struct S {
    int a[3], b[3], c[3];
};

int foo(S* s) {
  return &s.a[3] == &s.b[0];
}

The C standard says this returns 1; if you lower the address computation using inrange, it returns poison. I think?

Could you clarify how the C standard guarantees this will return 1? I think the standard allows padding between struct members a and b (even though I see very little reason to add padding here) so the comparison does not have a defined result.

[efriedma]

Could you clarify how the C standard guarantees this will return 1?

"Two pointers compare equal if [...] one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space."

I think the standard allows padding between struct members a and b (even though I see very little reason to add padding here)

The relevant rule says that if there isn't any padding, the pointers compare equal. And we don't insert padding in practice. It doesn't matter that some other compiler could theoretically add padding.

[brunodf]

In D114988#3437219, @efriedma wrote:

Could you clarify how the C standard guarantees this will return 1?

"Two pointers compare equal if [...] one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space."

I think the standard allows padding between struct members a and b (even though I see very little reason to add padding here)

The relevant rule says that if there isn't any padding, the pointers compare equal. And we don't insert padding in practice. It doesn't matter that some other compiler could theoretically add padding.

OK, got it. The cited sentence has footnote: "Two objects may be adjacent in memory because they are adjacent elements of a larger array or adjacent members of a structure with no padding between them, or because the implementation chose to place them so, even though they are unrelated."

I see a parallel with local variables:

int a[3], b[3];

That may happen to be placed next to each other in the stack frame, such that &a[3] == &b[0] indeed leading to the provenance problem you also mentioned.

llvm/docs/LangRef.rst

 storing to any pointer derived from the ``getelementptr`` has undefined
 behavior if the load or store would access memory outside of the bounds of
 the element selected by the index marked as ``inrange``. The result of a
 pointer comparison or ``ptrtoint`` (including ``ptrtoint``-like operations
 involving memory) involving a pointer derived from a ``getelementptr`` with
 the ``inrange`` keyword is undefined, with the exception of comparisons
 in the case where both operands are in the range of the element selected
 by the ``inrange`` keyword, inclusive of the address one past the end of
-that element. Note that the ``inrange`` keyword is currently only allowed
-in constant ``getelementptr`` expressions.
+that element.
 
 The getelementptr instruction is often confusing. For some more insight
 into how it works, see :doc:`the getelementptr FAQ <GetElementPtr>`.
 
 Example:
 """"""""
 
 .. code-block:: llvm

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum FunctionCodes {
   FUNC_CODE_OPERAND_BUNDLE = 55, // OPERAND_BUNDLE: [tag#, value...]
   FUNC_CODE_INST_UNOP = 56,      // UNOP:       [opcode, ty, opval]
   FUNC_CODE_INST_CALLBR = 57,    // CALLBR:     [attr, cc, norm, transfs,
                                  //              fnty, fnid, args...]
   FUNC_CODE_INST_FREEZE = 58,    // FREEZE: [opty, opval]
   FUNC_CODE_INST_ATOMICRMW = 59, // ATOMICRMW: [ptrty, ptr, valty, val,
                                  //             operation, align, vol,
                                  //             ordering, synchscope]
+  FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES =
+      60, // GEP:  [inbounds, (n)um indices, n+1 x operands, n x inrange]
+
 };
 
 enum UseListCodes {
   USELIST_CODE_DEFAULT = 1, // DEFAULT: [index..., value-id]
   USELIST_CODE_BB = 2       // BB: [index..., bb-id]
 };
 
 enum AttributeKindCodes {

llvm/include/llvm/IR/Instructions.h

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/CallingConv.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/TrailingObjects.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 
 namespace llvm {
 
 class APInt;
inline Type *checkGEPType(Type *Ty) {
   assert(Ty && "Invalid GetElementPtrInst indices for type!");
   return Ty;
 }
 
 /// an instruction for type-safe pointer arithmetic to
 /// access elements of arrays and structs
 ///
 class GetElementPtrInst : public Instruction {
+  // All but the first bit (which is 'inbounds') of the SubclassOptionalData
+  // can be use for 'inrange' markers.
+  using SubclassOptionalDataInlineBits = Bitfield::Element<uint8_t, 1, 6>;
+  // All but the last bit (which is 'has metadata') of the SubclassData
+  // can be use for [remaining] 'inrange' markers.
+  using SubclassDataInlineBits = Bitfield::Element<uint16_t, 0, 15>;
+  // The rest of the markers will have to be stored in trailing objects.
+
+  using trailing_obj = uintptr_t;
+  using trailing_obj_iterator = trailing_obj *;
+  using const_trailing_obj_iterator = const trailing_obj *;
+
+  static constexpr unsigned NumBitsPerTrailingObject =
+      CHAR_BIT * sizeof(trailing_obj);
+
   Type *SourceElementType;
   Type *ResultElementType;
 
   GetElementPtrInst(const GetElementPtrInst &GEPI);
 
   /// Constructors - Create a getelementptr instruction with a base pointer an
   /// list of indices. The first ctor can optionally insert before an existing
   /// instruction, the second appends the new instruction to the specified
   /// BasicBlock.
   inline GetElementPtrInst(Type *PointeeType, Value *Ptr,
-                           ArrayRef<Value *> IdxList, unsigned Values,
+                           ArrayRef<Value *> IdxList, unsigned NumOps,
                            const Twine &NameStr, Instruction *InsertBefore);
   inline GetElementPtrInst(Type *PointeeType, Value *Ptr,
-                           ArrayRef<Value *> IdxList, unsigned Values,
+                           ArrayRef<Value *> IdxList, unsigned NumOps,
                            const Twine &NameStr, BasicBlock *InsertAtEnd);
 
   void init(Value *Ptr, ArrayRef<Value *> IdxList, const Twine &NameStr);
 
+  static unsigned numTrailingObjects(unsigned NumIndices) {
+    unsigned NumBits = NumIndices;
+    static constexpr unsigned NumInlineBitsMax =
+        SubclassOptionalDataInlineBits::Bits + SubclassDataInlineBits::Bits;
+    ;
+    unsigned NumNonInlineBits =
+        NumBits > NumInlineBitsMax ? NumBits - NumInlineBitsMax : 0;
+    return divideCeil(NumNonInlineBits, NumBitsPerTrailingObject);
+  }
+
+  unsigned getNumTrailingObjects() const {
+    return numTrailingObjects(getNumIndices());
+  }
+
+  inline trailing_obj_iterator trailing_obj_begin() {
+    return reinterpret_cast<trailing_obj_iterator>(op_end());
+  }
+  inline const_trailing_obj_iterator trailing_obj_begin() const {
+    return reinterpret_cast<const_trailing_obj_iterator>(op_end());
+  }
+  inline trailing_obj_iterator trailing_obj_end() {
+    return trailing_obj_begin() + getNumTrailingObjects();
+  }
+  inline const_trailing_obj_iterator trailing_obj_end() const {
+    return trailing_obj_begin() + getNumTrailingObjects();
+  }
+
 protected:
   // Note: Instruction needs to be a friend here to call cloneImpl.
   friend class Instruction;
 
   GetElementPtrInst *cloneImpl() const;
 
 public:
   static GetElementPtrInst *Create(Type *PointeeType, Value *Ptr,
                                    ArrayRef<Value *> IdxList,
                                    const Twine &NameStr = "",
                                    Instruction *InsertBefore = nullptr) {
-    unsigned Values = 1 + unsigned(IdxList.size());
+    unsigned NumIndices = IdxList.size();
+    unsigned NumOps = 1 + NumIndices;
+    unsigned Values = NumOps + numTrailingObjects(NumIndices);
     assert(PointeeType && "Must specify element type");
     assert(cast<PointerType>(Ptr->getType()->getScalarType())
                ->isOpaqueOrPointeeTypeMatches(PointeeType));
-    return new (Values) GetElementPtrInst(PointeeType, Ptr, IdxList, Values,
+    return new (Values) GetElementPtrInst(PointeeType, Ptr, IdxList, NumOps,
                                           NameStr, InsertBefore);
   }
 
   static GetElementPtrInst *Create(Type *PointeeType, Value *Ptr,
                                    ArrayRef<Value *> IdxList,
                                    const Twine &NameStr,
                                    BasicBlock *InsertAtEnd) {
-    unsigned Values = 1 + unsigned(IdxList.size());
+    unsigned NumIndices = IdxList.size();
+    unsigned NumOps = 1 + NumIndices;
+    unsigned Values = NumOps + numTrailingObjects(NumIndices);
     assert(PointeeType && "Must specify element type");
     assert(cast<PointerType>(Ptr->getType()->getScalarType())
                ->isOpaqueOrPointeeTypeMatches(PointeeType));
-    return new (Values) GetElementPtrInst(PointeeType, Ptr, IdxList, Values,
+    return new (Values) GetElementPtrInst(PointeeType, Ptr, IdxList, NumOps,
                                           NameStr, InsertAtEnd);
   }
 
   /// Create an "inbounds" getelementptr. See the documentation for the
   /// "inbounds" flag in LangRef.html for details.
   static GetElementPtrInst *
   CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef<Value *> IdxList,
                  const Twine &NameStr = "",
public:
 
   /// Set or clear the inbounds flag on this GEP instruction.
   /// See LangRef.html for the meaning of inbounds on a getelementptr.
   void setIsInBounds(bool b = true);
 
   /// Determine whether the GEP has the inbounds flag.
   bool isInBounds() const;
 
+  /// Set or clear the inrange flag on the index \p Idx of this GEP instruction.
+  void setIsInRange(unsigned Idx, bool b = true);
+
+  /// Determine whether the index \p Idx of this GEP has the inrange flag.
+  bool isInRange(unsigned Idx) const;
+
   /// Accumulate the constant address offset of this GEP if possible.
   ///
   /// This routine accepts an APInt into which it will accumulate the constant
   /// offset of this GEP if the GEP is in fact constant. If the GEP is not
   /// all-constant, it returns false and the value of the offset APInt is
   /// undefined (it is *not* preserved!). The APInt passed into this routine
   /// must be at least as wide as the IntPtr type for the address space of
   /// the base GEP pointer.

 };
 
 template <>
 struct OperandTraits<GetElementPtrInst> :
   public VariadicOperandTraits<GetElementPtrInst, 1> {
 };
 
 GetElementPtrInst::GetElementPtrInst(Type *PointeeType, Value *Ptr,
-                                     ArrayRef<Value *> IdxList, unsigned Values,
+                                     ArrayRef<Value *> IdxList, unsigned NumOps,
                                      const Twine &NameStr,
                                      Instruction *InsertBefore)
     : Instruction(getGEPReturnType(PointeeType, Ptr, IdxList), GetElementPtr,
-                  OperandTraits<GetElementPtrInst>::op_end(this) - Values,
-                  Values, InsertBefore),
+                  OperandTraits<GetElementPtrInst>::op_end(this) - NumOps,
+                  NumOps, InsertBefore),
       SourceElementType(PointeeType),
       ResultElementType(getIndexedType(PointeeType, IdxList)) {
   assert(cast<PointerType>(getType()->getScalarType())
              ->isOpaqueOrPointeeTypeMatches(ResultElementType));
   init(Ptr, IdxList, NameStr);
 }
 
 GetElementPtrInst::GetElementPtrInst(Type *PointeeType, Value *Ptr,
-                                     ArrayRef<Value *> IdxList, unsigned Values,
+                                     ArrayRef<Value *> IdxList, unsigned NumOps,
                                      const Twine &NameStr,
                                      BasicBlock *InsertAtEnd)
     : Instruction(getGEPReturnType(PointeeType, Ptr, IdxList), GetElementPtr,
-                  OperandTraits<GetElementPtrInst>::op_end(this) - Values,
-                  Values, InsertAtEnd),
+                  OperandTraits<GetElementPtrInst>::op_end(this) - NumOps,
+                  NumOps, InsertAtEnd),
       SourceElementType(PointeeType),
       ResultElementType(getIndexedType(PointeeType, IdxList)) {
   assert(cast<PointerType>(getType()->getScalarType())
              ->isOpaqueOrPointeeTypeMatches(ResultElementType));
   init(Ptr, IdxList, NameStr);
 }
 
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrInst, Value)

llvm/include/llvm/IR/Operator.h

public:
   /// Test whether this is an inbounds GEP, as defined by LangRef.html.
   bool isInBounds() const {
     return SubclassOptionalData & IsInBounds;
   }
 
   /// Returns the offset of the index with an inrange attachment, or None if
   /// none.
   Optional<unsigned> getInRangeIndex() const {
+    // FIXME: GetElementPtrInst support.
     if (SubclassOptionalData >> 1 == 0) return None;
     return (SubclassOptionalData >> 1) - 1;
   }
 
   inline op_iterator       idx_begin()       { return op_begin()+1; }
   inline const_op_iterator idx_begin() const { return op_begin()+1; }
   inline op_iterator       idx_end()         { return op_end(); }
   inline const_op_iterator idx_end()   const { return op_end(); }

llvm/lib/Analysis/ValueTracking.cpp

static bool canCreateUndefOrPoison(const Operator *Op, bool PoisonOnly,
   case Instruction::ExtractValue:
   case Instruction::InsertValue:
   case Instruction::Freeze:
   case Instruction::ICmp:
   case Instruction::FCmp:
     return false;
   case Instruction::GetElementPtr:
     // inbounds is handled above
-    // TODO: what about inrange on constexpr?
+    // TODO: what about inrange?
     return false;
   default: {
     const auto *CE = dyn_cast<ConstantExpr>(Op);
     if (isa<CastInst>(Op) || (CE && CE->isCast()))
       return false;
     else if (Instruction::isBinaryOp(Opcode))
       return false;
     // Be conservative and return true.

llvm/lib/AsmParser/LLParser.cpp

return error(
         ExplicitTypeLoc,
         typeComparisonErrorMessage(
             "explicit pointee type doesn't match operand's pointee type", Ty,
             BasePointerType->getElementType()));
   }
 
   SmallVector<Value*, 16> Indices;
   bool AteExtraComma = false;
+  SmallVector<unsigned> InRangeIndices;
   // GEP returns a vector of pointers if at least one of parameters is a vector.
   // All vector parameters should have the same vector width.
   ElementCount GEPWidth = BaseType->isVectorTy()
                               ? cast<VectorType>(BaseType)->getElementCount()
                               : ElementCount::getFixed(0);
 
   while (EatIfPresent(lltok::comma)) {
     if (Lex.getKind() == lltok::MetadataVar) {
       AteExtraComma = true;
       break;
     }
+    if (EatIfPresent(lltok::kw_inrange))
+      InRangeIndices.emplace_back(Indices.size());
     if (parseTypeAndValue(Val, EltLoc, PFS))
       return true;
     if (!Val->getType()->isIntOrIntVectorTy())
       return error(EltLoc, "getelementptr index must be an integer");
 
     if (auto *ValVTy = dyn_cast<VectorType>(Val->getType())) {
       ElementCount ValNumEl = ValVTy->getElementCount();
       if (GEPWidth != ElementCount::getFixed(0) && GEPWidth != ValNumEl)
int LLParser::parseGetElementPtr(Instruction *&Inst, PerFunctionState &PFS) {
   if (!Indices.empty() && !Ty->isSized(&Visited))
     return error(Loc, "base element of getelementptr must be sized");
 
   if (!GetElementPtrInst::getIndexedType(Ty, Indices))
     return error(Loc, "invalid getelementptr indices");
   Inst = GetElementPtrInst::Create(Ty, Ptr, Indices);
   if (InBounds)
     cast<GetElementPtrInst>(Inst)->setIsInBounds(true);
+  for (unsigned InRangeInRangeIndice : InRangeIndices)
+    cast<GetElementPtrInst>(Inst)->setIsInRange(InRangeInRangeIndice, true);
   return AteExtraComma ? InstExtraComma : InstNormal;
 }
 
 /// parseExtractValue
 ///   ::= 'extractvalue' TypeAndValue (',' uint32)+
 int LLParser::parseExtractValue(Instruction *&Inst, PerFunctionState &PFS) {
   Value *Val; LocTy Loc;
   SmallVector<unsigned, 4> Indices;

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::FUNC_CODE_INST_CAST: {    // CAST: [opval, opty, destty, castopc]
           return error("Invalid cast");
         I = CastInst::Create(CastOp, Op, ResTy);
       }
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_INBOUNDS_GEP_OLD:
     case bitc::FUNC_CODE_INST_GEP_OLD:
-    case bitc::FUNC_CODE_INST_GEP: { // GEP: type, [n x operands]
+    case bitc::FUNC_CODE_INST_GEP: // GEP: inrange, type, [n x operands]
+    case bitc::
+        FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES: // GEP: inrange, n, type, [n+1
+                                                 // x operands, n x inrange]
+    {
       unsigned OpNum = 0;
 
       Type *Ty;
       bool InBounds;
+      Optional<unsigned> NumIndices;
 
-      if (BitCode == bitc::FUNC_CODE_INST_GEP) {
+      if (BitCode == bitc::FUNC_CODE_INST_GEP ||
+          BitCode == bitc::FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES) {
         InBounds = Record[OpNum++];
+        if (BitCode == bitc::FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES)
+          NumIndices = Record[OpNum++];
         Ty = getTypeByID(Record[OpNum++]);
       } else {
         InBounds = BitCode == bitc::FUNC_CODE_INST_INBOUNDS_GEP_OLD;
         Ty = nullptr;
       }
 
       Value *BasePtr;
       if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr))
         return error("Invalid record");
 
       if (!Ty) {
         Ty = cast<PointerType>(BasePtr->getType()->getScalarType())
                  ->getElementType();
       } else if (!cast<PointerType>(BasePtr->getType()->getScalarType())
                       ->isOpaqueOrPointeeTypeMatches(Ty)) {
         return error(
             "Explicit gep type does not match pointee type of pointer operand");
       }
 
       SmallVector<Value*, 16> GEPIdx;
-      while (OpNum != Record.size()) {
+      if (NumIndices)
+        GEPIdx.reserve(*NumIndices);
+
+      auto DoneParsingIndices = [&]() {
+        if (BitCode == bitc::FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES)
+          return GEPIdx.size() == *NumIndices;
+        return OpNum == Record.size();
+      };
+
+      while (!DoneParsingIndices()) {
         Value *Op;
         if (getValueTypePair(Record, OpNum, NextValueNo, Op))
           return error("Invalid record");
         GEPIdx.push_back(Op);
       }
 
       I = GetElementPtrInst::Create(Ty, BasePtr, GEPIdx);
 
       InstructionList.push_back(I);
       if (InBounds)
         cast<GetElementPtrInst>(I)->setIsInBounds(true);
+      if (BitCode == bitc::FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES) {
+        constexpr unsigned NumInRangeBitsPerChunk = 6;
+        unsigned NumInRangeBitChunks =
+            divideCeil(*NumIndices, NumInRangeBitsPerChunk);
+        APInt InRangeIndices(NumInRangeBitsPerChunk * NumInRangeBitChunks, 0);
+        for (unsigned ChunkIndex : seq(0U, NumInRangeBitChunks))
+          InRangeIndices.insertBits(Record[OpNum++],
+                                    NumInRangeBitsPerChunk * ChunkIndex,
+                                    NumInRangeBitsPerChunk);
+        for (unsigned Idx : seq(0U, *NumIndices))
+          if (InRangeIndices[Idx])
+            cast<GetElementPtrInst>(I)->setIsInRange(Idx, true);
+      }
       break;
     }
 
     case bitc::FUNC_CODE_INST_EXTRACTVAL: {
                                        // EXTRACTVAL: [opty, opval, n x indices]
       unsigned OpNum = 0;
       Value *Agg;
       if (getValueTypePair(Record, OpNum, NextValueNo, Agg))

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

enum {
   FUNCTION_INST_UNOP_FLAGS_ABBREV,
   FUNCTION_INST_BINOP_ABBREV,
   FUNCTION_INST_BINOP_FLAGS_ABBREV,
   FUNCTION_INST_CAST_ABBREV,
   FUNCTION_INST_RET_VOID_ABBREV,
   FUNCTION_INST_RET_VAL_ABBREV,
   FUNCTION_INST_UNREACHABLE_ABBREV,
   FUNCTION_INST_GEP_ABBREV,
+  FUNCTION_INST_GEP_WITH_INRANGE_INDICES_ABBREV,
 };
 
 /// Abstract class to manage the bitcode writing, subclassed for each bitcode
 /// file type.
 class BitcodeWriterBase {
 protected:
   /// The stream created and owned by the client.
   BitstreamWriter &Stream;
case Instruction::FNeg: {
     if (Flags != 0) {
       if (AbbrevToUse == FUNCTION_INST_UNOP_ABBREV)
         AbbrevToUse = FUNCTION_INST_UNOP_FLAGS_ABBREV;
       Vals.push_back(Flags);
     }
     break;
   }
   case Instruction::GetElementPtr: {
+    auto &GEPInst = cast<GetElementPtrInst>(I);
+    constexpr unsigned NumInRangeBitsPerChunk = 6;
+    unsigned NumInRangeChunks =
+        divideCeil(GEPInst.getNumIndices(), NumInRangeBitsPerChunk);
+    APInt InRangeIndices(NumInRangeBitsPerChunk * NumInRangeChunks, 0);
+    bool HadInRangeIndices = false;
+    for (unsigned Idx : seq(0U, GEPInst.getNumIndices()))
+      if (GEPInst.isInRange(Idx)) {
+        InRangeIndices.setBit(Idx);
+        HadInRangeIndices |= true;
+      }
+    if (HadInRangeIndices) {
+      Code = bitc::FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES;
+      AbbrevToUse = FUNCTION_INST_GEP_WITH_INRANGE_INDICES_ABBREV;
+    } else {
       Code = bitc::FUNC_CODE_INST_GEP;
       AbbrevToUse = FUNCTION_INST_GEP_ABBREV;
-    auto &GEPInst = cast<GetElementPtrInst>(I);
+    }
     Vals.push_back(GEPInst.isInBounds());
+    if (HadInRangeIndices)
+      Vals.push_back(GEPInst.getNumIndices());
     Vals.push_back(VE.getTypeID(GEPInst.getSourceElementType()));
     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
       pushValueAndType(I.getOperand(i), InstID, Vals);
+    if (HadInRangeIndices) {
+      for (unsigned InRangeChunkIndex : seq(0U, NumInRangeChunks))
+        Vals.push_back(InRangeIndices.extractBitsAsZExtValue(
+            NumInRangeBitsPerChunk,
+            NumInRangeBitsPerChunk * InRangeChunkIndex));
+    }
     break;
   }
   case Instruction::ExtractValue: {
     Code = bitc::FUNC_CODE_INST_EXTRACTVAL;
     pushValueAndType(I.getOperand(0), InstID, Vals);
     const ExtractValueInst *EVI = cast<ExtractValueInst>(&I);
     Vals.append(EVI->idx_begin(), EVI->idx_end());
     break;
// FIXME: This should only use space for first class types!
     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_UNREACHABLE));
     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID, Abbv) !=
         FUNCTION_INST_UNREACHABLE_ABBREV)
       llvm_unreachable("Unexpected abbrev ordering!");
   }
   {
     auto Abbv = std::make_shared<BitCodeAbbrev>();
     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_GEP));
-    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // inrange
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, // dest ty
                               Log2_32_Ceil(VE.getTypes().size() + 1)));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID, Abbv) !=
         FUNCTION_INST_GEP_ABBREV)
       llvm_unreachable("Unexpected abbrev ordering!");
   }
+  {
+    auto Abbv = std::make_shared<BitCodeAbbrev>();
+    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_GEP_WITH_INRANGE_INDICES));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // inrange
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // num indices
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,      // dest ty
+                              Log2_32_Ceil(VE.getTypes().size() + 1)));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
+    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID, Abbv) !=
+        FUNCTION_INST_GEP_WITH_INRANGE_INDICES_ABBREV)
+      llvm_unreachable("Unexpected abbrev ordering!");
+  }
 
   Stream.ExitBlock();
 }
 
 /// Write the module path strings, currently only used when generating
 /// a combined index file.
 void IndexBitcodeWriter::writeModStrings() {
   Stream.EnterSubblock(bitc::MODULE_STRTAB_BLOCK_ID, 3);

llvm/lib/IR/AsmWriter.cpp

if (isa<BranchInst>(I) && cast<BranchInst>(I).isConditional()) {
     if (!PrintAllTypes) {
       Out << ' ';
       TypePrinter.print(TheType, Out);
     }
 
     Out << ' ';
     for (unsigned i = 0, E = I.getNumOperands(); i != E; ++i) {
       if (i) Out << ", ";
+      if (const auto *GEP = dyn_cast<GetElementPtrInst>(&I))
+        if (i && GEP->isInRange(i - 1))
+          Out << "inrange ";
       writeOperand(I.getOperand(i), PrintAllTypes);
     }
   }
 
   // Print atomic ordering/alignment for memory operations
   if (const LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     if (LI->isAtomic())
       writeAtomic(LI->getContext(), LI->getOrdering(), LI->getSyncScopeID());

llvm/lib/IR/Instruction.cpp

void Instruction::dropPoisonGeneratingFlags() {
 
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::AShr:
   case Instruction::LShr:
     cast<PossiblyExactOperator>(this)->setIsExact(false);
     break;
 
-  case Instruction::GetElementPtr:
-    cast<GetElementPtrInst>(this)->setIsInBounds(false);
+  case Instruction::GetElementPtr: {
+    auto *GEPI = cast<GetElementPtrInst>(this);
+    GEPI->setIsInBounds(false);
+    for (unsigned Idx : seq(0U, GEPI->getNumIndices()))
+      GEPI->setIsInRange(Idx, false);
     break;
   }
+  }
   // TODO: FastMathFlags!
 
   assert(!hasPoisonGeneratingFlags() && "must be kept in sync");
 }
 
 void Instruction::dropUndefImplyingAttrsAndUnknownMetadata(
     ArrayRef<unsigned> KnownIDs) {
   dropUnknownNonDebugMetadata(KnownIDs);
void Instruction::copyIRFlags(const Value *V, bool IncludeWrapFlags) {
   // Copy the fast-math flags.
   if (auto *FP = dyn_cast<FPMathOperator>(V))
     if (isa<FPMathOperator>(this))
       copyFastMathFlags(FP->getFastMathFlags());
 
   if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(V))
     if (auto *DestGEP = dyn_cast<GetElementPtrInst>(this))
       DestGEP->setIsInBounds(SrcGEP->isInBounds() || DestGEP->isInBounds());
+  // FIXME: What about `inrange`?
 }
 
 void Instruction::andIRFlags(const Value *V) {
   if (auto *OB = dyn_cast<OverflowingBinaryOperator>(V)) {
     if (isa<OverflowingBinaryOperator>(this)) {
       setHasNoSignedWrap(hasNoSignedWrap() && OB->hasNoSignedWrap());
       setHasNoUnsignedWrap(hasNoUnsignedWrap() && OB->hasNoUnsignedWrap());
     }
if (isa<FPMathOperator>(this)) {
       FM &= FP->getFastMathFlags();
       copyFastMathFlags(FM);
     }
   }
 
   if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(V))
     if (auto *DestGEP = dyn_cast<GetElementPtrInst>(this))
       DestGEP->setIsInBounds(SrcGEP->isInBounds() && DestGEP->isInBounds());
+  // FIXME: What about `inrange`?
 }
 
 const char *Instruction::getOpcodeName(unsigned OpCode) {
   switch (OpCode) {
   // Terminators
   case Ret:    return "ret";
   case Br:     return "br";
   case Switch: return "switch";
const char *Instruction::getOpcodeName(unsigned OpCode) {
   case Freeze:         return "freeze";
 
   default: return "<Invalid operator> ";
   }
 }
 
 /// Return true if both instructions have the same special state. This must be
 /// kept in sync with FunctionComparator::cmpOperations in
-/// lib/Transforms/IPO/MergeFunctions.cpp.
+/// lib/Transforms/Utils/FunctionComparator.cpp.
 static bool haveSameSpecialState(const Instruction *I1, const Instruction *I2,
                                  bool IgnoreAlignment = false) {
   assert(I1->getOpcode() == I2->getOpcode() &&
          "Can not compare special state of different instructions");
 
   if (const AllocaInst *AI = dyn_cast<AllocaInst>(I1))
     return AI->getAllocatedType() == cast<AllocaInst>(I2)->getAllocatedType() &&
            (AI->getAlignment() == cast<AllocaInst>(I2)->getAlignment() ||
static bool haveSameSpecialState(const Instruction *I1, const Instruction *I2,
   if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I1))
     return RMWI->getOperation() == cast<AtomicRMWInst>(I2)->getOperation() &&
            RMWI->isVolatile() == cast<AtomicRMWInst>(I2)->isVolatile() &&
            RMWI->getOrdering() == cast<AtomicRMWInst>(I2)->getOrdering() &&
            RMWI->getSyncScopeID() == cast<AtomicRMWInst>(I2)->getSyncScopeID();
   if (const ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I1))
     return SVI->getShuffleMask() ==
            cast<ShuffleVectorInst>(I2)->getShuffleMask();
+  if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I1)) {
+    const GetElementPtrInst *OtherGEPI = cast<GetElementPtrInst>(I2);
+    for (unsigned Idx : seq(0U, GEPI->getNumIndices()))
+      if (GEPI->isInRange(Idx) != OtherGEPI->isInRange(Idx))
+        return false;
+    return true;
+  }
 
   return true;
 }
 
 bool Instruction::isIdenticalTo(const Instruction *I) const {
   return isIdenticalToWhenDefined(I) &&
          SubclassOptionalData == I->SubclassOptionalData;
 }
if (const PHINode *thisPHI = dyn_cast<PHINode>(this)) {
     return std::equal(thisPHI->block_begin(), thisPHI->block_end(),
                       otherPHI->block_begin());
   }
 
   return haveSameSpecialState(this, I);
 }
 
 // Keep this in sync with FunctionComparator::cmpOperations in
-// lib/Transforms/IPO/MergeFunctions.cpp.
+// lib/Transforms/Utils/FunctionComparator.cpp.
 bool Instruction::isSameOperationAs(const Instruction *I,
                                     unsigned flags) const {
   bool IgnoreAlignment = flags & CompareIgnoringAlignment;
   bool UseScalarTypes  = flags & CompareUsingScalarTypes;
 
   if (getOpcode() != I->getOpcode() ||
       getNumOperands() != I->getNumOperands() ||
       (UseScalarTypes ?

llvm/lib/IR/Instructions.cpp

GetElementPtrInst::GetElementPtrInst(const GetElementPtrInst &GEPI)
     : Instruction(GEPI.getType(), GetElementPtr,
                   OperandTraits<GetElementPtrInst>::op_end(this) -
                       GEPI.getNumOperands(),
                   GEPI.getNumOperands()),
       SourceElementType(GEPI.SourceElementType),
       ResultElementType(GEPI.ResultElementType) {
   std::copy(GEPI.op_begin(), GEPI.op_end(), op_begin());
   SubclassOptionalData = GEPI.SubclassOptionalData;
+  setSubclassData<SubclassDataInlineBits>(
+      GEPI.getSubclassData<SubclassDataInlineBits>());
+  std::copy(GEPI.trailing_obj_end(), GEPI.trailing_obj_end(),
+            trailing_obj_end());
 }
 
 Type *GetElementPtrInst::getTypeAtIndex(Type *Ty, Value *Idx) {
   if (auto *Struct = dyn_cast<StructType>(Ty)) {
     if (!Struct->indexValid(Idx))
       return nullptr;
     return Struct->getTypeAtIndex(Idx);
   }

 void GetElementPtrInst::setIsInBounds(bool B) {
   cast<GEPOperator>(this)->setIsInBounds(B);
 }
 
 bool GetElementPtrInst::isInBounds() const {
   return cast<GEPOperator>(this)->isInBounds();
 }
 
+void GetElementPtrInst::setIsInRange(unsigned Idx, bool b) {
+  assert(Idx < getNumIndices() && "Must be a valid index for this GEP!");
+
+  auto Update = [b, Idx](auto &Storage) {
+    if (b) // Set bit Idx
+      Storage |= (1U << Idx);
+    else // Keep all bits except bit Idx
+      Storage &= ~(1U << Idx);
+  };
+
+  auto HandleInlineStorage = [&](auto InlineStorage) {
+    using InlineStorageTy = decltype(InlineStorage);
+    if (Idx <= InlineStorageTy::Bits) {
+      auto Storage = getSubclassData<InlineStorageTy>();
+      Update(Storage);
+      setSubclassData<InlineStorageTy>(Storage);
+      return true;
+    }
+    Idx -= InlineStorageTy::Bits;
+    return false;
+  };
+
+  if (HandleInlineStorage(SubclassOptionalDataInlineBits{}))
+    return;
+  if (HandleInlineStorage(SubclassDataInlineBits{}))
+    return;
+
+  // In which trailing object does this bit reside?
+  unsigned TrailingObjectIndex = Idx / NumBitsPerTrailingObject;
+  uintptr_t &Storage = trailing_obj_begin()[TrailingObjectIndex];
+  // And which bit in that trailing object is that?
+  Idx %= NumBitsPerTrailingObject;
+  Update(Storage);
+}
+
+bool GetElementPtrInst::isInRange(unsigned Idx) const {
+  assert(Idx < getNumIndices() && "Must be a valid index for this GEP!");
+
+  auto Test = [Idx](auto Storage) { return Storage & (1U << Idx); };
+
+  auto HandleInlineStorage = [&](auto InlineStorage) -> Optional<bool> {
+    using InlineStorageTy = decltype(InlineStorage);
+    if (Idx <= InlineStorageTy::Bits) {
+      auto Storage = getSubclassData<InlineStorageTy>();
+      return Test(Storage);
+    }
+    Idx -= InlineStorageTy::Bits;
+    return None;
+  };
+
+  if (auto Res = HandleInlineStorage(SubclassOptionalDataInlineBits{}))
+    return *Res;
+  if (auto Res = HandleInlineStorage(SubclassDataInlineBits{}))
+    return *Res;
+
+  // In which trailing object does this bit reside?
+  unsigned TrailingObjectIndex = Idx / NumBitsPerTrailingObject;
+  uintptr_t TrailingObject = trailing_obj_begin()[TrailingObjectIndex];
+  // And which bit in that trailing object is that?
+  Idx %= NumBitsPerTrailingObject;
+  // Is bit Idx set in the trailing object?
+  return TrailingObject & (1U << Idx);
+}
+
 bool GetElementPtrInst::accumulateConstantOffset(const DataLayout &DL,
                                                  APInt &Offset) const {
   // Delegate to the generic GEPOperator implementation.
   return cast<GEPOperator>(this)->accumulateConstantOffset(DL, Offset);
 }
 
 bool GetElementPtrInst::collectOffset(
     const DataLayout &DL, unsigned BitWidth,

 //===----------------------------------------------------------------------===//
 //                           cloneImpl() implementations
 //===----------------------------------------------------------------------===//
 
 // Define these methods here so vtables don't get emitted into every translation
 // unit that uses these classes.
 
 GetElementPtrInst *GetElementPtrInst::cloneImpl() const {
-  return new (getNumOperands()) GetElementPtrInst(*this);
+  return new (getNumOperands() + getNumTrailingObjects())
+      GetElementPtrInst(*this);
 }
 
 UnaryOperator *UnaryOperator::cloneImpl() const {
   return Create(getOpcode(), Op<0>());
 }
 
 BinaryOperator *BinaryOperator::cloneImpl() const {
   return Create(getOpcode(), Op<0>(), Op<1>());

llvm/lib/IR/Operator.cpp

bool Operator::hasPoisonGeneratingFlags() const {
   }
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::AShr:
   case Instruction::LShr:
     return cast<PossiblyExactOperator>(this)->isExact();
   case Instruction::GetElementPtr: {
     auto *GEP = cast<GEPOperator>(this);
-    // Note: inrange exists on constexpr only
-    return GEP->isInBounds() || GEP->getInRangeIndex() != None;
+    if (GEP->isInBounds())
+      return true;
+    if (isa<ConstantExpr>(this))
+      return GEP->getInRangeIndex() != None;
+    auto *GEPI = dyn_cast<GetElementPtrInst>(this);
+    for (unsigned Idx : seq(0U, GEPI->getNumIndices()))
+      if (GEPI->isInRange(Idx))
+        return true;
+    return false;
   }
   default:
     return false;
   }
   // TODO: FastMathFlags!  (On instructions, but not constexpr)
 }
 
 Type *GEPOperator::getSourceElementType() const {

llvm/test/Assembler/getelementptr.ll

 
 ; Verify that array GEP doesn't incorrectly infer inbounds.
 define i32* @test9() {
 entry:
   ret i32* getelementptr ([16 x i32], [16 x i32]* @array, i64 0, i64 -13)
 ; CHECK-LABEL: define i32* @test9(
 ; CHECK: ret i32* getelementptr ([16 x i32], [16 x i32]* @array, i64 0, i64 -13)
 }
+
+; Verity that inrange on indices is handled correctly.
+define void @test10({ { { i32 } } } *%a) {
+; CHECK-LABEL: define void @test10(
+; CHECK:   %v0  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0,         i32 0,         i32 0
+; CHECK:   %v1  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0,         i32 0,         i32 0
+; CHECK:   %v2  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0, inrange i32 0,         i32 0,         i32 0
+; CHECK:   %v3  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0, inrange i32 0,         i32 0
+; CHECK:   %v4  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0,         i32 0, inrange i32 0
+; CHECK:   %v5  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0, inrange i32 0,         i32 0,         i32 0
+; CHECK:   %v6  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0, inrange i32 0,         i32 0
+; CHECK:   %v7  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0,         i32 0, inrange i32 0
+; CHECK:   %v8  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0,         i32 0, inrange i32 0
+; CHECK:   %v9  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0, inrange i32 0,         i32 0, inrange i32 0
+; CHECK:   %v10 = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0, inrange i32 0, inrange i32 0
+
+  %v0  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0,         i32 0,         i32 0
+
+  %v1  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0,         i32 0,         i32 0
+  %v2  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0, inrange i32 0,         i32 0,         i32 0
+  %v3  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0, inrange i32 0,         i32 0
+  %v4  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0,         i32 0, inrange i32 0
+
+  %v5  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0, inrange i32 0,         i32 0,         i32 0
+  %v6  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0, inrange i32 0,         i32 0
+  %v7  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0,         i32 0, inrange i32 0
+
+  %v8  = getelementptr { { { i32 } } }, { { { i32 } } }* %a, inrange i32 0,         i32 0,         i32 0, inrange i32 0
+  %v9  = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0, inrange i32 0,         i32 0, inrange i32 0
+  %v10 = getelementptr { { { i32 } } }, { { { i32 } } }* %a,         i32 0,         i32 0, inrange i32 0, inrange i32 0
+
+  ret void
+}