LLVM 17.0.0git
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"
19#include "llvm/IR/CFG.h"
21
22namespace 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
35private:
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] = pred_size(BB);
62 }
63
64public:
65 size_t size(BasicBlock *BB) const { return GetNumPreds(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
This file defines the BumpPtrAllocator interface.
This file defines the DenseMap class.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
iterator end()
Definition: DenseMap.h:84
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
void clear()
clear - Remove all information.
size_t size(BasicBlock *BB) const
ArrayRef< BasicBlock * > get(BasicBlock *BB)
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto predecessors(const MachineBasicBlock *BB)
unsigned pred_size(const MachineBasicBlock *BB)