Index: llvm/lib/Analysis/OrderedBasicBlock.cpp
===================================================================
--- llvm/lib/Analysis/OrderedBasicBlock.cpp
+++ llvm/lib/Analysis/OrderedBasicBlock.cpp
@@ -60,6 +60,27 @@
   return Inst != B;
 }
 
+namespace {
+struct LDomHistogram {
+  DenseMap<int, unsigned> DistanceFreq;
+  void addLocalDomDistance(int Distance) { DistanceFreq[Distance]++; }
+  ~LDomHistogram() {
+    std::vector<std::pair<int, unsigned>> SortedFreqs;
+    for (const auto &P : DistanceFreq)
+      SortedFreqs.push_back(P);
+    std::sort(
+        SortedFreqs.begin(), SortedFreqs.end(),
+        [](const std::pair<int, unsigned> &L,
+           const std::pair<int, unsigned> &R) { return L.first < R.first; });
+    llvm::errs() << "distance freq\n";
+    for (const auto &P : SortedFreqs) {
+      llvm::errs() << P.first << ' ' << P.second << '\n';
+    }
+  }
+};
+ManagedStatic<LDomHistogram> LDH;
+}
+
 /// Find out whether \p A dominates \p B, meaning whether \p A
 /// comes before \p B in \p BB. This is a simplification that considers
 /// cached instruction positions and ignores other basic blocks, being
@@ -69,20 +90,16 @@
          "Instructions must be in the same basic block!");
   assert(A->getParent() == BB && "Instructions must be in the tracked block!");
 
-  // First we lookup the instructions. If they don't exist, lookup will give us
-  // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
-  // exists and NB doesn't, it means NA must come before NB because we would
-  // have numbered NB as well if it didn't. The same is true for NB. If it
-  // exists, but NA does not, NA must come after it. If neither exist, we need
-  // to number the block and cache the results (by calling comesBefore).
   auto NAI = NumberedInsts.find(A);
   auto NBI = NumberedInsts.find(B);
-  if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
-    return NAI->second < NBI->second;
-  if (NAI != NumberedInsts.end())
-    return true;
-  if (NBI != NumberedInsts.end())
-    return false;
-
-  return comesBefore(A, B);
+  if (NAI == NumberedInsts.end() || NBI == NumberedInsts.end()) {
+    assert(NextInstPos == 0 && "inserted new instruction?");
+    for (const Instruction &I : *BB)
+      NumberedInsts[&I] = NextInstPos++;
+    NAI = NumberedInsts.find(A);
+    NBI = NumberedInsts.find(B);
+  }
+  assert(NAI != NumberedInsts.end() && NBI != NumberedInsts.end());
+  LDH->addLocalDomDistance(NBI->second - NAI->second);
+  return NAI->second < NBI->second;
 }