Fix the trunc instruction insertion problem in SLP pass

[bule]

Summary

Current SLP pass has this piece of code that inserts a trunc instruction after the vectorized instruction. In the case that the vectorized instruction is a phi node and not the last phi node in the BB, the trunc instruction will be inserted between two phi nodes, which will trigger verify problem in debug version or unpredictable error in another pass. See the testcase in the patch as an example. Try remove the -disable-verify option for the verify error.

This patch changes the algorithm to 'if the last vectorized instruction is a phi, insert it after the last phi node in current BB' to fix this problem.

[RKSimon]

Please can you regenerate the diff with context (git diff -U9999) ?

[anton-afanasyev]

Also could you please precommit test or just make diff against it (to see test changes before/after patch)?

[RKSimon]

In D98423#2619877, @anton-afanasyev wrote:

Also could you please precommit test or just make diff against it (to see test changes before/after patch)?

AFAICT the test currently crashes

[bule]

In D98423#2621666, @RKSimon wrote:

In D98423#2619877, @anton-afanasyev wrote:

Also could you please precommit test or just make diff against it (to see test changes before/after patch)?

AFAICT the test currently crashes

https://reviews.llvm.org/D98596 , pre-commit patch added

[bule]

add -U9999 diff patch and the change after the pre-commit patch

[bule]

In D98423#2619639, @RKSimon wrote:

Please can you regenerate the diff with context (git diff -U9999) ?

regenerated with pre-commit change. Updated.

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4915

isa<PHINode>(I)

[bjope]

llvm/test/Transforms/SLPVectorizer/AArch64/trunc-insertion.ll

1–2

I figure the idea is that -disable-verify can be removed in this patch.

[bule]

Use the isa function to check the phi node and remove the -disable-verify option in the testcase.

[anton-afanasyev]

LGTM

[bule]

The previous testcase didn't pass the pre-merge check because an element is duplicated. The precommit test case have been changed. This patch fix the problem along with the pre-commit patch.

[bule]

@anton-afanasyev Anton, you might need to help me merge this one as well.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4915

done

llvm/test/Transforms/SLPVectorizer/AArch64/trunc-insertion.ll

1–2

@anton-afanasyev what do you think?

1–2

Remove the -disable-verify option could make the result check more strict. So removed.

[anton-afanasyev]

llvm/test/Transforms/SLPVectorizer/AArch64/trunc-insertion.ll

1–2

Looks good.

[anton-afanasyev]

Closed by commit: https://reviews.llvm.org/rG9abe50047330
(modified summary a bit to comply with changes)

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

