contrib/llvm/include/llvm/IR/DomTreeUpdater.h

   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
  31   explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
  32   DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
  33       : DT(&DT_), Strategy(Strategy_) {}
  34   DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
  35       : DT(DT_), Strategy(Strategy_) {}
  36   DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
  37       : PDT(&PDT_), Strategy(Strategy_) {}
  38   DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
  39       : PDT(PDT_), Strategy(Strategy_) {}
  40   DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
  41                  UpdateStrategy Strategy_)
  42       : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
  43   DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
  44                  UpdateStrategy Strategy_)
  45       : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
  46
  47   ~DomTreeUpdater() { flush(); }
  48
  49   /// Returns true if the current strategy is Lazy.
  50   bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };
  51
  52   /// Returns true if the current strategy is Eager.
  53   bool isEager() const { return Strategy == UpdateStrategy::Eager; };
  54
  55   /// Returns true if it holds a DominatorTree.
  56   bool hasDomTree() const { return DT != nullptr; }
  57
  58   /// Returns true if it holds a PostDominatorTree.
  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.
  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:
 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
 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