Index: include/llvm/DebugInfo/DWARF/DWARFDie.h
===================================================================
--- include/llvm/DebugInfo/DWARF/DWARFDie.h
+++ include/llvm/DebugInfo/DWARF/DWARFDie.h
@@ -252,13 +252,6 @@
   void getCallerFrame(uint32_t &CallFile, uint32_t &CallLine,
                       uint32_t &CallColumn, uint32_t &CallDiscriminator) const;
   
-  /// Get inlined chain for a given address, rooted at the current DIE.
-  /// Returns empty chain if address is not contained in address range
-  /// of current DIE.
-  void
-  getInlinedChainForAddress(const uint64_t Address,
-                            SmallVectorImpl<DWARFDie> &InlinedChain) const;
-
   class attribute_iterator;
 
   /// Get an iterator range to all attributes in the current DIE only.
Index: include/llvm/DebugInfo/DWARF/DWARFUnit.h
===================================================================
--- include/llvm/DebugInfo/DWARF/DWARFUnit.h
+++ include/llvm/DebugInfo/DWARF/DWARFUnit.h
@@ -31,6 +31,7 @@
 #include <cstdint>
 #include <memory>
 #include <vector>
+#include <map>
 
 namespace llvm {
 
@@ -134,6 +135,9 @@
   uint64_t BaseAddr;
   // The compile unit debug information entry items.
   std::vector<DWARFDebugInfoEntry> DieArray;
+
+  // Map from range's start address to end address and corresponding DIE.
+  std::map<uint64_t, std::pair<uint64_t, DWARFDie>> AddrDieMap;
   typedef iterator_range<std::vector<DWARFDebugInfoEntry>::iterator>
       die_iterator_range;
 
@@ -183,6 +187,9 @@
     AddrOffsetSectionBase = Base;
   }
 
+  // Recursively update address to Die map.
+  void updateAddressDieMap(DWARFDie Die);
+
   void setRangesSection(StringRef RS, uint32_t Base) {
     RangeSection = RS;
     RangeSectionBase = Base;
Index: lib/DebugInfo/DWARF/DWARFDie.cpp
===================================================================
--- lib/DebugInfo/DWARF/DWARFDie.cpp
+++ lib/DebugInfo/DWARF/DWARFDie.cpp
@@ -352,32 +352,6 @@
   }
 }
 
-void DWARFDie::getInlinedChainForAddress(
-    const uint64_t Address, SmallVectorImpl<DWARFDie> &InlinedChain) const {
-  if (isNULL())
-    return;
-  DWARFDie DIE(*this);
-  while (DIE) {
-    // Append current DIE to inlined chain only if it has correct tag
-    // (e.g. it is not a lexical block).
-    if (DIE.isSubroutineDIE())
-      InlinedChain.push_back(DIE);
-
-    // Try to get child which also contains provided address.
-    DWARFDie Child = DIE.getFirstChild();
-    while (Child) {
-      if (Child.addressRangeContainsAddress(Address)) {
-        // Assume there is only one such child.
-        break;
-      }
-      Child = Child.getSibling();
-    }
-    DIE = Child;
-  }
-  // Reverse the obtained chain to make the root of inlined chain last.
-  std::reverse(InlinedChain.begin(), InlinedChain.end());
-}
-
 DWARFDie DWARFDie::getParent() const {
   if (isValid())
     return U->getParent(Die);
Index: lib/DebugInfo/DWARF/DWARFUnit.cpp
===================================================================
--- lib/DebugInfo/DWARF/DWARFUnit.cpp
+++ lib/DebugInfo/DWARF/DWARFUnit.cpp
@@ -343,17 +343,32 @@
     clearDIEs(true);
 }
 
+void DWARFUnit::updateAddressDieMap(DWARFDie Die) {
+  if (Die.isSubroutineDIE()) {
+    for (const auto& R : Die.getAddressRanges()) {
+      auto B = AddrDieMap.upper_bound(R.first);
+      if (B != AddrDieMap.begin() && R.first < (--B)->second.first) {
+        if (R.second < B->second.first)
+          AddrDieMap[R.second] = B->second;
+        if (R.first > B->first)
+          AddrDieMap[B->first].first = R.first;
+      }
+      AddrDieMap[R.first] = std::make_pair(R.second, Die);
+    }
+  }
+  for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
+    updateAddressDieMap(Child);
+}
+
 DWARFDie
 DWARFUnit::getSubprogramForAddress(uint64_t Address) {
   extractDIEsIfNeeded(false);
-  for (const DWARFDebugInfoEntry &D : DieArray) {
-    DWARFDie DIE(this, &D);
-    if (DIE.isSubprogramDIE() &&
-        DIE.addressRangeContainsAddress(Address)) {
-      return DIE;
-    }
-  }
-  return DWARFDie();
+  if (AddrDieMap.empty())
+    for (const DWARFDebugInfoEntry &D : DieArray)
+      if (D.getDepth() == 0)
+        updateAddressDieMap(DWARFDie(this, &D));
+  auto R = AddrDieMap.upper_bound(Address);
+  return R == AddrDieMap.begin() ? DWARFDie() : (--R)->second.second;
 }
 
 void
@@ -370,9 +385,13 @@
     SubprogramDIE = getSubprogramForAddress(Address);
 
   // Get inlined chain rooted at this subprogram DIE.
-  if (SubprogramDIE)
-    SubprogramDIE.getInlinedChainForAddress(Address, InlinedChain);
-  else
+  if (SubprogramDIE) {
+    while (SubprogramDIE) {
+      if (SubprogramDIE.isSubroutineDIE())
+        InlinedChain.push_back(SubprogramDIE);
+      SubprogramDIE = SubprogramDIE.getParent();
+    }
+  } else
     InlinedChain.clear();
 }