[lld-macho] Implement basic export trie

[int3]

Summary

Build the trie by performing a three-way radix quicksort: We start by
sorting the strings by their first characters, then sort the strings
with the same first characters by their second characters, and so on
recursively. Each time the prefixes diverge, we add a node to the trie.
Thanks to @ruiu for the idea.

I used llvm-mc's radix quicksort implementation as a starting point. The
trie offset fixpoint code was taken from
MachONormalizedFileBinaryWriter.cpp.

Depends on D76908.

[int3]

update

[int3]

update

[int3]

update

[int3]

lld/MachO/ExportTrie.cpp

41–43

may want to consider making this a BumpPtrList

91

The original implementation used a unique BumpPtrAllocator instance for the export trie construction, which gets deallocated once trie serialization is complete. Here I am using the global bAlloc that doesn't deallocate till the end of the program. Not if it's worth using a local allocator instance to reduce memory consumption

193–196

This is basically a topological sort. It's unclear to me though why this approach (of finding every element starting from the root) was chosen vs doing a single preorder traversal of the trie...

[int3]

rebase

[int3]

update test to use symtab addresses

[ruiu]

lld/MachO/ExportTrie.cpp

12

I'd add a file comment to explain the structure of the export table, that is, the symbol table is a trie instead of the usual runs of null-terminated strings. So it can be prefix-compressed and more compact, though it's more complicated.

49

I wonder if you can use std::vector.

[ruiu]

lld/MachO/ExportTrie.cpp

53

Do you need this destructor?

67

Initialize with = 0 here.

76

addSymbol seem to keep the internal trie consistent all the time, but I don't think we need to split the work between addSymbol and build. We can make addSymbol just to store an argument to an array, and move the code for trie construction to build.

lld/MachO/ExportTrie.h

24

I don't think we need to be efficient here. I'd use std::vector<> instead.

[int3]

lld/MachO/ExportTrie.cpp

49

yeah that's an option. Probably not worth testing until we have more functionality implemented and can profile against real inputs though

lld/MachO/ExportTrie.h

24

There doesn't seem to be a way to wrap an std::vector in a raw_ostream though, which I need for the ULEB encoding functions. Would you prefer I use an std::string and a raw_string_ostream instead?

[int3]

lld/MachO/ExportTrie.cpp

76

Not sure I understand what you're going for. Do you mean to have TrieBuilder::addSymbol collect the symbols to export in a vector, and then have build() call TrieNode::addSymbol() for all the symbols right before serializing the trie?

[int3]

address some comments

[ruiu]

lld/MachO/ExportTrie.cpp

76

Yes, that's what I meant.

[ruiu]

lld/MachO/ExportTrie.cpp

48

super nit: substring is a single word

76

What I wanted to say is that it looks like the trie implemented in this file is designed with the generic Map use cases in mind. You can add a new string one at a time to an existing trie, and you can also look it up as if it were a map (it is actually a map). In order to that, we create a trie in memory. But I think we can avoid that. We can just accumulate added strings to a vector, and in build() we sort the strings and directly emit a serialized trie from the sorted strings.

lld/MachO/ExportTrie.h

24

Yeah, I guess so. Symbol tables are not that small, and there's only one symbol table for each output, so we don't need to optimize it by using an LLVM-specific class. std::string would just work fine.

[smeenai]

lld/MachO/ExportTrie.cpp

76

+1 – we should only need the trie for output purposes here.

193–196

Not having looked at this in detail yet, would they give comparable results?

[ruiu]

lld/MachO/ExportTrie.cpp

76

It is probably better to rewrite the code instead of borrowing it from the existing code. I believe it shouldn't take too much time, and it might even be a bit of fun to write from scratch.

[int3]

lld/MachO/ExportTrie.cpp

76

We can just accumulate added strings to a vector, and in build() we sort the strings and directly emit a serialized trie from the sorted strings.

