Check in LLVM r95781.
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
new file mode 100644
index 0000000..c38e050
--- /dev/null
+++ b/lib/Analysis/PostDominators.cpp
@@ -0,0 +1,98 @@
+//===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the post-dominator construction algorithms.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "postdomtree"
+
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Instructions.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SetOperations.h"
+#include "llvm/Analysis/DominatorInternals.h"
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// PostDominatorTree Implementation
+//===----------------------------------------------------------------------===//
+
+char PostDominatorTree::ID = 0;
+char PostDominanceFrontier::ID = 0;
+static RegisterPass<PostDominatorTree>
+F("postdomtree", "Post-Dominator Tree Construction", true, true);
+
+bool PostDominatorTree::runOnFunction(Function &F) {
+ DT->recalculate(F);
+ DEBUG(DT->print(dbgs()));
+ return false;
+}
+
+PostDominatorTree::~PostDominatorTree() {
+ delete DT;
+}
+
+void PostDominatorTree::print(raw_ostream &OS, const Module *) const {
+ DT->print(OS);
+}
+
+
+FunctionPass* llvm::createPostDomTree() {
+ return new PostDominatorTree();
+}
+
+//===----------------------------------------------------------------------===//
+// PostDominanceFrontier Implementation
+//===----------------------------------------------------------------------===//
+
+static RegisterPass<PostDominanceFrontier>
+H("postdomfrontier", "Post-Dominance Frontier Construction", true, true);
+
+const DominanceFrontier::DomSetType &
+PostDominanceFrontier::calculate(const PostDominatorTree &DT,
+ const DomTreeNode *Node) {
+ // Loop over CFG successors to calculate DFlocal[Node]
+ BasicBlock *BB = Node->getBlock();
+ DomSetType &S = Frontiers[BB]; // The new set to fill in...
+ if (getRoots().empty()) return S;
+
+ if (BB)
+ for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
+ SI != SE; ++SI) {
+ // Does Node immediately dominate this predecessor?
+ DomTreeNode *SINode = DT[*SI];
+ if (SINode && SINode->getIDom() != Node)
+ S.insert(*SI);
+ }
+
+ // At this point, S is DFlocal. Now we union in DFup's of our children...
+ // Loop through and visit the nodes that Node immediately dominates (Node's
+ // children in the IDomTree)
+ //
+ for (DomTreeNode::const_iterator
+ NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
+ DomTreeNode *IDominee = *NI;
+ const DomSetType &ChildDF = calculate(DT, IDominee);
+
+ DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
+ for (; CDFI != CDFE; ++CDFI) {
+ if (!DT.properlyDominates(Node, DT[*CDFI]))
+ S.insert(*CDFI);
+ }
+ }
+
+ return S;
+}
+
+FunctionPass* llvm::createPostDomFrontier() {
+ return new PostDominanceFrontier();
+}