[InstCombine] Don't crash on out of bounds index in the insertelement

[igor-laevsky]

Summary

This is couple of minor fixes inspired by the llvm-opt-fuzzer. Even though they are not practically important, they come up often during the fuzzing runs and may clobber other issues.

Crashes happen when constant index of some instruction has unreasonable value (i.e out of bounds indexes for insertelement). Even though it's usually undefined behaviour we still can't crash the compiler.

I suspect there might be more of a similar issues, but these are all I have noticed so far.

[spatel]

I agree that we can't let these cases cause a crash, but this is at least 2 independent patches.

Let's handle the insertelement case first. The LangRef says:
"If idx exceeds the length of val, the results are undefined."
http://llvm.org/docs/LangRef.html#insertelement-instruction

So let's add a fold for that to InstSimplify, and we don't have to deal with it in InstCombine?

[igor-laevsky]

Hi Sanjay, thanks for the comments.

Updating InstSimplify is a reasonable thing to do, however it doesn't prevent instcombine from crashing. I believe we should do both changes.

I splited checks for shift operations into separate review thread: https://reviews.llvm.org/D40649 (by the way, there is InstSimplify rule for them already)

InstSimplify rule for the InsertElement is also in the separate review thread: https://reviews.llvm.org/D40650

And this review thread is now about instcombine crash specifically in the insertelement instruction with out of bounds index.

[spatel]

In D40390#940459, @igor-laevsky wrote:

Hi Sanjay, thanks for the comments.

Updating InstSimplify is a reasonable thing to do, however it doesn't prevent instcombine from crashing. I believe we should do both changes.

I splited checks for shift operations into separate review thread: https://reviews.llvm.org/D40649 (by the way, there is InstSimplify rule for them already)

InstSimplify rule for the InsertElement is also in the separate review thread: https://reviews.llvm.org/D40650

And this review thread is now about instcombine crash specifically in the insertelement instruction with out of bounds index.

Thanks for splitting things up.

You are correct that we still need an InstCombine change to avoid the crash, but it's different than what you have here currently. The problem is that we're not calling the new InstSimplify function at the start of InstCombiner::visitInsertElementInst().

It's standard practice in InstCombine to call the corresponding simplification routine for that opcode before trying other folds.

For example, the first thing we do for extractelement is:

Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
  if (Value *V = SimplifyExtractElementInst(EI.getVectorOperand(),
                                            EI.getIndexOperand(),
                                            SQ.getWithInstruction(&EI)))
    return replaceInstUsesWith(EI, V);

Now that we have an InstSimplify routine for the InsertElement opcode, we should call that function first. That avoids any crash potential from a bogus index value in InstCombine because we'll produce an undef and bail out. If you want to add that diff to D40650, I think that would be fine, or we can leave it here as a separate patch with test case.

[igor-laevsky]

Thanks, this way is a lot better. Updated the diff.

[spatel]

test/Transforms/InstCombine/out-of-bounds-indexes.ll

8–1

I know we're just making sure that we don't crash here, but I prefer to still run FileCheck and add check lines using /utils/update_test_checks.py, so we know what's actually coming out of instcombine.

Also, we can shrink both of these tests a bit to just focus on the bad instructions:

define i32 @lshr_bad_shift_amount(i32 %a) {
  %B = lshr i32 %a, 33
  %cmp = icmp eq i32 %B, 1
  tail call void @llvm.assume(i1 %cmp)
  ret i32 %B
}

define <4 x double> @inselt_bad_index(<4 x double> %a) {
  %I = insertelement <4 x double> %a, double 0.0, i64 4294967296
  ret <4 x double> %I
}

[spatel]

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

789

Maybe off-topic for this patch thread, but since we're cleaning this all up (thanks!), we should fix this line as mentioned in D40231 / D40650. If the index is undef, then we can return undef rather than VecOp (and it should happen in InstSimplify, not here).

[igor-laevsky]

Seems like I can't make tests any smaller because they need to trigger specific patterns in the instcombine

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

789

Yes, that makes sense. I suspect this might be already covered by the D40721. In any case I will send separate review for this.

[spatel]

I may be confused by the incremental diffs in these reviews, but we can minimize the insertelement test to just one line and still crash trunk:

$ cat inselt.ll

define <4 x double> @inselt_bad_index(<4 x double> %a) {
%I = insertelement <4 x double> %a, double 0.0, i64 4294967296
ret <4 x double> %I
}

