Add GSYM utility files along with unit tests.

[clayborg]

Summary

The full GSYM patch started with: https://reviews.llvm.org/D53379

In that patch we wanted to split up getting GSYM into the LLVM code base so we are not committing too much code at once.

This is a first in a series of patches where I only add the foundation classes along with complete unit tests. They provide the foundation for encoding and decoding a GSYM file.

File entries are defined in llvm::gsym::FileEntry. This class splits the file up into a directory and filename represented by uniqued string table offsets. This allows all files that are referred to in a GSYM file to be encoded as 1 based indexes into a global file table in the GSYM file.

Function information in stored in llvm::gsym::FunctionInfo. This object represents a contiguous address range that has a name and range with an optional line table and inline call stack information.

Line table entries are defined in llvm::gsym::LineEntry. They store only address, file and line information to keep the line tables simple and allows the information to be efficiently encoded in a subsequent patch.

Inline information is defined in llvm::gsym::InlineInfo. These structs store the name of the inline function, along with one or more address ranges, and the file and line that called this function. They also contain any child inline information.

There are also utility classes for address ranges in llvm::gsym::AddressRange, and string table support in llvm::gsym::StringTable which are simple classes.

The unit tests test all the APIs on these simple classes so they will be ready for the next patches where we will create GSYM files and parse GSYM files.

[jakehehrlich]

Sorry I wasn't very quick to get to this. This looks really good to me. I'm going to go over some of the this with a fine tooth comb tomorrow but It basically looks good as at high level glance.

include/llvm/DebugInfo/GSYM/StringTable.h

48

Return Option<uint32_t> instead.

[clayborg]

Change:

uint32_t llvm::gsym::StringTable::find(StringRef Str) const;

to return optional:

llvm::Optional<uint32_t> llvm::gsym::StringTable::find(StringRef Str) const;

as suggested.

[JDevlieghere]

include/llvm/DebugInfo/GSYM/FileEntry.h

14

This doesn't conform to the LLVM #include style: https://llvm.org/docs/CodingStandards.html#include-style

25

Should this be a Doxygen comment for this struct?

29

The comment for both is identical. I'd group them like

/// Offsets in the string table.
/// @{
...
/// @}

include/llvm/DebugInfo/GSYM/FunctionInfo.h

26

Same comment.

51

Can we make it so that only valid entries are created, for instance by using an Expected<FunctionInfo> wherever it's created? That way we don't need the isValid and maybe even the clear? This is more of a high level comment that applies to the whole diff.

82

Doxygen comment?

include/llvm/DebugInfo/GSYM/InlineInfo.h

24

Should this be a Doxygen comment for the struct? Applies for the other classes/structs as well.

[clayborg]

Address review comments:

• make all comment block doxygen blocks

[clayborg]

include/llvm/DebugInfo/GSYM/FunctionInfo.h

51

Both the DWARF, breakpad, and symbtab converters will create a temp object and then populate, then check if all is good before adding it. It is possible to avoid this, but the code will be cleaner if we can create the object and then populate it lazily. So I would prefer to keep this if possible.

[jakehehrlich]

A bunch of nits but this looks good to me.

include/llvm/DebugInfo/GSYM/FunctionInfo.h

88

nit: Most of the branches here are not tested by my eyes.

99

The motivation for comparing by lines like this is a bit lost on me. Is it just to ensure that if X != Y then either X < Y or Y < X? You'd have to do that for inlines as well if that's the case. You also don't maintain that property on LineInfo anyway.

include/llvm/DebugInfo/GSYM/LineEntry.h

34

In other cases you forwent the dump method and overloaded <<, why not do that here as well?

include/llvm/DebugInfo/GSYM/Range.h

41

maybe "isContiguousWith"

44

maybe "overlaps" or just "intersects" or "overlapsWith"

55

If looking up the greatest lower bound on an address in an array sorted by this predicate, the largest range possible would be chosen. It seems to me that we would actually prefer the *smallest* range be chosen because its information would be more specific. That would suggest that instead of LHS.End < RHS.End we should actually use LHS.End > RHS.End

69

prefer using

include/llvm/DebugInfo/GSYM/StringTable.h

40

same question

50

What is this needed for? I'm not sure I'm happy with this sort of linear search being needed.

lib/DebugInfo/GSYM/InlineInfo.cpp

42

return Option<std::vector<...>> instead perhaps?

lib/DebugInfo/GSYM/Range.cpp

23

Do we expect the number of ranges to be small?

27–32

None of this is needed and should fallout from the std::upper_bound call

33

s/begin/Begin

35

In general I think you want a greatest lower bound which is what you're doing but if you keep your current '<' operator and ignore my comment above about swaping the order of 'End' you can use std::lower_bound here and avoid the subtraction case.

[aprantl]

include/llvm/DebugInfo/GSYM/InlineInfo.h

42

It would be so much easier to reason about correctness if these structs were immutable. Doe we really need a clear() method?

[clayborg]

• Fixed all header includes to abide by https://llvm.org/docs/CodingStandards.html#include-style
• Fixed inline comments

[clayborg]

Marking inline comments as done and mentioning that I did add tests for FunctionInfo operator < as well for cases where things have inline info and line entries

include/llvm/DebugInfo/GSYM/FunctionInfo.h

88

I'll add some tests.

98–99

The main goal is to be able to sort FuncrtionInfo objects after we fill them out from a variety of places (symtab, DWARF, breakpad) and quickly pick out the one with the best info. We saw many issues with debug info when writing the parser where address ranges would overlap or differ for the same range. So we tried to pick the best info. We can modify this sorting as needed.

include/llvm/DebugInfo/GSYM/InlineInfo.h

42

These structs are not encoded in memory like this, they are very efficiently encoded and need to be decoded from a stream of bytes. These items are parsed from a stream, and we either parse everything (if you have a symbolication process that will stay around), or just what we need for a given address (for use in a tool like atos). Not sure if that says anything about wether these structs should be immutable though. Usually during lookups you might call clear on a FunctionInfo's Inline argument in case you lookup multiple addresses into the same FunctionInfo. That being said, nothing is stopping us from changing the APIs that we use for parsing to always return a new instance, or a llvm::Optional.

include/llvm/DebugInfo/GSYM/Range.h

