GenericDomTreeConstruction.h [plain text]
#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/GenericDomTree.h"
namespace llvm {
template<class GraphT>
unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
typename GraphT::NodeType* V, unsigned N) {
#if 0
InfoRec &VInfo = DT.Info[DT.Roots[i]];
VInfo.DFSNum = VInfo.Semi = ++N;
VInfo.Label = V;
Vertex.push_back(V);
for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
InfoRec &SuccVInfo = DT.Info[*SI];
if (SuccVInfo.Semi == 0) {
SuccVInfo.Parent = V;
N = DTDFSPass(DT, *SI, N);
}
}
#else
bool IsChildOfArtificialExit = (N != 0);
SmallVector<std::pair<typename GraphT::NodeType*,
typename GraphT::ChildIteratorType>, 32> Worklist;
Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
while (!Worklist.empty()) {
typename GraphT::NodeType* BB = Worklist.back().first;
typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
DT.Info[BB];
if (NextSucc == GraphT::child_begin(BB)) {
BBInfo.DFSNum = BBInfo.Semi = ++N;
BBInfo.Label = BB;
DT.Vertex.push_back(BB);
if (IsChildOfArtificialExit)
BBInfo.Parent = 1;
IsChildOfArtificialExit = false;
}
unsigned BBDFSNum = BBInfo.DFSNum;
if (NextSucc == GraphT::child_end(BB)) {
Worklist.pop_back();
continue;
}
++Worklist.back().second;
typename GraphT::NodeType* Succ = *NextSucc;
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo =
DT.Info[Succ];
if (SuccVInfo.Semi == 0) {
SuccVInfo.Parent = BBDFSNum;
Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
}
}
#endif
return N;
}
template<class GraphT>
typename GraphT::NodeType*
Eval(DominatorTreeBase<typename GraphT::NodeType>& DT,
typename GraphT::NodeType *VIn, unsigned LastLinked) {
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo =
DT.Info[VIn];
if (VInInfo.DFSNum < LastLinked)
return VIn;
SmallVector<typename GraphT::NodeType*, 32> Work;
SmallPtrSet<typename GraphT::NodeType*, 32> Visited;
if (VInInfo.Parent >= LastLinked)
Work.push_back(VIn);
while (!Work.empty()) {
typename GraphT::NodeType* V = Work.back();
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
DT.Info[V];
typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent];
if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) {
Work.push_back(VAncestor);
continue;
}
Work.pop_back();
if (VInfo.Parent < LastLinked)
continue;
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo =
DT.Info[VAncestor];
typename GraphT::NodeType* VAncestorLabel = VAInfo.Label;
typename GraphT::NodeType* VLabel = VInfo.Label;
if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
VInfo.Label = VAncestorLabel;
VInfo.Parent = VAInfo.Parent;
}
return VInInfo.Label;
}
template<class FuncT, class NodeT>
void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
FuncT& F) {
typedef GraphTraits<NodeT> GraphT;
unsigned N = 0;
bool MultipleRoots = (DT.Roots.size() > 1);
if (MultipleRoots) {
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
DT.Info[nullptr];
BBInfo.DFSNum = BBInfo.Semi = ++N;
BBInfo.Label = nullptr;
DT.Vertex.push_back(nullptr); }
for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
i != e; ++i)
N = DFSPass<GraphT>(DT, DT.Roots[i], N);
MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
SmallVector<unsigned, 32> Buckets;
Buckets.resize(N + 1);
for (unsigned i = 1; i <= N; ++i)
Buckets[i] = i;
for (unsigned i = N; i >= 2; --i) {
typename GraphT::NodeType* W = DT.Vertex[i];
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo =
DT.Info[W];
for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
typename GraphT::NodeType* V = DT.Vertex[Buckets[j]];
typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1);
DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
}
WInfo.Semi = WInfo.Parent;
typedef GraphTraits<Inverse<NodeT> > InvTraits;
for (typename InvTraits::ChildIteratorType CI =
InvTraits::child_begin(W),
E = InvTraits::child_end(W); CI != E; ++CI) {
typename InvTraits::NodeType *N = *CI;
if (DT.Info.count(N)) { unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
if (SemiU < WInfo.Semi)
WInfo.Semi = SemiU;
}
}
if (WInfo.Semi == WInfo.Parent) {
DT.IDoms[W] = DT.Vertex[WInfo.Parent];
} else {
Buckets[i] = Buckets[WInfo.Semi];
Buckets[WInfo.Semi] = i;
}
}
if (N >= 1) {
typename GraphT::NodeType* Root = DT.Vertex[1];
for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) {
typename GraphT::NodeType* V = DT.Vertex[Buckets[j]];
DT.IDoms[V] = Root;
}
}
for (unsigned i = 2; i <= N; ++i) {
typename GraphT::NodeType* W = DT.Vertex[i];
typename GraphT::NodeType*& WIDom = DT.IDoms[W];
if (WIDom != DT.Vertex[DT.Info[W].Semi])
WIDom = DT.IDoms[WIDom];
}
if (DT.Roots.empty()) return;
typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : nullptr;
DT.DomTreeNodes[Root] = DT.RootNode =
new DomTreeNodeBase<typename GraphT::NodeType>(Root, nullptr);
for (unsigned i = 2; i <= N; ++i) {
typename GraphT::NodeType* W = DT.Vertex[i];
DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[W];
if (BBNode) continue;
typename GraphT::NodeType* ImmDom = DT.getIDom(W);
assert(ImmDom || DT.DomTreeNodes[nullptr]);
DomTreeNodeBase<typename GraphT::NodeType> *IDomNode =
DT.getNodeForBlock(ImmDom);
DomTreeNodeBase<typename GraphT::NodeType> *C =
new DomTreeNodeBase<typename GraphT::NodeType>(W, IDomNode);
DT.DomTreeNodes[W] = IDomNode->addChild(C);
}
DT.IDoms.clear();
DT.Info.clear();
std::vector<typename GraphT::NodeType*>().swap(DT.Vertex);
DT.updateDFSNumbers();
}
}
#endif