Ah, I see what you mean. That would definitely be more memory/allocation-efficient. I guess we should do a radix sort instead of a simple std::sort so we don't compare prefixes needlessly.

193–196

I think the only difference would be the order (and therefore the offsets) of the serialized nodes. Might make things more or less compact, it's unclear to me...

[int3]

lld/MachO/ExportTrie.cpp

76

oh I see llvm-mc has a radix sort implementation in StringTableBuilder.cpp. Might steal that

[int3]

build trie via sorting

[int3]

rebase

[int3]

lld/MachO/ExportTrie.cpp

193–196

Aha, I see that ld64 has an -exported_symbols_order flag, so the export trie "can be optimized to make lookups of popular symbols faster". The implementation also secondarily sorts the trie by address. I guess that means dyld loads this trie lazily. I'll add a TODO to support this...

I think we can still implement it more efficiently than looking up every element from the root: While building the trie, we should keep track of the lowest user-ordered leaf that it contains. Then we can sort the nodes based on that.

[int3]

lld/MachO/ExportTrie.cpp

76

Btw, the current implementation still builds a trie explicitly in memory -- I think we need that in order to iteratively calculate the uleb offsets. But now the trie is built via sorting rather than repeated insertion. Compared to repeatedly inserting symbols, this approach is better because we don't have to repeatedly update / split nodes.

Let me know if this was roughly what you had in mind, or if I'm missing some way to avoid having the trie in memory altogether...

[int3]

rebase

[smeenai]

I haven't though about this too hard, but if -exported_symbols_order wasn't a thing, we wouldn't have to do the loop to convergence, right? We could just do a post-order traversal, so that the the offset of each child of a node is fixed before you reach that node. (The wrinkle is that the root node needs to be at the start of the trie, since all the offsets are positive, but you could just traverse everything except the root node and calculate their offsets, then calculate the size of the root node, then add that size to all the other offsets.)

I haven't thought very hard about how -exported_symbols_order will work in this scheme either, but your idea for that makes sense at a high level. It doesn't seem ld64 handles this super optimally either. For example, if you have symbols _a and _ab, and you want _ab to be ordered in the trie before _a (or just only have _ab in the exported symbols order file), ld64 produces:

<root>
  |
  _a
  |
  |-----
  |    |
  *b  *''

(terminal nodes prefixed with a *)

whereas without any order file, you would have gotten

<root>
  |
 *_a
  |
  *b

Both tries take the same number of node traversals to get to _ab, but the first one needlessly pessimizes _a in the process.

I'd be curious about exactly how dyld processes the export trie, to understand how much of a difference -exported_symbols_order might make.

