1226584Sdim//===-- DWARFDebugAranges.cpp -----------------------------------*- C++ -*-===// 2226584Sdim// 3226584Sdim// The LLVM Compiler Infrastructure 4226584Sdim// 5226584Sdim// This file is distributed under the University of Illinois Open Source 6226584Sdim// License. See LICENSE.TXT for details. 7226584Sdim// 8226584Sdim//===----------------------------------------------------------------------===// 9226584Sdim 10226584Sdim#include "DWARFDebugAranges.h" 11226584Sdim#include "DWARFCompileUnit.h" 12226584Sdim#include "DWARFContext.h" 13226584Sdim#include "llvm/Support/Format.h" 14226584Sdim#include "llvm/Support/raw_ostream.h" 15226584Sdim#include <algorithm> 16226584Sdim#include <cassert> 17226584Sdimusing namespace llvm; 18226584Sdim 19263508Sdimvoid DWARFDebugAranges::extract(DataExtractor DebugArangesData) { 20263508Sdim if (!DebugArangesData.isValidOffset(0)) 21263508Sdim return; 22263508Sdim uint32_t Offset = 0; 23263508Sdim typedef std::vector<DWARFDebugArangeSet> RangeSetColl; 24263508Sdim RangeSetColl Sets; 25263508Sdim DWARFDebugArangeSet Set; 26263508Sdim uint32_t TotalRanges = 0; 27226584Sdim 28263508Sdim while (Set.extract(DebugArangesData, &Offset)) { 29263508Sdim Sets.push_back(Set); 30263508Sdim TotalRanges += Set.getNumDescriptors(); 31263508Sdim } 32263508Sdim if (TotalRanges == 0) 33263508Sdim return; 34226584Sdim 35263508Sdim Aranges.reserve(TotalRanges); 36263508Sdim for (RangeSetColl::const_iterator I = Sets.begin(), E = Sets.end(); I != E; 37263508Sdim ++I) { 38263508Sdim uint32_t CUOffset = I->getCompileUnitDIEOffset(); 39226584Sdim 40263508Sdim for (uint32_t i = 0, n = I->getNumDescriptors(); i < n; ++i) { 41263508Sdim const DWARFDebugArangeSet::Descriptor *ArangeDescPtr = 42263508Sdim I->getDescriptor(i); 43263508Sdim uint64_t LowPC = ArangeDescPtr->Address; 44263508Sdim uint64_t HighPC = LowPC + ArangeDescPtr->Length; 45263508Sdim appendRange(CUOffset, LowPC, HighPC); 46226584Sdim } 47263508Sdim } 48226584Sdim} 49226584Sdim 50263508Sdimvoid DWARFDebugAranges::generate(DWARFContext *CTX) { 51263508Sdim clear(); 52263508Sdim if (!CTX) 53263508Sdim return; 54226584Sdim 55263508Sdim // Extract aranges from .debug_aranges section. 56263508Sdim DataExtractor ArangesData(CTX->getARangeSection(), CTX->isLittleEndian(), 0); 57263508Sdim extract(ArangesData); 58226584Sdim 59263508Sdim // Generate aranges from DIEs: even if .debug_aranges section is present, 60263508Sdim // it may describe only a small subset of compilation units, so we need to 61263508Sdim // manually build aranges for the rest of them. 62263508Sdim for (uint32_t i = 0, n = CTX->getNumCompileUnits(); i < n; ++i) { 63263508Sdim if (DWARFCompileUnit *CU = CTX->getCompileUnitAtIndex(i)) { 64263508Sdim uint32_t CUOffset = CU->getOffset(); 65263508Sdim if (ParsedCUOffsets.insert(CUOffset).second) 66263508Sdim CU->buildAddressRangeTable(this, true, CUOffset); 67226584Sdim } 68226584Sdim } 69226584Sdim 70263508Sdim sortAndMinimize(); 71226584Sdim} 72226584Sdim 73263508Sdimvoid DWARFDebugAranges::appendRange(uint32_t CUOffset, uint64_t LowPC, 74263508Sdim uint64_t HighPC) { 75226584Sdim if (!Aranges.empty()) { 76263508Sdim if (Aranges.back().CUOffset == CUOffset && 77263508Sdim Aranges.back().HighPC() == LowPC) { 78263508Sdim Aranges.back().setHighPC(HighPC); 79226584Sdim return; 80226584Sdim } 81226584Sdim } 82263508Sdim Aranges.push_back(Range(LowPC, HighPC, CUOffset)); 83226584Sdim} 84226584Sdim 85263508Sdimvoid DWARFDebugAranges::sortAndMinimize() { 86226584Sdim const size_t orig_arange_size = Aranges.size(); 87226584Sdim // Size of one? If so, no sorting is needed 88226584Sdim if (orig_arange_size <= 1) 89226584Sdim return; 90226584Sdim // Sort our address range entries 91263508Sdim std::stable_sort(Aranges.begin(), Aranges.end()); 92226584Sdim 93226584Sdim // Most address ranges are contiguous from function to function 94226584Sdim // so our new ranges will likely be smaller. We calculate the size 95226584Sdim // of the new ranges since although std::vector objects can be resized, 96226584Sdim // the will never reduce their allocated block size and free any excesss 97226584Sdim // memory, so we might as well start a brand new collection so it is as 98226584Sdim // small as possible. 99226584Sdim 100226584Sdim // First calculate the size of the new minimal arange vector 101226584Sdim // so we don't have to do a bunch of re-allocations as we 102226584Sdim // copy the new minimal stuff over to the new collection. 103226584Sdim size_t minimal_size = 1; 104226584Sdim for (size_t i = 1; i < orig_arange_size; ++i) { 105263508Sdim if (!Range::SortedOverlapCheck(Aranges[i-1], Aranges[i])) 106226584Sdim ++minimal_size; 107226584Sdim } 108226584Sdim 109226584Sdim // If the sizes are the same, then no consecutive aranges can be 110226584Sdim // combined, we are done. 111226584Sdim if (minimal_size == orig_arange_size) 112226584Sdim return; 113226584Sdim 114226584Sdim // Else, make a new RangeColl that _only_ contains what we need. 115226584Sdim RangeColl minimal_aranges; 116226584Sdim minimal_aranges.resize(minimal_size); 117226584Sdim uint32_t j = 0; 118226584Sdim minimal_aranges[j] = Aranges[0]; 119226584Sdim for (size_t i = 1; i < orig_arange_size; ++i) { 120263508Sdim if (Range::SortedOverlapCheck(minimal_aranges[j], Aranges[i])) { 121263508Sdim minimal_aranges[j].setHighPC(Aranges[i].HighPC()); 122226584Sdim } else { 123226584Sdim // Only increment j if we aren't merging 124226584Sdim minimal_aranges[++j] = Aranges[i]; 125226584Sdim } 126226584Sdim } 127263508Sdim assert(j+1 == minimal_size); 128226584Sdim 129226584Sdim // Now swap our new minimal aranges into place. The local 130226584Sdim // minimal_aranges will then contian the old big collection 131226584Sdim // which will get freed. 132226584Sdim minimal_aranges.swap(Aranges); 133226584Sdim} 134226584Sdim 135263508Sdimuint32_t DWARFDebugAranges::findAddress(uint64_t Address) const { 136226584Sdim if (!Aranges.empty()) { 137263508Sdim Range range(Address); 138226584Sdim RangeCollIterator begin = Aranges.begin(); 139226584Sdim RangeCollIterator end = Aranges.end(); 140263508Sdim RangeCollIterator pos = 141263508Sdim std::lower_bound(begin, end, range); 142226584Sdim 143263508Sdim if (pos != end && pos->containsAddress(Address)) { 144263508Sdim return pos->CUOffset; 145226584Sdim } else if (pos != begin) { 146226584Sdim --pos; 147263508Sdim if (pos->containsAddress(Address)) 148263508Sdim return pos->CUOffset; 149226584Sdim } 150226584Sdim } 151226584Sdim return -1U; 152226584Sdim} 153