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