Assuming that my post-order traversal scheme actually works, and assuming that we don't plan to support -exported_symbols_order any time soon, would it make sense to just use that scheme for now and figure out -exported_symbols_order when we get there? I suspect we'll run into a bunch more considerations when we actually get around to implementing that, so I don't think it's super important to be coding with that in mind right now. (As in, the post-order definitely won't work when we have to respect -exported_symbols_order, but we can think about that later.)

lld/MachO/ExportTrie.cpp

16

From what I understand of the trie structure, the strings for children are actually stored in the parent. This is interesting by itself, and it also implies that the root node is always the empty string. I think it's worth making a note of that and reflecting that in the diagram as well.

56

Nit: can this be part of the anonymous namespace above?

57

Should add a TODO about adding proper support for the reexport and stub-and-resolver flags.

72

I'd add a comment about what the return value signifies.

73

This is the 1 byte for the TerminalSize member, right? Might be clearer to explain that in the comment.

77

uleb128 of length of symbol info?

91

I think LLD generally just allocates everything using the global allocator and deallocates it in one fell swoop at the end (or just lets the OS clean it up), so this should be fine. I'd be curious if anything in LLD COFF or ELF uses local allocators though.

100

Why this assert? The nodeSize (or TerminalSize as macho2yaml terms it) is a ULEB128, right?

108

You'd just have to split up the node in that case, right?

138

Super nit: have the comments in the order of the parameters (or vice versa).

153

Would it be preferable to use either the median or a random pivot? (I'm assuming the standard quicksort considerations for pivots apply, namely that always using the first element would trigger the quadratic worst case for an already sorted input.)

185

Did you mean sortAndBuild?

Is there an easy way to either express this as a loop or trust that the compiler will do the tail call optimization? I don't mind the goto very much, but I'm wondering how it compares to the alternatives.

193–196

Yeah, -exported_symbols_order flag is a wrinkle :/ What you said makes sense for when we have to support that though.

[int3]

Post-order wouldn't work because the offsets are from the start of the export trie section, not from the parent node... not sure why it was designed that way :/

lld/MachO/ExportTrie.cpp

16

good catch, will fix

100

nope, it's a byte. Only the offsets are ulebs

108

yeah

153

yeah they do apply. I'll pick the median

185

Oops, this was copypasta from llvm-mc's original implementation (they called it multikeySort there)

The TCO was also from that implementation, but I think it's a "standard" quicksort optimization too, at least for the normal two-way quicksort. Wikipedia says that it's "suggested by Sedgwick and widely used in practice": https://en.wikipedia.org/wiki/Quicksort#Optimizations

[int3]

Re -exported_symbols_order, I think the scheme I have in mind would only change how the nodes are ordered, but not which ones are created, so we will hopefully not run into the weird ld64 case you described.

[int3]

lld/MachO/ExportTrie.cpp

91

I made that comment on the original build-trie-via-insertion diff, which did a bunch of unnecessary string copying. The current diff just uses StringRefs that point to the character buffers of the symbols themselves and assumes they are immutable while the trie is being built and serialized, so this is no longer an issue.

[int3]

lld/MachO/ExportTrie.cpp

100

nvm, I'm wrong, oops. It's a uleb indeed

[smeenai]

In D76977#2009150, @int3 wrote:

Post-order wouldn't work because the offsets are from the start of the export trie section, not from the parent node... not sure why it was designed that way :/

Ah, right ... I was initially thinking you could just compute the size of the root node once you reach it and then adjust all the other offsets accordingly, but of course adjusting the offset might change the length of its ULEB encoding, and then you're back in the same situation.

[int3]

lld/MachO/ExportTrie.cpp

16

I feel like the root node corresponding to the entry string is pretty standard for tries though. Also I think it makes more sense to say the strings are stored on the edges rather than the parent. I'll update the comment + diagram to reflect that; hopefully it's clearer from the new diagram that the root node corresponds to the empty string

100

I realized that the usage of nodeSize is inconsistent and confusing. In updateOffset() it includes the terminal size and the edges, but in writeTo() it doesn't. I'll rename nodeSize to terminalSize in writeTo().

185

It seems like there's no way to force the compiler to do TCO. There are only attributes to tell clang *not* to do TCO.

[int3]

address comments

[smeenai]

LGTM.

lld/MachO/ExportTrie.cpp

16

Looks good!

165

Nit: use vec.empty()

185

Yeah. LLVM has a musttail attribute, but I don't think that's exposed to clang, and IIRC even that doesn't guarantee a tail call. Ideally the optimizer would be able to figure this out on its own, but there's no guarantee of that.

Any opinions on the current goto structure vs. wrapping the whole thing in a while (!vec.empty()) and adding an explicit return in the isTerminal case? I think that'd be equivalent, though I guess the goto makes the tail recursive call more apparent.

[MaskRay]

lld/MachO/ExportTrie.cpp

139

Nit: auto *

lld/test/MachO/symtab.s

6

I wish we can have a conciser llvm-readobj output... Due to llvm-readobj's verbosity, I prefer llvm-readelf for ELF objects...

[int3]

address comments

lld/MachO/ExportTrie.cpp

185

Yeah I think while() here would make for more confusing code for the reason you mentioned (plus add more indentation :P)

lld/test/MachO/symtab.s

6

Hm, llvm-objdump --syms is terser, though I'm not sure it prints all the symbol info (in particular the flags). For the other tests where I just want the addresses of the symbols, I use objdump; but since this test is specifically for the symtab, I think it makes sense to get the most detailed representation of the symbols.

[int3]

rebase

[smeenai]

lld/MachO/ExportTrie.cpp

185

I randomly came across this thread again. https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html is a fun related read :)

lld/MachO/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(MachOOptionsTableGen)
 
 add_lld_library(lldMachO2
   Arch/X86_64.cpp
   Driver.cpp
+  ExportTrie.cpp
   InputFiles.cpp
   InputSection.cpp
   OutputSegment.cpp
   SymbolTable.cpp
   Symbols.cpp
   SyntheticSections.cpp
   Target.cpp
   Writer.cpp

lld/MachO/ExportTrie.h

+//===- ExportTrie.h ---------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_MACHO_EXPORT_TRIE_H
+#define LLD_MACHO_EXPORT_TRIE_H
+
+#include "llvm/ADT/ArrayRef.h"
+
+#include <vector>
+
+namespace lld {
+namespace macho {
+
+struct TrieNode;
+class Symbol;
+
+class TrieBuilder {
+public:
+  void addSymbol(const Symbol &sym) { exported.push_back(&sym); }
+  // Returns the size in bytes of the serialized trie.
+  size_t build();
+  void writeTo(uint8_t *buf);
+
+private:
+  TrieNode *makeNode();
+  void sortAndBuild(llvm::MutableArrayRef<const Symbol *> vec, TrieNode *node,
+                    size_t lastPos, size_t pos);
+
+  std::vector<const Symbol *> exported;
+  std::vector<TrieNode *> nodes;
+};
+
+} // namespace macho
+} // namespace lld
+
+#endif

lld/MachO/ExportTrie.cpp

+//===- ExportTrie.cpp -----------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This is a partial implementation of the Mach-O export trie format. It's
+// essentially a symbol table encoded as a compressed prefix trie, meaning that
+// the common prefixes of each symbol name are shared for a more compact
+// representation. The prefixes are stored on the edges of the trie, and one
+// edge can represent multiple characters. For example, given two exported
+// symbols _bar and _baz, we will have a trie like this (terminal nodes are
+// marked with an asterisk):
+//
+//              +-+-+
+//              |   | // root node
+//              +-+-+
+//                |
+//                | _ba
+//                |
+//              +-+-+
+//              |   |
+//              +-+-+
+//           r /     \ z
+//            /       \
+//        +-+-+       +-+-+
+//        | * |       | * |
+//        +-+-+       +-+-+
+//
+// More documentation of the format can be found in
+// llvm/tools/obj2yaml/macho2yaml.cpp.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ExportTrie.h"
+#include "Symbols.h"
+
+#include "lld/Common/Memory.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/BinaryFormat/MachO.h"
+#include "llvm/Support/LEB128.h"
+
+using namespace llvm;
+using namespace llvm::MachO;
+using namespace lld;
+using namespace lld::macho;
+
+namespace {
+
+struct Edge {
+  Edge(StringRef s, TrieNode *node) : substring(s), child(node) {}
+
+  StringRef substring;
+  struct TrieNode *child;
+};
+
+struct ExportInfo {
+  uint64_t address;
+  // TODO: Add proper support for re-exports & stub-and-resolver flags.
+};
+
+} // namespace
+
+namespace lld {
+namespace macho {
+
+struct TrieNode {
+  std::vector<Edge> edges;
+  Optional<ExportInfo> info;
+  // Estimated offset from the start of the serialized trie to the current node.
+  // This will converge to the true offset when updateOffset() is run to a
+  // fixpoint.
+  size_t offset = 0;
+
+  // Returns whether the new estimated offset differs from the old one.
+  bool updateOffset(size_t &nextOffset);
+  void writeTo(uint8_t *buf);
+};
+
+bool TrieNode::updateOffset(size_t &nextOffset) {
+  // Size of the whole node (including the terminalSize and the outgoing edges.)
+  // In contrast, terminalSize only records the size of the other data in the
+  // node.
+  size_t nodeSize;
+  if (info) {
+    uint64_t flags = 0;
+    uint32_t terminalSize =
+        getULEB128Size(flags) + getULEB128Size(info->address);
+    // Overall node size so far is the uleb128 size of the length of the symbol
+    // info + the symbol info itself.
+    nodeSize = terminalSize + getULEB128Size(terminalSize);
+  } else {
+    nodeSize = 1; // Size of terminalSize (which has a value of 0)
+  }
+  // Compute size of all child edges.
+  ++nodeSize; // Byte for number of children.
+  for (Edge &edge : edges) {
+    nodeSize += edge.substring.size() + 1             // String length.
+                + getULEB128Size(edge.child->offset); // Offset len.
+  }
+  // On input, 'nextOffset' is the new preferred location for this node.
+  bool result = (offset != nextOffset);
+  // Store new location in node object for use by parents.
+  offset = nextOffset;
+  nextOffset += nodeSize;
+  return result;
+}
+
+void TrieNode::writeTo(uint8_t *buf) {
+  buf += offset;
+  if (info) {
+    // TrieNodes with Symbol info: size, flags address
+    uint64_t flags = 0; // TODO: emit proper flags
+    uint32_t terminalSize =
+        getULEB128Size(flags) + getULEB128Size(info->address);
+    buf += encodeULEB128(terminalSize, buf);
+    buf += encodeULEB128(flags, buf);
+    buf += encodeULEB128(info->address, buf);
+  } else {
+    // TrieNode with no Symbol info.
+    *buf++ = 0; // terminalSize
+  }
+  // Add number of children. TODO: Handle case where we have more than 256.
+  assert(edges.size() < 256);
+  *buf++ = edges.size();
+  // Append each child edge substring and node offset.
+  for (const Edge &edge : edges) {
+    memcpy(buf, edge.substring.data(), edge.substring.size());
+    buf += edge.substring.size();
+    *buf++ = '\0';
+    buf += encodeULEB128(edge.child->offset, buf);
+  }
+}
+
+TrieNode *TrieBuilder::makeNode() {
+  auto *node = make<TrieNode>();
+  nodes.emplace_back(node);
+  return node;
+}
+
+static int charAt(const Symbol *sym, size_t pos) {
+  StringRef str = sym->getName();
+  if (pos >= str.size())
+    return -1;
+  return str[pos];
+}
+
+// Build the trie by performing a three-way radix quicksort: We start by sorting
+// the strings by their first characters, then sort the strings with the same
+// first characters by their second characters, and so on recursively. Each
+// time the prefixes diverge, we add a node to the trie.
+//
+// node:    The most recently created node along this path in the trie (i.e.
+//          the furthest from the root.)
+// lastPos: The prefix length of the most recently created node, i.e. the number
+//          of characters along its path from the root.
+// pos:     The string index we are currently sorting on. Note that each symbol
+//          S contained in vec has the same prefix S[0...pos).
+void TrieBuilder::sortAndBuild(MutableArrayRef<const Symbol *> vec,
+                               TrieNode *node, size_t lastPos, size_t pos) {
+tailcall:
+  if (vec.empty())
+    return;
+
+  // Partition items so that items in [0, i) are less than the pivot,
+  // [i, j) are the same as the pivot, and [j, vec.size()) are greater than
+  // the pivot.
+  const Symbol *pivotSymbol = vec[vec.size() / 2];
+  int pivot = charAt(pivotSymbol, pos);
+  size_t i = 0;
+  size_t j = vec.size();
+  for (size_t k = 0; k < j;) {
+    int c = charAt(vec[k], pos);
+    if (c < pivot)
+      std::swap(vec[i++], vec[k++]);
+    else if (c > pivot)
+      std::swap(vec[--j], vec[k]);
+    else
+      k++;
+  }
+
+  bool isTerminal = pivot == -1;
+  bool prefixesDiverge = i != 0 || j != vec.size();
+  if (lastPos != pos && (isTerminal || prefixesDiverge)) {
+    TrieNode *newNode = makeNode();
+    node->edges.emplace_back(pivotSymbol->getName().slice(lastPos, pos),
+                             newNode);
+    node = newNode;
+    lastPos = pos;
+  }
+
+  sortAndBuild(vec.slice(0, i), node, lastPos, pos);
+  sortAndBuild(vec.slice(j), node, lastPos, pos);
+
+  if (isTerminal) {
+    assert(j - i == 1); // no duplicate symbols
+    node->info = {pivotSymbol->getVA() + ImageBase};
+  } else {
+    // This is the tail-call-optimized version of the following:
+    // sortAndBuild(vec.slice(i, j - i), node, lastPos, pos + 1);
+    vec = vec.slice(i, j - i);
+    ++pos;
+    goto tailcall;
+  }
+}
+
+size_t TrieBuilder::build() {
+  if (exported.empty())
+    return 0;
+
+  TrieNode *root = makeNode();
+  sortAndBuild(exported, root, 0, 0);
+
+  // Assign each node in the vector an offset in the trie stream, iterating
+  // until all uleb128 sizes have stabilized.
+  size_t offset;
+  bool more;
+  do {
+    offset = 0;
+    more = false;
+    for (TrieNode *node : nodes)
+      more |= node->updateOffset(offset);
+  } while (more);
+
+  return offset;
+}
+
+void TrieBuilder::writeTo(uint8_t *buf) {
+  for (TrieNode *node : nodes)
+    node->writeTo(buf);
+}
+
+} // namespace macho
+} // namespace lld

lld/MachO/SyntheticSections.h

 //===- SyntheticSections.h -------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_SYNTHETIC_SECTIONS_H
 #define LLD_MACHO_SYNTHETIC_SECTIONS_H
 
+#include "ExportTrie.h"
 #include "InputSection.h"
 #include "Target.h"
 #include "llvm/ADT/SetVector.h"
 
 using namespace llvm::MachO;
 
 namespace lld {
 namespace macho {
public:
   SmallVector<char, 128> contents;
 };
 
 // Stores a trie that describes the set of exported symbols.
 class ExportSection : public InputSection {
 public:
   ExportSection();
   void finalizeContents();
-  size_t getSize() const override { return contents.size(); }
+  size_t getSize() const override { return size; }
   // Like other sections in __LINKEDIT, the export section is special: its
   // offsets are recorded in the LC_DYLD_INFO_ONLY load command, instead of in
   // section headers.
   bool isHidden() const override { return true; }
   void writeTo(uint8_t *buf) override;
 
-  SmallVector<char, 128> contents;
+private:
+  TrieBuilder trieBuilder;
+  size_t size = 0;
 };
 
 // Stores the strings referenced by the symbol table.
 class StringTableSection : public InputSection {
 public:
   StringTableSection();
   // Returns the start offset of the added string.
   uint32_t addString(StringRef);

lld/MachO/SyntheticSections.cpp

 //===- SyntheticSections.cpp ---------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "SyntheticSections.h"
 #include "Config.h"
+#include "ExportTrie.h"
 #include "InputFiles.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Support/EndianStream.h"

 }
 
 ExportSection::ExportSection() {
   segname = segment_names::linkEdit;
   name = section_names::export_;
 }
 
 void ExportSection::finalizeContents() {
-  raw_svector_ostream os{contents};
-  std::vector<const Defined *> exported;
   // TODO: We should check symbol visibility.
   for (const Symbol *sym : symtab->getSymbols())
     if (auto *defined = dyn_cast<Defined>(sym))
-      exported.push_back(defined);
-
-  if (exported.empty())
-    return;
-
-  if (exported.size() > 1) {
-    error("TODO: Unable to export more than 1 symbol");
-    return;
-  }
+      trieBuilder.addSymbol(*defined);
+  size = trieBuilder.build();
 
-  const Defined *sym = exported.front();
-  os << (char)0; // Indicates non-leaf node
-  os << (char)1; // # of children
-  os << sym->getName() << '\0';
-  encodeULEB128(sym->getName().size() + 4, os); // Leaf offset
-
-  // Leaf node
-  uint64_t addr = sym->getVA() + ImageBase;
-  os << (char)(1 + getULEB128Size(addr));
-  os << (char)0; // Flags
-  encodeULEB128(addr, os);
-  os << (char)0; // Terminator
-}
-
-void ExportSection::writeTo(uint8_t *buf) {
-  memcpy(buf, contents.data(), contents.size());
-}
+void ExportSection::writeTo(uint8_t *buf) { trieBuilder.writeTo(buf); }
 
 SymtabSection::SymtabSection(StringTableSection &stringTableSection)
     : stringTableSection(stringTableSection) {
   segname = segment_names::linkEdit;
   name = section_names::symbolTable;
   // TODO: When we introduce the SyntheticSections superclass, we should make
   // all synthetic sections aligned to WordSize by default.
   align = WordSize;

lld/test/MachO/Inputs/libhello.s

 .section __TEXT,__cstring
-.globl _hello_world
+.globl _hello_world, _hello_its_me
 
 _hello_world:
 .asciz "Hello world!\n"
+
+_hello_its_me:
+.asciz "Hello, it's me\n"

lld/test/MachO/dylink.s

 # RUN:   @executable_path/libgoodbye.dylib %t/libgoodbye.o -o %t/libgoodbye.dylib
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/dylink.o
 # RUN: lld -flavor darwinnew -o %t/dylink -Z -L%t -lhello -lgoodbye %t/dylink.o
 # RUN: llvm-objdump --bind -d %t/dylink | FileCheck %s
 
 # CHECK: movq [[#%u, HELLO_OFF:]](%rip), %rsi
 # CHECK-NEXT: [[#%x, HELLO_RIP:]]:
 
+# CHECK: movq [[#%u, HELLO_ITS_ME_OFF:]](%rip), %rsi
+# CHECK-NEXT: [[#%x, HELLO_ITS_ME_RIP:]]:
+
 # CHECK: movq [[#%u, GOODBYE_OFF:]](%rip), %rsi
 # CHECK-NEXT: [[#%x, GOODBYE_RIP:]]:
 
 # CHECK-LABEL: Bind table:
-# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, HELLO_RIP + HELLO_OFF]]     pointer 0 libhello   _hello_world
-# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, GOODBYE_RIP + GOODBYE_OFF]] pointer 0 libgoodbye _goodbye_world
+# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, HELLO_RIP + HELLO_OFF]]               pointer 0 libhello   _hello_world
+# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, HELLO_ITS_ME_RIP + HELLO_ITS_ME_OFF]] pointer 0 libhello   _hello_its_me
+# CHECK-DAG: __DATA_CONST __got 0x{{0*}}[[#%x, GOODBYE_RIP + GOODBYE_OFF]]           pointer 0 libgoodbye _goodbye_world
 
 .section __TEXT,__text
 .globl _main
 
 _main:
   movl $0x2000004, %eax # write() syscall
   mov $1, %rdi # stdout
   movq _hello_world@GOTPCREL(%rip), %rsi
   mov $13, %rdx # length of str
   syscall
 
   movl $0x2000004, %eax # write() syscall
   mov $1, %rdi # stdout
+  movq _hello_its_me@GOTPCREL(%rip), %rsi
+  mov $15, %rdx # length of str
+  syscall
+
+  movl $0x2000004, %eax # write() syscall
+  mov $1, %rdi # stdout
   movq _goodbye_world@GOTPCREL(%rip), %rsi
   mov $15, %rdx # length of str
   syscall
   mov $0, %rax
   ret

lld/test/MachO/export-trie.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: lld -flavor darwinnew -dylib %t.o -o %t.dylib
+
+# RUN: llvm-objdump --syms --exports-trie %t.dylib | \
+# RUN:   FileCheck %s --check-prefix=EXPORTS
+# EXPORTS-LABEL: SYMBOL TABLE:
+# EXPORTS-DAG:   [[#%x, HELLO_ADDR:]] {{.*}} _hello
+# EXPORTS-DAG:   [[#%x, HELLO_WORLD_ADDR:]] {{.*}} _hello_world
+# EXPORTS-DAG:   [[#%x, HELLO_ITS_ME_ADDR:]] {{.*}} _hello_its_me
+# EXPORTS-DAG:   [[#%x, HELLO_ITS_YOU_ADDR:]] {{.*}} _hello_its_you
+# EXPORTS-LABEL: Exports trie:
+# EXPORTS-DAG:   0x{{0*}}[[#%X, HELLO_ADDR]] _hello
+# EXPORTS-DAG:   0x{{0*}}[[#%X, HELLO_WORLD_ADDR]] _hello_world
+# EXPORTS-DAG:   0x{{0*}}[[#%x, HELLO_ITS_ME_ADDR:]] _hello_its_me
+# EXPORTS-DAG:   0x{{0*}}[[#%x, HELLO_ITS_YOU_ADDR:]] _hello_its_you
+
+## Check that we are sharing prefixes in the trie.
+# RUN: obj2yaml %t.dylib | FileCheck %s
+# CHECK-LABEL: ExportTrie:
+# CHECK: Name: ''
+# CHECK: Name: _hello
+# CHECK: Name: _
+# CHECK: Name: world
+# CHECK: Name: its_
+# CHECK: Name: me
+# CHECK: Name: you
+
+.section __TEXT,__cstring
+.globl _hello, _hello_world, _hello_its_me, _hello_its_you
+
+## Test for when an entire symbol name is a prefix of another.
+_hello:
+.asciz "Hello!\n"
+
+_hello_world:
+.asciz "Hello world!\n"
+
+.data
+_hello_its_me:
+.asciz "Hello, it's me\n"
+
+_hello_its_you:
+.asciz "Hello, it's you\n"

lld/test/MachO/no-exports-dylib.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: lld -flavor darwinnew -dylib %t.o -o %t.dylib
+
+# RUN: obj2yaml %t.dylib | FileCheck %s
+# CHECK: export_size: 0

lld/test/MachO/symtab.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: lld -flavor darwinnew -o %t %t.o
 # RUN: llvm-readobj -symbols %t | FileCheck %s
 
 # CHECK:      Symbols [
 # CHECK-NEXT:   Symbol {
 # CHECK-NEXT:     Name: _main
 # CHECK-NEXT:     Extern
 # CHECK-NEXT:     Type: Section (0xE)
 # CHECK-NEXT:     Section: __text (0x1)
 # CHECK-NEXT:     RefType:
 # CHECK-NEXT:     Flags [ (0x0)
 # CHECK-NEXT:     ]
 # CHECK-NEXT:     Value:
 # CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: bar
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __text (0x1)
+# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value:
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: foo
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __data
+# CHECK-NEXT:     RefType:
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value:
+# CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
+.data
+.global foo
+foo:
+  .asciz "Hello world!\n"
+
+.text
+.global bar
 .global _main
 
 _main:
   mov $0, %rax
   ret
+
+bar:
+  mov $2, %rax
+  ret