Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file defines the DomTreeUpdater class, which provides a uniform way to

// update dominator tree related data structures.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DOMTREEUPDATER_H

#define LLVM_ANALYSIS_DOMTREEUPDATER_H

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/ValueHandle.h"

#include "llvm/Support/Compiler.h"

#include <cstddef>

#include <functional>

#include <vector>

namespace llvm {

class PostDominatorTree;

class DomTreeUpdater {

public:

  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };

  explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}

  DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)

      : DT(&DT_), Strategy(Strategy_) {}

  DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)

      : DT(DT_), Strategy(Strategy_) {}

  DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)

      : PDT(&PDT_), Strategy(Strategy_) {}

  DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)

      : PDT(PDT_), Strategy(Strategy_) {}

  DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,

                 UpdateStrategy Strategy_)

      : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}

  DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,

                 UpdateStrategy Strategy_)

      : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}

  ~DomTreeUpdater() { flush(); }

  /// Returns true if the current strategy is Lazy.

  bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };

  /// Returns true if the current strategy is Eager.

  bool isEager() const { return Strategy == UpdateStrategy::Eager; };

  /// Returns true if it holds a DominatorTree.

  bool hasDomTree() const { return DT != nullptr; }

  /// Returns true if it holds a PostDominatorTree.

  bool hasPostDomTree() const { return PDT != nullptr; }

  /// Returns true if there is BasicBlock awaiting deletion.

  /// The deletion will only happen until a flush event and

  /// all available trees are up-to-date.

  /// Returns false under Eager UpdateStrategy.

  bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }

  /// Returns true if DelBB is awaiting deletion.

  /// Returns false under Eager UpdateStrategy.

  bool isBBPendingDeletion(BasicBlock *DelBB) const;

  /// Returns true if either of DT or PDT is valid and the tree has at

  /// least one update pending. If DT or PDT is nullptr it is treated

  /// as having no pending updates. This function does not check

  /// whether there is BasicBlock awaiting deletion.

  /// Returns false under Eager UpdateStrategy.

  bool hasPendingUpdates() const;

  /// Returns true if there are DominatorTree updates queued.

  /// Returns false under Eager UpdateStrategy or DT is nullptr.

  bool hasPendingDomTreeUpdates() const;

  /// Returns true if there are PostDominatorTree updates queued.

  /// Returns false under Eager UpdateStrategy or PDT is nullptr.

  bool hasPendingPostDomTreeUpdates() const;

  ///@{

  /// \name Mutation APIs

  ///

  /// These methods provide APIs for submitting updates to the DominatorTree and

  /// the PostDominatorTree.

  ///

  /// Note: There are two strategies to update the DominatorTree and the

  /// PostDominatorTree:

  /// 1. Eager UpdateStrategy: Updates are submitted and then flushed

  /// immediately.

  /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you

  /// explicitly call Flush APIs. 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.

  ///

  /// Although GenericDomTree provides several update primitives,

  /// it is not encouraged to use these APIs directly.

  /// Submit updates to all available trees.

  /// The Eager Strategy flushes updates immediately while the Lazy Strategy

  /// queues the updates.

  ///

  /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is

  /// in sync with + all updates before that single update.

  ///

  /// CAUTION!

  /// 1. It is required for the state of the LLVM IR to be updated

  /// *before* submitting the updates because the internal update routine will

  /// analyze the current state of the CFG to determine whether an update

  /// is valid.

  /// 2. It is illegal to submit any update that has already been submitted,

  /// i.e., you are supposed not to insert an existent edge or delete a

  /// nonexistent edge.

  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);

  /// Submit updates to all available trees. It will also

  /// 1. discard duplicated updates,

  /// 2. remove invalid updates. (Invalid updates means deletion of an edge that

  /// still exists or insertion of an edge that does not exist.)

  /// The Eager Strategy flushes updates immediately while the Lazy Strategy

  /// queues the updates.

  ///

  /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is

  /// in sync with + all updates before that single update.

  ///

  /// CAUTION!

  /// 1. It is required for the state of the LLVM IR to be updated

  /// *before* submitting the updates because the internal update routine will

  /// analyze the current state of the CFG to determine whether an update

  /// is valid.

  /// 2. It is illegal to submit any update that has already been submitted,

  /// i.e., you are supposed not to insert an existent edge or delete a

  /// nonexistent edge.

  /// 3. It is only legal to submit updates to an edge in the order CFG changes

  /// are made. The order you submit updates on different edges is not

  /// restricted.

  void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates);

  /// Notify DTU that the entry block was replaced.

  /// Recalculate all available trees and flush all BasicBlocks

  /// awaiting deletion immediately.

  void recalculate(Function &F);

  /// Delete DelBB. DelBB will be removed from its Parent and

  /// erased from available trees if it exists and finally get deleted.

  /// Under Eager UpdateStrategy, DelBB will be processed immediately.

  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and

  /// all available trees are up-to-date. Assert if any instruction of DelBB is

  /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB

  /// will be queued until flush() is called.

  void deleteBB(BasicBlock *DelBB);

  /// Delete DelBB. DelBB will be removed from its Parent and

  /// erased from available trees if it exists. Then the callback will

  /// be called. Finally, DelBB will be deleted.

  /// Under Eager UpdateStrategy, DelBB will be processed immediately.

  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and

  /// all available trees are up-to-date. Assert if any instruction of DelBB is

  /// modified while awaiting deletion. Multiple callbacks can be queued for one

  /// DelBB under Lazy UpdateStrategy.

  void callbackDeleteBB(BasicBlock *DelBB,

                        std::function<void(BasicBlock *)> Callback);

  ///@}

  ///@{

  /// \name Flush APIs

  ///

  /// CAUTION! By the moment these flush APIs are called, the current CFG needs

  /// to be the same as the CFG which DTU is in sync with + all updates

  /// submitted.

  /// Flush DomTree updates and return DomTree.

  /// It flushes Deleted BBs if both trees are up-to-date.

  /// It must only be called when it has a DomTree.

  DominatorTree &getDomTree();

  /// Flush PostDomTree updates and return PostDomTree.

  /// It flushes Deleted BBs if both trees are up-to-date.

  /// 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.

  void flush();

  ///@}

  /// Debug method to help view the internal state of this class.

  LLVM_DUMP_METHOD void dump() const;

