[LoopVectorize] Change PredicatedBBsAfterVectorization to be per VF

[david-arm]

Summary

When calculating the cost of Instruction::Br in getInstructionCost
we query PredicatedBBsAfterVectorization to see if there is a
scalar predicated block. However, this meant that the decisions
being made for a given fixed-width VF were affecting the cost for a
scalable VF. As a result we were returning InstructionCost::Invalid
pointlessly for a scalable VF that should have a low cost. I
encountered this for some loops when enabling tail-folding for
scalable VFs.

Test added here:

Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

[sdesmalen]

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

9

nit: can you clean up this test a bit? dso_local nocapture, etc aren't really required for the LV test.
Also, can you use some constant FP value instead of loading from @globval ?

17

What in this loop is causing PredicatedBBsAfterVectorization to be true for fixed-width vectors?

[david-arm]

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

17

It's the uniform load of @globval, which causes LoopVectorizationCostModel::collectInstsToScalarize to insert the BB into PredicatedBBsAfterVectorization.

[david-arm]

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

9

I can try using other types of uniform load, so long as the load is treated as scalar with predication for a fixed-width VF.

[david-arm]

• Tidied up test and removed the globvar.

[sdesmalen]

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

7

nit: Can this test be reduced a little bit more, I'm not sure if %boff, %coff and all of the pointers are really needed for this test.

17

Okay thanks, can you just add a comment to the test describing this? I didn't realise that the load from @globval had this effect.

[david-arm]

• Simplified test case.

[sdesmalen]

Thanks for the changes @david-arm. I just have a few more comments on the test.

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

14–16

If it selects VF=vscale x 4 then it seems redundant to check there is no invalid cost for that chosen VF.

If you want to check that it uses a scalable VF, you don't need the debug-output to tell you it chose that. You could remove the REQUIRES: asserts, the -debug option from the RUN line and instead check for <vscale x 4 x i32> in the resulting IR. What do you think?

Just a note that this test may become redundant in the future if SVE is used for fixed-width vectors and it can lower fixed-width masked load/store operations to use SVE. Maybe you can add a note here that this assumption is important for the test and may change in the future?

[david-arm]

• Removed checks for debug output.

[david-arm]

• Updated comment in the test to be more readable!

[sdesmalen]

Thanks @david-arm, LGTM.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

private:
 
   /// A type representing the costs for instructions if they were to be
   /// scalarized rather than vectorized. The entries are Instruction-Cost
   /// pairs.
   using ScalarCostsTy = DenseMap<Instruction *, InstructionCost>;
 
   /// A set containing all BasicBlocks that are known to present after
   /// vectorization as a predicated block.
-  SmallPtrSet<BasicBlock *, 4> PredicatedBBsAfterVectorization;
+  DenseMap<ElementCount, SmallPtrSet<BasicBlock *, 4>>
+      PredicatedBBsAfterVectorization;
 
   /// Records whether it is allowed to have the original scalar loop execute at
   /// least once. This may be needed as a fallback loop in case runtime
   /// aliasing/dependence checks fail, or to handle the tail/remainder
   /// iterations when the trip count is unknown or doesn't divide by the VF,
   /// or as a peel-loop to handle gaps in interleave-groups.
   /// Under optsize and when the trip count is very small we don't allow any
   /// iterations to execute in the scalar loop.
if (VF.isScalar() || VF.isZero() ||
       InstsToScalarize.find(VF) != InstsToScalarize.end())
     return;
 
   // Initialize a mapping for VF in InstsToScalalarize. If we find that it's
   // not profitable to scalarize any instructions, the presence of VF in the
   // map will indicate that we've analyzed it already.
   ScalarCostsTy &ScalarCostsVF = InstsToScalarize[VF];
 
