3 files changed, 29 insertions, 8 deletions
diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h
index 3197d3a7389..8b8a35573e7 100644
--- a/llvm/include/llvm/ADT/STLExtras.h
+++ b/llvm/include/llvm/ADT/STLExtras.h
@@ -1130,6 +1130,13 @@ auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
 }
 
+/// Provide wrappers to std::upper_bound which take ranges instead of having to
+/// pass begin/end explicitly.
+template <typename R, typename ForwardIt>
+auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
+  return std::upper_bound(adl_begin(Range), adl_end(Range), I);
+}
+
 /// Wrapper function around std::equal to detect if all elements
 /// in a container are same.
 template <typename R>
diff --git a/llvm/include/llvm/DebugInfo/DWARF/DWARFUnitIndex.h b/llvm/include/llvm/DebugInfo/DWARF/DWARFUnitIndex.h
index 49ed4bb222f..16be5f9401c 100644
--- a/llvm/include/llvm/DebugInfo/DWARF/DWARFUnitIndex.h
+++ b/llvm/include/llvm/DebugInfo/DWARF/DWARFUnitIndex.h
@@ -74,6 +74,7 @@ private:
   int InfoColumn = -1;
   std::unique_ptr<DWARFSectionKind[]> ColumnKinds;
   std::unique_ptr<Entry[]> Rows;
+  mutable std::vector<Entry *> OffsetLookup;
 
   static StringRef getColumnHeader(DWARFSectionKind DS);
 
diff --git a/llvm/lib/DebugInfo/DWARF/DWARFUnitIndex.cpp b/llvm/lib/DebugInfo/DWARF/DWARFUnitIndex.cpp
index 17f17572a30..3b39bf58b3c 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFUnitIndex.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFUnitIndex.cpp
@@ -164,14 +164,27 @@ DWARFUnitIndex::Entry::getOffset() const {
 
 const DWARFUnitIndex::Entry *
 DWARFUnitIndex::getFromOffset(uint32_t Offset) const {
-  for (uint32_t i = 0; i != Header.NumBuckets; ++i)
-    if (const auto &Contribs = Rows[i].Contributions) {
-      const auto &InfoContrib = Contribs[InfoColumn];
-      if (InfoContrib.Offset <= Offset &&
-          Offset < (InfoContrib.Offset + InfoContrib.Length))
-        return &Rows[i];
-    }
-  return nullptr;
+  if (OffsetLookup.empty()) {
+    for (uint32_t i = 0; i != Header.NumBuckets; ++i)
+      if (const auto &Contribs = Rows[i].Contributions)
+        OffsetLookup.push_back(&Rows[i]);
+    llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
+      return E1->Contributions[InfoColumn].Offset <
+             E2->Contributions[InfoColumn].Offset;
+    });
+  }
+  auto I =
+      llvm::upper_bound(OffsetLookup, Offset, [&](uint32_t Offset, Entry *E2) {
+        return Offset < E2->Contributions[InfoColumn].Offset;
+      });
+  if (I == OffsetLookup.begin())
+    return nullptr;
+  --I;
+  const auto *E = *I;
+  const auto &InfoContrib = E->Contributions[InfoColumn];
+  if ((InfoContrib.Offset + InfoContrib.Length) <= Offset)
+    return nullptr;
+  return E;
 }
 
 const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {