Index: include/clang/Tooling/ASTDiff/ASTDiff.h
===================================================================
--- include/clang/Tooling/ASTDiff/ASTDiff.h
+++ include/clang/Tooling/ASTDiff/ASTDiff.h
@@ -62,6 +62,7 @@
   ~ASTDiff();
 
   const Node *getMapped(NodeRef N) const;
+  ChangeKind getNodeChange(NodeRef N) const;
 
   class Impl;
 
@@ -106,10 +107,9 @@
 struct Node {
   SyntaxTree::Impl &Tree;
   NodeId Parent, LeftMostDescendant, RightMostDescendant;
-  int Depth, Height, Shift = 0;
+  int Depth, Height;
   ast_type_traits::DynTypedNode ASTNode;
   SmallVector<NodeId, 4> Children;
-  ChangeKind Change = NoChange;
   Node(SyntaxTree::Impl &Tree) : Tree(Tree), Children() {}
   Node(NodeRef Other) = delete;
   explicit Node(Node &&Other) = default;
Index: lib/Tooling/ASTDiff/ASTDiff.cpp
===================================================================
--- lib/Tooling/ASTDiff/ASTDiff.cpp
+++ lib/Tooling/ASTDiff/ASTDiff.cpp
@@ -32,12 +32,22 @@
   return (N1.isMacro() && N2.isMacro()) || N1.getType().isSame(N2.getType());
 }
 
+namespace {
+struct NodeChange {
+  ChangeKind Change = NoChange;
+  int Shift = 0;
+  NodeChange() = default;
+  NodeChange(ChangeKind Change, int Shift) : Change(Change), Shift(Shift) {}
+};
+} // end anonymous namespace
+
 class ASTDiff::Impl {
 private:
   std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
 
 public:
   SyntaxTree::Impl &T1, &T2;
+  std::map<NodeId, NodeChange> ChangesT1, ChangesT2;
 
   Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
        const ComparisonOptions &Options);
@@ -50,6 +60,8 @@
 
   const Node *getMapped(NodeRef N) const;
 
+  ChangeKind getNodeChange(NodeRef N) const;
+
 private:
   // Adds a mapping between two nodes.
   void link(NodeRef N1, NodeRef N2);
@@ -150,8 +162,8 @@
   PreorderIterator end() const { return begin() + getSize(); }
 
   NodeRef getNode(NodeId Id) const { return Nodes[Id]; }
-  Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
-  Node &getMutableNode(NodeRef N) { return getMutableNode(N.getId()); }
+  Node &getMutableNode(NodeRef N) { return Nodes[N.getId()]; }
+  Node &getMutableNode(NodeId Id) { return getMutableNode(getNode(Id)); }
 
 private:
   void initTree();
@@ -1091,16 +1103,12 @@
 
 void ASTDiff::Impl::computeChangeKinds() {
   for (NodeRef N1 : T1) {
-    if (!getDst(N1)) {
-      T1.getMutableNode(N1).Change = Delete;
-      T1.getMutableNode(N1).Shift -= 1;
-    }
+    if (!getDst(N1))
+      ChangesT1.emplace(N1.getId(), NodeChange(Delete, -1));
   }
   for (NodeRef N2 : T2) {
-    if (!getSrc(N2)) {
-      T2.getMutableNode(N2).Change = Insert;
-      T2.getMutableNode(N2).Shift -= 1;
-    }
+    if (!getSrc(N2))
+      ChangesT2.emplace(N2.getId(), NodeChange(Insert, -1));
   }
   for (NodeRef N1 : T1.NodesBfs) {
     if (!getDst(N1))
@@ -1108,23 +1116,22 @@
     NodeRef N2 = *getDst(N1);
     if (!haveSameParents(N1, N2) ||
         findNewPosition(N1) != findNewPosition(N2)) {
-      T1.getMutableNode(N1).Shift -= 1;
-      T2.getMutableNode(N2).Shift -= 1;
+      ChangesT1[N1.getId()].Shift -= 1;
+      ChangesT2[N2.getId()].Shift -= 1;
     }
   }
   for (NodeRef N2 : T2.NodesBfs) {
     if (!getSrc(N2))
       continue;
     NodeRef N1 = *getSrc(N2);
-    Node &MutableN1 = T1.getMutableNode(N1);
-    Node &MutableN2 = T2.getMutableNode(N2);
     if (!haveSameParents(N1, N2) ||
         findNewPosition(N1) != findNewPosition(N2)) {
-      MutableN1.Change = MutableN2.Change = Move;
+      ChangesT1[N1.getId()].Change = ChangesT2[N2.getId()].Change = Move;
     }
     if (areNodesDifferent(N1, N2)) {
-      MutableN1.Change = MutableN2.Change =
-          (N1.Change == Move ? UpdateMove : Update);
+      bool Moved = ChangesT1[N1.getId()].Change == Move;
+      ChangesT1[N1.getId()].Change = ChangesT2[N2.getId()].Change =
+          (Moved ? UpdateMove : Update);
     }
   }
 }
