1 files changed, 94 insertions, 0 deletions
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
new file mode 100644
index 000000000000..4853c2ac87b7
--- /dev/null
+++ b/lib/Analysis/PostDominators.cpp
@@ -0,0 +1,94 @@
+//===- 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->dump());
+  return false;
+}
+
+PostDominatorTree::~PostDominatorTree()
+{
+  delete DT;
+}
+
+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();
+}