private:

  class CallBackOnDeletion final : public CallbackVH {

  public:

    CallBackOnDeletion(BasicBlock *V,

                       std::function<void(BasicBlock *)> Callback)

        : CallbackVH(V), DelBB(V), Callback_(Callback) {}

  private:

    BasicBlock *DelBB = nullptr;

    std::function<void(BasicBlock *)> Callback_;

    void deleted() override {

      Callback_(DelBB);

      CallbackVH::deleted();

    }

  };

  SmallVector<DominatorTree::UpdateType, 16> PendUpdates;

  size_t PendDTUpdateIndex = 0;

  size_t PendPDTUpdateIndex = 0;

  DominatorTree *DT = nullptr;

  PostDominatorTree *PDT = nullptr;

  const UpdateStrategy Strategy;

  SmallPtrSet<BasicBlock *, 8> DeletedBBs;

  std::vector<CallBackOnDeletion> Callbacks;

  bool IsRecalculatingDomTree = false;

  bool IsRecalculatingPostDomTree = false;

  /// First remove all the instructions of DelBB and then make sure DelBB has a

  /// valid terminator instruction which is necessary to have when DelBB still

  /// has to be inside of its parent Function while awaiting deletion under Lazy

  /// UpdateStrategy to prevent other routines from asserting the state of the

  /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.

  void validateDeleteBB(BasicBlock *DelBB);

  /// Returns true if at least one BasicBlock is deleted.

  bool forceFlushDeletedBB();

  /// Helper function to apply all pending DomTree updates.

  void applyDomTreeUpdates();

  /// Helper function to apply all pending PostDomTree updates.

  void applyPostDomTreeUpdates();

  /// Helper function to flush deleted BasicBlocks if all available

  /// trees are up-to-date.

  void tryFlushDeletedBB();

  /// Drop all updates applied by all available trees and delete BasicBlocks if

  /// all available trees are up-to-date.

  void dropOutOfDateUpdates();

  /// Erase Basic Block node that has been unlinked from Function

  /// in the DomTree and PostDomTree.

  void eraseDelBBNode(BasicBlock *DelBB);

  /// Returns true if the update appears in the LLVM IR.

  /// It is used to check whether an update is valid in

  /// insertEdge/deleteEdge or is unnecessary in the batch update.

  bool isUpdateValid(DominatorTree::UpdateType Update) const;

  /// Returns true if the update is self dominance.

  bool isSelfDominance(DominatorTree::UpdateType Update) const;

};

} // namespace llvm

#endif // LLVM_ANALYSIS_DOMTREEUPDATER_H