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   /// Apply updates on all available trees. Under Eager UpdateStrategy with
  86   /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
  87   /// discard duplicated updates and self-dominance updates. If both DT and PDT
  88   /// are nullptrs, this function discards all updates. The Eager Strategy
  89   /// applies the updates immediately while the Lazy Strategy queues the
  90   /// updates. It is required for the state of the LLVM IR to be updated
  91   /// *before* applying the Updates because the internal update routine will
  92   /// analyze the current state of the relationship between a pair of (From, To)
  93   /// BasicBlocks to determine whether a single update needs to be discarded.
  94   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
  95                     bool ForceRemoveDuplicates = false);
  96
  97   /// Notify all available trees on an edge insertion. If both DT and PDT are
  98   /// nullptrs, this function discards the update. Under either Strategy,
  99   /// self-dominance update will be removed. The Eager Strategy applies
 100   /// the update immediately while the Lazy Strategy queues the update.
 101   /// It is recommended to only use this method when you have exactly one
 102   /// insertion (and no deletions). It is recommended to use applyUpdates() in
 103   /// all other cases. This function has to be called *after* making the update
 104   /// on the actual CFG. An internal functions checks if the edge exists in the
 105   /// CFG in DEBUG mode.
 106   void insertEdge(BasicBlock *From, BasicBlock *To);
 107
 108   /// Notify all available trees on an edge insertion.
 109   /// Under either Strategy, the following updates will be discard silently
 110   /// 1. Invalid - Inserting an edge that does not exist in the CFG.
 111   /// 2. Self-dominance update.
 112   /// 3. Both DT and PDT are nullptrs.
 113   /// The Eager Strategy applies the update immediately while the Lazy Strategy
 114   /// queues the update. It is recommended to only use this method when you have
 115   /// exactly one insertion (and no deletions) and want to discard an invalid
 116   /// update.
 117   void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
 118
 119   /// Notify all available trees on an edge deletion. If both DT and PDT are
 120   /// nullptrs, this function discards the update. Under either Strategy,
 121   /// self-dominance update will be removed. The Eager Strategy applies
 122   /// the update immediately while the Lazy Strategy queues the update.
 123   /// It is recommended to only use this method when you have exactly one
 124   /// deletion (and no insertions). It is recommended to use applyUpdates() in
 125   /// all other cases. This function has to be called *after* making the update
 126   /// on the actual CFG. An internal functions checks if the edge doesn't exist
 127   /// in the CFG in DEBUG mode.
 128   void deleteEdge(BasicBlock *From, BasicBlock *To);
 129
 130   /// Notify all available trees on an edge deletion.
 131   /// Under either Strategy, the following updates will be discard silently
 132   /// 1. Invalid - Deleting an edge that still exists in the CFG.
 133   /// 2. Self-dominance update.
 134   /// 3. Both DT and PDT are nullptrs.
 135   /// The Eager Strategy applies the update immediately while the Lazy Strategy
 136   /// queues the update. It is recommended to only use this method when you have
 137   /// exactly one deletion (and no insertions) and want to discard an invalid
 138   /// update.
 139   void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
 140
 141   /// Delete DelBB. DelBB will be removed from its Parent and
 142   /// erased from available trees if it exists and finally get deleted.
 143   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
 144   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
 145   /// all available trees are up-to-date. Assert if any instruction of DelBB is
 146   /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
 147   /// will be queued until flush() is called.
 148   void deleteBB(BasicBlock *DelBB);
 149
 150   /// Delete DelBB. DelBB will be removed from its Parent and
 151   /// erased from available trees if it exists. Then the callback will
 152   /// be called. Finally, DelBB will be deleted.
 153   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
 154   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
 155   /// all available trees are up-to-date. Assert if any instruction of DelBB is
 156   /// modified while awaiting deletion. Multiple callbacks can be queued for one
 157   /// DelBB under Lazy UpdateStrategy.
 158   void callbackDeleteBB(BasicBlock *DelBB,
 159                         std::function<void(BasicBlock *)> Callback);
 160
 161   /// Recalculate all available trees and flush all BasicBlocks
 162   /// awaiting deletion immediately.
 163   void recalculate(Function &F);
 164
 165   /// Flush DomTree updates and return DomTree.
 166   /// It also flush out of date updates applied by all available trees
 167   /// and flush Deleted BBs if both trees are up-to-date.
 168   /// It must only be called when it has a DomTree.
 169   DominatorTree &getDomTree();
 170
 171   /// Flush PostDomTree updates and return PostDomTree.
 172   /// It also flush out of date updates applied by all available trees
 173   /// and flush Deleted BBs if both trees are up-to-date.
 174   /// It must only be called when it has a PostDomTree.
 175   PostDominatorTree &getPostDomTree();
 176
 177   /// Apply all pending updates to available trees and flush all BasicBlocks
 178   /// awaiting deletion.
 179   /// Does nothing under Eager UpdateStrategy.
 180   void flush();
 181
 182   /// Debug method to help view the internal state of this class.
 183   LLVM_DUMP_METHOD void dump() const;
 184
 185 private:
 186   class CallBackOnDeletion final : public CallbackVH {
 187   public:
 188     CallBackOnDeletion(BasicBlock *V,
 189                        std::function<void(BasicBlock *)> Callback)
 190         : CallbackVH(V), DelBB(V), Callback_(Callback) {}
 191
 192   private:
 193     BasicBlock *DelBB = nullptr;
 194     std::function<void(BasicBlock *)> Callback_;
 195
 196     void deleted() override {
 197       Callback_(DelBB);
 198       CallbackVH::deleted();
 199     }
 200   };
 201
 202   SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
 203   size_t PendDTUpdateIndex = 0;
 204   size_t PendPDTUpdateIndex = 0;
 205   DominatorTree *DT = nullptr;
 206   PostDominatorTree *PDT = nullptr;
 207   const UpdateStrategy Strategy;
 208   SmallPtrSet<BasicBlock *, 8> DeletedBBs;
 209   std::vector<CallBackOnDeletion> Callbacks;
 210   bool IsRecalculatingDomTree = false;
 211   bool IsRecalculatingPostDomTree = false;
 212
 213   /// First remove all the instructions of DelBB and then make sure DelBB has a
 214   /// valid terminator instruction which is necessary to have when DelBB still
 215   /// has to be inside of its parent Function while awaiting deletion under Lazy
 216   /// UpdateStrategy to prevent other routines from asserting the state of the
 217   /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
 218   void validateDeleteBB(BasicBlock *DelBB);
 219
 220   /// Returns true if at least one BasicBlock is deleted.
 221   bool forceFlushDeletedBB();
 222
 223   /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
 224   /// UpdateStrategy. Returns true if the update is queued for update.
 225   bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
 226                        BasicBlock *To);
 227
 228   /// Helper function to apply all pending DomTree updates.
 229   void applyDomTreeUpdates();
 230
 231   /// Helper function to apply all pending PostDomTree updates.
 232   void applyPostDomTreeUpdates();
 233
 234   /// Helper function to flush deleted BasicBlocks if all available
 235   /// trees are up-to-date.
 236   void tryFlushDeletedBB();
 237
 238   /// Drop all updates applied by all available trees and delete BasicBlocks if
 239   /// all available trees are up-to-date.
 240   void dropOutOfDateUpdates();
 241
 242   /// Erase Basic Block node that has been unlinked from Function
 243   /// in the DomTree and PostDomTree.
 244   void eraseDelBBNode(BasicBlock *DelBB);
 245
 246   /// Returns true if the update appears in the LLVM IR.
 247   /// It is used to check whether an update is valid in
 248   /// insertEdge/deleteEdge or is unnecessary in the batch update.
 249   bool isUpdateValid(DominatorTree::UpdateType Update) const;
 250
 251   /// Returns true if the update is self dominance.
 252   bool isSelfDominance(DominatorTree::UpdateType Update) const;
 253 };
 254 } // namespace llvm
 255
 256 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H