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