[SLP] Fix PR38339: Instruction does not dominate all uses!

[ABataev]

Summary

If the ExtractElement instructions can be optimized out during the
vectorization and we need to reshuffle the parent vector, this
ShuffleInstruction may be inserted in the wrong place causing compiler
to produce incorrect code.

[spatel]

Someone more familiar with SLP should take a look, but this seems ok to me.

The testcase can be simplified to a single BB:

define void @f1(<2 x i16> %x, i16* %a) {
  %t2 = extractelement <2 x i16> %x, i32 0
  %t3 = extractelement <2 x i16> %x, i32 1
  %ptr0 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 0
  %ptr1 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 1
  %ptr2 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 2
  %ptr3 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 3
  store i16 %t2, i16* %a
  store i16 %t2, i16* %ptr0
  store i16 %t3, i16* %ptr1
  store i16 %t3, i16* %ptr2
  store i16 %t2, i16* %ptr3
  ret void
}

[RKSimon]

LGTM with @spatel test simplification

[efriedma]

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

3116

I don't think std::next(I->getIterator()) is a valid insertion point in all cases. V could be a phi, or an invoke, or some exception-handling instruction.

[efriedma]

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

3119

Also, you can't just stick the instruction at the beginning of the function in this case; it's illegal to hoist a reference to a canTrap() constant.

[ABataev]

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

3116

What if something like this:

auto It = std::next(I->getIterator());
for (auto E = I->getParent()->end(); It != E; ++It) {
  if (!isa<PHINode>(&*It)) {
    if (It->isEHPad())
      ++It;
    break; 
  }
}
Builder.SetInsertPoint(I->getParent(), It);

?

[efriedma]

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

3116

That doesn't really help... among other things, there are some blocks which have no legal insertion points.

Maybe there's some constraint on SLP vectorization which would help choose a better insertion point? Why can't we just use VL0 as the insertion point?

[ABataev]

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

3116

Yes, maybe that's the best option here. Will fix this.

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::ExtractElement: {
           Builder.SetInsertPoint(VL0);
           V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy), Mask,
                                           "reorder_shuffle");
         }
         if (NeedToShuffleReuses) {
           // TODO: Merge this shuffle with the ReorderShuffleMask.
           if (!E->ReorderIndices.empty())
             Builder.SetInsertPoint(VL0);
+          else if (auto *I = dyn_cast<Instruction>(V))
+            Builder.SetInsertPoint(I->getParent(),
+                                   std::next(I->getIterator()));
+          else
+            Builder.SetInsertPoint(&F->getEntryBlock(),
+                                   F->getEntryBlock().getFirstInsertionPt());
           V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                           E->ReuseShuffleIndices, "shuffle");
         }
         E->VectorizedValue = V;
         return V;
       }
       setInsertPointAfterBundle(E->Scalars, S);
       auto *V = Gather(E->Scalars, VecTy);

llvm/trunk/test/Transforms/SLPVectorizer/AArch64/PR38339.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -slp-vectorizer -S -mtriple=aarch64-apple-ios -mcpu=cyclone -o - %s | FileCheck %s
+
+define void @f1(<2 x i16> %x, i16* %a) {
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i16> [[X:%.*]], <2 x i16> undef, <4 x i32> <i32 0, i32 1, i32 1, i32 0>
+; CHECK-NEXT:    [[PTR0:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 0
+; CHECK-NEXT:    [[PTR1:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 1
+; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 2
+; CHECK-NEXT:    [[PTR3:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 3
+; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <4 x i16> [[SHUFFLE]], i32 0
+; CHECK-NEXT:    store i16 [[TMP1]], i16* [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i16* [[PTR0]] to <4 x i16>*
+; CHECK-NEXT:    store <4 x i16> [[SHUFFLE]], <4 x i16>* [[TMP2]], align 2
+; CHECK-NEXT:    ret void
+;
+  %t2 = extractelement <2 x i16> %x, i32 0
+  %t3 = extractelement <2 x i16> %x, i32 1
+  %ptr0 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 0
+  %ptr1 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 1
+  %ptr2 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 2
+  %ptr3 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 3
+  store i16 %t2, i16* %a
+  store i16 %t2, i16* %ptr0
+  store i16 %t3, i16* %ptr1
+  store i16 %t3, i16* %ptr2
+  store i16 %t2, i16* %ptr3
+  ret void
+}