From 2f0e63cc16feb39480805bd00f53bbe5e3031d29 Mon Sep 17 00:00:00 2001 From: Hal Finkel Date: Mon, 11 Feb 2013 05:29:49 +0000 Subject: BBVectorize: Avoid linear searches within the load-move set This is another cleanup aimed at eliminating linear searches in ranges of std::multimap. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174858 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Vectorize/BBVectorize.cpp | 50 +++++++++++++++++++------------- 1 file changed, 30 insertions(+), 20 deletions(-) (limited to 'lib/Transforms') diff --git a/lib/Transforms/Vectorize/BBVectorize.cpp b/lib/Transforms/Vectorize/BBVectorize.cpp index 682e992..0d3a444 100644 --- a/lib/Transforms/Vectorize/BBVectorize.cpp +++ b/lib/Transforms/Vectorize/BBVectorize.cpp @@ -277,7 +277,7 @@ namespace { bool trackUsesOfI(DenseSet &Users, AliasSetTracker &WriteSet, Instruction *I, Instruction *J, bool UpdateUsers = true, - std::multimap *LoadMoveSet = 0); + DenseSet *LoadMoveSetPairs = 0); void computePairsConnectedTo( std::multimap &CandidatePairs, @@ -362,19 +362,21 @@ namespace { void collectPairLoadMoveSet(BasicBlock &BB, DenseMap &ChosenPairs, std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs, Instruction *I); void collectLoadMoveSet(BasicBlock &BB, std::vector &PairableInsts, DenseMap &ChosenPairs, - std::multimap &LoadMoveSet); + std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs); bool canMoveUsesOfIAfterJ(BasicBlock &BB, - std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs, Instruction *I, Instruction *J); void moveUsesOfIAfterJ(BasicBlock &BB, - std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs, Instruction *&InsertionPt, Instruction *I, Instruction *J); @@ -1114,7 +1116,7 @@ namespace { bool BBVectorize::trackUsesOfI(DenseSet &Users, AliasSetTracker &WriteSet, Instruction *I, Instruction *J, bool UpdateUsers, - std::multimap *LoadMoveSet) { + DenseSet *LoadMoveSetPairs) { bool UsesI = false; // This instruction may already be marked as a user due, for example, to @@ -1132,9 +1134,8 @@ namespace { } } if (!UsesI && J->mayReadFromMemory()) { - if (LoadMoveSet) { - VPIteratorPair JPairRange = LoadMoveSet->equal_range(J); - UsesI = isSecondInIteratorPair(I, JPairRange); + if (LoadMoveSetPairs) { + UsesI = LoadMoveSetPairs->count(ValuePair(J, I)); } else { for (AliasSetTracker::iterator W = WriteSet.begin(), WE = WriteSet.end(); W != WE; ++W) { @@ -2737,7 +2738,7 @@ namespace { // Move all uses of the function I (including pairing-induced uses) after J. bool BBVectorize::canMoveUsesOfIAfterJ(BasicBlock &BB, - std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs, Instruction *I, Instruction *J) { // Skip to the first instruction past I. BasicBlock::iterator L = llvm::next(BasicBlock::iterator(I)); @@ -2745,18 +2746,18 @@ namespace { DenseSet Users; AliasSetTracker WriteSet(*AA); for (; cast(L) != J; ++L) - (void) trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSet); + (void) trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSetPairs); assert(cast(L) == J && "Tracking has not proceeded far enough to check for dependencies"); // If J is now in the use set of I, then trackUsesOfI will return true // and we have a dependency cycle (and the fusing operation must abort). - return !trackUsesOfI(Users, WriteSet, I, J, true, &LoadMoveSet); + return !trackUsesOfI(Users, WriteSet, I, J, true, &LoadMoveSetPairs); } // Move all uses of the function I (including pairing-induced uses) after J. void BBVectorize::moveUsesOfIAfterJ(BasicBlock &BB, - std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs, Instruction *&InsertionPt, Instruction *I, Instruction *J) { // Skip to the first instruction past I. @@ -2765,7 +2766,7 @@ namespace { DenseSet Users; AliasSetTracker WriteSet(*AA); for (; cast(L) != J;) { - if (trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSet)) { + if (trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSetPairs)) { // Move this instruction Instruction *InstToMove = L; ++L; @@ -2786,6 +2787,7 @@ namespace { void BBVectorize::collectPairLoadMoveSet(BasicBlock &BB, DenseMap &ChosenPairs, std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs, Instruction *I) { // Skip to the first instruction past I. BasicBlock::iterator L = llvm::next(BasicBlock::iterator(I)); @@ -2798,8 +2800,10 @@ namespace { // could be before I if this is an inverted input. for (BasicBlock::iterator E = BB.end(); cast(L) != E; ++L) { if (trackUsesOfI(Users, WriteSet, I, L)) { - if (L->mayReadFromMemory()) + if (L->mayReadFromMemory()) { LoadMoveSet.insert(ValuePair(L, I)); + LoadMoveSetPairs.insert(ValuePair(L, I)); + } } } } @@ -2814,14 +2818,16 @@ namespace { void BBVectorize::collectLoadMoveSet(BasicBlock &BB, std::vector &PairableInsts, DenseMap &ChosenPairs, - std::multimap &LoadMoveSet) { + std::multimap &LoadMoveSet, + DenseSet &LoadMoveSetPairs) { for (std::vector::iterator PI = PairableInsts.begin(), PIE = PairableInsts.end(); PI != PIE; ++PI) { DenseMap::iterator P = ChosenPairs.find(*PI); if (P == ChosenPairs.end()) continue; Instruction *I = cast(P->first); - collectPairLoadMoveSet(BB, ChosenPairs, LoadMoveSet, I); + collectPairLoadMoveSet(BB, ChosenPairs, LoadMoveSet, + LoadMoveSetPairs, I); } } @@ -2877,7 +2883,9 @@ namespace { ChosenPairs.insert(*P); std::multimap LoadMoveSet; - collectLoadMoveSet(BB, PairableInsts, ChosenPairs, LoadMoveSet); + DenseSet LoadMoveSetPairs; + collectLoadMoveSet(BB, PairableInsts, ChosenPairs, + LoadMoveSet, LoadMoveSetPairs); DEBUG(dbgs() << "BBV: initial: \n" << BB << "\n"); @@ -2909,7 +2917,7 @@ namespace { ChosenPairs.erase(FP); ChosenPairs.erase(P); - if (!canMoveUsesOfIAfterJ(BB, LoadMoveSet, I, J)) { + if (!canMoveUsesOfIAfterJ(BB, LoadMoveSetPairs, I, J)) { DEBUG(dbgs() << "BBV: fusion of: " << *I << " <-> " << *J << " aborted because of non-trivial dependency cycle\n"); @@ -3010,7 +3018,7 @@ namespace { // first instruction is disjoint from the input tree of the second // (by definition), and so commutes with it. - moveUsesOfIAfterJ(BB, LoadMoveSet, InsertionPt, I, J); + moveUsesOfIAfterJ(BB, LoadMoveSetPairs, InsertionPt, I, J); if (!isa(I)) { L->replaceAllUsesWith(K1); @@ -3036,8 +3044,10 @@ namespace { N != JPairRange.second; ++N) NewSetMembers.push_back(ValuePair(K, N->second)); for (std::vector::iterator A = NewSetMembers.begin(), - AE = NewSetMembers.end(); A != AE; ++A) + AE = NewSetMembers.end(); A != AE; ++A) { LoadMoveSet.insert(*A); + LoadMoveSetPairs.insert(*A); + } } // Before removing I, set the iterator to the next instruction. -- cgit v1.1