[SLP] Initialize VectorizedValue when gathering

[mssimpso]

Summary

We abort building vectorizable trees in some cases (e.g., if the maximum recursion depth is reached, if the region size is too large, etc.). If this happens for a reduction, we can be left with a root entry that needs to be gathered. For these cases, we need make sure we actually set VectorizedValue to the resulting vector.

This patch ensures we properly set VectorizedValue and it also ensures the insertelement sequence generated for the gathers is inserted at the correct location (after the last instruction in the bundle). Please let me know what you think.

Reference: https://llvm.org/bugs/show_bug.cgi?id=28330

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2174

Just to make sure I understand this correctly - you're running from Leader, inclusive, so that if VL[0] is the last instruction in program order, you'll end up with LastInst == Leader, right?
If so, it's probably worth a comment - or just initialize LastInst to Leader instead of null.

Also, won't we get worst-case quardatic behavior here, if VL[0] is consistently last (so we end up running to the end of the block for each bundle)?

[mssimpso]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2174

Right, if VL[0] is consistently last, we'll end up running to the end of the block a lot. I think the common case here should be that VL[0] is first in program order? (But I could be wrong about this). Is there a better way to do this? setInsertPointAfterBundle doesn't really work as expected.

For this particular bug, another way to fix the insertion issue might be to modify Gather to change the insert point before generating each insertlement instruction. What do you think?

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2174

I agree, the common case is that VL[0] is first - but there are at least two cases where it may be last:

1. For reductions, we may end up collecting things in reverse order (that is, VL[0] ought to be first, but it ends up last).
2. If the root if a bundle of stores, we'll sort the bundle so that consecutive stores in the bundle have consecutive pointers.

And changing the order of the root bundle affects the order of all bundles in the tree, since the lanes have to be consistent, so having things in reversed order propagates.

I think changing the insertion point before generating each insertelement instruction doesn't really solve the problem even for gathers, because the inserts need to be in the bundle order (they form a use-def chain), so we can't just put every insert after its VL[i].

I don't have a good solution off the top of my head, though.

[mssimpso]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2174

I think changing the insertion point before generating each insertelement instruction doesn't really solve the problem even for gathers, because the inserts need to be in the bundle order (they form a use-def chain), so we can't just put every insert after its VL[i].

OK, right. This won't work.

I'm now thinking that it may be possible to use ScheduleData for this. I'll give it a shot.

[mssimpso]

Addressed Michael's comments.

• Added more details in comments
• Used ScheduleData to optimize the common case. This prevents us from always iterating over all instructions in the block.

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2178

Could you please change this to be something like

} else {
 // If BB hasn't...
...
}

?

The dangling else really bugs me. :-)

2178

Also, how can it happen that the BB hasn't been scheduled?
I thought this only gets called from within vectorizeTree(), which calls scheduleBlock() first?

[mssimpso]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2178

No problem!

2178

That's a good question... For the test case, an entry for BB is never created in BlocksSchedules because buildTree_rec exits early (max recursion depth). The BlocksSchedules entry isn't created until later on in the function, right before the "practice" scheduling. In vectorizeTree, the "real" scheduling only happens for the blocks in BlocksSchedules.

I bet if we move the BlockSchedules entry creation to the top of buildTree_rec, we can eliminate the "else" block here. I'll update the patch. Thanks!

[mssimpso]

Addressed Michael's comments.

Michael,

I'm not sure we can avoid the "else" block like I previously guessed we might. We can end up with uninitialized schedule data if we exit early from buildTree_rec (in addition to a missing entry in BlocksSchedules). I've detailed the cases in the new comments I added. The "else" block is replaced by a new "if" to check for the null schedule data case.

Iterating over the block to find the insert point should be extremely rare I think, and probably only happens in exceptional cases such as the one demonstrated in the test case where we hit some hard limit and give up building the tree. I tested the current patch on the test suite and spec2000/2006, and we didn't have to iterate over the block a single time.

[mkuper]

I'm still slightly concerned. One of the reasons we'd bail out of buildTree_rec is if we hit one of the thresholds - whose only reason to exist in the first place is to provide an upper bound on compile time. So if bailing out of buildTree_rec because we exceeded a threshold causes us to take a compile-time hit, that's probably not good.
But I may just be paranoid - we'll take a hit only if we both exceeded the thresholds *and* the bundle is not in-order, and that may be extremely rare.

Other than that, LGTM.

[mssimpso]

Thanks, Michael.

