Check for overflows when calculating the offset in GetGEPCost.

[jlebar]

Summary

This avoids C++ UB if the GEP is weird and the calculation overflows
int64_t, and it's also observable in the cost model's results.

Such GEPs are almost surely not valid pointers, but LLVM nonetheless
generates them sometimes.

[efriedma]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

681 ↗

(On Diff #116893)

Should we use the pointer width here, rather than the constant "64"?

707 ↗

(On Diff #116893)

Might as well use wrapping math, rather than bailing out on overflow; that's how the actual lowering works.

[jlebar]

Wrap the GEP indices instead of bailing on overflow.

[jlebar]

Thank you for the review, Eli.

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

681 ↗

(On Diff #116893)

Looking at the langref, I think you're right, here and below. I've updated the patch, wdyt?

[efriedma]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

707 ↗

(On Diff #116898)

ConstIdx->getValue().sextOrTrunc(PtrSizeBits)? getSExtValue() can fail if ConstIdx is, for example, an i128.

[jlebar]

Call sextOrTrunc instead of assuming the offset constant has the same width as the pointer.

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

707 ↗

(On Diff #116898)

Indeed. Fixed, and added a testcase.

[efriedma]

LGTM

[eastig]

Hi Justin,

This patch has an problem with negative offsets and 32-bit pointers.
Here is a test case:

target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
target triple = "thumbv7em-arm-none-eabi"

define internal void @test(i16* %pOut, i16* %pIn) {
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %pIn.pn45 = phi i16* [ %pIn, %entry ], [ %add.ptr9, %for.body ]
  %i.046 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %pIn.addr.0 = getelementptr inbounds i16, i16* %pIn.pn45, i32 -32
  %0 = load i16, i16* %pIn.pn45, align 2
  store volatile i16 %0, i16* %pOut, align 2
  %add.ptr9 = getelementptr inbounds i16, i16* %pIn.pn45, i32 -64
  %inc = add nsw i32 %i.046, 1
  %cmp = icmp slt i32 %inc, 21
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body
  ret void
}

In armv7m the pointer size is 32-bit. "ConstIdx->getValue().sextOrTrunc(PtrSizeBits) " sets the width to 32. "BaseOffset.getLimitedValue()" calls "APInt::getZExtValue()" which returns a zero extended value. So a negative value is truncated to 32-bit and then zero extended to uint64_t. As a result a wrong value is created.

Run the following in a debugger to reproduce:

opt -loop-unswitch -S test.ll

Thanks,
Evgeny Astigeevich

[jlebar]

Thank you for the detailed bug report, Evgeny, and I'm sorry for the breakage.

I'm able to reproduce, and I've made a failing testcase for Analysis/CostModel/ARM. I'm working on the fix now.

[jlebar]

Fix is out for review in D38557.

[eastig]

Thank you, Justin.

llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h

int getGEPCost(Type *PointeeType, const Value *Ptr,
     if (Ptr != nullptr) {
       // TODO: will remove this when pointers have an opaque type.
       assert(Ptr->getType()->getScalarType()->getPointerElementType() ==
                  PointeeType &&
              "explicit pointee type doesn't match operand's pointee type");
       BaseGV = dyn_cast<GlobalValue>(Ptr->stripPointerCasts());
     }
     bool HasBaseReg = (BaseGV == nullptr);
-    int64_t BaseOffset = 0;
+
+    auto PtrSizeBits = DL.getPointerTypeSizeInBits(Ptr->getType());
+    APInt BaseOffset(PtrSizeBits, 0);
     int64_t Scale = 0;
 
     auto GTI = gep_type_begin(PointeeType, Operands);
     Type *TargetType = nullptr;
 
     // Handle the case where the GEP instruction has a single operand,
     // the basis, therefore TargetType is a nullptr.
     if (Operands.empty())
for (auto I = Operands.begin(); I != Operands.end(); ++I, ++GTI) {
           ConstIdx = dyn_cast<ConstantInt>(Splat);
       if (StructType *STy = GTI.getStructTypeOrNull()) {
         // For structures the index is always splat or scalar constant
         assert(ConstIdx && "Unexpected GEP index");
         uint64_t Field = ConstIdx->getZExtValue();
         BaseOffset += DL.getStructLayout(STy)->getElementOffset(Field);
       } else {
         int64_t ElementSize = DL.getTypeAllocSize(GTI.getIndexedType());
-        if (ConstIdx)
-          BaseOffset += ConstIdx->getSExtValue() * ElementSize;
-        else {
+        if (ConstIdx) {
+          BaseOffset +=
+              ConstIdx->getValue().sextOrTrunc(PtrSizeBits) * ElementSize;
+        } else {
           // Needs scale register.
           if (Scale != 0)
             // No addressing mode takes two scale registers.
             return TTI::TCC_Basic;
           Scale = ElementSize;
         }
       }
     }
 
     // Assumes the address space is 0 when Ptr is nullptr.
     unsigned AS =
         (Ptr == nullptr ? 0 : Ptr->getType()->getPointerAddressSpace());
     if (static_cast<T *>(this)->isLegalAddressingMode(
-            TargetType, const_cast<GlobalValue *>(BaseGV), BaseOffset,
-            HasBaseReg, Scale, AS))
+            TargetType, const_cast<GlobalValue *>(BaseGV),
+            static_cast<int64_t>(BaseOffset.getLimitedValue()), HasBaseReg,
+            Scale, AS))
       return TTI::TCC_Free;
     return TTI::TCC_Basic;
   }
 
   using BaseT::getIntrinsicCost;
 
   unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<const Value *> Arguments) {

llvm/trunk/test/Analysis/CostModel/X86/gep.ll

;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds <4 x i32>, <4 x i32>*
   %a9 = getelementptr inbounds <4 x i32>, <4 x i32>* undef, i32 0
 ;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds <4 x i64>, <4 x i64>*
   %a10 = getelementptr inbounds <4 x i64>, <4 x i64>* undef, i32 0
 ;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds <4 x float>, <4 x float>*
   %a11 = getelementptr inbounds <4 x float>, <4 x float>* undef, i32 0
 ;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds <4 x double>, <4 x double>*
   %a12 = getelementptr inbounds <4 x double>, <4 x double>* undef, i32 0
 
+  ; Check that we handle outlandishly large GEPs properly.  This is unlikely to
+  ; be a valid pointer, but LLVM still generates GEPs like this sometimes in
+  ; dead code.
+  ;
+  ; This GEP has index INT64_MAX, which is cost 1.
+;CHECK: cost of 1 for instruction: {{.*}} getelementptr inbounds i8, i8*
+  %giant_gep0 = getelementptr inbounds i8, i8* undef, i64 9223372036854775807
+
+  ; This GEP index wraps around to -1, which is cost 0.
+;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds i8, i8*
+  %giant_gep1 = getelementptr inbounds i8, i8* undef, i128 295147905179352825855
 
   ret void
 }