LLVM  14.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"
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] = pred_size(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
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::PredIteratorCache
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
Definition: PredIteratorCache.h:27
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Allocator.h
DenseMap.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PredIteratorCache::size
size_t size(BasicBlock *BB) const
Definition: PredIteratorCache.h:65
CFG.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::DenseMap
Definition: DenseMap.h:714
ArrayRef.h
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::sys::Memory
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
llvm::pred_size
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:124
llvm::PredIteratorCache::clear
void clear()
clear - Remove all information.
Definition: PredIteratorCache.h:71
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:474
SmallVector.h
llvm::PredIteratorCache::get
ArrayRef< BasicBlock * > get(BasicBlock *BB)
Definition: PredIteratorCache.h:66
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101