136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- PredIteratorCache.h - pred_iterator Cache ----------------*- C++ -*-===// 2312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// 3312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// The LLVM Compiler Infrastructure 4312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// 5312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// This file is distributed under the University of Illinois Open Source 6312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// License. See LICENSE.TXT for details. 7312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// 8312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner//===----------------------------------------------------------------------===// 9312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// 10312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// This file defines the PredIteratorCache class. 11312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner// 12312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner//===----------------------------------------------------------------------===// 13312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner 14312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner#include "llvm/ADT/DenseMap.h" 15312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner#include "llvm/ADT/SmallVector.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 17255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/Allocator.h" 18312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_IR_PREDITERATORCACHE_H 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_IR_PREDITERATORCACHE_H 21723a59c17eecad082f0c734d29553a5d392c24b2Chris Lattner 22312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattnernamespace llvm { 23312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner 24312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// PredIteratorCache - This class is an extremely trivial cache for 25312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// predecessor iterator queries. This is useful for code that repeatedly 26312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// wants the predecessor list for the same blocks. 27312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner class PredIteratorCache { 28312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// BlockToPredsMap - Pointer to null-terminated list. 29312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner DenseMap<BasicBlock*, BasicBlock**> BlockToPredsMap; 30ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson DenseMap<BasicBlock*, unsigned> BlockToPredCountMap; 31312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner 32312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// Memory - This is the space that holds cached preds. 33312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner BumpPtrAllocator Memory; 34312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner public: 35fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 36312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// GetPreds - Get a cached list for the null-terminated predecessor list of 37312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// the specified block. This can be used in a loop like this: 38312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) 39312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// use(*PI); 40312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// instead of: 41312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 42312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner BasicBlock **GetPreds(BasicBlock *BB) { 43312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner BasicBlock **&Entry = BlockToPredsMap[BB]; 44312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner if (Entry) return Entry; 45fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 46312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner SmallVector<BasicBlock*, 32> PredCache(pred_begin(BB), pred_end(BB)); 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PredCache.push_back(nullptr); // null terminator. 48ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson 49ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson BlockToPredCountMap[BB] = PredCache.size()-1; 50fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 51312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner Entry = Memory.Allocate<BasicBlock*>(PredCache.size()); 52312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner std::copy(PredCache.begin(), PredCache.end(), Entry); 53312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner return Entry; 54312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner } 55ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson 56ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson unsigned GetNumPreds(BasicBlock *BB) { 57ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson GetPreds(BB); 58ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson return BlockToPredCountMap[BB]; 59ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson } 60fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 61312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner /// clear - Remove all information. 62312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner void clear() { 63312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner BlockToPredsMap.clear(); 64ddcb3415cb83a8df3cad5241cbfe46d261946a7bOwen Anderson BlockToPredCountMap.clear(); 65312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner Memory.Reset(); 66312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner } 67312b9a17e6e2af826f95722cbb4e31afaa9f2933Chris Lattner }; 680401245ab3c0da232322a0cca7edaeff93dd6ff3Chris Lattner} // end namespace llvm 690401245ab3c0da232322a0cca7edaeff93dd6ff3Chris Lattner 70723a59c17eecad082f0c734d29553a5d392c24b2Chris Lattner#endif 71