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