1 //===- PredIteratorCache.h - pred_iterator Cache ----------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the PredIteratorCache class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_IR_PREDITERATORCACHE_H 14 #define LLVM_IR_PREDITERATORCACHE_H 15 16 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/IR/CFG.h" 20 #include "llvm/Support/Allocator.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 mutable DenseMap<BasicBlock *, BasicBlock **> BlockToPredsMap; 30 mutable DenseMap<BasicBlock *, unsigned> BlockToPredCountMap; 31 32 /// Memory - This is the space that holds cached preds. 33 BumpPtrAllocator Memory; 34 35 private: 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) 45 return Entry; 46 47 SmallVector<BasicBlock *, 32> PredCache(predecessors(BB)); 48 PredCache.push_back(nullptr); // null terminator. 49 50 BlockToPredCountMap[BB] = PredCache.size() - 1; 51 52 Entry = Memory.Allocate<BasicBlock *>(PredCache.size()); 53 std::copy(PredCache.begin(), PredCache.end(), Entry); 54 return Entry; 55 } 56 GetNumPreds(BasicBlock * BB)57 unsigned GetNumPreds(BasicBlock *BB) const { 58 auto Result = BlockToPredCountMap.find(BB); 59 if (Result != BlockToPredCountMap.end()) 60 return Result->second; 61 return BlockToPredCountMap[BB] = pred_size(BB); 62 } 63 64 public: size(BasicBlock * BB)65 size_t size(BasicBlock *BB) const { return GetNumPreds(BB); } get(BasicBlock * BB)66 ArrayRef<BasicBlock *> get(BasicBlock *BB) { 67 return ArrayRef(GetPreds(BB), GetNumPreds(BB)); 68 } 69 70 /// clear - Remove all information. clear()71 void clear() { 72 BlockToPredsMap.clear(); 73 BlockToPredCountMap.clear(); 74 Memory.Reset(); 75 } 76 }; 77 78 } // end namespace llvm 79 80 #endif 81