$ ./opt -instcombine inselt.ll -S
Assertion failed: (idx < size()), function operator[], file /Users/spatel/myllvm/llvm/include/llvm/ADT/SmallVector.h, line 149.
0 opt 0x0000000112a576bc llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 60
1 opt 0x0000000112a57cb9 PrintStackTraceSignalHandler(void*) + 25
2 opt 0x0000000112a53749 llvm::sys::RunSignalHandlers() + 425
3 opt 0x0000000112a58072 SignalHandler(int) + 354
4 libsystem_platform.dylib 0x00007fff5d2eaf5a _sigtramp + 26
5 libsystem_platform.dylib 000000000000000000 _sigtramp + 2731626688
6 libsystem_c.dylib 0x00007fff5d11630a abort + 127
7 libsystem_c.dylib 0x00007fff5d0de360 basename_r + 0
8 opt 0x00000001122abdeb foldInsSequenceIntoBroadcast(llvm::InsertElementInst&) + 603
9 opt 0x00000001122a94e0 llvm::InstCombiner::visitInsertElementInst(llvm::InsertElementInst&) + 1664
10 opt 0x00000001121e82a8 llvm::InstVisitor<llvm::InstCombiner, llvm::Instruction*>::visitInsertElement(llvm::InsertElementInst&) + 40
11 opt 0x00000001121d9872 llvm::InstVisitor<llvm::InstCombiner, llvm::Instruction*>::visit(llvm::Instruction&) + 1762
12 opt 0x00000001121d8b19 llvm::InstCombiner::run() + 2569
13 opt 0x00000001121da07f combineInstructionsOverFunction(llvm::Function&, llvm::InstCombineWorklist&, llvm::AAResults*, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::DominatorTree&, llvm::OptimizationRemarkEmitter&, bool, llvm::LoopInfo*) + 1007
14 opt 0x00000001121da306 llvm::InstructionCombiningPass::runOnFunction(llvm::Function&) + 342
15 opt 0x0000000111e7bf8f llvm::FPPassManager::runOnFunction(llvm::Function&) + 399
16 opt 0x0000000111e7c495 llvm::FPPassManager::runOnModule(llvm::Module&) + 117
17 opt 0x0000000111e7d264 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) + 2196
18 opt 0x0000000111e7c756 llvm::legacy::PassManagerImpl::run(llvm::Module&) + 342
19 opt 0x0000000111e7dfb1 llvm::legacy::PassManager::run(llvm::Module&) + 33
20 opt 0x000000010f8f58fc main + 27756
21 libdyld.dylib 0x00007fff5d06a145 start + 1
Stack dump:
0. Program arguments: ./opt -instcombine inselt.ll -S

1. Running pass 'Function Pass Manager' on module 'inselt.ll'.
2. Running pass 'Combine redundant instructions' on function '@inselt_bad_index'

Abort trap: 6

[igor-laevsky]

I must have confused something when doing reduction. Will update tests. Thanks.

[igor-laevsky]

Updated with reduced test case

[igor-laevsky]

Hi Sanjay, since D40650 is submitted, is this good to go?

[spatel]

LGTM.

[igor-laevsky]

Note: this was reverted due to the OpenGL mesa tests failures (rL320466)

[igor-laevsky]

Note: This was reintroduced in the rL320568.

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
   return nullptr;
 }
 
 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
   Value *VecOp    = IE.getOperand(0);
   Value *ScalarOp = IE.getOperand(1);
   Value *IdxOp    = IE.getOperand(2);
 
+  if (auto *V = SimplifyInsertElementInst(
+          VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
+    return replaceInstUsesWith(IE, V);
+
   // Inserting an undef or into an undefined place, remove this.
   if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
     replaceInstUsesWith(IE, VecOp);
 
   // If the inserted element was extracted from some other vector, and if the
   // indexes are constant, try to turn this into a shufflevector operation.
   if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
     if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
       unsigned NumInsertVectorElts = IE.getType()->getNumElements();
       unsigned NumExtractVectorElts =

test/Transforms/InstCombine/out-of-bounds-indexes.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 ; Check that we don't crash on unreasonable constant indexes
 
 define i32 @test_out_of_bounds(i32 %a, i1 %x, i1 %y) {
 ; CHECK-LABEL: @test_out_of_bounds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], 3
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 false)
;
   %and1 = and i128 %a, 3
   %B = lshr i128 %and1, -1
   %cmp = icmp eq i128 %B, 1
   tail call void @llvm.assume(i1 %cmp)
   ret i128 %and1
 }
 
 declare void @llvm.assume(i1)
+
+define <4 x double> @inselt_bad_index(<4 x double> %a) {
+; CHECK-LABEL: @inselt_bad_index(
+; CHECK-NEXT:    ret <4 x double> undef
+;
+  %I = insertelement <4 x double> %a, double 0.0, i64 4294967296
+  ret <4 x double> %I
+}

test/Transforms/InstCombine/vector_insertelt_shuffle.ll

;
   %ins2 = insertelement<4 x float> %ins1, float 5.0, i32 %a
   %ins3 = insertelement<4 x float> %ins2, float 3.0, i32 2
   %ins4 = insertelement<4 x float> %ins3, float 1.0, i32 1
   %ins5 = insertelement<4 x float> %ins4, float 2.0, i32 2
   %ins6 = insertelement<4 x float> %ins5, float 7.0, i32 %a
   ret <4 x float> %ins6
 }
 
+; Out of bounds index folds to undef
 define <4 x float> @bazzz(<4 x float> %x) {
 ; CHECK-LABEL: @bazzz(
-; CHECK-NEXT:    [[INS2:%.*]] = insertelement <4 x float> %x, float 2.000000e+00, i32 2
-; CHECK-NEXT:    ret <4 x float> [[INS2]]
+; CHECK-NEXT:   ret <4 x float> <float undef, float undef, float 2.000000e+00, float undef>
 ;
   %ins1 = insertelement<4 x float> %x, float 1.0, i32 5
   %ins2 = insertelement<4 x float> %ins1, float 2.0, i32 2
   ret <4 x float> %ins2
 }
 
 define <4 x float> @bazzzz(<4 x float> %x) {
 ; CHECK-LABEL: @bazzzz(