contrib/llvm/lib/DebugInfo/DWARFDebugAranges.cpp

   1 //===-- DWARFDebugAranges.cpp -----------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "DWARFDebugAranges.h"
  11 #include "DWARFCompileUnit.h"
  12 #include "DWARFContext.h"
  13 #include "llvm/Support/Format.h"
  14 #include "llvm/Support/raw_ostream.h"
  15 #include <algorithm>
  16 #include <cassert>
  17 using namespace llvm;
  18
  19 void DWARFDebugAranges::extract(DataExtractor DebugArangesData) {
  20   if (!DebugArangesData.isValidOffset(0))
  21     return;
  22   uint32_t Offset = 0;
  23   typedef std::vector<DWARFDebugArangeSet> RangeSetColl;
  24   RangeSetColl Sets;
  25   DWARFDebugArangeSet Set;
  26   uint32_t TotalRanges = 0;
  27
  28   while (Set.extract(DebugArangesData, &Offset)) {
  29     Sets.push_back(Set);
  30     TotalRanges += Set.getNumDescriptors();
  31   }
  32   if (TotalRanges == 0)
  33     return;
  34
  35   Aranges.reserve(TotalRanges);
  36   for (RangeSetColl::const_iterator I = Sets.begin(), E = Sets.end(); I != E;
  37        ++I) {
  38     uint32_t CUOffset = I->getCompileUnitDIEOffset();
  39
  40     for (uint32_t i = 0, n = I->getNumDescriptors(); i < n; ++i) {
  41       const DWARFDebugArangeSet::Descriptor *ArangeDescPtr =
  42           I->getDescriptor(i);
  43       uint64_t LowPC = ArangeDescPtr->Address;
  44       uint64_t HighPC = LowPC + ArangeDescPtr->Length;
  45       appendRange(CUOffset, LowPC, HighPC);
  46     }
  47   }
  48 }
  49
  50 void DWARFDebugAranges::generate(DWARFContext *CTX) {
  51   clear();
  52   if (!CTX)
  53     return;
  54
  55   // Extract aranges from .debug_aranges section.
  56   DataExtractor ArangesData(CTX->getARangeSection(), CTX->isLittleEndian(), 0);
  57   extract(ArangesData);
  58
  59   // Generate aranges from DIEs: even if .debug_aranges section is present,
  60   // it may describe only a small subset of compilation units, so we need to
  61   // manually build aranges for the rest of them.
  62   for (uint32_t i = 0, n = CTX->getNumCompileUnits(); i < n; ++i) {
  63     if (DWARFCompileUnit *CU = CTX->getCompileUnitAtIndex(i)) {
  64       uint32_t CUOffset = CU->getOffset();
  65       if (ParsedCUOffsets.insert(CUOffset).second)
  66         CU->buildAddressRangeTable(this, true, CUOffset);
  67     }
  68   }
  69
  70   sortAndMinimize();
  71 }
  72
  73 void DWARFDebugAranges::appendRange(uint32_t CUOffset, uint64_t LowPC,
  74                                     uint64_t HighPC) {
  75   if (!Aranges.empty()) {
  76     if (Aranges.back().CUOffset == CUOffset &&
  77         Aranges.back().HighPC() == LowPC) {
  78       Aranges.back().setHighPC(HighPC);
  79       return;
  80     }
  81   }
  82   Aranges.push_back(Range(LowPC, HighPC, CUOffset));
  83 }
  84
  85 void DWARFDebugAranges::sortAndMinimize() {
  86   const size_t orig_arange_size = Aranges.size();
  87   // Size of one? If so, no sorting is needed
  88   if (orig_arange_size <= 1)
  89     return;
  90   // Sort our address range entries
  91   std::stable_sort(Aranges.begin(), Aranges.end());
  92
  93   // Most address ranges are contiguous from function to function
  94   // so our new ranges will likely be smaller. We calculate the size
  95   // of the new ranges since although std::vector objects can be resized,
  96   // the will never reduce their allocated block size and free any excesss
  97   // memory, so we might as well start a brand new collection so it is as
  98   // small as possible.
  99
 100   // First calculate the size of the new minimal arange vector
 101   // so we don't have to do a bunch of re-allocations as we
 102   // copy the new minimal stuff over to the new collection.
 103   size_t minimal_size = 1;
 104   for (size_t i = 1; i < orig_arange_size; ++i) {
 105     if (!Range::SortedOverlapCheck(Aranges[i-1], Aranges[i]))
 106       ++minimal_size;
 107   }
 108
 109   // If the sizes are the same, then no consecutive aranges can be
 110   // combined, we are done.
 111   if (minimal_size == orig_arange_size)
 112     return;
 113
 114   // Else, make a new RangeColl that _only_ contains what we need.
 115   RangeColl minimal_aranges;
 116   minimal_aranges.resize(minimal_size);
 117   uint32_t j = 0;
 118   minimal_aranges[j] = Aranges[0];
 119   for (size_t i = 1; i < orig_arange_size; ++i) {
 120     if (Range::SortedOverlapCheck(minimal_aranges[j], Aranges[i])) {
 121       minimal_aranges[j].setHighPC(Aranges[i].HighPC());
 122     } else {
 123       // Only increment j if we aren't merging
 124       minimal_aranges[++j] = Aranges[i];
 125     }
 126   }
 127   assert(j+1 == minimal_size);
 128
 129   // Now swap our new minimal aranges into place. The local
 130   // minimal_aranges will then contian the old big collection
 131   // which will get freed.
 132   minimal_aranges.swap(Aranges);
 133 }
 134
 135 uint32_t DWARFDebugAranges::findAddress(uint64_t Address) const {
 136   if (!Aranges.empty()) {
 137     Range range(Address);
 138     RangeCollIterator begin = Aranges.begin();
 139     RangeCollIterator end = Aranges.end();
 140     RangeCollIterator pos =
 141         std::lower_bound(begin, end, range);
 142
 143     if (pos != end && pos->containsAddress(Address)) {
 144       return pos->CUOffset;
 145     } else if (pos != begin) {
 146       --pos;
 147       if (pos->containsAddress(Address))
 148         return pos->CUOffset;
 149     }
 150   }
 151   return -1U;
 152 }