159 lines · cpp
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-exception6//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 the50// start; in that way, enclosing scopes ranges are at the end of the51// 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 ranges71 // 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 in134 // 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 llvm::stable_sort(RangeEntries, 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