IR: Introduce inbounds attribute on getelementptr indices.

[pcc]

Summary

If the inbounds keyword is present before any index, loading from or
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 inbounds.

This can be used, e.g. for alias analysis or to split globals at element
boundaries where beneficial.

As previously proposed on llvm-dev:
http://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html

[majnemer]

Seeing as how this doesn't have to do with the original inbounds attribute, perhaps we should call it something else?
Maybe inrange or withinrange? Not sure...

[mehdi_amini]

Will this play well with GetUnderlyingObject? Aren't we using it in some places to rewrite the memory accesses? Will this feature be intrusive in all the code that deal with GEP and memory accesses to honor/preserve this "inbound"?

[pcc]

I think my concern with a separate keyword was that it would essentially need to be a synonym of inbounds in order to be descriptive, and I generally prefer not to use synonyms to refer to different things, as that can be confusing. But maybe using the same keyword would be even more confusing, and perhaps the overriding concern here should be searchability in langref. With that considered, I think I'm ok with inrange.

[pcc]

Will this play well with GetUnderlyingObject? Aren't we using it in some places to rewrite the memory accesses?

That should be fine. If we do end up splitting an object, the underlying object will change, but by the rules of this annotation, that change would be unobservable.

Will this feature be intrusive in all the code that deal with GEP and memory accesses to honor/preserve this "inbound"?

Passes are free to discard this annotation, it's similar to metadata in that way.

[majnemer]

I think you need to update andIRFlags.

include/llvm/IR/Operator.h

384–387 ↗

