]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/include/llvm/IR/PredIteratorCache.h
Merge llvm, clang, lld, lldb, compiler-rt and libc++ r305575, and update
[FreeBSD/FreeBSD.git] / contrib / llvm / include / llvm / IR / PredIteratorCache.h
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   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) const {
59     auto Result = BlockToPredCountMap.find(BB);
60     if (Result != BlockToPredCountMap.end())
61       return Result->second;
62     return BlockToPredCountMap[BB] = std::distance(pred_begin(BB), pred_end(BB));
63   }
64
65 public:
66   size_t size(BasicBlock *BB) const { return GetNumPreds(BB); }
67   ArrayRef<BasicBlock *> get(BasicBlock *BB) {
68     return makeArrayRef(GetPreds(BB), GetNumPreds(BB));
69   }
70
71   /// clear - Remove all information.
72   void clear() {
73     BlockToPredsMap.clear();
74     BlockToPredCountMap.clear();
75     Memory.Reset();
76   }
77 };
78
79 } // end namespace llvm
80
81 #endif