1193323Sed//===- llvm/Support/PredIteratorCache.h - pred_iterator Cache ---*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the PredIteratorCache class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14252723Sdim#include "llvm/ADT/DenseMap.h" 15252723Sdim#include "llvm/ADT/SmallVector.h" 16193323Sed#include "llvm/Support/Allocator.h" 17193323Sed#include "llvm/Support/CFG.h" 18193323Sed 19193323Sed#ifndef LLVM_SUPPORT_PREDITERATORCACHE_H 20193323Sed#define LLVM_SUPPORT_PREDITERATORCACHE_H 21193323Sed 22193323Sednamespace llvm { 23193323Sed 24193323Sed /// PredIteratorCache - This class is an extremely trivial cache for 25193323Sed /// predecessor iterator queries. This is useful for code that repeatedly 26193323Sed /// wants the predecessor list for the same blocks. 27193323Sed class PredIteratorCache { 28193323Sed /// BlockToPredsMap - Pointer to null-terminated list. 29193323Sed DenseMap<BasicBlock*, BasicBlock**> BlockToPredsMap; 30193323Sed DenseMap<BasicBlock*, unsigned> BlockToPredCountMap; 31193323Sed 32193323Sed /// Memory - This is the space that holds cached preds. 33193323Sed BumpPtrAllocator Memory; 34193323Sed public: 35193323Sed 36193323Sed /// GetPreds - Get a cached list for the null-terminated predecessor list of 37193323Sed /// the specified block. This can be used in a loop like this: 38193323Sed /// for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) 39193323Sed /// use(*PI); 40193323Sed /// instead of: 41193323Sed /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 42193323Sed BasicBlock **GetPreds(BasicBlock *BB) { 43193323Sed BasicBlock **&Entry = BlockToPredsMap[BB]; 44193323Sed if (Entry) return Entry; 45193323Sed 46193323Sed SmallVector<BasicBlock*, 32> PredCache(pred_begin(BB), pred_end(BB)); 47193323Sed PredCache.push_back(0); // null terminator. 48193323Sed 49193323Sed BlockToPredCountMap[BB] = PredCache.size()-1; 50193323Sed 51193323Sed Entry = Memory.Allocate<BasicBlock*>(PredCache.size()); 52193323Sed std::copy(PredCache.begin(), PredCache.end(), Entry); 53193323Sed return Entry; 54193323Sed } 55193323Sed 56193323Sed unsigned GetNumPreds(BasicBlock *BB) { 57193323Sed GetPreds(BB); 58193323Sed return BlockToPredCountMap[BB]; 59193323Sed } 60193323Sed 61193323Sed /// clear - Remove all information. 62193323Sed void clear() { 63193323Sed BlockToPredsMap.clear(); 64193323Sed BlockToPredCountMap.clear(); 65193323Sed Memory.Reset(); 66193323Sed } 67193323Sed }; 68193323Sed} // end namespace llvm 69193323Sed 70193323Sed#endif 71