1 //===- PredIteratorCache.h - pred_iterator Cache ----------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the PredIteratorCache class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_IR_PREDITERATORCACHE_H 15 #define LLVM_IR_PREDITERATORCACHE_H 16 17 #include "llvm/ADT/ArrayRef.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/IR/CFG.h" 21 #include "llvm/Support/Allocator.h" 22 23 namespace llvm { 24 25 /// PredIteratorCache - This class is an extremely trivial cache for 26 /// predecessor iterator queries. This is useful for code that repeatedly 27 /// wants the predecessor list for the same blocks. 28 class PredIteratorCache { 29 /// BlockToPredsMap - Pointer to null-terminated list. 30 mutable DenseMap<BasicBlock *, BasicBlock **> BlockToPredsMap; 31 mutable DenseMap<BasicBlock *, unsigned> BlockToPredCountMap; 32 33 /// Memory - This is the space that holds cached preds. 34 BumpPtrAllocator Memory; 35 36 private: 37 /// GetPreds - Get a cached list for the null-terminated predecessor list of 38 /// the specified block. This can be used in a loop like this: 39 /// for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) 40 /// use(*PI); 41 /// instead of: 42 /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 43 BasicBlock **GetPreds(BasicBlock *BB) { 44 BasicBlock **&Entry = BlockToPredsMap[BB]; 45 if (Entry) 46 return Entry; 47 48 SmallVector<BasicBlock *, 32> PredCache(pred_begin(BB), pred_end(BB)); 49 PredCache.push_back(nullptr); // null terminator. 50 51 BlockToPredCountMap[BB] = PredCache.size() - 1; 52 53 Entry = Memory.Allocate<BasicBlock *>(PredCache.size()); 54 std::copy(PredCache.begin(), PredCache.end(), Entry); 55 return Entry; 56 } 57 58 unsigned GetNumPreds(BasicBlock *BB) const { 59 auto Result = BlockToPredCountMap.find(BB); 60 if (Result != BlockToPredCountMap.end()) 61 return Result->second; 62 return BlockToPredCountMap[BB] = std::distance(pred_begin(BB), pred_end(BB)); 63 } 64 65 public: 66 size_t size(BasicBlock *BB) const { return GetNumPreds(BB); } 67 ArrayRef<BasicBlock *> get(BasicBlock *BB) { 68 return makeArrayRef(GetPreds(BB), GetNumPreds(BB)); 69 } 70 71 /// clear - Remove all information. 72 void clear() { 73 BlockToPredsMap.clear(); 74 BlockToPredCountMap.clear(); 75 Memory.Reset(); 76 } 77 }; 78 79 } // end namespace llvm 80 81 #endif 82
