From c89e75e93e24613fe95a72df4007dff5b97a1beb Mon Sep 17 00:00:00 2001 From: Hal Finkel Date: Thu, 1 Nov 2012 06:26:34 +0000 Subject: BBVectorize: Account for internal shuffle costs When target costs are available, use them to account for the costs of shuffles on internal edges of the DAG of candidate pairs. Because the shuffle costs here are currently for only the internal edges, the current target cost model is trivial, and the chain depth requirement is still in place, I don't yet have an easy test case. Nevertheless, by looking at the debug output, it does seem to do the right think to the effective "size" of each DAG of candidate pairs. llvm-svn: 167217 --- llvm/lib/Transforms/Vectorize/BBVectorize.cpp | 62 ++++++++++++++++++++++++++- 1 file changed, 60 insertions(+), 2 deletions(-) (limited to 'llvm/lib/Transforms') diff --git a/llvm/lib/Transforms/Vectorize/BBVectorize.cpp b/llvm/lib/Transforms/Vectorize/BBVectorize.cpp index 40277dc237c..6e36ff7b5d2 100644 --- a/llvm/lib/Transforms/Vectorize/BBVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/BBVectorize.cpp @@ -246,7 +246,10 @@ namespace { void choosePairs(std::multimap &CandidatePairs, DenseMap &CandidatePairCostSavings, std::vector &PairableInsts, + DenseSet &FixedOrderPairs, + DenseMap &PairConnectionTypes, std::multimap &ConnectedPairs, + std::multimap &ConnectedPairDeps, DenseSet &PairableInstUsers, DenseMap& ChosenPairs); @@ -308,7 +311,10 @@ namespace { std::multimap &CandidatePairs, DenseMap &CandidatePairCostSavings, std::vector &PairableInsts, + DenseSet &FixedOrderPairs, + DenseMap &PairConnectionTypes, std::multimap &ConnectedPairs, + std::multimap &ConnectedPairDeps, DenseSet &PairableInstUsers, std::multimap &PairableInstUserMap, DenseMap &ChosenPairs, @@ -550,6 +556,7 @@ namespace { case Instruction::Trunc: case Instruction::FPTrunc: case Instruction::BitCast: + case Instruction::ShuffleVector: return VTTI->getCastInstrCost(Opcode, T1, T2); } @@ -714,7 +721,8 @@ namespace { DenseMap ChosenPairs; choosePairs(CandidatePairs, CandidatePairCostSavings, - PairableInsts, ConnectedPairs, + PairableInsts, FixedOrderPairs, PairConnectionTypes, + ConnectedPairs, ConnectedPairDeps, PairableInstUsers, ChosenPairs); if (ChosenPairs.empty()) continue; @@ -1597,7 +1605,10 @@ namespace { std::multimap &CandidatePairs, DenseMap &CandidatePairCostSavings, std::vector &PairableInsts, + DenseSet &FixedOrderPairs, + DenseMap &PairConnectionTypes, std::multimap &ConnectedPairs, + std::multimap &ConnectedPairDeps, DenseSet &PairableInstUsers, std::multimap &PairableInstUserMap, DenseMap &ChosenPairs, @@ -1654,10 +1665,53 @@ namespace { int EffSize = 0; if (VTTI) { + // The node weights represent the cost savings associated with + // fusing the pair of instructions. for (DenseSet::iterator S = PrunedTree.begin(), E = PrunedTree.end(); S != E; ++S) { if (getDepthFactor(S->first)) EffSize += CandidatePairCostSavings.find(*S)->second; + + // The edge weights contribute in a negative sense: they represent + // the cost of shuffles. + VPPIteratorPair IP = ConnectedPairDeps.equal_range(*S); + if (IP.first != ConnectedPairDeps.end()) { + unsigned NumDepsDirect = 0, NumDepsSwap = 0; + for (std::multimap::iterator Q = IP.first; + Q != IP.second; ++Q) { + DenseMap::iterator R = + PairConnectionTypes.find(VPPair(Q->second, Q->first)); + assert(R != PairConnectionTypes.end() && + "Cannot find pair connection type"); + if (R->second == PairConnectionDirect) + ++NumDepsDirect; + else if (R->second == PairConnectionSwap) + ++NumDepsSwap; + } + + // If there are more swaps than direct connections, then + // the pair order will be flipped during fusion. So the real + // number of swaps is the minimum number. + bool FlipOrder = !FixedOrderPairs.count(*S) && + ((NumDepsSwap > NumDepsDirect) || + FixedOrderPairs.count(ValuePair(S->second, S->first))); + + for (std::multimap::iterator Q = IP.first; + Q != IP.second; ++Q) { + DenseMap::iterator R = + PairConnectionTypes.find(VPPair(Q->second, Q->first)); + assert(R != PairConnectionTypes.end() && + "Cannot find pair connection type"); + Type *Ty1 = Q->second.first->getType(), + *Ty2 = Q->second.second->getType(); + Type *VTy = getVecTypeForPair(Ty1, Ty2); + if ((R->second == PairConnectionDirect && FlipOrder) || + (R->second == PairConnectionSwap && !FlipOrder) || + R->second == PairConnectionSplat) + EffSize -= (int) getInstrCost(Instruction::ShuffleVector, + VTy, VTy); + } + } } } else { for (DenseSet::iterator S = PrunedTree.begin(), @@ -1685,7 +1739,10 @@ namespace { std::multimap &CandidatePairs, DenseMap &CandidatePairCostSavings, std::vector &PairableInsts, + DenseSet &FixedOrderPairs, + DenseMap &PairConnectionTypes, std::multimap &ConnectedPairs, + std::multimap &ConnectedPairDeps, DenseSet &PairableInstUsers, DenseMap& ChosenPairs) { bool UseCycleCheck = @@ -1704,7 +1761,8 @@ namespace { int BestEffSize = 0; DenseSet BestTree; findBestTreeFor(CandidatePairs, CandidatePairCostSavings, - PairableInsts, ConnectedPairs, + PairableInsts, FixedOrderPairs, PairConnectionTypes, + ConnectedPairs, ConnectedPairDeps, PairableInstUsers, PairableInstUserMap, ChosenPairs, BestTree, BestMaxDepth, BestEffSize, ChoiceRange, UseCycleCheck); -- cgit v1.2.3