#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
template <class NodeT> class DominatorBase {
protected:
std::vector<NodeT *> Roots;
- const bool IsPostDominators;
- inline explicit DominatorBase(bool isPostDom)
+ bool IsPostDominators;
+ explicit DominatorBase(bool isPostDom)
: Roots(), IsPostDominators(isPostDom) {}
+ DominatorBase(DominatorBase &&Arg)
+ : Roots(std::move(Arg.Roots)),
+ IsPostDominators(std::move(Arg.IsPostDominators)) {
+ Arg.Roots.clear();
+ }
+ DominatorBase &operator=(DominatorBase &&RHS) {
+ Roots = std::move(RHS.Roots);
+ IsPostDominators = std::move(RHS.IsPostDominators);
+ RHS.Roots.clear();
+ return *this;
+ }
public:
/// getRoots - Return the root blocks of the current CFG. This may include
/// multiple blocks if we are computing post dominators. For forward
/// dominators, this will always be a single block (the entry node).
///
- inline const std::vector<NodeT *> &getRoots() const { return Roots; }
+ const std::vector<NodeT *> &getRoots() const { return Roots; }
/// isPostDominator - Returns true if analysis based of postdoms
///
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
: TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) {}
- DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
- Children.push_back(C);
+ std::unique_ptr<DomTreeNodeBase<NodeT>>
+ addChild(std::unique_ptr<DomTreeNodeBase<NodeT>> C) {
+ Children.push_back(C.get());
return C;
}
};
template <class NodeT>
-inline raw_ostream &operator<<(raw_ostream &o,
- const DomTreeNodeBase<NodeT> *Node) {
+raw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase<NodeT> *Node) {
if (Node->getBlock())
Node->getBlock()->printAsOperand(o, false);
else
}
template <class NodeT>
-inline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
- unsigned Lev) {
+void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
+ unsigned Lev) {
o.indent(2 * Lev) << "[" << Lev << "] " << N;
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
E = N->end();
/// This class is a generic template over graph nodes. It is instantiated for
/// various graphs in the LLVM IR or in the code generator.
template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
+ DominatorTreeBase(const DominatorTreeBase &) LLVM_DELETED_FUNCTION;
+ DominatorTreeBase &operator=(const DominatorTreeBase &) LLVM_DELETED_FUNCTION;
+
bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
const DomTreeNodeBase<NodeT> *B) const {
assert(A != B);
return IDom != nullptr;
}
+ /// \brief Wipe this tree's state without releasing any resources.
+ ///
+ /// This is essentially a post-move helper only. It leaves the object in an
+ /// assignable and destroyable state, but otherwise invalid.
+ void wipe() {
+ DomTreeNodes.clear();
+ IDoms.clear();
+ Vertex.clear();
+ Info.clear();
+ RootNode = nullptr;
+ }
+
protected:
- typedef DenseMap<NodeT *, DomTreeNodeBase<NodeT> *> DomTreeNodeMapType;
+ typedef DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>
+ DomTreeNodeMapType;
DomTreeNodeMapType DomTreeNodes;
DomTreeNodeBase<NodeT> *RootNode;
DenseMap<NodeT *, InfoRec> Info;
void reset() {
- for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
- E = DomTreeNodes.end();
- I != E; ++I)
- delete I->second;
DomTreeNodes.clear();
IDoms.clear();
this->Roots.clear();
public:
explicit DominatorTreeBase(bool isPostDom)
: DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
- virtual ~DominatorTreeBase() { reset(); }
+
+ DominatorTreeBase(DominatorTreeBase &&Arg)
+ : DominatorBase<NodeT>(
+ std::move(static_cast<DominatorBase<NodeT> &>(Arg))),
+ DomTreeNodes(std::move(Arg.DomTreeNodes)),
+ RootNode(std::move(Arg.RootNode)),
+ DFSInfoValid(std::move(Arg.DFSInfoValid)),
+ SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)),
+ Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) {
+ Arg.wipe();
+ }
+ DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
+ DominatorBase<NodeT>::operator=(
+ std::move(static_cast<DominatorBase<NodeT> &>(RHS)));
+ DomTreeNodes = std::move(RHS.DomTreeNodes);
+ RootNode = std::move(RHS.RootNode);
+ DFSInfoValid = std::move(RHS.DFSInfoValid);
+ SlowQueries = std::move(RHS.SlowQueries);
+ IDoms = std::move(RHS.IDoms);
+ Vertex = std::move(RHS.Vertex);
+ Info = std::move(RHS.Info);
+ RHS.wipe();
+ return *this;
+ }
/// compare - Return false if the other dominator tree base matches this
/// dominator tree base. Otherwise return true.
if (OI == OtherDomTreeNodes.end())
return true;
- DomTreeNodeBase<NodeT> *MyNd = I->second;
- DomTreeNodeBase<NodeT> *OtherNd = OI->second;
+ DomTreeNodeBase<NodeT> &MyNd = *I->second;
+ DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
- if (MyNd->compare(OtherNd))
+ if (MyNd.compare(&OtherNd))
return true;
}
return false;
}
- virtual void releaseMemory() { reset(); }
+ void releaseMemory() { reset(); }
/// getNode - return the (Post)DominatorTree node for the specified basic
/// block. This is the same as using operator[] on this class.
///
- inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
- return DomTreeNodes.lookup(BB);
+ DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
+ auto I = DomTreeNodes.find(BB);
+ if (I != DomTreeNodes.end())
+ return I->second.get();
+ return nullptr;
}
- inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const {
- return getNode(BB);
- }
+ DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); }
/// getRootNode - This returns the entry node for the CFG of the function. If
/// this tree represents the post-dominance relations for a function, however,
return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
}
- inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
- return A;
- }
+ bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
/// dominates - Returns true iff A dominates B. Note that this is not a
/// constant time operation!
///
- inline bool dominates(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) const {
+ bool dominates(const DomTreeNodeBase<NodeT> *A,
+ const DomTreeNodeBase<NodeT> *B) const {
// A node trivially dominates itself.
if (B == A)
return true;
DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
assert(IDomNode && "Not immediate dominator specified for block!");
DFSInfoValid = false;
- return DomTreeNodes[BB] =
- IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
+ return (DomTreeNodes[BB] = IDomNode->addChild(
+ llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
}
/// changeImmediateDominator - This method is used to update the dominator
}
DomTreeNodes.erase(BB);
- delete Node;
- }
-
- /// removeNode - Removes a node from the dominator tree. Block must not
- /// dominate any other blocks. Invalidates any node pointing to removed
- /// block.
- void removeNode(NodeT *BB) {
- assert(getNode(BB) && "Removing node that isn't in dominator tree.");
- DomTreeNodes.erase(BB);
}
/// splitBlock - BB is split and now it has one successor. Update dominator
// Add a new tree node for this NodeT, and link it as a child of
// IDomNode
- DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
- return this->DomTreeNodes[BB] = IDomNode->addChild(C);
+ return (this->DomTreeNodes[BB] = IDomNode->addChild(
+ llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
}
- inline NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); }
+ NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); }
- inline void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
+ void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
public:
/// recalculate - compute a dominator tree for the given function
projects / oota-llvm.git / blobdiff