[Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset (PR42699)

[miyuki]

Summary

Currently when computing a GEP offset using the function EmitGEPOffset
for the following instruction

getelementptr inbounds i32, i32* %p, i64 %offs

we get

mul nuw i64 %offs, 4

Unfortunately we cannot assume that unsigned wrapping won't happen
here because %offs is allowed to be negative.

Making such assumptions can lead to miscompilations: see the new test
test24_neg_offs in InstCombine/icmp.ll. Without the patch InstCombine
would generate the following comparison:

icmp eq i64 %offs, 4611686018427387902; 0x3ffffffffffffffe

Whereas the correct value to compare with is -2.

This patch replaces the NUW flag with NSW in the multiplication
instructions generated by EmitGEPOffset and adjusts the test suite.

https://bugs.llvm.org/show_bug.cgi?id=42699

[lebedev.ri]

I'm not fully convinced this is correct, as per
https://llvm.org/docs/LangRef.html#getelementptr-instruction

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

If the inbounds keyword is not present, the offsets are added to the base address with
silently-wrapping two’s complement arithmetic.

At worst NUW should be relaxed to NSW.

[miyuki]

In D68342#1691617, @lebedev.ri wrote:

I'm not fully convinced this is correct, as per
https://llvm.org/docs/LangRef.html#getelementptr-instruction

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

At worst NUW should be relaxed to NSW.

What about the case I mentioned, i.e. an object which is larger than half of its address space?

[lebedev.ri]

In D68342#1691704, @miyuki wrote:

In D68342#1691617, @lebedev.ri wrote:

I'm not fully convinced this is correct, as per
https://llvm.org/docs/LangRef.html#getelementptr-instruction

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

I do not understand this point, could you elaborate please?

At worst NUW should be relaxed to NSW.

What about the case I mentioned, i.e. an object which is larger than half of its address space?

[miyuki]

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

I do not understand this point, could you elaborate please?

Nothing in the code implies that buf points to a single i32 value rather than to an element in an array of i32, but Clang nevertheless adds inbounds. If InstCombine tried to get an offset from the getelementptr inbounds i32, i32* %buf, i64 -2 instruction it would generate a mul nuw i64 4, -2 instruction, which wraps.

[lebedev.ri]

In D68342#1691781, @miyuki wrote:

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

I do not understand this point, could you elaborate please?

Nothing in the code implies that buf points to a single i32 value rather than to an element in an array of i32, but Clang nevertheless adds inbounds.

I don't see how that follows?
Quote from http://eel.is/c++draft/expr.add#4:

4     When an expression J that has integral type is added to or subtracted
      from an expression P of pointer type, the result has the type of P.
(4.1) If P evaluates to a null pointer value and J evaluates to 0,
      the result is a null pointer value.
(4.2) Otherwise, if P points to an array element i of an array object x with n
      elements ([dcl.array]), the expressions P + J and J + P
      (where J has the value j) point to the (possibly-hypothetical) array
      element i+j of x if 0≤i+j≤n and the expression P - J points to the 
      (possibly-hypothetical) array element i−j of x if 0≤i−j≤n.
(4.3) Otherwise, the behavior is undefined.

(see also C 6.5.6p8)

Which quite precisely maps to LangRef

"If the inbounds keyword is present, the result value of the getelementptr is a poison value if the base pointer is not an in bounds address of an allocated object <...>"

So clang is perfectly correct here.

If InstCombine tried to get an offset from the getelementptr inbounds i32, i32* %buf, i64 -2 instruction it would generate a mul nuw i64 4, -2 instruction, which wraps.

[miyuki]

So clang is perfectly correct here.

Yes, Clang is correct. EmitGEPOffset is doing the wrong thing.
nuw is incorrect because negative offsets are allowed. nsw would also be incorrect because of the quote you mentioned before:

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

nsw would imply that signed overflow must not occur when computing the offset in the integer type of the same width as the pointer type. But LangRef is talking about infinitely precise arithmetic.

[miyuki]

ping

[lebedev.ri]

In D68342#1692607, @miyuki wrote:

So clang is perfectly correct here.

Yes, Clang is correct. EmitGEPOffset is doing the wrong thing.
nuw is incorrect because negative offsets are allowed. nsw would also be incorrect because of the quote you mentioned before:

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

nsw would imply that signed overflow must not occur when computing the offset in the integer type of the same width as the pointer type. But LangRef is talking about infinitely precise arithmetic.

I'll rephrase.
I don't think this case is defined for address space 0 - i don't believe you can ever have an object e.g. occupying [i8 128, i8 8] (i.e. including null pointer).
It it likely not so for other address spaces. So the likely solution is to use NSW iff address space = 0.

[miyuki]

Added the NSW flag. This discussion thread also suggests that signed overflows should not occur in the inbounds GEPs: https://lists.llvm.org/pipermail/llvm-dev/2017-November/118914.html

[nlopes]

The patch looks good to me. Actually I had reported this bug a while back as well: https://bugs.llvm.org/show_bug.cgi?id=42699
I agree we can't have objects larger than half of the address space.

My only question is : why the restriction to address space 0? LangRef doesn't have any exception for other address spaces in these matters AFAICT.

[miyuki]

@lebedev.ri, do you agree that all address spaces should be treated the same way as address space 0 (i.e. no signed overflow)?

[lebedev.ri]

In D68342#1710600, @miyuki wrote:

@lebedev.ri, do you agree that all address spaces should be treated the same way as address space 0 (i.e. no signed overflow)?

I wouldn't be surprised if that isn't so, i don't think it's really documented what normal assumptions do and don't apply to non-0-address-spaces.

[miyuki]

Don't treat non-zero address space specially

[miyuki]

In D68342#1710616, @lebedev.ri wrote:

In D68342#1710600, @miyuki wrote:

@lebedev.ri, do you agree that all address spaces should be treated the same way as address space 0 (i.e. no signed overflow)?

I wouldn't be surprised if that isn't so, i don't think it's really documented what normal assumptions do and don't apply to non-0-address-spaces.

OK, let's stick to what is documented for GEP (and the status quo about objects larger than half of the address space).

[lebedev.ri]

After re-reading everything posted/linked above, SGTM.
Please wait for @nlopes / @reames / @aqjune.

[nlopes]

LGTM
(there's only a typo in the comment "singned")

[aqjune]

I agree that the size of a block should not be larger than the half of memory size.

https://lists.llvm.org/pipermail/llvm-dev/2017-November/118914.html

This is a pretty informative link. :) Thank you for sharing this.

llvm/include/llvm/Analysis/Utils/Local.h

 template <typename IRBuilderTy>
 Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP,
                      bool NoAssumptions = false) {
   GEPOperator *GEPOp = cast<GEPOperator>(GEP);
   Type *IntPtrTy = DL.getIntPtrType(GEP->getType());
   Value *Result = Constant::getNullValue(IntPtrTy);
 
   // If the GEP is inbounds, we know that none of the addressing operations will
-  // overflow in an unsigned sense.
+  // overflow in a signed sense.
   bool isInBounds = GEPOp->isInBounds() && !NoAssumptions;
 
   // Build a mask for high order bits.
   unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth();
   uint64_t PtrSizeMask =
       std::numeric_limits<uint64_t>::max() >> (64 - IntPtrWidth);
 
   gep_type_iterator GTI = gep_type_begin(GEP);
if (Constant *OpC = dyn_cast<Constant>(Op)) {
       }
 
       // Splat the constant if needed.
       if (IntPtrTy->isVectorTy() && !OpC->getType()->isVectorTy())
         OpC = ConstantVector::getSplat(IntPtrTy->getVectorNumElements(), OpC);
 
       Constant *Scale = ConstantInt::get(IntPtrTy, Size);
       Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
-      Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/);
+      Scale =
+          ConstantExpr::getMul(OC, Scale, false /*NUW*/, isInBounds /*NSW*/);
       // Emit an add instruction.
       Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
       continue;
     }
 
     // Splat the index if needed.
     if (IntPtrTy->isVectorTy() && !Op->getType()->isVectorTy())
       Op = Builder->CreateVectorSplat(IntPtrTy->getVectorNumElements(), Op);
 
     // Convert to correct type.
     if (Op->getType() != IntPtrTy)
       Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
     if (Size != 1) {
       // We'll let instcombine(mul) convert this to a shl if possible.
       Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size),
-                              GEP->getName()+".idx", isInBounds /*NUW*/);
+                              GEP->getName() + ".idx", false /*NUW*/,
+                              isInBounds /*NSW*/);
     }
 
     // Emit an add instruction.
     Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
   }
   return Result;
 }
 
 }
 
 #endif // LLVM_TRANSFORMS_UTILS_LOCAL_H

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

;
   %tmp.4 = icmp eq i32* %tmp.1, %tmp.3
   ret i1 %tmp.4
 }
 
 %S = type { i32, [ 100 x i32] }
 
 define <2 x i1> @test6(<2 x i32> %X, <2 x %S*> %P) nounwind {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i32> [[X:%.*]], <i32 1073741823, i32 1073741823>
+; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i32> %X, <i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %A = getelementptr inbounds %S, <2 x %S*> %P, <2 x i32> zeroinitializer, <2 x i32> <i32 1, i32 1>, <2 x i32> %X
   %B = getelementptr inbounds %S, <2 x %S*> %P, <2 x i32> <i32 0, i32 0>, <2 x i32> <i32 0, i32 0>
   %C = icmp eq <2 x i32*> %A, %B
   ret <2 x i1> %C
 }
 
 ; Same as above, but indices scalarized.
 define <2 x i1> @test6b(<2 x i32> %X, <2 x %S*> %P) nounwind {
 ; CHECK-LABEL: @test6b(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i32> [[X:%.*]], <i32 1073741823, i32 1073741823>
+; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i32> %X, <i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %A = getelementptr inbounds %S, <2 x %S*> %P, i32 0, i32 1, <2 x i32> %X
   %B = getelementptr inbounds %S, <2 x %S*> %P, i32 0, i32 0
   %C = icmp eq <2 x i32*> %A, %B
   ret <2 x i1> %C
 }
 

llvm/test/Transforms/InstCombine/getelementptr.ll

define i1 @test13(i64 %X, %S* %P) {
         %A = getelementptr inbounds %S, %S* %P, i32 0, i32 1, i64 %X
         %B = getelementptr inbounds %S, %S* %P, i32 0, i32 0
   %C = icmp eq i32* %A, %B
   ret i1 %C
 ; CHECK-LABEL: @test13(
 ; CHECK:    %C = icmp eq i64 %X, -1
 }
 
-; This is a test of icmp + shl nuw in disguise - 4611... is 0x3fff...
 define <2 x i1> @test13_vector(<2 x i64> %X, <2 x %S*> %P) nounwind {
 ; CHECK-LABEL: @test13_vector(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i64> %X, <i64 4611686018427387903, i64 4611686018427387903>
+; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i64> %X, <i64 -1, i64 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %A = getelementptr inbounds %S, <2 x %S*> %P, <2 x i64> zeroinitializer, <2 x i32> <i32 1, i32 1>, <2 x i64> %X
   %B = getelementptr inbounds %S, <2 x %S*> %P, <2 x i64> <i64 0, i64 0>, <2 x i32> <i32 0, i32 0>
   %C = icmp eq <2 x i32*> %A, %B
   ret <2 x i1> %C
 }
 
-; This is a test of icmp + shl nuw in disguise - 4611... is 0x3fff...
 define <2 x i1> @test13_vector2(i64 %X, <2 x %S*> %P) nounwind {
 ; CHECK-LABEL: @test13_vector2(
 ; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <2 x i64> undef, i64 [[X:%.*]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw <2 x i64> [[DOTSPLATINSERT]], <i64 2, i64 undef>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i64> [[DOTSPLATINSERT]], <i64 2, i64 undef>
 ; CHECK-NEXT:    [[A_IDX:%.*]] = shufflevector <2 x i64> [[TMP1]], <2 x i64> undef, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i64> [[A_IDX]], <i64 -4, i64 -4>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %A = getelementptr inbounds %S, <2 x %S*> %P, <2 x i64> zeroinitializer, <2 x i32> <i32 1, i32 1>, i64 %X
   %B = getelementptr inbounds %S, <2 x %S*> %P, <2 x i64> <i64 0, i64 0>, <2 x i32> <i32 0, i32 0>
   %C = icmp eq <2 x i32*> %A, %B
   ret <2 x i1> %C
 }
 
 ; This is a test of icmp + shl nuw in disguise - 4611... is 0x3fff...
 define <2 x i1> @test13_vector3(i64 %X, <2 x %S*> %P) nounwind {
 ; CHECK-LABEL: @test13_vector3(
 ; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <2 x i64> undef, i64 [[X:%.*]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw <2 x i64> [[DOTSPLATINSERT]], <i64 2, i64 undef>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i64> [[DOTSPLATINSERT]], <i64 2, i64 undef>
 ; CHECK-NEXT:    [[A_IDX:%.*]] = shufflevector <2 x i64> [[TMP1]], <2 x i64> undef, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i64> [[A_IDX]], <i64 4, i64 4>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %A = getelementptr inbounds %S, <2 x %S*> %P, <2 x i64> zeroinitializer, <2 x i32> <i32 1, i32 1>, i64 %X
   %B = getelementptr inbounds %S, <2 x %S*> %P, <2 x i64> <i64 0, i64 0>, <2 x i32> <i32 1, i32 1>, i64 1
   %C = icmp eq <2 x i32*> %A, %B
   ret <2 x i1> %C
 }
 
 define i1 @test13_as1(i16 %X, %S addrspace(1)* %P) {
 ; CHECK-LABEL: @test13_as1(
 ; CHECK-NEXT:  %C = icmp eq i16 %X, -1
 ; CHECK-NEXT: ret i1 %C
   %A = getelementptr inbounds %S, %S addrspace(1)* %P, i16 0, i32 1, i16 %X
   %B = getelementptr inbounds %S, %S addrspace(1)* %P, i16 0, i32 0
   %C = icmp eq i32 addrspace(1)* %A, %B
   ret i1 %C
 }
 
-; This is a test of icmp + shl nuw in disguise - 16383 is 0x3fff.
 define <2 x i1> @test13_vector_as1(<2 x i16> %X, <2 x %S addrspace(1)*> %P) {
 ; CHECK-LABEL: @test13_vector_as1(
-; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i16> %X, <i16 16383, i16 16383>
+; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i16> %X, <i16 -1, i16 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %A = getelementptr inbounds %S, <2 x %S addrspace(1)*> %P, <2 x i16> <i16 0, i16 0>, <2 x i32> <i32 1, i32 1>, <2 x i16> %X
   %B = getelementptr inbounds %S, <2 x %S addrspace(1)*> %P, <2 x i16> <i16 0, i16 0>, <2 x i32> <i32 0, i32 0>
   %C = icmp eq <2 x i32 addrspace(1)*> %A, %B
   ret <2 x i1> %C
 }
 

llvm/test/Transforms/InstCombine/icmp-custom-dl.ll

;
   %call = call i32 @test58_d(i64 %use)
   ret i1 %cmp
 }
 
 define i1 @test60(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test60(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[I:%.*]] to i32
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[J:%.*]] to i32
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i32 [[TMP1]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[GEP1_IDX]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %bit = bitcast i8* %foo to i32*
   %gep1 = getelementptr inbounds i32, i32* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = bitcast i32* %gep1 to i8*
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp
 }
 
 define i1 @test60_as1(i8 addrspace(1)* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test60_as1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[I:%.*]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[J:%.*]] to i16
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 [[TMP1]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i16 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i16 [[GEP1_IDX]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8 addrspace(1)* %foo, i64 %j
   %cast1 = bitcast i32 addrspace(1)* %gep1 to i8 addrspace(1)*
   %cmp = icmp ult i8 addrspace(1)* %cast1, %gep2
;
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = addrspacecast i32 addrspace(3)* %gep1 to i8*
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp
 }
 
 define i1 @test60_addrspacecast_smaller(i8* %foo, i16 %i, i64 %j) {
 ; CHECK-LABEL: @test60_addrspacecast_smaller(
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 [[I:%.*]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i16 [[I:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[J:%.*]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i16 [[GEP1_IDX]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %bit = addrspacecast i8* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i16 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = addrspacecast i32 addrspace(1)* %gep1 to i8*

llvm/test/Transforms/InstCombine/icmp.ll

 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[I:%.*]], 1000
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %p1 = getelementptr inbounds i32, i32* getelementptr inbounds ([1000 x i32], [1000 x i32]* @X, i64 0, i64 0), i64 %i
   %cmp = icmp eq i32* %p1, getelementptr inbounds ([1000 x i32], [1000 x i32]* @X, i64 1, i64 0)
   ret i1 %cmp
 }
 
+; Note: offs can be negative, LLVM used to make an incorrect assumption that
+; unsigned overflow does not happen during offset computation
+define i1 @test24_neg_offs(i32* %p, i64 %offs) {
+; CHECK-LABEL: @test24_neg_offs(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[OFFS:%.*]], -2
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %p1 = getelementptr inbounds i32, i32* %p, i64 %offs
+  %conv1 = ptrtoint i32* %p to i64
+  %conv2 = ptrtoint i32* %p1 to i64
+  %delta = sub i64 %conv1, %conv2
+  %cmp = icmp eq i64 %delta, 8
+  ret i1 %cmp
+}
+
 @X_as1 = addrspace(1) global [1000 x i32] zeroinitializer
 
 define i1 @test24_as1(i64 %i) {
 ; CHECK-LABEL: @test24_as1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[I:%.*]] to i16
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 1000
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
;
   %cmp = icmp ult i8 addrspace(1)* %cast1, %gep2
   %use = ptrtoint i8 addrspace(1)* %cast1 to i64
   %call = call i32 @test58_d(i64 %use)
   ret i1 %cmp
 }
 
 define i1 @test60(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test60(
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i64 [[I:%.*]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i64 [[I:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i64 [[GEP1_IDX]], [[J:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %bit = bitcast i8* %foo to i32*
   %gep1 = getelementptr inbounds i32, i32* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = bitcast i32* %gep1 to i8*
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp
 }
 
 define i1 @test60_as1(i8 addrspace(1)* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test60_as1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[I:%.*]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[J:%.*]] to i16
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 [[TMP1]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i16 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i16 [[GEP1_IDX]], [[TMP2]]
 ; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8 addrspace(1)* %foo, i64 %j
   %cast1 = bitcast i32 addrspace(1)* %gep1 to i8 addrspace(1)*
   %cmp = icmp ult i8 addrspace(1)* %cast1, %gep2
   ret i1 %cmp
 }
 
 ; Same as test60, but look through an addrspacecast instead of a
 ; bitcast. This uses the same sized addrspace.
 define i1 @test60_addrspacecast(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test60_addrspacecast(
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i64 [[I:%.*]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i64 [[I:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i64 [[GEP1_IDX]], [[J:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %bit = addrspacecast i8* %foo to i32 addrspace(3)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(3)* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = addrspacecast i32 addrspace(3)* %gep1 to i8*
   %cmp = icmp ult i8* %cast1, %gep2
   ret i1 %cmp
 }
 
 define i1 @test60_addrspacecast_smaller(i8* %foo, i16 %i, i64 %j) {
 ; CHECK-LABEL: @test60_addrspacecast_smaller(
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 [[I:%.*]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i16 [[I:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[J:%.*]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i16 [[GEP1_IDX]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %bit = addrspacecast i8* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i16 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = addrspacecast i32 addrspace(1)* %gep1 to i8*

llvm/test/Transforms/InstCombine/sub.ll

;
   ret i16 %G
 }
 
 
 @Arr = external global [42 x i16]
 
 define i64 @test24b(i8* %P, i64 %A){
 ; CHECK-LABEL: @test24b(
-; CHECK-NEXT:    [[B_IDX:%.*]] = shl nuw i64 [[A:%.*]], 1
+; CHECK-NEXT:    [[B_IDX:%.*]] = shl nsw i64 [[A:%.*]], 1
 ; CHECK-NEXT:    ret i64 [[B_IDX]]
 ;
   %B = getelementptr inbounds [42 x i16], [42 x i16]* @Arr, i64 0, i64 %A
   %C = ptrtoint i16* %B to i64
   %G = sub i64 %C, ptrtoint ([42 x i16]* @Arr to i64)
   ret i64 %G
 }
 
 
 define i64 @test25(i8* %P, i64 %A){
 ; CHECK-LABEL: @test25(
-; CHECK-NEXT:    [[B_IDX:%.*]] = shl nuw i64 [[A:%.*]], 1
-; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[B_IDX]], -84
-; CHECK-NEXT:    ret i64 [[TMP1]]
+; CHECK-NEXT:    [[B_IDX:%.*]] = shl nsw i64 [[A:%.*]], 1
+; CHECK-NEXT:    [[DIFF_NEG:%.*]] = add i64 [[B_IDX]], -84
+; CHECK-NEXT:    ret i64 [[DIFF_NEG]]
 ;
   %B = getelementptr inbounds [42 x i16], [42 x i16]* @Arr, i64 0, i64 %A
   %C = ptrtoint i16* %B to i64
   %G = sub i64 %C, ptrtoint (i16* getelementptr ([42 x i16], [42 x i16]* @Arr, i64 1, i64 0) to i64)
   ret i64 %G
 }
 
 @Arr_as1 = external addrspace(1) global [42 x i16]
 
 define i16 @test25_as1(i8 addrspace(1)* %P, i64 %A) {
 ; CHECK-LABEL: @test25_as1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i16
-; CHECK-NEXT:    [[B_IDX:%.*]] = shl nuw i16 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i16 [[B_IDX]], -84
-; CHECK-NEXT:    ret i16 [[TMP2]]
+; CHECK-NEXT:    [[B_IDX:%.*]] = shl nsw i16 [[TMP1]], 1
+; CHECK-NEXT:    [[DIFF_NEG:%.*]] = add i16 [[B_IDX]], -84
+; CHECK-NEXT:    ret i16 [[DIFF_NEG]]
 ;
   %B = getelementptr inbounds [42 x i16], [42 x i16] addrspace(1)* @Arr_as1, i64 0, i64 %A
   %C = ptrtoint i16 addrspace(1)* %B to i16
   %G = sub i16 %C, ptrtoint (i16 addrspace(1)* getelementptr ([42 x i16], [42 x i16] addrspace(1)* @Arr_as1, i64 1, i64 0) to i16)
   ret i16 %G
 }
 
 define i32 @test26(i32 %x) {
;
   %cast1 = ptrtoint i8* %gep1 to i64
   %cast2 = ptrtoint i8* %gep2 to i64
   %sub = sub i64 %cast1, %cast2
   ret i64 %sub
 }
 
 define i64 @test30(i8* %foo, i64 %i, i64 %j) {
 ; CHECK-LABEL: @test30(
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i64 [[I:%.*]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i64 [[I:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[GEP1_IDX]], [[J:%.*]]
 ; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %bit = bitcast i8* %foo to i32*
   %gep1 = getelementptr inbounds i32, i32* %bit, i64 %i
   %gep2 = getelementptr inbounds i8, i8* %foo, i64 %j
   %cast1 = ptrtoint i32* %gep1 to i64
   %cast2 = ptrtoint i8* %gep2 to i64
   %sub = sub i64 %cast1, %cast2
   ret i64 %sub
 }
 
 define i16 @test30_as1(i8 addrspace(1)* %foo, i16 %i, i16 %j) {
 ; CHECK-LABEL: @test30_as1(
-; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nuw i16 [[I:%.*]], 2
+; CHECK-NEXT:    [[GEP1_IDX:%.*]] = shl nsw i16 [[I:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i16 [[GEP1_IDX]], [[J:%.*]]
 ; CHECK-NEXT:    ret i16 [[TMP1]]
 ;
   %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)*
   %gep1 = getelementptr inbounds i32, i32 addrspace(1)* %bit, i16 %i
   %gep2 = getelementptr inbounds i8, i8 addrspace(1)* %foo, i16 %j
   %cast1 = ptrtoint i32 addrspace(1)* %gep1 to i16
   %cast2 = ptrtoint i8 addrspace(1)* %gep2 to i16