[SLP][TTI][X86] Implement addsub cost calculation.

[vporpo]

Summary

This patch adds support for the addsub instructions in SLP's getEntryCost().
This relies on extending TTI->getShuffleCost() to return the correct cost
for such instructions.

[vporpo]

Moved the cost calculation code from getShuffleCost() to a separate function: getAltInstrCost().

[vporpo]

Rebased.

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   /// passed through \p Args, which helps improve the cost estimation in some
   /// cases, like in broadcast loads.
   /// NOTE: For subvector extractions Tp represents the source type.
   InstructionCost getShuffleCost(ShuffleKind Kind, VectorType *Tp,
                                  ArrayRef<int> Mask = None, int Index = 0,
                                  VectorType *SubTp = nullptr,
                                  ArrayRef<const Value *> Args = None) const;
 
+  /// \Returns the cost of an add-sub instruction. This corresponds to a shuffle
+  /// + fadd + fsub pattern in IR.
+  InstructionCost getAltInstrCost(VectorType *VecTy, ArrayRef<int> ShuffleMask,
+                                  ArrayRef<const Instruction *> Args) const;
+
   /// Represents a hint about the context in which a cast is used.
   ///
   /// For zext/sext, the context of the cast is the operand, which must be a
   /// load of some kind. For trunc, the context is of the cast is the single
   /// user of the instruction, which must be a store of some kind.
   ///
   /// This enum allows the vectorizer to give getCastInstrCost an idea of the
   /// type of cast it's dealing with, as not every cast is equal. For instance,
virtual InstructionCost getArithmeticInstrCost(
       unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind,
       OperandValueKind Opd1Info, OperandValueKind Opd2Info,
       OperandValueProperties Opd1PropInfo, OperandValueProperties Opd2PropInfo,
       ArrayRef<const Value *> Args, const Instruction *CxtI = nullptr) = 0;
   virtual InstructionCost getShuffleCost(ShuffleKind Kind, VectorType *Tp,
                                          ArrayRef<int> Mask, int Index,
                                          VectorType *SubTp,
                                          ArrayRef<const Value *> Args) = 0;
+  virtual InstructionCost
+  getAltInstrCost(VectorType *VecTy, ArrayRef<int> ShuffleMask,
+                  ArrayRef<const Instruction *> Args) const = 0;
   virtual InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst,
                                            Type *Src, CastContextHint CCH,
                                            TTI::TargetCostKind CostKind,
                                            const Instruction *I) = 0;
   virtual InstructionCost getExtractWithExtendCost(unsigned Opcode, Type *Dst,
                                                    VectorType *VecTy,
                                                    unsigned Index) = 0;
   virtual InstructionCost getCFInstrCost(unsigned Opcode,
return Impl.getArithmeticInstrCost(Opcode, Ty, CostKind, Opd1Info, Opd2Info,
                                        Opd1PropInfo, Opd2PropInfo, Args, CxtI);
   }
   InstructionCost getShuffleCost(ShuffleKind Kind, VectorType *Tp,
                                  ArrayRef<int> Mask, int Index,
                                  VectorType *SubTp,
                                  ArrayRef<const Value *> Args) override {
     return Impl.getShuffleCost(Kind, Tp, Mask, Index, SubTp, Args);
   }
