Index: llvm/include/llvm/Analysis/DomTreeUpdater.h =================================================================== --- llvm/include/llvm/Analysis/DomTreeUpdater.h +++ llvm/include/llvm/Analysis/DomTreeUpdater.h @@ -82,15 +82,49 @@ /// Returns false under Eager UpdateStrategy or PDT is nullptr. bool hasPendingPostDomTreeUpdates() const; + ///@{ + /// \name Mutation API + /// + /// These methods provide the core API for updating the DominatorTree and + /// the PostDominatorTree. + /// + /// Note: There are four ways to update the DominatorTree: + /// 1. via the DomTreeUpdater class: + /// a. Eager UpdateStrategy: It is a bare wrapper of the incremental updater + /// of the DominatorTree class. + /// b. Lazy UpdateStrategy: It is recommended to use this update strategy + /// when you submit a bunch of updates multiple times which can then + /// add up to a large number of updates between two queries on the + /// DominatorTree. The incremental updater can reschedule the updates or + /// decide to recalculate the dominator tree in order to speedup the updating + /// process depending on the number of updates. + /// 2. via the DominatorTree class: + /// a. incremental updater APIs in the DominatorTree class: It is always *not* + /// encouraged to use these APIs directly. You should use DomTreeUpdater for + /// more convenient preservation of both DomTree and PostDomTree in + /// transformations. + /// b. low-level APIs in the DominatorTree class: These APIs are more + /// error-prone but is typically faster than the incremental updater when you + /// do trivial modifications to the DominatorTree and then query it + /// immediately in a tight loop. In this case, using the incremental updater + /// can involve graph searching which can slow down the update. It is always + /// recommended to use the incremental updater if the performance influence is + /// acceptable. + /// Apply updates on all available trees. Under Eager UpdateStrategy with /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will /// discard duplicated updates and self-dominance updates. If both DT and PDT /// are nullptrs, this function discards all updates. The Eager Strategy /// applies the updates immediately while the Lazy Strategy queues the - /// updates. It is required for the state of the LLVM IR to be updated + /// updates. + /// + /// CAUTION! + /// 1. It is required for the state of the LLVM IR to be updated /// *before* applying the Updates because the internal update routine will /// analyze the current state of the relationship between a pair of (From, To) /// BasicBlocks to determine whether a single update needs to be discarded. + /// 2. It is illegal to submit any (From, To) pair that the DomTreeUpdater + /// or the DominatorTree already acknowledged. void applyUpdates(ArrayRef Updates, bool ForceRemoveDuplicates = false); @@ -98,11 +132,12 @@ /// nullptrs, this function discards the update. Under either Strategy, /// self-dominance update will be removed. The Eager Strategy applies /// the update immediately while the Lazy Strategy queues the update. - /// It is recommended to only use this method when you have exactly one - /// insertion (and no deletions). It is recommended to use applyUpdates() in - /// all other cases. This function has to be called *after* making the update - /// on the actual CFG. An internal functions checks if the edge exists in the + /// An internal functions checks if the edge exists in the /// CFG in DEBUG mode. + /// CAUTION! It is only legal to use this method when you have exactly one + /// insertion (and no deletions). This function has to be called *after* + /// making the update on the actual CFG. It is illegal to submit any + /// update that the DomTreeUpdater or the DominatorTree already acknowledged. void insertEdge(BasicBlock *From, BasicBlock *To); /// Notify all available trees on an edge insertion. @@ -111,20 +146,23 @@ /// 2. Self-dominance update. /// 3. Both DT and PDT are nullptrs. /// The Eager Strategy applies the update immediately while the Lazy Strategy - /// queues the update. It is recommended to only use this method when you have - /// exactly one insertion (and no deletions) and want to discard an invalid - /// update. + /// queues the update. It is only recommended to use this method when you + /// want to discard an invalid update. + /// CAUTION! It is only legal to use this method when you have exactly one + /// insertion (and no deletions). It is illegal to submit any + /// update that the DomTreeUpdater or the DominatorTree already acknowledged. void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To); /// Notify all available trees on an edge deletion. If both DT and PDT are /// nullptrs, this function discards the update. Under either Strategy, /// self-dominance update will be removed. The Eager Strategy applies /// the update immediately while the Lazy Strategy queues the update. - /// It is recommended to only use this method when you have exactly one - /// deletion (and no insertions). It is recommended to use applyUpdates() in - /// all other cases. This function has to be called *after* making the update - /// on the actual CFG. An internal functions checks if the edge doesn't exist + /// An internal functions checks if the edge doesn't exist /// in the CFG in DEBUG mode. + /// CAUTION! It is only legal to use this method when you have exactly one + /// deletion (and no insertions). This function has to be called *after* + /// making the update on the actual CFG. It is illegal to submit any + /// update that the DomTreeUpdater or the DominatorTree already acknowledged. void deleteEdge(BasicBlock *From, BasicBlock *To); /// Notify all available trees on an edge deletion. @@ -133,9 +171,11 @@ /// 2. Self-dominance update. /// 3. Both DT and PDT are nullptrs. /// The Eager Strategy applies the update immediately while the Lazy Strategy - /// queues the update. It is recommended to only use this method when you have - /// exactly one deletion (and no insertions) and want to discard an invalid - /// update. + /// queues the update. It is only recommended to use this method when you + /// want to discard an invalid update. + /// CAUTION! It is only legal to use this method when you have exactly one + /// deletion (and no insertions). It is illegal to submit any + /// update that the DomTreeUpdater or the DominatorTree already acknowledged. void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To); /// Delete DelBB. DelBB will be removed from its Parent and @@ -162,6 +202,13 @@ /// awaiting deletion immediately. void recalculate(Function &F); + /// Apply all pending updates to available trees and flush all BasicBlocks + /// awaiting deletion. + /// Does nothing under Eager UpdateStrategy. + void flush(); + + ///@} + /// Flush DomTree updates and return DomTree. /// It also flush out of date updates applied by all available trees /// and flush Deleted BBs if both trees are up-to-date. @@ -174,11 +221,6 @@ /// It must only be called when it has a PostDomTree. PostDominatorTree &getPostDomTree(); - /// Apply all pending updates to available trees and flush all BasicBlocks - /// awaiting deletion. - /// Does nothing under Eager UpdateStrategy. - void flush(); - /// Debug method to help view the internal state of this class. LLVM_DUMP_METHOD void dump() const;