(On Diff #65454)

How will this play with intersectOptionalDataWith?

[eli.friedman]

(I'll refer to the new attribute as inrange to try to avoid confusion.)

Does the way you're using subclass data mean that GVN just works correctly without any additional changes? Or does it need to be modified to avoid unifying a non-inrange GEP with an inrange GEP?

inrange markings probably interact badly with certain existing optimizations; for example, a gep with all zero indexes plus a bitcast currently gets folded into just a bitcast, but that loses the inrange marking. Not a correctness problem, but it'll probably be difficult to fix the resulting missed optimizations.

We'll probably have to be extremely cautious in terms of how we actually use inrange in clang. Applying inrange to a computation like "&p->a" is theoretically allowed by the C standard, but likely to cause problems in practice. Specifically, we could end up breaking programs without any good way to find the problem. Existing tools like valgrind and asan can't detect this sort of issue at all. That's more of a question of what makes sense for clang rather than something which affects the attribute itself... but if clang can't really use inrange markings outside of vtables, that reduces the utility a lot.

[pcc]

Does the way you're using subclass data mean that GVN just works correctly without any additional changes? Or does it need to be modified to avoid unifying a non-inrange GEP with an inrange GEP?

If we allow this attribute on instructions, we would need to modify andIRFlags to recognize the new attribute, as David mentioned. At the moment, we only allow it on constants (I will document this more clearly).

inrange markings probably interact badly with certain existing optimizations; for example, a gep with all zero indexes plus a bitcast currently gets folded into just a bitcast, but that loses the inrange marking.

That specific fold is one that I inhibited, see lib/IR/ConstantFold.cpp, line 551.

Not a correctness problem, but it'll probably be difficult to fix the resulting missed optimizations.

While working on this patch I did try to identify any missed optimizations specific to vtables by hacking in some code like this:

diff --git a/lib/IR/Constants.cpp b/lib/IR/Constants.cpp
index 1fbd75f..1d445ff 100644
--- a/lib/IR/Constants.cpp
+++ b/lib/IR/Constants.cpp
@@ -1940,6 +1940,13 @@ Constant *ConstantExpr::getGetElementPtr(Type *Ty, Constant *C,
     ArgVec.push_back(Idx);
   }
 
+#if 0
+  if (isa<GlobalVariable>(C) && C->getName().startswith("_ZTV") &&
+      C->getName().find("type_info") == StringRef::npos &&
+      (!InBoundsIndex || *InBoundsIndex != 1))
+    abort();
+#endif
+
   unsigned SubClassOptionalData = InBounds ? GEPOperator::IsInBounds : 0;
   if (InBoundsIndex && *InBoundsIndex < 63)
     SubClassOptionalData |= (*InBoundsIndex + 1) << 1;

The constant folding changes I made in this patch were sufficient to be able to compile Chromium on Linux without aborting (with the above code turned on) and without a regression in binary size.

I'm not sure if there's a better way in general to track missed optimizations.

That's more of a question of what makes sense for clang rather than something which affects the attribute itself... but if clang can't really use inrange markings outside of vtables, that reduces the utility a lot.

You have a point there, but I'd expect that frontends for more memory safe languages may be able to make more extensive use of this attribute than clang.

[mehdi_amini]

In D22793#496473, @pcc wrote:

Passes are free to discard this annotation, it's similar to metadata in that way.

Oh, that wasn't clear to me.

In D22793#496512, @eli.friedman wrote:

We'll probably have to be extremely cautious in terms of how we actually use inrange in clang. Applying inrange to a computation like "&p->a" is theoretically allowed by the C standard, but likely to cause problems in practice. Specifically, we could end up breaking programs without any good way to find the problem. Existing tools like valgrind and asan can't detect this sort of issue at all. That's more of a question of what makes sense for clang rather than something which affects the attribute itself... but if clang can't really use inrange markings outside of vtables, that reduces the utility a lot.

Isn't it similar to TBBA? What kind of extra problem do you anticipate?
You may be able to chime in on this related thread on llvm-dev currently: https://groups.google.com/forum/#!topic/llvm-dev/Lc8POEocCX8

[eli.friedman]

It's similar to TBAA, I guess... TBAA tends to cause problems too; fno-strict-aliasing is popular for a reason. :)

[pcc]

I think you need to update andIRFlags.

Because this attribute is not currently supported on instructions, we don't need to do that yet.

include/llvm/IR/Operator.h

384–387 ↗

(On Diff #65454)

We discussed this on IRC and concluded that we can remove that function (D22830).

[pcc]

• Rename inbounds -> inrange

[pcc]

• Add language to langref forbidding certain pointer comparisons involving inrange GEPs

[hfinkel]

In D22793#496751, @eli.friedman wrote:

It's similar to TBAA, I guess... TBAA tends to cause problems too; fno-strict-aliasing is popular for a reason. :)

I think we should follow the same approach here. Just like with TBAA, and with nsw on integer operations, we produce the flag when possible, and add a command-line option to turn it off.

[hfinkel]

docs/LangRef.rst

7551 ↗

(On Diff #65626)

I don't think we should limit this to constant expressions. We should be able to use this to model p.x[i] vs. p.y. Removing the restriction to constant expressions will also mean you need to generalize the text about pointer comparisons: instead of saying that all operands must be identical, you'll need to say that the same elements need to be selected (or something like that).

include/llvm/IR/Operator.h

382 ↗

(On Diff #65626)

Can more than once index have inrange on it? It looks like no, but this is not clear from the LangRef, and I don't understand that restriction regardless.

[majnemer]

docs/LangRef.rst

7546–7549 ↗

(On Diff #65626)

What if I do a ptrtoint and compare the ints?

[pcc]

docs/LangRef.rst

7546–7549 ↗

(On Diff #65626)

Yes, good point. "pointer comparison" can just become "comparison" then, I think.

7551 ↗

(On Diff #65626)

Seems reasonable enough, but I'm not sure if I'll have any time soon to implement this for non-constants. Perhaps the non-constant implementation can be a separate patch.

include/llvm/IR/Operator.h

382 ↗

(On Diff #65626)

No more than one. The rationale is that inrange on a given index will be at least as restrictive as inrange on any earlier index, so there's no point in allowing more than one. I'll document this in the langref.

[hfinkel]

docs/LangRef.rst

7551 ↗

(On Diff #65626)

Aside from the LangRef, what needs to change to allow non-constant indicies? I think they should be allowed, even if taking advantage of them is future work. I don't see anything in the parser changes that forbids them.

[pcc]

docs/LangRef.rst

7551 ↗

(On Diff #65626)

We would need printing and parsing support, as well as a bitcode representation for getelementptr instructions (as opposed to only constants) with an inrange annotation. Should be straightforward, but a non-zero amount of work.

[hfinkel]

docs/LangRef.rst

7551 ↗

(On Diff #65626)

Ah, so it only applies to constants right now, not to actual GEP instructions. I see what you mean now, but when I originally read the text, I thought that you meant that the index expression needed to be constant, not that the entire GEP needed to be a constant.

[sanjoy]

docs/LangRef.rst

7550 ↗

(On Diff #65626)

This is a little odd since (IIUC) it implies that replacing an inrange GEP with a not inrange version of the same GEP can introduce undefined behavior; that is:

x0 = gep_inrange(A, 42)
x1 = gep_normal(A, 42)
result = x0 == x0 ;; perhaps hidden behind a function

to

x0 = gep_inrange(A, 42)
x1 = gep_normal(A, 42)
result = x0 == y0 ;; perhaps hidden behind a function

via x1->replaceAllUsesWith(x0).

Why do you need this property / caveat?

7551 ↗

(On Diff #65626)

Given that, it is probably better to say "allowed in constant getelementptr expressions"

[eli.friedman]

docs/LangRef.rst

7548 ↗

(On Diff #65626)

Hmm... this sort of restricts the possible uses of the marking. For example, given:

struct X {
    int x, y[2];
};
int f(struct X *x, int i) { return x->y[i]; }
int *f2(struct X *x) { return x->y; }

We can mark the GEP in x->y[i] inrange, but we can't mark the GEP in x->y inrange because it could be used in a pointer comparison. I guess that's okay (the stated form is convenient for performing SROA). That said, inevitably someone is going to push for a version which doesn't make comparisons undefined so it can be used more aggressively in C code.

You should probably state explicitly that the result of converting an inrange pointer to an integer is undef; you can't actually do anything useful with the result anyway.

[sanjoy]

docs/LangRef.rst

7550 ↗

(On Diff #65626)

There's a typo, in the transformed snippet we should have result = x0 == x1. Also pretend that there are other uses of x1 (so it isn't trivially DCE'ed away).

[hfinkel]

docs/LangRef.rst

7548 ↗

(On Diff #65626)

What's the motivation for the current language? I don't think we can have anything that strict.

[eli.friedman]

docs/LangRef.rst

7547 ↗

(On Diff #65626)

I think this is supposed to be "if both operands were derived from an inrange GEP"?

7548 ↗

(On Diff #65626)

The motivation here is that we want to be able to say "if every use of a given global is an inrange GEP, SROA is legal (i.e. we can split the global)". That requires some sort of restriction on comparisons because we could change the result of a comparison in an unpredictable way.

[pcc]

docs/LangRef.rst

7548 ↗

(On Diff #65626)

The intent was to allow optimization passes to re-arrange elements of an indexed object (i.e. what SplitGlobals does). Although at this point it does seem that trying to restrict pointer comparisons in general would be likely to make this too restrictive for use by C family frontends. Instead I think the best approach would be to change SplitGlobals to check for the unnamed_addr attribute, and remove the pointer comparison language here.

You should probably state explicitly that the result of converting an inrange pointer to an integer is undef;

Will do.

7550 ↗

(On Diff #65626)

I think this is moot in light of my other comment.

7551 ↗

(On Diff #65626)

Will do

[hfinkel]

docs/LangRef.rst

7548 ↗

(On Diff #65626)

I'd think that we just need to check the use-def chains, starting with uses of the global, to see if the address was captured.

[pcc]

docs/LangRef.rst

7548 ↗

(On Diff #65626)

The problem with that, at least for vtables, is that the vtable address will be captured in most normal cases (e.g. the constructor will store the vtable address in the object's vtable pointer). So for split globals I think we need to rely on unnamed_addr here.

[hfinkel]

docs/LangRef.rst

7548 ↗

(On Diff #65626)

That makes sense.

[pcc]

• Remove pointer comparison language. Explicitly forbid ptrtoint. Clarify language related to constant expressions.

[hfinkel]

In D22793#497101, @pcc wrote:

• Remove pointer comparison language. Explicitly forbid ptrtoint. Clarify language related to constant expressions.

If we're relying on unnamed_addr, why do you need to forbid ptrtoint?

[pcc]

On second thoughts, that restriction doesn't seem necessary, so I've removed it.

[pcc]

• Remove ptrtoint restriction

[delena]

I think that "inrange" mark for non-constant indices will help to handle x.y[i] cases. Do you plan to cover non-constant indices?

[pete]

include/llvm/IR/Operator.h

382 ↗

(On Diff #65651)

Sorry to come late to this one...

My read on this implies that inrange on the start of a GEP would be equivalent to inbounds today. Is that the case?

Assuming it is, the inrange is strictly a more accurate version of inbounds, and we should only have inrange. Put another way, keep the name inbounds, but allow it to be applied to any single type in the GEP.

So that would make all of these equivalent in terms of AA, and all of these alias each other:

%arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2
%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 1, i32 2
%arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, inbounds i32 2

But these won't alias because the inbounds applies to an index with a different value:

%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 0, i32 2
%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 1, i32 2

And these will alias because one has inbounds and the other doesn't:

%arrayidx = getelementptr %struct.ST, %struct.ST* %s, i64 0, i32 2
%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 1, i32 2

[pcc]

Apologies for the delayed response, I just returned from a long vacation.

include/llvm/IR/Operator.h

382 ↗

(On Diff #65651)

My read on this implies that inrange on the start of a GEP would be equivalent to inbounds today. Is that the case?

No. The inbounds keyword is a bounds restriction with regard to the allocated object, while inrange on the start of the GEP is a bounds restriction with regard to the GEP element type (or subelement type). The inrange restriction also applies to any pointers derived from the inrange GEP, while this isn't the case for inbounds. So, for example if you have an allocated object of type [2 x %struct.ST] and a pointer %s referring to its first element, and the instructions

%i1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 0
%i2 = getelementptr %struct.ST, %struct.ST* %s, inrange i64 0

the instruction

%i1a = getelementptr %struct.ST, %struct.ST* %i1, i64 1

would yield a pointer to the second element of the allocated object but the instruction

%i2a = getelementptr %struct.ST, %struct.ST* %i2, i64 1

would yield an undefined value.

[pcc]

• Forbid pointer comparison and ptrtoint as discussed

[mehdi_amini]

docs/LangRef.rst

7549 ↗

(On Diff #70625)

Isn't it hard to guarantee in face of transformations?

Let say a pass would do outlining, passing the pointer derived from the GEP by argument, in this new function the inrange information would be lost and another transformation allowed to introduce a pointer comparison.

[pcc]

docs/LangRef.rst

7549 ↗

(On Diff #70625)

Hrm, yes, I think you're right. It looks like we can't avoid specifying exactly which comparisons are allowable in practice.

Taking into account Sanjoy's point from earlier, I believe this would suffice:

The result of a pointer
comparison or ``ptrtoint`` 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.

[pcc]

Refresh; incorporate my suggested wording change

[pcc]

Ping.

[efriedma]

I haven't reviewed the assembly and bitcode reading/writing changes.

The semantics here look right.

llvm/docs/LangRef.rst

7578 ↗

(On Diff #75491)

Might want to clarify that this includes ptrtoint-like operations involving memory.

llvm/include/llvm/IR/Operator.h

386 ↗

(On Diff #75491)

Please add a comment somewhere describing exactly how many bits are dedicated to InRangeIndex.

llvm/lib/Analysis/ConstantFolding.cpp

950 ↗

(On Diff #75491)

Should we preserve inbounds here? (Please add a FIXME if it's complicated somehow.)

970 ↗

(On Diff #75491)

Does this patch affect this TODO somehow?

llvm/lib/IR/ConstantFold.cpp

551 ↗

(On Diff #75491)

This is a little awkward... but I don't really see an alternative; it's okay, I guess.

[pcc]

• Address review comments

llvm/lib/Analysis/ConstantFolding.cpp

950 ↗

(On Diff #75491)

My first impression is that it would be sound to preserve inbounds if all GEPs are inbounds, which is what D26441 does. Let's deal with that orthogonally though.

970 ↗

(On Diff #75491)

I guess it would be covered by the "etc" :)

But added to be explicit.

llvm/lib/IR/ConstantFold.cpp

551 ↗

(On Diff #75491)

Right, this should be no longer needed in the typeless pointer world anyway.

[efriedma]

Okay, that addresses my comments. (I haven't tried to review the bitcode/assembly reading/writing changes; I'm hoping you can find someone else to review that.)

[pcc]

@eugenis may I ask you to review the rest of this patch?

[mehdi_amini]

The implementation looks good to me.

include/llvm/IR/Constants.h

1079 ↗

(On Diff #70625)

Update the doxygen.

lib/Analysis/ConstantFolding.cpp

906 ↗

(On Diff #70625)

s/inbounds/inrange/

llvm/trunk/docs/LangRef.rst

 '``getelementptr``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = getelementptr <ty>, <ty>* <ptrval>{, <ty> <idx>}*
-      <result> = getelementptr inbounds <ty>, <ty>* <ptrval>{, <ty> <idx>}*
-      <result> = getelementptr <ty>, <ptr vector> <ptrval>, <vector index type> <idx>
+      <result> = getelementptr <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*
+      <result> = getelementptr inbounds <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*
+      <result> = getelementptr <ty>, <ptr vector> <ptrval>, [inrange] <vector index type> <idx>
 
 Overview:
 """""""""
 
 The '``getelementptr``' instruction is used to get the address of a
 subelement of an :ref:`aggregate <t_aggregate>` data structure. It performs
 address calculation only and does not access memory. The instruction can also
 be used to calculate a vector of such addresses.

 offsets have a different width from the pointer, they are sign-extended
 or truncated to the width of the pointer. The result value of the
 ``getelementptr`` may be outside the object pointed to by the base
 pointer. The result value may not necessarily be used to access memory
 though, even if it happens to point into allocated storage. See the
 :ref:`Pointer Aliasing Rules <pointeraliasing>` section for more
 information.
 
+If the ``inrange`` keyword is present before any index, loading from or
+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.
+
 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/trunk/include/llvm/Bitcode/LLVMBitCodes.h

enum ConstantsCodes {
   CST_CODE_CE_SHUFFLEVEC = 16,   // CE_SHUFFLEVEC: [opval, opval, opval]
   CST_CODE_CE_CMP = 17,          // CE_CMP:        [opty, opval, opval, pred]
   CST_CODE_INLINEASM_OLD = 18,   // INLINEASM:     [sideeffect|alignstack,
                                  //                 asmstr,conststr]
   CST_CODE_CE_SHUFVEC_EX = 19,   // SHUFVEC_EX:    [opty, opval, opval, opval]
   CST_CODE_CE_INBOUNDS_GEP = 20, // INBOUNDS_GEP:  [n x operands]
   CST_CODE_BLOCKADDRESS = 21,    // CST_CODE_BLOCKADDRESS [fnty, fnval, bb#]
   CST_CODE_DATA = 22,            // DATA:          [n x elements]
-  CST_CODE_INLINEASM = 23        // INLINEASM:     [sideeffect|alignstack|
+  CST_CODE_INLINEASM = 23,       // INLINEASM:     [sideeffect|alignstack|
                                  //                 asmdialect,asmstr,conststr]
+  CST_CODE_CE_GEP_WITH_INRANGE_INDEX = 24, //      [opty, flags, n x operands]
 };
 
 /// CastOpcodes - These are values used in the bitcode files to encode which
 /// cast a CST_CODE_CE_CAST or a XXX refers to.  The values of these enums
 /// have no fixed relation to the LLVM IR enum values.  Changing these will
 /// break compatibility with old files.
 enum CastOpcodes {
   CAST_TRUNC = 0,

llvm/trunk/include/llvm/IR/Constants.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_CONSTANTS_H
 #define LLVM_IR_CONSTANTS_H
 
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/OperandTraits.h"
 
 namespace llvm {
 
 class ArrayType;
 class IntegerType;
public:
   static Constant *getICmp(unsigned short pred, Constant *LHS, Constant *RHS,
                            bool OnlyIfReduced = false);
   static Constant *getFCmp(unsigned short pred, Constant *LHS, Constant *RHS,
                            bool OnlyIfReduced = false);
 
   /// Getelementptr form.  Value* is only accepted for convenience;
   /// all elements must be Constants.
   ///
+  /// \param InRangeIndex the inrange index if present or None.
   /// \param OnlyIfReducedTy see \a getWithOperands() docs.
   static Constant *getGetElementPtr(Type *Ty, Constant *C,
                                     ArrayRef<Constant *> IdxList,
                                     bool InBounds = false,
+                                    Optional<unsigned> InRangeIndex = None,
                                     Type *OnlyIfReducedTy = nullptr) {
     return getGetElementPtr(
         Ty, C, makeArrayRef((Value * const *)IdxList.data(), IdxList.size()),
-        InBounds, OnlyIfReducedTy);
+        InBounds, InRangeIndex, OnlyIfReducedTy);
   }
   static Constant *getGetElementPtr(Type *Ty, Constant *C, Constant *Idx,
                                     bool InBounds = false,
+                                    Optional<unsigned> InRangeIndex = None,
                                     Type *OnlyIfReducedTy = nullptr) {
     // This form of the function only exists to avoid ambiguous overload
     // warnings about whether to convert Idx to ArrayRef<Constant *> or
     // ArrayRef<Value *>.
-    return getGetElementPtr(Ty, C, cast<Value>(Idx), InBounds, OnlyIfReducedTy);
+    return getGetElementPtr(Ty, C, cast<Value>(Idx), InBounds, InRangeIndex,
+                            OnlyIfReducedTy);
   }
   static Constant *getGetElementPtr(Type *Ty, Constant *C,
                                     ArrayRef<Value *> IdxList,
                                     bool InBounds = false,
+                                    Optional<unsigned> InRangeIndex = None,
                                     Type *OnlyIfReducedTy = nullptr);
 
   /// Create an "inbounds" getelementptr. See the documentation for the
   /// "inbounds" flag in LangRef.html for details.
   static Constant *getInBoundsGetElementPtr(Type *Ty, Constant *C,
                                             ArrayRef<Constant *> IdxList) {
     return getGetElementPtr(Ty, C, IdxList, true);
   }

llvm/trunk/include/llvm/IR/Operator.h

 
 
 class ZExtOperator : public ConcreteOperator<Operator, Instruction::ZExt> {};
 
 
 class GEPOperator
   : public ConcreteOperator<Operator, Instruction::GetElementPtr> {
   enum {
-    IsInBounds = (1 << 0)
+    IsInBounds = (1 << 0),
+    // InRangeIndex: bits 1-6
   };
 
   friend class GetElementPtrInst;
   friend class ConstantExpr;
   void setIsInBounds(bool B) {
     SubclassOptionalData =
       (SubclassOptionalData & ~IsInBounds) | (B * IsInBounds);
   }
 
 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 {
+    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(); }
 
   Value *getPointerOperand() {
     return getOperand(0);

llvm/trunk/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, const DataLayout &DL,
-                         const TargetLibraryInfo *TLI) {
+                         Type *ResultTy, Optional<unsigned> InRangeIndex,
+                         const DataLayout &DL, const TargetLibraryInfo *TLI) {
   Type *IntPtrTy = DL.getIntPtrType(ResultTy);
 
   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() != IntPtrTy) {
       Any = true;
       NewIdxs.push_back(ConstantExpr::getCast(CastInst::getCastOpcode(Ops[i],
                                                                       true,
                                                                       IntPtrTy,
                                                                       true),
                                               Ops[i], IntPtrTy));
     } else
       NewIdxs.push_back(Ops[i]);
   }
 
   if (!Any)
     return nullptr;
 
-  Constant *C = ConstantExpr::getGetElementPtr(SrcElemTy, Ops[0], NewIdxs);
+  Constant *C = ConstantExpr::getGetElementPtr(
+      SrcElemTy, Ops[0], NewIdxs, /*InBounds=*/false, InRangeIndex);
   if (Constant *Folded = ConstantFoldConstant(C, DL, TLI))
     C = Folded;
 
   return C;
 }
 
 /// Strip the pointer casts, but preserve the address space information.
 Constant* StripPtrCastKeepAS(Constant* Ptr, Type *&ElemTy) {
Constant* StripPtrCastKeepAS(Constant* Ptr, Type *&ElemTy) {
   return Ptr;
 }
 
 /// If we can symbolically evaluate the GEP constant expression, do so.
 Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP,
                                   ArrayRef<Constant *> Ops,
                                   const DataLayout &DL,
                                   const TargetLibraryInfo *TLI) {
+  const GEPOperator *InnermostGEP = GEP;
+
   Type *SrcElemTy = GEP->getSourceElementType();
   Type *ResElemTy = GEP->getResultElementType();
   Type *ResTy = GEP->getType();
   if (!SrcElemTy->isSized())
     return nullptr;
 
-  if (Constant *C = CastGEPIndices(SrcElemTy, Ops, ResTy, DL, TLI))
+  if (Constant *C = CastGEPIndices(SrcElemTy, Ops, ResTy,
+                                   GEP->getInRangeIndex(), DL, TLI))
     return C;
 
   Constant *Ptr = Ops[0];
   if (!Ptr->getType()->isPointerTy())
     return nullptr;
 
   Type *IntPtrTy = DL.getIntPtrType(Ptr->getType());
 
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.
   while (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
+    InnermostGEP = GEP;
+
     SmallVector<Value *, 4> NestedOps(GEP->op_begin() + 1, GEP->op_end());
 
     // Do not try the incorporate the sub-GEP if some index is not a number.
     bool AllConstantInt = true;
     for (Value *NestedOp : NestedOps)
       if (!isa<ConstantInt>(NestedOp)) {
         AllConstantInt = false;
         break;
Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP,
   } while (Ty != ResElemTy);
 
   // If we haven't used up the entire offset by descending the static
   // type, then the offset is pointing into the middle of an indivisible
   // member, so we can't simplify it.
   if (Offset != 0)
     return nullptr;
 
+  // Preserve the inrange index from the innermost GEP if possible. We must
+  // have calculated the same indices up to and including the inrange index.
+  Optional<unsigned> InRangeIndex;
+  if (Optional<unsigned> LastIRIndex = InnermostGEP->getInRangeIndex())
+    if (SrcElemTy == InnermostGEP->getSourceElementType() &&
+        NewIdxs.size() > *LastIRIndex) {
+      InRangeIndex = LastIRIndex;
+      for (unsigned I = 0; I <= *LastIRIndex; ++I)
+        if (NewIdxs[I] != InnermostGEP->getOperand(I + 1)) {
+          InRangeIndex = None;
+          break;
+        }
+    }
+
   // Create a GEP.
-  Constant *C = ConstantExpr::getGetElementPtr(SrcElemTy, Ptr, NewIdxs);
+  Constant *C = ConstantExpr::getGetElementPtr(
+      SrcElemTy, Ptr, NewIdxs, /*InBounds=*/false, InRangeIndex);
   assert(C->getType()->getPointerElementType() == Ty &&
          "Computed GetElementPtr has unexpected type!");
 
   // If we ended up indexing a member with a type that doesn't match
   // the type of what the original indices indexed, add a cast.
   if (Ty != ResElemTy)
     C = FoldBitCast(C, ResTy, DL);
 
   return C;
 }
 
 /// Attempt to constant fold an instruction with the
 /// specified opcode and operands.  If successful, the constant result is
 /// returned, if not, null is returned.  Note that this function can fail when
 /// attempting to fold instructions like loads and stores, which have no
 /// constant expression form.
 ///
-/// TODO: This function neither utilizes nor preserves nsw/nuw/inbounds/etc
-/// information, due to only being passed an opcode and operands. Constant
+/// TODO: This function neither utilizes nor preserves nsw/nuw/inbounds/inrange
+/// etc information, due to only being passed an opcode and operands. Constant
 /// folding using this function strips this information.
 ///
 Constant *ConstantFoldInstOperandsImpl(const Value *InstOrCE, unsigned Opcode,
                                        ArrayRef<Constant *> Ops,
                                        const DataLayout &DL,
                                        const TargetLibraryInfo *TLI) {
   Type *DestTy = InstOrCE->getType();
 
   // Handle easy binops first.
   if (Instruction::isBinaryOp(Opcode))
     return ConstantFoldBinaryOpOperands(Opcode, Ops[0], Ops[1], DL);
 
   if (Instruction::isCast(Opcode))
     return ConstantFoldCastOperand(Opcode, Ops[0], DestTy, DL);
 
   if (auto *GEP = dyn_cast<GEPOperator>(InstOrCE)) {
     if (Constant *C = SymbolicallyEvaluateGEP(GEP, Ops, DL, TLI))
       return C;
 
-    return ConstantExpr::getGetElementPtr(GEP->getSourceElementType(),
-                                          Ops[0], Ops.slice(1));
+    return ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), Ops[0],
+                                          Ops.slice(1), GEP->isInBounds(),
+                                          GEP->getInRangeIndex());
   }
 
   if (auto *CE = dyn_cast<ConstantExpr>(InstOrCE))
     return CE->getWithOperands(Ops);
 
   switch (Opcode) {
   default: return nullptr;
   case Instruction::ICmp:

llvm/trunk/lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(ninf);
   KEYWORD(nsz);
   KEYWORD(arcp);
   KEYWORD(fast);
   KEYWORD(nuw);
   KEYWORD(nsw);
   KEYWORD(exact);
   KEYWORD(inbounds);
+  KEYWORD(inrange);
   KEYWORD(align);
   KEYWORD(addrspace);
   KEYWORD(section);
   KEYWORD(alias);
   KEYWORD(ifunc);
   KEYWORD(module);
   KEYWORD(asm);
   KEYWORD(sideeffect);

llvm/trunk/lib/AsmParser/LLParser.h

private:
 
     bool ParseExceptionArgs(SmallVectorImpl<Value *> &Args,
                             PerFunctionState &PFS);
 
     // Constant Parsing.
     bool ParseValID(ValID &ID, PerFunctionState *PFS = nullptr);
     bool ParseGlobalValue(Type *Ty, Constant *&V);
     bool ParseGlobalTypeAndValue(Constant *&V);
-    bool ParseGlobalValueVector(SmallVectorImpl<Constant *> &Elts);
+    bool ParseGlobalValueVector(SmallVectorImpl<Constant *> &Elts,
+                                Optional<unsigned> *InRangeOp = nullptr);
     bool parseOptionalComdat(StringRef GlobalName, Comdat *&C);
     bool ParseMetadataAsValue(Value *&V, PerFunctionState &PFS);
     bool ParseValueAsMetadata(Metadata *&MD, const Twine &TypeMsg,
                               PerFunctionState *PFS);
     bool ParseMetadata(Metadata *&MD, PerFunctionState *PFS);
     bool ParseMDTuple(MDNode *&MD, bool IsDistinct = false);
     bool ParseMDNode(MDNode *&MD);
     bool ParseMDNodeTail(MDNode *&MD);

llvm/trunk/lib/AsmParser/LLParser.cpp

case lltok::kw_select: {
 
     LocTy ExplicitTypeLoc = Lex.getLoc();
     if (Opc == Instruction::GetElementPtr) {
       if (ParseType(Ty) ||
           ParseToken(lltok::comma, "expected comma after getelementptr's type"))
         return true;
     }
 
-    if (ParseGlobalValueVector(Elts) ||
+    Optional<unsigned> InRangeOp;
+    if (ParseGlobalValueVector(
+            Elts, Opc == Instruction::GetElementPtr ? &InRangeOp : nullptr) ||
         ParseToken(lltok::rparen, "expected ')' in constantexpr"))
       return true;
 
     if (Opc == Instruction::GetElementPtr) {
       if (Elts.size() == 0 ||
           !Elts[0]->getType()->getScalarType()->isPointerTy())
         return Error(ID.Loc, "base of getelementptr must be a pointer");
 
if (Opc == Instruction::GetElementPtr) {
       }
 
       SmallPtrSet<Type*, 4> Visited;
       if (!Indices.empty() && !Ty->isSized(&Visited))
         return Error(ID.Loc, "base element of getelementptr must be sized");
 
       if (!GetElementPtrInst::getIndexedType(Ty, Indices))
         return Error(ID.Loc, "invalid getelementptr indices");
-      ID.ConstantVal =
-          ConstantExpr::getGetElementPtr(Ty, Elts[0], Indices, InBounds);
+
+      if (InRangeOp) {
+        if (*InRangeOp == 0)
+          return Error(ID.Loc,
+                       "inrange keyword may not appear on pointer operand");
+        --*InRangeOp;
+      }
+
+      ID.ConstantVal = ConstantExpr::getGetElementPtr(Ty, Elts[0], Indices,
+                                                      InBounds, InRangeOp);
     } else if (Opc == Instruction::Select) {
       if (Elts.size() != 3)
         return Error(ID.Loc, "expected three operands to select");
       if (const char *Reason = SelectInst::areInvalidOperands(Elts[0], Elts[1],
                                                               Elts[2]))
         return Error(ID.Loc, Reason);
       ID.ConstantVal = ConstantExpr::getSelect(Elts[0], Elts[1], Elts[2]);
     } else if (Opc == Instruction::ShuffleVector) {
if (EatIfPresent(lltok::lparen)) {
     C = getComdat(GlobalName, KwLoc);
   }
 
   return false;
 }
 
 /// ParseGlobalValueVector
 ///   ::= /*empty*/
-///   ::= TypeAndValue (',' TypeAndValue)*
-bool LLParser::ParseGlobalValueVector(SmallVectorImpl<Constant *> &Elts) {
+///   ::= [inrange] TypeAndValue (',' [inrange] TypeAndValue)*
+bool LLParser::ParseGlobalValueVector(SmallVectorImpl<Constant *> &Elts,
+                                      Optional<unsigned> *InRangeOp) {
   // Empty list.
   if (Lex.getKind() == lltok::rbrace ||
       Lex.getKind() == lltok::rsquare ||
       Lex.getKind() == lltok::greater ||
       Lex.getKind() == lltok::rparen)
     return false;
 
-  Constant *C;
-  if (ParseGlobalTypeAndValue(C)) return true;
-  Elts.push_back(C);
+  do {
+    if (InRangeOp && !*InRangeOp && EatIfPresent(lltok::kw_inrange))
+      *InRangeOp = Elts.size();
 
-  while (EatIfPresent(lltok::comma)) {
+    Constant *C;
     if (ParseGlobalTypeAndValue(C)) return true;
     Elts.push_back(C);
-  }
+  } while (EatIfPresent(lltok::comma));
 
   return false;
 }
 
 bool LLParser::ParseMDTuple(MDNode *&MD, bool IsDistinct) {
   SmallVector<Metadata *, 16> Elts;
   if (ParseMDNodeVector(Elts))
     return true;

llvm/trunk/lib/AsmParser/LLToken.h

enum Kind {
   kw_ninf,
   kw_nsz,
   kw_arcp,
   kw_fast,
   kw_nuw,
   kw_nsw,
   kw_exact,
   kw_inbounds,
+  kw_inrange,
   kw_align,
   kw_addrspace,
   kw_section,
   kw_alias,
   kw_ifunc,
   kw_module,
   kw_asm,
   kw_sideeffect,

llvm/trunk/lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::CST_CODE_CE_CAST: {  // CE_CAST: [opcode, opty, opval]
         if (!OpTy)
           return error("Invalid record");
         Constant *Op = ValueList.getConstantFwdRef(Record[2], OpTy);
         V = UpgradeBitCastExpr(Opc, Op, CurTy);
         if (!V) V = ConstantExpr::getCast(Opc, Op, CurTy);
       }
       break;
     }
-    case bitc::CST_CODE_CE_INBOUNDS_GEP:
-    case bitc::CST_CODE_CE_GEP: {  // CE_GEP:        [n x operands]
+    case bitc::CST_CODE_CE_INBOUNDS_GEP: // [ty, n x operands]
+    case bitc::CST_CODE_CE_GEP: // [ty, n x operands]
+    case bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX: { // [ty, flags, n x
+                                                     // operands]
       unsigned OpNum = 0;
       Type *PointeeType = nullptr;
-      if (Record.size() % 2)
+      if (BitCode == bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX ||
+          Record.size() % 2)
         PointeeType = getTypeByID(Record[OpNum++]);
+
+      bool InBounds = false;
+      Optional<unsigned> InRangeIndex;
+      if (BitCode == bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX) {
+        uint64_t Op = Record[OpNum++];
+        InBounds = Op & 1;
+        InRangeIndex = Op >> 1;
+      } else if (BitCode == bitc::CST_CODE_CE_INBOUNDS_GEP)
+        InBounds = true;
+
       SmallVector<Constant*, 16> Elts;
       while (OpNum != Record.size()) {
         Type *ElTy = getTypeByID(Record[OpNum++]);
         if (!ElTy)
           return error("Invalid record");
         Elts.push_back(ValueList.getConstantFwdRef(Record[OpNum++], ElTy));
       }
 
       if (PointeeType &&
           PointeeType !=
               cast<SequentialType>(Elts[0]->getType()->getScalarType())
                   ->getElementType())
         return error("Explicit gep operator type does not match pointee type "
                      "of pointer operand");
 
       if (Elts.size() < 1)
         return error("Invalid gep with no operands");
 
       ArrayRef<Constant *> Indices(Elts.begin() + 1, Elts.end());
       V = ConstantExpr::getGetElementPtr(PointeeType, Elts[0], Indices,
-                                         BitCode ==
-                                             bitc::CST_CODE_CE_INBOUNDS_GEP);
+                                         InBounds, InRangeIndex);
       break;
     }
     case bitc::CST_CODE_CE_SELECT: {  // CE_SELECT: [opval#, opval#, opval#]
       if (Record.size() < 3)
         return error("Invalid record");
 
       Type *SelectorTy = Type::getInt1Ty(Context);
 

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

if (C->isNullValue()) {
           uint64_t Flags = getOptimizationFlags(CE);
           if (Flags != 0)
             Record.push_back(Flags);
         }
         break;
       case Instruction::GetElementPtr: {
         Code = bitc::CST_CODE_CE_GEP;
         const auto *GO = cast<GEPOperator>(C);
-        if (GO->isInBounds())
-          Code = bitc::CST_CODE_CE_INBOUNDS_GEP;
         Record.push_back(VE.getTypeID(GO->getSourceElementType()));
+        if (Optional<unsigned> Idx = GO->getInRangeIndex()) {
+          Code = bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX;
+          Record.push_back((*Idx << 1) | GO->isInBounds());
+        } else if (GO->isInBounds())
+          Code = bitc::CST_CODE_CE_INBOUNDS_GEP;
         for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
           Record.push_back(VE.getTypeID(C->getOperand(i)->getType()));
           Record.push_back(VE.getValueID(C->getOperand(i)));
         }
         break;
       }
       case Instruction::Select:
         Code = bitc::CST_CODE_CE_SELECT;

llvm/trunk/lib/IR/AsmWriter.cpp

static void WriteConstantInternal(raw_ostream &Out, const Constant *CV,
   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CV)) {
     Out << CE->getOpcodeName();
     WriteOptimizationInfo(Out, CE);
     if (CE->isCompare())
       Out << ' ' << CmpInst::getPredicateName(
                         static_cast<CmpInst::Predicate>(CE->getPredicate()));
     Out << " (";
 
+    Optional<unsigned> InRangeOp;
     if (const GEPOperator *GEP = dyn_cast<GEPOperator>(CE)) {
       TypePrinter.print(GEP->getSourceElementType(), Out);
       Out << ", ";
+      InRangeOp = GEP->getInRangeIndex();
+      if (InRangeOp)
+        ++*InRangeOp;
     }
 
     for (User::const_op_iterator OI=CE->op_begin(); OI != CE->op_end(); ++OI) {
+      if (InRangeOp && (OI - CE->op_begin()) == *InRangeOp)
+        Out << "inrange ";
       TypePrinter.print((*OI)->getType(), Out);
       Out << ' ';
       WriteAsOperandInternal(Out, *OI, &TypePrinter, Machine, Context);
       if (OI+1 != CE->op_end())
         Out << ", ";
     }
 
     if (CE->hasIndices()) {

llvm/trunk/lib/IR/ConstantFold.h

 // These operators may return a null object if they don't know how to perform
 // the specified operation on the specified constant types.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_IR_CONSTANTFOLD_H
 #define LLVM_LIB_IR_CONSTANTFOLD_H
 
+#include "llvm/ADT/Optional.h"
+
 namespace llvm {
 template <typename T> class ArrayRef;
   class Value;
   class Constant;
   class Type;
 
   // Constant fold various types of instruction...
   Constant *ConstantFoldCastInstruction(
template <typename T> class ArrayRef;
   Constant *ConstantFoldExtractValueInstruction(Constant *Agg,
                                                 ArrayRef<unsigned> Idxs);
   Constant *ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val,
                                                ArrayRef<unsigned> Idxs);
   Constant *ConstantFoldBinaryInstruction(unsigned Opcode, Constant *V1,
                                           Constant *V2);
   Constant *ConstantFoldCompareInstruction(unsigned short predicate,
                                            Constant *C1, Constant *C2);
-  Constant *ConstantFoldGetElementPtr(Type *Ty, Constant *C, bool inBounds,
-                                      ArrayRef<Constant *> Idxs);
-  Constant *ConstantFoldGetElementPtr(Type *Ty, Constant *C, bool inBounds,
+  Constant *ConstantFoldGetElementPtr(Type *Ty, Constant *C, bool InBounds,
+                                      Optional<unsigned> InRangeIndex,
                                       ArrayRef<Value *> Idxs);
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/IR/ConstantFold.cpp

Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V,
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
     if (CE->isCast()) {
       // Try hard to fold cast of cast because they are often eliminable.
       if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
         return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy);
     } else if (CE->getOpcode() == Instruction::GetElementPtr &&
                // Do not fold addrspacecast (gep 0, .., 0). It might make the
                // addrspacecast uncanonicalized.
-               opc != Instruction::AddrSpaceCast) {
+               opc != Instruction::AddrSpaceCast &&
+               // Do not fold bitcast (gep) with inrange index, as this loses
+               // information.
+               !cast<GEPOperator>(CE)->getInRangeIndex().hasValue()) {
       // If all of the indexes in the GEP are null values, there is no pointer
       // adjustment going on.  We might as well cast the source pointer.
       bool isAllNull = true;
       for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
         if (!CE->getOperand(i)->isNullValue()) {
           isAllNull = false;
           break;
         }
static bool isIndexInRangeOfSequentialType(SequentialType *STy,
   int64_t IndexVal = CI->getSExtValue();
   if (IndexVal < 0 || (NumElements > 0 && (uint64_t)IndexVal >= NumElements))
     return false;
 
   // Otherwise, it is in-range.
   return true;
 }
 
-template<typename IndexTy>
-static Constant *ConstantFoldGetElementPtrImpl(Type *PointeeTy, Constant *C,
-                                               bool inBounds,
-                                               ArrayRef<IndexTy> Idxs) {
+Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C,
+                                          bool InBounds,
+                                          Optional<unsigned> InRangeIndex,
+                                          ArrayRef<Value *> Idxs) {
   if (Idxs.empty()) return C;
   Constant *Idx0 = cast<Constant>(Idxs[0]);
   if ((Idxs.size() == 1 && Idx0->isNullValue()))
     return C;
 
   if (isa<UndefValue>(C)) {
     Type *GEPTy = GetElementPtrInst::getGEPReturnType(
         C, makeArrayRef((Value * const *)Idxs.data(), Idxs.size()));
if (CE->getOpcode() == Instruction::GetElementPtr) {
           } else {
             Combined =
               ConstantExpr::get(Instruction::Add, Idx0, Combined);
           }
         }
 
         NewIndices.push_back(Combined);
         NewIndices.append(Idxs.begin() + 1, Idxs.end());
+
+        // The combined GEP normally inherits its index inrange attribute from
+        // the inner GEP, but if the inner GEP's last index was adjusted by the
+        // outer GEP, any inbounds attribute on that index is invalidated.
+        Optional<unsigned> IRIndex = cast<GEPOperator>(CE)->getInRangeIndex();
+        if (IRIndex && *IRIndex == CE->getNumOperands() - 2 && !Idx0->isNullValue())
+          IRIndex = None;
+
         return ConstantExpr::getGetElementPtr(
             cast<GEPOperator>(CE)->getSourceElementType(), CE->getOperand(0),
-            NewIndices, inBounds && cast<GEPOperator>(CE)->isInBounds());
+            NewIndices, InBounds && cast<GEPOperator>(CE)->isInBounds(),
+            IRIndex);
       }
     }
 
     // Attempt to fold casts to the same type away.  For example, folding:
     //
     //   i32* getelementptr ([2 x i32]* bitcast ([3 x i32]* %X to [2 x i32]*),
     //                       i64 0, i64 0)
     // into:
     //
     //   i32* getelementptr ([3 x i32]* %X, i64 0, i64 0)
     //
     // Don't fold if the cast is changing address spaces.
     if (CE->isCast() && Idxs.size() > 1 && Idx0->isNullValue()) {
       PointerType *SrcPtrTy =
         dyn_cast<PointerType>(CE->getOperand(0)->getType());
       PointerType *DstPtrTy = dyn_cast<PointerType>(CE->getType());
       if (SrcPtrTy && DstPtrTy) {
         ArrayType *SrcArrayTy =
           dyn_cast<ArrayType>(SrcPtrTy->getElementType());
         ArrayType *DstArrayTy =
           dyn_cast<ArrayType>(DstPtrTy->getElementType());
         if (SrcArrayTy && DstArrayTy
             && SrcArrayTy->getElementType() == DstArrayTy->getElementType()
             && SrcPtrTy->getAddressSpace() == DstPtrTy->getAddressSpace())
-          return ConstantExpr::getGetElementPtr(
-              SrcArrayTy, (Constant *)CE->getOperand(0), Idxs, inBounds);
+          return ConstantExpr::getGetElementPtr(SrcArrayTy,
+                                                (Constant *)CE->getOperand(0),
+                                                Idxs, InBounds, InRangeIndex);
       }
     }
   }
 
   // Check to see if any array indices are not within the corresponding
   // notional array or vector bounds. If so, try to determine if they can be
   // factored out into preceding dimensions.
   SmallVector<Constant *, 8> NewIdxs;
   Type *Ty = PointeeTy;
   Type *Prev = C->getType();
   bool Unknown = !isa<ConstantInt>(Idxs[0]);
   for (unsigned i = 1, e = Idxs.size(); i != e;
        Prev = Ty, Ty = cast<CompositeType>(Ty)->getTypeAtIndex(Idxs[i]), ++i) {
     auto *CI = dyn_cast<ConstantInt>(Idxs[i]);
     if (!CI) {
       // We don't know if it's in range or not.
       Unknown = true;
       continue;
     }
+    if (InRangeIndex && i == *InRangeIndex + 1) {
+      // If an index is marked inrange, we cannot apply this canonicalization to
+      // the following index, as that will cause the inrange index to point to
+      // the wrong element.
+      continue;
+    }
     if (isa<StructType>(Ty)) {
       // The verify makes sure that GEPs into a struct are in range.
       continue;
     }
     auto *STy = cast<SequentialType>(Ty);
     if (isa<PointerType>(STy)) {
       // We don't know if it's in range or not.
       Unknown = true;
for (unsigned i = 1, e = Idxs.size(); i != e;
 
     NewIdxs[i - 1] = ConstantExpr::getAdd(PrevIdx, Div);
   }
 
   // If we did any factoring, start over with the adjusted indices.
   if (!NewIdxs.empty()) {
     for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
       if (!NewIdxs[i]) NewIdxs[i] = cast<Constant>(Idxs[i]);
-    return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, inBounds);
+    return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds,
+                                          InRangeIndex);
   }
 
   // If all indices are known integers and normalized, we can do a simple
   // check for the "inbounds" property.
-  if (!Unknown && !inBounds)
+  if (!Unknown && !InBounds)
     if (auto *GV = dyn_cast<GlobalVariable>(C))
       if (!GV->hasExternalWeakLinkage() && isInBoundsIndices(Idxs))
-        return ConstantExpr::getInBoundsGetElementPtr(PointeeTy, C, Idxs);
+        return ConstantExpr::getGetElementPtr(PointeeTy, C, Idxs,
+                                              /*InBounds=*/true, InRangeIndex);
 
   return nullptr;
 }
-
-Constant *llvm::ConstantFoldGetElementPtr(Type *Ty, Constant *C,
-                                          bool inBounds,
-                                          ArrayRef<Constant *> Idxs) {
-  return ConstantFoldGetElementPtrImpl(Ty, C, inBounds, Idxs);
-}
-
-Constant *llvm::ConstantFoldGetElementPtr(Type *Ty, Constant *C,
-                                          bool inBounds,
-                                          ArrayRef<Value *> Idxs) {
-  return ConstantFoldGetElementPtrImpl(Ty, C, inBounds, Idxs);
-}

llvm/trunk/lib/IR/Constants.cpp

Constant *ConstantExpr::getWithOperands(ArrayRef<Constant *> Ops, Type *Ty,
   case Instruction::ShuffleVector:
     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2],
                                           OnlyIfReducedTy);
   case Instruction::GetElementPtr: {
     auto *GEPO = cast<GEPOperator>(this);
     assert(SrcTy || (Ops[0]->getType() == getOperand(0)->getType()));
     return ConstantExpr::getGetElementPtr(
         SrcTy ? SrcTy : GEPO->getSourceElementType(), Ops[0], Ops.slice(1),
-        GEPO->isInBounds(), OnlyIfReducedTy);
+        GEPO->isInBounds(), GEPO->getInRangeIndex(), OnlyIfReducedTy);
   }
   case Instruction::ICmp:
   case Instruction::FCmp:
     return ConstantExpr::getCompare(getPredicate(), Ops[0], Ops[1],
                                     OnlyIfReducedTy);
   default:
     assert(getNumOperands() == 2 && "Must be binary operator?");
     return ConstantExpr::get(getOpcode(), Ops[0], Ops[1], SubclassOptionalData,
Constant *ConstantExpr::getSelect(Constant *C, Constant *V1, Constant *V2,
   ConstantExprKeyType Key(Instruction::Select, ArgVec);
 
   LLVMContextImpl *pImpl = C->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(V1->getType(), Key);
 }
 
 Constant *ConstantExpr::getGetElementPtr(Type *Ty, Constant *C,
                                          ArrayRef<Value *> Idxs, bool InBounds,
+                                         Optional<unsigned> InRangeIndex,
                                          Type *OnlyIfReducedTy) {
   if (!Ty)
     Ty = cast<PointerType>(C->getType()->getScalarType())->getElementType();
   else
     assert(
         Ty ==
         cast<PointerType>(C->getType()->getScalarType())->getContainedType(0u));
 
-  if (Constant *FC = ConstantFoldGetElementPtr(Ty, C, InBounds, Idxs))
+  if (Constant *FC =
+          ConstantFoldGetElementPtr(Ty, C, InBounds, InRangeIndex, Idxs))
     return FC;          // Fold a few common cases.
 
   // Get the result type of the getelementptr!
   Type *DestTy = GetElementPtrInst::getIndexedType(Ty, Idxs);
   assert(DestTy && "GEP indices invalid!");
   unsigned AS = C->getType()->getPointerAddressSpace();
   Type *ReqTy = DestTy->getPointerTo(AS);
 
assert((!Idxs[i]->getType()->isVectorTy() ||
             Idxs[i]->getType()->getVectorNumElements() == NumVecElts) &&
            "getelementptr index type missmatch");
 
     Constant *Idx = cast<Constant>(Idxs[i]);
     if (NumVecElts && !Idxs[i]->getType()->isVectorTy())
       Idx = ConstantVector::getSplat(NumVecElts, Idx);
     ArgVec.push_back(Idx);
   }
+
+  unsigned SubClassOptionalData = InBounds ? GEPOperator::IsInBounds : 0;
+  if (InRangeIndex && *InRangeIndex < 63)
+    SubClassOptionalData |= (*InRangeIndex + 1) << 1;
   const ConstantExprKeyType Key(Instruction::GetElementPtr, ArgVec, 0,
-                                InBounds ? GEPOperator::IsInBounds : 0, None,
-                                Ty);
+                                SubClassOptionalData, None, Ty);
 
   LLVMContextImpl *pImpl = C->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
 }
 
 Constant *ConstantExpr::getICmp(unsigned short pred, Constant *LHS,
                                 Constant *RHS, bool OnlyIfReduced) {
   assert(LHS->getType() == RHS->getType());

llvm/trunk/test/Analysis/ConstantFolding/gep.ll

+; RUN: opt -instcombine -S -o - %s | FileCheck %s
+; Tests that we preserve the inrange attribute on indices where possible.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+
+@vt = external global [3 x i8*]
+
+; CHECK: define i32 (...)* @f0()
+define i32 (...)* @f0() {
+  ; CHECK-NEXT: load i32 (...)*, i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @vt, inrange i64 0, i64 2) to i32 (...)**)
+  %load = load i32 (...)*, i32 (...)** getelementptr (i32 (...)*, i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @vt, inrange i64 0, i64 1) to i32 (...)**), i64 1)
+  ret i32 (...)* %load
+}
+
+; CHECK: define i32 (...)* @f1()
+define i32 (...)* @f1() {
+  ; CHECK-NEXT: load i32 (...)*, i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @vt, i64 0, i64 2) to i32 (...)**)
+  %load = load i32 (...)*, i32 (...)** getelementptr (i32 (...)*, i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @vt, i64 0, inrange i64 1) to i32 (...)**), i64 1)
+  ret i32 (...)* %load
+}
+
+; CHECK: define i32 (...)* @f2()
+define i32 (...)* @f2() {
+  ; CHECK-NEXT: load i32 (...)*, i32 (...)** bitcast (i8** getelementptr ([3 x i8*], [3 x i8*]* @vt, i64 1, i64 1) to i32 (...)**)
+  %load = load i32 (...)*, i32 (...)** getelementptr (i32 (...)*, i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @vt, i64 0, inrange i64 1) to i32 (...)**), i64 3)
+  ret i32 (...)* %load
+}

llvm/trunk/test/Assembler/getelementptr.ll

 @x = external global {i32, i32}
 @y = global i32* getelementptr ({ i32, i32 }, { i32, i32 }* @x, i16 42, i32 0)
 ; CHECK: @y = global i32* getelementptr ({ i32, i32 }, { i32, i32 }* @x, i16 42, i32 0)
 
 @PR23753_a = external global i8
 @PR23753_b = global i8* getelementptr (i8, i8* @PR23753_a, i64 ptrtoint (i8* @PR23753_a to i64))
 ; CHECK: @PR23753_b = global i8* getelementptr (i8, i8* @PR23753_a, i64 ptrtoint (i8* @PR23753_a to i64))
 
+; Verify that inrange on an index inhibits over-indexed getelementptr folding.
+
+@nestedarray = global [2 x [4 x i8*]] zeroinitializer
+
+; CHECK: @nestedarray.1 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, inrange i32 0, i64 1, i32 0)
+@nestedarray.1 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, inrange i32 0, i32 0, i32 4)
+
+; CHECK: @nestedarray.2 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, i32 0, inrange i32 0, i32 4)
+@nestedarray.2 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, i32 0, inrange i32 0, i32 4)
+
+; CHECK: @nestedarray.3 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, i32 0, inrange i32 0, i32 0)
+@nestedarray.3 = alias i8*, getelementptr inbounds ([4 x i8*], [4 x i8*]* getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, i32 0, inrange i32 0), i32 0, i32 0)
+
+; CHECK: @nestedarray.4 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, i32 0, i32 1, i32 0)
+@nestedarray.4 = alias i8*, getelementptr inbounds ([4 x i8*], [4 x i8*]* getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, i32 0, inrange i32 0), i32 1, i32 0)
+
+; CHECK: @nestedarray.5 = alias i8*, getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, inrange i32 0, i32 1, i32 0)
+@nestedarray.5 = alias i8*, getelementptr inbounds ([4 x i8*], [4 x i8*]* getelementptr inbounds ([2 x [4 x i8*]], [2 x [4 x i8*]]* @nestedarray, inrange i32 0, i32 0), i32 1, i32 0)
+
 ; See if i92 indices work too.
 define i32 *@test({i32, i32}* %t, i92 %n) {
 ; CHECK: @test
 ; CHECK: %B = getelementptr { i32, i32 }, { i32, i32 }* %t, i92 %n, i32 0
   %B = getelementptr {i32, i32}, {i32, i32}* %t, i92 %n, i32 0
   ret i32* %B
 }
 

llvm/trunk/test/Bitcode/compatibility.ll

 normal:
   ret void
 }
 
 
 declare void @f.writeonly() writeonly
 ; CHECK: declare void @f.writeonly() #39
 
+;; Constant Expressions
+
+define i8** @constexpr() {
+  ; CHECK: ret i8** getelementptr inbounds ({ [4 x i8*], [4 x i8*] }, { [4 x i8*], [4 x i8*] }* null, i32 0, inrange i32 1, i32 2)
+  ret i8** getelementptr inbounds ({ [4 x i8*], [4 x i8*] }, { [4 x i8*], [4 x i8*] }* null, i32 0, inrange i32 1, i32 2)
+}
+
 ; CHECK: attributes #0 = { alignstack=4 }
 ; CHECK: attributes #1 = { alignstack=8 }
 ; CHECK: attributes #2 = { alwaysinline }
 ; CHECK: attributes #3 = { cold }
 ; CHECK: attributes #4 = { convergent }
 ; CHECK: attributes #5 = { inlinehint }
 ; CHECK: attributes #6 = { jumptable }
 ; CHECK: attributes #7 = { minsize }