HELLO·Android
系统源代码
IT资讯
技术文章
我的收藏
注册
登录
-
我收藏的文章
创建代码块
我的代码块
我的账号
Lollipop MR1
|
5.1.0_r3
下载
查看原文件
收藏
根目录
external
llvm
lib
Transforms
Vectorize
BBVectorize.cpp
//===- BBVectorize.cpp - A Basic-Block Vectorizer -------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements a basic-block vectorization pass. The algorithm was // inspired by that used by the Vienna MAP Vectorizor by Franchetti and Kral, // et al. It works by looking for chains of pairable operations and then // pairing them. // //===----------------------------------------------------------------------===// #define BBV_NAME "bb-vectorize" #include "llvm/Transforms/Vectorize.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Type.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Local.h" #include
using namespace llvm; #define DEBUG_TYPE BBV_NAME static cl::opt
IgnoreTargetInfo("bb-vectorize-ignore-target-info", cl::init(false), cl::Hidden, cl::desc("Ignore target information")); static cl::opt
ReqChainDepth("bb-vectorize-req-chain-depth", cl::init(6), cl::Hidden, cl::desc("The required chain depth for vectorization")); static cl::opt
UseChainDepthWithTI("bb-vectorize-use-chain-depth", cl::init(false), cl::Hidden, cl::desc("Use the chain depth requirement with" " target information")); static cl::opt
SearchLimit("bb-vectorize-search-limit", cl::init(400), cl::Hidden, cl::desc("The maximum search distance for instruction pairs")); static cl::opt
SplatBreaksChain("bb-vectorize-splat-breaks-chain", cl::init(false), cl::Hidden, cl::desc("Replicating one element to a pair breaks the chain")); static cl::opt
VectorBits("bb-vectorize-vector-bits", cl::init(128), cl::Hidden, cl::desc("The size of the native vector registers")); static cl::opt
MaxIter("bb-vectorize-max-iter", cl::init(0), cl::Hidden, cl::desc("The maximum number of pairing iterations")); static cl::opt
Pow2LenOnly("bb-vectorize-pow2-len-only", cl::init(false), cl::Hidden, cl::desc("Don't try to form non-2^n-length vectors")); static cl::opt
MaxInsts("bb-vectorize-max-instr-per-group", cl::init(500), cl::Hidden, cl::desc("The maximum number of pairable instructions per group")); static cl::opt
MaxPairs("bb-vectorize-max-pairs-per-group", cl::init(3000), cl::Hidden, cl::desc("The maximum number of candidate instruction pairs per group")); static cl::opt
MaxCandPairsForCycleCheck("bb-vectorize-max-cycle-check-pairs", cl::init(200), cl::Hidden, cl::desc("The maximum number of candidate pairs with which to use" " a full cycle check")); static cl::opt
NoBools("bb-vectorize-no-bools", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize boolean (i1) values")); static cl::opt
NoInts("bb-vectorize-no-ints", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize integer values")); static cl::opt
NoFloats("bb-vectorize-no-floats", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize floating-point values")); // FIXME: This should default to false once pointer vector support works. static cl::opt
NoPointers("bb-vectorize-no-pointers", cl::init(/*false*/ true), cl::Hidden, cl::desc("Don't try to vectorize pointer values")); static cl::opt
NoCasts("bb-vectorize-no-casts", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize casting (conversion) operations")); static cl::opt
NoMath("bb-vectorize-no-math", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize floating-point math intrinsics")); static cl::opt
NoBitManipulation("bb-vectorize-no-bitmanip", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize BitManipulation intrinsics")); static cl::opt
NoFMA("bb-vectorize-no-fma", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize the fused-multiply-add intrinsic")); static cl::opt
NoSelect("bb-vectorize-no-select", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize select instructions")); static cl::opt
NoCmp("bb-vectorize-no-cmp", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize comparison instructions")); static cl::opt
NoGEP("bb-vectorize-no-gep", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize getelementptr instructions")); static cl::opt
NoMemOps("bb-vectorize-no-mem-ops", cl::init(false), cl::Hidden, cl::desc("Don't try to vectorize loads and stores")); static cl::opt
AlignedOnly("bb-vectorize-aligned-only", cl::init(false), cl::Hidden, cl::desc("Only generate aligned loads and stores")); static cl::opt
NoMemOpBoost("bb-vectorize-no-mem-op-boost", cl::init(false), cl::Hidden, cl::desc("Don't boost the chain-depth contribution of loads and stores")); static cl::opt
FastDep("bb-vectorize-fast-dep", cl::init(false), cl::Hidden, cl::desc("Use a fast instruction dependency analysis")); #ifndef NDEBUG static cl::opt
DebugInstructionExamination("bb-vectorize-debug-instruction-examination", cl::init(false), cl::Hidden, cl::desc("When debugging is enabled, output information on the" " instruction-examination process")); static cl::opt
DebugCandidateSelection("bb-vectorize-debug-candidate-selection", cl::init(false), cl::Hidden, cl::desc("When debugging is enabled, output information on the" " candidate-selection process")); static cl::opt
DebugPairSelection("bb-vectorize-debug-pair-selection", cl::init(false), cl::Hidden, cl::desc("When debugging is enabled, output information on the" " pair-selection process")); static cl::opt
DebugCycleCheck("bb-vectorize-debug-cycle-check", cl::init(false), cl::Hidden, cl::desc("When debugging is enabled, output information on the" " cycle-checking process")); static cl::opt
PrintAfterEveryPair("bb-vectorize-debug-print-after-every-pair", cl::init(false), cl::Hidden, cl::desc("When debugging is enabled, dump the basic block after" " every pair is fused")); #endif STATISTIC(NumFusedOps, "Number of operations fused by bb-vectorize"); namespace { struct BBVectorize : public BasicBlockPass { static char ID; // Pass identification, replacement for typeid const VectorizeConfig Config; BBVectorize(const VectorizeConfig &C = VectorizeConfig()) : BasicBlockPass(ID), Config(C) { initializeBBVectorizePass(*PassRegistry::getPassRegistry()); } BBVectorize(Pass *P, const VectorizeConfig &C) : BasicBlockPass(ID), Config(C) { AA = &P->getAnalysis
(); DT = &P->getAnalysis
().getDomTree(); SE = &P->getAnalysis
(); DataLayoutPass *DLP = P->getAnalysisIfAvailable
(); DL = DLP ? &DLP->getDataLayout() : nullptr; TTI = IgnoreTargetInfo ? nullptr : &P->getAnalysis
(); } typedef std::pair
ValuePair; typedef std::pair
ValuePairWithCost; typedef std::pair
ValuePairWithDepth; typedef std::pair
VPPair; // A ValuePair pair typedef std::pair
VPPairWithType; AliasAnalysis *AA; DominatorTree *DT; ScalarEvolution *SE; const DataLayout *DL; const TargetTransformInfo *TTI; // FIXME: const correct? bool vectorizePairs(BasicBlock &BB, bool NonPow2Len = false); bool getCandidatePairs(BasicBlock &BB, BasicBlock::iterator &Start, DenseMap
> &CandidatePairs, DenseSet
&FixedOrderPairs, DenseMap
&CandidatePairCostSavings, std::vector
&PairableInsts, bool NonPow2Len); // FIXME: The current implementation does not account for pairs that // are connected in multiple ways. For example: // C1 = A1 / A2; C2 = A2 / A1 (which may be both direct and a swap) enum PairConnectionType { PairConnectionDirect, PairConnectionSwap, PairConnectionSplat }; void computeConnectedPairs( DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, std::vector
&PairableInsts, DenseMap
> &ConnectedPairs, DenseMap
&PairConnectionTypes); void buildDepMap(BasicBlock &BB, DenseMap
> &CandidatePairs, std::vector
&PairableInsts, DenseSet
&PairableInstUsers); void choosePairs(DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, DenseMap
&CandidatePairCostSavings, std::vector
&PairableInsts, DenseSet
&FixedOrderPairs, DenseMap
&PairConnectionTypes, DenseMap
> &ConnectedPairs, DenseMap
> &ConnectedPairDeps, DenseSet
&PairableInstUsers, DenseMap
& ChosenPairs); void fuseChosenPairs(BasicBlock &BB, std::vector
&PairableInsts, DenseMap
& ChosenPairs, DenseSet
&FixedOrderPairs, DenseMap
&PairConnectionTypes, DenseMap
> &ConnectedPairs, DenseMap
> &ConnectedPairDeps); bool isInstVectorizable(Instruction *I, bool &IsSimpleLoadStore); bool areInstsCompatible(Instruction *I, Instruction *J, bool IsSimpleLoadStore, bool NonPow2Len, int &CostSavings, int &FixedOrder); bool trackUsesOfI(DenseSet
&Users, AliasSetTracker &WriteSet, Instruction *I, Instruction *J, bool UpdateUsers = true, DenseSet
*LoadMoveSetPairs = nullptr); void computePairsConnectedTo( DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, std::vector
&PairableInsts, DenseMap
> &ConnectedPairs, DenseMap
&PairConnectionTypes, ValuePair P); bool pairsConflict(ValuePair P, ValuePair Q, DenseSet
&PairableInstUsers, DenseMap
> *PairableInstUserMap = nullptr, DenseSet
*PairableInstUserPairSet = nullptr); bool pairWillFormCycle(ValuePair P, DenseMap
> &PairableInstUsers, DenseSet
&CurrentPairs); void pruneDAGFor( DenseMap
> &CandidatePairs, std::vector
&PairableInsts, DenseMap
> &ConnectedPairs, DenseSet
&PairableInstUsers, DenseMap
> &PairableInstUserMap, DenseSet
&PairableInstUserPairSet, DenseMap
&ChosenPairs, DenseMap
&DAG, DenseSet
&PrunedDAG, ValuePair J, bool UseCycleCheck); void buildInitialDAGFor( DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, std::vector
&PairableInsts, DenseMap
> &ConnectedPairs, DenseSet
&PairableInstUsers, DenseMap
&ChosenPairs, DenseMap
&DAG, ValuePair J); void findBestDAGFor( DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, DenseMap
&CandidatePairCostSavings, std::vector
&PairableInsts, DenseSet
&FixedOrderPairs, DenseMap
&PairConnectionTypes, DenseMap
> &ConnectedPairs, DenseMap
> &ConnectedPairDeps, DenseSet
&PairableInstUsers, DenseMap
> &PairableInstUserMap, DenseSet
&PairableInstUserPairSet, DenseMap
&ChosenPairs, DenseSet
&BestDAG, size_t &BestMaxDepth, int &BestEffSize, Value *II, std::vector
&JJ, bool UseCycleCheck); Value *getReplacementPointerInput(LLVMContext& Context, Instruction *I, Instruction *J, unsigned o); void fillNewShuffleMask(LLVMContext& Context, Instruction *J, unsigned MaskOffset, unsigned NumInElem, unsigned NumInElem1, unsigned IdxOffset, std::vector
&Mask); Value *getReplacementShuffleMask(LLVMContext& Context, Instruction *I, Instruction *J); bool expandIEChain(LLVMContext& Context, Instruction *I, Instruction *J, unsigned o, Value *&LOp, unsigned numElemL, Type *ArgTypeL, Type *ArgTypeR, bool IBeforeJ, unsigned IdxOff = 0); Value *getReplacementInput(LLVMContext& Context, Instruction *I, Instruction *J, unsigned o, bool IBeforeJ); void getReplacementInputsForPair(LLVMContext& Context, Instruction *I, Instruction *J, SmallVectorImpl
&ReplacedOperands, bool IBeforeJ); void replaceOutputsOfPair(LLVMContext& Context, Instruction *I, Instruction *J, Instruction *K, Instruction *&InsertionPt, Instruction *&K1, Instruction *&K2); void collectPairLoadMoveSet(BasicBlock &BB, DenseMap
&ChosenPairs, DenseMap
> &LoadMoveSet, DenseSet
&LoadMoveSetPairs, Instruction *I); void collectLoadMoveSet(BasicBlock &BB, std::vector
&PairableInsts, DenseMap
&ChosenPairs, DenseMap
> &LoadMoveSet, DenseSet
&LoadMoveSetPairs); bool canMoveUsesOfIAfterJ(BasicBlock &BB, DenseSet
&LoadMoveSetPairs, Instruction *I, Instruction *J); void moveUsesOfIAfterJ(BasicBlock &BB, DenseSet
&LoadMoveSetPairs, Instruction *&InsertionPt, Instruction *I, Instruction *J); void combineMetadata(Instruction *K, const Instruction *J); bool vectorizeBB(BasicBlock &BB) { if (skipOptnoneFunction(BB)) return false; if (!DT->isReachableFromEntry(&BB)) { DEBUG(dbgs() << "BBV: skipping unreachable " << BB.getName() << " in " << BB.getParent()->getName() << "\n"); return false; } DEBUG(if (TTI) dbgs() << "BBV: using target information\n"); bool changed = false; // Iterate a sufficient number of times to merge types of size 1 bit, // then 2 bits, then 4, etc. up to half of the target vector width of the // target vector register. unsigned n = 1; for (unsigned v = 2; (TTI || v <= Config.VectorBits) && (!Config.MaxIter || n <= Config.MaxIter); v *= 2, ++n) { DEBUG(dbgs() << "BBV: fusing loop #" << n << " for " << BB.getName() << " in " << BB.getParent()->getName() << "...\n"); if (vectorizePairs(BB)) changed = true; else break; } if (changed && !Pow2LenOnly) { ++n; for (; !Config.MaxIter || n <= Config.MaxIter; ++n) { DEBUG(dbgs() << "BBV: fusing for non-2^n-length vectors loop #: " << n << " for " << BB.getName() << " in " << BB.getParent()->getName() << "...\n"); if (!vectorizePairs(BB, true)) break; } } DEBUG(dbgs() << "BBV: done!\n"); return changed; } bool runOnBasicBlock(BasicBlock &BB) override { // OptimizeNone check deferred to vectorizeBB(). AA = &getAnalysis
(); DT = &getAnalysis
().getDomTree(); SE = &getAnalysis
(); DataLayoutPass *DLP = getAnalysisIfAvailable
(); DL = DLP ? &DLP->getDataLayout() : nullptr; TTI = IgnoreTargetInfo ? nullptr : &getAnalysis
(); return vectorizeBB(BB); } void getAnalysisUsage(AnalysisUsage &AU) const override { BasicBlockPass::getAnalysisUsage(AU); AU.addRequired
(); AU.addRequired
(); AU.addRequired
(); AU.addRequired
(); AU.addPreserved
(); AU.addPreserved
(); AU.addPreserved
(); AU.setPreservesCFG(); } static inline VectorType *getVecTypeForPair(Type *ElemTy, Type *Elem2Ty) { assert(ElemTy->getScalarType() == Elem2Ty->getScalarType() && "Cannot form vector from incompatible scalar types"); Type *STy = ElemTy->getScalarType(); unsigned numElem; if (VectorType *VTy = dyn_cast
(ElemTy)) { numElem = VTy->getNumElements(); } else { numElem = 1; } if (VectorType *VTy = dyn_cast
(Elem2Ty)) { numElem += VTy->getNumElements(); } else { numElem += 1; } return VectorType::get(STy, numElem); } static inline void getInstructionTypes(Instruction *I, Type *&T1, Type *&T2) { if (StoreInst *SI = dyn_cast
(I)) { // For stores, it is the value type, not the pointer type that matters // because the value is what will come from a vector register. Value *IVal = SI->getValueOperand(); T1 = IVal->getType(); } else { T1 = I->getType(); } if (CastInst *CI = dyn_cast
(I)) T2 = CI->getSrcTy(); else T2 = T1; if (SelectInst *SI = dyn_cast
(I)) { T2 = SI->getCondition()->getType(); } else if (ShuffleVectorInst *SI = dyn_cast
(I)) { T2 = SI->getOperand(0)->getType(); } else if (CmpInst *CI = dyn_cast
(I)) { T2 = CI->getOperand(0)->getType(); } } // Returns the weight associated with the provided value. A chain of // candidate pairs has a length given by the sum of the weights of its // members (one weight per pair; the weight of each member of the pair // is assumed to be the same). This length is then compared to the // chain-length threshold to determine if a given chain is significant // enough to be vectorized. The length is also used in comparing // candidate chains where longer chains are considered to be better. // Note: when this function returns 0, the resulting instructions are // not actually fused. inline size_t getDepthFactor(Value *V) { // InsertElement and ExtractElement have a depth factor of zero. This is // for two reasons: First, they cannot be usefully fused. Second, because // the pass generates a lot of these, they can confuse the simple metric // used to compare the dags in the next iteration. Thus, giving them a // weight of zero allows the pass to essentially ignore them in // subsequent iterations when looking for vectorization opportunities // while still tracking dependency chains that flow through those // instructions. if (isa
(V) || isa
(V)) return 0; // Give a load or store half of the required depth so that load/store // pairs will vectorize. if (!Config.NoMemOpBoost && (isa
(V) || isa
(V))) return Config.ReqChainDepth/2; return 1; } // Returns the cost of the provided instruction using TTI. // This does not handle loads and stores. unsigned getInstrCost(unsigned Opcode, Type *T1, Type *T2, TargetTransformInfo::OperandValueKind Op1VK = TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OperandValueKind Op2VK = TargetTransformInfo::OK_AnyValue) { switch (Opcode) { default: break; case Instruction::GetElementPtr: // We mark this instruction as zero-cost because scalar GEPs are usually // lowered to the instruction addressing mode. At the moment we don't // generate vector GEPs. return 0; case Instruction::Br: return TTI->getCFInstrCost(Opcode); case Instruction::PHI: return 0; case Instruction::Add: case Instruction::FAdd: case Instruction::Sub: case Instruction::FSub: case Instruction::Mul: case Instruction::FMul: case Instruction::UDiv: case Instruction::SDiv: case Instruction::FDiv: case Instruction::URem: case Instruction::SRem: case Instruction::FRem: case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: case Instruction::And: case Instruction::Or: case Instruction::Xor: return TTI->getArithmeticInstrCost(Opcode, T1, Op1VK, Op2VK); case Instruction::Select: case Instruction::ICmp: case Instruction::FCmp: return TTI->getCmpSelInstrCost(Opcode, T1, T2); case Instruction::ZExt: case Instruction::SExt: case Instruction::FPToUI: case Instruction::FPToSI: case Instruction::FPExt: case Instruction::PtrToInt: case Instruction::IntToPtr: case Instruction::SIToFP: case Instruction::UIToFP: case Instruction::Trunc: case Instruction::FPTrunc: case Instruction::BitCast: case Instruction::ShuffleVector: return TTI->getCastInstrCost(Opcode, T1, T2); } return 1; } // This determines the relative offset of two loads or stores, returning // true if the offset could be determined to be some constant value. // For example, if OffsetInElmts == 1, then J accesses the memory directly // after I; if OffsetInElmts == -1 then I accesses the memory // directly after J. bool getPairPtrInfo(Instruction *I, Instruction *J, Value *&IPtr, Value *&JPtr, unsigned &IAlignment, unsigned &JAlignment, unsigned &IAddressSpace, unsigned &JAddressSpace, int64_t &OffsetInElmts, bool ComputeOffset = true) { OffsetInElmts = 0; if (LoadInst *LI = dyn_cast
(I)) { LoadInst *LJ = cast
(J); IPtr = LI->getPointerOperand(); JPtr = LJ->getPointerOperand(); IAlignment = LI->getAlignment(); JAlignment = LJ->getAlignment(); IAddressSpace = LI->getPointerAddressSpace(); JAddressSpace = LJ->getPointerAddressSpace(); } else { StoreInst *SI = cast
(I), *SJ = cast
(J); IPtr = SI->getPointerOperand(); JPtr = SJ->getPointerOperand(); IAlignment = SI->getAlignment(); JAlignment = SJ->getAlignment(); IAddressSpace = SI->getPointerAddressSpace(); JAddressSpace = SJ->getPointerAddressSpace(); } if (!ComputeOffset) return true; const SCEV *IPtrSCEV = SE->getSCEV(IPtr); const SCEV *JPtrSCEV = SE->getSCEV(JPtr); // If this is a trivial offset, then we'll get something like // 1*sizeof(type). With target data, which we need anyway, this will get // constant folded into a number. const SCEV *OffsetSCEV = SE->getMinusSCEV(JPtrSCEV, IPtrSCEV); if (const SCEVConstant *ConstOffSCEV = dyn_cast
(OffsetSCEV)) { ConstantInt *IntOff = ConstOffSCEV->getValue(); int64_t Offset = IntOff->getSExtValue(); Type *VTy = IPtr->getType()->getPointerElementType(); int64_t VTyTSS = (int64_t) DL->getTypeStoreSize(VTy); Type *VTy2 = JPtr->getType()->getPointerElementType(); if (VTy != VTy2 && Offset < 0) { int64_t VTy2TSS = (int64_t) DL->getTypeStoreSize(VTy2); OffsetInElmts = Offset/VTy2TSS; return (abs64(Offset) % VTy2TSS) == 0; } OffsetInElmts = Offset/VTyTSS; return (abs64(Offset) % VTyTSS) == 0; } return false; } // Returns true if the provided CallInst represents an intrinsic that can // be vectorized. bool isVectorizableIntrinsic(CallInst* I) { Function *F = I->getCalledFunction(); if (!F) return false; Intrinsic::ID IID = (Intrinsic::ID) F->getIntrinsicID(); if (!IID) return false; switch(IID) { default: return false; case Intrinsic::sqrt: case Intrinsic::powi: case Intrinsic::sin: case Intrinsic::cos: case Intrinsic::log: case Intrinsic::log2: case Intrinsic::log10: case Intrinsic::exp: case Intrinsic::exp2: case Intrinsic::pow: case Intrinsic::round: case Intrinsic::copysign: case Intrinsic::ceil: case Intrinsic::nearbyint: case Intrinsic::rint: case Intrinsic::trunc: case Intrinsic::floor: case Intrinsic::fabs: return Config.VectorizeMath; case Intrinsic::bswap: case Intrinsic::ctpop: case Intrinsic::ctlz: case Intrinsic::cttz: return Config.VectorizeBitManipulations; case Intrinsic::fma: case Intrinsic::fmuladd: return Config.VectorizeFMA; } } bool isPureIEChain(InsertElementInst *IE) { InsertElementInst *IENext = IE; do { if (!isa
(IENext->getOperand(0)) && !isa
(IENext->getOperand(0))) { return false; } } while ((IENext = dyn_cast
(IENext->getOperand(0)))); return true; } }; // This function implements one vectorization iteration on the provided // basic block. It returns true if the block is changed. bool BBVectorize::vectorizePairs(BasicBlock &BB, bool NonPow2Len) { bool ShouldContinue; BasicBlock::iterator Start = BB.getFirstInsertionPt(); std::vector
AllPairableInsts; DenseMap
AllChosenPairs; DenseSet
AllFixedOrderPairs; DenseMap
AllPairConnectionTypes; DenseMap
> AllConnectedPairs, AllConnectedPairDeps; do { std::vector
PairableInsts; DenseMap
> CandidatePairs; DenseSet
FixedOrderPairs; DenseMap
CandidatePairCostSavings; ShouldContinue = getCandidatePairs(BB, Start, CandidatePairs, FixedOrderPairs, CandidatePairCostSavings, PairableInsts, NonPow2Len); if (PairableInsts.empty()) continue; // Build the candidate pair set for faster lookups. DenseSet
CandidatePairsSet; for (DenseMap
>::iterator I = CandidatePairs.begin(), E = CandidatePairs.end(); I != E; ++I) for (std::vector
::iterator J = I->second.begin(), JE = I->second.end(); J != JE; ++J) CandidatePairsSet.insert(ValuePair(I->first, *J)); // Now we have a map of all of the pairable instructions and we need to // select the best possible pairing. A good pairing is one such that the // users of the pair are also paired. This defines a (directed) forest // over the pairs such that two pairs are connected iff the second pair // uses the first. // Note that it only matters that both members of the second pair use some // element of the first pair (to allow for splatting). DenseMap
> ConnectedPairs, ConnectedPairDeps; DenseMap
PairConnectionTypes; computeConnectedPairs(CandidatePairs, CandidatePairsSet, PairableInsts, ConnectedPairs, PairConnectionTypes); if (ConnectedPairs.empty()) continue; for (DenseMap
>::iterator I = ConnectedPairs.begin(), IE = ConnectedPairs.end(); I != IE; ++I) for (std::vector
::iterator J = I->second.begin(), JE = I->second.end(); J != JE; ++J) ConnectedPairDeps[*J].push_back(I->first); // Build the pairable-instruction dependency map DenseSet
PairableInstUsers; buildDepMap(BB, CandidatePairs, PairableInsts, PairableInstUsers); // There is now a graph of the connected pairs. For each variable, pick // the pairing with the largest dag meeting the depth requirement on at // least one branch. Then select all pairings that are part of that dag // and remove them from the list of available pairings and pairable // variables. DenseMap
ChosenPairs; choosePairs(CandidatePairs, CandidatePairsSet, CandidatePairCostSavings, PairableInsts, FixedOrderPairs, PairConnectionTypes, ConnectedPairs, ConnectedPairDeps, PairableInstUsers, ChosenPairs); if (ChosenPairs.empty()) continue; AllPairableInsts.insert(AllPairableInsts.end(), PairableInsts.begin(), PairableInsts.end()); AllChosenPairs.insert(ChosenPairs.begin(), ChosenPairs.end()); // Only for the chosen pairs, propagate information on fixed-order pairs, // pair connections, and their types to the data structures used by the // pair fusion procedures. for (DenseMap
::iterator I = ChosenPairs.begin(), IE = ChosenPairs.end(); I != IE; ++I) { if (FixedOrderPairs.count(*I)) AllFixedOrderPairs.insert(*I); else if (FixedOrderPairs.count(ValuePair(I->second, I->first))) AllFixedOrderPairs.insert(ValuePair(I->second, I->first)); for (DenseMap
::iterator J = ChosenPairs.begin(); J != IE; ++J) { DenseMap
::iterator K = PairConnectionTypes.find(VPPair(*I, *J)); if (K != PairConnectionTypes.end()) { AllPairConnectionTypes.insert(*K); } else { K = PairConnectionTypes.find(VPPair(*J, *I)); if (K != PairConnectionTypes.end()) AllPairConnectionTypes.insert(*K); } } } for (DenseMap
>::iterator I = ConnectedPairs.begin(), IE = ConnectedPairs.end(); I != IE; ++I) for (std::vector
::iterator J = I->second.begin(), JE = I->second.end(); J != JE; ++J) if (AllPairConnectionTypes.count(VPPair(I->first, *J))) { AllConnectedPairs[I->first].push_back(*J); AllConnectedPairDeps[*J].push_back(I->first); } } while (ShouldContinue); if (AllChosenPairs.empty()) return false; NumFusedOps += AllChosenPairs.size(); // A set of pairs has now been selected. It is now necessary to replace the // paired instructions with vector instructions. For this procedure each // operand must be replaced with a vector operand. This vector is formed // by using build_vector on the old operands. The replaced values are then // replaced with a vector_extract on the result. Subsequent optimization // passes should coalesce the build/extract combinations. fuseChosenPairs(BB, AllPairableInsts, AllChosenPairs, AllFixedOrderPairs, AllPairConnectionTypes, AllConnectedPairs, AllConnectedPairDeps); // It is important to cleanup here so that future iterations of this // function have less work to do. (void) SimplifyInstructionsInBlock(&BB, DL, AA->getTargetLibraryInfo()); return true; } // This function returns true if the provided instruction is capable of being // fused into a vector instruction. This determination is based only on the // type and other attributes of the instruction. bool BBVectorize::isInstVectorizable(Instruction *I, bool &IsSimpleLoadStore) { IsSimpleLoadStore = false; if (CallInst *C = dyn_cast
(I)) { if (!isVectorizableIntrinsic(C)) return false; } else if (LoadInst *L = dyn_cast
(I)) { // Vectorize simple loads if possbile: IsSimpleLoadStore = L->isSimple(); if (!IsSimpleLoadStore || !Config.VectorizeMemOps) return false; } else if (StoreInst *S = dyn_cast
(I)) { // Vectorize simple stores if possbile: IsSimpleLoadStore = S->isSimple(); if (!IsSimpleLoadStore || !Config.VectorizeMemOps) return false; } else if (CastInst *C = dyn_cast
(I)) { // We can vectorize casts, but not casts of pointer types, etc. if (!Config.VectorizeCasts) return false; Type *SrcTy = C->getSrcTy(); if (!SrcTy->isSingleValueType()) return false; Type *DestTy = C->getDestTy(); if (!DestTy->isSingleValueType()) return false; } else if (isa
(I)) { if (!Config.VectorizeSelect) return false; } else if (isa
(I)) { if (!Config.VectorizeCmp) return false; } else if (GetElementPtrInst *G = dyn_cast
(I)) { if (!Config.VectorizeGEP) return false; // Currently, vector GEPs exist only with one index. if (G->getNumIndices() != 1) return false; } else if (!(I->isBinaryOp() || isa
(I) || isa
(I) || isa
(I))) { return false; } // We can't vectorize memory operations without target data if (!DL && IsSimpleLoadStore) return false; Type *T1, *T2; getInstructionTypes(I, T1, T2); // Not every type can be vectorized... if (!(VectorType::isValidElementType(T1) || T1->isVectorTy()) || !(VectorType::isValidElementType(T2) || T2->isVectorTy())) return false; if (T1->getScalarSizeInBits() == 1) { if (!Config.VectorizeBools) return false; } else { if (!Config.VectorizeInts && T1->isIntOrIntVectorTy()) return false; } if (T2->getScalarSizeInBits() == 1) { if (!Config.VectorizeBools) return false; } else { if (!Config.VectorizeInts && T2->isIntOrIntVectorTy()) return false; } if (!Config.VectorizeFloats && (T1->isFPOrFPVectorTy() || T2->isFPOrFPVectorTy())) return false; // Don't vectorize target-specific types. if (T1->isX86_FP80Ty() || T1->isPPC_FP128Ty() || T1->isX86_MMXTy()) return false; if (T2->isX86_FP80Ty() || T2->isPPC_FP128Ty() || T2->isX86_MMXTy()) return false; if ((!Config.VectorizePointers || !DL) && (T1->getScalarType()->isPointerTy() || T2->getScalarType()->isPointerTy())) return false; if (!TTI && (T1->getPrimitiveSizeInBits() >= Config.VectorBits || T2->getPrimitiveSizeInBits() >= Config.VectorBits)) return false; return true; } // This function returns true if the two provided instructions are compatible // (meaning that they can be fused into a vector instruction). This assumes // that I has already been determined to be vectorizable and that J is not // in the use dag of I. bool BBVectorize::areInstsCompatible(Instruction *I, Instruction *J, bool IsSimpleLoadStore, bool NonPow2Len, int &CostSavings, int &FixedOrder) { DEBUG(if (DebugInstructionExamination) dbgs() << "BBV: looking at " << *I << " <-> " << *J << "\n"); CostSavings = 0; FixedOrder = 0; // Loads and stores can be merged if they have different alignments, // but are otherwise the same. if (!J->isSameOperationAs(I, Instruction::CompareIgnoringAlignment | (NonPow2Len ? Instruction::CompareUsingScalarTypes : 0))) return false; Type *IT1, *IT2, *JT1, *JT2; getInstructionTypes(I, IT1, IT2); getInstructionTypes(J, JT1, JT2); unsigned MaxTypeBits = std::max( IT1->getPrimitiveSizeInBits() + JT1->getPrimitiveSizeInBits(), IT2->getPrimitiveSizeInBits() + JT2->getPrimitiveSizeInBits()); if (!TTI && MaxTypeBits > Config.VectorBits) return false; // FIXME: handle addsub-type operations! if (IsSimpleLoadStore) { Value *IPtr, *JPtr; unsigned IAlignment, JAlignment, IAddressSpace, JAddressSpace; int64_t OffsetInElmts = 0; if (getPairPtrInfo(I, J, IPtr, JPtr, IAlignment, JAlignment, IAddressSpace, JAddressSpace, OffsetInElmts) && abs64(OffsetInElmts) == 1) { FixedOrder = (int) OffsetInElmts; unsigned BottomAlignment = IAlignment; if (OffsetInElmts < 0) BottomAlignment = JAlignment; Type *aTypeI = isa
(I) ? cast
(I)->getValueOperand()->getType() : I->getType(); Type *aTypeJ = isa
(J) ? cast
(J)->getValueOperand()->getType() : J->getType(); Type *VType = getVecTypeForPair(aTypeI, aTypeJ); if (Config.AlignedOnly) { // An aligned load or store is possible only if the instruction // with the lower offset has an alignment suitable for the // vector type. unsigned VecAlignment = DL->getPrefTypeAlignment(VType); if (BottomAlignment < VecAlignment) return false; } if (TTI) { unsigned ICost = TTI->getMemoryOpCost(I->getOpcode(), aTypeI, IAlignment, IAddressSpace); unsigned JCost = TTI->getMemoryOpCost(J->getOpcode(), aTypeJ, JAlignment, JAddressSpace); unsigned VCost = TTI->getMemoryOpCost(I->getOpcode(), VType, BottomAlignment, IAddressSpace); ICost += TTI->getAddressComputationCost(aTypeI); JCost += TTI->getAddressComputationCost(aTypeJ); VCost += TTI->getAddressComputationCost(VType); if (VCost > ICost + JCost) return false; // We don't want to fuse to a type that will be split, even // if the two input types will also be split and there is no other // associated cost. unsigned VParts = TTI->getNumberOfParts(VType); if (VParts > 1) return false; else if (!VParts && VCost == ICost + JCost) return false; CostSavings = ICost + JCost - VCost; } } else { return false; } } else if (TTI) { unsigned ICost = getInstrCost(I->getOpcode(), IT1, IT2); unsigned JCost = getInstrCost(J->getOpcode(), JT1, JT2); Type *VT1 = getVecTypeForPair(IT1, JT1), *VT2 = getVecTypeForPair(IT2, JT2); TargetTransformInfo::OperandValueKind Op1VK = TargetTransformInfo::OK_AnyValue; TargetTransformInfo::OperandValueKind Op2VK = TargetTransformInfo::OK_AnyValue; // On some targets (example X86) the cost of a vector shift may vary // depending on whether the second operand is a Uniform or // NonUniform Constant. switch (I->getOpcode()) { default : break; case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: // If both I and J are scalar shifts by constant, then the // merged vector shift count would be either a constant splat value // or a non-uniform vector of constants. if (ConstantInt *CII = dyn_cast
(I->getOperand(1))) { if (ConstantInt *CIJ = dyn_cast
(J->getOperand(1))) Op2VK = CII == CIJ ? TargetTransformInfo::OK_UniformConstantValue : TargetTransformInfo::OK_NonUniformConstantValue; } else { // Check for a splat of a constant or for a non uniform vector // of constants. Value *IOp = I->getOperand(1); Value *JOp = J->getOperand(1); if ((isa
(IOp) || isa
(IOp)) && (isa
(JOp) || isa
(JOp))) { Op2VK = TargetTransformInfo::OK_NonUniformConstantValue; Constant *SplatValue = cast
(IOp)->getSplatValue(); if (SplatValue != nullptr && SplatValue == cast
(JOp)->getSplatValue()) Op2VK = TargetTransformInfo::OK_UniformConstantValue; } } } // Note that this procedure is incorrect for insert and extract element // instructions (because combining these often results in a shuffle), // but this cost is ignored (because insert and extract element // instructions are assigned a zero depth factor and are not really // fused in general). unsigned VCost = getInstrCost(I->getOpcode(), VT1, VT2, Op1VK, Op2VK); if (VCost > ICost + JCost) return false; // We don't want to fuse to a type that will be split, even // if the two input types will also be split and there is no other // associated cost. unsigned VParts1 = TTI->getNumberOfParts(VT1), VParts2 = TTI->getNumberOfParts(VT2); if (VParts1 > 1 || VParts2 > 1) return false; else if ((!VParts1 || !VParts2) && VCost == ICost + JCost) return false; CostSavings = ICost + JCost - VCost; } // The powi,ctlz,cttz intrinsics are special because only the first // argument is vectorized, the second arguments must be equal. CallInst *CI = dyn_cast
(I); Function *FI; if (CI && (FI = CI->getCalledFunction())) { Intrinsic::ID IID = (Intrinsic::ID) FI->getIntrinsicID(); if (IID == Intrinsic::powi || IID == Intrinsic::ctlz || IID == Intrinsic::cttz) { Value *A1I = CI->getArgOperand(1), *A1J = cast
(J)->getArgOperand(1); const SCEV *A1ISCEV = SE->getSCEV(A1I), *A1JSCEV = SE->getSCEV(A1J); return (A1ISCEV == A1JSCEV); } if (IID && TTI) { SmallVector
Tys; for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) Tys.push_back(CI->getArgOperand(i)->getType()); unsigned ICost = TTI->getIntrinsicInstrCost(IID, IT1, Tys); Tys.clear(); CallInst *CJ = cast
(J); for (unsigned i = 0, ie = CJ->getNumArgOperands(); i != ie; ++i) Tys.push_back(CJ->getArgOperand(i)->getType()); unsigned JCost = TTI->getIntrinsicInstrCost(IID, JT1, Tys); Tys.clear(); assert(CI->getNumArgOperands() == CJ->getNumArgOperands() && "Intrinsic argument counts differ"); for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) { if ((IID == Intrinsic::powi || IID == Intrinsic::ctlz || IID == Intrinsic::cttz) && i == 1) Tys.push_back(CI->getArgOperand(i)->getType()); else Tys.push_back(getVecTypeForPair(CI->getArgOperand(i)->getType(), CJ->getArgOperand(i)->getType())); } Type *RetTy = getVecTypeForPair(IT1, JT1); unsigned VCost = TTI->getIntrinsicInstrCost(IID, RetTy, Tys); if (VCost > ICost + JCost) return false; // We don't want to fuse to a type that will be split, even // if the two input types will also be split and there is no other // associated cost. unsigned RetParts = TTI->getNumberOfParts(RetTy); if (RetParts > 1) return false; else if (!RetParts && VCost == ICost + JCost) return false; for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) { if (!Tys[i]->isVectorTy()) continue; unsigned NumParts = TTI->getNumberOfParts(Tys[i]); if (NumParts > 1) return false; else if (!NumParts && VCost == ICost + JCost) return false; } CostSavings = ICost + JCost - VCost; } } return true; } // Figure out whether or not J uses I and update the users and write-set // structures associated with I. Specifically, Users represents the set of // instructions that depend on I. WriteSet represents the set // of memory locations that are dependent on I. If UpdateUsers is true, // and J uses I, then Users is updated to contain J and WriteSet is updated // to contain any memory locations to which J writes. The function returns // true if J uses I. By default, alias analysis is used to determine // whether J reads from memory that overlaps with a location in WriteSet. // If LoadMoveSet is not null, then it is a previously-computed map // where the key is the memory-based user instruction and the value is // the instruction to be compared with I. So, if LoadMoveSet is provided, // then the alias analysis is not used. This is necessary because this // function is called during the process of moving instructions during // vectorization and the results of the alias analysis are not stable during // that process. bool BBVectorize::trackUsesOfI(DenseSet
&Users, AliasSetTracker &WriteSet, Instruction *I, Instruction *J, bool UpdateUsers, DenseSet
*LoadMoveSetPairs) { bool UsesI = false; // This instruction may already be marked as a user due, for example, to // being a member of a selected pair. if (Users.count(J)) UsesI = true; if (!UsesI) for (User::op_iterator JU = J->op_begin(), JE = J->op_end(); JU != JE; ++JU) { Value *V = *JU; if (I == V || Users.count(V)) { UsesI = true; break; } } if (!UsesI && J->mayReadFromMemory()) { if (LoadMoveSetPairs) { UsesI = LoadMoveSetPairs->count(ValuePair(J, I)); } else { for (AliasSetTracker::iterator W = WriteSet.begin(), WE = WriteSet.end(); W != WE; ++W) { if (W->aliasesUnknownInst(J, *AA)) { UsesI = true; break; } } } } if (UsesI && UpdateUsers) { if (J->mayWriteToMemory()) WriteSet.add(J); Users.insert(J); } return UsesI; } // This function iterates over all instruction pairs in the provided // basic block and collects all candidate pairs for vectorization. bool BBVectorize::getCandidatePairs(BasicBlock &BB, BasicBlock::iterator &Start, DenseMap
> &CandidatePairs, DenseSet
&FixedOrderPairs, DenseMap
&CandidatePairCostSavings, std::vector
&PairableInsts, bool NonPow2Len) { size_t TotalPairs = 0; BasicBlock::iterator E = BB.end(); if (Start == E) return false; bool ShouldContinue = false, IAfterStart = false; for (BasicBlock::iterator I = Start++; I != E; ++I) { if (I == Start) IAfterStart = true; bool IsSimpleLoadStore; if (!isInstVectorizable(I, IsSimpleLoadStore)) continue; // Look for an instruction with which to pair instruction *I... DenseSet
Users; AliasSetTracker WriteSet(*AA); if (I->mayWriteToMemory()) WriteSet.add(I); bool JAfterStart = IAfterStart; BasicBlock::iterator J = std::next(I); for (unsigned ss = 0; J != E && ss <= Config.SearchLimit; ++J, ++ss) { if (J == Start) JAfterStart = true; // Determine if J uses I, if so, exit the loop. bool UsesI = trackUsesOfI(Users, WriteSet, I, J, !Config.FastDep); if (Config.FastDep) { // Note: For this heuristic to be effective, independent operations // must tend to be intermixed. This is likely to be true from some // kinds of grouped loop unrolling (but not the generic LLVM pass), // but otherwise may require some kind of reordering pass. // When using fast dependency analysis, // stop searching after first use: if (UsesI) break; } else { if (UsesI) continue; } // J does not use I, and comes before the first use of I, so it can be // merged with I if the instructions are compatible. int CostSavings, FixedOrder; if (!areInstsCompatible(I, J, IsSimpleLoadStore, NonPow2Len, CostSavings, FixedOrder)) continue; // J is a candidate for merging with I. if (!PairableInsts.size() || PairableInsts[PairableInsts.size()-1] != I) { PairableInsts.push_back(I); } CandidatePairs[I].push_back(J); ++TotalPairs; if (TTI) CandidatePairCostSavings.insert(ValuePairWithCost(ValuePair(I, J), CostSavings)); if (FixedOrder == 1) FixedOrderPairs.insert(ValuePair(I, J)); else if (FixedOrder == -1) FixedOrderPairs.insert(ValuePair(J, I)); // The next call to this function must start after the last instruction // selected during this invocation. if (JAfterStart) { Start = std::next(J); IAfterStart = JAfterStart = false; } DEBUG(if (DebugCandidateSelection) dbgs() << "BBV: candidate pair " << *I << " <-> " << *J << " (cost savings: " << CostSavings << ")\n"); // If we have already found too many pairs, break here and this function // will be called again starting after the last instruction selected // during this invocation. if (PairableInsts.size() >= Config.MaxInsts || TotalPairs >= Config.MaxPairs) { ShouldContinue = true; break; } } if (ShouldContinue) break; } DEBUG(dbgs() << "BBV: found " << PairableInsts.size() << " instructions with candidate pairs\n"); return ShouldContinue; } // Finds candidate pairs connected to the pair P =
. This means that // it looks for pairs such that both members have an input which is an // output of PI or PJ. void BBVectorize::computePairsConnectedTo( DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, std::vector
&PairableInsts, DenseMap
> &ConnectedPairs, DenseMap
&PairConnectionTypes, ValuePair P) { StoreInst *SI, *SJ; // For each possible pairing for this variable, look at the uses of // the first value... for (Value::user_iterator I = P.first->user_begin(), E = P.first->user_end(); I != E; ++I) { User *UI = *I; if (isa
(UI)) { // A pair cannot be connected to a load because the load only takes one // operand (the address) and it is a scalar even after vectorization. continue; } else if ((SI = dyn_cast
(UI)) && P.first == SI->getPointerOperand()) { // Similarly, a pair cannot be connected to a store through its // pointer operand. continue; } // For each use of the first variable, look for uses of the second // variable... for (User *UJ : P.second->users()) { if ((SJ = dyn_cast
(UJ)) && P.second == SJ->getPointerOperand()) continue; // Look for
: if (CandidatePairsSet.count(ValuePair(UI, UJ))) { VPPair VP(P, ValuePair(UI, UJ)); ConnectedPairs[VP.first].push_back(VP.second); PairConnectionTypes.insert(VPPairWithType(VP, PairConnectionDirect)); } // Look for
: if (CandidatePairsSet.count(ValuePair(UJ, UI))) { VPPair VP(P, ValuePair(UJ, UI)); ConnectedPairs[VP.first].push_back(VP.second); PairConnectionTypes.insert(VPPairWithType(VP, PairConnectionSwap)); } } if (Config.SplatBreaksChain) continue; // Look for cases where just the first value in the pair is used by // both members of another pair (splatting). for (Value::user_iterator J = P.first->user_begin(); J != E; ++J) { User *UJ = *J; if ((SJ = dyn_cast
(UJ)) && P.first == SJ->getPointerOperand()) continue; if (CandidatePairsSet.count(ValuePair(UI, UJ))) { VPPair VP(P, ValuePair(UI, UJ)); ConnectedPairs[VP.first].push_back(VP.second); PairConnectionTypes.insert(VPPairWithType(VP, PairConnectionSplat)); } } } if (Config.SplatBreaksChain) return; // Look for cases where just the second value in the pair is used by // both members of another pair (splatting). for (Value::user_iterator I = P.second->user_begin(), E = P.second->user_end(); I != E; ++I) { User *UI = *I; if (isa
(UI)) continue; else if ((SI = dyn_cast
(UI)) && P.second == SI->getPointerOperand()) continue; for (Value::user_iterator J = P.second->user_begin(); J != E; ++J) { User *UJ = *J; if ((SJ = dyn_cast
(UJ)) && P.second == SJ->getPointerOperand()) continue; if (CandidatePairsSet.count(ValuePair(UI, UJ))) { VPPair VP(P, ValuePair(UI, UJ)); ConnectedPairs[VP.first].push_back(VP.second); PairConnectionTypes.insert(VPPairWithType(VP, PairConnectionSplat)); } } } } // This function figures out which pairs are connected. Two pairs are // connected if some output of the first pair forms an input to both members // of the second pair. void BBVectorize::computeConnectedPairs( DenseMap
> &CandidatePairs, DenseSet
&CandidatePairsSet, std::vector
&PairableInsts, DenseMap
> &ConnectedPairs, DenseMap
&PairConnectionTypes) { for (std::vector
::iterator PI = PairableInsts.begin(), PE = PairableInsts.end(); PI != PE; ++PI) { DenseMap
>::iterator PP = CandidatePairs.find(*PI); if (PP == CandidatePairs.end()) continue; for (std::vector
::iterator P = PP->second.begin(), E = PP->second.end(); P != E; ++P) computePairsConnectedTo(CandidatePairs, CandidatePairsSet, PairableInsts, ConnectedPairs, PairConnectionTypes, ValuePair(*PI, *P)); } DEBUG(size_t TotalPairs = 0; for (DenseMap
>::iterator I = ConnectedPairs.begin(), IE = ConnectedPairs.end(); I != IE; ++I) TotalPairs += I->second.size(); dbgs() << "BBV: found " << TotalPairs << " pair connections.\n"); } // This function builds a set of use tuples such that
is in the set // if B is in the use dag of A. If B is in the use dag of A, then B // depends on the output of A. void BBVectorize::buildDepMap( BasicBlock &BB, DenseMap
> &CandidatePairs, std::vector
&PairableInsts, DenseSet
&PairableInstUsers) { DenseSet
IsInPair; for (DenseMap
>::iterator C = CandidatePairs.begin(), E = CandidatePairs.end(); C != E; ++C) { IsInPair.insert(C->first); IsInPair.insert(C->second.begin(), C->second.end()); } // Iterate through the basic block, recording all users of each // pairable instruction. BasicBlock::iterator E = BB.end(), EL = BasicBlock::iterator(cast
(PairableInsts.back())); for (BasicBlock::iterator I = BB.getFirstInsertionPt(); I != E; ++I) { if (IsInPair.find(I) == IsInPair.end()) continue; DenseSet
Users; AliasSetTracker WriteSet(*AA); if (I->mayWriteToMemory()) WriteSet.add(I); for (BasicBlock::iterator J = std::next(I); J != E; ++J) { (void) trackUsesOfI(Users, WriteSet, I, J); if (J == EL) break; } for (DenseSet
::iterator U = Users.begin(), E = Users.end(); U != E; ++U) { if (IsInPair.find(*U) == IsInPair.end()) continue; PairableInstUsers.insert(ValuePair(I, *U)); } if (I == EL) break; } } // Returns true if an input to pair P is an output of pair Q and also an // input of pair Q is an output of pair P. If this is the case, then these // two pairs cannot be simultaneously fused. bool BBVectorize::pairsConflict(ValuePair P, ValuePair Q, DenseSet
&PairableInstUsers, DenseMap
> *PairableInstUserMap, DenseSet
*PairableInstUserPairSet) { // Two pairs are in conflict if they are mutual Users of eachother. bool QUsesP = PairableInstUsers.count(ValuePair(P.first, Q.first)) || PairableInstUsers.count(ValuePair(P.first, Q.second)) || PairableInstUsers.count(ValuePair(P.second, Q.first)) || PairableInstUsers.count(ValuePair(P.second, Q.second)); bool PUsesQ = PairableInstUsers.count(ValuePair(Q.first, P.first)) || PairableInstUsers.count(ValuePair(Q.first, P.second)) || PairableInstUsers.count(ValuePair(Q.second, P.first)) || PairableInstUsers.count(ValuePair(Q.second, P.second)); if (PairableInstUserMap) { // FIXME: The expensive part of the cycle check is not so much the cycle // check itself but this edge insertion procedure. This needs some // profiling and probably a different data structure. if (PUsesQ) { if (PairableInstUserPairSet->insert(VPPair(Q, P)).second) (*PairableInstUserMap)[Q].push_back(P); } if (QUsesP) { if (PairableInstUserPairSet->insert(VPPair(P, Q)).second) (*PairableInstUserMap)[P].push_back(Q); } } return (QUsesP && PUsesQ); } // This function walks the use graph of current pairs to see if, starting // from P, the walk returns to P. bool BBVectorize::pairWillFormCycle(ValuePair P, DenseMap
> &PairableInstUserMap, DenseSet
&CurrentPairs) { DEBUG(if (DebugCycleCheck) dbgs() << "BBV: starting cycle check for : " << *P.first << " <-> " << *P.second << "\n"); // A lookup table of visisted pairs is kept because the PairableInstUserMap // contains non-direct associations. DenseSet
Visited; SmallVector
Q; // General depth-first post-order traversal: Q.push_back(P); do { ValuePair QTop = Q.pop_back_val(); Visited.insert(QTop); DEBUG(if (DebugCycleCheck) dbgs() << "BBV: cycle check visiting: " << *QTop.first << " <-> " << *QTop.second << "\n"); DenseMap
>::iterator QQ = PairableInstUserMap.find(QTop); if (QQ == PairableInstUserMap.end()) continue; for (std::vector
::iterator C = QQ->second.begin(), CE = QQ->second.end(); C != CE; ++C) { if (*C == P) { DEBUG(dbgs() << "BBV: rejected to prevent non-trivial cycle formation: " << QTop.first << " <-> " << C->second << "\n"); return true; } if (CurrentPairs.count(*C) && !Visited.count(*C)) Q.push_back(*C); } } while (!Q.empty()); return false; } // This function builds the initial dag of connected pairs with the // pair J at the root. void BBVectorize::buildInitialDAGFor( DenseMap
> &CandidatePairs, DenseSet