1 //===-- DWARFDebugAranges.cpp -----------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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"
20 class CountArangeDescriptors {
22 CountArangeDescriptors(uint32_t &count_ref) : Count(count_ref) {}
23 void operator()(const DWARFDebugArangeSet &Set) {
24 Count += Set.getNumDescriptors();
29 class AddArangeDescriptors {
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);
40 for (uint32_t i = 0, n = Set.getNumDescriptors(); i < n; ++i) {
41 const DWARFDebugArangeSet::Descriptor *ArangeDescPtr =
43 Range.LowPC = ArangeDescPtr->Address;
44 Range.Length = ArangeDescPtr->Length;
46 // Insert each item in increasing address order so binary searching
48 DWARFDebugAranges::RangeColl::iterator InsertPos =
49 std::lower_bound(RangeCollection.begin(), RangeCollection.end(),
51 RangeCollection.insert(InsertPos, Range);
55 DWARFDebugAranges::RangeColl &RangeCollection;
56 DWARFDebugAranges::ParsedCUOffsetColl &CUOffsetCollection;
60 void DWARFDebugAranges::extract(DataExtractor DebugArangesData) {
61 if (!DebugArangesData.isValidOffset(0))
65 typedef std::vector<DWARFDebugArangeSet> SetCollection;
68 DWARFDebugArangeSet set;
70 while (set.extract(DebugArangesData, &offset))
75 std::for_each(sets.begin(), sets.end(), CountArangeDescriptors(count));
78 Aranges.reserve(count);
79 AddArangeDescriptors range_adder(Aranges, ParsedCUOffsets);
80 std::for_each(sets.begin(), sets.end(), range_adder);
84 void DWARFDebugAranges::generate(DWARFContext *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);
98 void DWARFDebugAranges::dump(raw_ostream &OS) const {
99 for (RangeCollIterator I = Aranges.begin(), E = Aranges.end(); I != E; ++I) {
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());
109 void DWARFDebugAranges::appendRange(uint32_t CUOffset, uint64_t LowPC,
111 if (!Aranges.empty()) {
112 if (Aranges.back().CUOffset == CUOffset &&
113 Aranges.back().HighPC() == LowPC) {
114 Aranges.back().setHighPC(HighPC);
118 Aranges.push_back(Range(LowPC, HighPC, CUOffset));
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)
126 // Sort our address range entries
127 std::stable_sort(Aranges.begin(), Aranges.end());
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.
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]))
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)
150 // Else, make a new RangeColl that _only_ contains what we need.
151 RangeColl minimal_aranges;
152 minimal_aranges.resize(minimal_size);
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());
159 // Only increment j if we aren't merging
160 minimal_aranges[++j] = Aranges[i];
163 assert(j+1 == minimal_size);
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);
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);
179 if (pos != end && pos->containsAddress(Address)) {
180 return pos->CUOffset;
181 } else if (pos != begin) {
183 if (pos->containsAddress(Address))
184 return pos->CUOffset;