Index: llvm/trunk/include/llvm/ADT/iterator.h
===================================================================
--- llvm/trunk/include/llvm/ADT/iterator.h
+++ llvm/trunk/include/llvm/ADT/iterator.h
@@ -334,6 +334,34 @@
                     PointerIteratorT(std::end(std::forward<RangeT>(Range))));
 }
 
+// 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;
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_ITERATOR_H
Index: llvm/trunk/include/llvm/IR/CFGDiff.h
===================================================================
--- llvm/trunk/include/llvm/IR/CFGDiff.h
+++ llvm/trunk/include/llvm/IR/CFGDiff.h
@@ -0,0 +1,286 @@
+//===- 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>
+
+// Two booleans are used to define orders in graphs:
+// InverseGraph defines when we need to reverse the whole graph and is as such
+// also equivalent to applying updates in reverse.
+// InverseEdge defines whether we want to change the edges direction. E.g., for
+// a non-inversed graph, the children are naturally the successors when
+// InverseEdge is false and the predecessors when InverseEdge is true.
+
+// We define two base clases that call into GraphDiff, one for successors
+// (CFGSuccessors), where InverseEdge is false, and one for predecessors
+// (CFGPredecessors), where InverseEdge is true.
+// FIXME: Further refactoring may merge the two base classes into a single one
+// templated / parametrized on using succ_iterator/pred_iterator and false/true
+// for the InverseEdge.
+
+// CFGViewSuccessors and CFGViewPredecessors, both can be parametrized to
+// consider the graph inverted or not (i.e. InverseGraph). Successors
+// implicitly has InverseEdge = false and Predecessors implicitly has
+// InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits
+// instantiations that follow define the value of InverseGraph.
+
+// GraphTraits instantiations:
+// - GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
+// - GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
+// - second pair item is BasicBlock *, then InverseEdge = false (so it inherits
+// from CFGViewSuccessors).
+// - second pair item is Inverse<BasicBlock *>, then InverseEdge = true (so it
+// inherits from CFGViewPredecessors).
+
+// The 4 GraphTraits are as follows:
+// 1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> :
+//        CFGViewSuccessors<false>
+// Regular CFG, children means successors, InverseGraph = false,
+// InverseEdge = false.
+// 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
+//        CFGViewSuccessors<true>
+// Reverse the graph, get successors but reverse-apply updates,
+// InverseGraph = true, InverseEdge = false.
+// 3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> :
+//        CFGViewPredecessors<false>
+// Regular CFG, reverse edges, so children mean predecessors,
+// InverseGraph = false, InverseEdge = true.
+// 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
+//        : CFGViewPredecessors<true>
+// Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.
+
+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 {
+  using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
+  UpdateMapType SuccInsert;
+  UpdateMapType SuccDelete;
+  UpdateMapType PredInsert;
+  UpdateMapType PredDelete;
+  // Using a singleton empty vector for all BasicBlock requests with no
+  // children.
+  SmallVector<NodePtr, 1> Empty;
+
+  void printMap(raw_ostream &OS, const UpdateMapType &M) const {
+    for (auto Pair : M)
+      for (auto Child : Pair.second) {
+        OS << "(";
+        Pair.first->printAsOperand(OS, false);
+        OS << ", ";
+        Child->printAsOperand(OS, false);
+        OS << ") ";
+      }
+    OS << "\n";
+  }
+
+public:
+  GraphDiff() {}
+  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates, bool InverseGraph = false) {
+    SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
+    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
+    for (auto U : LegalizedUpdates) {
+      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 InverseEdge,
+                   bool InverseGraph) const {
+    auto &DeleteChildren =
+        (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
+    auto It = DeleteChildren.find(BB);
+    if (It == DeleteChildren.end())
+      return false;
+    auto &EdgesForBB = It->second;
+    return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
+  }
+
+  iterator_range<typename SmallVectorImpl<NodePtr>::const_iterator>
+  getAddedChildren(const NodePtr BB, bool InverseEdge,
+                   bool InverseGraph) const {
+    auto &InsertChildren =
+        (InverseEdge != InverseGraph) ? PredInsert : SuccInsert;
+    auto It = InsertChildren.find(BB);
+    if (It == InsertChildren.end())
+      return make_range(Empty.begin(), Empty.end());
+    return make_range(It->second.begin(), It->second.end());
+  }
+
+  void print(raw_ostream &OS) const {
+    OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
+          "===== (Note: notion of children/inverse_children depends on "
+          "the direction of edges and the graph.)\n";
+    OS << "Children to insert:\n\t";
+    printMap(OS, SuccInsert);
+    OS << "Children to delete:\n\t";
+    printMap(OS, SuccDelete);
+    OS << "Inverse_children to insert:\n\t";
+    printMap(OS, PredInsert);
+    OS << "Inverse_children to delete:\n\t";
+    printMap(OS, PredDelete);
+    OS << "\n";
+  }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
+#endif
+};
+
+template <bool InverseGraph = false> struct CFGViewSuccessors {
+  using DataRef = const GraphDiff<BasicBlock *> *;
+  using NodeRef = std::pair<DataRef, BasicBlock *>;
+
+  using ExistingChildIterator =
+      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, InverseGraph);
+    }
+  };
+  using FilterExistingChildrenIterator =
+      filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
+
+  using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
+  using AddNewChildrenIterator =
+      WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
+  using ChildIteratorType =
+      concat_iterator<NodeRef, FilterExistingChildrenIterator,
+                      AddNewChildrenIterator>;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, false, InverseGraph);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+        make_range<ExistingChildIterator>({succ_begin(N.second), N.first},
+                                          {succ_end(N.second), N.first}),
+        DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewChildrenIterator>(
+        {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
+
+    return concat_iterator<NodeRef, FilterExistingChildrenIterator,
+                           AddNewChildrenIterator>(firstit, secondit);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, false, InverseGraph);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+        make_range<ExistingChildIterator>({succ_end(N.second), N.first},
+                                          {succ_end(N.second), N.first}),
+        DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewChildrenIterator>(
+        {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
+
+    return concat_iterator<NodeRef, FilterExistingChildrenIterator,
+                           AddNewChildrenIterator>(firstit, secondit);
+  }
+};
+
+template <bool InverseGraph = false> struct CFGViewPredecessors {
+  using DataRef = const GraphDiff<BasicBlock *> *;
+  using NodeRef = std::pair<DataRef, BasicBlock *>;
+
+  using ExistingChildIterator =
+      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, InverseGraph);
+    }
+  };
+  using FilterExistingChildrenIterator =
+      filter_iterator<ExistingChildIterator, DeletedEdgesFilter>;
+
+  using vec_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
+  using AddNewChildrenIterator =
+      WrappedPairNodeDataIterator<vec_iterator, NodeRef, DataRef>;
+  using ChildIteratorType =
+      concat_iterator<NodeRef, FilterExistingChildrenIterator,
+                      AddNewChildrenIterator>;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, true, InverseGraph);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+        make_range<ExistingChildIterator>({pred_begin(N.second), N.first},
+                                          {pred_end(N.second), N.first}),
+        DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewChildrenIterator>(
+        {InsertVec.begin(), N.first}, {InsertVec.end(), N.first});
+
+    return concat_iterator<NodeRef, FilterExistingChildrenIterator,
+                           AddNewChildrenIterator>(firstit, secondit);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    auto InsertVec = N.first->getAddedChildren(N.second, true, InverseGraph);
+    // filter iterator init:
+    auto firstit = make_filter_range(
+        make_range<ExistingChildIterator>({pred_end(N.second), N.first},
+                                          {pred_end(N.second), N.first}),
+        DeletedEdgesFilter(N.second));
+    // new inserts iterator init:
+    auto secondit = make_range<AddNewChildrenIterator>(
+        {InsertVec.end(), N.first}, {InsertVec.end(), N.first});
+
+    return concat_iterator<NodeRef, FilterExistingChildrenIterator,
+                           AddNewChildrenIterator>(firstit, secondit);
+  }
+};
+
+template <>
+struct GraphTraits<std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>>
+    : CFGViewSuccessors<false> {};
+template <>
+struct GraphTraits<
+    std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>>
+    : CFGViewSuccessors<true> {};
+template <>
+struct GraphTraits<
+    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>>
+    : CFGViewPredecessors<false> {};
+template <>
+struct GraphTraits<
+    std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>>
+    : CFGViewPredecessors<true> {};
+} // end namespace llvm
+
+#endif // LLVM_IR_CFGDIFF_H
Index: llvm/trunk/include/llvm/Support/CFGUpdate.h
===================================================================
--- llvm/trunk/include/llvm/Support/CFGUpdate.h
+++ llvm/trunk/include/llvm/Support/CFGUpdate.h
@@ -0,0 +1,113 @@
+//===- 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
+
+#include "llvm/Support/Debug.h"
+
+namespace llvm {
+namespace cfg {
+enum class UpdateKind : unsigned char { Insert, Delete };
+
+template <typename NodePtr> class Update {
+  using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
+  NodePtr From;
+  NodeKindPair ToAndKind;
+
+public:
+  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;
+  }
+
+  void print(raw_ostream &OS) const {
+    OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
+    getFrom()->printAsOperand(OS, false);
+    OS << " -> ";
+    getTo()->printAsOperand(OS, false);
+  }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
+#endif
+};
+
+// LegalizeUpdates function simplifies updates assuming a graph structure.
+// This function serves double purpose:
+// a) It removes redundant updates, which makes it easier to reverse-apply
+//    them when traversing CFG.
+// b) It optimizes away updates that cancel each other out, as the end result
+//    is the same.
+template <typename NodePtr>
+void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
+                     SmallVectorImpl<Update<NodePtr>> &Result,
+                     bool InverseGraph) {
+  // Count the total number of inserions of each edge.
+  // Each insertion adds 1 and deletion subtracts 1. The end number should be
+  // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
+  // of updates contains multiple updates of the same kind and we assert for
+  // that case.
+  SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
+  Operations.reserve(AllUpdates.size());
+
+  for (const auto &U : AllUpdates) {
+    NodePtr From = U.getFrom();
+    NodePtr To = U.getTo();
+    if (InverseGraph)
+      std::swap(From, To); // Reverse edge for postdominators.
+
+    Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
+  }
+
+  Result.clear();
+  Result.reserve(Operations.size());
+  for (auto &Op : Operations) {
+    const int NumInsertions = Op.second;
+    assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
+    if (NumInsertions == 0)
+      continue;
+    const UpdateKind UK =
+        NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
+    Result.push_back({UK, Op.first.first, Op.first.second});
+  }
+
+  // Make the order consistent by not relying on pointer values within the
+  // set. Reuse the old Operations map.
+  // In the future, we should sort by something else to minimize the amount
+  // of work needed to perform the series of updates.
+  for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
+    const auto &U = AllUpdates[i];
+    if (!InverseGraph)
+      Operations[{U.getFrom(), U.getTo()}] = int(i);
+    else
+      Operations[{U.getTo(), U.getFrom()}] = int(i);
+  }
+
+  llvm::sort(Result.begin(), Result.end(),
+             [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) {
+               return Operations[{A.getFrom(), A.getTo()}] >
+                      Operations[{B.getFrom(), B.getTo()}];
+             });
+}
+
+} // end namespace cfg
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_CFGUPDATE_H