BoUpSLP::vectorizeTree(ExtraValueToDebugLocsMap &ExternallyUsedValues) {
   Builder.SetInsertPoint(&F->getEntryBlock().front());
   auto *VectorRoot = vectorizeTree(VectorizableTree[0].get());
 
   // If the vectorized tree can be rewritten in a smaller type, we truncate the
   // vectorized root. InstCombine will then rewrite the entire expression. We
   // sign extend the extracted values below.
   auto *ScalarRoot = VectorizableTree[0]->Scalars[0];
   if (MinBWs.count(ScalarRoot)) {
-    if (auto *I = dyn_cast<Instruction>(VectorRoot))
+    if (auto *I = dyn_cast<Instruction>(VectorRoot)) {
+      // If current instr is a phi and not the last phi, insert it after the
+      // last phi node.
+      if (isa<PHINode>(I))
+        Builder.SetInsertPoint(&*I->getParent()->getFirstInsertionPt());
+      else
         Builder.SetInsertPoint(&*++BasicBlock::iterator(I));
+    }
     auto BundleWidth = VectorizableTree[0]->Scalars.size();
     auto *MinTy = IntegerType::get(F->getContext(), MinBWs[ScalarRoot].first);
     auto *VecTy = FixedVectorType::get(MinTy, BundleWidth);
     auto *Trunc = Builder.CreateTrunc(VectorRoot, VecTy);
     VectorizableTree[0]->VectorizedValue = Trunc;
   }
 
   LLVM_DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size()

llvm/test/Transforms/SLPVectorizer/AArch64/trunc-insertion.ll

-;RUN: opt < %s -disable-verify -slp-vectorizer -S | FileCheck %s
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+;RUN: opt < %s -slp-vectorizer -S | FileCheck %s
 target triple = "aarch64-unknown-linux-gnu"
 @d = internal unnamed_addr global i32 5, align 4
 
 define dso_local void @l() local_unnamed_addr {
 ; CHECK-LABEL: @l(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i16> [ undef, [[BB:%.*]] ], [ [[TMP12:%.*]], [[BB25:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i16> [ undef, [[BB:%.*]] ], [ [[TMP11:%.*]], [[BB25:%.*]] ]
 ; CHECK-NEXT:    br i1 undef, label [[BB3:%.*]], label [[BB11:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[I4:%.*]] = zext i1 undef to i32
 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i16> [[TMP0]], undef
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt <2 x i16> [[TMP1]], <i16 8, i16 8>
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i1> [[TMP2]] to <2 x i32>
 ; CHECK-NEXT:    br label [[BB25]]
 ; CHECK:       bb11:
 ; CHECK-NEXT:    [[I12:%.*]] = zext i1 undef to i32
 ; CHECK-NEXT:    [[TMP4:%.*]] = xor <2 x i16> [[TMP0]], undef
 ; CHECK-NEXT:    [[TMP5:%.*]] = sext <2 x i16> [[TMP4]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule <2 x i64> undef, [[TMP5]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = zext <2 x i1> [[TMP6]] to <2 x i32>
 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp ult <2 x i32> undef, [[TMP7]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = zext <2 x i1> [[TMP8]] to <2 x i32>
 ; CHECK-NEXT:    br label [[BB25]]
 ; CHECK:       bb25:
 ; CHECK-NEXT:    [[I28:%.*]] = phi i32 [ [[I12]], [[BB11]] ], [ [[I4]], [[BB3]] ]
 ; CHECK-NEXT:    [[TMP10:%.*]] = phi <2 x i32> [ [[TMP9]], [[BB11]] ], [ [[TMP3]], [[BB3]] ]
-; CHECK-NEXT:    [[TMP11:%.*]] = trunc <2 x i32> [[TMP10]] to <2 x i8>
-; CHECK-NEXT:    [[TMP12]] = phi <2 x i16> [ [[TMP4]], [[BB11]] ], [ [[TMP1]], [[BB3]] ]
-; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <2 x i8> [[TMP11]], i32 0
+; CHECK-NEXT:    [[TMP11]] = phi <2 x i16> [ [[TMP4]], [[BB11]] ], [ [[TMP1]], [[BB3]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = trunc <2 x i32> [[TMP10]] to <2 x i8>
+; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <2 x i8> [[TMP12]], i32 0
 ; CHECK-NEXT:    [[TMP14:%.*]] = zext i8 [[TMP13]] to i32
 ; CHECK-NEXT:    [[I31:%.*]] = and i32 undef, [[TMP14]]
-; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <2 x i8> [[TMP11]], i32 1
+; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <2 x i8> [[TMP12]], i32 1
 ; CHECK-NEXT:    [[TMP16:%.*]] = zext i8 [[TMP15]] to i32
 ; CHECK-NEXT:    [[I32:%.*]] = and i32 [[I31]], [[TMP16]]
 ; CHECK-NEXT:    [[I33:%.*]] = and i32 [[I32]], [[I28]]
 ; CHECK-NEXT:    br i1 undef, label [[BB34:%.*]], label [[BB1]]
 ; CHECK:       bb34:
 ; CHECK-NEXT:    [[I35:%.*]] = phi i32 [ [[I33]], [[BB25]] ]
 ; CHECK-NEXT:    br label [[BB36:%.*]]
 ; CHECK:       bb36: