[NFC][InstructionCost]Migrate VectorCombine.cpp to use InstructionCost

[CarolineConcatto]

Summary

This patch changes these functions:
  vectorizeLoadInsert
  isExtractExtractCheap
  foldExtractedCmps
  scalarizeBinopOrCmp
  getShuffleExtract
  foldBitcastShuf
  to use the class InstructionCost when calling TTI.get<something>Cost().

  This patch is part of a series of patches to use InstructionCost instead of
   unsigned/int for the cost model functions.
  See this thread for context:
      http://lists.llvm.org/pipermail/llvm-dev/2020-November/146408.html
  See this patch for the introduction of the type:
      https://reviews.llvm.org/D91174

Observation: 
 This patch adds the test || !NewCost.isValid(), because we want to
  return false when:
   !NewCost.isValid && !OldCost.isValid()->the cost to transform it expensive
  and
   !NewCost.isValid() && OldCost.isValid()
  Therefore for simplication we only add  test for !NewCost.isValid()

[ctetreau]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

201

the or is redundant.

259

Because of this assert, the branches will never be taken. This will result in different behavior in release vs debug mode.

Either remove the assert, or remove the two early returns.

Regardless, invalid costs are guaranteed to compare higher than valid costs, so the early returns are redundant.

321

can std::min be used here? InstructionCost has overloaded comparison operators and a total ordering.

Assuming it can be, we should probably get rid of InstructionCost::min and InstructionCost::max. That can be a different patch.

363–364

this is redundant. If OldCost is valid, and NewCost is invalid, then OldCost < NewCost returns true.

526

the or is redundant

636

the or is redundant

737

the or is redundant

[david-arm]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

259

Hi @ctetreau, after discussion during the last SVE sync call @paulwalker-arm thought we shouldn't be relying upon the lexicographical ordering that defines invalid costs to be infinitely expensive. He suggested that doing so is actually a bug in the code. So the route we've been taking so far is to either check for validity explicitly or assert that it's valid. If you think this is the wrong approach here then we can perhaps discuss it and agree on a consistent approach?

363–364

Again, @CarolineConcatto is just adding checks here as per discussion on the last SVE sync call, but we're happy to discuss the correct approach.

[spatel]

I haven't followed the details enough to comment on the changes directly, but thanks for the cleanup! The mismatched signed/unsigned cost model APIs are/were a mess.

[ctetreau]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

259

I'm not sure how I missed that conversation, but as you may recall from the review thread for D91174, I fought hard for the total ordering to be added and documented so that it's guaranteed to be true. This is exactly the sort of case you'd want to this ordering for; the validity checks are guaranteed to be redundant with the greater-than checks. Additionally, adding the redundant validity checks is more error prone, because it's more operator-heavy lines of code you can mess up.

[paulwalker-arm]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

259

To be clear I have nothing against relying on the total ordering but I feel if the transformation is expecting instructions to have an actual cost then it should either assert or explicitly check for such. An example of this is LoopVectorize where there has already been extensive validation to ensure a loop is vectorisable and thus not being able to cost the loop is a sure sign there's either a bug in LoopVectorize's isLegal code or the cost functions themselves.

[sdesmalen]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

259

It seems that the algorithm requires at least one of the Costs to be valid (it has to choose either Ext0 or Ext1), so if the assert is changed to:

assert((Cost0.isValid() || Cost1.isValid()) && "At least one of Cost0 and Cost1 should be valid");

the existing code below should be sufficient and the two early returns that were added can be removed like @ctetreau suggested.

363–364

Similar to above, change the assert to check OldCost.isValid() || NewCost.isValid() and remove the early exit.

[CarolineConcatto]

-remove redundat invalid check

[CarolineConcatto]

Thank you, everyone, for the review.
I have removed the redundant invalid check.
Also, thank you for making clear that invalid, atm, means as well high cost.
I'll have that in mind for the next patches.

[ctetreau]

In D94069#2489637, @CarolineConcatto wrote:

Also, thank you for making clear that invalid, atm, means as well high cost.
I'll have that in mind for the next patches.

I would say "infinitely costly", not "high cost". Somebody may have "a lot" of LLVMBucks, nobody has infinity LLVMBucks.

