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