X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCostModel.cpp;h=b11f64d4bf0b3f8b9fce8d19b0525488de8d2c82;hb=454a57ccb6a7b85c960074109d2e8c18b0a7f0ab;hp=8435e397077f48f2857f2b24034f66c2ba1d7cbc;hpb=fb55a8fd7c38aa09d9c243d48a8a72d890f36a3d;p=oota-llvm.git diff --git a/lib/Analysis/CostModel.cpp b/lib/Analysis/CostModel.cpp index 8435e397077..b11f64d4bf0 100644 --- a/lib/Analysis/CostModel.cpp +++ b/lib/Analysis/CostModel.cpp @@ -17,24 +17,32 @@ // //===----------------------------------------------------------------------===// -#define CM_NAME "cost-model" -#define DEBUG_TYPE CM_NAME +#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Value.h" #include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; +#define CM_NAME "cost-model" +#define DEBUG_TYPE CM_NAME + +static cl::opt EnableReduxCost("costmodel-reduxcost", cl::init(false), + cl::Hidden, + cl::desc("Recognize reduction patterns.")); + namespace { class CostModelAnalysis : public FunctionPass { public: static char ID; // Class identification, replacement for typeinfo - CostModelAnalysis() : FunctionPass(ID), F(0), TTI(0) { + CostModelAnalysis() : FunctionPass(ID), F(nullptr), TTI(nullptr) { initializeCostModelAnalysisPass( *PassRegistry::getPassRegistry()); } @@ -46,9 +54,9 @@ namespace { unsigned getInstructionCost(const Instruction *I) const; private: - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual bool runOnFunction(Function &F); - virtual void print(raw_ostream &OS, const Module*) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; + void print(raw_ostream &OS, const Module*) const override; /// The function that we analyze. Function *F; @@ -75,20 +83,305 @@ CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool CostModelAnalysis::runOnFunction(Function &F) { this->F = &F; - TTI = getAnalysisIfAvailable(); + auto *TTIWP = getAnalysisIfAvailable(); + TTI = TTIWP ? &TTIWP->getTTI(F) : nullptr; return false; } +static bool isReverseVectorMask(SmallVectorImpl &Mask) { + for (unsigned i = 0, MaskSize = Mask.size(); i < MaskSize; ++i) + if (Mask[i] > 0 && Mask[i] != (int)(MaskSize - 1 - i)) + return false; + return true; +} + +static bool isAlternateVectorMask(SmallVectorImpl &Mask) { + bool isAlternate = true; + unsigned MaskSize = Mask.size(); + + // Example: shufflevector A, B, <0,5,2,7> + for (unsigned i = 0; i < MaskSize && isAlternate; ++i) { + if (Mask[i] < 0) + continue; + isAlternate = Mask[i] == (int)((i & 1) ? MaskSize + i : i); + } + + if (isAlternate) + return true; + + isAlternate = true; + // Example: shufflevector A, B, <4,1,6,3> + for (unsigned i = 0; i < MaskSize && isAlternate; ++i) { + if (Mask[i] < 0) + continue; + isAlternate = Mask[i] == (int)((i & 1) ? i : MaskSize + i); + } + + return isAlternate; +} + +static TargetTransformInfo::OperandValueKind getOperandInfo(Value *V) { + TargetTransformInfo::OperandValueKind OpInfo = + TargetTransformInfo::OK_AnyValue; + + // Check for a splat of a constant or for a non uniform vector of constants. + if (isa(V) || isa(V)) { + OpInfo = TargetTransformInfo::OK_NonUniformConstantValue; + if (cast(V)->getSplatValue() != nullptr) + OpInfo = TargetTransformInfo::OK_UniformConstantValue; + } + + return OpInfo; +} + +static bool matchPairwiseShuffleMask(ShuffleVectorInst *SI, bool IsLeft, + unsigned Level) { + // We don't need a shuffle if we just want to have element 0 in position 0 of + // the vector. + if (!SI && Level == 0 && IsLeft) + return true; + else if (!SI) + return false; + + SmallVector Mask(SI->getType()->getVectorNumElements(), -1); + + // Build a mask of 0, 2, ... (left) or 1, 3, ... (right) depending on whether + // we look at the left or right side. + for (unsigned i = 0, e = (1 << Level), val = !IsLeft; i != e; ++i, val += 2) + Mask[i] = val; + + SmallVector ActualMask = SI->getShuffleMask(); + return Mask == ActualMask; +} + +static bool matchPairwiseReductionAtLevel(const BinaryOperator *BinOp, + unsigned Level, unsigned NumLevels) { + // Match one level of pairwise operations. + // %rdx.shuf.0.0 = shufflevector <4 x float> %rdx, <4 x float> undef, + // <4 x i32> + // %rdx.shuf.0.1 = shufflevector <4 x float> %rdx, <4 x float> undef, + // <4 x i32> + // %bin.rdx.0 = fadd <4 x float> %rdx.shuf.0.0, %rdx.shuf.0.1 + if (BinOp == nullptr) + return false; + + assert(BinOp->getType()->isVectorTy() && "Expecting a vector type"); + + unsigned Opcode = BinOp->getOpcode(); + Value *L = BinOp->getOperand(0); + Value *R = BinOp->getOperand(1); + + ShuffleVectorInst *LS = dyn_cast(L); + if (!LS && Level) + return false; + ShuffleVectorInst *RS = dyn_cast(R); + if (!RS && Level) + return false; + + // On level 0 we can omit one shufflevector instruction. + if (!Level && !RS && !LS) + return false; + + // Shuffle inputs must match. + Value *NextLevelOpL = LS ? LS->getOperand(0) : nullptr; + Value *NextLevelOpR = RS ? RS->getOperand(0) : nullptr; + Value *NextLevelOp = nullptr; + if (NextLevelOpR && NextLevelOpL) { + // If we have two shuffles their operands must match. + if (NextLevelOpL != NextLevelOpR) + return false; + + NextLevelOp = NextLevelOpL; + } else if (Level == 0 && (NextLevelOpR || NextLevelOpL)) { + // On the first level we can omit the shufflevector <0, undef,...>. So the + // input to the other shufflevector <1, undef> must match with one of the + // inputs to the current binary operation. + // Example: + // %NextLevelOpL = shufflevector %R, <1, undef ...> + // %BinOp = fadd %NextLevelOpL, %R + if (NextLevelOpL && NextLevelOpL != R) + return false; + else if (NextLevelOpR && NextLevelOpR != L) + return false; + + NextLevelOp = NextLevelOpL ? R : L; + } else + return false; + + // Check that the next levels binary operation exists and matches with the + // current one. + BinaryOperator *NextLevelBinOp = nullptr; + if (Level + 1 != NumLevels) { + if (!(NextLevelBinOp = dyn_cast(NextLevelOp))) + return false; + else if (NextLevelBinOp->getOpcode() != Opcode) + return false; + } + + // Shuffle mask for pairwise operation must match. + if (matchPairwiseShuffleMask(LS, true, Level)) { + if (!matchPairwiseShuffleMask(RS, false, Level)) + return false; + } else if (matchPairwiseShuffleMask(RS, true, Level)) { + if (!matchPairwiseShuffleMask(LS, false, Level)) + return false; + } else + return false; + + if (++Level == NumLevels) + return true; + + // Match next level. + return matchPairwiseReductionAtLevel(NextLevelBinOp, Level, NumLevels); +} + +static bool matchPairwiseReduction(const ExtractElementInst *ReduxRoot, + unsigned &Opcode, Type *&Ty) { + if (!EnableReduxCost) + return false; + + // Need to extract the first element. + ConstantInt *CI = dyn_cast(ReduxRoot->getOperand(1)); + unsigned Idx = ~0u; + if (CI) + Idx = CI->getZExtValue(); + if (Idx != 0) + return false; + + BinaryOperator *RdxStart = dyn_cast(ReduxRoot->getOperand(0)); + if (!RdxStart) + return false; + + Type *VecTy = ReduxRoot->getOperand(0)->getType(); + unsigned NumVecElems = VecTy->getVectorNumElements(); + if (!isPowerOf2_32(NumVecElems)) + return false; + + // We look for a sequence of shuffle,shuffle,add triples like the following + // that builds a pairwise reduction tree. + // + // (X0, X1, X2, X3) + // (X0 + X1, X2 + X3, undef, undef) + // ((X0 + X1) + (X2 + X3), undef, undef, undef) + // + // %rdx.shuf.0.0 = shufflevector <4 x float> %rdx, <4 x float> undef, + // <4 x i32> + // %rdx.shuf.0.1 = shufflevector <4 x float> %rdx, <4 x float> undef, + // <4 x i32> + // %bin.rdx.0 = fadd <4 x float> %rdx.shuf.0.0, %rdx.shuf.0.1 + // %rdx.shuf.1.0 = shufflevector <4 x float> %bin.rdx.0, <4 x float> undef, + // <4 x i32> + // %rdx.shuf.1.1 = shufflevector <4 x float> %bin.rdx.0, <4 x float> undef, + // <4 x i32> + // %bin.rdx8 = fadd <4 x float> %rdx.shuf.1.0, %rdx.shuf.1.1 + // %r = extractelement <4 x float> %bin.rdx8, i32 0 + if (!matchPairwiseReductionAtLevel(RdxStart, 0, Log2_32(NumVecElems))) + return false; + + Opcode = RdxStart->getOpcode(); + Ty = VecTy; + + return true; +} + +static std::pair +getShuffleAndOtherOprd(BinaryOperator *B) { + + Value *L = B->getOperand(0); + Value *R = B->getOperand(1); + ShuffleVectorInst *S = nullptr; + + if ((S = dyn_cast(L))) + return std::make_pair(R, S); + + S = dyn_cast(R); + return std::make_pair(L, S); +} + +static bool matchVectorSplittingReduction(const ExtractElementInst *ReduxRoot, + unsigned &Opcode, Type *&Ty) { + if (!EnableReduxCost) + return false; + + // Need to extract the first element. + ConstantInt *CI = dyn_cast(ReduxRoot->getOperand(1)); + unsigned Idx = ~0u; + if (CI) + Idx = CI->getZExtValue(); + if (Idx != 0) + return false; + + BinaryOperator *RdxStart = dyn_cast(ReduxRoot->getOperand(0)); + if (!RdxStart) + return false; + unsigned RdxOpcode = RdxStart->getOpcode(); + + Type *VecTy = ReduxRoot->getOperand(0)->getType(); + unsigned NumVecElems = VecTy->getVectorNumElements(); + if (!isPowerOf2_32(NumVecElems)) + return false; + + // We look for a sequence of shuffles and adds like the following matching one + // fadd, shuffle vector pair at a time. + // + // %rdx.shuf = shufflevector <4 x float> %rdx, <4 x float> undef, + // <4 x i32> + // %bin.rdx = fadd <4 x float> %rdx, %rdx.shuf + // %rdx.shuf7 = shufflevector <4 x float> %bin.rdx, <4 x float> undef, + // <4 x i32> + // %bin.rdx8 = fadd <4 x float> %bin.rdx, %rdx.shuf7 + // %r = extractelement <4 x float> %bin.rdx8, i32 0 + + unsigned MaskStart = 1; + Value *RdxOp = RdxStart; + SmallVector ShuffleMask(NumVecElems, 0); + unsigned NumVecElemsRemain = NumVecElems; + while (NumVecElemsRemain - 1) { + // Check for the right reduction operation. + BinaryOperator *BinOp; + if (!(BinOp = dyn_cast(RdxOp))) + return false; + if (BinOp->getOpcode() != RdxOpcode) + return false; + + Value *NextRdxOp; + ShuffleVectorInst *Shuffle; + std::tie(NextRdxOp, Shuffle) = getShuffleAndOtherOprd(BinOp); + + // Check the current reduction operation and the shuffle use the same value. + if (Shuffle == nullptr) + return false; + if (Shuffle->getOperand(0) != NextRdxOp) + return false; + + // Check that shuffle masks matches. + for (unsigned j = 0; j != MaskStart; ++j) + ShuffleMask[j] = MaskStart + j; + // Fill the rest of the mask with -1 for undef. + std::fill(&ShuffleMask[MaskStart], ShuffleMask.end(), -1); + + SmallVector Mask = Shuffle->getShuffleMask(); + if (ShuffleMask != Mask) + return false; + + RdxOp = NextRdxOp; + NumVecElemsRemain /= 2; + MaskStart *= 2; + } + + Opcode = RdxOpcode; + Ty = VecTy; + return true; +} + unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { if (!TTI) return -1; switch (I->getOpcode()) { - case Instruction::GetElementPtr:{ - Type *ValTy = I->getOperand(0)->getType()->getPointerElementType(); - return TTI->getAddressComputationCost(ValTy); - } + case Instruction::GetElementPtr: + return TTI->getUserCost(I); case Instruction::Ret: case Instruction::PHI: @@ -113,7 +406,12 @@ unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { case Instruction::And: case Instruction::Or: case Instruction::Xor: { - return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType()); + TargetTransformInfo::OperandValueKind Op1VK = + getOperandInfo(I->getOperand(0)); + TargetTransformInfo::OperandValueKind Op2VK = + getOperandInfo(I->getOperand(1)); + return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK, + Op2VK); } case Instruction::Select: { const SelectInst *SI = cast(I); @@ -149,7 +447,8 @@ unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { case Instruction::UIToFP: case Instruction::Trunc: case Instruction::FPTrunc: - case Instruction::BitCast: { + case Instruction::BitCast: + case Instruction::AddrSpaceCast: { Type *SrcTy = I->getOperand(0)->getType(); return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy); } @@ -159,18 +458,56 @@ unsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { unsigned Idx = -1; if (CI) Idx = CI->getZExtValue(); + + // Try to match a reduction sequence (series of shufflevector and vector + // adds followed by a extractelement). + unsigned ReduxOpCode; + Type *ReduxType; + + if (matchVectorSplittingReduction(EEI, ReduxOpCode, ReduxType)) + return TTI->getReductionCost(ReduxOpCode, ReduxType, false); + else if (matchPairwiseReduction(EEI, ReduxOpCode, ReduxType)) + return TTI->getReductionCost(ReduxOpCode, ReduxType, true); + return TTI->getVectorInstrCost(I->getOpcode(), EEI->getOperand(0)->getType(), Idx); } case Instruction::InsertElement: { - const InsertElementInst * IE = cast(I); - ConstantInt *CI = dyn_cast(IE->getOperand(2)); - unsigned Idx = -1; - if (CI) - Idx = CI->getZExtValue(); - return TTI->getVectorInstrCost(I->getOpcode(), - IE->getType(), Idx); + const InsertElementInst * IE = cast(I); + ConstantInt *CI = dyn_cast(IE->getOperand(2)); + unsigned Idx = -1; + if (CI) + Idx = CI->getZExtValue(); + return TTI->getVectorInstrCost(I->getOpcode(), + IE->getType(), Idx); + } + case Instruction::ShuffleVector: { + const ShuffleVectorInst *Shuffle = cast(I); + Type *VecTypOp0 = Shuffle->getOperand(0)->getType(); + unsigned NumVecElems = VecTypOp0->getVectorNumElements(); + SmallVector Mask = Shuffle->getShuffleMask(); + + if (NumVecElems == Mask.size()) { + if (isReverseVectorMask(Mask)) + return TTI->getShuffleCost(TargetTransformInfo::SK_Reverse, VecTypOp0, + 0, nullptr); + if (isAlternateVectorMask(Mask)) + return TTI->getShuffleCost(TargetTransformInfo::SK_Alternate, + VecTypOp0, 0, nullptr); + } + + return -1; + } + case Instruction::Call: + if (const IntrinsicInst *II = dyn_cast(I)) { + SmallVector Tys; + for (unsigned J = 0, JE = II->getNumArgOperands(); J != JE; ++J) + Tys.push_back(II->getArgOperand(J)->getType()); + + return TTI->getIntrinsicInstrCost(II->getIntrinsicID(), II->getType(), + Tys); } + return -1; default: // We don't have any information on this instruction. return -1; @@ -183,7 +520,7 @@ void CostModelAnalysis::print(raw_ostream &OS, const Module*) const { for (Function::iterator B = F->begin(), BE = F->end(); B != BE; ++B) { for (BasicBlock::iterator it = B->begin(), e = B->end(); it != e; ++it) { - Instruction *Inst = it; + Instruction *Inst = &*it; unsigned Cost = getInstructionCost(Inst); if (Cost != (unsigned)-1) OS << "Cost Model: Found an estimated cost of " << Cost;