Sorry to nitpick, but it's important to get these things right initially before everybody sees some flawed example and emulates it. If you need something to have a really high cost, you should just pick some really high valid cost. If you need something to never be within any cost budget, you should use invalid.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

259

To be clear I have nothing against relying on the total ordering but I feel if the transformation is expecting instructions to have an actual cost then it should either assert or explicitly check for such.

If it's an honest-to-gosh bug for some call to return invalid, then this is fine. I feel like this should never happen in any function that returns InstructionCost though. This would be akin to swallowing an exception and calling exit().

[ctetreau]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

200

Is this needed?

• If the old cost is invalid, but the new cost is valid, then do the transform.
• If neither cost is valid, then OldCost < NewCost will cause a return of false.

253

Reasonable to return nullptr?

If neither cost is valid, then neither of the inputs should be replaced

359–360

Would it be reasonable to return false here? If all costs involved are invalid, then I would say the transform is not cheap.

525

reasonable to return false here? If neither cost is valid, then do not do the transform

635

reasonable to return false?

736

reasonable to return false?

[CarolineConcatto]

-remove asserts for OldCost invalid
-add return if both costs are invalid

[CarolineConcatto]

Hi @ctetreau,
Thank you for the review.
So I removed all the asserts and added the earlier return if both costs are invalid, because in this case it means that the transformation is not cheap.
If only OldCost is invalid I believe we should do nothing, for the same reason I removed the test for !NewCost.isValid().

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

253

I think it is fine to add if the test if both are equal following the logic of if (Index0 == Index1)

359–360

If I remove the assert and leave the test to do its job the return will be false, because OldCost would be equal to NewCost.

635

If both are invalid, maybe.
But if OldCost is invalid I think you mean return true, because OldCost>NewCost
And in this last case I don't think we should add the earlier return because it is a change on the code path.

736

If both are invalid, maybe.
But if OldCost is invalid I think you mean return true, because OldCost>NewCost
And in this last case I don't think we should add the earlier return because it is a change on the code path.

[CarolineConcatto]

-add missing invalid costs test for scalarizeBinopOrCmp

[sdesmalen]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

525

Does this assert need to be removed still?

[CarolineConcatto]

-remove missed assert

[CarolineConcatto]

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

525

Yes, sorry missed that!

[sdesmalen]

Added two nits, but LGTM otherwise.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

635

nit: || !NewCost.isValid() should be sufficient (see the other comment).

737

I don't think the or was redundant.

If the new cost is invalid, then it shouldn't do the transform. With only testing OldCost < NewCost, we'd get:

        isValid?
   OldCost  NewCost       (OldCost < NewCost)     result
--------------------------------------------------------
1.    true    true     OldCost.Val < NewCost.Val    ?
2.    true    false          Valid < Invalid       true
3.    false   true         Invalid < Valid        false
4.    false   false        Invalid < Invalid      false

However, 4. should be 'true' in order to return early from the function.

         isValid?
   OldCost  NewCost  (OldCost < NewCost || !NewCost.isValid)    result
-----------------------------------------------------------------------
1.    true    true      OldCost.Val < NewCost.Val || false        ?
2.    true    false           Valid < Invalid || true            true
3.    false   true          Invalid < Valid   || false          false
4.    false   false         Invalid < Invalid || true            true

Gives us the result we want.

nit: based on that I believe !OldCost.isValid() && is now redundant.

[CarolineConcatto]

-replace (!NewCost.isValid && !OldCost.isvalid()) by !NewCost.isValid()

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), DL, Load, &DT)) {
     // negation does not change the result of the alignment calculation.
     Alignment = commonAlignment(Alignment, Offset.getZExtValue());
   }
 
   // Original pattern: insertelt undef, load [free casts of] PtrOp, 0
   // Use the greater of the alignment on the load or its source pointer.
   Alignment = std::max(SrcPtr->getPointerAlignment(DL), Alignment);
   Type *LoadTy = Load->getType();
