LCOV - code coverage report
Current view: top level - include/llvm/IR - DomTreeUpdater.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 14 15 93.3 %
Date: 2018-10-20 13:21:21 Functions: 3 7 42.9 %
Legend: Lines: hit not hit

          Line data    Source code
       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      271227 :       : DT(&DT_), Strategy(Strategy_) {}
      34             :   DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
      35      137592 :       : 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          12 :       : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
      43             :   DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
      44             :                  UpdateStrategy Strategy_)
      45      131541 :       : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
      46             : 
      47      180167 :   ~DomTreeUpdater() { flush(); }
      48             : 
      49             :   /// Returns true if the current strategy is Lazy.
      50           5 :   bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };
      51             : 
      52             :   /// Returns true if the current strategy is Eager.
      53           2 :   bool isEager() const { return Strategy == UpdateStrategy::Eager; };
      54             : 
      55             :   /// Returns true if it holds a DominatorTree.
      56           0 :   bool hasDomTree() const { return DT != nullptr; }
      57             : 
      58             :   /// Returns true if it holds a PostDominatorTree.
      59           5 :   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           4 :   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           3 :     CallBackOnDeletion(BasicBlock *V,
     190             :                        std::function<void(BasicBlock *)> Callback)
     191           6 :         : CallbackVH(V), DelBB(V), Callback_(Callback) {}
     192             : 
     193             :   private:
     194             :     BasicBlock *DelBB = nullptr;
     195             :     std::function<void(BasicBlock *)> Callback_;
     196             : 
     197           3 :     void deleted() override {
     198           6 :       Callback_(DelBB);
     199             :       CallbackVH::deleted();
     200           3 :     }
     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

Generated by: LCOV version 1.13