This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by igor-laevsky on Nov 23 2017, 6:18 AM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

igor-laevsky created this revision.Nov 23 2017, 6:18 AM
spatel edited edge metadata.Nov 27 2017, 9:05 AM

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 retitled this revision from [InstCombine] Don't crash on unreasonable constant indexes to [InstCombine] Don't crash on out of bounds index in the insertelement.

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.

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.

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

spatel added inline comments.Nov 30 2017, 8:16 AM
test/Transforms/InstCombine/out-of-bounds-indexes.ll
1 ↗(On Diff #124941)

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 added inline comments.Nov 30 2017, 8:32 AM
lib/Transforms/InstCombine/InstCombineVectorOps.cpp
790 ↗(On Diff #124941)

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).

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

lib/Transforms/InstCombine/InstCombineVectorOps.cpp
790 ↗(On Diff #124941)

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 added a comment.Dec 1 2017, 9:48 AM

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

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

Updated with reduced test case

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

spatel accepted this revision.Dec 7 2017, 6:25 AM

LGTM.

This revision is now accepted and ready to land.Dec 7 2017, 6:25 AM
This revision was automatically updated to reflect the committed changes.

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

Note: This was reintroduced in the rL320568.