Handle big index in getelementptr instruction

[chfast]

Summary

CodeGen incorrectly ignores (assert from APInt) constant index bigger than 2^64 in getelementptr instruction. This is a test and fix for that.

[rnk]

lib/CodeGen/SelectionDAG/FastISel.cpp

500

We usually don't use auto when the type is non-obvious. uint64_t here would help readability.

521

Don't shadow the outer 'I' variable.

521

This sizeof computation doesn't get PtrSize. LLVM is a cross compiler. You can compute it out of the loop.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

3432–3442

Too much auto is bad for readability.

[chfast]

lib/CodeGen/SelectionDAG/FastISel.cpp

521

I don't want a PtrSize, I want TotalOffs size in bits, because I'm going to add to that variable.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

3432–3442

Ok, I will change that, but I don't agree. From my point as a newbie it's better to have auto. Let's look at PtrTy variable: .getPointerTy() method returns value of type MVT and I have no idea that that mean. Moreover, in previous version it was converted implicitly to EVT. I don't care what C++ compiler type PtrTy has, I know it represents a pointer type (the name informs about that) and I want to know its size and create a constant of that type.

[majnemer]

lib/CodeGen/SelectionDAG/FastISel.cpp

521

In that case, please just use 64. LLVM assumes that pointers are not wider than 64-bits.

Is this functionally different from:

CI->getValue().trunc(64).getSExtValue();

?

[chfast]

lib/CodeGen/SelectionDAG/FastISel.cpp

521

It is different. CI->getValue() can be also smaller than i64, e.g i8. We need to sext if smaller, trunc if bigger.

[chfast]

Suggestions from reviewers applied

[rnk]

lgtm, seems reasonable.

[chilledheart]

Hi all,
Just be curious, is this fix to be platform-independent?
After I noticed the testcase is X86-only, I tested X86/getelementptr.ll with more platform+optimization level combinations. There are some crashes:

; RUN: llc < %s -O0 -march=arm64
; RUN: llc < %s -O0 -march=r600

For most of platforms -O2 seem fine, and no crash was found.

Is the result correct or not?

The backtrace of craches are attached below:
-march=arm64

