[NFC][LoopVectorize] Remove setBestPlan in favour of getBestPlanFor

[david-arm]

Summary

I have removed LoopVectorizationPlanner::setBestPlan, since this
function is quite aggressive because it deletes all other plans
except the one containing the <VF,UF> pair required. The code is
currently written to assume that all <VF,UF> pairs will live in the
same vplan. This is overly restrictive, since scalable VFs live in
different plans to fixed-width VFS. When we add support for
vectorising epilogue loops when the main loop uses scalable vectors
then we will the vplan for the main loop will be different to the
epilogue.

Instead I have added a new function called

LoopVectorizationPlanner::getBestPlanFor

that returns the best vplan for the <VF,UF> pair requested and leaves
all the vplans untouched. We then pass this best vplan to

LoopVectorizationPlanner::executePlan

This patch was spun off due to comments in D109432.

[bmahjour]

Seems like a reasonable idea to me, but just pointing out that the lifetime of unused plans will be extended with this patch. Could we delete unused plans, eg by calling something like LVP.deleteVPlansExcept(BestPlan2) right before LVP.executePlan(...,) on line 10435?

[bmahjour]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

293

could you make this function const?

[david-arm]

In D111125#3043297, @bmahjour wrote:

Seems like a reasonable idea to me, but just pointing out that the lifetime of unused plans will be extended with this patch. Could we delete unused plans, eg by calling something like LVP.deleteVPlansExcept(BestPlan2) right before LVP.executePlan(...,) on line 10435?

Hi @bmahjour, I think that's basically what I was doing in D109432, where I backed up a copy of the plans before deleting them. @sdesmalen suggested I could take a different approach with this patch instead. The problem is that once the plans are deleted I can't get them back again, and the scalable VFs and fixed-width VFs live in different plans. This meant that if I deleted the plans when emitting the main vector loop, I then had to find a way of reinstating the plans so I could then generate the epilogue vector loop.

[david-arm]

• Added const keywords.

[bmahjour]

In D111125#3044674, @david-arm wrote:

In D111125#3043297, @bmahjour wrote:

Seems like a reasonable idea to me, but just pointing out that the lifetime of unused plans will be extended with this patch. Could we delete unused plans, eg by calling something like LVP.deleteVPlansExcept(BestPlan2) right before LVP.executePlan(...,) on line 10435?

Hi @bmahjour, I think that's basically what I was doing in D109432, where I backed up a copy of the plans before deleting them. @sdesmalen suggested I could take a different approach with this patch instead. The problem is that once the plans are deleted I can't get them back again, and the scalable VFs and fixed-width VFs live in different plans. This meant that if I deleted the plans when emitting the main vector loop, I then had to find a way of reinstating the plans so I could then generate the epilogue vector loop.

Yes, but say the plan for the main loop (scalable) is P1 and the plan for the epilogue (fixed-width) is P2. Assuming P1 != P2, once P1 is executed, we don't need it anymore, so we can delete it right before executing P2. Similarly for the path where epilogue is not vectorized, we could delete all other plans before executing the "best plan". Am I misunderstanding something?

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

293

sorry I meant making the member function constant, but the return type would be good to be const as well (ie const VPlanPtr &getBestPlanFor(ElementCount VF, unsigned UF) const;)

[david-arm]

• Added 'const' keyword to function, which required changing how we set the BestVF and BestUF.

[david-arm]

Hi @bmahjour, I'll have a look into ways of removing some of the unneeded vplans too!

[bmahjour]

In D111125#3047359, @david-arm wrote:

Hi @bmahjour, I'll have a look into ways of removing some of the unneeded vplans too!

Thanks @david-arm!

[david-arm]

• Ensured we remove all unneeded vplans separately.

[bmahjour]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

315

Instead of passing the list of VFs, why not pass in a VPlanPtr objects that's returned by getBestPlanFor? That would simplify the interface (since you don't have to pass in a list), simplifies the logic (since it makes it clear that we only delete plans that are not considered "best"), and avoids iterating through the list of VFs and VPlans a second time.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8192

I'd suggest moving this debug line to the beginning of executePlan and keep outputting the interleave factor (BestUF).

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

315

