llvm/lib/DebugInfo/LogicalView/Core/LVRange.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-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
  17 using namespace llvm;
  18 using namespace llvm::logicalview;
  19
  20 #define DEBUG_TYPE "Range"
  21
  22 void 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.
  52 void 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
  68 void 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.
  83 LVScope *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.
 109 LVScope *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].
 118 bool 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.
 127 void 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
 145 void 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 }