LLVM  10.0.0svn
PredIteratorCache.h
Go to the documentation of this file.
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.
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.
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 
48  PredCache.push_back(nullptr); // null terminator.
49 
50  BlockToPredCountMap[BB] = PredCache.size() - 1;
51 
52  Entry = Memory.Allocate<BasicBlock *>(PredCache.size());
53  std::copy(PredCache.begin(), PredCache.end(), Entry);
54  return Entry;
55  }
56 
57  unsigned GetNumPreds(BasicBlock *BB) const {
58  auto Result = BlockToPredCountMap.find(BB);
59  if (Result != BlockToPredCountMap.end())
60  return Result->second;
61  return BlockToPredCountMap[BB] = std::distance(pred_begin(BB), pred_end(BB));
62  }
63 
64 public:
65  size_t size(BasicBlock *BB) const { return GetNumPreds(BB); }
67  return makeArrayRef(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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This class provides various memory handling functions that manipulate MemoryBlock instances...
Definition: Memory.h:53
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:195
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
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:32
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
size_t size(BasicBlock *BB) const
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:112
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
size_t size() const
Definition: SmallVector.h:52
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:837
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:215
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iterator end()
Definition: DenseMap.h:82
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1217