diff --git a/clang/lib/AST/ASTStructuralEquivalence.cpp b/clang/lib/AST/ASTStructuralEquivalence.cpp
index 0fa5aff..db48405 100644
--- a/clang/lib/AST/ASTStructuralEquivalence.cpp
+++ b/clang/lib/AST/ASTStructuralEquivalence.cpp
@@ -1574,20 +1574,24 @@
                                      Decl *D1, Decl *D2) {
   // FIXME: Check for known structural equivalences via a callback of some sort.
 
+  D1 = D1->getCanonicalDecl();
+  D2 = D2->getCanonicalDecl();
+  std::pair<Decl *, Decl *> P{D1, D2};
+
   // Check whether we already know that these two declarations are not
   // structurally equivalent.
-  if (Context.NonEquivalentDecls.count(
-          std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl())))
+  if (Context.NonEquivalentDecls.count(P))
     return false;
 
-  // Determine whether we've already produced a tentative equivalence for D1.
-  Decl *&EquivToD1 = Context.TentativeEquivalences[D1->getCanonicalDecl()];
-  if (EquivToD1)
-    return EquivToD1 == D2->getCanonicalDecl();
+  // Check if a check for these declarations is already pending.
+  // If yes D1 and D2 will be checked later (from DeclsToCheck),
+  // or these are already checked (and equivalent).
+  bool Inserted = Context.VisitedDecls.insert(P).second;
+  if (!Inserted)
+    return true;
 
-  // Produce a tentative equivalence D1 <-> D2, which will be checked later.
-  EquivToD1 = D2->getCanonicalDecl();
-  Context.DeclsToCheck.push_back(D1->getCanonicalDecl());
+  Context.DeclsToCheck.push(P);
+
   return true;
 }
 
@@ -1703,11 +1707,13 @@
   // Ensure that the implementation functions (all static functions in this TU)
   // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
   // because that will wreak havoc the internal state (DeclsToCheck and
-  // TentativeEquivalences members) and can cause faulty behaviour. For
-  // instance, some leaf declarations can be stated and cached as inequivalent
-  // as a side effect of one inequivalent element in the DeclsToCheck list.
+  // VisitedDecls members) and can cause faulty behaviour.
+  // In other words: Do not start a graph search from a new node with the
+  // internal data of another search in progress.
+  // FIXME: Better encapsulation and separation of internal and public
+  // functionality.
   assert(DeclsToCheck.empty());
-  assert(TentativeEquivalences.empty());
+  assert(VisitedDecls.empty());
 
   if (!::IsStructurallyEquivalent(*this, D1, D2))
     return false;
@@ -1717,7 +1723,7 @@
 
 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
   assert(DeclsToCheck.empty());
-  assert(TentativeEquivalences.empty());
+  assert(VisitedDecls.empty());
   if (!::IsStructurallyEquivalent(*this, T1, T2))
     return false;
 
@@ -1876,11 +1882,11 @@
 bool StructuralEquivalenceContext::Finish() {
   while (!DeclsToCheck.empty()) {
     // Check the next declaration.
-    Decl *D1 = DeclsToCheck.front();
-    DeclsToCheck.pop_front();
+    std::pair<Decl *, Decl *> P = DeclsToCheck.front();
+    DeclsToCheck.pop();
 
-    Decl *D2 = TentativeEquivalences[D1];
-    assert(D2 && "Unrecorded tentative equivalence?");
+    Decl *D1 = P.first;
+    Decl *D2 = P.second;
 
     bool Equivalent =
         CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
@@ -1888,8 +1894,8 @@
     if (!Equivalent) {
       // Note that these two declarations are not equivalent (and we already
       // know about it).
-      NonEquivalentDecls.insert(
-          std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl()));
+      NonEquivalentDecls.insert(P);
+
       return true;
     }
   }