[NFC][InstructionCost] Refactor LoopVectorizationCostModel::selectVectorizationFactor

[david-arm]

Summary

This patch is the first of two patches that are designed to migrate
costs in LoopVectorize.cpp to use the new InstructionCost class.
This refactoring is necessary preparation for the second part, which
switches from using float cost to InstructionCost. The tuple is
introduced here because the InstructionCost could be invalid and
so it's not possible to maintain a running cost value in the loop
that divides the cost by the width.

See this patch for the introduction of the type: https://reviews.llvm.org/D91174
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/2020-November/146408.html

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

std::pair<unsigned, unsigned>

5415

std::pair<unsigned, unsigned> ScalarCost = {ExpectedCost, 1}

5422

std::numeric_limits<unsigned>::max() ?

5435

std::pair<unsigned, unsigned> (that also allows removing the cast on line 5461)

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

This is no longer a NFC change if I use unsigned. This changes the behaviour of cases where different vectorisation factors produce fractional, and different, costs. For example, (float) 10 / 2 is less than (float) 11 / 2, whereas using integers would give the same result of 5. I don't mind making the change, but then I think I should remove NFC from the subject line.

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

I think what I can do keep it as NFC is simultaneously change float->unsigned and change the algorithm in isLowerVectorCost() to do the same as the dependent patch - D92178. That way we'd still make the same choice of VF as before.

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

Perhaps I misunderstood, but I thought the reason for having this as a std::pair is so that you can postpone the division itself, i.e. the MinimumCost is ExpectedCost / 1, and later on as VectorCost / i, where the MinimumCost variable itself is represented as {ExpectedCost, 1} and {VectorCost, i}. You'd need to add a cast in isLowerVectorCost to make sure both LHS and RHS of the comparison are evaluated as float.

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

Ah yes I see, that would work. I'll update the patch!

[david-arm]

• Changed float->unsigned in the tuple used for selecting vectorisation factors.

[sdesmalen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5415

I think you missed this one. This would remove the need for {ScalarCost, 1} on line 5456.

5437

nit: cast is no longer necessary?

5460

nit: return {ElementCount::getFixed(MinCost.second), MinCost.first};

[ctetreau]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

Why was this removed?

[david-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

Not sure which line you're referring to here - the debug line is still there I think?

[ctetreau]

I don't think you needs these pairs. If you check validity of the InstructionCost in the for loop, and break or continue if it's invalid, then you can just use a scalar value as it did before. (I commented as such on D92178)

Since this patch just adds the pair, you should be able to abandon it (unless I'm missing something)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5414

ahh, I see it now. The diff has it in all-red, but it looks like you just shuffled some lines.

[david-arm]

After some recent upstream discussions in the SVE sync call this patch is no longer needed.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

LoopVectorizationCostModel::computeFeasibleMaxVF(unsigned ConstTripCount) {
   }
   return ElementCount::getFixed(MaxVF);
 }
 
 VectorizationFactor
 LoopVectorizationCostModel::selectVectorizationFactor(ElementCount MaxVF) {
   assert(!MaxVF.isScalable() && "scalable vectors not yet supported");
 
-  float Cost = expectedCost(ElementCount::getFixed(1)).first;
-  const float ScalarCost = Cost;
-  unsigned Width = 1;
-  LLVM_DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)ScalarCost << ".\n");
+  unsigned ExpectedCost = expectedCost(ElementCount::getFixed(1)).first;
+  LLVM_DEBUG(dbgs() << "LV: Scalar loop costs: " << ExpectedCost << ".\n");
+
+  std::pair<float, unsigned> MinCost = {ExpectedCost, 1};
+  const float ScalarCost = ExpectedCost;
 
   bool ForceVectorization = Hints->getForce() == LoopVectorizeHints::FK_Enabled;
   if (ForceVectorization && MaxVF.isVector()) {
     // Ignore scalar width, because the user explicitly wants vectorization.
     // Initialize cost to max so that VF = 2 is, at least, chosen during cost
     // evaluation.
-    Cost = std::numeric_limits<float>::max();
+    MinCost.first = std::numeric_limits<float>::max();
   }
 
+  auto isLowerVectorCost = [](std::pair<float, unsigned> LHS,
+                              std::pair<float, unsigned> RHS) {
+    return (LHS.first / LHS.second) < (RHS.first / RHS.second);
+  };
+
   for (unsigned i = 2; i <= MaxVF.getFixedValue(); i *= 2) {
     // Notice that the vector loop needs to be executed less times, so
     // we need to divide the cost of the vector loops by the width of
     // the vector elements.
     VectorizationCostTy C = expectedCost(ElementCount::getFixed(i));
-    float VectorCost = C.first / (float)i;
+    std::pair<float, unsigned> VectorCost = {C.first, i};
     LLVM_DEBUG(dbgs() << "LV: Vector loop of width " << i
-                      << " costs: " << (int)VectorCost << ".\n");
+                      << " costs: " << (int)(C.first / i) << ".\n");
     if (!C.second && !ForceVectorization) {
       LLVM_DEBUG(
           dbgs() << "LV: Not considering vector loop of width " << i
                  << " because it will not generate any vector instructions.\n");
       continue;
     }
-    if (VectorCost < Cost) {
-      Cost = VectorCost;
-      Width = i;
-    }
+    if (isLowerVectorCost(VectorCost, MinCost))
+      MinCost = VectorCost;
   }
 
   if (!EnableCondStoresVectorization && NumPredStores) {
     reportVectorizationFailure("There are conditional stores.",
         "store that is conditionally executed prevents vectorization",
         "ConditionalStore", ORE, TheLoop);
-    Width = 1;
-    Cost = ScalarCost;
+    MinCost = {ScalarCost, 1};
   }
 
-  LLVM_DEBUG(if (ForceVectorization && Width > 1 && Cost >= ScalarCost) dbgs()
+  LLVM_DEBUG(if (ForceVectorization && MinCost.second > 1 &&
+                 isLowerVectorCost({ScalarCost, 1}, MinCost)) dbgs()
              << "LV: Vectorization seems to be not beneficial, "
              << "but was forced by a user.\n");
-  LLVM_DEBUG(dbgs() << "LV: Selecting VF: " << Width << ".\n");
-  VectorizationFactor Factor = {ElementCount::getFixed(Width),
-                                (unsigned)(Width * Cost)};
-  return Factor;
+  LLVM_DEBUG(dbgs() << "LV: Selecting VF: " << MinCost.second << ".\n");
+  ElementCount EC = ElementCount::getFixed(MinCost.second);
+  return {EC, (unsigned)MinCost.first};
 }
 
 std::pair<unsigned, unsigned>
 LoopVectorizationCostModel::getSmallestAndWidestTypes() {
   unsigned MinWidth = -1U;
   unsigned MaxWidth = 8;
   const DataLayout &DL = TheFunction->getParent()->getDataLayout();