[LV] Invalidate cost model decisions along with interleave groups.

[fhahn]

Summary

Cost-modeling decisions are tied to the compute interleave groups
(widening decisions, scalar and uniform values). When invalidating the
interleave groups, those decisions also need to be invalidated.

Otherwise there is a mis-match during VPlan construction.
VPWidenMemoryRecipes created initially are left around w/o converting them
into VPInterleave recipes. Such a conversion indeed should not take place,
and these gather/scatter recipes may in fact be right. The crux is leaving around
obsolete CM_Interleave (and dependent) markings of instructions along with
their costs, instead of recalculating decisions, costs, and recipes.

Alternatively to forcing a complete recompute later on, we could try
to selectively invalidate the decisions connected to the interleave
groups. But we would likely need to run the uniform/scalar value
detection parts again anyways and the extra complexity is probably not
worth it.

Fixes PR45572.

[Ayal]

Clarifying the summary a bit:

Cost-modeling decisions are tied to the compute interleave groups
(widening decisions, scalar and uniform values). We [When] invalidating the
interleave groups, those decisions also need to be invalidated.

Otherwise there is a mis-match during VPlan construction where no
VPInterleave recipes are created and VPWidenMemoryRecipes are left
around for instructions marked as interleaved. This happens if
a vectorization factor is chosen for which computeMaxVF already computed
the CM decisions.

VPWidenMemoryRecipes created initially are indeed left around w/o converting them into VPInterleave recipes, but such conversion indeed should not take place, and these gather/scatter recipes may in fact be right. The crux is leaving around obsolete CM_Interleave (and dependent) markings of instructions along with their costs, instead of recalculating decisions, costs, and recipes.

llvm/include/llvm/Analysis/VectorUtils.h

757

Apply a similar fix to invalidateGroupsRequiringScalarEpilogue() as well? I.e., have it return an indication if any groups were invalidated, and if so clear WideningDecisions, Uniforms and Scalars.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1322

If there are no groups there's no need to call reset() either. Seems logical to first do InterleaveInfo.reset(), as it triggers clearing of WideningDecisions (at-least the CM_Interleave ones), which in turn triggers clearing Uniforms and Scalars.

Best have InterleaveInfo.reset() return an indication if any groups were destroyed, and iff so clear the rest? (Can indeed be more selective by also checking if there were any CM_Interleave decisions, etc., but agree that the extra complexity is probably not worth it.)

[fhahn]

Addressed comments.

In D78298#1986961, @Ayal wrote:

Clarifying the summary a bit:

Cost-modeling decisions are tied to the compute interleave groups
(widening decisions, scalar and uniform values). We [When] invalidating the
interleave groups, those decisions also need to be invalidated.

Otherwise there is a mis-match during VPlan construction where no
VPInterleave recipes are created and VPWidenMemoryRecipes are left
around for instructions marked as interleaved. This happens if
a vectorization factor is chosen for which computeMaxVF already computed
the CM decisions.

VPWidenMemoryRecipes created initially are indeed left around w/o converting them into VPInterleave recipes, but such conversion indeed should not take place, and these gather/scatter recipes may in fact be right. The crux is leaving around obsolete CM_Interleave (and dependent) markings of instructions along with their costs, instead of recalculating decisions, costs, and recipes.

Thanks Ayal, I'll update the description to

Cost-modeling decisions are tied to the compute interleave groups
(widening decisions, scalar and uniform values). When invalidating the
interleave groups, those decisions also need to be invalidated.

Otherwise there is a mis-match during VPlan construction.
VPWidenMemoryRecipes created initially are left around w/o converting them
into VPInterleave recipes. Such a conversion indeed should not take place,
and these gather/scatter recipes may in fact be right. The crux is leaving around
obsolete CM_Interleave (and dependent) markings of instructions along with
their costs, instead of recalculating decisions, costs, and recipes.

Does that sound good?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1322

I've renamed the function to invalidateCostModelingDecision, changed InterleaveInfo::reset to return a bool indicating if any groups have been invalidated (and renamed it to invalidateGroups to bring it in line with invalidateGroupsRequiring...). invalidateCostModelingDecisions is only called if invalidateGroups* returns true.

[Ayal]

Sure, the updated summary's fine :-).

llvm/include/llvm/Analysis/VectorUtils.h

714

Simpler to early-exit at the start by "if (InterleaveGroups.empty()) return false;" and at the end "return true;"?

