Update clang to r339409.
Change-Id: I800772d2d838223be1f6b40d490c4591b937fca2
diff --git a/linux-x64/clang/include/llvm/IR/DomTreeUpdater.h b/linux-x64/clang/include/llvm/IR/DomTreeUpdater.h
new file mode 100644
index 0000000..e5bb092
--- /dev/null
+++ b/linux-x64/clang/include/llvm/IR/DomTreeUpdater.h
@@ -0,0 +1,257 @@
+//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the DomTreeUpdater class, which provides a uniform way to
+// update dominator tree related data structures.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DOMTREEUPDATER_H
+#define LLVM_DOMTREEUPDATER_H
+
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/GenericDomTree.h"
+#include <functional>
+#include <vector>
+
+namespace llvm {
+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;
+
+ /// Apply updates on all available trees. Under Eager UpdateStrategy with
+ /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
+ /// discard duplicated updates and self-dominance updates. If both DT and PDT
+ /// are nullptrs, this function discards all updates. The Eager Strategy
+ /// applies the updates immediately while the Lazy Strategy queues the
+ /// updates. It is required for the state of the LLVM IR to be updated
+ /// *before* applying the Updates because the internal update routine will
+ /// analyze the current state of the relationship between a pair of (From, To)
+ /// BasicBlocks to determine whether a single update needs to be discarded.
+ void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
+ bool ForceRemoveDuplicates = false);
+
+ /// Notify all available trees on an edge insertion. If both DT and PDT are
+ /// nullptrs, this function discards the update. Under either Strategy,
+ /// self-dominance update will be removed. The Eager Strategy applies
+ /// the update immediately while the Lazy Strategy queues the update.
+ /// It is recommended to only use this method when you have exactly one
+ /// insertion (and no deletions). It is recommended to use applyUpdates() in
+ /// all other cases. This function has to be called *after* making the update
+ /// on the actual CFG. An internal functions checks if the edge exists in the
+ /// CFG in DEBUG mode.
+ void insertEdge(BasicBlock *From, BasicBlock *To);
+
+ /// Notify all available trees on an edge insertion.
+ /// Under either Strategy, the following updates will be discard silently
+ /// 1. Invalid - Inserting an edge that does not exist in the CFG.
+ /// 2. Self-dominance update.
+ /// 3. Both DT and PDT are nullptrs.
+ /// The Eager Strategy applies the update immediately while the Lazy Strategy
+ /// queues the update. It is recommended to only use this method when you have
+ /// exactly one insertion (and no deletions) and want to discard an invalid
+ /// update.
+ void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+
+ /// Notify all available trees on an edge deletion. If both DT and PDT are
+ /// nullptrs, this function discards the update. Under either Strategy,
+ /// self-dominance update will be removed. The Eager Strategy applies
+ /// the update immediately while the Lazy Strategy queues the update.
+ /// It is recommended to only use this method when you have exactly one
+ /// deletion (and no insertions). It is recommended to use applyUpdates() in
+ /// all other cases. This function has to be called *after* making the update
+ /// on the actual CFG. An internal functions checks if the edge doesn't exist
+ /// in the CFG in DEBUG mode.
+ void deleteEdge(BasicBlock *From, BasicBlock *To);
+
+ /// Notify all available trees on an edge deletion.
+ /// Under either Strategy, the following updates will be discard silently
+ /// 1. Invalid - Deleting an edge that still exists in the CFG.
+ /// 2. Self-dominance update.
+ /// 3. Both DT and PDT are nullptrs.
+ /// The Eager Strategy applies the update immediately while the Lazy Strategy
+ /// queues the update. It is recommended to only use this method when you have
+ /// exactly one deletion (and no insertions) and want to discard an invalid
+ /// update.
+ void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+
+ /// 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);
+
+ /// Recalculate all available trees and flush all BasicBlocks
+ /// awaiting deletion immediately.
+ void recalculate(Function &F);
+
+ /// Flush DomTree updates and return DomTree.
+ /// It also flush out of date updates applied by all available trees
+ /// and flush 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 also flush out of date updates applied by all available trees
+ /// and flush 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.
+ /// Does nothing under Eager UpdateStrategy.
+ 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();
+
+ /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
+ /// UpdateStrategy. Returns true if the update is queued for update.
+ bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
+ BasicBlock *To);
+
+ /// 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_DOMTREEUPDATER_H