llc: /home/ch/sources-llvm/llvm/include/llvm/ADT/APInt.h:1336: int64_t llvm::APInt::getSExtValue() const: Assertion `getMinSignedBits() <= 64 && "Too many bits for int64_t"' failed.
#0 0x1e5d41e llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/ch/sources-llvm/llvm/lib/Support/Unix/Signals.inc:424:15
#1 0x1e5e399 PrintStackTraceSignalHandler(void*) /home/ch/sources-llvm/llvm/lib/Support/Unix/Signals.inc:483:1
#2 0x1e5e873 SignalHandler(int) /home/ch/sources-llvm/llvm/lib/Support/Unix/Signals.inc:199:60
#3 0x7fc7b90468d0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0xf8d0)
#4 0x7fc7b8286107 gsignal /build/glibc-Ir_s5K/glibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#5 0x7fc7b82874e8 abort /build/glibc-Ir_s5K/glibc-2.19/stdlib/abort.c:91:0
#6 0x7fc7b827f226 __assert_fail_base /build/glibc-Ir_s5K/glibc-2.19/assert/assert.c:92:0
#7 0x7fc7b827f2d2 (/lib/x86_64-linux-gnu/libc.so.6+0x2e2d2)
#8 0x7bd18c llvm::APInt::getSExtValue() const /home/ch/sources-llvm/llvm/include/llvm/ADT/APInt.h:1337:20
#9 0x7d57fc llvm::ConstantInt::getSExtValue() const /home/ch/sources-llvm/llvm/include/llvm/IR/Constants.h:121:5
#10 0x8f4c57 (anonymous namespace)::AArch64FastISel::selectGetElementPtr(llvm::Instruction const*) /home/ch/sources-llvm/llvm/lib/Target/AArch64/AArch64FastISel.cpp:4848:13
#11 0x8b69bb (anonymous namespace)::AArch64FastISel::fastSelectInstruction(llvm::Instruction const*) /home/ch/sources-llvm/llvm/lib/Target/AArch64/AArch64FastISel.cpp:4962:5
#12 0x1c044d9 llvm::FastISel::selectInstruction(llvm::Instruction const*) /home/ch/sources-llvm/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp:1350:7
#13 0x1d0ff12 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) /home/ch/sources-llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1250:13
#14 0x1d0e7ce llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/ch/sources-llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:465:33
#15 0x80e083 (anonymous namespace)::AArch64DAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/ch/sources-llvm/llvm/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp:60:5
#16 0x15df0ce llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/ch/sources-llvm/llvm/lib/CodeGen/MachineFunctionPass.cpp:40:3
#17 0x19b57bd llvm::FPPassManager::runOnFunction(llvm::Function&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1538:23
#18 0x19b5ac8 llvm::FPPassManager::runOnModule(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1558:16
#19 0x19b6189 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1616:23
#20 0x19b5d7e llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1723:16
#21 0x19b6631 llvm::legacy::PassManager::run(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1756:3
#22 0x784e01 compileModule(char**, llvm::LLVMContext&) /home/ch/sources-llvm/llvm/tools/llc/llc.cpp:378:3
#23 0x783c76 main /home/ch/sources-llvm/llvm/tools/llc/llc.cpp:201:13
#24 0x7fc7b8272b45 __libc_start_main /build/glibc-Ir_s5K/glibc-2.19/csu/libc-start.c:321:0
#25 0x783994 _start (/home/ch/build-debug/bin/llc+0x783994)
Stack dump:
0.	Program arguments: /home/ch/build-debug/bin/llc getelementptr.ll -O0 -march=arm64 
1.	Running pass 'Function Pass Manager' on module 'getelementptr.ll'.
2.	Running pass 'AArch64 Instruction Selection' on function '@test_trunc65'

-march=r600

Not Implemented
UNREACHABLE executed at /home/ch/sources-llvm/llvm/lib/Target/R600/AMDGPUInstrInfo.cpp:97!
#0 0x1e5d41e llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/ch/sources-llvm/llvm/lib/Support/Unix/Signals.inc:424:15
#1 0x1e5e399 PrintStackTraceSignalHandler(void*) /home/ch/sources-llvm/llvm/lib/Support/Unix/Signals.inc:483:1
#2 0x1e5e873 SignalHandler(int) /home/ch/sources-llvm/llvm/lib/Support/Unix/Signals.inc:199:60
#3 0x7fc8ff8168d0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0xf8d0)
#4 0x7fc8fea56107 gsignal /build/glibc-Ir_s5K/glibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#5 0x7fc8fea574e8 abort /build/glibc-Ir_s5K/glibc-2.19/stdlib/abort.c:91:0
#6 0x1e0f746 (/home/ch/build-debug/bin/llc+0x1e0f746)
#7 0xf08af8 /home/ch/sources-llvm/llvm/lib/Target/R600/AMDGPUInstrInfo.cpp:97:3
#8 0x168a193 (anonymous namespace)::RAFast::spillVirtReg(llvm::MachineBasicBlock::bundle_iterator<llvm::MachineInstr, llvm::ilist_iterator<llvm::MachineInstr> >, (anonymous namespace)::RAFast::LiveReg*) /home/ch/sources-llvm/llvm/lib/CodeGen/RegAllocFast.cpp:290:5
#9 0x16883ab (anonymous namespace)::RAFast::spillAll(llvm::MachineBasicBlock::bundle_iterator<llvm::MachineInstr, llvm::ilist_iterator<llvm::MachineInstr> >) /home/ch/sources-llvm/llvm/lib/CodeGen/RegAllocFast.cpp:334:16
#10 0x168668a (anonymous namespace)::RAFast::AllocateBasicBlock() /home/ch/sources-llvm/llvm/lib/CodeGen/RegAllocFast.cpp:1067:3
#11 0x1684ba0 (anonymous namespace)::RAFast::runOnMachineFunction(llvm::MachineFunction&) /home/ch/sources-llvm/llvm/lib/CodeGen/RegAllocFast.cpp:1103:5
#12 0x15df0ce llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/ch/sources-llvm/llvm/lib/CodeGen/MachineFunctionPass.cpp:40:3
#13 0x19b57bd llvm::FPPassManager::runOnFunction(llvm::Function&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1538:23
#14 0x19b5ac8 llvm::FPPassManager::runOnModule(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1558:16
#15 0x19b6189 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1616:23
#16 0x19b5d7e llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1723:16
#17 0x19b6631 llvm::legacy::PassManager::run(llvm::Module&) /home/ch/sources-llvm/llvm/lib/IR/LegacyPassManager.cpp:1756:3
#18 0x784e01 compileModule(char**, llvm::LLVMContext&) /home/ch/sources-llvm/llvm/tools/llc/llc.cpp:378:3
#19 0x783c76 main /home/ch/sources-llvm/llvm/tools/llc/llc.cpp:201:13
#20 0x7fc8fea42b45 __libc_start_main /build/glibc-Ir_s5K/glibc-2.19/csu/libc-start.c:321:0
#21 0x783994 _start (/home/ch/build-debug/bin/llc+0x783994)
Stack dump:
0.	Program arguments: /home/ch/build-debug/bin/llc getelementptr.ll -O0 -march=r600 
1.	Running pass 'Function Pass Manager' on module 'getelementptr.ll'.
2.	Running pass 'Fast Register Allocator' on function '@test_trunc65'

[chfast]

The fix was applied to generic CodeGen and is target independent. But it looks like the test case revealed bugs in target-specific code for some other targets. It looks like the crashes discovered are similar to the one I fixed - the assumption that GEP index is never bigger than 64 bit.

I can take a deeper look at that if you want.

[chilledheart]

In D8219#158348, @chfast wrote:

The fix was applied to generic CodeGen and is target independent. But it looks like the test case revealed bugs in target-specific code for some other targets. It looks like the crashes discovered are similar to the one I fixed - the assumption that GEP index is never bigger than 64 bit.

I can take a deeper look at that if you want.

Hi chfast,

These revealed bugs seem probably unrelated with this fix, so we can just submit them into the bugzilla. But if it doesn't take you much time, please go ahead. Anyway, either is fine with me.

Cheers,
Chilledheart

[chfast]

In D8219#158390, @chilledheart wrote:

In D8219#158348, @chfast wrote:

The fix was applied to generic CodeGen and is target independent. But it looks like the test case revealed bugs in target-specific code for some other targets. It looks like the crashes discovered are similar to the one I fixed - the assumption that GEP index is never bigger than 64 bit.

I can take a deeper look at that if you want.

Hi chfast,

These revealed bugs seem probably unrelated with this fix, so we can just submit them into the bugzilla. But if it doesn't take you much time, please go ahead. Anyway, either is fine with me.

Cheers,
Chilledheart

arm64 needs the same fix, see D9140. R600 is different story, probably needs a bug report.

lib/CodeGen/SelectionDAG/FastISel.cpp

bool FastISel::selectGetElementPtr(const User *I) {
   uint64_t MaxOffs = 2048;
   Type *Ty = I->getOperand(0)->getType();
   MVT VT = TLI.getPointerTy();
   for (GetElementPtrInst::const_op_iterator OI = I->op_begin() + 1,
                                             E = I->op_end();
        OI != E; ++OI) {
     const Value *Idx = *OI;
     if (auto *StTy = dyn_cast<StructType>(Ty)) {
-      unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
+      auto Field = cast<ConstantInt>(Idx)->getZExtValue();
       if (Field) {
         // N = N + Offset
         TotalOffs += DL.getStructLayout(StTy)->getElementOffset(Field);
         if (TotalOffs >= MaxOffs) {
           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
           if (!N) // Unhandled operand. Halt "fast" selection and bail.
             return false;
           NIsKill = true;
           TotalOffs = 0;
         }
       }
       Ty = StTy->getElementType(Field);
     } else {
       Ty = cast<SequentialType>(Ty)->getElementType();
 
       // If this is a constant subscript, handle it quickly.
       if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
         if (CI->isZero())
           continue;
         // N = N + Offset
-        TotalOffs +=
-            DL.getTypeAllocSize(Ty) * cast<ConstantInt>(CI)->getSExtValue();
+        auto I = CI->getValue().sextOrTrunc(sizeof(TotalOffs)*8).getSExtValue();
+        TotalOffs += DL.getTypeAllocSize(Ty) * I;
         if (TotalOffs >= MaxOffs) {
           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
           if (!N) // Unhandled operand. Halt "fast" selection and bail.
             return false;
           NIsKill = true;
           TotalOffs = 0;
         }
         continue;

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

if (StructType *StTy = dyn_cast<StructType>(Ty)) {
         uint64_t Offset = DL->getStructLayout(StTy)->getElementOffset(Field);
         N = DAG.getNode(ISD::ADD, getCurSDLoc(), N.getValueType(), N,
                         DAG.getConstant(Offset, N.getValueType()));
       }
 
       Ty = StTy->getElementType(Field);
     } else {
       Ty = cast<SequentialType>(Ty)->getElementType();
+      auto PtrTy = DAG.getTargetLoweringInfo().getPointerTy(AS);
+      auto PtrSize = PtrTy.getSizeInBits();
+      auto ElementSize = APInt{PtrSize, DL->getTypeAllocSize(Ty)};
 
       // If this is a constant subscript, handle it quickly.
-      const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-      if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
-        if (CI->isZero()) continue;
-        uint64_t Offs =
-            DL->getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
-        SDValue OffsVal;
-        EVT PTy = TLI.getPointerTy(AS);
-        unsigned PtrBits = PTy.getSizeInBits();
-        if (PtrBits < 64)
-          OffsVal = DAG.getNode(ISD::TRUNCATE, getCurSDLoc(), PTy,
-                                DAG.getConstant(Offs, MVT::i64));
-        else
-          OffsVal = DAG.getConstant(Offs, PTy);
-
-        N = DAG.getNode(ISD::ADD, getCurSDLoc(), N.getValueType(), N,
-                        OffsVal);
+      if (auto CI = dyn_cast<ConstantInt>(Idx)) {
+        if (CI->isZero())
+          continue;
+        auto Offs = ElementSize * CI->getValue().sextOrTrunc(PtrSize);
+        auto OffsVal = DAG.getConstant(Offs, PtrTy);
+        N = DAG.getNode(ISD::ADD, getCurSDLoc(), N.getValueType(), N, OffsVal);
         continue;
       }
 
       // N = N + Idx * ElementSize;
-      APInt ElementSize =
-          APInt(TLI.getPointerSizeInBits(AS), DL->getTypeAllocSize(Ty));
       SDValue IdxN = getValue(Idx);
 
       // If the index is smaller or larger than intptr_t, truncate or extend
       // it.
       IdxN = DAG.getSExtOrTrunc(IdxN, getCurSDLoc(), N.getValueType());
 
       // If this is a multiply by a power of two, turn it into a shl
       // immediately.  This is a very common case.

test/CodeGen/X86/getelementptr.ll

+; RUN: llc < %s -O0 -march=x86
+; RUN: llc < %s -O0 -march=x86-64
+; RUN: llc < %s -O2 -march=x86
+; RUN: llc < %s -O2 -march=x86-64
+
+
+; Test big index trunc to pointer size:
+
+define i8* @test_trunc65(i8* %ptr) nounwind {
+; CHECK-LABEL: test_trunc65
+; CHECK: 3
+  %d = getelementptr i8, i8* %ptr, i65 18446744073709551619 ; 2^64 + 3
+  ret i8* %d
+}
+
+define i8* @test_trunc128(i8* %ptr) nounwind {
+; CHECK-LABEL: test_trunc128
+; CHECK: 5
+  %d = getelementptr i8, i8* %ptr, i128 18446744073709551621 ; 2^64 + 5
+  ret i8* %d
+}
+
+define i8* @test_trunc160(i8* %ptr) nounwind {
+; CHECK-LABEL: test_trunc160
+; CHECK: 8
+  %d = getelementptr i8, i8* %ptr, i160 18446744073709551624 ; 2^64 + 8
+  ret i8* %d
+}
+
+define i8* @test_trunc256(i8* %ptr) nounwind {
+; CHECK-LABEL: test_trunc256
+; CHECK: 13
+  %d = getelementptr i8, i8* %ptr, i256 18446744073709551629 ; 2^64 + 13
+  ret i8* %d
+}
+
+define i8* @test_trunc2048(i8* %ptr) nounwind {
+; CHECK-LABEL: test_trunc2048
+; CHECK: 21
+  %d = getelementptr i8, i8* %ptr, i2048 18446744073709551637 ; 2^64 + 21
+  ret i8* %d
+}
+
+
+; Test small index sext to pointer size
+
+define i8* @test_sext3(i8* %ptr) nounwind {
+; CHECK-LABEL: test_sext3
+; CHECK: -3
+  %d = getelementptr i8, i8* %ptr, i3 -3
+  ret i8* %d
+}
+
+define i8* @test_sext5(i8* %ptr) nounwind {
+; CHECK-LABEL: test_sext5
+; CHECK: -5
+  %d = getelementptr i8, i8* %ptr, i5 -5
+  ret i8* %d
+}
+
+define i8* @test_sext8(i8* %ptr) nounwind {
+; CHECK-LABEL: test_sext8
+; CHECK: -8
+  %d = getelementptr i8, i8* %ptr, i8 -8
+  ret i8* %d
+}
+
+define i8* @test_sext13(i8* %ptr) nounwind {
+; CHECK-LABEL: test_sext13
+; CHECK: -13
+  %d = getelementptr i8, i8* %ptr, i8 -13
+  ret i8* %d
+}
+
+define i8* @test_sext16(i8* %ptr) nounwind {
+; CHECK-LABEL: test_sext16
+; CHECK: -21
+  %d = getelementptr i8, i8* %ptr, i8 -21
+  ret i8* %d
+}
+