• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
163   /// Under Lazy Strategy, available trees will only be recalculated if there
164   /// are pending updates or there is BasicBlock awaiting deletion. Returns true
165   /// if at least one tree is recalculated.
166   bool recalculate(Function &F);
167 
168   /// Flush DomTree updates and return DomTree.
169   /// It also flush out of date updates applied by all available trees
170   /// and flush Deleted BBs if both trees are up-to-date.
171   /// It must only be called when it has a DomTree.
172   DominatorTree &getDomTree();
173 
174   /// Flush PostDomTree updates and return PostDomTree.
175   /// It also flush out of date updates applied by all available trees
176   /// and flush Deleted BBs if both trees are up-to-date.
177   /// It must only be called when it has a PostDomTree.
178   PostDominatorTree &getPostDomTree();
179 
180   /// Apply all pending updates to available trees and flush all BasicBlocks
181   /// awaiting deletion.
182   /// Does nothing under Eager UpdateStrategy.
183   void flush();
184 
185   /// Debug method to help view the internal state of this class.
186   LLVM_DUMP_METHOD void dump() const;
187 
188 private:
189   class CallBackOnDeletion final : public CallbackVH {
190   public:
CallBackOnDeletion(BasicBlock * V,std::function<void (BasicBlock *)> Callback)191     CallBackOnDeletion(BasicBlock *V,
192                        std::function<void(BasicBlock *)> Callback)
193         : CallbackVH(V), DelBB(V), Callback_(Callback) {}
194 
195   private:
196     BasicBlock *DelBB = nullptr;
197     std::function<void(BasicBlock *)> Callback_;
198 
deleted()199     void deleted() override {
200       Callback_(DelBB);
201       CallbackVH::deleted();
202     }
203   };
204 
205   SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
206   size_t PendDTUpdateIndex = 0;
207   size_t PendPDTUpdateIndex = 0;
208   DominatorTree *DT = nullptr;
209   PostDominatorTree *PDT = nullptr;
210   const UpdateStrategy Strategy;
211   SmallPtrSet<BasicBlock *, 8> DeletedBBs;
212   std::vector<CallBackOnDeletion> Callbacks;
213   bool IsRecalculatingDomTree = false;
214   bool IsRecalculatingPostDomTree = false;
215 
216   /// First remove all the instructions of DelBB and then make sure DelBB has a
217   /// valid terminator instruction which is necessary to have when DelBB still
218   /// has to be inside of its parent Function while awaiting deletion under Lazy
219   /// UpdateStrategy to prevent other routines from asserting the state of the
220   /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
221   void validateDeleteBB(BasicBlock *DelBB);
222 
223   /// Returns true if at least one BasicBlock is deleted.
224   bool forceFlushDeletedBB();
225 
226   /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
227   /// UpdateStrategy. Returns true if the update is queued for update.
228   bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
229                        BasicBlock *To);
230 
231   /// Helper function to apply all pending DomTree updates.
232   void applyDomTreeUpdates();
233 
234   /// Helper function to apply all pending PostDomTree updates.
235   void applyPostDomTreeUpdates();
236 
237   /// Helper function to flush deleted BasicBlocks if all available
238   /// trees are up-to-date.
239   void tryFlushDeletedBB();
240 
241   /// Drop all updates applied by all available trees and delete BasicBlocks if
242   /// all available trees are up-to-date.
243   void dropOutOfDateUpdates();
244 
245   /// Erase Basic Block node that has been unlinked from Function
246   /// in the DomTree and PostDomTree.
247   void eraseDelBBNode(BasicBlock *DelBB);
248 
249   /// Returns true if the update appears in the LLVM IR.
250   /// It is used to check whether an update is valid in
251   /// insertEdge/deleteEdge or is unnecessary in the batch update.
252   bool isUpdateValid(DominatorTree::UpdateType Update) const;
253 
254   /// Returns true if the update is self dominance.
255   bool isSelfDominance(DominatorTree::UpdateType Update) const;
256 };
257 } // namespace llvm
258 
259 #endif // LLVM_DOMTREEUPDATER_H
260