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 DenseMap<BasicBlock *, BasicBlock **> BlockToPredsMap; 31 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) GetPreds(BasicBlock * BB)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 GetNumPreds(BasicBlock * BB)58 unsigned GetNumPreds(BasicBlock *BB) { 59 GetPreds(BB); 60 return BlockToPredCountMap[BB]; 61 } 62 63 public: size(BasicBlock * BB)64 size_t size(BasicBlock *BB) { return GetNumPreds(BB); } get(BasicBlock * BB)65 ArrayRef<BasicBlock *> get(BasicBlock *BB) { 66 return makeArrayRef(GetPreds(BB), GetNumPreds(BB)); 67 } 68 69 /// clear - Remove all information. clear()70 void clear() { 71 BlockToPredsMap.clear(); 72 BlockToPredCountMap.clear(); 73 Memory.Reset(); 74 } 75 }; 76 77 } // end namespace llvm 78 79 #endif 80