55

I would expect an address with the same start address to still compare the end address:

[0x100-0x101) < [0x100-0x102)

with lower bound you always have to know to back up by one in case the the addresses are equal.

69

llvm/include/llvm/DebugInfo/GSYM/Range.h:71:12: error: using declaration cannot refer to a template specialization
using std::vector<AddressRange> AddressRanges;

^     ~~~~~~~~~~~~~~

include/llvm/DebugInfo/GSYM/StringTable.h

50

I can take this out. This class is used for the mmap'ed string table, not for creating the string table, so I will remove this.

lib/DebugInfo/GSYM/Range.cpp

23

Yes, usually not usually a ton of these.

32

Will remove. Need empty check though.

35

I tried that with:

bool llvm::gsym::contains(const AddressRanges &Ranges, uint64_t Addr) {
  if (Ranges.empty())
    return false;
  auto Begin = Ranges.begin();
  auto EndPos = Ranges.end();
  auto Pos = std::lower_bound(Begin, EndPos, Addr);
  if (Pos != EndPos)
    return Pos->contains(Addr);
  return false;
}

But this failed in the following cases:

EXPECT_TRUE(contains(Ranges, 0x2000-1));
EXPECT_TRUE(contains(Ranges, 0x3000-1));
EXPECT_TRUE(contains(Ranges, 0x5000-1));

[jakehehrlich]

include/llvm/DebugInfo/GSYM/FunctionInfo.h

98–99

Ah sorry I meant to click for the line above where it says LHS.Lines < RHS.Lines I mean that that specifically doesn't make sense to me. It's not clear that that would correlate to a better answer in anyway to me.

include/llvm/DebugInfo/GSYM/Range.h

55

You're right. I just got by logic a bit wrong there. That was the result I expected but I got my self turned around in the reasoning somehow.

69

using AddressRanges = std::vector<AddressRange>; is what I meant.

lib/DebugInfo/GSYM/Range.cpp

32

I think if you remove

if (Pos == EndPos)
    return Ranges.back().contains(Addr);

Then in the empty case Pos == EndPos == Begin which means if (Pos != Begin) will jump to the return false line right?

35

Ah right, It doesn't give you a strict lower bound. I suppose what you have is best. Why is the first algorithm we learn in school so hard to get right?

[clayborg]

Converted AddressRange objects into a class so we can ensure consistent and correct results when using accessors.

Converted AddressRanges into a class instead of a typedef to a vector of AddressRange objects. Converted all places that were directly using the vector to use the class. The AddressRanges now will combine intersecting address ranges and not add empty AddressRange objects to a list. This will help normalize address range objects so we can emit them efficiently into the final GSYM file.

[clayborg]

Marked things as done.

include/llvm/DebugInfo/GSYM/Range.h

70

I ended up converting AddressRanges to a class for more control and normalization of address range collections.

[clayborg]

friendly ping

[clayborg]

It would be great to get this moving. I have figured out how the rest of the patches will be broken up to make them really simple to test and get in, but need this one to go in first.

[jakehehrlich]

Sorry about the lull here. This LGTM

[aprantl]

include/llvm/DebugInfo/GSYM/FileEntry.h

25

