LLVM  9.0.0svn
DomTreeUpdater.h
Go to the documentation of this file.
1 //===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- 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 DomTreeUpdater class, which provides a uniform way to
10 // update dominator tree related data structures.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_DOMTREEUPDATER_H
15 #define LLVM_DOMTREEUPDATER_H
16 
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/ValueHandle.h"
22 #include <functional>
23 #include <vector>
24 
25 namespace llvm {
27 public:
28  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
29 
30  explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
32  : DT(&DT_), Strategy(Strategy_) {}
34  : DT(DT_), Strategy(Strategy_) {}
36  : PDT(&PDT_), Strategy(Strategy_) {}
38  : PDT(PDT_), Strategy(Strategy_) {}
40  UpdateStrategy Strategy_)
41  : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
43  UpdateStrategy Strategy_)
44  : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
45 
47 
48  /// Returns true if the current strategy is Lazy.
49  bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };
50 
51  /// Returns true if the current strategy is Eager.
52  bool isEager() const { return Strategy == UpdateStrategy::Eager; };
53 
54  /// Returns true if it holds a DominatorTree.
55  bool hasDomTree() const { return DT != nullptr; }
56 
57  /// Returns true if it holds a PostDominatorTree.
58  bool hasPostDomTree() const { return PDT != nullptr; }
59 
60  /// Returns true if there is BasicBlock awaiting deletion.
61  /// The deletion will only happen until a flush event and
62  /// all available trees are up-to-date.
63  /// Returns false under Eager UpdateStrategy.
64  bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }
65 
66  /// Returns true if DelBB is awaiting deletion.
67  /// Returns false under Eager UpdateStrategy.
68  bool isBBPendingDeletion(BasicBlock *DelBB) const;
69 
70  /// Returns true if either of DT or PDT is valid and the tree has at
71  /// least one update pending. If DT or PDT is nullptr it is treated
72  /// as having no pending updates. This function does not check
73  /// whether there is BasicBlock awaiting deletion.
74  /// Returns false under Eager UpdateStrategy.
75  bool hasPendingUpdates() const;
76 
77  /// Returns true if there are DominatorTree updates queued.
78  /// Returns false under Eager UpdateStrategy or DT is nullptr.
79  bool hasPendingDomTreeUpdates() const;
80 
81  /// Returns true if there are PostDominatorTree updates queued.
82  /// Returns false under Eager UpdateStrategy or PDT is nullptr.
83  bool hasPendingPostDomTreeUpdates() const;
84 
85  /// Apply updates on all available trees. Under Eager UpdateStrategy with
86  /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
87  /// discard duplicated updates and self-dominance updates. If both DT and PDT
88  /// are nullptrs, this function discards all updates. The Eager Strategy
89  /// applies the updates immediately while the Lazy Strategy queues the
90  /// updates. It is required for the state of the LLVM IR to be updated
91  /// *before* applying the Updates because the internal update routine will
92  /// analyze the current state of the relationship between a pair of (From, To)
93  /// BasicBlocks to determine whether a single update needs to be discarded.
95  bool ForceRemoveDuplicates = false);
96 
97  /// Notify all available trees on an edge insertion. If both DT and PDT are
98  /// nullptrs, this function discards the update. Under either Strategy,
99  /// self-dominance update will be removed. The Eager Strategy applies
100  /// the update immediately while the Lazy Strategy queues the update.
101  /// It is recommended to only use this method when you have exactly one
102  /// insertion (and no deletions). It is recommended to use applyUpdates() in
103  /// all other cases. This function has to be called *after* making the update
104  /// on the actual CFG. An internal functions checks if the edge exists in the
105  /// CFG in DEBUG mode.
106  void insertEdge(BasicBlock *From, BasicBlock *To);
107 
108  /// Notify all available trees on an edge insertion.
109  /// Under either Strategy, the following updates will be discard silently
110  /// 1. Invalid - Inserting an edge that does not exist in the CFG.
111  /// 2. Self-dominance update.
112  /// 3. Both DT and PDT are nullptrs.
113  /// The Eager Strategy applies the update immediately while the Lazy Strategy
114  /// queues the update. It is recommended to only use this method when you have
115  /// exactly one insertion (and no deletions) and want to discard an invalid
116  /// update.
117  void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
118 
119  /// Notify all available trees on an edge deletion. If both DT and PDT are
120  /// nullptrs, this function discards the update. Under either Strategy,
121  /// self-dominance update will be removed. The Eager Strategy applies
122  /// the update immediately while the Lazy Strategy queues the update.
123  /// It is recommended to only use this method when you have exactly one
124  /// deletion (and no insertions). It is recommended to use applyUpdates() in
125  /// all other cases. This function has to be called *after* making the update
126  /// on the actual CFG. An internal functions checks if the edge doesn't exist
127  /// in the CFG in DEBUG mode.
128  void deleteEdge(BasicBlock *From, BasicBlock *To);
129 
130  /// Notify all available trees on an edge deletion.
131  /// Under either Strategy, the following updates will be discard silently
132  /// 1. Invalid - Deleting an edge that still exists in the CFG.
133  /// 2. Self-dominance update.
134  /// 3. Both DT and PDT are nullptrs.
135  /// The Eager Strategy applies the update immediately while the Lazy Strategy
136  /// queues the update. It is recommended to only use this method when you have
137  /// exactly one deletion (and no insertions) and want to discard an invalid
138  /// update.
139  void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
140 
141  /// Delete DelBB. DelBB will be removed from its Parent and
142  /// erased from available trees if it exists and finally get deleted.
143  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
144  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
145  /// all available trees are up-to-date. Assert if any instruction of DelBB is
146  /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
147  /// will be queued until flush() is called.
148  void deleteBB(BasicBlock *DelBB);
149 
150  /// Delete DelBB. DelBB will be removed from its Parent and
151  /// erased from available trees if it exists. Then the callback will
152  /// be called. Finally, DelBB will be deleted.
153  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
154  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
155  /// all available trees are up-to-date. Assert if any instruction of DelBB is
156  /// modified while awaiting deletion. Multiple callbacks can be queued for one
157  /// DelBB under Lazy UpdateStrategy.
158  void callbackDeleteBB(BasicBlock *DelBB,
159  std::function<void(BasicBlock *)> Callback);
160 
161  /// Recalculate all available trees and flush all BasicBlocks
162  /// awaiting deletion immediately.
163  void recalculate(Function &F);
164 
165  /// Flush DomTree updates and return DomTree.
166  /// It also flush out of date updates applied by all available trees
167  /// and flush Deleted BBs if both trees are up-to-date.
168  /// It must only be called when it has a DomTree.
170 
171  /// Flush PostDomTree updates and return PostDomTree.
172  /// It also flush out of date updates applied by all available trees
173  /// and flush Deleted BBs if both trees are up-to-date.
174  /// It must only be called when it has a PostDomTree.
176 
177  /// Apply all pending updates to available trees and flush all BasicBlocks
178  /// awaiting deletion.
179  /// Does nothing under Eager UpdateStrategy.
180  void flush();
181 
182  /// Debug method to help view the internal state of this class.
183  LLVM_DUMP_METHOD void dump() const;
184 
185 private:
186  class CallBackOnDeletion final : public CallbackVH {
187  public:
188  CallBackOnDeletion(BasicBlock *V,
189  std::function<void(BasicBlock *)> Callback)
190  : CallbackVH(V), DelBB(V), Callback_(Callback) {}
191 
192  private:
193  BasicBlock *DelBB = nullptr;
194  std::function<void(BasicBlock *)> Callback_;
195 
196  void deleted() override {
197  Callback_(DelBB);
199  }
200  };
201 
203  size_t PendDTUpdateIndex = 0;
204  size_t PendPDTUpdateIndex = 0;
205  DominatorTree *DT = nullptr;
206  PostDominatorTree *PDT = nullptr;
207  const UpdateStrategy Strategy;
208  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
209  std::vector<CallBackOnDeletion> Callbacks;
210  bool IsRecalculatingDomTree = false;
211  bool IsRecalculatingPostDomTree = false;
212 
213  /// First remove all the instructions of DelBB and then make sure DelBB has a
214  /// valid terminator instruction which is necessary to have when DelBB still
215  /// has to be inside of its parent Function while awaiting deletion under Lazy
216  /// UpdateStrategy to prevent other routines from asserting the state of the
217  /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
218  void validateDeleteBB(BasicBlock *DelBB);
219 
220  /// Returns true if at least one BasicBlock is deleted.
221  bool forceFlushDeletedBB();
222 
223  /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
224  /// UpdateStrategy. Returns true if the update is queued for update.
225  bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
226  BasicBlock *To);
227 
228  /// Helper function to apply all pending DomTree updates.
229  void applyDomTreeUpdates();
230 
231  /// Helper function to apply all pending PostDomTree updates.
232  void applyPostDomTreeUpdates();
233 
234  /// Helper function to flush deleted BasicBlocks if all available
235  /// trees are up-to-date.
236  void tryFlushDeletedBB();
237 
238  /// Drop all updates applied by all available trees and delete BasicBlocks if
239  /// all available trees are up-to-date.
240  void dropOutOfDateUpdates();
241 
242  /// Erase Basic Block node that has been unlinked from Function
243  /// in the DomTree and PostDomTree.
244  void eraseDelBBNode(BasicBlock *DelBB);
245 
246  /// Returns true if the update appears in the LLVM IR.
247  /// It is used to check whether an update is valid in
248  /// insertEdge/deleteEdge or is unnecessary in the batch update.
249  bool isUpdateValid(DominatorTree::UpdateType Update) const;
250 
251  /// Returns true if the update is self dominance.
252  bool isSelfDominance(DominatorTree::UpdateType Update) const;
253 };
254 } // namespace llvm
255 
256 #endif // LLVM_DOMTREEUPDATER_H
DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:464
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
bool hasPostDomTree() const
Returns true if it holds a PostDominatorTree.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
F(f)
bool isLazy() const
Returns true if the current strategy is Lazy.
DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, UpdateStrategy Strategy_)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, UpdateStrategy Strategy_)
bool isEager() const
Returns true if the current strategy is Eager.
virtual void deleted()
Callback for Value destruction.
Definition: ValueHandle.h:409
void deleteEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
bool hasPendingDeletedBB() const
Returns true if there is BasicBlock awaiting deletion.
void insertEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge insertion.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending...
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates, bool ForceRemoveDuplicates=false)
Apply updates on all available trees.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
void recalculate(Function &F)
Recalculate all available trees and flush all BasicBlocks awaiting deletion immediately.
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge insertion.
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
const unsigned Kind
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
print Print MemDeps of function
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
DomTreeUpdater(UpdateStrategy Strategy_)
bool hasDomTree() const
Returns true if it holds a DominatorTree.