1//===-- LVRange.cpp -------------------------------------------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This implements the LVRange class. 10// 11//===----------------------------------------------------------------------===// 12 13#include "llvm/DebugInfo/LogicalView/Core/LVRange.h" 14#include "llvm/DebugInfo/LogicalView/Core/LVLocation.h" 15#include "llvm/DebugInfo/LogicalView/Core/LVOptions.h" 16 17using namespace llvm; 18using namespace llvm::logicalview; 19 20#define DEBUG_TYPE "Range" 21 22void LVRange::startSearch() { 23 RangesTree.clear(); 24 25 LLVM_DEBUG({ dbgs() << "\nRanges Tree entries:\n"; }); 26 27 // Traverse the ranges and store them into the interval tree. 28 for (LVRangeEntry &RangeEntry : RangeEntries) { 29 LLVM_DEBUG({ 30 LVScope *Scope = RangeEntry.scope(); 31 dbgs() << "Scope: " << format_decimal(Scope->getLevel(), 5) << " " 32 << "Range: [" << hexValue(RangeEntry.lower()) << ":" 33 << hexValue(RangeEntry.upper()) << "]\n"; 34 }); 35 36 RangesTree.insert(RangeEntry.lower(), RangeEntry.upper(), 37 RangeEntry.scope()); 38 } 39 40 // Create the interval tree. 41 RangesTree.create(); 42 43 LLVM_DEBUG({ 44 dbgs() << "\nRanges Tree:\n"; 45 RangesTree.print(dbgs()); 46 }); 47} 48 49// Add the pair in an ascending order, with the smallest ranges at the 50// start; in that way, enclosing scopes ranges are at the end of the 51// list; we assume that low <= high. 52void LVRange::addEntry(LVScope *Scope, LVAddress LowerAddress, 53 LVAddress UpperAddress) { 54 // We assume the low <= high. 55 if (LowerAddress > UpperAddress) 56 std::swap(LowerAddress, UpperAddress); 57 58 // Record the lowest and highest seen addresses. 59 if (LowerAddress < Lower) 60 Lower = LowerAddress; 61 if (UpperAddress > Upper) 62 Upper = UpperAddress; 63 64 // Just add the scope and range pair, in no particular order. 65 RangeEntries.emplace_back(LowerAddress, UpperAddress, Scope); 66} 67 68void LVRange::addEntry(LVScope *Scope) { 69 assert(Scope && "Scope must not be nullptr"); 70 // Traverse the ranges and update the ranges set only if the ranges 71 // values are not already recorded. 72 if (const LVLocations *Locations = Scope->getRanges()) 73 for (const LVLocation *Location : *Locations) { 74 LVAddress LowPC = Location->getLowerAddress(); 75 LVAddress HighPC = Location->getUpperAddress(); 76 if (!hasEntry(LowPC, HighPC)) 77 // Add the pair of addresses. 78 addEntry(Scope, LowPC, HighPC); 79 } 80} 81 82// Get the scope associated with the input address. 83LVScope *LVRange::getEntry(LVAddress Address) const { 84 LLVM_DEBUG({ dbgs() << format("Searching: 0x%08x\nFound: ", Address); }); 85 86 LVScope *Target = nullptr; 87 LVLevel TargetLevel = 0; 88 LVLevel Level = 0; 89 LVScope *Scope = nullptr; 90 for (LVRangesTree::find_iterator Iter = RangesTree.find(Address), 91 End = RangesTree.find_end(); 92 Iter != End; ++Iter) { 93 LLVM_DEBUG( 94 { dbgs() << format("[0x%08x,0x%08x] ", Iter->left(), Iter->right()); }); 95 Scope = Iter->value(); 96 Level = Scope->getLevel(); 97 if (Level > TargetLevel) { 98 TargetLevel = Level; 99 Target = Scope; 100 } 101 } 102 103 LLVM_DEBUG({ dbgs() << (Scope ? "\n" : "None\n"); }); 104 105 return Target; 106} 107 108// Find the associated Scope for the given ranges values. 109LVScope *LVRange::getEntry(LVAddress LowerAddress, 110 LVAddress UpperAddress) const { 111 for (const LVRangeEntry &RangeEntry : RangeEntries) 112 if (LowerAddress >= RangeEntry.lower() && UpperAddress < RangeEntry.upper()) 113 return RangeEntry.scope(); 114 return nullptr; 115} 116 117// True if the range addresses contain the pair [LowerAddress, UpperAddress]. 118bool LVRange::hasEntry(LVAddress LowerAddress, LVAddress UpperAddress) const { 119 for (const LVRangeEntry &RangeEntry : RangeEntries) 120 if (LowerAddress == RangeEntry.lower() && 121 UpperAddress == RangeEntry.upper()) 122 return true; 123 return false; 124} 125 126// Sort the range elements for the whole Compile Unit. 127void LVRange::sort() { 128 auto CompareRangeEntry = [](const LVRangeEntry &lhs, 129 const LVRangeEntry &rhs) -> bool { 130 if (lhs.lower() < rhs.lower()) 131 return true; 132 133 // If the lower address is the same, use the upper address value in 134 // order to put first the smallest interval. 135 if (lhs.lower() == rhs.lower()) 136 return lhs.upper() < rhs.upper(); 137 138 return false; 139 }; 140 141 // Sort the ranges using low address and range size. 142 std::stable_sort(RangeEntries.begin(), RangeEntries.end(), CompareRangeEntry); 143} 144 145void LVRange::print(raw_ostream &OS, bool Full) const { 146 size_t Indentation = 0; 147 for (const LVRangeEntry &RangeEntry : RangeEntries) { 148 LVScope *Scope = RangeEntry.scope(); 149 Scope->printAttributes(OS, Full); 150 Indentation = options().indentationSize(); 151 if (Indentation) 152 OS << " "; 153 OS << format("[0x%08x,0x%08x] ", RangeEntry.lower(), RangeEntry.upper()) 154 << formattedKind(Scope->kind()) << " " << formattedName(Scope->getName()) 155 << "\n"; 156 } 157 printExtra(OS, Full); 158} 159