-  int OldCost = TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
+  InstructionCost OldCost =
+      TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
   APInt DemandedElts = APInt::getOneBitSet(MinVecNumElts, 0);
   OldCost += TTI.getScalarizationOverhead(MinVecTy, DemandedElts,
                                           /* Insert */ true, HasExtract);
 
   // New pattern: load VecPtr
-  int NewCost = TTI.getMemoryOpCost(Instruction::Load, MinVecTy, Alignment, AS);
+  InstructionCost NewCost =
+      TTI.getMemoryOpCost(Instruction::Load, MinVecTy, Alignment, AS);
   // Optionally, we are shuffling the loaded vector element(s) into place.
   if (OffsetEltIndex)
     NewCost += TTI.getShuffleCost(TTI::SK_PermuteSingleSrc, MinVecTy);
 
   // We can aggressively convert to the vector form because the backend can
   // invert this transform if it does not result in a performance win.
-  if (OldCost < NewCost)
+  if (OldCost < NewCost || !NewCost.isValid())
     return false;
 
   // It is safe and potentially profitable to load a vector directly:
   // inselt undef, load Scalar, 0 --> load VecPtr
   IRBuilder<> Builder(Load);
   Value *CastedPtr = Builder.CreateBitCast(SrcPtr, MinVecTy->getPointerTo(AS));
   Value *VecLd = Builder.CreateAlignedLoad(MinVecTy, CastedPtr, Alignment);
 
   // Set everything but element 0 to undef to prevent poison from propagating
ExtractElementInst *VectorCombine::getShuffleExtract(
   unsigned Index1 = cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue();
 
   // If the extract indexes are identical, no shuffle is needed.
   if (Index0 == Index1)
     return nullptr;
 
   Type *VecTy = Ext0->getVectorOperand()->getType();
   assert(VecTy == Ext1->getVectorOperand()->getType() && "Need matching types");
-  int Cost0 = TTI.getVectorInstrCost(Ext0->getOpcode(), VecTy, Index0);
-  int Cost1 = TTI.getVectorInstrCost(Ext1->getOpcode(), VecTy, Index1);
+  InstructionCost Cost0 =
+      TTI.getVectorInstrCost(Ext0->getOpcode(), VecTy, Index0);
+  InstructionCost Cost1 =
+      TTI.getVectorInstrCost(Ext1->getOpcode(), VecTy, Index1);
+
+  // If both costs are invalid no shuffle is needed
+  if (!Cost0.isValid() && !Cost1.isValid())
+    return nullptr;
 
   // We are extracting from 2 different indexes, so one operand must be shuffled
   // before performing a vector operation and/or extract. The more expensive
   // extract will be replaced by a shuffle.
   if (Cost0 > Cost1)
     return Ext0;
   if (Cost1 > Cost0)
     return Ext1;
 
   // If the costs are equal and there is a preferred extract index, shuffle the
   // opposite operand.
   if (PreferredExtractIndex == Index0)
     return Ext1;
   if (PreferredExtractIndex == Index1)
     return Ext0;
 
bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
                                           unsigned Opcode,
                                           ExtractElementInst *&ConvertToShuffle,
                                           unsigned PreferredExtractIndex) {
   assert(isa<ConstantInt>(Ext0->getOperand(1)) &&
          isa<ConstantInt>(Ext1->getOperand(1)) &&
          "Expected constant extract indexes");
   Type *ScalarTy = Ext0->getType();
   auto *VecTy = cast<VectorType>(Ext0->getOperand(0)->getType());
-  int ScalarOpCost, VectorOpCost;
+  InstructionCost ScalarOpCost, VectorOpCost;
 
   // Get cost estimates for scalar and vector versions of the operation.
   bool IsBinOp = Instruction::isBinaryOp(Opcode);
   if (IsBinOp) {
     ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
     VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
   } else {
     assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
            "Expected a compare");
     ScalarOpCost = TTI.getCmpSelInstrCost(Opcode, ScalarTy,
                                           CmpInst::makeCmpResultType(ScalarTy));
     VectorOpCost = TTI.getCmpSelInstrCost(Opcode, VecTy,
                                           CmpInst::makeCmpResultType(VecTy));
   }
 
   // Get cost estimates for the extract elements. These costs will factor into
   // both sequences.
   unsigned Ext0Index = cast<ConstantInt>(Ext0->getOperand(1))->getZExtValue();
   unsigned Ext1Index = cast<ConstantInt>(Ext1->getOperand(1))->getZExtValue();
 
