From b54d29735af9ddabce268c817ccc2ab3eb54d719 Mon Sep 17 00:00:00 2001
From: Ahmed Bougacha <ahmed.bougacha@gmail.com>
Date: Thu, 30 May 2013 18:18:36 +0000
Subject: [PATCH] MCObjectSymbolizer: Switch from IntervalMap to sorted vector,
 following r182625.

This removes the need for the missing SectionRef operator< workaround, and fixes
an IntervalMap assert about alignment on MSVC.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182949 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/MC/MCObjectSymbolizer.h | 15 ++++----
 lib/MC/MCObjectSymbolizer.cpp        | 56 +++++++++++++++++++++++-----
 2 files changed, 54 insertions(+), 17 deletions(-)

diff --git a/include/llvm/MC/MCObjectSymbolizer.h b/include/llvm/MC/MCObjectSymbolizer.h
index 0e3a17b8f7d..555cf5195df 100644
--- a/include/llvm/MC/MCObjectSymbolizer.h
+++ b/include/llvm/MC/MCObjectSymbolizer.h
@@ -15,10 +15,10 @@
 #ifndef LLVM_MC_MCOBJECTSYMBOLIZER_H
 #define LLVM_MC_MCOBJECTSYMBOLIZER_H
 
-#include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/MC/MCSymbolizer.h"
 #include "llvm/Object/ObjectFile.h"
+#include <vector>
 
 namespace llvm {
 
@@ -33,12 +33,8 @@ protected:
   const object::ObjectFile *Obj;
 
   typedef DenseMap<uint64_t, object::RelocationRef> AddrToRelocMap;
-  // FIXME: Working around a missing SectionRef operator!= by storing
-  // DataRefImpl.p instead of SectionRef. Feel free to improve!
-  typedef IntervalMap<uint64_t, uintptr_t> AddrToSectionMap;
-
-  AddrToSectionMap::Allocator AddrToSectionAllocator;
-  AddrToSectionMap AddrToSection;
+  typedef std::vector<object::SectionRef> SortedSectionList;
+  SortedSectionList SortedSections;
 
   // Map a load address to the first relocation that applies there. As far as I
   // know, if there are several relocations at the exact same address, they are
@@ -48,6 +44,11 @@ protected:
   // relocation (referencing the subtrahend symbol).
   AddrToRelocMap AddrToReloc;
 
+  // Helpers around SortedSections.
+  SortedSectionList::const_iterator findSectionContaining(uint64_t Addr) const;
+  void insertSection(object::SectionRef Section);
+
+
   MCObjectSymbolizer(MCContext &Ctx, OwningPtr<MCRelocationInfo> &RelInfo,
                      const object::ObjectFile *Obj);
 
diff --git a/lib/MC/MCObjectSymbolizer.cpp b/lib/MC/MCObjectSymbolizer.cpp
index 1803498991e..923c9a0d5fa 100644
--- a/lib/MC/MCObjectSymbolizer.cpp
+++ b/lib/MC/MCObjectSymbolizer.cpp
@@ -17,6 +17,7 @@
 #include "llvm/Object/MachO.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
 
 using namespace llvm;
 using namespace object;
@@ -40,15 +41,16 @@ public:
         return;
     }
     uint64_t Addr = Value;
-    AddrToSectionMap::const_iterator SI = AddrToSection.find(Addr);
-    if (SI.valid()) {
-      DataRefImpl DRI; DRI.p = *SI;
-      SectionRef S(DRI, Obj);
+    SortedSectionList::const_iterator SI = findSectionContaining(Addr);
+    errs() << " looking for sec " << Addr << "\n";
+    if (SI != SortedSections.end()) {
+      const SectionRef &S = *SI;
       StringRef Name; S.getName(Name);
+      uint64_t SAddr; S.getAddress(SAddr);
       if (Name == "__cstring") {
         StringRef Contents;
         S.getContents(Contents);
-        Contents = Contents.substr(Addr - SI.start());
+        Contents = Contents.substr(Addr - SAddr);
         cStream << " ## literal pool for: "
                 << Contents.substr(0, Contents.find_first_of(0));
       }
@@ -62,9 +64,7 @@ public:
 MCObjectSymbolizer::MCObjectSymbolizer(MCContext &Ctx,
                                        OwningPtr<MCRelocationInfo> &RelInfo,
                                        const ObjectFile *Obj)
-    : MCSymbolizer(Ctx, RelInfo), Obj(Obj),
-      AddrToSectionAllocator(), AddrToSection(AddrToSectionAllocator),
-      AddrToReloc() {
+    : MCSymbolizer(Ctx, RelInfo), Obj(Obj), SortedSections(), AddrToReloc() {
   error_code ec;
   for (section_iterator SI = Obj->begin_sections(),
                         SE = Obj->end_sections();
@@ -81,8 +81,7 @@ MCObjectSymbolizer::MCObjectSymbolizer(MCContext &Ctx,
     bool RequiredForExec; RelSecI->isRequiredForExecution(RequiredForExec);
     if (RequiredForExec == false || Size == 0)
       continue;
-    AddrToSection.insert(StartAddr, StartAddr + Size - 1,
-                         SI->getRawDataRefImpl().p);
+    insertSection(*SI);
     for (relocation_iterator RI = SI->begin_relocations(),
                              RE = SI->end_relocations();
                              RI != RE;
@@ -177,3 +176,40 @@ MCObjectSymbolizer::createObjectSymbolizer(MCContext &Ctx,
   }
   return new MCObjectSymbolizer(Ctx, RelInfo, Obj);
 }
+
+// SortedSections implementation.
+
+static bool SectionStartsBefore(const SectionRef &S, uint64_t Addr) {
+  uint64_t SAddr; S.getAddress(SAddr);
+  return SAddr < Addr;
+}
+
+MCObjectSymbolizer::SortedSectionList::const_iterator
+MCObjectSymbolizer::findSectionContaining(uint64_t Addr) const {
+  SortedSectionList::const_iterator
+    EndIt = SortedSections.end(),
+    It = std::lower_bound(SortedSections.begin(), EndIt,
+                          Addr, SectionStartsBefore);
+  if (It == EndIt)
+    return It;
+  uint64_t SAddr; It->getAddress(SAddr);
+  uint64_t SSize; It->getSize(SSize);
+  if (Addr >= SAddr + SSize)
+    return EndIt;
+  return It;
+}
+
+void MCObjectSymbolizer::insertSection(SectionRef Sec) {
+  uint64_t SAddr; Sec.getAddress(SAddr);
+  uint64_t SSize; Sec.getSize(SSize);
+  SortedSectionList::iterator It = std::lower_bound(SortedSections.begin(),
+                                                    SortedSections.end(),
+                                                    SAddr,
+                                                    SectionStartsBefore);
+  if (It != SortedSections.end()) {
+    uint64_t FoundSAddr; It->getAddress(FoundSAddr);
+    if (FoundSAddr < SAddr + SSize)
+      llvm_unreachable("Inserting overlapping sections");
+  }
+  SortedSections.insert(It, Sec);
+}
-- 
2.34.1