include/llvm/Analysis/DomTreeUpdater.h

   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_ANALYSIS_DOMTREEUPDATER_H
  15 #define LLVM_ANALYSIS_DOMTREEUPDATER_H
  16
  17 #include "llvm/Analysis/PostDominators.h"
  18 #include "llvm/IR/Dominators.h"
  19 #include "llvm/IR/Instructions.h"
  20 #include "llvm/IR/ValueHandle.h"
  21 #include "llvm/Support/GenericDomTree.h"
  22 #include <functional>
  23 #include <vector>
  24
  25 namespace llvm {
  26 class DomTreeUpdater {
  27 public:
  28   enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
  29
  30   explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
  31   DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
  32       : DT(&DT_), Strategy(Strategy_) {}
  33   DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
  34       : DT(DT_), Strategy(Strategy_) {}
  35   DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
  36       : PDT(&PDT_), Strategy(Strategy_) {}
  37   DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
  38       : PDT(PDT_), Strategy(Strategy_) {}
  39   DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
  40                  UpdateStrategy Strategy_)
  41       : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
  42   DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
  43                  UpdateStrategy Strategy_)
  44       : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
  45
  46   ~DomTreeUpdater() { flush(); }
  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   ///@{
  86   /// \name Mutation APIs
  87   ///
  88   /// These methods provide APIs for submitting updates to the DominatorTree and
  89   /// the PostDominatorTree.
  90   ///
  91   /// Note: There are two strategies to update the DominatorTree and the
  92   /// PostDominatorTree:
  93   /// 1. Eager UpdateStrategy: Updates are submitted and then flushed
  94   /// immediately.
  95   /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you
  96   /// explicitly call Flush APIs. It is recommended to use this update strategy
  97   /// when you submit a bunch of updates multiple times which can then
  98   /// add up to a large number of updates between two queries on the
  99   /// DominatorTree. The incremental updater can reschedule the updates or
 100   /// decide to recalculate the dominator tree in order to speedup the updating
 101   /// process depending on the number of updates.
 102   ///
 103   /// Although GenericDomTree provides several update primitives,
 104   /// it is not encouraged to use these APIs directly.
 105
 106   /// Submit updates to all available trees.
 107   /// The Eager Strategy flushes updates immediately while the Lazy Strategy
 108   /// queues the updates.
 109   ///
 110   /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
 111   /// in sync with + all updates before that single update.
 112   ///
 113   /// CAUTION!
 114   /// 1. It is required for the state of the LLVM IR to be updated
 115   /// *before* submitting the updates because the internal update routine will
 116   /// analyze the current state of the CFG to determine whether an update
 117   /// is valid.
 118   /// 2. It is illegal to submit any update that has already been submitted,
 119   /// i.e., you are supposed not to insert an existent edge or delete a
 120   /// nonexistent edge.
 121   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
 122
 123   /// Submit updates to all available trees. It will also
 124   /// 1. discard duplicated updates,
 125   /// 2. remove invalid updates. (Invalid updates means deletion of an edge that
 126   /// still exists or insertion of an edge that does not exist.)
 127   /// The Eager Strategy flushes updates immediately while the Lazy Strategy
 128   /// queues the updates.
 129   ///
 130   /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
 131   /// in sync with + all updates before that single update.
 132   ///
 133   /// CAUTION!
 134   /// 1. It is required for the state of the LLVM IR to be updated
 135   /// *before* submitting the updates because the internal update routine will
 136   /// analyze the current state of the CFG to determine whether an update
 137   /// is valid.
 138   /// 2. It is illegal to submit any update that has already been submitted,
 139   /// i.e., you are supposed not to insert an existent edge or delete a
 140   /// nonexistent edge.
 141   /// 3. It is only legal to submit updates to an edge in the order CFG changes
 142   /// are made. The order you submit updates on different edges is not
 143   /// restricted.
 144   void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates);
 145
 146   /// Notify DTU that the entry block was replaced.
 147   /// Recalculate all available trees and flush all BasicBlocks
 148   /// awaiting deletion immediately.
 149   void recalculate(Function &F);
 150
 151   /// \deprecated { Submit an edge insertion to all available trees. The Eager
 152   /// Strategy flushes this update immediately while the Lazy Strategy queues
 153   /// the update. An internal function checks if the edge exists in the CFG in
 154   /// DEBUG mode. CAUTION! This function has to be called *after* making the
 155   /// update on the actual CFG. It is illegal to submit any update that has
 156   /// already been applied. }
 157   LLVM_ATTRIBUTE_DEPRECATED(void insertEdge(BasicBlock *From, BasicBlock *To),
 158                             "Use applyUpdates() instead.");
 159
 160   /// \deprecated {Submit an edge insertion to all available trees.
 161   /// Under either Strategy, an invalid update will be discard silently.
 162   /// Invalid update means inserting an edge that does not exist in the CFG.
 163   /// The Eager Strategy flushes this update immediately while the Lazy Strategy
 164   /// queues the update. It is only recommended to use this method when you
 165   /// want to discard an invalid update.
 166   /// CAUTION! It is illegal to submit any update that has already been
 167   /// submitted. }
 168   LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From,
 169                                                    BasicBlock *To),
 170                             "Use applyUpdatesPermissive() instead.");
 171
 172   /// \deprecated { Submit an edge deletion to all available trees. The Eager
 173   /// Strategy flushes this update immediately while the Lazy Strategy queues
 174   /// the update. An internal function checks if the edge doesn't exist in the
 175   /// CFG in DEBUG mode.
 176   /// CAUTION! This function has to be called *after* making the update on the
 177   /// actual CFG. It is illegal to submit any update that has already been
 178   /// submitted. }
 179   LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To),
 180                             "Use applyUpdates() instead.");
 181
 182   /// \deprecated { Submit an edge deletion to all available trees.
 183   /// Under either Strategy, an invalid update will be discard silently.
 184   /// Invalid update means deleting an edge that exists in the CFG.
 185   /// The Eager Strategy flushes this update immediately while the Lazy Strategy
 186   /// queues the update. It is only recommended to use this method when you
 187   /// want to discard an invalid update.
 188   /// CAUTION! It is illegal to submit any update that has already been
 189   /// submitted. }
 190   LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From,
 191                                                    BasicBlock *To),
 192                             "Use applyUpdatesPermissive() instead.");
 193
 194   /// Delete DelBB. DelBB will be removed from its Parent and
 195   /// erased from available trees if it exists and finally get deleted.
 196   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
 197   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
 198   /// all available trees are up-to-date. Assert if any instruction of DelBB is
 199   /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
 200   /// will be queued until flush() is called.
 201   void deleteBB(BasicBlock *DelBB);
 202
 203   /// Delete DelBB. DelBB will be removed from its Parent and
 204   /// erased from available trees if it exists. Then the callback will
 205   /// be called. Finally, DelBB will be deleted.
 206   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
 207   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
 208   /// all available trees are up-to-date. Assert if any instruction of DelBB is
 209   /// modified while awaiting deletion. Multiple callbacks can be queued for one
 210   /// DelBB under Lazy UpdateStrategy.
 211   void callbackDeleteBB(BasicBlock *DelBB,
 212                         std::function<void(BasicBlock *)> Callback);
 213
 214   ///@}
 215
 216   ///@{
 217   /// \name Flush APIs
 218   ///
 219   /// CAUTION! By the moment these flush APIs are called, the current CFG needs
 220   /// to be the same as the CFG which DTU is in sync with + all updates
 221   /// submitted.
 222
 223   /// Flush DomTree updates and return DomTree.
 224   /// It flushes Deleted BBs if both trees are up-to-date.
 225   /// It must only be called when it has a DomTree.
 226   DominatorTree &getDomTree();
 227
 228   /// Flush PostDomTree updates and return PostDomTree.
 229   /// It flushes Deleted BBs if both trees are up-to-date.
 230   /// It must only be called when it has a PostDomTree.
 231   PostDominatorTree &getPostDomTree();
 232
 233   /// Apply all pending updates to available trees and flush all BasicBlocks
 234   /// awaiting deletion.
 235
 236   void flush();
 237
 238   ///@}
 239
 240   /// Debug method to help view the internal state of this class.
 241   LLVM_DUMP_METHOD void dump() const;
 242
 243 private:
 244   class CallBackOnDeletion final : public CallbackVH {
 245   public:
 246     CallBackOnDeletion(BasicBlock *V,
 247                        std::function<void(BasicBlock *)> Callback)
 248         : CallbackVH(V), DelBB(V), Callback_(Callback) {}
 249
 250   private:
 251     BasicBlock *DelBB = nullptr;
 252     std::function<void(BasicBlock *)> Callback_;
 253
 254     void deleted() override {
 255       Callback_(DelBB);
 256       CallbackVH::deleted();
 257     }
 258   };
 259
 260   SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
 261   size_t PendDTUpdateIndex = 0;
 262   size_t PendPDTUpdateIndex = 0;
 263   DominatorTree *DT = nullptr;
 264   PostDominatorTree *PDT = nullptr;
 265   const UpdateStrategy Strategy;
 266   SmallPtrSet<BasicBlock *, 8> DeletedBBs;
 267   std::vector<CallBackOnDeletion> Callbacks;
 268   bool IsRecalculatingDomTree = false;
 269   bool IsRecalculatingPostDomTree = false;
 270
 271   /// First remove all the instructions of DelBB and then make sure DelBB has a
 272   /// valid terminator instruction which is necessary to have when DelBB still
 273   /// has to be inside of its parent Function while awaiting deletion under Lazy
 274   /// UpdateStrategy to prevent other routines from asserting the state of the
 275   /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
 276   void validateDeleteBB(BasicBlock *DelBB);
 277
 278   /// Returns true if at least one BasicBlock is deleted.
 279   bool forceFlushDeletedBB();
 280
 281   /// Helper function to apply all pending DomTree updates.
 282   void applyDomTreeUpdates();
 283
 284   /// Helper function to apply all pending PostDomTree updates.
 285   void applyPostDomTreeUpdates();
 286
 287   /// Helper function to flush deleted BasicBlocks if all available
 288   /// trees are up-to-date.
 289   void tryFlushDeletedBB();
 290
 291   /// Drop all updates applied by all available trees and delete BasicBlocks if
 292   /// all available trees are up-to-date.
 293   void dropOutOfDateUpdates();
 294
 295   /// Erase Basic Block node that has been unlinked from Function
 296   /// in the DomTree and PostDomTree.
 297   void eraseDelBBNode(BasicBlock *DelBB);
 298
 299   /// Returns true if the update appears in the LLVM IR.
 300   /// It is used to check whether an update is valid in
 301   /// insertEdge/deleteEdge or is unnecessary in the batch update.
 302   bool isUpdateValid(DominatorTree::UpdateType Update) const;
 303
 304   /// Returns true if the update is self dominance.
 305   bool isSelfDominance(DominatorTree::UpdateType Update) const;
 306 };
 307 } // namespace llvm
 308
 309 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H