Index: include/llvm/IR/CFGDiff.h
===================================================================
--- /dev/null
+++ include/llvm/IR/CFGDiff.h
@@ -0,0 +1,216 @@
+//===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines specializations of GraphTraits that allows generic
+// algorithms to see a different snapshot of a CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_CFGDIFF_H
+#define LLVM_IR_CFGDIFF_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/Support/CFGUpdate.h"
+#include "llvm/Support/type_traits.h"
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+
+namespace llvm {
+
+// GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
+// utilities to skip edges marked as deleted and return a set of edges marked as
+// newly inserted. The current diff treats the CFG as a graph rather than a
+// multigraph. Added edges are pruned to be unique, and deleted edges will
+// remove all existing edges between two blocks.
+template <typename NodePtr>
+class GraphDiff {
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> SuccInsert;
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> SuccDelete;
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> PredInsert;
+  SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>> PredDelete;
+  SmallVector<NodePtr, 1> Empty;
+
+  public:
+  GraphDiff () {}
+  GraphDiff (ArrayRef<cfg::Update<NodePtr>> Updates) {
+    for (auto U : Updates) {
+      //TODO: preprocessing to remove duplicates and edges that cancel out.
+      // see: LegalizeUpdates in DomTreeConstruction.
+
+      if (U.getKind() == cfg::UpdateKind::Insert) {
+        SuccInsert[U.getFrom()].push_back(U.getTo());
+        PredInsert[U.getTo()].push_back(U.getFrom());
+      }
+      else {
+        SuccDelete[U.getFrom()].push_back(U.getTo());
+        PredDelete[U.getTo()].push_back(U.getFrom());
+      }
+    }
+  }
+
+  bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool Inverse) const {
+    auto &DeleteChildren = Inverse ? PredDelete : SuccDelete;
+    auto It = DeleteChildren.find(BB);
+    if (It == DeleteChildren.end())
+      return false;
+    auto &EdgesForBB = It->second;
+    if (llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end())
+      return true;
+    return false;
+  }
+
+  const SmallVectorImpl<NodePtr>* getAddedChildren(const NodePtr BB, bool Inverse) const {
+    auto &InsertChildren = Inverse ? PredInsert : SuccInsert;
+    auto It = InsertChildren.find(BB);
+    if (It == InsertChildren.end())
+      return &Empty;
+    return &It->second;
+  }
+};
+
+// Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
+// to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
+template <typename ItType, typename NodeRef, typename DataRef>
+class WrappedPairNodeDataIterator
+    : public iterator_adaptor_base<
+          WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
+          typename std::iterator_traits<ItType>::iterator_category,
+          NodeRef, std::ptrdiff_t, NodeRef *, NodeRef &> {
+  using BaseT = iterator_adaptor_base<
+      WrappedPairNodeDataIterator, ItType,
+      typename std::iterator_traits<ItType>::iterator_category,
+      NodeRef, std::ptrdiff_t, NodeRef *, NodeRef &>;
+
+  const DataRef DR;
+  mutable NodeRef NR;
+
+public:
+  WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
+      : BaseT(Begin), DR(DR) { NR.first = DR; }
+
+  NodeRef& operator*() const {
+    NR.second = *this->I;
+    return NR;
+  }
+};
+
+template <> struct GraphTraits<std::pair<const GraphDiff<BasicBlock*> *, BasicBlock*>> {
+  using DataRef = const GraphDiff<BasicBlock*> *;
+  using NodeRef = std::pair<DataRef, BasicBlock *>;
+
+  using SuccIterator = WrappedPairNodeDataIterator<succ_iterator, NodeRef, DataRef>;
+  struct DeletedEdgesFilter {
+    BasicBlock *BB;
+    DeletedEdgesFilter (BasicBlock *BB) : BB(BB) {};
+    bool operator()(NodeRef N) const {
+      return !N.first->ignoreChild(BB, N.second, false);
+    }
+  };
+  using FilterSuccessorsIterator =
+      filter_iterator<SuccIterator, DeletedEdgesFilter>;
+
+  using vec_iterator = SmallVectorImpl<BasicBlock*>::const_iterator;
+  using AddNewSuccessorsIterator = WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
+  using ChildIteratorType =
+      concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator>;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, false);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<SuccIterator>(
+              {succ_begin(N.second), N.first},
+              {succ_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->begin(), N.first},
+              {InsertVec->end(), N.first});
+
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, false);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<SuccIterator>(
+              {succ_end(N.second), N.first},
+              {succ_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->end(), N.first},
+              {InsertVec->end(), N.first});
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+};
+
+template <> struct GraphTraits<std::pair<const GraphDiff<BasicBlock*> *, Inverse<BasicBlock*>>> {
+  using DataRef = const GraphDiff<BasicBlock*> *;
+  using NodeRef = std::pair<DataRef, BasicBlock *>;
+
+  using PredIterator = WrappedPairNodeDataIterator<pred_iterator, NodeRef, DataRef>;
+  struct DeletedEdgesFilter {
+    BasicBlock *BB;
+    DeletedEdgesFilter (BasicBlock *BB) : BB(BB) {};
+    bool operator()(NodeRef N) const {
+      return !N.first->ignoreChild(BB, N.second, true);
+    }
+  };
+  using FilterSuccessorsIterator =
+      filter_iterator<PredIterator, DeletedEdgesFilter>;
+
+  using vec_iterator = SmallVectorImpl<BasicBlock*>::const_iterator;
+  using AddNewSuccessorsIterator = WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
+  using ChildIteratorType =
+      concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator>;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, true);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<PredIterator>(
+              {pred_begin(N.second), N.first},
+              {pred_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->begin(), N.first},
+              {InsertVec->end(), N.first});
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, true);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+          make_range<PredIterator>(
+              {pred_end(N.second), N.first},
+              {pred_end(N.second), N.first}),
+              DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewSuccessorsIterator>(
+              {InsertVec->end(), N.first},
+              {InsertVec->end(), N.first});
+    return concat_iterator<NodeRef, FilterSuccessorsIterator, AddNewSuccessorsIterator> (
+          firstit, secondit);
+  }
+};
+} // end namespace llvm
+
+#endif // LLVM_IR_CFGDIFF_H
Index: include/llvm/Support/CFGUpdate.h
===================================================================
--- /dev/null
+++ include/llvm/Support/CFGUpdate.h
@@ -0,0 +1,50 @@
+//===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the
+// Edge ends.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CFGUPDATE_H
+#define LLVM_SUPPORT_CFGUPDATE_H
+
+namespace llvm {
+namespace cfg {
+enum class UpdateKind : unsigned char { Insert, Delete };
+
+template <typename NodePtr>
+struct Update {
+  using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
+
+  NodePtr From;
+  NodeKindPair ToAndKind;
+
+  Update(UpdateKind Kind, NodePtr From, NodePtr To)
+      : From(From), ToAndKind(To, Kind) {}
+
+  UpdateKind getKind() const { return ToAndKind.getInt(); }
+  NodePtr getFrom() const { return From; }
+  NodePtr getTo() const { return ToAndKind.getPointer(); }
+  bool operator==(const Update &RHS) const {
+    return From == RHS.From && ToAndKind == RHS.ToAndKind;
+  }
+
+  friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
+    OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
+    U.getFrom()->printAsOperand(OS, false);
+    OS << " -> ";
+    U.getTo()->printAsOperand(OS, false);
+    return OS;
+  }
+};
+} // end namespace cfg
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_CFGUPDATE_H