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 22namespace 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) 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 56 unsigned GetNumPreds(BasicBlock *BB) { 57 GetPreds(BB); 58 return BlockToPredCountMap[BB]; 59 } 60 61 /// clear - Remove all information. 62 void clear() { 63 BlockToPredsMap.clear(); 64 BlockToPredCountMap.clear(); 65 Memory.Reset(); 66 } 67 }; 68} // end namespace llvm 69 70#endif 71