-  int Extract0Cost =
+  InstructionCost Extract0Cost =
       TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, Ext0Index);
-  int Extract1Cost =
+  InstructionCost Extract1Cost =
       TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, Ext1Index);
 
   // A more expensive extract will always be replaced by a splat shuffle.
   // For example, if Ext0 is more expensive:
   // opcode (extelt V0, Ext0), (ext V1, Ext1) -->
   // extelt (opcode (splat V0, Ext0), V1), Ext1
   // TODO: Evaluate whether that always results in lowest cost. Alternatively,
   //       check the cost of creating a broadcast shuffle and shuffling both
   //       operands to element 0.
-  int CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
+  InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
 
   // Extra uses of the extracts mean that we include those costs in the
   // vector total because those instructions will not be eliminated.
-  int OldCost, NewCost;
+  InstructionCost OldCost, NewCost;
   if (Ext0->getOperand(0) == Ext1->getOperand(0) && Ext0Index == Ext1Index) {
     // Handle a special case. If the 2 extracts are identical, adjust the
     // formulas to account for that. The extra use charge allows for either the
     // CSE'd pattern or an unoptimized form with identical values:
     // opcode (extelt V, C), (extelt V, C) --> extelt (opcode V, V), C
     bool HasUseTax = Ext0 == Ext1 ? !Ext0->hasNUses(2)
                                   : !Ext0->hasOneUse() || !Ext1->hasOneUse();
     OldCost = CheapExtractCost + ScalarOpCost;
if (ConvertToShuffle) {
     // extraction lane. Therefore, it is a splat shuffle. Ex:
     // ShufMask = { undef, undef, 0, undef }
     // TODO: The cost model has an option for a "broadcast" shuffle
     //       (splat-from-element-0), but no option for a more general splat.
     NewCost +=
         TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
   }
 
   // Aggressively form a vector op if the cost is equal because the transform
   // may enable further optimization.
   // Codegen can reverse this transform (scalarize) if it was not profitable.
   return OldCost < NewCost;
 }
 
 /// Create a shuffle that translates (shifts) 1 element from the input vector
 /// to a new element location.
 static Value *createShiftShuffle(Value *Vec, unsigned OldIndex,
                                  unsigned NewIndex, IRBuilder<> &Builder) {
   // The shuffle mask is undefined except for 1 lane that is being translated
   // to the new element index. Example for OldIndex == 2 and NewIndex == 0:
   // ShufMask = { 2, undef, undef, undef }
   auto *VecTy = cast<FixedVectorType>(Vec->getType());
bool VectorCombine::foldBitcastShuf(Instruction &I) {
   // TODO: We could allow any shuffle.
   auto *DestTy = dyn_cast<FixedVectorType>(I.getType());
   auto *SrcTy = dyn_cast<FixedVectorType>(V->getType());
   if (!SrcTy || !DestTy || I.getOperand(0)->getType() != SrcTy)
     return false;
 
   // The new shuffle must not cost more than the old shuffle. The bitcast is
   // moved ahead of the shuffle, so assume that it has the same cost as before.
-  if (TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, DestTy) >
-      TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, SrcTy))
+  InstructionCost DestCost =
+      TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, DestTy);
+  InstructionCost SrcCost =
+      TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, SrcTy);
+  if (DestCost > SrcCost || !DestCost.isValid())
     return false;
 
   unsigned DestNumElts = DestTy->getNumElements();
   unsigned SrcNumElts = SrcTy->getNumElements();
   SmallVector<int, 16> NewMask;
   if (SrcNumElts <= DestNumElts) {
     // The bitcast is from wide to narrow/equal elements. The shuffle mask can
     // always be expanded to the equivalent form choosing narrower elements.
     assert(DestNumElts % SrcNumElts == 0 && "Unexpected shuffle mask");
bool VectorCombine::scalarizeBinopOrCmp(Instruction &I) {
   Type *VecTy = I.getType();
   assert(VecTy->isVectorTy() &&
          (IsConst0 || IsConst1 || V0->getType() == V1->getType()) &&
          (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() ||
           ScalarTy->isPointerTy()) &&
          "Unexpected types for insert element into binop or cmp");
 
   unsigned Opcode = I.getOpcode();
-  int ScalarOpCost, VectorOpCost;
+  InstructionCost ScalarOpCost, VectorOpCost;
   if (IsCmp) {
     ScalarOpCost = TTI.getCmpSelInstrCost(Opcode, ScalarTy);
     VectorOpCost = TTI.getCmpSelInstrCost(Opcode, VecTy);
   } else {
     ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
     VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
   }
 
   // Get cost estimate for the insert element. This cost will factor into
   // both sequences.
-  int InsertCost =
+  InstructionCost InsertCost =
       TTI.getVectorInstrCost(Instruction::InsertElement, VecTy, Index);
-  int OldCost = (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) +
-                VectorOpCost;
-  int NewCost = ScalarOpCost + InsertCost +
+  InstructionCost OldCost =
+      (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) + VectorOpCost;
+  InstructionCost NewCost = ScalarOpCost + InsertCost +
                             (IsConst0 ? 0 : !Ins0->hasOneUse() * InsertCost) +
                             (IsConst1 ? 0 : !Ins1->hasOneUse() * InsertCost);
 
   // We want to scalarize unless the vector variant actually has lower cost.
-  if (OldCost < NewCost)
+  if (OldCost < NewCost || !NewCost.isValid())
     return false;
 
   // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index) -->
   // inselt NewVecC, (scalar_op V0, V1), Index
   if (IsCmp)
     ++NumScalarCmp;
   else
     ++NumScalarBO;
 
bool VectorCombine::foldExtractedCmps(Instruction &I) {
   // binop i1 (cmp Pred (ext X, Index0), C0), (cmp Pred (ext X, Index1), C1)
   CmpInst::Predicate Pred = P0;
   unsigned CmpOpcode = CmpInst::isFPPredicate(Pred) ? Instruction::FCmp
                                                     : Instruction::ICmp;
   auto *VecTy = dyn_cast<FixedVectorType>(X->getType());
   if (!VecTy)
     return false;
 
-  int OldCost = TTI.getVectorInstrCost(Ext0->getOpcode(), VecTy, Index0);
+  InstructionCost OldCost =
+      TTI.getVectorInstrCost(Ext0->getOpcode(), VecTy, Index0);
   OldCost += TTI.getVectorInstrCost(Ext1->getOpcode(), VecTy, Index1);
   OldCost += TTI.getCmpSelInstrCost(CmpOpcode, I0->getType()) * 2;
   OldCost += TTI.getArithmeticInstrCost(I.getOpcode(), I.getType());
 
   // The proposed vector pattern is:
   // vcmp = cmp Pred X, VecC
   // ext (binop vNi1 vcmp, (shuffle vcmp, Index1)), Index0
   int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
   int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
   auto *CmpTy = cast<FixedVectorType>(CmpInst::makeCmpResultType(X->getType()));
-  int NewCost = TTI.getCmpSelInstrCost(CmpOpcode, X->getType());
+  InstructionCost NewCost = TTI.getCmpSelInstrCost(CmpOpcode, X->getType());
   NewCost +=
       TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, CmpTy);
   NewCost += TTI.getArithmeticInstrCost(I.getOpcode(), CmpTy);
   NewCost += TTI.getVectorInstrCost(Ext0->getOpcode(), CmpTy, CheapIndex);
 
   // Aggressively form vector ops if the cost is equal because the transform
   // may enable further optimization.
   // Codegen can reverse this transform (scalarize) if it was not profitable.
-  if (OldCost < NewCost)
+  if (OldCost < NewCost || !NewCost.isValid())
     return false;
 
   // Create a vector constant from the 2 scalar constants.
   SmallVector<Constant *, 32> CmpC(VecTy->getNumElements(),
                                    UndefValue::get(VecTy->getElementType()));
   CmpC[Index0] = C0;
   CmpC[Index1] = C1;
   Value *VCmp = Builder.CreateCmp(Pred, X, ConstantVector::get(CmpC));