I could do that, but would have to change this immediately in D109432 to accept a list of vplans, since in that patch different VFs will be in different plans. I would like to keep this as a list if possible. If you still think it's better to pass in a list of VPlanPtrs here instead of a list of VFs I can see if that makes the code simpler?

[bmahjour]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

315

Ok, fair enough....I guess you could make it a list in this patch and pass a list of size one (just like you're doing now), but I still think that the type of the list element should be VPlanPtr.

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

315

Hi @bmahjour, there is just one problem with your approach - the VPlanPtr is defined as std::unique_ptr<VPlan>, which means that I can only return a reference from getBestPlanFor. In order to pass a list of VPlanPtrs to removePlansExcept I have to first call getBestPlanFor to get VPlanPtr references. However, those references become invalid after calling removePlansExcept! That means that in effect I have to perform this call sequence:

const VPlanPtr &PB1 = getBestPlanFor();
const VPlanPtr &PB2 = getBestPlanFor();
removePlansExcept({PB1, PB2});
const VPlanPtr &P1 = getBestPlanFor();
const VPlanPtr &P2 = getBestPlanFor();

This was the actual reason I passed in a list of VFs here instead. In order to pass in a list of VPlanPtrs I can think of three choices:

1. We change VPlanPtr to be simply "typedef VPlan *VPlanPtr;" and stop making it unique. This allows the VPlanPtr to be copied. Then I change getBestPlanFor to return const VPlanPtr instead of a reference, which allows me to pass a list of VPlanPtrs to removePlansExcept.
2. We don't remove the plans at all.
3. We stick with passing a list of VFs to removePlansExcept.

I'm also happy to listen to alternative suggestions! However, at the moment I can't really move forward with this patch.

[sdesmalen]

(Sorry for the slow reply, I was traveling last week)

My suggestion on the other patch was to make the code structurally simpler. Removing plans prematurely complicates things, because you need to carefully keep track which plans can be removed and which ones may be needed.
@bmahjour Is there a real problem with memory-usage that requires us to reduce the lifetime of these plans a little bit longer? If not, I'd like to suggest not removing the plans to keep the code simpler.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8209–8210

nit: odd spaces?

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8209–8210

Yeah, clang-format does that, which surprised me too. I can try to remove the spaces, but I have a feeling I will then be told to fix up formatting. :)

[bmahjour]

In D111125#3055328, @sdesmalen wrote:

(Sorry for the slow reply, I was traveling last week)

My suggestion on the other patch was to make the code structurally simpler. Removing plans prematurely complicates things, because you need to carefully keep track which plans can be removed and which ones may be needed.
@bmahjour Is there a real problem with memory-usage that requires us to reduce the lifetime of these plans a little bit longer? If not, I'd like to suggest not removing the plans to keep the code simpler.

I do not know of a "real problem", but would expect loops with large bodies would benefit from some level of garbage collection. I've proposed to delete plans at specific static locations in the code when we know we don't need them, so should not need extra book keeping. I think we are very close to a solution that deletes unused plans, but if there are further complications or controversies I'm ok with dealing with the garbage collection aspect as a separate patch.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

315

Hi @david-arm , sorry I was away last week. Yes, the references would indeed be invalidated as the container elements are moved around. However, the problem can be avoided by making getBestPlanFor and executePlan work with raw pointers. These functions simply use the passed vplan and do not alter it nor do they care about its ownership, so no need to pass them a smart pointer. Here's a patch I tried on top of yours that works fine:

pass-raw-ptr.patch4 KBDownload

[david-arm]

Hi @bmahjour, thanks a lot for sharing a patch to change the interfaces!

To address @sdesmalen's point that removePlansExcept introduces complexity to reduce the lifetime of vplans when their short lifetime may not have a noticable impact on memory usage, I did an experiment where I built the LLVM test suite with two versions of this patch: 1) Patch A that keeps all the vplans, 2) Patch B that removes the unneeded vplans. I recorded the memory usage of each compilation using /usr/bin/time -v and extracted the maximum resident memory each time. I then took the average of all these values to determine the average maximum resident memory usage. I found practically no difference in peak memory consumption between Patch A and B.

