[InstSimplify] Fold insertelement into undef if index is out of bounds

[igor-laevsky]

Summary

This is branched from the D40390.

According to the llvm ir specification insertelement with out of bounds index is undef. This change implements this rule for the InstSimplify. It's mostly valuable as a way to prevent accidental crashes in various passes which are not expecting such indexes.

[igor-laevsky]

Add test case

[spatel]

LGTM.

Note that we should also check if the index itself is 'undef' (similar to D40231), but that may hit the problem described in that review (cc'ing @arsenm @zvi).

Please add a TODO comment for that.

[spatel]

As noted in D40721, we should add a constant folding check to the top of SimplifyInsertElementInst() to avoid a regression in folding an insertelement with all operands constant.
This won't fold directly to a constant for the test in pr28725.ll but rather a constant expression. I think that's ok. Instcombine will manage to fold that further when it does its own constant folding.

[igor-laevsky]

Add constant folding.
This breaks InstSimplify/pr28725.ll. However it's now folded into constant expression and instcombine simplifies it fully. Added relevant test case to the instcombine.

[spatel]

LGTM - see inline comments for some small bits.

lib/Analysis/InstructionSimplify.cpp

3810 ↗

(On Diff #125493)

Nit: period at end of sentence; same for comment below here.

3816 ↗

(On Diff #125493)

Please add a 'TODO' comment about handling an undef index.

test/Transforms/InstCombine/pr28725.ll

3 ↗

(On Diff #125493)

Do we really need to specify a triple and/or datalayout?

[igor-laevsky]

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

[spatel]

For reference, discussion about the failure is going on in the mailing list post-commit thread for r319894:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20171211/509121.html

[igor-laevsky]

Note: This was reintroduced in the rL320568.

llvm/trunk/include/llvm/Analysis/ConstantFolding.h

Constant *ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val,
                                              ArrayRef<unsigned> Idxs);
 
 /// \brief Attempt to constant fold an extractvalue instruction with the
 /// specified operands and indices.  The constant result is returned if
 /// successful; if not, null is returned.
 Constant *ConstantFoldExtractValueInstruction(Constant *Agg,
                                               ArrayRef<unsigned> Idxs);
 
+/// \brief Attempt to constant fold an insertelement instruction with the
+/// specified operands and indices.  The constant result is returned if
+/// successful; if not, null is returned.
+Constant *ConstantFoldInsertElementInstruction(Constant *Val,
+                                               Constant *Elt,
+                                               Constant *Idx);
+
 /// \brief Attempt to constant fold an extractelement instruction with the
 /// specified operands and indices.  The constant result is returned if
 /// successful; if not, null is returned.
 Constant *ConstantFoldExtractElementInstruction(Constant *Val, Constant *Idx);
 
 /// \brief Attempt to constant fold a shufflevector instruction with the
 /// specified operands and indices.  The constant result is returned if
 /// successful; if not, null is returned.

llvm/trunk/include/llvm/Analysis/InstructionSimplify.h

 /// Given operands for a GetElementPtrInst, fold the result or return null.
 Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
                        const SimplifyQuery &Q);
 
 /// Given operands for an InsertValueInst, fold the result or return null.
 Value *SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs,
                                const SimplifyQuery &Q);
 
+/// Given operands for an InsertElement, fold the result or return null.
+Value *SimplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx,
+                                 const SimplifyQuery &Q);
+
 /// Given operands for an ExtractValueInst, fold the result or return null.
 Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
                                 const SimplifyQuery &Q);
 
 /// Given operands for an ExtractElementInst, fold the result or return null.
 Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
                                   const SimplifyQuery &Q);
 

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

 }
 
 Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
                                      ArrayRef<unsigned> Idxs,
                                      const SimplifyQuery &Q) {
   return ::SimplifyInsertValueInst(Agg, Val, Idxs, Q, RecursionLimit);
 }
 
+Value *llvm::SimplifyInsertElementInst(Value *Vec, Value *Val, Value *Idx,
+                                       const SimplifyQuery &Q) {
+  // Try to constant fold.
+  auto *VecC = dyn_cast<Constant>(Vec);
+  auto *ValC = dyn_cast<Constant>(Val);
+  auto *IdxC = dyn_cast<Constant>(Idx);
+  if (VecC && ValC && IdxC)
+    return ConstantFoldInsertElementInstruction(VecC, ValC, IdxC);
+
+  // Fold into undef if index is out of bounds.
+  if (auto *CI = dyn_cast<ConstantInt>(Idx)) {
+    uint64_t NumElements = cast<VectorType>(Vec->getType())->getNumElements();
+
+    if (CI->uge(NumElements))
+      return UndefValue::get(Vec->getType());
+  }
+
+  // TODO: We should also fold if index is iteslf an undef.
+
+  return nullptr;
+}
+
 /// Given operands for an ExtractValueInst, see if we can fold the result.
 /// If not, this returns null.
 static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
                                        const SimplifyQuery &, unsigned) {
   if (auto *CAgg = dyn_cast<Constant>(Agg))
     return ConstantFoldExtractValueInstruction(CAgg, Idxs);
 
   // extractvalue x, (insertvalue y, elt, n), n -> elt
Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
   }
   case Instruction::InsertValue: {
     InsertValueInst *IV = cast<InsertValueInst>(I);
     Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
                                      IV->getInsertedValueOperand(),
                                      IV->getIndices(), Q);
     break;
   }
+  case Instruction::InsertElement: {
+    auto *IE = cast<InsertElementInst>(I);
+    Result = SimplifyInsertElementInst(IE->getOperand(0), IE->getOperand(1),
+                                       IE->getOperand(2), Q);
+    break;
+  }
   case Instruction::ExtractValue: {
     auto *EVI = cast<ExtractValueInst>(I);
     Result = SimplifyExtractValueInst(EVI->getAggregateOperand(),
                                       EVI->getIndices(), Q);
     break;
   }
   case Instruction::ExtractElement: {
     auto *EEI = cast<ExtractElementInst>(I);

llvm/trunk/test/Transforms/InstSimplify/pr28725.ll

 ; RUN: opt -S -instsimplify < %s | FileCheck %s
-target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-pc-windows-msvc"
 %S = type { i16, i32 }
 
 define <2 x i16> @test1() {
 entry:
   %b = insertelement <2 x i16> <i16 undef, i16 0>, i16 extractvalue (%S select (i1 icmp eq (i16 extractelement (<2 x i16> bitcast (<1 x i32> <i32 1> to <2 x i16>), i32 0), i16 0), %S zeroinitializer, %S { i16 0, i32 1 }), 0), i32 0
   ret <2 x i16> %b
 }
 
+; InstCombine will be able to fold this into zeroinitializer
 ; CHECK-LABEL: @test1(
-; CHECK: ret <2 x i16> zeroinitializer
+; CHECK: ret <2 x i16> <i16 extractvalue (%S select (i1 icmp eq (i16 extractelement (<2 x i16> bitcast (<1 x i32> <i32 1> to <2 x i16>), i32 0), i16 0), %S zeroinitializer, %S { i16 0, i32 1 }), 0), i16 0>