16bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem//===- CostModel.cpp ------ Cost Model Analysis ---------------------------===// 26bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// 36bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// The LLVM Compiler Infrastructure 46bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// 56bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// This file is distributed under the University of Illinois Open Source 66bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// License. See LICENSE.TXT for details. 76bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// 86bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem//===----------------------------------------------------------------------===// 96bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// 106bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// This file defines the cost model analysis. It provides a very basic cost 1199b7a993762a926f042e7cb582e45c577ede596dNadav Rotem// estimation for LLVM-IR. This analysis uses the services of the codegen 1299b7a993762a926f042e7cb582e45c577ede596dNadav Rotem// to approximate the cost of any IR instruction when lowered to machine 1399b7a993762a926f042e7cb582e45c577ede596dNadav Rotem// instructions. The cost results are unit-less and the cost number represents 1499b7a993762a926f042e7cb582e45c577ede596dNadav Rotem// the throughput of the machine assuming that all loads hit the cache, all 1599b7a993762a926f042e7cb582e45c577ede596dNadav Rotem// branches are predicted, etc. The cost numbers can be added in order to 1699b7a993762a926f042e7cb582e45c577ede596dNadav Rotem// compare two or more transformation alternatives. 176bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// 186bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem//===----------------------------------------------------------------------===// 196bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 2065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer#include "llvm/ADT/STLExtras.h" 216bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem#include "llvm/Analysis/Passes.h" 22be04929f7fd76a921540e9901f24563e51dc1219Chandler Carruth#include "llvm/Analysis/TargetTransformInfo.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 258611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer#include "llvm/IR/IntrinsicInst.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Value.h" 276bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem#include "llvm/Pass.h" 2865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer#include "llvm/Support/CommandLine.h" 296bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem#include "llvm/Support/Debug.h" 306bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem#include "llvm/Support/raw_ostream.h" 316bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotemusing namespace llvm; 326bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define CM_NAME "cost-model" 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE CM_NAME 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighoferstatic cl::opt<bool> EnableReduxCost("costmodel-reduxcost", cl::init(false), 3765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer cl::Hidden, 3865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer cl::desc("Recognize reduction patterns.")); 3965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 406bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotemnamespace { 416bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem class CostModelAnalysis : public FunctionPass { 426bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 436bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem public: 446bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem static char ID; // Class identification, replacement for typeinfo 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CostModelAnalysis() : FunctionPass(ID), F(nullptr), TTI(nullptr) { 466bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem initializeCostModelAnalysisPass( 476bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem *PassRegistry::getPassRegistry()); 486bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 496bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 506bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem /// Returns the expected cost of the instruction. 516bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem /// Returns -1 if the cost is unknown. 526bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem /// Note, this method does not cache the cost calculation and it 536bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem /// can be expensive in some cases. 54e70b2680a89e1ffb88594f032da9fef757b487faNadav Rotem unsigned getInstructionCost(const Instruction *I) const; 556bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 566bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem private: 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void print(raw_ostream &OS, const Module*) const override; 606bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 616bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem /// The function that we analyze. 626bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem Function *F; 63194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth /// Target information. 64194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth const TargetTransformInfo *TTI; 656bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem }; 666bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem} // End of anonymous namespace 676bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 686bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem// Register this pass. 696bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotemchar CostModelAnalysis::ID = 0; 706bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotemstatic const char cm_name[] = "Cost Model Analysis"; 716bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav RotemINITIALIZE_PASS_BEGIN(CostModelAnalysis, CM_NAME, cm_name, false, true) 726bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav RotemINITIALIZE_PASS_END (CostModelAnalysis, CM_NAME, cm_name, false, true) 736bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 746bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav RotemFunctionPass *llvm::createCostModelAnalysisPass() { 756bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem return new CostModelAnalysis(); 766bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem} 776bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 786bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotemvoid 796bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav RotemCostModelAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 806bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem AU.setPreservesAll(); 816bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem} 826bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 836bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotembool 846bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav RotemCostModelAnalysis::runOnFunction(Function &F) { 856bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem this->F = &F; 86ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>(); 87ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TTI = TTIWP ? &TTIWP->getTTI(F) : nullptr; 886bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 896bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem return false; 906bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem} 916bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 929e639e8fd95488cb4c8ef2f7f3a41919acb29ac4Craig Topperstatic bool isReverseVectorMask(SmallVectorImpl<int> &Mask) { 934fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer for (unsigned i = 0, MaskSize = Mask.size(); i < MaskSize; ++i) 944fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer if (Mask[i] > 0 && Mask[i] != (int)(MaskSize - 1 - i)) 954fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer return false; 964fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer return true; 974fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer} 984fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer 99c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hinesstatic bool isAlternateVectorMask(SmallVectorImpl<int> &Mask) { 100c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines bool isAlternate = true; 101c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines unsigned MaskSize = Mask.size(); 102c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 103c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Example: shufflevector A, B, <0,5,2,7> 104c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines for (unsigned i = 0; i < MaskSize && isAlternate; ++i) { 105c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Mask[i] < 0) 106c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines continue; 107c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines isAlternate = Mask[i] == (int)((i & 1) ? MaskSize + i : i); 108c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 109c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 110c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (isAlternate) 111c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return true; 112c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 113c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines isAlternate = true; 114c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Example: shufflevector A, B, <4,1,6,3> 115c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines for (unsigned i = 0; i < MaskSize && isAlternate; ++i) { 116c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (Mask[i] < 0) 117c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines continue; 118c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines isAlternate = Mask[i] == (int)((i & 1) ? i : MaskSize + i); 119c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 120c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 121c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return isAlternate; 122c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines} 123c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 1246bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighoferstatic TargetTransformInfo::OperandValueKind getOperandInfo(Value *V) { 1256bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer TargetTransformInfo::OperandValueKind OpInfo = 1266bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer TargetTransformInfo::OK_AnyValue; 1276bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Check for a splat of a constant or for a non uniform vector of constants. 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<ConstantVector>(V) || isa<ConstantDataVector>(V)) { 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OpInfo = TargetTransformInfo::OK_NonUniformConstantValue; 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (cast<Constant>(V)->getSplatValue() != nullptr) 1326bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer OpInfo = TargetTransformInfo::OK_UniformConstantValue; 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 1346bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer 1356bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer return OpInfo; 1366bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer} 1376bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer 13865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighoferstatic bool matchPairwiseShuffleMask(ShuffleVectorInst *SI, bool IsLeft, 13965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned Level) { 14065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // We don't need a shuffle if we just want to have element 0 in position 0 of 14165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // the vector. 14265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!SI && Level == 0 && IsLeft) 14365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return true; 14465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer else if (!SI) 14565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 14665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 14765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer SmallVector<int, 32> Mask(SI->getType()->getVectorNumElements(), -1); 14865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 14965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Build a mask of 0, 2, ... (left) or 1, 3, ... (right) depending on whether 15065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // we look at the left or right side. 15165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer for (unsigned i = 0, e = (1 << Level), val = !IsLeft; i != e; ++i, val += 2) 15265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Mask[i] = val; 15365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 15465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer SmallVector<int, 16> ActualMask = SI->getShuffleMask(); 155f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Mask == ActualMask; 15665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer} 15765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 15865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighoferstatic bool matchPairwiseReductionAtLevel(const BinaryOperator *BinOp, 15965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned Level, unsigned NumLevels) { 16065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Match one level of pairwise operations. 16165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf.0.0 = shufflevector <4 x float> %rdx, <4 x float> undef, 16265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 0, i32 2 , i32 undef, i32 undef> 16365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf.0.1 = shufflevector <4 x float> %rdx, <4 x float> undef, 16465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 1, i32 3, i32 undef, i32 undef> 16565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %bin.rdx.0 = fadd <4 x float> %rdx.shuf.0.0, %rdx.shuf.0.1 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (BinOp == nullptr) 16765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 16865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 1692bc3cd83b34b3f76dfb98940201f35464150fa9fEric Christopher assert(BinOp->getType()->isVectorTy() && "Expecting a vector type"); 17065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 17165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned Opcode = BinOp->getOpcode(); 17265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Value *L = BinOp->getOperand(0); 17365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Value *R = BinOp->getOperand(1); 17465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 17565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer ShuffleVectorInst *LS = dyn_cast<ShuffleVectorInst>(L); 17665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!LS && Level) 17765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 17865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer ShuffleVectorInst *RS = dyn_cast<ShuffleVectorInst>(R); 17965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!RS && Level) 18065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 18165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 18265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // On level 0 we can omit one shufflevector instruction. 18365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!Level && !RS && !LS) 18465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 18565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 18665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Shuffle inputs must match. 187dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *NextLevelOpL = LS ? LS->getOperand(0) : nullptr; 188dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *NextLevelOpR = RS ? RS->getOperand(0) : nullptr; 189dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *NextLevelOp = nullptr; 19065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (NextLevelOpR && NextLevelOpL) { 19165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // If we have two shuffles their operands must match. 19265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (NextLevelOpL != NextLevelOpR) 19365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 19465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 19565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer NextLevelOp = NextLevelOpL; 19665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer } else if (Level == 0 && (NextLevelOpR || NextLevelOpL)) { 19765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // On the first level we can omit the shufflevector <0, undef,...>. So the 19865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // input to the other shufflevector <1, undef> must match with one of the 19965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // inputs to the current binary operation. 20065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Example: 20165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %NextLevelOpL = shufflevector %R, <1, undef ...> 20265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %BinOp = fadd %NextLevelOpL, %R 20365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (NextLevelOpL && NextLevelOpL != R) 20465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 20565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer else if (NextLevelOpR && NextLevelOpR != L) 20665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 20765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 20865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer NextLevelOp = NextLevelOpL ? R : L; 20965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer } else 21065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 21165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 21265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Check that the next levels binary operation exists and matches with the 21365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // current one. 214dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BinaryOperator *NextLevelBinOp = nullptr; 21565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (Level + 1 != NumLevels) { 21665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!(NextLevelBinOp = dyn_cast<BinaryOperator>(NextLevelOp))) 21765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 21865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer else if (NextLevelBinOp->getOpcode() != Opcode) 21965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 22065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer } 22165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 22265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Shuffle mask for pairwise operation must match. 22365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (matchPairwiseShuffleMask(LS, true, Level)) { 22465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!matchPairwiseShuffleMask(RS, false, Level)) 22565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 22665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer } else if (matchPairwiseShuffleMask(RS, true, Level)) { 22765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!matchPairwiseShuffleMask(LS, false, Level)) 22865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 22965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer } else 23065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 23165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 23265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (++Level == NumLevels) 23365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return true; 23465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 23565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Match next level. 23665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return matchPairwiseReductionAtLevel(NextLevelBinOp, Level, NumLevels); 23765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer} 23865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 23965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighoferstatic bool matchPairwiseReduction(const ExtractElementInst *ReduxRoot, 24065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned &Opcode, Type *&Ty) { 24165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!EnableReduxCost) 24265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 24365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 24465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Need to extract the first element. 24565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer ConstantInt *CI = dyn_cast<ConstantInt>(ReduxRoot->getOperand(1)); 24665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned Idx = ~0u; 24765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (CI) 24865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Idx = CI->getZExtValue(); 24965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (Idx != 0) 25065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 25165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 25265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer BinaryOperator *RdxStart = dyn_cast<BinaryOperator>(ReduxRoot->getOperand(0)); 25365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!RdxStart) 25465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 25565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 25665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Type *VecTy = ReduxRoot->getOperand(0)->getType(); 25765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned NumVecElems = VecTy->getVectorNumElements(); 25865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!isPowerOf2_32(NumVecElems)) 25965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 26065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 26165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // We look for a sequence of shuffle,shuffle,add triples like the following 26265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // that builds a pairwise reduction tree. 26365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // 26465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // (X0, X1, X2, X3) 26565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // (X0 + X1, X2 + X3, undef, undef) 26665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // ((X0 + X1) + (X2 + X3), undef, undef, undef) 26765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // 26865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf.0.0 = shufflevector <4 x float> %rdx, <4 x float> undef, 26965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 0, i32 2 , i32 undef, i32 undef> 27065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf.0.1 = shufflevector <4 x float> %rdx, <4 x float> undef, 27165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 1, i32 3, i32 undef, i32 undef> 27265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %bin.rdx.0 = fadd <4 x float> %rdx.shuf.0.0, %rdx.shuf.0.1 27365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf.1.0 = shufflevector <4 x float> %bin.rdx.0, <4 x float> undef, 27465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 0, i32 undef, i32 undef, i32 undef> 27565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf.1.1 = shufflevector <4 x float> %bin.rdx.0, <4 x float> undef, 27665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef> 27765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %bin.rdx8 = fadd <4 x float> %rdx.shuf.1.0, %rdx.shuf.1.1 27865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %r = extractelement <4 x float> %bin.rdx8, i32 0 27965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!matchPairwiseReductionAtLevel(RdxStart, 0, Log2_32(NumVecElems))) 28065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 28165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 28265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Opcode = RdxStart->getOpcode(); 28365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Ty = VecTy; 28465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 28565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return true; 28665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer} 28765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 28865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighoferstatic std::pair<Value *, ShuffleVectorInst *> 28965457b679ae240c1a37da82c5484dac478c47b6dArnold SchwaighofergetShuffleAndOtherOprd(BinaryOperator *B) { 29065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 29165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Value *L = B->getOperand(0); 29265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Value *R = B->getOperand(1); 293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ShuffleVectorInst *S = nullptr; 29465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 29565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if ((S = dyn_cast<ShuffleVectorInst>(L))) 29665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return std::make_pair(R, S); 29765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 29865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer S = dyn_cast<ShuffleVectorInst>(R); 29965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return std::make_pair(L, S); 30065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer} 30165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 30265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighoferstatic bool matchVectorSplittingReduction(const ExtractElementInst *ReduxRoot, 30365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned &Opcode, Type *&Ty) { 30465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!EnableReduxCost) 30565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 30665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 30765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Need to extract the first element. 30865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer ConstantInt *CI = dyn_cast<ConstantInt>(ReduxRoot->getOperand(1)); 30965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned Idx = ~0u; 31065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (CI) 31165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Idx = CI->getZExtValue(); 31265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (Idx != 0) 31365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 31465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 31565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer BinaryOperator *RdxStart = dyn_cast<BinaryOperator>(ReduxRoot->getOperand(0)); 31665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!RdxStart) 31765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 31865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned RdxOpcode = RdxStart->getOpcode(); 31965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 32065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Type *VecTy = ReduxRoot->getOperand(0)->getType(); 32165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned NumVecElems = VecTy->getVectorNumElements(); 32265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!isPowerOf2_32(NumVecElems)) 32365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 32465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 32565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // We look for a sequence of shuffles and adds like the following matching one 32665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // fadd, shuffle vector pair at a time. 32765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // 32865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf = shufflevector <4 x float> %rdx, <4 x float> undef, 32965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 2, i32 3, i32 undef, i32 undef> 33065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %bin.rdx = fadd <4 x float> %rdx, %rdx.shuf 33165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %rdx.shuf7 = shufflevector <4 x float> %bin.rdx, <4 x float> undef, 33265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef> 33365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %bin.rdx8 = fadd <4 x float> %bin.rdx, %rdx.shuf7 33465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // %r = extractelement <4 x float> %bin.rdx8, i32 0 33565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 33665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned MaskStart = 1; 33765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Value *RdxOp = RdxStart; 33865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer SmallVector<int, 32> ShuffleMask(NumVecElems, 0); 33965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned NumVecElemsRemain = NumVecElems; 34065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer while (NumVecElemsRemain - 1) { 34165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Check for the right reduction operation. 34265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer BinaryOperator *BinOp; 34365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (!(BinOp = dyn_cast<BinaryOperator>(RdxOp))) 34465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 34565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (BinOp->getOpcode() != RdxOpcode) 34665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 34765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 34865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Value *NextRdxOp; 34965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer ShuffleVectorInst *Shuffle; 35036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(NextRdxOp, Shuffle) = getShuffleAndOtherOprd(BinOp); 35165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 35265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Check the current reduction operation and the shuffle use the same value. 353dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Shuffle == nullptr) 35465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 35565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (Shuffle->getOperand(0) != NextRdxOp) 35665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 35765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 35865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Check that shuffle masks matches. 35965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer for (unsigned j = 0; j != MaskStart; ++j) 36065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer ShuffleMask[j] = MaskStart + j; 36165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Fill the rest of the mask with -1 for undef. 36265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer std::fill(&ShuffleMask[MaskStart], ShuffleMask.end(), -1); 36365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 36465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer SmallVector<int, 16> Mask = Shuffle->getShuffleMask(); 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (ShuffleMask != Mask) 36665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return false; 36765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 36865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer RdxOp = NextRdxOp; 36965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer NumVecElemsRemain /= 2; 37065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer MaskStart *= 2; 37165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer } 37265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 37365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Opcode = RdxOpcode; 37465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Ty = VecTy; 37565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return true; 37665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer} 37765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 378e70b2680a89e1ffb88594f032da9fef757b487faNadav Rotemunsigned CostModelAnalysis::getInstructionCost(const Instruction *I) const { 379194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth if (!TTI) 3806bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem return -1; 3816bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 3826bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem switch (I->getOpcode()) { 383f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar case Instruction::GetElementPtr: 384f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return TTI->getUserCost(I); 385fb55a8fd7c38aa09d9c243d48a8a72d890f36a3dArnold Schwaighofer 3866bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Ret: 3876bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::PHI: 3886bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Br: { 389194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getCFInstrCost(I->getOpcode()); 3906bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 3916bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Add: 3926bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FAdd: 3936bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Sub: 3946bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FSub: 3956bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Mul: 3966bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FMul: 3976bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::UDiv: 3986bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::SDiv: 3996bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FDiv: 4006bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::URem: 4016bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::SRem: 4026bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FRem: 4036bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Shl: 4046bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::LShr: 4056bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::AShr: 4066bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::And: 4076bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Or: 4086bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Xor: { 4096bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer TargetTransformInfo::OperandValueKind Op1VK = 4106bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer getOperandInfo(I->getOperand(0)); 4116bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer TargetTransformInfo::OperandValueKind Op2VK = 4126bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer getOperandInfo(I->getOperand(1)); 4136bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer return TTI->getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK, 4146bf4f676413b8f7d97aaff289997aab344180957Arnold Schwaighofer Op2VK); 4156bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 4166bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Select: { 417e70b2680a89e1ffb88594f032da9fef757b487faNadav Rotem const SelectInst *SI = cast<SelectInst>(I); 4186bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem Type *CondTy = SI->getCondition()->getType(); 419194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getCmpSelInstrCost(I->getOpcode(), I->getType(), CondTy); 4206bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 4216bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::ICmp: 4226bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FCmp: { 4236bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem Type *ValTy = I->getOperand(0)->getType(); 424194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getCmpSelInstrCost(I->getOpcode(), ValTy); 4256bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 4266bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Store: { 427e70b2680a89e1ffb88594f032da9fef757b487faNadav Rotem const StoreInst *SI = cast<StoreInst>(I); 4286bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem Type *ValTy = SI->getValueOperand()->getType(); 429194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getMemoryOpCost(I->getOpcode(), ValTy, 4306bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem SI->getAlignment(), 4316bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem SI->getPointerAddressSpace()); 4326bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 4336bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Load: { 434e70b2680a89e1ffb88594f032da9fef757b487faNadav Rotem const LoadInst *LI = cast<LoadInst>(I); 435194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getMemoryOpCost(I->getOpcode(), I->getType(), 4366bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem LI->getAlignment(), 4376bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem LI->getPointerAddressSpace()); 4386bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 4396bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::ZExt: 4406bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::SExt: 4416bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FPToUI: 4426bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FPToSI: 4436bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FPExt: 4446bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::PtrToInt: 4456bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::IntToPtr: 4466bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::SIToFP: 4476bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::UIToFP: 4486bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::Trunc: 4496bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem case Instruction::FPTrunc: 45036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case Instruction::BitCast: 45136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case Instruction::AddrSpaceCast: { 4526bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem Type *SrcTy = I->getOperand(0)->getType(); 453194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getCastInstrCost(I->getOpcode(), I->getType(), SrcTy); 4546bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 455f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem case Instruction::ExtractElement: { 456e70b2680a89e1ffb88594f032da9fef757b487faNadav Rotem const ExtractElementInst * EEI = cast<ExtractElementInst>(I); 457f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1)); 458f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem unsigned Idx = -1; 459f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem if (CI) 460f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem Idx = CI->getZExtValue(); 46165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 46265457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // Try to match a reduction sequence (series of shufflevector and vector 46365457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer // adds followed by a extractelement). 46465457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer unsigned ReduxOpCode; 46565457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer Type *ReduxType; 46665457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 46765457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer if (matchVectorSplittingReduction(EEI, ReduxOpCode, ReduxType)) 46865457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return TTI->getReductionCost(ReduxOpCode, ReduxType, false); 46965457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer else if (matchPairwiseReduction(EEI, ReduxOpCode, ReduxType)) 47065457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer return TTI->getReductionCost(ReduxOpCode, ReduxType, true); 47165457b679ae240c1a37da82c5484dac478c47b6dArnold Schwaighofer 472194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth return TTI->getVectorInstrCost(I->getOpcode(), 473194bd71b069abd7b3bd278b1df840f9cc9a4161aChandler Carruth EEI->getOperand(0)->getType(), Idx); 474f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem } 475f1495671605b50a4b0386697fee0b76ebae9d17fNadav Rotem case Instruction::InsertElement: { 4762ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper const InsertElementInst * IE = cast<InsertElementInst>(I); 4772ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2)); 4782ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper unsigned Idx = -1; 4792ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper if (CI) 4802ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper Idx = CI->getZExtValue(); 4812ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper return TTI->getVectorInstrCost(I->getOpcode(), 4822ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper IE->getType(), Idx); 4832ebba647eab05aaf71f6a309f855720ab6f90c7fCraig Topper } 4844fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer case Instruction::ShuffleVector: { 4854fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer const ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 4864fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer Type *VecTypOp0 = Shuffle->getOperand(0)->getType(); 4874fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer unsigned NumVecElems = VecTypOp0->getVectorNumElements(); 4884fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer SmallVector<int, 16> Mask = Shuffle->getShuffleMask(); 4894fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer 490c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (NumVecElems == Mask.size()) { 491c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (isReverseVectorMask(Mask)) 492c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return TTI->getShuffleCost(TargetTransformInfo::SK_Reverse, VecTypOp0, 493c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 0, nullptr); 494c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (isAlternateVectorMask(Mask)) 495c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return TTI->getShuffleCost(TargetTransformInfo::SK_Alternate, 496c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines VecTypOp0, 0, nullptr); 497c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines } 498c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 4994fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer return -1; 5004fc6484ee2439a9506d525ca757171e0ecc07744Arnold Schwaighofer } 5018611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer case Instruction::Call: 5028611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 503de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Value *, 4> Args; 5048611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer for (unsigned J = 0, JE = II->getNumArgOperands(); J != JE; ++J) 505de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Args.push_back(II->getArgOperand(J)); 506de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 507de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar FastMathFlags FMF; 508de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (auto *FPMO = dyn_cast<FPMathOperator>(II)) 509de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar FMF = FPMO->getFastMathFlags(); 5108611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer 5118611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer return TTI->getIntrinsicInstrCost(II->getIntrinsicID(), II->getType(), 512de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Args, FMF); 5138611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer } 5148611d4449a77ca05e808823bc966573a85da00cbBenjamin Kramer return -1; 5156bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem default: 5166bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem // We don't have any information on this instruction. 5176bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem return -1; 5186bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 5196bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem} 5206bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 5216bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotemvoid CostModelAnalysis::print(raw_ostream &OS, const Module*) const { 5226bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem if (!F) 5236bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem return; 5246bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 525de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (BasicBlock &B : *F) { 526de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Instruction &Inst : B) { 527de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Cost = getInstructionCost(&Inst); 5286bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem if (Cost != (unsigned)-1) 5296bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem OS << "Cost Model: Found an estimated cost of " << Cost; 5306bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem else 5316bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem OS << "Cost Model: Unknown cost"; 5326bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem 533de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << " for instruction: " << Inst << "\n"; 5346bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 5356bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem } 5366bed58ef240b1e1a1fb41fb867a8ba6e7566e0e9Nadav Rotem} 537