Still need to set RequiresScalarEpilogue to false. One would hope RequiresScalarEpilogue would always be false if there are no groups, but that requires another fix: releaseGroup() does not recompute RequiresScalarEpilogue (if it's true and the released group requiresScalarEpilogue); another option would be to set ReleaseScalarEpilogue once at the end, if any surviving group requiresScalarEpilogue.

759

Thanks for taking care of this as well! Would be good to have a test, perhaps a version of invalidate-cm-after-invalidating-interleavegroups.ll where idx.mul is bumped by more than 7, trip count is a power of 2, under optsize, would do(?).

llvm/lib/Analysis/VectorUtils.cpp

1258

(As noted earlier, cannot simply assert that DelSet is not empty, and return true.
But at-least now RequiresScalarEpilogue is accurate ...)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4992–4993

nit: could fuse into a single if. OTOH, perhaps an LLVM_DEBUG in between may be useful, as in the general invalidateGroups()?

[Ayal]

llvm/include/llvm/Analysis/VectorUtils.h

714

Actually releaseGroup() does not need to recompute RequiresScalarEpilogue, because the latter is indeed set according to surviving groups only, that are not released later.

[fhahn]

Address comments, add additional test case.

[fhahn]

llvm/include/llvm/Analysis/VectorUtils.h

714

I've added an assertion that empty groups implies RequiresScalarEpilogue == false.

759

This is actually not required, as the groups are invalidated before any cost-modeling decisions are taken. I've added a test case that should crash otherwise, as suggested.

llvm/lib/Analysis/VectorUtils.cpp

1258

(from above)

Actually releaseGroup() does not need to recompute RequiresScalarEpilogue, because the latter is indeed set according to surviving groups only, that are not released later.

Right, it should always be up-to-date, right? in invalidateGroups all groups are removed and it is set to false. In invalidateGroupsRequiringScalarEpilogue, all groups requiring a scalar epilogue are removed and it is set to false as well. I've added an assertion.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4992–4993

There's no need to invalidate anything CM related, as nothing's computed yet. I've added an assertion to that effect and a comment.

[Ayal]

This looks good to me, thanks!

llvm/lib/Analysis/VectorUtils.cpp

1258

Right, very good.
Better place the assert immediately after the loop that fills DelSet.

Independent fix: would be better to loop over InterleaveGroups rather than InterleaveGroupMap in order to fill DelSet; which could then be a SmallVector; w/o the need for the "Avoid releasing a Group twice" comment.

[fhahn]

llvm/lib/Analysis/VectorUtils.cpp

1258

Independent fix: would be better to loop over InterleaveGroups rather than InterleaveGroupMap in order to fill DelSet; which could then be a SmallVector; w/o the need for the "Avoid releasing a Group twice" comment.

I don't think we actually need an extra set/vector. Instead we should be able to just use an early_inc_range, which allows removing the current element as well: D78420

llvm/include/llvm/Analysis/VectorUtils.h

 /// between the member and the group in a map.
 class InterleavedAccessInfo {
 public:
   InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
                         DominatorTree *DT, LoopInfo *LI,
                         const LoopAccessInfo *LAI)
       : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
 
-  ~InterleavedAccessInfo() { reset(); }
+  ~InterleavedAccessInfo() { invalidateGroups(); }
 
   /// Analyze the interleaved accesses and collect them in interleave
   /// groups. Substitute symbolic strides using \p Strides.
   /// Consider also predicated loads/stores in the analysis if
   /// \p EnableMaskedInterleavedGroup is true.
   void analyzeInterleaving(bool EnableMaskedInterleavedGroup);
 
   /// Invalidate groups, e.g., in case all blocks in loop will be predicated
   /// contrary to original assumption. Although we currently prevent group
   /// formation for predicated accesses, we may be able to relax this limitation
-  /// in the future once we handle more complicated blocks.
-  void reset() {
+  /// in the future once we handle more complicated blocks. Returns true if any
+  /// groups were invalidated.
+  bool invalidateGroups() {
+    if (InterleaveGroups.empty()) {
+      assert(
+          !RequiresScalarEpilogue &&
+          "RequiresScalarEpilog should not be set without interleave groups");
+      return false;
+    }
+
     InterleaveGroupMap.clear();
     for (auto *Ptr : InterleaveGroups)
       delete Ptr;
     InterleaveGroups.clear();
     RequiresScalarEpilogue = false;
+    return true;
   }
 
-
   /// Check if \p Instr belongs to any interleave group.
   bool isInterleaved(Instruction *Instr) const {
     return InterleaveGroupMap.find(Instr) != InterleaveGroupMap.end();
   }
 
   /// Get the interleave group that \p Instr belongs to.
   ///
   /// \returns nullptr if doesn't have such group.
public:
 
   /// Returns true if an interleaved group that may access memory
   /// out-of-bounds requires a scalar epilogue iteration for correctness.
   bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }
 
   /// Invalidate groups that require a scalar epilogue (due to gaps). This can
   /// happen when optimizing for size forbids a scalar epilogue, and the gap
   /// cannot be filtered by masking the load/store.
   void invalidateGroupsRequiringScalarEpilogue();
 
 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
   /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
   /// The interleaved access analysis can also add new predicates (for example
   /// by versioning strides of pointers).
   PredicatedScalarEvolution &PSE;
 
   Loop *TheLoop;
   DominatorTree *DT;

llvm/lib/Analysis/VectorUtils.cpp

void InterleavedAccessInfo::invalidateGroupsRequiringScalarEpilogue() {
 
   // Avoid releasing a Group twice.
   SmallPtrSet<InterleaveGroup<Instruction> *, 4> DelSet;
   for (auto &I : InterleaveGroupMap) {
     InterleaveGroup<Instruction> *Group = I.second;
     if (Group->requiresScalarEpilogue())
       DelSet.insert(Group);
   }
+  assert(!DelSet.empty() && "At least one group must be invalidated, as a "
+                            "scalar epilogue was required");
   for (auto *Ptr : DelSet) {
     LLVM_DEBUG(
         dbgs()
         << "LV: Invalidate candidate interleaved group due to gaps that "
            "require a scalar epilogue (not allowed under optsize) and cannot "
            "be masked (not enabled). \n");
     releaseGroup(Ptr);
   }
 
   RequiresScalarEpilogue = false;
 }
 
 template <typename InstT>
 void InterleaveGroup<InstT>::addMetadata(InstT *NewInst) const {
   llvm_unreachable("addMetadata can only be used for Instruction");
 }
 
 namespace llvm {
 template <>

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
 
   /// Estimate cost of a call instruction CI if it were vectorized with factor
   /// VF. Return the cost of the instruction, including scalarization overhead
   /// if it's needed. The flag NeedToScalarize shows if the call needs to be
   /// scalarized -
   /// i.e. either vector version isn't available, or is too expensive.
   unsigned getVectorCallCost(CallInst *CI, unsigned VF, bool &NeedToScalarize);
 
+  /// Invalidates decisions already taken by the cost model.
+  void invalidateCostModelingDecisions() {
+    WideningDecisions.clear();
+    Uniforms.clear();
+    Scalars.clear();
+  }
+
 private:
   unsigned NumPredStores = 0;
 
   /// \return An upper bound for the vectorization factor, larger than zero.
   /// One is returned if vectorization should best be avoided due to cost.
   unsigned computeFeasibleMaxVF(unsigned ConstTripCount);
 
   /// The vectorization cost is a combination of the cost itself and a boolean
   /// indicating whether any of the contributing operations will actually
   /// operate on
   /// vector values after type legalization in the backend. If this latter value
   /// is
if (runtimeChecksRequired())
       return None;
     break;
   }
 
   // Now try the tail folding
 
   // Invalidate interleave groups that require an epilogue if we can't mask
   // the interleave-group.
-  if (!useMaskedInterleavedAccesses(TTI))
+  if (!useMaskedInterleavedAccesses(TTI)) {
+    assert(WideningDecisions.empty() && Uniforms.empty() && Scalars.empty() &&
+           "No decisions should have been taken at this point");
+    // Note: There is no need to invalidate any cost modeling decisions here, as
+    // non where taken so far.
     InterleaveInfo.invalidateGroupsRequiringScalarEpilogue();
+  }
 
   unsigned MaxVF = computeFeasibleMaxVF(TC);
   if (TC > 0 && TC % MaxVF == 0) {
     // Accept MaxVF if we do not have a tail.
     LLVM_DEBUG(dbgs() << "LV: No tail will remain for any chosen VF.\n");
     return MaxVF;
   }
 
Optional<VectorizationFactor> LoopVectorizationPlanner::plan(unsigned UserVF) {
 
   // Invalidate interleave groups if all blocks of loop will be predicated.
   if (CM.blockNeedsPredication(OrigLoop->getHeader()) &&
       !useMaskedInterleavedAccesses(*TTI)) {
     LLVM_DEBUG(
         dbgs()
         << "LV: Invalidate all interleaved groups due to fold-tail by masking "
            "which requires masked-interleaved support.\n");
-    CM.InterleaveInfo.reset();
+    if (CM.InterleaveInfo.invalidateGroups())
+      // Invalidating interleave groups also requires invalidating all decisions
+      // based on them, which includes widening decisions and uniform and scalar
+      // values.
+      CM.invalidateCostModelingDecisions();
   }
 
   if (UserVF) {
     LLVM_DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
     assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
     // Collect the instructions (and their associated costs) that will be more
     // profitable to scalarize.
     CM.selectUserVectorizationFactor(UserVF);

llvm/test/Transforms/LoopVectorize/Hexagon/invalidate-cm-after-invalidating-interleavegroups.ll

+; RUN: opt -loop-vectorize -hexagon-autohvx=1 -force-vector-width=64 -prefer-predicate-over-epilog -S %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
+target triple = "hexagon"
+
+; Test for PR45572.
+
+; Check that interleave groups and decisions based on them are correctly
+; invalidated with tail-folding on platforms where masked interleaved accesses
+; are disabled.
+
+; Make sure a vector body has been created, 64 element vectors are used and a block predicate has been computed.
+; Also make sure the loads are not widened.
+
+; CHECK-LABEL: @test1
+; CHECK: vector.body:
+; CHECK: %induction = add <64 x i32>
+; CHECK: icmp ule <64 x i32> %induction
+; CHECK-NOT: load <{{.*}} x i32>
+
+
+define void @test1(i32* %arg, i32 %N) #0 {
+entry:
+  %tmp = alloca i8
+  br label %loop
+
+loop:                                              ; preds = %bb2, %bb
+  %iv = phi i32 [ %iv.next, %loop], [ 0, %entry ]
+  %idx.mul = mul nuw nsw i32 %iv, 7
+  %idx.start = add nuw nsw i32 %idx.mul, 1
+  %tmp6 = getelementptr inbounds i32, i32* %arg, i32 %idx.start
+  %tmp7 = load i32, i32* %tmp6, align 4
+  %tmp8 = add nuw nsw i32 %idx.start, 1
+  %tmp9 = getelementptr inbounds i32, i32* %arg, i32 %tmp8
+  %tmp10 = load i32, i32* %tmp9, align 4
+  %tmp11 = add nuw nsw i32 %idx.start, 2
+  %tmp12 = getelementptr inbounds i32, i32* %arg, i32 %tmp11
+  %tmp13 = load i32, i32* %tmp12, align 4
+  %tmp14 = add nuw nsw i32 %idx.start, 3
+  %tmp15 = getelementptr inbounds i32, i32* %arg, i32 %tmp14
+  %tmp16 = load i32, i32* %tmp15, align 4
+  %tmp18 = add nuw nsw i32 %idx.start, 4
+  %tmp19 = getelementptr inbounds i32, i32* %arg, i32 %tmp18
+  %tmp20 = load i32, i32* %tmp19, align 4
+  %tmp21 = add nuw nsw i32 %idx.start, 5
+  %tmp22 = getelementptr inbounds i32, i32* %arg, i32 %tmp21
+  %tmp23 = load i32, i32* %tmp22, align 4
+  %tmp25 = add nuw nsw i32 %idx.start, 6
+  %tmp26 = getelementptr inbounds i32, i32* %arg, i32 %tmp25
+  %tmp27 = load i32, i32* %tmp26, align 4
+  store i8 0, i8* %tmp, align 1
+  %iv.next= add nuw nsw i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv.next, %N
+  br i1 %exit.cond, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+; The loop below only requires tail folding due to interleave groups with gaps.
+; Make sure the loads are not widened.
+
+; CHECK-LABEL: @test2
+; CHECK: vector.body:
+; CHECK-NOT: load <{{.*}} x i32>
+define void @test2(i32* %arg) #1 {
+entry:
+  %tmp = alloca i8
+  br label %loop
+
+loop:                                              ; preds = %bb2, %bb
+  %iv = phi i32 [ %iv.next, %loop], [ 0, %entry ]
+  %idx.start = mul nuw nsw i32 %iv, 5
+  %tmp6 = getelementptr inbounds i32, i32* %arg, i32 %idx.start
+  %tmp7 = load i32, i32* %tmp6, align 4
+  %tmp8 = add nuw nsw i32 %idx.start, 1
+  %tmp9 = getelementptr inbounds i32, i32* %arg, i32 %tmp8
+  %tmp10 = load i32, i32* %tmp9, align 4
+  %tmp11 = add nuw nsw i32 %idx.start, 2
+  %tmp12 = getelementptr inbounds i32, i32* %arg, i32 %tmp11
+  %tmp13 = load i32, i32* %tmp12, align 4
+  %tmp14 = add nuw nsw i32 %idx.start, 3
+  %tmp15 = getelementptr inbounds i32, i32* %arg, i32 %tmp14
+  %tmp16 = load i32, i32* %tmp15, align 4
+  store i8 0, i8* %tmp, align 1
+  %iv.next= add nuw nsw i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv.next, 128
+  br i1 %exit.cond, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+
+attributes #0 = { "target-features"="+hvx,+hvx-length128b" }
+attributes #1 = { optsize "target-features"="+hvx,+hvx-length128b" }