/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/IR/PredIteratorCache.h
Line | Count | Source |
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 | | |
23 | | namespace 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. |
28 | | class PredIteratorCache { |
29 | | /// BlockToPredsMap - Pointer to null-terminated list. |
30 | | mutable DenseMap<BasicBlock *, BasicBlock **> BlockToPredsMap; |
31 | | mutable DenseMap<BasicBlock *, unsigned> BlockToPredCountMap; |
32 | | |
33 | | /// Memory - This is the space that holds cached preds. |
34 | | BumpPtrAllocator Memory; |
35 | | |
36 | | private: |
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 | 18.8M | BasicBlock **GetPreds(BasicBlock *BB) { |
44 | 18.8M | BasicBlock **&Entry = BlockToPredsMap[BB]; |
45 | 18.8M | if (Entry) |
46 | 15.8M | return Entry; |
47 | 18.8M | |
48 | 3.01M | SmallVector<BasicBlock *, 32> PredCache(pred_begin(BB), pred_end(BB)); |
49 | 3.01M | PredCache.push_back(nullptr); // null terminator. |
50 | 3.01M | |
51 | 3.01M | BlockToPredCountMap[BB] = PredCache.size() - 1; |
52 | 3.01M | |
53 | 3.01M | Entry = Memory.Allocate<BasicBlock *>(PredCache.size()); |
54 | 3.01M | std::copy(PredCache.begin(), PredCache.end(), Entry); |
55 | 3.01M | return Entry; |
56 | 18.8M | } |
57 | | |
58 | 20.3M | unsigned GetNumPreds(BasicBlock *BB) const { |
59 | 20.3M | auto Result = BlockToPredCountMap.find(BB); |
60 | 20.3M | if (Result != BlockToPredCountMap.end()) |
61 | 19.2M | return Result->second; |
62 | 1.02M | return BlockToPredCountMap[BB] = std::distance(pred_begin(BB), pred_end(BB)); |
63 | 20.3M | } |
64 | | |
65 | | public: |
66 | 1.44M | size_t size(BasicBlock *BB) const { return GetNumPreds(BB); } |
67 | 18.8M | ArrayRef<BasicBlock *> get(BasicBlock *BB) { |
68 | 18.8M | return makeArrayRef(GetPreds(BB), GetNumPreds(BB)); |
69 | 18.8M | } |
70 | | |
71 | | /// clear - Remove all information. |
72 | 62.8k | void clear() { |
73 | 62.8k | BlockToPredsMap.clear(); |
74 | 62.8k | BlockToPredCountMap.clear(); |
75 | 62.8k | Memory.Reset(); |
76 | 62.8k | } |
77 | | }; |
78 | | |
79 | | } // end namespace llvm |
80 | | |
81 | | #endif |