From 13ba3ca69f933b03ad2c9dbb0a382914f1868500 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Tue, 21 Apr 2015 21:11:50 +0000 Subject: [PATCH] Revamp PredIteratorCache interface to be cleaner. Summary: This lets us use range based for loops. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9169 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@235416 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Analysis/MemoryDependenceAnalysis.h | 3 +- include/llvm/IR/PredIteratorCache.h | 87 ++++++++++--------- lib/Analysis/MemoryDependenceAnalysis.cpp | 25 +++--- lib/Transforms/Scalar/LICM.cpp | 6 +- lib/Transforms/Utils/LCSSA.cpp | 8 +- 5 files changed, 68 insertions(+), 61 deletions(-) diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index c8453e9ea34..cf51dd62388 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/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 @@ namespace llvm { AliasAnalysis *AA; DominatorTree *DT; AssumptionCache *AC; - std::unique_ptr PredCache; + PredIteratorCache PredCache; public: MemoryDependenceAnalysis(); diff --git a/include/llvm/IR/PredIteratorCache.h b/include/llvm/IR/PredIteratorCache.h index 5e1be37805f..118310aed1d 100644 --- a/include/llvm/IR/PredIteratorCache.h +++ b/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,58 @@ 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: + size_t size(BasicBlock *BB) { return GetNumPreds(BB); } + ArrayRef get(BasicBlock *BB) { + return makeArrayRef(GetPreds(BB), GetNumPreds(BB)); + } + + /// clear - Remove all information. + void clear() { + BlockToPredsMap.clear(); + BlockToPredCountMap.clear(); + Memory.Reset(); + } +}; - /// clear - Remove all information. - void clear() { - BlockToPredsMap.clear(); - BlockToPredCountMap.clear(); - Memory.Reset(); - } - }; } // end namespace llvm #endif diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 84769cb07d7..3c1826a58e6 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -65,7 +65,7 @@ INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", "Memory Dependence Analysis", false, true) MemoryDependenceAnalysis::MemoryDependenceAnalysis() - : FunctionPass(ID), PredCache() { + : FunctionPass(ID) { initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } MemoryDependenceAnalysis::~MemoryDependenceAnalysis() { @@ -79,7 +79,7 @@ void MemoryDependenceAnalysis::releaseMemory() { ReverseLocalDeps.clear(); ReverseNonLocalDeps.clear(); ReverseNonLocalPtrDeps.clear(); - PredCache->clear(); + PredCache.clear(); } /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. @@ -96,8 +96,6 @@ bool MemoryDependenceAnalysis::runOnFunction(Function &F) { DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); DT = DTWP ? &DTWP->getDomTree() : nullptr; - if (!PredCache) - PredCache.reset(new PredIteratorCache()); return false; } @@ -770,8 +768,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { } 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 : PredCache.get(QueryBB)) + DirtyBlocks.push_back(Pred); ++NumUncacheNonLocal; } @@ -856,8 +854,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // 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 : PredCache.get(DirtyBB)) + DirtyBlocks.push_back(Pred); } } @@ -1232,13 +1230,13 @@ getNonLocalPointerDepFromBB(Instruction *QueryInst, if (!Pointer.NeedsPHITranslationFromBlock(BB)) { SkipFirstBlock = false; SmallVector NewBlocks; - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { + for (BasicBlock *Pred : PredCache.get(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 @@ getNonLocalPointerDepFromBB(Instruction *QueryInst, Cache = nullptr; PredList.clear(); - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { - BasicBlock *Pred = *PI; + for (BasicBlock *Pred : PredCache.get(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 @@ void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { /// 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, diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index 1333b024f7b..0b98f6c2c12 100644 --- a/lib/Transforms/Scalar/LICM.cpp +++ b/lib/Transforms/Scalar/LICM.cpp @@ -704,10 +704,10 @@ namespace { // 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 : PredCache.get(BB)) + PN->addIncoming(I, Pred); return PN; } return V; diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index 1cba367a3e4..cf155a6487a 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -112,17 +112,17 @@ static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, 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 : PredCache.get(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))); -- 2.34.1