+  InstructionCost
+  getAltInstrCost(VectorType *VecTy, ArrayRef<int> ShuffleMask,
+                  ArrayRef<const Instruction *> Args) const override {
+    return Impl.getAltInstrCost(VecTy, ShuffleMask, Args);
+  }
   InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src,
                                    CastContextHint CCH,
                                    TTI::TargetCostKind CostKind,
                                    const Instruction *I) override {
     return Impl.getCastInstrCost(Opcode, Dst, Src, CCH, CostKind, I);
   }
   InstructionCost getExtractWithExtendCost(unsigned Opcode, Type *Dst,
                                            VectorType *VecTy,

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   InstructionCost getShuffleCost(TTI::ShuffleKind Kind, VectorType *Ty,
                                  ArrayRef<int> Mask, int Index,
                                  VectorType *SubTp,
                                  ArrayRef<const Value *> Args = None) const {
     return 1;
   }
 
+  InstructionCost getAltInstrCost(VectorType *VecTy, ArrayRef<int> ShuffleMask,
+                                  ArrayRef<const Instruction *> Args) const {
+    return 1;
+  }
+
   InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src,
                                    TTI::CastContextHint CCH,
                                    TTI::TargetCostKind CostKind,
                                    const Instruction *I) const {
     switch (Opcode) {
     default:
       break;
     case Instruction::IntToPtr: {

llvm/lib/Analysis/TargetTransformInfo.cpp

InstructionCost TargetTransformInfo::getShuffleCost(
     ShuffleKind Kind, VectorType *Ty, ArrayRef<int> Mask, int Index,
     VectorType *SubTp, ArrayRef<const Value *> Args) const {
   InstructionCost Cost =
       TTIImpl->getShuffleCost(Kind, Ty, Mask, Index, SubTp, Args);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
+InstructionCost
+TargetTransformInfo::getAltInstrCost(VectorType *VecTy,
+                                     ArrayRef<int> ShuffleMask,
+                                     ArrayRef<const Instruction *> Args) const {
+  InstructionCost Cost = TTIImpl->getAltInstrCost(VecTy, ShuffleMask, Args);
+  assert(Cost >= 0 && "TTI should not produce negative costs!");
+  return Cost;
+}
+
 TTI::CastContextHint
 TargetTransformInfo::getCastContextHint(const Instruction *I) {
   if (!I)
     return CastContextHint::None;
 
   auto getLoadStoreKind = [](const Value *V, unsigned LdStOp, unsigned MaskedOp,
                              unsigned GatScatOp) {
     const Instruction *I = dyn_cast<Instruction>(V);

llvm/lib/Target/X86/X86TargetTransformInfo.h

InstructionCost getArithmeticInstrCost(
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None,
       ArrayRef<const Value *> Args = ArrayRef<const Value *>(),
       const Instruction *CxtI = nullptr);
   InstructionCost getShuffleCost(TTI::ShuffleKind Kind, VectorType *Tp,
                                  ArrayRef<int> Mask, int Index,
                                  VectorType *SubTp,
                                  ArrayRef<const Value *> Args = None);
+  InstructionCost getAltInstrCost(VectorType *VecTy, ArrayRef<int> ShuffleMask,
+                                  ArrayRef<const Instruction *> Args) const;
   InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src,
                                    TTI::CastContextHint CCH,
                                    TTI::TargetCostKind CostKind,
                                    const Instruction *I = nullptr);
   InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy,
                                      CmpInst::Predicate VecPred,
                                      TTI::TargetCostKind CostKind,
                                      const Instruction *I = nullptr);

llvm/lib/Target/X86/X86TargetTransformInfo.cpp

InstructionCost X86TTIImpl::getShuffleCost(TTI::ShuffleKind Kind,
 
   if (ST->hasSSE1())
     if (const auto *Entry = CostTableLookup(SSE1ShuffleTbl, Kind, LT.second))
       return LT.first * Entry->Cost;
 
   return BaseT::getShuffleCost(Kind, BaseTp, Mask, Index, SubTp);
 }
 
+InstructionCost
+X86TTIImpl::getAltInstrCost(VectorType *VecTy, ArrayRef<int> ShuffleMask,
+                            ArrayRef<const Instruction *> Args) const {
+  assert(cast<FixedVectorType>(VecTy)->getNumElements() == ShuffleMask.size() &&
+         "Expected same number of lanes");
+  assert(Args.size() == 2 && isa<BinaryOperator>(Args[0]) &&
+         isa<BinaryOperator>(Args[1]) && "Not an AddSub instruction");
+#ifndef NDEBUG
+  // For the Add-sub pattern we need the operands of the operands to be same:
+  unsigned Opcode0 = cast<BinaryOperator>(Args[0])->getOpcode();
+  unsigned Opcode1 = cast<BinaryOperator>(Args[1])->getOpcode();
+  SmallBitVector OpcodeMask(ShuffleMask.size(), 0);
+  unsigned NumLanes = ShuffleMask.size();
+  for (unsigned Lane : seq<unsigned>(0, NumLanes))
+    if (ShuffleMask[Lane] >= (int)NumLanes)
+      OpcodeMask.set(Lane);
+  assert(isLegalAltInstr(VecTy, Opcode0, Opcode1, OpcodeMask) &&
+         "We can only accept patterns matched by isLegalAltInstr()");
+#endif
+  if (ST->hasSSE3())
+    return 2; // 2xf32 addsubps, 2xf64 addsubpd
+  if (ST->hasAVX())
+    return 1; // 4xf32 vaddsubps, 2xf64 vaddsubpd
+  if (ST->hasAVX2())
+    return 1; // 8xf32 vaddsubps, 4xf64 vaddsubpd
+  llvm_unreachable("Should have been rejected by isLegalAltInstr()");
+}
+
 InstructionCost X86TTIImpl::getCastInstrCost(unsigned Opcode, Type *Dst,
                                              Type *Src,
                                              TTI::CastContextHint CCH,
                                              TTI::TargetCostKind CostKind,
                                              const Instruction *I) {
   int ISD = TLI->InstructionOpcodeToISD(Opcode);
   assert(ISD && "Invalid opcode");
 

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

public:
 
   /// Gets reordering data for the given tree entry. If the entry is vectorized
   /// - just return ReorderIndices, otherwise check if the scalars can be
   /// reordered and return the most optimal order.
   /// \param TopToBottom If true, include the order of vectorized stores and
   /// insertelement nodes, otherwise skip them.
   Optional<OrdersType> getReorderingData(const TreeEntry &TE, bool TopToBottom);
 
+  /// \Returns true if \p TE is an alt-shuffle that can be lowered to a single
+  /// instruction. An example of this is the X86 addsub instruction.
+  bool isAltShuffleThatLowersToOneInstr(const TreeEntry *TE) const;
+
   /// Reorders the current graph to the most profitable order starting from the
   /// root node to the leaf nodes. The best order is chosen only from the nodes
   /// of the same size (vectorization factor). Smaller nodes are considered
   /// parts of subgraph with smaller VF and they are reordered independently. We
   /// can make it because we still need to extend smaller nodes to the wider VF
   /// and we can merge reordering shuffles with the widening shuffles.
   void reorderTopToBottom();
 
if (Optional<OrdersType> CurrentOrder = findReusedOrderedScalars(TE))
       return CurrentOrder;
     if (TE.Scalars.size() >= 4)
       if (Optional<OrdersType> Order = findPartiallyOrderedLoads(TE))
         return Order;
   }
   return None;
 }
 
+bool BoUpSLP::isAltShuffleThatLowersToOneInstr(const TreeEntry *TE) const {
+  if (!TE->isAltShuffle())
+    return false;
+  VectorType *VecTy =
+      FixedVectorType::get(TE->Scalars[0]->getType(), TE->Scalars.size());
+  unsigned Opcode0 = TE->getOpcode();
+  unsigned Opcode1 = TE->getAltOpcode();
+  // The opcode mask selects between the two opcodes.
+  SmallBitVector OpcodeMask(TE->Scalars.size(), 0);
+  for (unsigned Lane : seq<unsigned>(0, TE->Scalars.size()))
+    if (cast<Instruction>(TE->Scalars[Lane])->getOpcode() == Opcode1)
+      OpcodeMask.set(Lane);
+  // If this pattern is supported by the target then we consider the order.
+  return TTI->isLegalAltInstr(VecTy, Opcode0, Opcode1, OpcodeMask);
+}
+
 void BoUpSLP::reorderTopToBottom() {
   // Maps VF to the graph nodes.
   DenseMap<unsigned, SetVector<TreeEntry *>> VFToOrderedEntries;
   // ExtractElement gather nodes which can be vectorized and need to handle
   // their ordering.
   DenseMap<const TreeEntry *, OrdersType> GathersToOrders;
 
   // AltShuffles can also have a preferred ordering that leads to fewer
if (!ExternalUserReorderIndices.empty()) {
       VFToOrderedEntries[TE->Scalars.size()].insert(TE.get());
       ExternalUserReorderMap.try_emplace(TE.get(),
                                          std::move(ExternalUserReorderIndices));
     }
 
     // Patterns like [fadd,fsub] can be combined into a single instruction in
     // x86. Reordering them into [fsub,fadd] blocks this pattern. So we need
     // to take into account their order when looking for the most used order.
-    if (TE->isAltShuffle()) {
-      VectorType *VecTy =
-          FixedVectorType::get(TE->Scalars[0]->getType(), TE->Scalars.size());
-      unsigned Opcode0 = TE->getOpcode();
-      unsigned Opcode1 = TE->getAltOpcode();
-      // The opcode mask selects between the two opcodes.
-      SmallBitVector OpcodeMask(TE->Scalars.size(), 0);
-      for (unsigned Lane : seq<unsigned>(0, TE->Scalars.size()))
-        if (cast<Instruction>(TE->Scalars[Lane])->getOpcode() == Opcode1)
-          OpcodeMask.set(Lane);
-      // If this pattern is supported by the target then we consider the order.
-      if (TTI->isLegalAltInstr(VecTy, Opcode0, Opcode1, OpcodeMask)) {
-        VFToOrderedEntries[TE->Scalars.size()].insert(TE.get());
-        AltShufflesToOrders.try_emplace(TE.get(), OrdersType());
-      }
+    if (isAltShuffleThatLowersToOneInstr(TE.get())) {
       // TODO: Check the reverse order too.
     }
 
     if (Optional<OrdersType> CurrentOrder =
             getReorderingData(*TE, /*TopToBottom=*/true)) {
       // Do not include ordering for nodes used in the alt opcode vectorization,
       // better to reorder them during bottom-to-top stage. If follow the order
       // here, it causes reordering of the whole graph though actually it is
case Instruction::ShuffleVector: {
         }
       }
       for (Value *V : VL) {
         Instruction *I = cast<Instruction>(V);
         assert(E->isOpcodeOrAlt(I) && "Unexpected main/alternate opcode");
         ScalarCost += TTI->getInstructionCost(I, CostKind);
       }
       // VecCost is equal to sum of the cost of creating 2 vectors
-      // and the cost of creating shuffle.
+      // and the cost of creating shuffle, except if this is an alternate
+      // sequence that can be lowered to a single instruction, like x86 addsub.
       InstructionCost VecCost = 0;
+      bool LowersToOneAltInstr = isAltShuffleThatLowersToOneInstr(E);
       // Try to find the previous shuffle node with the same operands and same
       // main/alternate ops.
       auto &&TryFindNodeWithEqualOperands = [this, E]() {
         for (const std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
           if (TE.get() == E)
             break;
           if (TE->isAltShuffle() &&
               ((TE->getOpcode() == E->getOpcode() &&
                 TE->getAltOpcode() == E->getAltOpcode()) ||
                (TE->getOpcode() == E->getAltOpcode() &&
                 TE->getAltOpcode() == E->getOpcode())) &&
               TE->hasEqualOperands(*E))
             return true;
         }
         return false;
       };
       if (TryFindNodeWithEqualOperands()) {
         LLVM_DEBUG({
           dbgs() << "SLP: diamond match for alternate node found.\n";
           E->dump();
         });
         // No need to add new vector costs here since we're going to reuse
         // same main/alternate vector ops, just do different shuffling.
       } else if (Instruction::isBinaryOp(E->getOpcode())) {
-        VecCost = TTI->getArithmeticInstrCost(E->getOpcode(), VecTy, CostKind);
-        VecCost += TTI->getArithmeticInstrCost(E->getAltOpcode(), VecTy,
-                                               CostKind);
+        if (!LowersToOneAltInstr) {
+          VecCost =
+              TTI->getArithmeticInstrCost(E->getOpcode(), VecTy, CostKind);
+          VecCost +=
+              TTI->getArithmeticInstrCost(E->getAltOpcode(), VecTy, CostKind);
+        }
       } else if (auto *CI0 = dyn_cast<CmpInst>(VL0)) {
         VecCost = TTI->getCmpSelInstrCost(E->getOpcode(), ScalarTy,
                                           Builder.getInt1Ty(),
                                           CI0->getPredicate(), CostKind, VL0);
         VecCost += TTI->getCmpSelInstrCost(
             E->getOpcode(), ScalarTy, Builder.getInt1Ty(),
             cast<CmpInst>(E->getAltOp())->getPredicate(), CostKind,
             E->getAltOp());
       } else {
         Type *Src0SclTy = E->getMainOp()->getOperand(0)->getType();
         Type *Src1SclTy = E->getAltOp()->getOperand(0)->getType();
         auto *Src0Ty = FixedVectorType::get(Src0SclTy, VL.size());
         auto *Src1Ty = FixedVectorType::get(Src1SclTy, VL.size());
         VecCost = TTI->getCastInstrCost(E->getOpcode(), VecTy, Src0Ty,
                                         TTI::CastContextHint::None, CostKind);
         VecCost += TTI->getCastInstrCost(E->getAltOpcode(), VecTy, Src1Ty,
                                          TTI::CastContextHint::None, CostKind);
       }
 
+      if (LowersToOneAltInstr) {
+        SmallVector<int> Mask;
+        buildShuffleEntryMask(
+            E->Scalars, E->ReorderIndices, E->ReuseShuffleIndices,
+            [E](Instruction *I) {
+              assert(E->isOpcodeOrAlt(I) && "Unexpected main/alternate opcode");
+              return I->getOpcode() == E->getAltOpcode();
+            },
+            Mask);
+        ArrayRef<Instruction *> Args = {E->getMainOp(), E->getAltOp()};
+        CommonCost = TTI->getAltInstrCost(FinalVecTy, Mask, Args);
+      } else {
         if (E->ReuseShuffleIndices.empty()) {
           CommonCost =
               TTI->getShuffleCost(TargetTransformInfo::SK_Select, FinalVecTy);
         } else {
           SmallVector<int> Mask;
           buildShuffleEntryMask(
               E->Scalars, E->ReorderIndices, E->ReuseShuffleIndices,
               [E](Instruction *I) {
-              assert(E->isOpcodeOrAlt(I) && "Unexpected main/alternate opcode");
+                assert(E->isOpcodeOrAlt(I) &&
+                       "Unexpected main/alternate opcode");
                 return I->getOpcode() == E->getAltOpcode();
               },
               Mask);
-        CommonCost = TTI->getShuffleCost(TargetTransformInfo::SK_PermuteTwoSrc,
-                                         FinalVecTy, Mask);
+          CommonCost = TTI->getShuffleCost(
+              TargetTransformInfo::SK_PermuteTwoSrc, FinalVecTy, Mask);
+        }
       }
       LLVM_DEBUG(dumpTreeCosts(E, CommonCost, VecCost, ScalarCost));
       return CommonCost + VecCost - ScalarCost;
     }
     default:
       llvm_unreachable("Unknown instruction");
   }
 }