One benefit from keeping all vplans until after code-generation is that we avoid having to structure the code in a certain way (i.e. having to decide on all relevant vplans first, before removing the unnecessary ones and doing code-gen for the selected plans) and the code will look more natural. I also wondered if there would ever be a situation in future where we might need three or more plans? I realise it's a bit of a stretch, but I could imagine more layers, i.e. a main vector loop, a vector epilogue, and a predicated vector tail.

Anyway, any thoughts you have are appreciated!

[bmahjour]

Thanks for doing the experiment and collecting data on test-suite.

I don't feel strongly about this, but given that we've already spent a fair bit of effort discussing and implementing a solution, I slightly prefer to have a way to claim unused memory so we stay closer to the current state of the vectorizer, and be a bit more future-proof. I worry that vplans may get heavier or more numerous and that the test-suite may not be representative of the larger applications compiled with LLVM. That's my last two cents. I'll leave it up to you and/or other reviewers to make the final call.

[david-arm]

• Removed the removePlansExcept function.
• Changed getBestPlanFor to just return a raw "VPlan *" pointer.

[david-arm]

Hi @bmahjour, I hope you don't mind but I've gone with the simpler patch for now, which doesn't involve removing the vplans. However, if this becomes a problem in future or some buildbots flag up issues I'm happy to revisit this!

[bmahjour]

That's fine. LGTM.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8188–8189

can we instead return a reference?

8206

This seems a bit inaccurate now. Maybe it would be better to say Executing best plan with VF, UF or something like that?

[david-arm]

• Changed getBestPlanFor to return a reference.
• Updated the debug message in executePlan, which also required changing a test.

[sdesmalen]

Cheers @david-arm, LGTM!

[fhahn]

Thanks, LGTM

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

class LoopVectorizationPlanner {
 
   OptimizationRemarkEmitter *ORE;
 
   SmallVector<VPlanPtr, 4> VPlans;
 
   /// A builder used to construct the current plan.
   VPBuilder Builder;
 
-  /// The best number of elements of the vector types used in the
-  /// transformed loop. BestVF = None means that vectorization is
-  /// disabled.
-  Optional<ElementCount> BestVF = None;
-  unsigned BestUF = 0;
-
 public:
   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
                            const TargetTransformInfo *TTI,
                            LoopVectorizationLegality *Legal,
                            LoopVectorizationCostModel &CM,
                            InterleavedAccessInfo &IAI,
                            PredicatedScalarEvolution &PSE,
                            const LoopVectorizeHints &Hints,
                            LoopVectorizationRequirements &Requirements,
                            OptimizationRemarkEmitter *ORE)
       : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM), IAI(IAI),
         PSE(PSE), Hints(Hints), Requirements(Requirements), ORE(ORE) {}
 
   /// Plan how to best vectorize, return the best VF and its cost, or None if
   /// vectorization and interleaving should be avoided up front.
   Optional<VectorizationFactor> plan(ElementCount UserVF, unsigned UserIC);
 
   /// Use the VPlan-native path to plan how to best vectorize, return the best
   /// VF and its cost.
   VectorizationFactor planInVPlanNativePath(ElementCount UserVF);
 
-  /// Finalize the best decision and dispose of all other VPlans.
-  void setBestPlan(ElementCount VF, unsigned UF);
+  /// Return the best VPlan for the <VF,UF> pair.
+  const VPlanPtr &getBestPlanFor(ElementCount VF, unsigned UF) const;
 
   /// Generate the IR code for the body of the vectorized loop according to the
-  /// best selected VPlan.
-  void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
+  /// best selected VPlan \p BestPlan.
+  void executePlan(ElementCount VF, unsigned UF, const VPlanPtr &BestPlan,
+                   InnerLoopVectorizer &LB, DominatorTree *DT);
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void printPlans(raw_ostream &O);
 #endif
 
   /// Look through the existing plans and return true if we have one with all
   /// the vectorization factors in question.
   bool hasPlanWithVFs(const ArrayRef<ElementCount> VFs) const {
     return any_of(VPlans, [&](const VPlanPtr &Plan) {
       return all_of(VFs, [&](const ElementCount &VF) {
         return Plan->hasVF(VF);
       });
     });
   }
 
   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
   /// returned value holds for the entire \p Range.
   static bool
   getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
                            VFRange &Range);
 
 protected:
   /// Collect the instructions from the original loop that would be trivially
   /// dead in the vectorized loop if generated.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if ((ThresholdReached && !Hints.allowReordering()) ||
       LLVM_DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
       Hints.emitRemarkWithHints();
       return VectorizationFactor::Disabled();
     }
   }
   return SelectedVF;
 }
 