I think it needs to go *before* the struct FileEntry { line, doesn't it?

[clayborg]

Fixed build bots as they showed an iterator was being used even if it was the end of a collection.

$ svn commit
Sending lib/DebugInfo/GSYM/Range.cpp
Transmitting file data .done
Committing transaction...
Committed revision 364447.

[kcc]

Hi, 
I think this is causing a failure on the asan bot. Please fix or revert ASAP

[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from GSYMTest

[ RUN ] GSYMTest.TestRanges

19204==ERROR: AddressSanitizer: container-overflow on address 0x606000000390 at pc 0x00000052cde7 bp 0x7ffdbaad4740 sp 0x7ffdbaad4738

READ of size 8 at 0x606000000390 thread T0

#0 0x52cde6 in endAddress /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/DebugInfo/GSYM/Range.h:48:40
#1 0x52cde6 in intersects /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/DebugInfo/GSYM/Range.h:58
#2 0x52cde6 in intersect /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/DebugInfo/GSYM/Range.h:61
#3 0x52cde6 in llvm::gsym::AddressRanges::insert(llvm::gsym::AddressRange const&) /b/sanitizer-x86_64-linux-fast/build/llvm/lib/DebugInfo/GSYM/Range.cpp:35
#4 0x511b8d in GSYMTest_TestRanges_Test::TestBody() /b/sanitizer-x86_64-linux-fast/build/llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp:350:10
#5 0x5bcd00 in HandleExceptionsInMethodIfSupported<testing::Test, void> /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc

[thakis]

The test binary looks like it has many dependencies it doesn't actually need:

llvm/trunk/unittests/DebugInfo/GSYM/CMakeLists.txt

2 ↗

(On Diff #206660)

This looks unused?

3 ↗

(On Diff #206660)

This, too.

5 ↗

(On Diff #206660)

As does this.

6 ↗

(On Diff #206660)

And this.

7 ↗

(On Diff #206660)

And this.

[MaskRay]

llvm/trunk/include/llvm/DebugInfo/GSYM/FileEntry.h

5 ↗

(On Diff #206660)

llvm has switched to Apache 2.0. Please check other files for the correct licence notice.

[MaskRay]

include/llvm/DebugInfo/GSYM/Range.h

31

These mutable setters do not seem very useful. I deleted them in r364637

41

The name still doesn't make much sense to me. Deleted in r364634

60

Comparison between different types of objects may bring confusion. They were only used in upper_bound. I deleted them in r364634.

69

Fixed in r364634

llvm/trunk/unittests/DebugInfo/GSYM/CMakeLists.txt

2 ↗

(On Diff #206660)

Removed in r364634

include/llvm/DebugInfo/GSYM/FileEntry.h

+//===- FileEntry.h ----------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_FILEENTRY_H
+#define LLVM_DEBUGINFO_GSYM_FILEENTRY_H
+
+#include <functional>
+#include <stdint.h>
+#include <utility>
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Hashing.h"
+
+namespace llvm {
+namespace gsym {
+
+struct FileEntry {
+  // Files in GSYM are contained in FileEntry structs where we split the 
+  // directory and basename into two different strings in the string 
+  // table. This allows paths to shared commont directory and filename
+  // strings and saves space.
+  uint32_t Dir = 0;  ///< String table offset in the string table.
+  uint32_t Base = 0; ///< String table offset in the string table.
+
+  FileEntry() = default;
+  FileEntry(uint32_t D, uint32_t B) : Dir(D), Base(B) {}
+
+  // Implement operator== so that FileEntry can be used as key in
+  // unordered containers.
+  bool operator==(const FileEntry &RHS) const {
+    return Base == RHS.Base && Dir == RHS.Dir;
+  };
+  bool operator!=(const FileEntry &RHS) const {
+    return Base != RHS.Base || Dir != RHS.Dir;
+  };
+};
+
+} // namespace gsym
+
+template <> struct DenseMapInfo<gsym::FileEntry> {
+  static inline gsym::FileEntry getEmptyKey() {
+    const auto key = DenseMapInfo<uint32_t>::getEmptyKey();
+    return gsym::FileEntry(key, key);
+    
+  }
+  static inline gsym::FileEntry getTombstoneKey() {
+    const auto key = DenseMapInfo<uint32_t>::getTombstoneKey();
+    return gsym::FileEntry(key, key);
+  }
+  static unsigned getHashValue(const gsym::FileEntry &Val) {
+    return llvm::hash_combine(DenseMapInfo<uint32_t>::getHashValue(Val.Dir),
+                              DenseMapInfo<uint32_t>::getHashValue(Val.Base));
+  }
+  static bool isEqual(const gsym::FileEntry &LHS, const gsym::FileEntry &RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_FILEENTRY_H

include/llvm/DebugInfo/GSYM/FunctionInfo.h

+//===- FunctionInfo.h -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H
+#define LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H
+
+#include <tuple>
+#include <vector>
+
+#include "llvm/DebugInfo/GSYM/InlineInfo.h"
+#include "llvm/DebugInfo/GSYM/LineEntry.h"
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include "llvm/DebugInfo/GSYM/StringTable.h"
+
+namespace llvm {
+class raw_ostream;
+namespace gsym {
+
+struct FunctionInfo {
+  // Function information in GSYM files encodes information for one 
+  // contiguous address range. The name of the function is encoded as
+  // a string table offset and allows multiple functions with the same
+  // name to share the name string in the string table. Line tables are
+  // stored in a sorted vector of gsym::LineEntry objects and are split
+  // into line tables for each function. If a function has a discontiguous
+  // range, it will be split into two gsym::FunctionInfo objects. If the
+  // function has inline functions, the information will be encoded in
+  // the "Inline" member, see gsym::InlineInfo for more information.
+  AddressRange Range;
+  uint32_t Name; ///< String table offset in the string table.
+  std::vector<gsym::LineEntry> Lines;
+  InlineInfo Inline;
+
+  FunctionInfo(uint64_t Addr = 0, uint64_t Size = 0, uint32_t N = 0)
+      : Range(Addr, Addr + Size), Name(N) {}
+
+  bool hasRichInfo() const {
+    // Returns whether we have something else than range and name. When
+    // converting information from a symbol table and from debug info, we 
+    // might end up with multiple FunctionInfo objects for the same range
+    // and we need to be able to tell which one is the better object to use.
+    return !Lines.empty() || Inline.isValid();
+  }
+
+  bool isValid() const {
+    // Address and size can be zero and there can be no line entries for a
+    // symbol so the only indication this entry is valid is if the name is
+    // not zero. This can happen when extracting information from symbol 
+    // tables that do not encode symbol sizes. In that case only the 
+    // address and name will be filled in.
+    return Name != 0;
+  }
+
+  uint64_t startAddress() const { return Range.startAddress(); }
+  uint64_t endAddress() const { return Range.endAddress(); }
+  uint64_t size() const { return Range.size(); }
+  void setStartAddress(uint64_t Addr) { Range.setStartAddress(Addr); }
+  void setEndAddress(uint64_t Addr) { Range.setEndAddress(Addr); }
+  void setSize(uint64_t Size) { Range.setSize(Size); }
+
+  void clear() {
+    Range.clear();
+    Name = 0;
+    Lines.clear();
+    Inline.clear();
+  }
+};
+
+inline bool operator==(const FunctionInfo &LHS, const FunctionInfo &RHS) {
+  return LHS.Range == RHS.Range && LHS.Name == RHS.Name &&
+         LHS.Lines == RHS.Lines && LHS.Inline == RHS.Inline;
+}
+inline bool operator!=(const FunctionInfo &LHS, const FunctionInfo &RHS) {
+  return !(LHS == RHS);
+}
+// This sorting will order things consistently by address range first, but then
+// followed by inlining being valid and line tables. We might end up with a
+// FunctionInfo from debug info that will have the same range as one from the
+// symbol table, but we want to quickly be able to sort and use the best version
+// when creating the final GSYM file. 
+inline bool operator<(const FunctionInfo &LHS, const FunctionInfo &RHS) {
+  // First sort by address range
+  if (LHS.Range != RHS.Range)
+    return LHS.Range < RHS.Range;
+
+  // Then sort by inline
+  if (LHS.Inline.isValid() != RHS.Inline.isValid())
+    return RHS.Inline.isValid();
+
+  // If the number of lines is the same, then compare line table entries
+  if (LHS.Lines.size() == RHS.Lines.size())
+    return LHS.Lines < RHS.Lines;
+  // Then sort by number of line table entries (more is better)
+  return LHS.Lines.size() < RHS.Lines.size();
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const FunctionInfo &R);
+
+} // namespace gsym
+} // namespace llvm
+
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H

include/llvm/DebugInfo/GSYM/InlineInfo.h

+//===- InlineInfo.h ---------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_INLINEINFO_H
+#define LLVM_DEBUGINFO_GSYM_INLINEINFO_H
+
+#include <stdint.h>
+#include <vector>
+
+#include "Range.h"
+
+namespace llvm {
+class raw_ostream;
+
+namespace gsym {
+
+struct InlineInfo {
+  // Inline information stores the name of the inline function along with
+  // an array of address ranges. It also stores the call file and call line
+  // that called this inline function. This allows us to unwind inline call 
+  // stacks back to the inline or concrete function that called this 
+  // function. Inlined functions contained in this function are stored in the
+  // "Children" variable. All address ranges must be sorted and all address
+  // ranges of all children must be contained in the ranges of this function.
+  // Any clients that encode information will need to ensure the ranges are
+  // all contined correctly or lookups could fail. Add ranges in these objects
+  // must be contained in the top level FunctionInfo address ranges as well.
+
+  uint32_t Name; ///< String table offset in the string table.
+  uint32_t CallFile; ///< 1 based file index in the file table.
+  uint32_t CallLine; ///< Source line number.
+  AddressRanges Ranges;
+  std::vector<InlineInfo> Children;
+  InlineInfo() : Name(0), CallFile(0), CallLine(0) {}
+  void clear() {
+    Name = 0;
+    CallFile = 0;
+    CallLine = 0;
+    Ranges.clear();
+    Children.clear();
+  }
+  bool isValid() const { return !Ranges.empty(); }
+  /// Lookup an address in the InlineInfo object
+  ///
+  /// This function is used to symbolicate an inline call stack and can 
+  /// turn one address in the program into one or more inline call stacks
+  /// and have the stack trace show the original call site from 
+  /// non-inlined code.
+  ///
+  /// \param Addr the address to lookup
+  /// \param InlineStack a vector of InlineInfo objects that describe the
+  /// inline call stack for a given address.
+  ///
+  /// \returns true if successful, false otherwise
+  bool getInlineStack(uint64_t Addr,
+                      std::vector<const InlineInfo *> &InlineStack) const;
+};
+
+inline bool operator==(const InlineInfo &LHS, const InlineInfo &RHS) {
+  return LHS.Name == RHS.Name && LHS.CallFile == RHS.CallFile &&
+         LHS.CallLine == RHS.CallLine && LHS.Ranges == RHS.Ranges &&
+         LHS.Children == RHS.Children;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const InlineInfo &FI);
+
+} // namespace gsym
+} // namespace llvm
+
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_INLINEINFO_H

include/llvm/DebugInfo/GSYM/LineEntry.h

+//===- LineEntry.h ----------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_LINEENTRY_H
+#define LLVM_DEBUGINFO_GSYM_LINEENTRY_H
+
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+
+namespace llvm {
+namespace gsym {
+struct LineEntry {
+  // Line entries are used to encode the line tables in FunctionInfo objects.
+  // They are stored as a sorted vector of these objects and store the
+  // address, file and line of the line table row for a given address. The
+  // size of a line table entry is calculated by looking at the next entry
+  // in the FunctionInfo's vector of entries.
+  uint64_t Addr; ///< Start address of this line entry.
+  uint32_t File; ///< 1 based index of file in FileTable
+  uint32_t Line; ///< Source line number.
+  LineEntry(uint64_t A = 0, uint32_t F = 0, uint32_t L = 0)
+      : Addr(A), File(F), Line(L) {}
+  bool isValid() { return File != 0; }
+  void dump(llvm::raw_ostream &OS) const {
+    OS << "addr=" << format("0x%08" PRIx64, Addr)
+       << ", file=" << format("%3u", File) << ", line=" << format("%3u", Line)
+       << '\n';
+  }
+};
+inline bool operator==(const LineEntry &lhs, const LineEntry &rhs) {
+  return lhs.Addr == rhs.Addr && lhs.File == rhs.File && lhs.Line == rhs.Line;
+}
+inline bool operator!=(const LineEntry &lhs, const LineEntry &rhs) {
+  return !(lhs == rhs);
+}
+inline bool operator<(const LineEntry &lhs, const LineEntry &rhs) {
+  return lhs.Addr < rhs.Addr;
+}
+} // namespace gsym
+} // namespace llvm
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_LINEENTRY_H

include/llvm/DebugInfo/GSYM/Range.h

+//===- AddressRange.h -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_RANGE_H
+#define LLVM_DEBUGINFO_GSYM_RANGE_H
+
+#include <stdint.h>
+#include <vector>
+
+#define HEX8(v) llvm::format_hex(v, 4)
+#define HEX16(v) llvm::format_hex(v, 6)
+#define HEX32(v) llvm::format_hex(v, 10)
+#define HEX64(v) llvm::format_hex(v, 18)
+
+namespace llvm {
+class raw_ostream;
+
+namespace gsym {
+struct AddressRange {
+  uint64_t Start;
+  uint64_t End;
+  AddressRange(uint64_t S = 0, uint64_t E = 0) : Start(S), End(E) {}
+  uint64_t size() const { return Start < End ? End - Start : 0; }
+  void setStartAddress(uint64_t Addr) { Start = Addr; }
+  void setEndAddress(uint64_t Addr) { End = Addr; }
+  void setSize(uint64_t Size) { End = Start + Size; }
+  uint64_t startAddress() const { return Start; }
+  uint64_t endAddress() const { return End; }
+  void clear() {
+    Start = 0;
+    End = 0;
+  }
+  bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
+  bool doesAdjoinOrIntersect(const AddressRange &RHS) const {
+    return (Start <= RHS.End) && (End >= RHS.Start);
+  }
+  bool doesIntersect(const AddressRange &RHS) const {
+    return (Start < RHS.End) && (End > RHS.Start);
+  }
+};
+
+inline bool operator==(const AddressRange &LHS, const AddressRange &RHS) {
+  return LHS.Start == RHS.Start && LHS.End == RHS.End;
+}
+inline bool operator!=(const AddressRange &LHS, const AddressRange &RHS) {
+  return LHS.Start != RHS.Start || LHS.End != RHS.End;
+}
+inline bool operator<(const AddressRange &LHS, const AddressRange &RHS) {
+  if (LHS.Start == RHS.Start)
+    return LHS.End < RHS.End;
+  return LHS.Start < RHS.Start;
+}
+inline bool operator<(const AddressRange &LHS, uint64_t Addr) {
+  return LHS.Start < Addr;
+}
+inline bool operator<(uint64_t Addr, const AddressRange &RHS) {
+  return Addr < RHS.Start;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const AddressRange &R);
+
+typedef std::vector<AddressRange> AddressRanges;
+bool contains(const AddressRanges &Ranges, uint64_t Addr);
+void insert(AddressRanges &Ranges, const AddressRange &R);
+
+} // namespace gsym
+} // namespace llvm
+
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_RANGE_H

include/llvm/DebugInfo/GSYM/StringTable.h

+//===- StringTable.h --------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_STRINGTABLE_H
+#define LLVM_DEBUGINFO_GSYM_STRINGTABLE_H
+
+#include <stdint.h>
+#include <string>
+
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+
+
+namespace llvm {
+namespace gsym {
+struct StringTable {
+  /// String tables in GSYM files are required to start with an empty 
+  /// string at offset zero. Strings must be UTF8 NULL terminated strings.
+  StringRef Data;
+  StringTable() : Data() {}
+  StringTable(StringRef D) : Data(D) {}
+  StringRef operator[](size_t Offset) const { return getString(Offset); }
+  StringRef getString(uint32_t Offset) const {
+    if (Offset < Data.size()) {
+      auto End = Data.find('\0', Offset);
+      return Data.substr(Offset, End - Offset);
+    }
+    return StringRef();
+  }
+  void clear() { Data = StringRef(); }
+  void dump(raw_ostream &OS) const {
+    OS << "String table:\n";
+    uint32_t Offset = 0;
+    const size_t Size = Data.size();
+    while (Offset < Size) {
+      StringRef Str = getString(Offset);
+      OS << HEX32(Offset) << ": \"" << Str << "\"\n";
+      Offset += Str.size() + 1;
+    }
+  }
+  llvm::Optional<uint32_t> find(StringRef Str) const {
+    // Return the first byte of the GSYM string table which contains the 
+    // empty string for empty strings.
+    if (Str.empty())
+      return 0; 
+    size_t Offset = 0;
+    size_t Pos;
+    while ((Pos = Data.find(Str, Offset)) != StringRef::npos) {
+      auto NullTerminator = Data.substr(Pos + Str.size(), 1);
+      if (NullTerminator.empty())
+        break;
+      if (NullTerminator[0] == '\0')
+        return Pos;
+      Offset += Str.size() + 1;
+    }
+    return llvm::None;
+  }
+};
+} // namespace gsym
+} // namespace llvm
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_STRINGTABLE_H

lib/DebugInfo/CMakeLists.txt

 add_subdirectory(DWARF)
+add_subdirectory(GSYM)
 add_subdirectory(MSF)
 add_subdirectory(CodeView)
 add_subdirectory(PDB)
 add_subdirectory(Symbolize)

lib/DebugInfo/GSYM/CMakeLists.txt

+add_llvm_library(LLVMDebugInfoGSYM
+  FunctionInfo.cpp
+  InlineInfo.cpp
+  Range.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/GSYM
+  ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo
+  )

lib/DebugInfo/GSYM/FunctionInfo.cpp

+//===- FunctionInfo.cpp -----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <inttypes.h>
+
+#include "llvm/DebugInfo/GSYM/FunctionInfo.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace gsym;
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const FunctionInfo &FI) {
+  OS << '[' << HEX64(FI.Range.startAddress()) << '-'
+     << HEX64(FI.Range.endAddress()) << "): "
+     << "Name=" << HEX32(FI.Name) << '\n';
+  for (const auto &Line : FI.Lines)
+    Line.dump(OS);
+  OS << FI.Inline;
+  return OS;
+}

lib/DebugInfo/GSYM/InlineInfo.cpp

+//===- InlineInfo.cpp -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <inttypes.h>
+
+#include <algorithm>
+
+#include "llvm/DebugInfo/GSYM/FileEntry.h"
+#include "llvm/DebugInfo/GSYM/InlineInfo.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace gsym;
+
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const InlineInfo &II) {
+  if (!II.isValid())
+    return OS;
+  bool First = true;
+  for (auto Range : II.Ranges) {
+    if (First)
+      First = false;
+    else
+      OS << ' ';
+    OS << Range;
+  }
+  OS << " Name = " << HEX32(II.Name) << ", CallFile = " << II.CallFile
+     << ", CallLine = " << II.CallFile << '\n';
+  for (const auto &Child : II.Children)
+    OS << Child;
+  return OS;
+}
+
+bool InlineInfo::getInlineStack(
+    uint64_t Addr, std::vector<const InlineInfo *> &InlineStack) const {
+  for (const auto &Range : Ranges) {
+    if (Range.contains(Addr)) {
+      // If this is the top level that represents the concrete function,
+      // there will be no name and we shoud clear the inline stack. Otherwise
+      // we have found an inline call stack that we need to insert.
+      if (Name == 0)
+        InlineStack.clear();
+      else
+        InlineStack.insert(InlineStack.begin(), this);
+      for (const auto &Child : Children) {
+        if (Child.getInlineStack(Addr, InlineStack))
+          break;
+      }
+      return !InlineStack.empty();
+    }
+  }
+  return false;
+}

lib/DebugInfo/GSYM/Range.cpp

+//===- InlineInfo.cpp -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <inttypes.h>
+
+#include <algorithm>
+
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace gsym;
+
+void llvm::gsym::insert(AddressRanges &Ranges, const AddressRange &Range) {
+  Ranges.insert(std::upper_bound(Ranges.begin(), Ranges.end(), Range), Range);
+}
+
+bool llvm::gsym::contains(const AddressRanges &Ranges, uint64_t Addr) {
+  if (Ranges.empty())
+    return false;
+  if (Addr < Ranges.front().Start)
+    return false;
+  if (Addr >= Ranges.back().End)
+    return false;
+  auto begin = Ranges.begin();
+  auto EndPos = Ranges.end();
+  auto Pos = std::upper_bound(begin, EndPos, Addr);
+  if (Pos == EndPos)
+    return Ranges.back().contains(Addr);
+  if (Pos != begin) {
+    --Pos;
+    return Pos->contains(Addr);
+  }
+  return false;
+}
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRange &R) {
+  return OS << '[' << HEX64(R.startAddress()) << " - " << HEX64(R.endAddress())
+            << ")";
+}

unittests/DebugInfo/CMakeLists.txt

 add_subdirectory(CodeView)
 add_subdirectory(DWARF)
+add_subdirectory(GSYM)
 add_subdirectory(MSF)
 add_subdirectory(PDB)

unittests/DebugInfo/GSYM/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  ${LLVM_TARGETS_TO_BUILD}
+  AsmPrinter
+  DebugInfoGSYM
+  MC
+  Object
+  ObjectYAML
+  Support
+  )
+
+add_llvm_unittest(DebugInfoGSYMTests
+  GSYMTest.cpp
+  )
+
+target_link_libraries(DebugInfoGSYMTests PRIVATE LLVMTestingSupport)

unittests/DebugInfo/GSYM/GSYMTest.cpp

+//===- llvm/unittest/DebugInfo/GSYMTest.cpp -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/DebugInfo/GSYM/FileEntry.h"
+#include "llvm/DebugInfo/GSYM/FunctionInfo.h"
+#include "llvm/DebugInfo/GSYM/InlineInfo.h"
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include "llvm/DebugInfo/GSYM/StringTable.h"
+#include "llvm/Testing/Support/Error.h"
+
+#include "gtest/gtest.h"
+#include <sstream>
+#include <string>
+
+using namespace llvm;
+using namespace gsym;
+
+TEST(GSYMTest, TestFileEntry) {
+  // Make sure default constructed GSYM FileEntry has zeroes in the 
+  // directory and basename string table indexes.
+  FileEntry empty1;
+  FileEntry empty2;
+  EXPECT_EQ(empty1.Dir, 0u);
+  EXPECT_EQ(empty1.Base, 0u);
+  // Verify equality operator works
+  FileEntry a1(10,30);
+  FileEntry a2(10,30);
+  FileEntry b(10,40);
+  EXPECT_EQ(empty1, empty2);
+  EXPECT_EQ(a1, a2);
+  EXPECT_NE(a1, b);
+  EXPECT_NE(a1, empty1);
+  // Test we can use llvm::gsym::FileEntry in llvm::DenseMap.
+  DenseMap<FileEntry, uint32_t> EntryToIndex;
+  constexpr uint32_t Index1 = 1;
+  constexpr uint32_t Index2 = 1;
+  auto R = EntryToIndex.insert(std::make_pair(a1, Index1));
+  EXPECT_TRUE(R.second);
+  EXPECT_EQ(R.first->second, Index1);
+  R = EntryToIndex.insert(std::make_pair(a1, Index1));
+  EXPECT_FALSE(R.second);
+  EXPECT_EQ(R.first->second, Index1);
+  R = EntryToIndex.insert(std::make_pair(b, Index2));
+  EXPECT_TRUE(R.second);
+  EXPECT_EQ(R.first->second, Index2);
+  R = EntryToIndex.insert(std::make_pair(a1, Index2));
+  EXPECT_FALSE(R.second);
+  EXPECT_EQ(R.first->second, Index2);
+}
+
+
+TEST(GSYMTest, TestFunctionInfo) {
+  // Test GSYM FunctionInfo structs and functionality.
+  FunctionInfo invalid;
+  EXPECT_FALSE(invalid.isValid());
+  EXPECT_FALSE(invalid.hasRichInfo());
+  const uint64_t StartAddr = 0x1000;
+  const uint64_t EndAddr = 0x1100;
+  const uint64_t Size = EndAddr - StartAddr;
+  FunctionInfo FI(StartAddr, Size, 30);
+  EXPECT_TRUE(FI.isValid());
+  EXPECT_FALSE(FI.hasRichInfo());
+  EXPECT_EQ(FI.startAddress(), StartAddr);
+  EXPECT_EQ(FI.endAddress(), EndAddr);
+  EXPECT_EQ(FI.size(), Size);
+  const uint32_t FileIdx = 1;
+  const uint32_t Line = 12;
+  FI.Lines.push_back(LineEntry(StartAddr,FileIdx,Line));
+  EXPECT_TRUE(FI.hasRichInfo());
+  FI.clear();
+  EXPECT_FALSE(FI.isValid());
+  EXPECT_FALSE(FI.hasRichInfo());
+
+  FunctionInfo A1(0x1000, 0x100, 30);
+  FunctionInfo A2(0x1000, 0x100, 30);
+  FunctionInfo B;
+  // Check == operator
+  EXPECT_EQ(A1, A2);
+  // Make sure things are not equal if they only differ by start address.
+  B = A2;
+  B.setStartAddress(0x2000);
+  EXPECT_NE(B, A2);
+  // Make sure things are not equal if they only differ by size.
+  B = A2;
+  B.setSize(0x101);
+  EXPECT_NE(B, A2);
+  // Make sure things are not equal if they only differ by name.
+  B = A2;
+  B.Name = 60;
+  EXPECT_NE(B, A2);
+  // Check < operator.
+  // Check less than where address differs.
+  B = A2;
+  B.setStartAddress(A2.startAddress() + 0x1000);
+  EXPECT_LT(A1, B);
+  
+}
+
+TEST(GSYMTest, TestInlineInfo) {
+  // Test InlineInfo structs.
+  InlineInfo II;
+  EXPECT_FALSE(II.isValid());
+  II.Ranges.push_back(AddressRange(0x1000,0x2000));
+  // Make sure InlineInfo in valid with just an address range since
+  // top level InlineInfo objects have ranges with no name, call file
+  // or call line
+  EXPECT_TRUE(II.isValid());
+  // Make sure InlineInfo isn't after being cleared.
+  II.clear();
+  EXPECT_FALSE(II.isValid());
+
+  // Create an InlineInfo that contains the following data. The
+  // indentation of the address range indicates the parent child
+  // relationships of the InlineInfo objects:
+  //
+  // Variable    Range and values
+  // =========== ====================================================
+  // Root        [0x100-0x200) (no name, file, or line)
+  // Inline1       [0x150-0x160) Name = 1, File = 1, Line = 11
+  // Inline1Sub1     [0x152-0x155) Name = 2, File = 2, Line = 22
+  // Inline1Sub2     [0x157-0x158) Name = 3, File = 3, Line = 33
+  InlineInfo Root;
+  Root.Ranges.push_back(AddressRange(0x100,0x200));
+  InlineInfo Inline1;
+  Inline1.Ranges.push_back(AddressRange(0x150,0x160));
+  Inline1.Name = 1;
+  Inline1.CallFile = 1;
+  Inline1.CallLine = 11;
+  InlineInfo Inline1Sub1;
+  Inline1Sub1.Ranges.push_back(AddressRange(0x152, 0x155));
+  Inline1Sub1.Name = 2;
+  Inline1Sub1.CallFile = 2;
+  Inline1Sub1.CallLine = 22;
+  InlineInfo Inline1Sub2;
+  Inline1Sub2.Ranges.push_back(AddressRange(0x157,0x158));
+  Inline1Sub2.Name = 3;
+  Inline1Sub2.CallFile = 3;
+  Inline1Sub2.CallLine = 33;
+  Inline1.Children.push_back(Inline1Sub1);
+  Inline1.Children.push_back(Inline1Sub2);
+  Root.Children.push_back(Inline1);
+
+  std::vector<const InlineInfo *> InlineInfos;
+  // Make sure an address that is out of range won't match
+  EXPECT_FALSE(Root.getInlineStack(0x50, InlineInfos));
+
+  // Verify that we get no inline stacks for addresses out of [0x100-0x200) 
+  EXPECT_FALSE(Root.getInlineStack(Root.Ranges.front().startAddress() - 1, 
+                                   InlineInfos));
+  EXPECT_FALSE(Root.getInlineStack(Root.Ranges.front().endAddress(), 
+                                   InlineInfos));
+  // Verify we get no inline stack entries for addresses that are in
+  // [0x100-0x200) but not in [0x150-0x160)
+  EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges.front().startAddress() - 1, 
+                                  InlineInfos));
+  EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges.front().endAddress(), 
+                                  InlineInfos));
+
+
+  // Verify we get one inline stack entry for addresses that are in
+  // [[0x150-0x160)) but not in [0x152-0x155) or [0x157-0x158)
+  EXPECT_TRUE(Root.getInlineStack(Inline1.Ranges.front().startAddress(), 
+                                  InlineInfos));
+  ASSERT_EQ(InlineInfos.size(), 1u);
+  ASSERT_EQ(*InlineInfos[0], Inline1);
+  EXPECT_TRUE(Root.getInlineStack(Inline1.Ranges.front().endAddress() - 1, 
+                                  InlineInfos));
+  ASSERT_EQ(InlineInfos.size(), 1u);
+  ASSERT_EQ(*InlineInfos[0], Inline1);
+
+  // Verify we get two inline stack entries for addresses that are in
+  // [0x152-0x155)
+  EXPECT_TRUE(Root.getInlineStack(Inline1Sub1.Ranges.front().startAddress(), 
+                                  InlineInfos));
+  ASSERT_EQ(InlineInfos.size(), 2u);
+  ASSERT_EQ(*InlineInfos[0], Inline1Sub1);
+  ASSERT_EQ(*InlineInfos[1], Inline1);
+  EXPECT_TRUE(Root.getInlineStack(Inline1Sub1.Ranges.front().endAddress() - 1,
+                                  InlineInfos));
+  ASSERT_EQ(InlineInfos.size(), 2u);
+  ASSERT_EQ(*InlineInfos[0], Inline1Sub1);
+  ASSERT_EQ(*InlineInfos[1], Inline1);
+
+  // Verify we get two inline stack entries for addresses that are in
+  // [0x157-0x158)
+  EXPECT_TRUE(Root.getInlineStack(Inline1Sub2.Ranges.front().startAddress(), 
+                                  InlineInfos));
+  ASSERT_EQ(InlineInfos.size(), 2u);
+  ASSERT_EQ(*InlineInfos[0], Inline1Sub2);
+  ASSERT_EQ(*InlineInfos[1], Inline1);
+  EXPECT_TRUE(Root.getInlineStack(Inline1Sub2.Ranges.front().endAddress() - 1,
+                                  InlineInfos));
+  ASSERT_EQ(InlineInfos.size(), 2u);
+  ASSERT_EQ(*InlineInfos[0], Inline1Sub2);
+  ASSERT_EQ(*InlineInfos[1], Inline1);
+} 
+
+TEST(GSYMTest, TestLineEntry) {
+  // test llvm::gsym::LineEntry structs.
+  const uint64_t ValidAddr = 0x1000;
+  const uint64_t InvalidFileIdx = 0;
+  const uint32_t ValidFileIdx = 1;
+  const uint32_t ValidLine = 5;
+
+  LineEntry Invalid;
+  EXPECT_FALSE(Invalid.isValid());
+  // Make sure that an entry is invalid if it has a bad file index.
+  LineEntry BadFile(ValidAddr, InvalidFileIdx, ValidLine);
+  EXPECT_FALSE(BadFile.isValid());
+  // Test operators
+  LineEntry E1(ValidAddr, ValidFileIdx, ValidLine);
+  LineEntry E2(ValidAddr, ValidFileIdx, ValidLine);
+  LineEntry DifferentAddr(ValidAddr+1, ValidFileIdx, ValidLine);
+  LineEntry DifferentFile(ValidAddr, ValidFileIdx+1, ValidLine);
+  LineEntry DifferentLine(ValidAddr, ValidFileIdx, ValidLine+1);
+  EXPECT_TRUE(E1.isValid());
+  EXPECT_EQ(E1, E2);
+  EXPECT_NE(E1, DifferentAddr);
+  EXPECT_NE(E1, DifferentFile);
+  EXPECT_NE(E1, DifferentLine);
+  EXPECT_LT(E1, DifferentAddr);
+}
+
+TEST(GSYMTest, TestRanges) {
+  // test llvm::gsym::AddressRange.
+  const uint64_t StartAddr = 0x1000;
+  const uint64_t EndAddr = 0x2000;
+  // Verify constructor and API to ensure it takes start and end address.
+  const AddressRange Range(StartAddr, EndAddr);
+  EXPECT_EQ(Range.startAddress(), StartAddr);
+  EXPECT_EQ(Range.endAddress(), EndAddr);
+  EXPECT_EQ(Range.size(), EndAddr-StartAddr);
+
+  // Verify llvm::gsym::AddressRange::contains().
+  EXPECT_FALSE(Range.contains(0));
+  EXPECT_FALSE(Range.contains(StartAddr-1));
+  EXPECT_TRUE(Range.contains(StartAddr));
+  EXPECT_TRUE(Range.contains(EndAddr-1));
+  EXPECT_FALSE(Range.contains(EndAddr));
+  EXPECT_FALSE(Range.contains(UINT64_MAX));
+
+  const AddressRange RangeSame(StartAddr, EndAddr);
+  const AddressRange RangeDifferentStart(StartAddr+1, EndAddr);
+  const AddressRange RangeDifferentEnd(StartAddr, EndAddr+1);
+  const AddressRange RangeDifferentStartEnd(StartAddr+1, EndAddr+1);
+  // Test == and != with values that are the same
+  EXPECT_EQ(Range, RangeSame);
+  EXPECT_FALSE(Range != RangeSame);
+  // Test == and != with values that are the different
+  EXPECT_NE(Range, RangeDifferentStart);
+  EXPECT_NE(Range, RangeDifferentEnd);
+  EXPECT_NE(Range, RangeDifferentStartEnd);
+  EXPECT_FALSE(Range == RangeDifferentStart);
+  EXPECT_FALSE(Range == RangeDifferentEnd);
+  EXPECT_FALSE(Range == RangeDifferentStartEnd);
+
+  // Test "bool operator<(const AddressRange &, const AddressRange &)".
+  EXPECT_FALSE(Range < RangeSame);
+  EXPECT_FALSE(RangeSame < Range);
+  EXPECT_LT(Range, RangeDifferentStart);
+  EXPECT_LT(Range, RangeDifferentEnd);
+  EXPECT_LT(Range, RangeDifferentStartEnd);
+  // Test "bool operator<(const AddressRange &, uint64_t)"
+  EXPECT_LT(Range, StartAddr + 1);
+  // Test "bool operator<(uint64_t, const AddressRange &)"
+  EXPECT_LT(StartAddr - 1, Range);
+
+  // Verify llvm::gsym::AddressRange::doesAdjoinOrIntersect() and
+  // llvm::gsym::AddressRange::doesIntersect().
+  const AddressRange EndsBeforeRangeStart(0, StartAddr-1);
+  const AddressRange EndsAtRangeStart(0, StartAddr);
+  const AddressRange OverlapsRangeStart(StartAddr-1, StartAddr+1);
+  const AddressRange InsideRange(StartAddr+1, EndAddr-1);
+  const AddressRange OverlapsRangeEnd(EndAddr-1, EndAddr+1);
+  const AddressRange StartsAtRangeEnd(EndAddr, EndAddr+0x100);
+  const AddressRange StartsAfterRangeEnd(EndAddr+1, EndAddr+0x100);
+
+  EXPECT_FALSE(Range.doesAdjoinOrIntersect(EndsBeforeRangeStart));
+  EXPECT_TRUE(Range.doesAdjoinOrIntersect(EndsAtRangeStart));
+  EXPECT_TRUE(Range.doesAdjoinOrIntersect(OverlapsRangeStart));
+  EXPECT_TRUE(Range.doesAdjoinOrIntersect(InsideRange));
+  EXPECT_TRUE(Range.doesAdjoinOrIntersect(OverlapsRangeEnd));
+  EXPECT_TRUE(Range.doesAdjoinOrIntersect(StartsAtRangeEnd));
+  EXPECT_FALSE(Range.doesAdjoinOrIntersect(StartsAfterRangeEnd));
+
+  EXPECT_FALSE(Range.doesIntersect(EndsBeforeRangeStart));
+  EXPECT_FALSE(Range.doesIntersect(EndsAtRangeStart));
+  EXPECT_TRUE(Range.doesIntersect(OverlapsRangeStart));
+  EXPECT_TRUE(Range.doesIntersect(InsideRange));
+  EXPECT_TRUE(Range.doesIntersect(OverlapsRangeEnd));
+  EXPECT_FALSE(Range.doesIntersect(StartsAtRangeEnd));
+  EXPECT_FALSE(Range.doesIntersect(StartsAfterRangeEnd));
+
+  // Test the functions that maintain GSYM address ranges:
+  //  "bool contains(const AddressRanges &Ranges, uint64_t Addr);"
+  //  "void insert(AddressRanges &Ranges, const AddressRange &R);"
+  AddressRanges Ranges;
+  insert(Ranges, AddressRange(0x1000, 0x2000));
+  insert(Ranges, AddressRange(0x2000, 0x3000));
+  insert(Ranges, AddressRange(0x4000, 0x5000));
+
+  EXPECT_FALSE(contains(Ranges, 0x1000-1));
+  EXPECT_TRUE(contains(Ranges, 0x1000));
+  EXPECT_TRUE(contains(Ranges, 0x2000));
+  EXPECT_TRUE(contains(Ranges, 0x4000));
+  EXPECT_TRUE(contains(Ranges, 0x2000-1));
+  EXPECT_TRUE(contains(Ranges, 0x3000-1));
+  EXPECT_FALSE(contains(Ranges, 0x3000+1));
+  EXPECT_TRUE(contains(Ranges, 0x5000-1));
+  EXPECT_FALSE(contains(Ranges, 0x5000+1));
+}
+
+TEST(GSYMTest, TestStringTable) {
+  StringTable StrTab(StringRef("\0Hello\0World\0", 13));
+  // Test extracting strings from a string table.
+  EXPECT_EQ(StrTab.getString(0), "");
+  EXPECT_EQ(StrTab.getString(1), "Hello");
+  EXPECT_EQ(StrTab.getString(7), "World");
+  EXPECT_EQ(StrTab.getString(8), "orld");
+  // Test pointing to last NULL terminator gets empty string.
+  EXPECT_EQ(StrTab.getString(12), "");
+  // Test pointing to past end gets empty string.
+  EXPECT_EQ(StrTab.getString(13), "");
+
+  // Test finding strings in a string table.
+  EXPECT_EQ(StrTab.find(""), 0u);
+  EXPECT_EQ(StrTab.find("Hello"), 1u);
+  EXPECT_EQ(StrTab.find("ello"), 2u);
+  EXPECT_EQ(StrTab.find("o"), 5u);
+  EXPECT_EQ(StrTab.find("World"), 7u);
+  EXPECT_EQ(StrTab.find("d"), 11u);
+  EXPECT_EQ(StrTab.find("not found"), llvm::None);
+}