From c8d396a8a7e4abdbd86f78bb9aa78c7a3e0e2f0b Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Tue, 14 Mar 2017 11:25:45 +0000 Subject: [PATCH] Make PredIteratorCache size() logically const. Do not require copying predecessors to get size. Summary: Every single benchmark i can run, on large and small cfgs, fully connected, etc, across 3 different platforms (x86, arm., and PPC) says that the current pred iterator cache is a losing proposition. I can't find a case where it's faster than just walking preds, and in some cases, it's 5-10% slower. This is due to copying the preds. It also degrades into copying the entire cfg. The one operation that is occasionally faster is the cached size. This makes that operation faster by not relying on having the copies available. I'm not even sure that is faster enough to be worth it. I, again, have trouble finding cases where this takes long enough in a pass to be worth caching compared to a million other things they could cache or improve. My suggestion: We next remove the get() interface. We do stronger benchmarking of size(). We probably end up killing this entire cache. / Reviewers: chandlerc Subscribers: aemerson, llvm-commits, trentxintong Differential Revision: https://reviews.llvm.org/D30873 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@297733 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/PredIteratorCache.h | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/include/llvm/IR/PredIteratorCache.h b/include/llvm/IR/PredIteratorCache.h index 118310aed1d..81f53531143 100644 --- a/include/llvm/IR/PredIteratorCache.h +++ b/include/llvm/IR/PredIteratorCache.h @@ -27,8 +27,8 @@ namespace llvm { /// wants the predecessor list for the same blocks. class PredIteratorCache { /// BlockToPredsMap - Pointer to null-terminated list. - DenseMap BlockToPredsMap; - DenseMap BlockToPredCountMap; + mutable DenseMap BlockToPredsMap; + mutable DenseMap BlockToPredCountMap; /// Memory - This is the space that holds cached preds. BumpPtrAllocator Memory; @@ -55,13 +55,15 @@ private: return Entry; } - unsigned GetNumPreds(BasicBlock *BB) { - GetPreds(BB); - return BlockToPredCountMap[BB]; + unsigned GetNumPreds(BasicBlock *BB) const { + auto Result = BlockToPredCountMap.find(BB); + if (Result != BlockToPredCountMap.end()) + return Result->second; + return BlockToPredCountMap[BB] = std::distance(pred_begin(BB), pred_end(BB)); } public: - size_t size(BasicBlock *BB) { return GetNumPreds(BB); } + size_t size(BasicBlock *BB) const { return GetNumPreds(BB); } ArrayRef get(BasicBlock *BB) { return makeArrayRef(GetPreds(BB), GetNumPreds(BB)); } -- 2.50.1