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#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/IR/CFG.h"
17#include "llvm/Support/Allocator.h"
18
19#ifndef LLVM_IR_PREDITERATORCACHE_H
20#define LLVM_IR_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(nullptr); // 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