+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SetOperations.h"
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// ImmediatePostDominators Implementation
+//===----------------------------------------------------------------------===//
+
+static RegisterPass<ImmediatePostDominators>
+D("postidom", "Immediate Post-Dominators Construction", true);
+
+unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
+ unsigned N) {
+ std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
+ std::set<BasicBlock *> visited;
+ workStack.push_back(std::make_pair(V, &VInfo));
+
+ do {
+ BasicBlock *currentBB = workStack.back().first;
+ InfoRec *currentVInfo = workStack.back().second;
+
+ // Visit each block only once.
+ if (visited.count(currentBB) == 0) {
+
+ visited.insert(currentBB);
+ currentVInfo->Semi = ++N;
+ currentVInfo->Label = currentBB;
+
+ Vertex.push_back(currentBB); // Vertex[n] = current;
+ // Info[currentBB].Ancestor = 0;
+ // Ancestor[n] = 0
+ // Child[currentBB] = 0;
+ currentVInfo->Size = 1; // Size[currentBB] = 1
+ }
+
+ // Visit children
+ bool visitChild = false;
+ for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB);
+ PI != PE && !visitChild; ++PI) {
+ InfoRec &SuccVInfo = Info[*PI];
+ if (SuccVInfo.Semi == 0) {
+ SuccVInfo.Parent = currentBB;
+ if (visited.count (*PI) == 0) {
+ workStack.push_back(std::make_pair(*PI, &SuccVInfo));
+ visitChild = true;
+ }
+ }
+ }
+
+ // If all children are visited or if this block has no child then pop this
+ // block out of workStack.
+ if (!visitChild)
+ workStack.pop_back();
+
+ } while (!workStack.empty());
+
+ return N;
+}
+
+void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
+ BasicBlock *VAncestor = VInfo.Ancestor;
+ InfoRec &VAInfo = Info[VAncestor];
+ if (VAInfo.Ancestor == 0)
+ return;
+
+ Compress(VAncestor, VAInfo);
+
+ BasicBlock *VAncestorLabel = VAInfo.Label;
+ BasicBlock *VLabel = VInfo.Label;
+ if (Info[VAncestorLabel].Semi < Info[VLabel].Semi)
+ VInfo.Label = VAncestorLabel;
+
+ VInfo.Ancestor = VAInfo.Ancestor;
+}
+
+BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) {
+ InfoRec &VInfo = Info[V];
+
+ // Higher-complexity but faster implementation
+ if (VInfo.Ancestor == 0)
+ return V;
+ Compress(V, VInfo);
+ return VInfo.Label;
+}
+
+void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W,
+ InfoRec &WInfo) {
+ // Higher-complexity but faster implementation
+ WInfo.Ancestor = V;
+}
+
+bool ImmediatePostDominators::runOnFunction(Function &F) {
+ IDoms.clear(); // Reset from the last time we were run...
+ Roots.clear();
+
+ // Step #0: Scan the function looking for the root nodes of the post-dominance
+ // relationships. These blocks, which have no successors, end with return and
+ // unwind instructions.
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+ if (succ_begin(I) == succ_end(I))
+ Roots.push_back(I);
+
+ Vertex.push_back(0);
+
+ // Step #1: Number blocks in depth-first order and initialize variables used
+ // in later stages of the algorithm.
+ unsigned N = 0;
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ N = DFSPass(Roots[i], Info[Roots[i]], N);
+
+ for (unsigned i = N; i >= 2; --i) {
+ BasicBlock *W = Vertex[i];
+ InfoRec &WInfo = Info[W];
+
+ // Step #2: Calculate the semidominators of all vertices
+ for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI)
+ if (Info.count(*SI)) { // Only if this predecessor is reachable!
+ unsigned SemiU = Info[Eval(*SI)].Semi;
+ if (SemiU < WInfo.Semi)
+ WInfo.Semi = SemiU;
+ }
+
+ Info[Vertex[WInfo.Semi]].Bucket.push_back(W);
+
+ BasicBlock *WParent = WInfo.Parent;
+ Link(WParent, W, WInfo);
+
+ // Step #3: Implicitly define the immediate dominator of vertices
+ std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket;
+ while (!WParentBucket.empty()) {
+ BasicBlock *V = WParentBucket.back();
+ WParentBucket.pop_back();
+ BasicBlock *U = Eval(V);
+ IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent;
+ }
+ }
+
+ // Step #4: Explicitly define the immediate dominator of each vertex
+ for (unsigned i = 2; i <= N; ++i) {
+ BasicBlock *W = Vertex[i];
+ BasicBlock *&WIDom = IDoms[W];
+ if (WIDom != Vertex[Info[W].Semi])
+ WIDom = IDoms[WIDom];
+ }
+
+ // Free temporary memory used to construct idom's
+ Info.clear();
+ std::vector<BasicBlock*>().swap(Vertex);
+
+ return false;
+}