LLVM  6.0.0svn
PredIteratorCache.h
Go to the documentation of this file.
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.
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.
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 
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); }
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
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
This class provides various memory handling functions that manipulate MemoryBlock instances...
Definition: Memory.h:46
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it...
Definition: Allocator.h:192
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
size_t size(BasicBlock *BB) const
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:212
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
void clear()
clear - Remove all information.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
iterator end()
Definition: DenseMap.h:79