blob: 72f65a3386be5fbebb0e3deff2e4a04dc94a7d90 [file]
//===- SLPCostAnalysis.cpp - SLP Vectorizer free cost helpers -------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "SLPCostAnalysis.h"
#include "SLPTypeUtils.h"
#include "SLPUtils.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/VectorTypeUtils.h"
#include "llvm/Support/Casting.h"
#include <cassert>
#include <utility>
using namespace llvm;
using namespace llvm::PatternMatch;
namespace llvm::slpvectorizer {
InstructionCost getShuffleCost(const TargetTransformInfo &TTI,
TTI::ShuffleKind Kind, VectorType *Tp,
const TTI::TargetCostKind CostKind,
ArrayRef<int> Mask, int Index, VectorType *SubTp,
ArrayRef<const Value *> Args) {
VectorType *DstTy = Tp;
if (!Mask.empty())
DstTy = FixedVectorType::get(Tp->getScalarType(), Mask.size());
if (Kind != TTI::SK_PermuteTwoSrc)
return TTI.getShuffleCost(Kind, DstTy, Tp, CostKind, Mask, Index, SubTp,
Args);
int NumSrcElts = Tp->getElementCount().getKnownMinValue();
int NumSubElts;
if (Mask.size() > 2 && ShuffleVectorInst::isInsertSubvectorMask(
Mask, NumSrcElts, NumSubElts, Index)) {
if (Index + NumSubElts > NumSrcElts &&
Index + NumSrcElts <= static_cast<int>(Mask.size()))
return TTI.getShuffleCost(TTI::SK_InsertSubvector, DstTy, Tp, CostKind,
Mask, Index, Tp);
}
return TTI.getShuffleCost(Kind, DstTy, Tp, CostKind, Mask, Index, SubTp,
Args);
}
std::pair<InstructionCost, InstructionCost>
getGEPCosts(const TargetTransformInfo &TTI, ArrayRef<Value *> Ptrs,
Value *BasePtr, unsigned Opcode, const TTI::TargetCostKind CostKind,
Type *ScalarTy, VectorType *VecTy) {
InstructionCost ScalarCost = 0;
InstructionCost VecCost = 0;
// Here we differentiate two cases: (1) when Ptrs represent a regular
// vectorization tree node (as they are pointer arguments of scattered
// loads) or (2) when Ptrs are the arguments of loads or stores being
// vectorized as plane wide unit-stride load/store since all the
// loads/stores are known to be from/to adjacent locations.
if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
// Case 2: estimate costs for pointer related costs when vectorizing to
// a wide load/store.
// Scalar cost is estimated as a set of pointers with known relationship
// between them.
// For vector code we will use BasePtr as argument for the wide load/store
// but we also need to account all the instructions which are going to
// stay in vectorized code due to uses outside of these scalar
// loads/stores.
ScalarCost = TTI.getPointersChainCost(
Ptrs, BasePtr, TTI::PointersChainInfo::getUnitStride(), ScalarTy,
CostKind);
SmallVector<const Value *> PtrsRetainedInVecCode;
for (Value *V : Ptrs) {
if (V == BasePtr) {
PtrsRetainedInVecCode.push_back(V);
continue;
}
auto *Ptr = dyn_cast<GetElementPtrInst>(V);
// For simplicity assume Ptr to stay in vectorized code if it's not a
// GEP instruction. We don't care since it's cost considered free.
// TODO: We should check for any uses outside of vectorizable tree
// rather than just single use.
if (!Ptr || !Ptr->hasOneUse())
PtrsRetainedInVecCode.push_back(V);
}
if (PtrsRetainedInVecCode.size() == Ptrs.size()) {
// If all pointers stay in vectorized code then we don't have
// any savings on that.
return std::make_pair(TTI::TCC_Free, TTI::TCC_Free);
}
VecCost = TTI.getPointersChainCost(PtrsRetainedInVecCode, BasePtr,
TTI::PointersChainInfo::getKnownStride(),
VecTy, CostKind);
} else {
// Case 1: Ptrs are the arguments of loads that we are going to transform
// into masked gather load intrinsic.
// All the scalar GEPs will be removed as a result of vectorization.
// For any external uses of some lanes extract element instructions will
// be generated (which cost is estimated separately).
TTI::PointersChainInfo PtrsInfo =
all_of(Ptrs,
[](const Value *V) {
auto *Ptr = dyn_cast<GetElementPtrInst>(V);
return Ptr && !Ptr->hasAllConstantIndices();
})
? TTI::PointersChainInfo::getUnknownStride()
: TTI::PointersChainInfo::getKnownStride();
ScalarCost =
TTI.getPointersChainCost(Ptrs, BasePtr, PtrsInfo, ScalarTy, CostKind);
auto *BaseGEP = dyn_cast<GEPOperator>(BasePtr);
if (!BaseGEP) {
auto *It = find_if(Ptrs, IsaPred<GEPOperator>);
if (It != Ptrs.end())
BaseGEP = cast<GEPOperator>(*It);
}
if (BaseGEP) {
SmallVector<const Value *> Indices(BaseGEP->indices());
VecCost = TTI.getGEPCost(BaseGEP->getSourceElementType(),
BaseGEP->getPointerOperand(), Indices, CostKind,
VecTy);
}
}
return std::make_pair(ScalarCost, VecCost);
}
InstructionCost getBlendedLoadCost(const TargetTransformInfo &TTI, Type *VecTy,
Align Alignment, unsigned AddressSpace,
const TTI::TargetCostKind CostKind) {
Type *CmpTy = CmpInst::makeCmpResultType(VecTy);
return 2 * TTI.getMemIntrinsicInstrCost(
MemIntrinsicCostAttributes(Intrinsic::masked_load, VecTy,
Alignment, AddressSpace),
CostKind) +
TTI.getArithmeticInstrCost(Instruction::Xor, CmpTy, CostKind) +
TTI.getCmpSelInstrCost(Instruction::Select, VecTy, CmpTy,
CmpInst::BAD_ICMP_PREDICATE, CostKind);
}
InstructionCost getMaskedDivRemCost(const TargetTransformInfo &TTI, bool ReVec,
unsigned Opcode, Type *ScalarTy,
unsigned NumElts,
const TTI::TargetCostKind CostKind,
FixedVectorType **PaddedTy) {
FixedVectorType *PaddedVecTy =
getMaskedDivRemType(TTI, Opcode, ScalarTy, NumElts, ReVec);
if (!PaddedVecTy)
return InstructionCost::getInvalid();
// One mask bit per element of the padded vector, not per padded lane.
auto *MaskTy =
FixedVectorType::get(IntegerType::getInt1Ty(ScalarTy->getContext()),
PaddedVecTy->getNumElements());
InstructionCost DirectCost = TTI.getArithmeticInstrCost(
Opcode, getWidenedType(ScalarTy, NumElts), CostKind);
IntrinsicCostAttributes ICA(getMaskedDivRemIntrinsic(Opcode), PaddedVecTy,
{PaddedVecTy, PaddedVecTy, MaskTy});
InstructionCost MaskedCost = TTI.getIntrinsicInstrCost(ICA, CostKind);
if (!MaskedCost.isValid() || MaskedCost >= DirectCost)
return InstructionCost::getInvalid();
if (PaddedTy)
*PaddedTy = PaddedVecTy;
return MaskedCost;
}
InstructionCost
getScalarizationOverhead(const TargetTransformInfo &TTI, bool ReVec,
Type *ScalarTy, VectorType *Ty,
const APInt &DemandedElts, bool Insert, bool Extract,
const TTI::TargetCostKind CostKind, bool ForPoisonSrc,
ArrayRef<Value *> VL, TTI::VectorInstrContext VIC) {
assert(!isa<ScalableVectorType>(Ty) &&
"ScalableVectorType is not supported.");
assert(getNumElements(ScalarTy) * DemandedElts.getBitWidth() ==
getNumElements(Ty) &&
"Incorrect usage.");
if (auto *VecTy = dyn_cast<FixedVectorType>(ScalarTy)) {
assert(ReVec && "Only supported by REVEC.");
// If ScalarTy is FixedVectorType, we should use CreateInsertVector instead
// of CreateInsertElement.
unsigned ScalarTyNumElements = VecTy->getNumElements();
InstructionCost Cost = 0;
for (unsigned I : seq(DemandedElts.getBitWidth())) {
if (!DemandedElts[I])
continue;
if (Insert)
Cost += getShuffleCost(TTI, TTI::SK_InsertSubvector, Ty, CostKind, {},
I * ScalarTyNumElements, VecTy);
if (Extract)
Cost += getShuffleCost(TTI, TTI::SK_ExtractSubvector, Ty, CostKind, {},
I * ScalarTyNumElements, VecTy);
}
return Cost;
}
return TTI.getScalarizationOverhead(Ty, DemandedElts, Insert, Extract,
CostKind, ForPoisonSrc, VL, VIC);
}
InstructionCost getVectorInstrCost(
const TargetTransformInfo &TTI, bool ReVec, Type *ScalarTy, unsigned Opcode,
Type *Val, const TTI::TargetCostKind CostKind, unsigned Index,
Value *Scalar,
ArrayRef<std::tuple<Value *, User *, int>> ScalarUserAndIdx) {
if (Opcode == Instruction::ExtractElement) {
if (auto *VecTy = dyn_cast<FixedVectorType>(ScalarTy)) {
assert(ReVec && "Only supported by REVEC.");
assert(isa<VectorType>(Val) && "Val must be a vector type.");
return getShuffleCost(TTI, TTI::SK_ExtractSubvector,
cast<VectorType>(Val), CostKind, {},
Index * VecTy->getNumElements(), VecTy);
}
}
return TTI.getVectorInstrCost(Opcode, Val, CostKind, Index, Scalar,
ScalarUserAndIdx);
}
InstructionCost getExtractWithExtendCost(const TargetTransformInfo &TTI,
bool ReVec, unsigned Opcode, Type *Dst,
VectorType *VecTy, unsigned Index,
const TTI::TargetCostKind CostKind) {
if (isVectorizedTy(Dst)) {
assert(ReVec && "Only supported by REVEC.");
auto *SubTp = cast<FixedVectorType>(
getWidenedType(toScalarizedTy(VecTy), getNumElements(Dst)));
return getShuffleCost(TTI, TTI::SK_ExtractSubvector, VecTy, CostKind, {},
Index * getNumElements(Dst), SubTp) +
TTI.getCastInstrCost(Opcode, Dst, SubTp, TTI::CastContextHint::None,
CostKind);
}
return TTI.getExtractWithExtendCost(Opcode, Dst, VecTy, Index, CostKind);
}
/// Returns the cast context hint for the trunc of the booleanized reduction
/// result, which inherits the uses of the reduction root \p Root.
static TTI::CastContextHint getBoolReduxResultCCH(const Value *Root) {
if (!Root->hasOneUse())
return TTI::CastContextHint::None;
const Value *U = *Root->user_begin();
if (isa<StoreInst>(U))
return TTI::CastContextHint::Normal;
if (match(U, m_Intrinsic<Intrinsic::masked_store>()))
return TTI::CastContextHint::Masked;
if (match(U, m_Intrinsic<Intrinsic::masked_scatter>()))
return TTI::CastContextHint::GatherScatter;
return TTI::CastContextHint::None;
}
InstructionCost getBoolReduxWideRdxCost(const TargetTransformInfo &TTI,
RecurKind RdxKind,
FixedVectorType *VecTy,
const Value *Root, FastMathFlags FMF,
const TTI::TargetCostKind CostKind) {
Type *I1Ty = Type::getInt1Ty(VecTy->getContext());
return TTI.getArithmeticReductionCost(
RecurrenceDescriptor::getOpcode(RdxKind), VecTy, FMF, CostKind) +
TTI.getCastInstrCost(Instruction::Trunc, I1Ty, VecTy->getScalarType(),
getBoolReduxResultCCH(Root), CostKind);
}
InstructionCost getBoolReduxBitcastCmpCost(const TargetTransformInfo &TTI,
RecurKind RdxKind,
FixedVectorType *VecTy,
const Value *Root,
ArrayRef<Instruction *> ChainInsts,
const TTI::TargetCostKind CostKind) {
// The new instructions are costed in the context of the replaced cast chain
// instructions.
auto TruncIt =
find_if(ChainInsts, [](Instruction *I) { return isa<TruncInst>(I); });
const Instruction *TruncI = TruncIt == ChainInsts.end() ? nullptr : *TruncIt;
auto CmpIt =
find_if(ChainInsts, [](Instruction *I) { return isa<ICmpInst>(I); });
const Instruction *CmpI = CmpIt == ChainInsts.end() ? nullptr : *CmpIt;
unsigned VF = VecTy->getNumElements();
auto *I1VecTy =
FixedVectorType::get(Type::getInt1Ty(VecTy->getContext()), VF);
Type *IntTy = IntegerType::get(VecTy->getContext(), VF);
Constant *CmpRHS = RdxKind == RecurKind::And
? Constant::getAllOnesValue(IntTy)
: Constant::getNullValue(IntTy);
return TTI.getCastInstrCost(Instruction::Trunc, I1VecTy, VecTy,
TTI.getCastContextHint(TruncI), CostKind,
TruncI) +
TTI.getCastInstrCost(Instruction::BitCast, IntTy, I1VecTy,
TTI.getCastContextHint(TruncI), CostKind) +
TTI.getCmpSelInstrCost(Instruction::ICmp, IntTy, /*CondTy=*/nullptr,
RdxKind == RecurKind::And ? CmpInst::ICMP_EQ
: CmpInst::ICMP_NE,
CostKind, TTI.getOperandInfo(Root),
TTI.getOperandInfo(CmpRHS), CmpI);
}
} // namespace llvm::slpvectorizer