1 files changed, 206 insertions, 4 deletions
diff --git a/contrib/llvm-project/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp b/contrib/llvm-project/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp
index 781c1755241d..1b8c974fdcd2 100644
--- a/contrib/llvm-project/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp
+++ b/contrib/llvm-project/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp
@@ -1,14 +1,16 @@
 //===- InlineInfo.cpp -------------------------------------------*- C++ -*-===//
 //
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/GSYM/FileEntry.h"
+#include "llvm/DebugInfo/GSYM/FileWriter.h"
+#include "llvm/DebugInfo/GSYM/GsymReader.h"
 #include "llvm/DebugInfo/GSYM/InlineInfo.h"
+#include "llvm/Support/DataExtractor.h"
 #include <algorithm>
 #include <inttypes.h>
 
@@ -57,3 +59,203 @@ llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr
     return Result;
   return llvm::None;
 }
+
+/// Skip an InlineInfo object in the specified data at the specified offset.
+///
+/// Used during the InlineInfo::lookup() call to quickly skip child InlineInfo
+/// objects where the addres ranges isn't contained in the InlineInfo object
+/// or its children. This avoids allocations by not appending child InlineInfo
+/// objects to the InlineInfo::Children array.
+///
+/// \param Data The binary stream to read the data from.
+///
+/// \param Offset The byte offset within \a Data.
+///
+/// \param SkippedRanges If true, address ranges have already been skipped.
+
+static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges) {
+  if (!SkippedRanges) {
+    if (AddressRanges::skip(Data, Offset) == 0)
+      return false;
+  }
+  bool HasChildren = Data.getU8(&Offset) != 0;
+  Data.getU32(&Offset); // Skip Inline.Name.
+  Data.getULEB128(&Offset); // Skip Inline.CallFile.
+  Data.getULEB128(&Offset); // Skip Inline.CallLine.
+  if (HasChildren) {
+    while (skip(Data, Offset, false /* SkippedRanges */))
+      /* Do nothing */;
+  }
+  // We skipped a valid InlineInfo.
+  return true;
+}
+
+/// A Lookup helper functions.
+///
+/// Used during the InlineInfo::lookup() call to quickly only parse an
+/// InlineInfo object if the address falls within this object. This avoids
+/// allocations by not appending child InlineInfo objects to the
+/// InlineInfo::Children array and also skips any InlineInfo objects that do
+/// not contain the address we are looking up.
+///
+/// \param Data The binary stream to read the data from.
+///
+/// \param Offset The byte offset within \a Data.
+///
+/// \param BaseAddr The address that the relative address range offsets are
+///                 relative to.
+
+static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset,
+                   uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs,
+                   llvm::Error &Err) {
+  InlineInfo Inline;
+  Inline.Ranges.decode(Data, BaseAddr, Offset);
+  if (Inline.Ranges.empty())
+    return true;
+  // Check if the address is contained within the inline information, and if
+  // not, quickly skip this InlineInfo object and all its children.
+  if (!Inline.Ranges.contains(Addr)) {
+    skip(Data, Offset, true /* SkippedRanges */);
+    return false;
+  }
+
+  // The address range is contained within this InlineInfo, add the source
+  // location for this InlineInfo and any children that contain the address.
+  bool HasChildren = Data.getU8(&Offset) != 0;
+  Inline.Name = Data.getU32(&Offset);
+  Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
+  Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
+  if (HasChildren) {
+    // Child address ranges are encoded relative to the first address in the
+    // parent InlineInfo object.
+    const auto ChildBaseAddr = Inline.Ranges[0].Start;
+    bool Done = false;
+    while (!Done)
+      Done = lookup(GR, Data, Offset, ChildBaseAddr, Addr, SrcLocs, Err);
+  }
+
+  Optional<FileEntry> CallFile = GR.getFile(Inline.CallFile);
+  if (!CallFile) {
+    Err = createStringError(std::errc::invalid_argument,
+                            "failed to extract file[%" PRIu32 "]",
+                            Inline.CallFile);
+    return false;
+  }
+
+  SourceLocation SrcLoc;
+  SrcLoc.Name = SrcLocs.back().Name;
+  SrcLoc.Dir = GR.getString(CallFile->Dir);
+  SrcLoc.Base = GR.getString(CallFile->Base);
+  SrcLoc.Line = Inline.CallLine;
+  SrcLocs.back().Name = GR.getString(Inline.Name);
+  SrcLocs.push_back(SrcLoc);
+  return true;
+}
+
+llvm::Error InlineInfo::lookup(const GsymReader &GR, DataExtractor &Data,
+                               uint64_t BaseAddr, uint64_t Addr,
+                               SourceLocations &SrcLocs) {
+  // Call our recursive helper function starting at offset zero.
+  uint64_t Offset = 0;
+  llvm::Error Err = Error::success();
+  ::lookup(GR, Data, Offset, BaseAddr, Addr, SrcLocs, Err);
+  return Err;
+}
+
+/// Decode an InlineInfo in Data at the specified offset.
+///
+/// A local helper function to decode InlineInfo objects. This function is
+/// called recursively when parsing child InlineInfo objects.
+///
+/// \param Data The data extractor to decode from.
+/// \param Offset The offset within \a Data to decode from.
+/// \param BaseAddr The base address to use when decoding address ranges.
+/// \returns An InlineInfo or an error describing the issue that was
+/// encountered during decoding.
+static llvm::Expected<InlineInfo> decode(DataExtractor &Data, uint64_t &Offset,
+                                         uint64_t BaseAddr) {
+  InlineInfo Inline;
+  if (!Data.isValidOffset(Offset))
+    return createStringError(std::errc::io_error,
+        "0x%8.8" PRIx64 ": missing InlineInfo address ranges data", Offset);
+  Inline.Ranges.decode(Data, BaseAddr, Offset);
+  if (Inline.Ranges.empty())
+    return Inline;
+  if (!Data.isValidOffsetForDataOfSize(Offset, 1))
+    return createStringError(std::errc::io_error,
+        "0x%8.8" PRIx64 ": missing InlineInfo uint8_t indicating children",
+        Offset);
+  bool HasChildren = Data.getU8(&Offset) != 0;
+  if (!Data.isValidOffsetForDataOfSize(Offset, 4))
+    return createStringError(std::errc::io_error,
+        "0x%8.8" PRIx64 ": missing InlineInfo uint32_t for name", Offset);
+  Inline.Name = Data.getU32(&Offset);
+  if (!Data.isValidOffset(Offset))
+    return createStringError(std::errc::io_error,
+        "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call file", Offset);
+  Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
+  if (!Data.isValidOffset(Offset))
+    return createStringError(std::errc::io_error,
+        "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call line", Offset);
+  Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
+  if (HasChildren) {
+    // Child address ranges are encoded relative to the first address in the
+    // parent InlineInfo object.
+    const auto ChildBaseAddr = Inline.Ranges[0].Start;
+    while (true) {
+      llvm::Expected<InlineInfo> Child = decode(Data, Offset, ChildBaseAddr);
+      if (!Child)
+        return Child.takeError();
+      // InlineInfo with empty Ranges termintes a child sibling chain.
+      if (Child.get().Ranges.empty())
+        break;
+      Inline.Children.emplace_back(std::move(*Child));
+    }
+  }
+  return Inline;
+}
+
+llvm::Expected<InlineInfo> InlineInfo::decode(DataExtractor &Data,
+                                              uint64_t BaseAddr) {
+  uint64_t Offset = 0;
+  return ::decode(Data, Offset, BaseAddr);
+}
+
+llvm::Error InlineInfo::encode(FileWriter &O, uint64_t BaseAddr) const {
+  // Users must verify the InlineInfo is valid prior to calling this funtion.
+  // We don't want to emit any InlineInfo objects if they are not valid since
+  // it will waste space in the GSYM file.
+  if (!isValid())
+    return createStringError(std::errc::invalid_argument,
+                             "attempted to encode invalid InlineInfo object");
+  Ranges.encode(O, BaseAddr);
+  bool HasChildren = !Children.empty();
+  O.writeU8(HasChildren);
+  O.writeU32(Name);
+  O.writeULEB(CallFile);
+  O.writeULEB(CallLine);
+  if (HasChildren) {
+    // Child address ranges are encoded as relative to the first
+    // address in the Ranges for this object. This keeps the offsets
+    // small and allows for efficient encoding using ULEB offsets.
+    const uint64_t ChildBaseAddr = Ranges[0].Start;
+    for (const auto &Child : Children) {
+      // Make sure all child address ranges are contained in the parent address
+      // ranges.
+      for (const auto &ChildRange: Child.Ranges) {
+        if (!Ranges.contains(ChildRange))
+          return createStringError(std::errc::invalid_argument,
+                                   "child range not contained in parent");
+      }
+      llvm::Error Err = Child.encode(O, ChildBaseAddr);
+      if (Err)
+        return Err;
+    }
+
+    // Terminate child sibling chain by emitting a zero. This zero will cause
+    // the decodeAll() function above to return false and stop the decoding
+    // of child InlineInfo objects that are siblings.
+    O.writeULEB(0);
+  }
+  return Error::success();
+}