+  PredicatedBBsAfterVectorization[VF].clear();
+
   // Find all the instructions that are scalar with predication in the loop and
   // determine if it would be better to not if-convert the blocks they are in.
   // If so, we also record the instructions to scalarize.
   for (BasicBlock *BB : TheLoop->blocks()) {
     if (!blockNeedsPredicationForAnyReason(BB))
       continue;
     for (Instruction &I : *BB)
       if (isScalarWithPredication(&I, VF)) {
         ScalarCostsTy ScalarCosts;
         // Do not apply discount if scalable, because that would lead to
         // invalid scalarization costs.
         // Do not apply discount logic if hacked cost is needed
         // for emulated masked memrefs.
         if (!VF.isScalable() && !useEmulatedMaskMemRefHack(&I, VF) &&
             computePredInstDiscount(&I, ScalarCosts, VF) >= 0)
           ScalarCostsVF.insert(ScalarCosts.begin(), ScalarCosts.end());
         // Remember that BB will remain after vectorization.
-        PredicatedBBsAfterVectorization.insert(BB);
+        PredicatedBBsAfterVectorization[VF].insert(BB);
       }
   }
 }
 
 int LoopVectorizationCostModel::computePredInstDiscount(
     Instruction *PredInst, ScalarCostsTy &ScalarCosts, ElementCount VF) {
   assert(!isUniformAfterVectorization(PredInst, VF) &&
          "Instruction marked uniform-after-vectorization will be predicated");
case Instruction::GetElementPtr:
     return 0;
   case Instruction::Br: {
     // In cases of scalarized and predicated instructions, there will be VF
     // predicated blocks in the vectorized loop. Each branch around these
     // blocks requires also an extract of its vector compare i1 element.
     bool ScalarPredicatedBB = false;
     BranchInst *BI = cast<BranchInst>(I);
     if (VF.isVector() && BI->isConditional() &&
-        (PredicatedBBsAfterVectorization.count(BI->getSuccessor(0)) ||
-         PredicatedBBsAfterVectorization.count(BI->getSuccessor(1))))
+        (PredicatedBBsAfterVectorization[VF].count(BI->getSuccessor(0)) ||
+         PredicatedBBsAfterVectorization[VF].count(BI->getSuccessor(1))))
       ScalarPredicatedBB = true;
 
     if (ScalarPredicatedBB) {
       // Not possible to scalarize scalable vector with predicated instructions.
       if (VF.isScalable())
         return InstructionCost::getInvalid();
       // Return cost for branches around scalarized and predicated blocks.
       auto *Vec_i1Ty =

llvm/test/Transforms/LoopVectorize/AArch64/sve-tail-folding-cost.ll

+; RUN: opt -S -loop-vectorize -prefer-predicate-over-epilogue=predicate-dont-vectorize <%s | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnu"
+
+; The uniform load of %d in the following loop triggers the special
+; branch costing code in LoopVectorizationCostModel::getInstructionCost.
+; However, this should only affect the fixed-width cost because for
+; NEON it needs to scalarize the load, whereas for SVE it can use a predicated load.
+; Because of how the LoopVectorizer annotates the load to need scalarization with
+; predicated blocks, this leads to different costs for the branch instruction.
+;
+; NOTE: This test assumes we will never use a fixed-width VF due to
+; the high cost of scalarizing the masked store, however this assumption may
+; break in future if we permit the use of SVE loads and stores to perform the
+; fixed-width operations.
+define i32 @uniform_load(i64 %n, ptr readnone %c, ptr %d) #0 {
+; CHECK-LABEL: @uniform_load(
+; CHECK: call void @llvm.masked.store.nxv4f32.p0(<vscale x 4 x float>
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
+  %load2 = load float, ptr %d, align 4
+  %arrayidx2 = getelementptr inbounds float, ptr %c, i64 %indvars.iv
+  store float %load2, ptr %arrayidx2, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.not = icmp eq i64 %indvars.iv.next, %n
+  br i1 %exitcond.not, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret i32 0
+}
+
+attributes #0 = { vscale_range(1,16) "target-features"="+sve" }