1 //===- llvm/Support/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 #include "llvm/Support/Allocator.h" 15 #include "llvm/Support/CFG.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/SmallVector.h" 18 19 #ifndef LLVM_SUPPORT_PREDITERATORCACHE_H 20 #define LLVM_SUPPORT_PREDITERATORCACHE_H 21 22 namespace llvm { 23 24 /// PredIteratorCache - This class is an extremely trivial cache for 25 /// predecessor iterator queries. This is useful for code that repeatedly 26 /// wants the predecessor list for the same blocks. 27 class PredIteratorCache { 28 /// BlockToPredsMap - Pointer to null-terminated list. 29 DenseMap<BasicBlock*, BasicBlock**> BlockToPredsMap; 30 DenseMap<BasicBlock*, unsigned> BlockToPredCountMap; 31 32 /// Memory - This is the space that holds cached preds. 33 BumpPtrAllocator Memory; 34 public: 35 36 /// GetPreds - Get a cached list for the null-terminated predecessor list of 37 /// the specified block. This can be used in a loop like this: 38 /// for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) 39 /// use(*PI); 40 /// instead of: 41 /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) GetPreds(BasicBlock * BB)42 BasicBlock **GetPreds(BasicBlock *BB) { 43 BasicBlock **&Entry = BlockToPredsMap[BB]; 44 if (Entry) return Entry; 45 46 SmallVector<BasicBlock*, 32> PredCache(pred_begin(BB), pred_end(BB)); 47 PredCache.push_back(0); // null terminator. 48 49 BlockToPredCountMap[BB] = PredCache.size()-1; 50 51 Entry = Memory.Allocate<BasicBlock*>(PredCache.size()); 52 std::copy(PredCache.begin(), PredCache.end(), Entry); 53 return Entry; 54 } 55 GetNumPreds(BasicBlock * BB)56 unsigned GetNumPreds(BasicBlock *BB) { 57 GetPreds(BB); 58 return BlockToPredCountMap[BB]; 59 } 60 61 /// clear - Remove all information. clear()62 void clear() { 63 BlockToPredsMap.clear(); 64 BlockToPredCountMap.clear(); 65 Memory.Reset(); 66 } 67 }; 68 } // end namespace llvm 69 70 #endif 71