Index: include/llvm/Analysis/MemoryDependenceAnalysis.h =================================================================== --- include/llvm/Analysis/MemoryDependenceAnalysis.h +++ include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -19,6 +19,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/BasicBlock.h" +#include "llvm/IR/PredIteratorCache.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" @@ -325,7 +326,7 @@ AliasAnalysis *AA; DominatorTree *DT; AssumptionCache *AC; - std::unique_ptr PredCache; + PredIteratorCache PredCache; public: MemoryDependenceAnalysis(); Index: include/llvm/IR/PredIteratorCache.h =================================================================== --- include/llvm/IR/PredIteratorCache.h +++ include/llvm/IR/PredIteratorCache.h @@ -14,6 +14,7 @@ #ifndef LLVM_IR_PREDITERATORCACHE_H #define LLVM_IR_PREDITERATORCACHE_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/CFG.h" @@ -21,50 +22,62 @@ namespace llvm { - /// PredIteratorCache - This class is an extremely trivial cache for - /// predecessor iterator queries. This is useful for code that repeatedly - /// wants the predecessor list for the same blocks. - class PredIteratorCache { - /// BlockToPredsMap - Pointer to null-terminated list. - DenseMap BlockToPredsMap; - DenseMap BlockToPredCountMap; +/// PredIteratorCache - This class is an extremely trivial cache for +/// predecessor iterator queries. This is useful for code that repeatedly +/// wants the predecessor list for the same blocks. +class PredIteratorCache { + /// BlockToPredsMap - Pointer to null-terminated list. + DenseMap BlockToPredsMap; + DenseMap BlockToPredCountMap; - /// Memory - This is the space that holds cached preds. - BumpPtrAllocator Memory; - public: + /// Memory - This is the space that holds cached preds. + BumpPtrAllocator Memory; - /// GetPreds - Get a cached list for the null-terminated predecessor list of - /// the specified block. This can be used in a loop like this: - /// for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) - /// use(*PI); - /// instead of: - /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - BasicBlock **GetPreds(BasicBlock *BB) { - BasicBlock **&Entry = BlockToPredsMap[BB]; - if (Entry) return Entry; +private: + /// GetPreds - Get a cached list for the null-terminated predecessor list of + /// the specified block. This can be used in a loop like this: + /// for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) + /// use(*PI); + /// instead of: + /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + BasicBlock **GetPreds(BasicBlock *BB) { + BasicBlock **&Entry = BlockToPredsMap[BB]; + if (Entry) + return Entry; - SmallVector PredCache(pred_begin(BB), pred_end(BB)); - PredCache.push_back(nullptr); // null terminator. - - BlockToPredCountMap[BB] = PredCache.size()-1; + SmallVector PredCache(pred_begin(BB), pred_end(BB)); + PredCache.push_back(nullptr); // null terminator. - Entry = Memory.Allocate(PredCache.size()); - std::copy(PredCache.begin(), PredCache.end(), Entry); - return Entry; - } - - unsigned GetNumPreds(BasicBlock *BB) { - GetPreds(BB); - return BlockToPredCountMap[BB]; - } + BlockToPredCountMap[BB] = PredCache.size() - 1; + + Entry = Memory.Allocate(PredCache.size()); + std::copy(PredCache.begin(), PredCache.end(), Entry); + return Entry; + } + + unsigned GetNumPreds(BasicBlock *BB) { + GetPreds(BB); + return BlockToPredCountMap[BB]; + } + +public: + BasicBlock **begin(BasicBlock *BB) { return GetPreds(BB); } + BasicBlock **end(BasicBlock *BB) { return GetPreds(BB) + GetNumPreds(BB); } + size_t size(BasicBlock *BB) { return GetNumPreds(BB); } + + /// clear - Remove all information. + void clear() { + BlockToPredsMap.clear(); + BlockToPredCountMap.clear(); + Memory.Reset(); + } +}; + +inline ArrayRef cached_predecessors(PredIteratorCache &PC, + BasicBlock *BB) { + return makeArrayRef(PC.begin(BB), PC.end(BB)); +} - /// clear - Remove all information. - void clear() { - BlockToPredsMap.clear(); - BlockToPredCountMap.clear(); - Memory.Reset(); - } - }; } // end namespace llvm #endif Index: lib/Analysis/MemoryDependenceAnalysis.cpp =================================================================== --- lib/Analysis/MemoryDependenceAnalysis.cpp +++ lib/Analysis/MemoryDependenceAnalysis.cpp @@ -65,7 +65,7 @@ "Memory Dependence Analysis", false, true) MemoryDependenceAnalysis::MemoryDependenceAnalysis() - : FunctionPass(ID), PredCache() { + : FunctionPass(ID) { initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } MemoryDependenceAnalysis::~MemoryDependenceAnalysis() { @@ -79,7 +79,7 @@ ReverseLocalDeps.clear(); ReverseNonLocalDeps.clear(); ReverseNonLocalPtrDeps.clear(); - PredCache->clear(); + PredCache.clear(); } /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. @@ -96,8 +96,6 @@ DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); DT = DTWP ? &DTWP->getDomTree() : nullptr; - if (!PredCache) - PredCache.reset(new PredIteratorCache()); return false; } @@ -770,8 +768,8 @@ } else { // Seed DirtyBlocks with each of the preds of QueryInst's block. BasicBlock *QueryBB = QueryCS.getInstruction()->getParent(); - for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI) - DirtyBlocks.push_back(*PI); + for (BasicBlock *Pred : cached_predecessors(PredCache, QueryBB)) + DirtyBlocks.push_back(Pred); ++NumUncacheNonLocal; } @@ -856,8 +854,8 @@ // If the block *is* completely transparent to the load, we need to check // the predecessors of this block. Add them to our worklist. - for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI) - DirtyBlocks.push_back(*PI); + for (BasicBlock *Pred : cached_predecessors(PredCache, DirtyBB)) + DirtyBlocks.push_back(Pred); } } @@ -1232,13 +1230,13 @@ if (!Pointer.NeedsPHITranslationFromBlock(BB)) { SkipFirstBlock = false; SmallVector NewBlocks; - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { + for (BasicBlock *Pred : cached_predecessors(PredCache, BB)) { // Verify that we haven't looked at this block yet. std::pair::iterator, bool> - InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr())); + InsertRes = Visited.insert(std::make_pair(Pred, Pointer.getAddr())); if (InsertRes.second) { // First time we've looked at *PI. - NewBlocks.push_back(*PI); + NewBlocks.push_back(Pred); continue; } @@ -1274,8 +1272,7 @@ Cache = nullptr; PredList.clear(); - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { - BasicBlock *Pred = *PI; + for (BasicBlock *Pred : cached_predecessors(PredCache, BB)){ PredList.push_back(std::make_pair(Pred, Pointer)); // Get the PHI translated pointer in this predecessor. This can fail if @@ -1465,7 +1462,7 @@ /// This needs to be done when the CFG changes, e.g., due to splitting /// critical edges. void MemoryDependenceAnalysis::invalidateCachedPredecessors() { - PredCache->clear(); + PredCache.clear(); } /// removeInstruction - Remove an instruction from the dependence analysis, Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -704,10 +704,10 @@ // We need to create an LCSSA PHI node for the incoming value and // store that. PHINode *PN = PHINode::Create( - I->getType(), PredCache.GetNumPreds(BB), + I->getType(), PredCache.size(BB), I->getName() + ".lcssa", BB->begin()); - for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI) - PN->addIncoming(I, *PI); + for (BasicBlock *Pred : cached_predecessors(PredCache, BB)) + PN->addIncoming(I, Pred); return PN; } return V; Index: lib/Transforms/Utils/LCSSA.cpp =================================================================== --- lib/Transforms/Utils/LCSSA.cpp +++ lib/Transforms/Utils/LCSSA.cpp @@ -112,17 +112,17 @@ if (SSAUpdate.HasValueForBlock(ExitBB)) continue; - PHINode *PN = PHINode::Create(Inst.getType(), PredCache.GetNumPreds(ExitBB), + PHINode *PN = PHINode::Create(Inst.getType(), PredCache.size(ExitBB), Inst.getName() + ".lcssa", ExitBB->begin()); // Add inputs from inside the loop for this PHI. - for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) { - PN->addIncoming(&Inst, *PI); + for (BasicBlock *Pred : cached_predecessors(PredCache, ExitBB)) { + PN->addIncoming(&Inst, Pred); // If the exit block has a predecessor not within the loop, arrange for // the incoming value use corresponding to that predecessor to be // rewritten in terms of a different LCSSA PHI. - if (!L.contains(*PI)) + if (!L.contains(Pred)) UsesToRewrite.push_back( &PN->getOperandUse(PN->getOperandNumForIncomingValue( PN->getNumIncomingValues() - 1)));