[LV] Use SCEV to check if the trip count <= VF * UF.

[fhahn]

Summary

Just comparing constant trip counts causes LV to miss cases where the
vector loop body only executes once.

The motivation for this is to remove the need for unrolling to remove
vector loop back-edges, if the body only executes once.

It requires using non-recursive SCEV reasoning, as at this stage the CFG
is incomplete and only reasoning based on existing expression can be
used. In particular, more complex strategies like proving via induction
cannot be used, as LI/DT may be out of date.

Alternatively the result of the check could be computed earlier.

[reames]

llvm/lib/Transforms/Vectorize/VPlan.cpp

608 ↗

(On Diff #456943)

Please don't change the SCEV interface for this. Just use isKnownPredicate. You don't care if the reasoning is recursive or not.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

608 ↗

(On Diff #456943)

The issue here is that we would need to limit the reasoning to methods that don’t try to look at the current IR, just at the SCEV expression, because the IR is in incomplete/partially modified state.

Using non-recursive reasoning is a proxy for that, but I’m not sure if it provides the required guarantees in all cases.

The alternative would be to compute the property before we start modifying the CFG, like we do for trip count expansion.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.cpp

608 ↗

(On Diff #456943)

Analyzing and optimizing VPlan should ideally take place as VPlan2VPlan and reflected in VPlan itself before starting/preparing to execute it - at which time the IR is in incomplete/partially modified state. This case of optimizing away the latch branch for single iteration loops depends on UF which VPlan is currently agnostic to and encounters only when executing. How about cloning VPlans (also) according to which UF*VF's result in a single iteration (upto reasonable UF values - computeMaxUF()?), updating the default "UF>=1" in VPlan names and extending getBestPlanFor() to pass both VF and UF? That may admittedly require splitting ranges currently serving multiple VF's.

[fhahn]

Rebased on top of D135017, which contains the main refactoring to prepare for this change, which now just changes to use ScalarEvolution::isKnowPredicate.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

608 ↗

(On Diff #456943)

I put up D135017 which is a step in between: perform the simplification as VP2VP transform that's VF & UF specific. This means we simplify before IR modifications and ScalarEvolution can be used without worrying about querying while the IR is in an incomplete state.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

488

Could this be simplified using SE.getSmallConstantMaxTripCount(L)? Or a caching thereof.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

488

SE.getSmallConstantMaxTripCount(L) only supports the case where the trip count is a constant, while isKnownPredicate supports the non-constant case as well.

[fhahn]

rebase after update to D135017

[Ayal]

Looks good to me, thanks.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

483–485

Thought: create vector trip count SCEV, once VF and UF are set; use it to create vector trip count Value, and also to check if it is known to be less than or equal to 1?

488

Ok. Non-constant case seems a bit extreme, unless tail is folded - vectorizing and unrolling to a known upper bound will otherwise run the original scalar loop whenever its trip count misses the exact upper bound.

[fhahn]

rebase after recent changes

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

483–485

Will do as follow-up! Would be good to integrate it once the loop skeleton is also created in VPlan.

488

Yes, the transform just removes an unneeded branch; deciding whether it is profitable to vectorize with scalar tail will still be done elsewhere.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

void VPlanTransforms::optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
   //  1. BranchOnCount, or
   //  2. BranchOnCond where the input is Not(ActiveLaneMask).
   if (!Term || (Term->getOpcode() != VPInstruction::BranchOnCount &&
                 (Term->getOpcode() != VPInstruction::BranchOnCond ||
                  !canSimplifyBranchOnCond(Term))))
     return;
 
   Type *IdxTy =
       Plan.getCanonicalIV()->getStartValue()->getLiveInIRValue()->getType();
   const SCEV *TripCount = createTripCountSCEV(IdxTy, PSE);
-  auto *C = dyn_cast<SCEVConstant>(TripCount);
   ScalarEvolution &SE = *PSE.getSE();
-  if (!C || TripCount->isZero() ||
-      C->getAPInt().getZExtValue() > BestVF.getKnownMinValue() * BestUF)
+  const SCEV *C =
+      SE.getConstant(TripCount->getType(), BestVF.getKnownMinValue() * BestUF);
+  if (TripCount->isZero() ||
+      !SE.isKnownPredicate(CmpInst::ICMP_ULE, TripCount, C))
     return;
 
   LLVMContext &Ctx = SE.getContext();
   auto *BOC =
       new VPInstruction(VPInstruction::BranchOnCond,
                         {Plan.getOrAddExternalDef(ConstantInt::getTrue(Ctx))});
   Term->eraseFromParent();
   ExitingVPBB->appendRecipe(BOC);
   Plan.setVF(BestVF);
   Plan.setUF(BestUF);
   // TODO: Further simplifications are possible
   //      1. Replace inductions with constants.
   //      2. Replace vector loop region with VPBasicBlock.
 }

llvm/test/Transforms/LoopVectorize/vector-loop-backedge-elimination.ll

 ; RUN: opt -passes=loop-vectorize -force-vector-width=8 -force-vector-interleave=1 -S %s | FileCheck --check-prefixes=CHECK,VF8UF1 %s
 ; RUN: opt -passes=loop-vectorize -force-vector-width=8 -force-vector-interleave=2 -S %s | FileCheck --check-prefixes=CHECK,VF8UF2 %s
 ; RUN: opt -passes=loop-vectorize -force-vector-width=16 -force-vector-interleave=1 -S %s | FileCheck --check-prefixes=CHECK,VF16UF1 %s
 
 target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
 
 ; Check if the vector loop condition can be simplified to true for a given
 ; VF/IC combination.
 define void @test_tc_less_than_16(ptr %A, i64 %N) {
 ; CHECK-LABEL: define void @test_tc_less_than_16(
 ; VF8UF1:       [[CMP:%.+]] = icmp eq i64 %index.next, %n.vec
 ; VF8UF1-NEXT:  br i1 [[CMP]], label %middle.block, label %vector.body
 ;
-; VF8UF2:       [[CMP:%.+]] = icmp eq i64 %index.next, %n.vec
-; VF8UF2-NEXT:  br i1 [[CMP]], label %middle.block, label %vector.body
+; VF8UF2:       br i1 true, label %middle.block, label %vector.body
 ;
-; VF16UF1:       [[CMP:%.+]] = icmp eq i64 %index.next, %n.vec
-; VF16UF1-NEXT:  br i1 [[CMP]], label %middle.block, label %vector.body
+; VF16UF1:      br i1 true, label %middle.block, label %vector.body
 ;
 entry:
   %and = and i64 %N, 15
   br label %loop
 
 loop:
   %iv = phi i64 [ %and, %entry ], [ %iv.next, %loop ]
   %p.src = phi ptr [ %A, %entry ], [ %p.src.next, %loop ]