diff --git a/clang/lib/Tooling/NodeIntrospection.cpp b/clang/lib/Tooling/NodeIntrospection.cpp
--- a/clang/lib/Tooling/NodeIntrospection.cpp
+++ b/clang/lib/Tooling/NodeIntrospection.cpp
@@ -13,6 +13,9 @@
 #include "clang/Tooling/NodeIntrospection.h"
 
 #include "clang/AST/AST.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
@@ -40,6 +43,42 @@
   return Result;
 }
 
+/// A 3 way comparison of LHS and RHS based on call names.
+static int compareLocationCall(const LocationCall &LHS,
+                               const LocationCall &RHS) {
+  // Expand the call stacks into a vector so we can traverse it in reverse
+  // order.
+  llvm::SmallVector<const LocationCall *> Left, Right;
+  for (const LocationCall *Item = &LHS; Item; Item = Item->on())
+    Left.push_back(Item);
+  for (const LocationCall *Item = &RHS; Item; Item = Item->on())
+    Right.push_back(Item);
+
+  auto LI = Left.rbegin(), LE = Left.rend(), RI = Right.rbegin();
+  // It's common for 2 location calls to start with the same prefix:
+  // getTypeSourceInfo()->getTypeLoc().getAs<..>().getLocalSourceRange()
+  // getTypeSourceInfo()->getTypeLoc().getLocalSourceRange()
+  // We can use pointer identity to quickly try and skip these cases.
+  for (; LI != LE && *LI == *RI; *LI++, *RI++)
+    assert(RI != Right.rend());
+  for (; LI != LE; ++LI, ++RI) {
+    // If we haven't returned up to here, both call stacks are the same up the
+    // here are the same. If we detect that RI is at the end, that means the
+    // rights last item was a SourceLocation/Range accessor. Therefore the
+    // preceding item in left should also return a Loc/Range and it should be
+    // the last item in its stack.
+    assert(RI != Right.rend());
+    if (auto Strcmp = (*LI)->name().compare((*RI)->name()))
+      return Strcmp;
+    // As both calls are the same, they should both either return by value or
+    // both return by pointer.
+    assert((*LI)->returnsPointer() == (*RI)->returnsPointer());
+  }
+  // As before but flipped.
+  assert(RI == Right.rend());
+  return 0;
+}
+
 namespace internal {
 bool RangeLessThan::operator()(
     std::pair<SourceRange, SharedLocationCall> const &LHS,
@@ -57,15 +96,13 @@
   else if (LHS.first.getEnd() != RHS.first.getEnd())
     return false;
 
-  return LocationCallFormatterCpp::format(*LHS.second) <
-         LocationCallFormatterCpp::format(*RHS.second);
+  return compareLocationCall(*LHS.second, *RHS.second) < 0;
 }
 bool RangeLessThan::operator()(
     std::pair<SourceLocation, SharedLocationCall> const &LHS,
     std::pair<SourceLocation, SharedLocationCall> const &RHS) const {
   if (LHS.first == RHS.first)
-    return LocationCallFormatterCpp::format(*LHS.second) <
-           LocationCallFormatterCpp::format(*RHS.second);
+    return compareLocationCall(*LHS.second, *RHS.second) < 0;
   return LHS.first < RHS.first;
 }
 } // namespace internal