-void LoopVectorizationPlanner::setBestPlan(ElementCount VF, unsigned UF) {
+const VPlanPtr &LoopVectorizationPlanner::getBestPlanFor(ElementCount VF,
+                                                         unsigned UF) const {
   LLVM_DEBUG(dbgs() << "Setting best plan to VF=" << VF << ", UF=" << UF
                     << '\n');
-  BestVF = VF;
-  BestUF = UF;
 
-  erase_if(VPlans, [VF](const VPlanPtr &Plan) {
-    return !Plan->hasVF(VF);
-  });
-  assert(VPlans.size() == 1 && "Best VF has not a single VPlan.");
+  assert(count_if(VPlans,
+                  [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==
+             1 &&
+         "Best VF has not a single VPlan.");
+
+  for (const VPlanPtr &Plan : VPlans) {
+    if (Plan->hasVF(VF))
+      return Plan;
+  }
+  llvm_unreachable("No plan found!");
 }
 
-void LoopVectorizationPlanner::executePlan(InnerLoopVectorizer &ILV,
+void LoopVectorizationPlanner::executePlan(ElementCount BestVF, unsigned BestUF,
+                                           const VPlanPtr &BestVPlan,
+                                           InnerLoopVectorizer &ILV,
                                            DominatorTree *DT) {
   // Perform the actual loop transformation.
 
   // 1. Create a new empty loop. Unlink the old loop and connect the new one.
-  assert(BestVF.hasValue() && "Vectorization Factor is missing");
-  assert(VPlans.size() == 1 && "Not a single VPlan to execute.");
-
-  VPTransformState State{
-      *BestVF, BestUF, LI, DT, ILV.Builder, &ILV, VPlans.front().get()};
+  VPTransformState State{BestVF, BestUF,         LI, DT, ILV.Builder,
+                         &ILV,   BestVPlan.get()};
   State.CFG.PrevBB = ILV.createVectorizedLoopSkeleton();
   State.TripCount = ILV.getOrCreateTripCount(nullptr);
   State.CanonicalIV = ILV.Induction;
 
   ILV.printDebugTracesAtStart();
 
   //===------------------------------------------------===//
   //
   // Notice: any optimization or new instruction that go
   // into the code below should also be implemented in
   // the cost-model.
   //
   //===------------------------------------------------===//
 
   // 2. Copy and widen instructions from the old loop into the new loop.
-  VPlans.front()->execute(&State);
+  BestVPlan->execute(&State);
 
   // 3. Fix the vectorized code: take care of header phi's, live-outs,
   //    predication, updating analyses.
   ILV.fixVectorizedLoop(State);
 
   ILV.printDebugTracesAtEnd();
 }
 
static bool processLoopInVPlanNativePath(
 
   // If we are stress testing VPlan builds, do not attempt to generate vector
   // code. Masked vector code generation support will follow soon.
   // Also, do not attempt to vectorize if no vector code will be produced.
   if (VPlanBuildStressTest || EnableVPlanPredication ||
       VectorizationFactor::Disabled() == VF)
     return false;
 
-  LVP.setBestPlan(VF.Width, 1);
+  const VPlanPtr &BestPlan = LVP.getBestPlanFor(VF.Width, 1);
 
   {
     GeneratedRTChecks Checks(*PSE.getSE(), DT, LI,
                              F->getParent()->getDataLayout());
     InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, 1, LVL,
                            &CM, BFI, PSI, Checks);
     LLVM_DEBUG(dbgs() << "Vectorizing outer loop in \""
                       << L->getHeader()->getParent()->getName() << "\"\n");
-    LVP.executePlan(LB, DT);
+    LVP.executePlan(VF.Width, 1, BestPlan, LB, DT);
   }
 
   // Mark the loop as already vectorized to avoid vectorizing again.
   Hints.setAlreadyVectorized();
   assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()));
   return true;
 }
 
#endif /* NDEBUG */
   {
     // Optimistically generate runtime checks. Drop them if they turn out to not
     // be profitable. Limit the scope of Checks, so the cleanup happens
     // immediately after vector codegeneration is done.
     GeneratedRTChecks Checks(*PSE.getSE(), DT, LI,
                              F->getParent()->getDataLayout());
     if (!VF.Width.isScalar() || IC > 1)
       Checks.Create(L, *LVL.getLAI(), PSE.getUnionPredicate());
-    LVP.setBestPlan(VF.Width, IC);
+    const VPlanPtr &BestPlan = LVP.getBestPlanFor(VF.Width, IC);
 
     using namespace ore;
     if (!VectorizeLoop) {
       assert(IC > 1 && "interleave count should not be 1 or 0");
       // If we decided that it is not legal to vectorize the loop, then
       // interleave it.
       InnerLoopUnroller Unroller(L, PSE, LI, DT, TLI, TTI, AC, ORE, IC, &LVL,
                                  &CM, BFI, PSI, Checks);
-      LVP.executePlan(Unroller, DT);
+      LVP.executePlan(VF.Width, IC, BestPlan, Unroller, DT);
 
       ORE->emit([&]() {
         return OptimizationRemark(LV_NAME, "Interleaved", L->getStartLoc(),
                                   L->getHeader())
                << "interleaved loop (interleaved count: "
                << NV("InterleaveCount", IC) << ")";
       });
     } else {
       // If we decided that it is *legal* to vectorize the loop, then do it.
 
       // Consider vectorizing the epilogue too if it's profitable.
       VectorizationFactor EpilogueVF =
           CM.selectEpilogueVectorizationFactor(VF.Width, LVP);
       if (EpilogueVF.Width.isVector()) {
 
         // The first pass vectorizes the main loop and creates a scalar epilogue
         // to be vectorized by executing the plan (potentially with a different
         // factor) again shortly afterwards.
         EpilogueLoopVectorizationInfo EPI(VF.Width, IC, EpilogueVF.Width, 1);
         EpilogueVectorizerMainLoop MainILV(L, PSE, LI, DT, TLI, TTI, AC, ORE,
                                            EPI, &LVL, &CM, BFI, PSI, Checks);
 
-        LVP.setBestPlan(EPI.MainLoopVF, EPI.MainLoopUF);
-        LVP.executePlan(MainILV, DT);
+        const VPlanPtr &BestPlan =
+            LVP.getBestPlanFor(EPI.MainLoopVF, EPI.MainLoopUF);
+        LVP.executePlan(EPI.MainLoopVF, EPI.MainLoopUF, BestPlan, MainILV, DT);
         ++LoopsVectorized;
 
         simplifyLoop(L, DT, LI, SE, AC, nullptr, false /* PreserveLCSSA */);
         formLCSSARecursively(*L, *DT, LI, SE);
 
         // Second pass vectorizes the epilogue and adjusts the control flow
         // edges from the first pass.
-        LVP.setBestPlan(EPI.EpilogueVF, EPI.EpilogueUF);
+        const VPlanPtr &BestPlan2 =
+            LVP.getBestPlanFor(EPI.EpilogueVF, EPI.EpilogueUF);
         EPI.MainLoopVF = EPI.EpilogueVF;
         EPI.MainLoopUF = EPI.EpilogueUF;
         EpilogueVectorizerEpilogueLoop EpilogILV(L, PSE, LI, DT, TLI, TTI, AC,
                                                  ORE, EPI, &LVL, &CM, BFI, PSI,
                                                  Checks);
-        LVP.executePlan(EpilogILV, DT);
+        LVP.executePlan(EPI.EpilogueVF, EPI.EpilogueUF, BestPlan2, EpilogILV,
+                        DT);
         ++LoopsEpilogueVectorized;
 
         if (!MainILV.areSafetyChecksAdded())
           DisableRuntimeUnroll = true;
       } else {
         InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, IC,
                                &LVL, &CM, BFI, PSI, Checks);
-        LVP.executePlan(LB, DT);
+        LVP.executePlan(VF.Width, IC, BestPlan, LB, DT);
         ++LoopsVectorized;
 
         // Add metadata to disable runtime unrolling a scalar loop when there
         // are no runtime checks about strides and memory. A scalar loop that is
         // rarely used is not worth unrolling.
         if (!LB.areSafetyChecksAdded())
           DisableRuntimeUnroll = true;
       }