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