@@ -1152,17 +1159,37 @@
 }
 
 int ASTDiff::Impl::findNewPosition(NodeRef N) const {
+  const std::map<NodeId, NodeChange> *Changes;
+  if (&N.Tree == &T1)
+    Changes = &ChangesT1;
+  else
+    Changes = &ChangesT2;
+
   if (!N.getParent())
     return 0;
   int Position = N.findPositionInParent();
   for (NodeRef Sibling : *N.getParent()) {
-    Position += Sibling.Shift;
+    if (Changes->count(Sibling.getId()))
+      Position += Changes->at(Sibling.getId()).Shift;
     if (&Sibling == &N)
       return Position;
   }
   llvm_unreachable("Node not found amongst parent's children.");
 }
 
+ChangeKind ASTDiff::Impl::getNodeChange(NodeRef N) const {
+  const std::map<NodeId, NodeChange> *Changes;
+  if (&N.Tree == &T1) {
+    Changes = &ChangesT1;
+  } else {
+    assert(&N.Tree == &T2 && "Invalid tree.");
+    Changes = &ChangesT2;
+  }
+  if (Changes->count(N.getId()))
+    return Changes->at(N.getId()).Change;
+  return NoChange;
+}
+
 ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
                  const ComparisonOptions &Options)
     : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
@@ -1173,6 +1200,10 @@
   return DiffImpl->getMapped(N);
 }
 
+ChangeKind ASTDiff::getNodeChange(NodeRef N) const {
+  return DiffImpl->getNodeChange(N);
+}
+
 SyntaxTree::SyntaxTree(ASTUnit &AST)
     : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
           this, AST.getASTContext().getTranslationUnitDecl(), AST)) {}
Index: tools/clang-diff/ClangDiff.cpp
===================================================================
--- tools/clang-diff/ClangDiff.cpp
+++ tools/clang-diff/ClangDiff.cpp
@@ -298,10 +298,11 @@
   OS << "<span id='" << MyTag << Node.getId() << "' "
      << "tid='" << OtherTag << TargetId << "' ";
   OS << "title='";
+  diff::ChangeKind Change = Diff.getNodeChange(Node);
   printHtml(OS, Node.getTypeLabel());
   OS << "\n" << LeftId << " -> " << RightId << "'";
-  if (Node.Change != diff::NoChange)
-    OS << " class='" << getChangeKindAbbr(Node.Change) << "'";
+  if (Change != diff::NoChange)
+    OS << " class='" << getChangeKindAbbr(Change) << "'";
   OS << ">";
 
   for (diff::NodeRef Child : Node)
@@ -399,7 +400,8 @@
                            diff::SyntaxTree &SrcTree, diff::SyntaxTree &DstTree,
                            diff::NodeRef Dst) {
   const diff::Node *Src = Diff.getMapped(Dst);
-  switch (Dst.Change) {
+  diff::ChangeKind Change = Diff.getNodeChange(Dst);
+  switch (Change) {
   case diff::NoChange:
     break;
   case diff::Delete:
@@ -412,11 +414,11 @@
   case diff::Insert:
   case diff::Move:
   case diff::UpdateMove:
-    if (Dst.Change == diff::Insert)
+    if (Change == diff::Insert)
       OS << "Insert";
-    else if (Dst.Change == diff::Move)
+    else if (Change == diff::Move)
       OS << "Move";
-    else if (Dst.Change == diff::UpdateMove)
+    else if (Change == diff::UpdateMove)
       OS << "Update and Move";
     OS << " ";
     printNode(OS, DstTree, Dst);