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 namespace {
  20   class CountArangeDescriptors {
  21   public:
  22     CountArangeDescriptors(uint32_t &count_ref) : Count(count_ref) {}
  23     void operator()(const DWARFDebugArangeSet &Set) {
  24       Count += Set.getNumDescriptors();
  25     }
  26     uint32_t &Count;
  27   };
  28
  29   class AddArangeDescriptors {
  30   public:
  31     AddArangeDescriptors(DWARFDebugAranges::RangeColl &Ranges,
  32                          DWARFDebugAranges::ParsedCUOffsetColl &CUOffsets)
  33       : RangeCollection(Ranges),
  34         CUOffsetCollection(CUOffsets) {}
  35     void operator()(const DWARFDebugArangeSet &Set) {
  36       DWARFDebugAranges::Range Range;
  37       Range.CUOffset = Set.getCompileUnitDIEOffset();
  38       CUOffsetCollection.insert(Range.CUOffset);
  39
  40       for (uint32_t i = 0, n = Set.getNumDescriptors(); i < n; ++i) {
  41         const DWARFDebugArangeSet::Descriptor *ArangeDescPtr =
  42             Set.getDescriptor(i);
  43         Range.LowPC = ArangeDescPtr->Address;
  44         Range.Length = ArangeDescPtr->Length;
  45
  46         // Insert each item in increasing address order so binary searching
  47         // can later be done!
  48         DWARFDebugAranges::RangeColl::iterator InsertPos =
  49           std::lower_bound(RangeCollection.begin(), RangeCollection.end(),
  50                            Range);
  51         RangeCollection.insert(InsertPos, Range);
  52       }
  53
  54     }
  55     DWARFDebugAranges::RangeColl &RangeCollection;
  56     DWARFDebugAranges::ParsedCUOffsetColl &CUOffsetCollection;
  57   };
  58 }
  59
  60 void DWARFDebugAranges::extract(DataExtractor DebugArangesData) {
  61   if (!DebugArangesData.isValidOffset(0))
  62     return;
  63   uint32_t offset = 0;
  64
  65   typedef std::vector<DWARFDebugArangeSet> SetCollection;
  66   SetCollection sets;
  67
  68   DWARFDebugArangeSet set;
  69   Range range;
  70   while (set.extract(DebugArangesData, &offset))
  71     sets.push_back(set);
  72
  73   uint32_t count = 0;
  74
  75   std::for_each(sets.begin(), sets.end(), CountArangeDescriptors(count));
  76
  77   if (count > 0) {
  78     Aranges.reserve(count);
  79     AddArangeDescriptors range_adder(Aranges, ParsedCUOffsets);
  80     std::for_each(sets.begin(), sets.end(), range_adder);
  81   }
  82 }
  83
  84 void DWARFDebugAranges::generate(DWARFContext *CTX) {
  85   if (CTX) {
  86     const uint32_t num_compile_units = CTX->getNumCompileUnits();
  87     for (uint32_t cu_idx = 0; cu_idx < num_compile_units; ++cu_idx) {
  88       if (DWARFCompileUnit *cu = CTX->getCompileUnitAtIndex(cu_idx)) {
  89         uint32_t CUOffset = cu->getOffset();
  90         if (ParsedCUOffsets.insert(CUOffset).second)
  91           cu->buildAddressRangeTable(this, true, CUOffset);
  92       }
  93     }
  94   }
  95   sortAndMinimize();
  96 }
  97
  98 void DWARFDebugAranges::dump(raw_ostream &OS) const {
  99   for (RangeCollIterator I = Aranges.begin(), E = Aranges.end(); I != E; ++I) {
 100     I->dump(OS);
 101   }
 102 }
 103
 104 void DWARFDebugAranges::Range::dump(raw_ostream &OS) const {
 105   OS << format("{0x%8.8x}: [0x%8.8" PRIx64 " - 0x%8.8" PRIx64 ")\n",
 106                CUOffset, LowPC, HighPC());
 107 }
 108
 109 void DWARFDebugAranges::appendRange(uint32_t CUOffset, uint64_t LowPC,
 110                                     uint64_t HighPC) {
 111   if (!Aranges.empty()) {
 112     if (Aranges.back().CUOffset == CUOffset &&
 113         Aranges.back().HighPC() == LowPC) {
 114       Aranges.back().setHighPC(HighPC);
 115       return;
 116     }
 117   }
 118   Aranges.push_back(Range(LowPC, HighPC, CUOffset));
 119 }
 120
 121 void DWARFDebugAranges::sortAndMinimize() {
 122   const size_t orig_arange_size = Aranges.size();
 123   // Size of one? If so, no sorting is needed
 124   if (orig_arange_size <= 1)
 125     return;
 126   // Sort our address range entries
 127   std::stable_sort(Aranges.begin(), Aranges.end());
 128
 129   // Most address ranges are contiguous from function to function
 130   // so our new ranges will likely be smaller. We calculate the size
 131   // of the new ranges since although std::vector objects can be resized,
 132   // the will never reduce their allocated block size and free any excesss
 133   // memory, so we might as well start a brand new collection so it is as
 134   // small as possible.
 135
 136   // First calculate the size of the new minimal arange vector
 137   // so we don't have to do a bunch of re-allocations as we
 138   // copy the new minimal stuff over to the new collection.
 139   size_t minimal_size = 1;
 140   for (size_t i = 1; i < orig_arange_size; ++i) {
 141     if (!Range::SortedOverlapCheck(Aranges[i-1], Aranges[i]))
 142       ++minimal_size;
 143   }
 144
 145   // If the sizes are the same, then no consecutive aranges can be
 146   // combined, we are done.
 147   if (minimal_size == orig_arange_size)
 148     return;
 149
 150   // Else, make a new RangeColl that _only_ contains what we need.
 151   RangeColl minimal_aranges;
 152   minimal_aranges.resize(minimal_size);
 153   uint32_t j = 0;
 154   minimal_aranges[j] = Aranges[0];
 155   for (size_t i = 1; i < orig_arange_size; ++i) {
 156     if (Range::SortedOverlapCheck(minimal_aranges[j], Aranges[i])) {
 157       minimal_aranges[j].setHighPC(Aranges[i].HighPC());
 158     } else {
 159       // Only increment j if we aren't merging
 160       minimal_aranges[++j] = Aranges[i];
 161     }
 162   }
 163   assert(j+1 == minimal_size);
 164
 165   // Now swap our new minimal aranges into place. The local
 166   // minimal_aranges will then contian the old big collection
 167   // which will get freed.
 168   minimal_aranges.swap(Aranges);
 169 }
 170
 171 uint32_t DWARFDebugAranges::findAddress(uint64_t Address) const {
 172   if (!Aranges.empty()) {
 173     Range range(Address);
 174     RangeCollIterator begin = Aranges.begin();
 175     RangeCollIterator end = Aranges.end();
 176     RangeCollIterator pos =
 177         std::lower_bound(begin, end, range);
 178
 179     if (pos != end && pos->containsAddress(Address)) {
 180       return pos->CUOffset;
 181     } else if (pos != begin) {
 182       --pos;
 183       if (pos->containsAddress(Address))
 184         return pos->CUOffset;
 185     }
 186   }
 187   return -1U;
 188 }