X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FCostModel.cpp;h=1b74f8c19c51636ab651be39ecf6021a59bda80c;hb=48164ed24df7df33e416b83d40135ad97a6db489;hp=5adbf458104e1132635b9530756d18cbfb5346ee;hpb=f1495671605b50a4b0386697fee0b76ebae9d17f;p=oota-llvm.git diff --git a/lib/Analysis/CostModel.cpp b/lib/Analysis/CostModel.cpp index 5adbf458104..1b74f8c19c5 100644 --- a/lib/Analysis/CostModel.cpp +++ b/lib/Analysis/CostModel.cpp @@ -8,30 +8,41 @@ //===----------------------------------------------------------------------===// // // This file defines the cost model analysis. It provides a very basic cost -// estimation for LLVM-IR. The cost result can be thought of as cycles, but it -// is really unit-less. The estimated cost is ment to be used for comparing -// alternatives. +// estimation for LLVM-IR. This analysis uses the services of the codegen +// to approximate the cost of any IR instruction when lowered to machine +// instructions. The cost results are unit-less and the cost number represents +// the throughput of the machine assuming that all loads hit the cache, all +// branches are predicted, etc. The cost numbers can be added in order to +// compare two or more transformation alternatives. // //===----------------------------------------------------------------------===// -#define CM_NAME "cost-model" -#define DEBUG_TYPE CM_NAME +#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/Passes.h" -#include "llvm/Function.h" -#include "llvm/Instructions.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/TargetTransformInfo.h" -#include "llvm/Value.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), VTTI(0) { + CostModelAnalysis() : FunctionPass(ID), F(nullptr), TTI(nullptr) { initializeCostModelAnalysisPass( *PassRegistry::getPassRegistry()); } @@ -40,17 +51,17 @@ namespace { /// Returns -1 if the cost is unknown. /// Note, this method does not cache the cost calculation and it /// can be expensive in some cases. - unsigned getInstructionCost(Instruction *I) const; + 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; - /// Vector target information. - const VectorTargetTransformInfo *VTTI; + /// Target information. + const TargetTransformInfo *TTI; }; } // End of anonymous namespace @@ -72,25 +83,314 @@ CostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool CostModelAnalysis::runOnFunction(Function &F) { this->F = &F; - - // Target information. - TargetTransformInfo *TTI; TTI = getAnalysisIfAvailable(); - if (TTI) - VTTI = TTI->getVectorTargetTransformInfo(); return false; } -unsigned CostModelAnalysis::getInstructionCost(Instruction *I) const { - if (!VTTI) +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(); + if (Mask != ActualMask) + return false; + + return true; +} + +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::Ret: case Instruction::PHI: case Instruction::Br: { - return VTTI->getCFInstrCost(I->getOpcode()); + return TTI->getCFInstrCost(I->getOpcode()); } case Instruction::Add: case Instruction::FAdd: @@ -110,28 +410,33 @@ unsigned CostModelAnalysis::getInstructionCost(Instruction *I) const { case Instruction::And: case Instruction::Or: case Instruction::Xor: { - return VTTI->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: { - SelectInst *SI = cast(I); + const SelectInst *SI = cast(I); Type *CondTy = SI->getCondition()->getType(); - return VTTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy); + return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy); } case Instruction::ICmp: case Instruction::FCmp: { Type *ValTy = I->getOperand(0)->getType(); - return VTTI->getCmpSelInstrCost(I->getOpcode(), ValTy); + return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy); } case Instruction::Store: { - StoreInst *SI = cast(I); + const StoreInst *SI = cast(I); Type *ValTy = SI->getValueOperand()->getType(); - return VTTI->getMemoryOpCost(I->getOpcode(), ValTy, + return TTI->getMemoryOpCost(I->getOpcode(), ValTy, SI->getAlignment(), SI->getPointerAddressSpace()); } case Instruction::Load: { - LoadInst *LI = cast(I); - return VTTI->getMemoryOpCost(I->getOpcode(), I->getType(), + const LoadInst *LI = cast(I); + return TTI->getMemoryOpCost(I->getOpcode(), I->getType(), LI->getAlignment(), LI->getPointerAddressSpace()); } @@ -146,28 +451,67 @@ unsigned CostModelAnalysis::getInstructionCost(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 VTTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy); + return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy); } case Instruction::ExtractElement: { - ExtractElementInst * EEI = cast(I); + const ExtractElementInst * EEI = cast(I); ConstantInt *CI = dyn_cast(I->getOperand(1)); unsigned Idx = -1; if (CI) Idx = CI->getZExtValue(); - return VTTI->getVectorInstrCost(I->getOpcode(), - EEI->getOperand(0)->getType(), Idx); + + // 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: { - InsertElementInst * IE = cast(I); - ConstantInt *CI = dyn_cast(IE->getOperand(2)); - unsigned Idx = -1; - if (CI) - Idx = CI->getZExtValue(); - return VTTI->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;