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

47 ↗

(On Diff #203920)

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

13 ↗

(On Diff #203920)

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

24 ↗

(On Diff #203920)

Should this be a Doxygen comment for this struct?

28 ↗

(On Diff #203920)

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

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

include/llvm/DebugInfo/GSYM/FunctionInfo.h

26 ↗

(On Diff #204556)

Same comment.

51 ↗

(On Diff #204556)

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 ↗

(On Diff #204556)

Doxygen comment?

include/llvm/DebugInfo/GSYM/InlineInfo.h

24 ↗

(On Diff #204556)

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 ↗

(On Diff #204556)

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

87 ↗

(On Diff #204805)

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

98 ↗

(On Diff #204805)

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

33 ↗

(On Diff #204805)

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

include/llvm/DebugInfo/GSYM/Range.h

40 ↗

(On Diff #204805)

maybe "isContiguousWith"

43 ↗

(On Diff #204805)

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

54 ↗

(On Diff #204805)

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

68 ↗

(On Diff #204805)

prefer using

include/llvm/DebugInfo/GSYM/StringTable.h

39 ↗

(On Diff #204805)

same question

49 ↗

(On Diff #204805)

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

41 ↗

(On Diff #204805)

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

lib/DebugInfo/GSYM/Range.cpp

22 ↗

(On Diff #204805)

Do we expect the number of ranges to be small?

26–31 ↗

(On Diff #204805)

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

32 ↗

(On Diff #204805)

s/begin/Begin

34 ↗

(On Diff #204805)

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

41 ↗

(On Diff #204805)

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

87 ↗

(On Diff #204805)

I'll add some tests.

97–98 ↗

(On Diff #204805)

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

41 ↗

(On Diff #204805)

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

54 ↗

(On Diff #204805)

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.

68 ↗

(On Diff #204805)

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

49 ↗

(On Diff #204805)

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

22 ↗

(On Diff #204805)

Yes, usually not usually a ton of these.

31 ↗

(On Diff #204805)

Will remove. Need empty check though.

34 ↗

(On Diff #204805)

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

97–98 ↗

(On Diff #204805)

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

54 ↗

(On Diff #204805)

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.

68 ↗

(On Diff #204805)

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

lib/DebugInfo/GSYM/Range.cpp

31 ↗

(On Diff #204805)

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?

34 ↗

(On Diff #204805)

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

69 ↗

(On Diff #205362)

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

24 ↗

(On Diff #203920)

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

This looks unused?

3

This, too.

5

As does this.

6

And this.

7

And this.

[MaskRay]

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

5

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

[MaskRay]

include/llvm/DebugInfo/GSYM/Range.h

30 ↗

(On Diff #204805)

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

40 ↗

(On Diff #204805)

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

59 ↗

(On Diff #204805)

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

68 ↗

(On Diff #204805)

Fixed in r364634

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

2

Removed in r364634

llvm/trunk/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 "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Hashing.h"
+#include <functional>
+#include <stdint.h>
+#include <utility>
+
+namespace llvm {
+namespace gsym {
+
+/// 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.
+struct FileEntry {
+
+  /// Offsets in the string table.
+  /// @{
+  uint32_t Dir = 0;
+  uint32_t Base = 0;
+  /// @}
+
+  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

llvm/trunk/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 "llvm/DebugInfo/GSYM/InlineInfo.h"
+#include "llvm/DebugInfo/GSYM/LineEntry.h"
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include "llvm/DebugInfo/GSYM/StringTable.h"
+#include <tuple>
+#include <vector>
+
+namespace llvm {
+class raw_ostream;
+namespace gsym {
+
+/// 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.
+struct FunctionInfo {
+  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

llvm/trunk/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 "llvm/ADT/Optional.h"
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include <stdint.h>
+#include <vector>
+
+
+namespace llvm {
+class raw_ostream;
+
+namespace gsym {
+
+/// 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.
+struct InlineInfo {
+
+  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
+  typedef std::vector<const InlineInfo *> InlineArray;
+  llvm::Optional<InlineArray> getInlineStack(uint64_t Addr) 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

llvm/trunk/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/DebugInfo/GSYM/Range.h"
+
+namespace llvm {
+namespace gsym {
+
+/// 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.
+struct LineEntry {
+  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; }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const LineEntry &LE) {
+  return OS << "addr=" << HEX64(LE.Addr) << ", file=" << format("%3u", LE.File) 
+      << ", line=" << format("%3u", LE.Line);
+}
+
+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

llvm/trunk/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 "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.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 {
+
+/// A class that represents an address range. The range is specified using
+/// a start and an end address. 
+class AddressRange {
+  uint64_t Start;
+  uint64_t End;
+public:
+  AddressRange(uint64_t S = 0, uint64_t E = 0) : Start(S), End(E) {}
+  /// Access to the size must use the size() accessor to ensure the correct
+  /// answer. This allows an AddressRange to be constructed with invalid
+  /// address ranges where the end address is less that the start address
+  /// either because it was not set, or because of incorrect data.
+  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; }
+  /// Access to the end address must use the size() accessor to ensure the
+  /// correct answer. This allows an AddressRange to be constructed with
+  /// invalid address ranges where the end address is less that the start 
+  /// address either because it was not set, or because of incorrect data.
+  uint64_t endAddress() const { return Start + size(); }
+  void clear() {
+    Start = 0;
+    End = 0;
+  }
+  bool contains(uint64_t Addr) const { return Start <= Addr && Addr < endAddress(); }
+  bool isContiguousWith(const AddressRange &R) const {
+    return (Start <= R.endAddress()) && (endAddress() >= R.Start);
+  }
+  bool intersects(const AddressRange &R) const {
+    return (Start < R.endAddress()) && (endAddress() > R.Start);
+  }
+  bool intersect(const AddressRange &R) {
+    if (intersects(R)) {
+      Start = std::min<uint64_t>(Start, R.Start);
+      End = std::max<uint64_t>(endAddress(), R.endAddress());
+      return true;
+    }
+    return false;
+  }
+};
+
+inline bool operator==(const AddressRange &LHS, const AddressRange &RHS) {
+  return LHS.startAddress() == RHS.startAddress() && LHS.endAddress() == RHS.endAddress();
+}
+inline bool operator!=(const AddressRange &LHS, const AddressRange &RHS) {
+  return LHS.startAddress() != RHS.startAddress() || LHS.endAddress() != RHS.endAddress();
+}
+inline bool operator<(const AddressRange &LHS, const AddressRange &RHS) {
+  if (LHS.startAddress() == RHS.startAddress())
+    return LHS.endAddress() < RHS.endAddress();
+  return LHS.startAddress() < RHS.startAddress();
+}
+inline bool operator<(const AddressRange &LHS, uint64_t Addr) {
+  return LHS.startAddress() < Addr;
+}
+inline bool operator<(uint64_t Addr, const AddressRange &RHS) {
+  return Addr < RHS.startAddress();
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const AddressRange &R);
+
+/// The AddressRanges class helps normalize address range collections.
+/// This class keeps a sorted vector of AddressRange objects and can perform
+/// insertions and searches efficiently. The address ranges are always sorted
+/// and never contain any invalid or empty address ranges. This allows us to
+/// emit address ranges into the GSYM file efficiently. Intersecting address
+/// ranges are combined during insertion so that we can emit the most compact
+/// representation for address ranges when writing to disk.
+class AddressRanges {
+protected:
+  typedef std::vector<AddressRange> Collection;
+  Collection Ranges;
+public:
+  void clear() { Ranges.clear(); }
+  bool empty() const { return Ranges.empty(); }
+  bool contains(uint64_t Addr) const;
+  void insert(const AddressRange &R);
+  size_t size() const { return Ranges.size(); }
+  bool operator==(const AddressRanges &RHS) const {
+    return Ranges == RHS.Ranges;
+  }
+  const AddressRange &operator[](size_t i) const {
+    assert(i < Ranges.size());
+    return Ranges[i];
+  }
+  Collection::const_iterator begin() const { return Ranges.begin(); }
+  Collection::const_iterator end() const { return Ranges.end(); }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const AddressRanges &AR);
+
+} // namespace gsym
+} // namespace llvm
+
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_RANGE_H

llvm/trunk/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 "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include <stdint.h>
+#include <string>
+
+
+namespace llvm {
+namespace gsym {
+
+/// String tables in GSYM files are required to start with an empty 
+/// string at offset zero. Strings must be UTF8 NULL terminated strings.
+struct StringTable {
+  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(); }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const StringTable &S) {
+  OS << "String table:\n";
+  uint32_t Offset = 0;
+  const size_t Size = S.Data.size();
+  while (Offset < Size) {
+    StringRef Str = S.getString(Offset);
+    OS << HEX32(Offset) << ": \"" << Str << "\"\n";
+    Offset += Str.size() + 1;
+  }
+  return OS;
+}
+
+} // namespace gsym
+} // namespace llvm
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_STRINGTABLE_H

llvm/trunk/lib/DebugInfo/CMakeLists.txt

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

llvm/trunk/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
+  )

llvm/trunk/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 "llvm/DebugInfo/GSYM/FunctionInfo.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)
+    OS << Line << '\n';
+  OS << FI.Inline;
+  return OS;
+}

llvm/trunk/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 "llvm/DebugInfo/GSYM/FileEntry.h"
+#include "llvm/DebugInfo/GSYM/InlineInfo.h"
+#include <algorithm>
+#include <inttypes.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;
+}
+
+static bool getInlineStackHelper(const InlineInfo &II, uint64_t Addr, 
+    std::vector<const InlineInfo *> &InlineStack) {
+  if (II.Ranges.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 (II.Name != 0)
+      InlineStack.insert(InlineStack.begin(), &II);
+    for (const auto &Child : II.Children) {
+      if (::getInlineStackHelper(Child, Addr, InlineStack))
+        break;
+    }
+    return !InlineStack.empty();
+  }
+  return false;
+}
+
+llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr) const {
+  InlineArray Result;
+  if (getInlineStackHelper(*this, Addr, Result))
+    return Result;
+  return llvm::None;
+}

llvm/trunk/lib/DebugInfo/GSYM/Range.cpp

+//===- Range.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include <algorithm>
+#include <inttypes.h>
+
+using namespace llvm;
+using namespace gsym;
+
+
+void AddressRanges::insert(const AddressRange &Range) {
+  if (Range.size() == 0)
+    return;
+  // Ranges.insert(std::upper_bound(Ranges.begin(), Ranges.end(), Range), Range);
+
+  // // Check if an existing range intersects with this range, and if so, 
+  // // grow the intersecting ranges instead of adding a new one.
+  auto Begin = Ranges.begin();
+  auto End = Ranges.end();
+  const auto Iter = std::upper_bound(Begin, End, Range);
+  if (Iter != Begin) {
+    auto PrevIter = Iter - 1;
+    // If the previous range itersects with "Range" they will be combined.
+    if (PrevIter->intersect(Range)) {
+      // Now check if the previous range intersects with the next range since
+      // the previous range was combined. If so, combine them and remove the
+      // next range.
+      if (PrevIter->intersect(*Iter))
+        Ranges.erase(Iter);
+      return;
+    }
+  }
+  // If the next range intersects with "Range", combined and return.
+  if (Iter != End && Iter->intersect(Range))
+    return;
+  Ranges.insert(Iter, Range);
+}
+
+bool AddressRanges::contains(uint64_t Addr) const {
+  if (Ranges.empty())
+    return false;
+  auto Begin = Ranges.begin();
+  auto Pos = std::upper_bound(Begin, Ranges.end(), Addr);
+  if (Pos == Begin)
+    return false;
+  --Pos;
+  return Pos->contains(Addr);
+}
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRange &R) {
+  return OS << '[' << HEX64(R.startAddress()) << " - " << HEX64(R.endAddress())
+            << ")";
+}
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRanges &AR) {
+  size_t Size = AR.size();
+  for (size_t I=0; I<Size; ++I) {
+    if (I)
+      OS << ' ';
+    OS << AR[I];
+  }
+  return OS;
+}
+

llvm/trunk/unittests/DebugInfo/CMakeLists.txt

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

llvm/trunk/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)

llvm/trunk/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;
+  const uint32_t NameOffset = 30;
+  FunctionInfo FI(StartAddr, Size, NameOffset);
+  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, NameOffset);
+  FunctionInfo A2(0x1000, 0x100, NameOffset);
+  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);
+  
+  // We use the < operator to take a variety of different FunctionInfo
+  // structs from a variety of sources: symtab, debug info, runtime info
+  // and we sort them and want the sorting to allow us to quickly get the
+  // best version of a function info. 
+  FunctionInfo FISymtab(StartAddr, Size, NameOffset);
+  FunctionInfo FIWithLines(StartAddr, Size, NameOffset);
+  FIWithLines.Lines.push_back(LineEntry(StartAddr,FileIdx,Line));
+  // Test that a FunctionInfo with just a name and size is less than one
+  // that has name, size and any number of line table entries
+  EXPECT_LT(FISymtab, FIWithLines);
+
+  FunctionInfo FIWithLinesAndInline = FIWithLines;
+  FIWithLinesAndInline.Inline.Ranges.insert(AddressRange(StartAddr, StartAddr + 0x10));
+  // Test that a FunctionInfo with name, size, and line entries is less than
+  // the same one with valid inline info
+  EXPECT_LT(FIWithLines, FIWithLinesAndInline);
+
+  // Test if we have an entry with lines and one with more lines for the same
+  // range, the ones with more lines is greater than the one with less.
+  FunctionInfo FIWithMoreLines = FIWithLines;
+  FIWithMoreLines.Lines.push_back(LineEntry(StartAddr,FileIdx,Line+5));
+  EXPECT_LT(FIWithLines, FIWithMoreLines);
+
+  // Test that if we have the same number of lines we compare the line entries
+  // in the FunctionInfo.Lines vector.
+  FunctionInfo FIWithLinesWithHigherAddress = FIWithLines;
+  FIWithLinesWithHigherAddress.Lines[0].Addr += 0x10;
+  EXPECT_LT(FIWithLines, FIWithLinesWithHigherAddress);
+}
+
+TEST(GSYMTest, TestInlineInfo) {
+  // Test InlineInfo structs.
+  InlineInfo II;
+  EXPECT_FALSE(II.isValid());
+  II.Ranges.insert(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.insert(AddressRange(0x100,0x200));
+  InlineInfo Inline1;
+  Inline1.Ranges.insert(AddressRange(0x150,0x160));
+  Inline1.Name = 1;
+  Inline1.CallFile = 1;
+  Inline1.CallLine = 11;
+  InlineInfo Inline1Sub1;
+  Inline1Sub1.Ranges.insert(AddressRange(0x152, 0x155));
+  Inline1Sub1.Name = 2;
+  Inline1Sub1.CallFile = 2;
+  Inline1Sub1.CallLine = 22;
+  InlineInfo Inline1Sub2;
+  Inline1Sub2.Ranges.insert(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);
+
+  // Make sure an address that is out of range won't match
+  EXPECT_FALSE(Root.getInlineStack(0x50));
+
+  // Verify that we get no inline stacks for addresses out of [0x100-0x200) 
+  EXPECT_FALSE(Root.getInlineStack(Root.Ranges[0].startAddress()-1));
+  EXPECT_FALSE(Root.getInlineStack(Root.Ranges[0].endAddress()));
+
+  // 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[0].startAddress()-1));
+  EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges[0].endAddress()));
+
+
+  // Verify we get one inline stack entry for addresses that are in
+  // [[0x150-0x160)) but not in [0x152-0x155) or [0x157-0x158)
+  auto InlineInfos = Root.getInlineStack(Inline1.Ranges[0].startAddress());
+  ASSERT_TRUE(InlineInfos);
+  ASSERT_EQ(InlineInfos->size(), 1u);
+  ASSERT_EQ(*InlineInfos->at(0), Inline1);
+  InlineInfos = Root.getInlineStack(Inline1.Ranges[0].endAddress()-1);
+  EXPECT_TRUE(InlineInfos);
+  ASSERT_EQ(InlineInfos->size(), 1u);
+  ASSERT_EQ(*InlineInfos->at(0), Inline1);
+
+  // Verify we get two inline stack entries for addresses that are in
+  // [0x152-0x155)
+  InlineInfos = Root.getInlineStack(Inline1Sub1.Ranges[0].startAddress());
+  EXPECT_TRUE(InlineInfos);
+  ASSERT_EQ(InlineInfos->size(), 2u);
+  ASSERT_EQ(*InlineInfos->at(0), Inline1Sub1);
+  ASSERT_EQ(*InlineInfos->at(1), Inline1);
+  InlineInfos = Root.getInlineStack(Inline1Sub1.Ranges[0].endAddress()-1);
+  EXPECT_TRUE(InlineInfos);
+  ASSERT_EQ(InlineInfos->size(), 2u);
+  ASSERT_EQ(*InlineInfos->at(0), Inline1Sub1);
+  ASSERT_EQ(*InlineInfos->at(1), Inline1);
+
+  // Verify we get two inline stack entries for addresses that are in
+  // [0x157-0x158)
+  InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].startAddress());
+  EXPECT_TRUE(InlineInfos);
+  ASSERT_EQ(InlineInfos->size(), 2u);
+  ASSERT_EQ(*InlineInfos->at(0), Inline1Sub2);
+  ASSERT_EQ(*InlineInfos->at(1), Inline1);
+  InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].endAddress()-1);
+  EXPECT_TRUE(InlineInfos);
+  ASSERT_EQ(InlineInfos->size(), 2u);
+  ASSERT_EQ(*InlineInfos->at(0), Inline1Sub2);
+  ASSERT_EQ(*InlineInfos->at(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::isContiguousWith() and
+  // llvm::gsym::AddressRange::intersects().
+  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.isContiguousWith(EndsBeforeRangeStart));
+  EXPECT_TRUE(Range.isContiguousWith(EndsAtRangeStart));
+  EXPECT_TRUE(Range.isContiguousWith(OverlapsRangeStart));
+  EXPECT_TRUE(Range.isContiguousWith(InsideRange));
+  EXPECT_TRUE(Range.isContiguousWith(OverlapsRangeEnd));
+  EXPECT_TRUE(Range.isContiguousWith(StartsAtRangeEnd));
+  EXPECT_FALSE(Range.isContiguousWith(StartsAfterRangeEnd));
+
+  EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart));
+  EXPECT_FALSE(Range.intersects(EndsAtRangeStart));
+  EXPECT_TRUE(Range.intersects(OverlapsRangeStart));
+  EXPECT_TRUE(Range.intersects(InsideRange));
+  EXPECT_TRUE(Range.intersects(OverlapsRangeEnd));
+  EXPECT_FALSE(Range.intersects(StartsAtRangeEnd));
+  EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd));
+
+  // Test the functions that maintain GSYM address ranges:
+  //  "bool AddressRange::contains(uint64_t Addr) const;"
+  //  "void AddressRanges::insert(const AddressRange &R);"
+  AddressRanges Ranges;
+  Ranges.insert(AddressRange(0x1000, 0x2000));
+  Ranges.insert(AddressRange(0x2000, 0x3000));
+  Ranges.insert(AddressRange(0x4000, 0x5000));
+
+  EXPECT_FALSE(Ranges.contains(0));
+  EXPECT_FALSE(Ranges.contains(0x1000-1));
+  EXPECT_TRUE(Ranges.contains(0x1000));
+  EXPECT_TRUE(Ranges.contains(0x2000));
+  EXPECT_TRUE(Ranges.contains(0x4000));
+  EXPECT_TRUE(Ranges.contains(0x2000-1));
+  EXPECT_TRUE(Ranges.contains(0x3000-1));
+  EXPECT_FALSE(Ranges.contains(0x3000+1));
+  EXPECT_TRUE(Ranges.contains(0x5000-1));
+  EXPECT_FALSE(Ranges.contains(0x5000+1));
+  EXPECT_FALSE(Ranges.contains(UINT64_MAX));
+
+  // Verify that intersecting ranges get combined
+  Ranges.clear();
+  Ranges.insert(AddressRange(0x1100, 0x1F00));
+  // Verify a wholy contained range that is added doesn't do anything.
+  Ranges.insert(AddressRange(0x1500, 0x1F00));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0], AddressRange(0x1100, 0x1F00));
+
+  // Verify a range that starts before and intersects gets combined.
+  Ranges.insert(AddressRange(0x1000, Ranges[0].startAddress()+1));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x1F00));
+
+  // Verify a range that starts inside and extends ranges gets combined.
+  Ranges.insert(AddressRange(Ranges[0].endAddress()-1, 0x2000));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000));
+
+  // Verify that adjacent ranges don't get combined
+  Ranges.insert(AddressRange(0x2000, 0x3000));
+  EXPECT_EQ(Ranges.size(), 2u);
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000));
+  EXPECT_EQ(Ranges[1], AddressRange(0x2000, 0x3000));
+  // Verify if we add an address range that intersects two ranges
+  // that they get combined
+  Ranges.insert(AddressRange(Ranges[0].endAddress()-1, 
+                             Ranges[1].startAddress()+1));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x3000));
+
+
+}
+
+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), "");
+}