1 | //===- PredIteratorCache.h - pred_iterator Cache ----------------*- C++ -*-===// |
---|---|
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines the PredIteratorCache class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_IR_PREDITERATORCACHE_H |
14 | #define LLVM_IR_PREDITERATORCACHE_H |
15 | |
16 | #include "llvm/ADT/ArrayRef.h" |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/SmallVector.h" |
19 | #include "llvm/IR/CFG.h" |
20 | #include "llvm/Support/Allocator.h" |
21 | |
22 | namespace 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 | mutable DenseMap<BasicBlock *, BasicBlock **> BlockToPredsMap; |
30 | mutable DenseMap<BasicBlock *, unsigned> BlockToPredCountMap; |
31 | |
32 | /// Memory - This is the space that holds cached preds. |
33 | BumpPtrAllocator Memory; |
34 | |
35 | private: |
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) |
45 | return Entry; |
46 | |
47 | SmallVector<BasicBlock *, 32> PredCache(predecessors(BB)); |
48 | PredCache.push_back(Elt: nullptr); // null terminator. |
49 | |
50 | BlockToPredCountMap[BB] = PredCache.size() - 1; |
51 | |
52 | Entry = Memory.Allocate<BasicBlock *>(Num: PredCache.size()); |
53 | std::copy(first: PredCache.begin(), last: PredCache.end(), result: Entry); |
54 | return Entry; |
55 | } |
56 | |
57 | unsigned GetNumPreds(BasicBlock *BB) const { |
58 | auto Result = BlockToPredCountMap.find(Val: BB); |
59 | if (Result != BlockToPredCountMap.end()) |
60 | return Result->second; |
61 | return BlockToPredCountMap[BB] = pred_size(BB); |
62 | } |
63 | |
64 | public: |
65 | size_t size(BasicBlock *BB) const { return GetNumPreds(BB); } |
66 | ArrayRef<BasicBlock *> get(BasicBlock *BB) { |
67 | return ArrayRef(GetPreds(BB), GetNumPreds(BB)); |
68 | } |
69 | |
70 | /// clear - Remove all information. |
71 | void clear() { |
72 | BlockToPredsMap.clear(); |
73 | BlockToPredCountMap.clear(); |
74 | Memory.Reset(); |
75 | } |
76 | }; |
77 | |
78 | } // end namespace llvm |
79 | |
80 | #endif |
81 |