It looks like we used to number the instructions in the block, and then use the numbering for this purpose. There was even a "getLastInstruction(ArrayRef<Value *> VL)" but this was all removed in rL214494.

Matt.

[mssimpso]

Erik, do you have any thoughts on this change? Thanks!

[hans]

This is now the final release-blocking PR for 3.9. No pressure :-)

[mssimpso]

If there are no objections then, I'll commit this patch with Michael's LGTM to unblock the release. I'll also add a comment describing Michael's compile-time reservations.

[hans]

In D23410#519403, @mssimpso wrote:

If there are no objections then, I'll commit this patch with Michael's LGTM to unblock the release. I'll also add a comment describing Michael's compile-time reservations.

Sounds good to me.

[mssimpso]

Committed in rL279125.

[vitalybuka]

Reverted by r279363

[mssimpso]

Reapplied in rL279369 and rL279370 with a change to the test case that avoids hitting the unsigned behavior. The unsigned behavior will be addressed in D23723.

lib/Transforms/Vectorize/SLPVectorizer.cpp

if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
         }
       }
     }
     // else unchanged
   }
 }
 
 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) {
-  Instruction *VL0 = cast<Instruction>(VL[0]);
-  BasicBlock::iterator NextInst(VL0);
-  ++NextInst;
-  Builder.SetInsertPoint(VL0->getParent(), NextInst);
-  Builder.SetCurrentDebugLocation(VL0->getDebugLoc());
+
+  // Get the basic block this bundle is in. All instructions in the bundle
+  // should be in this block.
+  auto *Front = cast<Instruction>(VL.front());
+  auto *BB = Front->getParent();
+  assert(all_of(make_range(VL.begin(), VL.end()), [&](Value *V) -> bool {
+    return cast<Instruction>(V)->getParent() == BB;
+  }));
+
+  // The last instruction in the bundle in program order.
+  Instruction *LastInst = nullptr;
+
+  // Find the last instruction. The common case should be that BB has been
+  // scheduled, and the last instruction is VL.back(). So we start with
+  // VL.back() and iterate over schedule data until we reach the end of the
+  // bundle. The end of the bundle is marked by null ScheduleData.
+  if (BlocksSchedules.count(BB)) {
+    auto &BS = BlocksSchedules[BB];
+    for (auto *SD = BS->getScheduleData(VL.back()); SD; SD = SD->NextInBundle)
+      LastInst = SD->Inst;
+  }
+
+  // LastInst can still be null at this point if there's either not an entry
+  // for BB in BlocksSchedules or there's no ScheduleData available for
+  // VL.back(). This can be the case if buildTree_rec aborts for various
+  // reasons (e.g., the maximum recursion depth is reached, the maximum region
+  // size is reached, etc.). ScheduleData is initialized in the scheduling
+  // "dry-run".
+  //
+  // If this happens, we can still find the last instruction by brute force. We
+  // iterate forwards from Front (inclusive) until we either see all
+  // instructions in the bundle or reach the end of the block. If Front is the
+  // last instruction in program order, LastInst will be set to Front, and we
+  // will visit all the remaining instructions in the block
+  if (!LastInst) {
+    SmallPtrSet<Value *, 16> Bundle(VL.begin(), VL.end());
+    auto ForwardStart = BasicBlock::iterator(Front);
+    for (auto &I : make_range(ForwardStart, BB->end())) {
+      if (Bundle.erase(&I))
+        LastInst = &I;
+      if (Bundle.empty())
+        break;
+    }
+  }
+
+  // Set the insertion point after the last instruction in the bundle. Set the
+  // debug location to Front.
+  Builder.SetInsertPoint(BB, next(BasicBlock::iterator(LastInst)));
+  Builder.SetCurrentDebugLocation(Front->getDebugLoc());
 }
 
 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
   Value *Vec = UndefValue::get(Ty);
   // Generate the 'InsertElement' instruction.
   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
   Type *ScalarTy = VL0->getType();
   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
     ScalarTy = SI->getValueOperand()->getType();
   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
 
   if (E->NeedToGather) {
     setInsertPointAfterBundle(E->Scalars);
-    return Gather(E->Scalars, VecTy);
+    auto *V = Gather(E->Scalars, VecTy);
+    E->VectorizedValue = V;
+    return V;
   }
 
   unsigned Opcode = getSameOpcode(E->Scalars);
 
   switch (Opcode) {
     case Instruction::PHI: {
       PHINode *PH = dyn_cast<PHINode>(VL0);
       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
switch (Opcode) {
     }
 
     case Instruction::ExtractElement: {
       if (canReuseExtract(E->Scalars, Instruction::ExtractElement)) {
         Value *V = VL0->getOperand(0);
         E->VectorizedValue = V;
         return V;
       }
-      return Gather(E->Scalars, VecTy);
+      setInsertPointAfterBundle(E->Scalars);
+      auto *V = Gather(E->Scalars, VecTy);
+      E->VectorizedValue = V;
+      return V;
     }
     case Instruction::ExtractValue: {
       if (canReuseExtract(E->Scalars, Instruction::ExtractValue)) {
         LoadInst *LI = cast<LoadInst>(VL0->getOperand(0));
         Builder.SetInsertPoint(LI);
         PointerType *PtrTy = PointerType::get(VecTy, LI->getPointerAddressSpace());
         Value *Ptr = Builder.CreateBitCast(LI->getOperand(0), PtrTy);
         LoadInst *V = Builder.CreateAlignedLoad(Ptr, LI->getAlignment());
         E->VectorizedValue = V;
         return propagateMetadata(V, E->Scalars);
       }
-      return Gather(E->Scalars, VecTy);
+      setInsertPointAfterBundle(E->Scalars);
+      auto *V = Gather(E->Scalars, VecTy);
+      E->VectorizedValue = V;
+      return V;
     }
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::FPExt:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:

test/Transforms/SLPVectorizer/AArch64/gather-root.ll

+; RUN: opt < %s -slp-vectorizer -S | FileCheck %s --check-prefix=DEFAULT
+; RUN: opt < %s -slp-recursion-max-depth=0 -slp-vectorizer -S | FileCheck %s --check-prefix=GATHER
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+@a = common global [80 x i8] zeroinitializer, align 16
+
+; DEFAULT-LABEL: @PR28330(
+; DEFAULT: %tmp17 = phi i32 [ %tmp34, %for.body ], [ 0, %entry ]
+; DEFAULT: %tmp18 = phi i32 [ %tmp35, %for.body ], [ %n, %entry ]
+; DEFAULT: %[[S0:.+]] = select <8 x i1> %1, <8 x i32> <i32 -720, i32 -720, i32 -720, i32 -720, i32 -720, i32 -720, i32 -720, i32 -720>, <8 x i32> <i32 -80, i32 -80, i32 -80, i32 -80, i32 -80, i32 -80, i32 -80, i32 -80>
+; DEFAULT: %[[R0:.+]] = shufflevector <8 x i32> %[[S0]], <8 x i32> undef, <8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef>
+; DEFAULT: %[[R1:.+]] = add <8 x i32> %[[S0]], %[[R0]]
+; DEFAULT: %[[R2:.+]] = shufflevector <8 x i32> %[[R1]], <8 x i32> undef, <8 x i32> <i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; DEFAULT: %[[R3:.+]] = add <8 x i32> %[[R1]], %[[R2]]
+; DEFAULT: %[[R4:.+]] = shufflevector <8 x i32> %[[R3]], <8 x i32> undef, <8 x i32> <i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; DEFAULT: %[[R5:.+]] = add <8 x i32> %[[R3]], %[[R4]]
+; DEFAULT: %[[R6:.+]] = extractelement <8 x i32> %[[R5]], i32 0
+; DEFAULT: %tmp34 = add i32 %[[R6]], %tmp17
+;
+; GATHER-LABEL: @PR28330(
+; GATHER: %tmp17 = phi i32 [ %tmp34, %for.body ], [ 0, %entry ]
+; GATHER: %tmp18 = phi i32 [ %tmp35, %for.body ], [ %n, %entry ]
+; GATHER: %tmp19 = select i1 %tmp1, i32 -720, i32 -80
+; GATHER: %tmp21 = select i1 %tmp3, i32 -720, i32 -80
+; GATHER: %tmp23 = select i1 %tmp5, i32 -720, i32 -80
+; GATHER: %tmp25 = select i1 %tmp7, i32 -720, i32 -80
+; GATHER: %tmp27 = select i1 %tmp9, i32 -720, i32 -80
+; GATHER: %tmp29 = select i1 %tmp11, i32 -720, i32 -80
+; GATHER: %tmp31 = select i1 %tmp13, i32 -720, i32 -80
+; GATHER: %tmp33 = select i1 %tmp15, i32 -720, i32 -80
+; GATHER: %[[I0:.+]] = insertelement <8 x i32> undef, i32 %tmp19, i32 0
+; GATHER: %[[I1:.+]] = insertelement <8 x i32> %[[I0]], i32 %tmp21, i32 1
+; GATHER: %[[I2:.+]] = insertelement <8 x i32> %[[I1]], i32 %tmp23, i32 2
+; GATHER: %[[I3:.+]] = insertelement <8 x i32> %[[I2]], i32 %tmp25, i32 3
+; GATHER: %[[I4:.+]] = insertelement <8 x i32> %[[I3]], i32 %tmp27, i32 4
+; GATHER: %[[I5:.+]] = insertelement <8 x i32> %[[I4]], i32 %tmp29, i32 5
+; GATHER: %[[I6:.+]] = insertelement <8 x i32> %[[I5]], i32 %tmp31, i32 6
+; GATHER: %[[I7:.+]] = insertelement <8 x i32> %[[I6]], i32 %tmp33, i32 7
+; GATHER: %[[R0:.+]] = shufflevector <8 x i32> %[[I7]], <8 x i32> undef, <8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 undef, i32 undef, i32 undef, i32 undef>
+; GATHER: %[[R1:.+]] = add <8 x i32> %[[I7]], %[[R0]]
+; GATHER: %[[R2:.+]] = shufflevector <8 x i32> %[[R1]], <8 x i32> undef, <8 x i32> <i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; GATHER: %[[R3:.+]] = add <8 x i32> %[[R1]], %[[R2]]
+; GATHER: %[[R4:.+]] = shufflevector <8 x i32> %[[R3]], <8 x i32> undef, <8 x i32> <i32 1, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef>
+; GATHER: %[[R5:.+]] = add <8 x i32> %[[R3]], %[[R4]]
+; GATHER: %[[R6:.+]] = extractelement <8 x i32> %[[R5]], i32 0
+; GATHER: %tmp34 = add i32 %[[R6]], %tmp17
+
+define void @PR28330(i32 %n) {
+entry:
+  %tmp0 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 1), align 1
+  %tmp1 = icmp eq i8 %tmp0, 0
+  %tmp2 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 2), align 2
+  %tmp3 = icmp eq i8 %tmp2, 0
+  %tmp4 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 3), align 1
+  %tmp5 = icmp eq i8 %tmp4, 0
+  %tmp6 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 4), align 4
+  %tmp7 = icmp eq i8 %tmp6, 0
+  %tmp8 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 5), align 1
+  %tmp9 = icmp eq i8 %tmp8, 0
+  %tmp10 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 6), align 2
+  %tmp11 = icmp eq i8 %tmp10, 0
+  %tmp12 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 7), align 1
+  %tmp13 = icmp eq i8 %tmp12, 0
+  %tmp14 = load i8, i8* getelementptr inbounds ([80 x i8], [80 x i8]* @a, i64 0, i64 8), align 8
+  %tmp15 = icmp eq i8 %tmp14, 0
+  br label %for.body
+
+for.body:
+  %tmp17 = phi i32 [ %tmp34, %for.body ], [ 0, %entry ]
+  %tmp18 = phi i32 [ %tmp35, %for.body ], [ %n, %entry ]
+  %tmp19 = select i1 %tmp1, i32 -720, i32 -80
+  %tmp20 = add i32 %tmp17, %tmp19
+  %tmp21 = select i1 %tmp3, i32 -720, i32 -80
+  %tmp22 = add i32 %tmp20, %tmp21
+  %tmp23 = select i1 %tmp5, i32 -720, i32 -80
+  %tmp24 = add i32 %tmp22, %tmp23
+  %tmp25 = select i1 %tmp7, i32 -720, i32 -80
+  %tmp26 = add i32 %tmp24, %tmp25
+  %tmp27 = select i1 %tmp9, i32 -720, i32 -80
+  %tmp28 = add i32 %tmp26, %tmp27
+  %tmp29 = select i1 %tmp11, i32 -720, i32 -80
+  %tmp30 = add i32 %tmp28, %tmp29
+  %tmp31 = select i1 %tmp13, i32 -720, i32 -80
+  %tmp32 = add i32 %tmp30, %tmp31
+  %tmp33 = select i1 %tmp15, i32 -720, i32 -80
+  %tmp34 = add i32 %tmp32, %tmp33
+  %tmp35 = add nsw i32 %tmp18, -1
+  %tmp36 = icmp eq i32 %tmp35, 0
+  br i1 %tmp36, label %for.end, label %for.body
+
+for.end:
+  ret void
+}