[ConstantFold] Remove unnecessary bounded index restriction

[nikic]

Summary

The fold for merging a GEP of GEP into a single GEP currently bails if doing so would result in notional overindexing. The justification given in the comment above this check is dangerously incorrect: GEPs with notional overindexing are perfectly fine, and if some code treats them incorrectly, then that code is broken, not the GEP. Such a GEP might legally appear in source IR, so only preventing its creation cannot be sufficient. (The constant folder also ends up canonicalizing the GEP to remove the notional overindexing, but that's neither here nor there.)

This check dates back to https://github.com/llvm/llvm-project/commit/bd4fef4a8939db18f39b108e19097b25e2c7c47a, and as far as I can tell the original issue this was trying to patch around has since been resolved.

[nikic]

Update some clang tests. Will update the rest if this is generally fine.

[nlopes]

LGTM. I agree there's no issue in combining OOB geps.
The code seems to handle well the mix of inbounds and non-bounds geps, by dropping inbounds.

I glanced through the OMP test changes, as they looked scary, but they seem fine. They produce a +1 pointer, which is ok.

llvm/lib/IR/ConstantFold.cpp

return ConstantExpr::getGetElementPtr(
         NewIndices, InBounds && GEP->isInBounds(), GEP->getInRangeIndex());
   }
 
   gep_type_iterator LastI = gep_type_end(GEP);
   for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
        I != E; ++I)
     LastI = I;
 
-  // We cannot combine indices if doing so would take us outside of an
-  // array or vector.  Doing otherwise could trick us if we evaluated such a
-  // GEP as part of a load.
-  //
-  // e.g. Consider if the original GEP was:
-  // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c,
-  //                    i32 0, i32 0, i64 0)
-  //
-  // If we then tried to offset it by '8' to get to the third element,
-  // an i8, we should *not* get:
-  // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c,
-  //                    i32 0, i32 0, i64 8)
-  //
-  // This GEP tries to index array element '8  which runs out-of-bounds.
-  // Subsequent evaluation would get confused and produce erroneous results.
-  //
-  // The following prohibits such a GEP from being formed by checking to see
-  // if the index is in-range with respect to an array.
+  // We can't combine GEPs if the last index is a struct type.
   if (!LastI.isSequential())
     return nullptr;
+  // We could perform the transform with non-constant index, but prefer leaving
+  // it as GEP of GEP rather than GEP of add for now.
   ConstantInt *CI = dyn_cast<ConstantInt>(Idx0);
   if (!CI)
     return nullptr;
-  if (LastI.isBoundedSequential() &&
-      !isIndexInRangeOfArrayType(LastI.getSequentialNumElements(), CI))
-    return nullptr;
 
   // TODO: This code may be extended to handle vectors as well.
   auto *LastIdx = cast<Constant>(GEP->getOperand(GEP->getNumOperands()-1));
   Type *LastIdxTy = LastIdx->getType();
   if (LastIdxTy->isVectorTy())
     return nullptr;
 
   SmallVector<Value*, 16> NewIndices;

llvm/test/Transforms/SCCP/apint-bigint2.ll

;
   %F = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 5
   %G = getelementptr i101, i101* %F, i101 %DD
   %L3 = load i101, i101* %G
   ret i101 %L3
 }
 
 define void @index_too_large() {
 ; CHECK-LABEL: @index_too_large(
-; CHECK-NEXT:    store i101* getelementptr (i101, i101* getelementptr ([6 x i101], [6 x i101]* @Y, i32 0, i32 -1), i101 9224497936761618431), i101** undef, align 8
+; CHECK-NEXT:    store i101* getelementptr ([6 x i101], [6 x i101]* @Y, i101 1537416322793603071, i101 4), i101** undef, align 8
 ; CHECK-NEXT:    ret void
 ;
   %ptr1 = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 -1
   %ptr2 = getelementptr i101, i101* %ptr1, i101 9224497936761618431
   store i101* %ptr2, i101** undef
   ret void
 }
 

llvm/test/Transforms/SCCP/replace-dereferenceable-ptr-with-undereferenceable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=ipsccp -S %s | FileCheck %s
 
 @y = common global [1 x i32] zeroinitializer, align 4
 @x = common global [1 x i32] zeroinitializer, align 4
 
 define i32 @eq_undereferenceable(i32* %p) {
 ; CHECK-LABEL: @eq_undereferenceable(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i32 1, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32* [[P:%.*]], getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32* [[P:%.*]], getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0)
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 2, i32* getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1), align 4
+; CHECK-NEXT:    store i32 2, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0), align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   store i32 1, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
   %cmp = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)

 if.end:                                           ; preds = %if.then, %entry
   %0 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0), align 4
   ret i32 %0
 }
 
 define i1 @eq_undereferenceable_cmp_simp(i32* %p) {
 ; CHECK-LABEL: @eq_undereferenceable_cmp_simp(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP_0:%.*]] = icmp eq i32* [[P:%.*]], getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
+; CHECK-NEXT:    [[CMP_0:%.*]] = icmp eq i32* [[P:%.*]], getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0)
 ; CHECK-NEXT:    br i1 [[CMP_0]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 2, i32* getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1), align 4
+; CHECK-NEXT:    store i32 2, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0), align 4
 ; CHECK-NEXT:    ret i1 true
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp eq i32* [[P]], getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
+; CHECK-NEXT:    [[CMP_2:%.*]] = icmp eq i32* [[P]], getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0)
 ; CHECK-NEXT:    ret i1 [[CMP_2]]
 ;
 entry:
   %cmp.0 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   br i1 %cmp.0, label %if.then, label %if.end
 
 if.then:                                          ; preds = %entry
   store i32 2, i32* %p, align 4
   %cmp.1 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   ret i1 %cmp.1
 
 if.end:                                           ; preds = %if.then, %entry
   %cmp.2 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   ret i1 %cmp.2
 }