[lld-macho] create __TEXT,__unwind_info from __LD,__compact_unwind

[gkm]

Summary

Digest the input __LD,__compact_unwind and produce the output __TEXT,__unwind_info. This is the initial commit with the major functionality.

Successor commits will add handling for ...

• __TEXT,__eh_frame
• personalities & LSDA
• -r pass-through

[gkm]

• Relocate some macro definitions into libunwind/include/mach-o/compact_unwind_encoding.h
• Decouple target word size from the host word size for the compact unwind entry structs

[int3]

just a partial review for now... will come back and do a deeper reading next week after I understand a bit more about the CU format.

lld/MachO/OutputSegment.cpp

54

nit: StringRefs can be compared using ==

lld/MachO/UnwindInfo.cpp

2

missing license header

59

I think this should be isNeeded(), not isHidden() -- "hidden" indicates that the section header is absent but that the section data itself should still be emitted

94

nit: targetIsec would be clearer

140

frequencies

lld/MachO/UnwindInfo.h

52–67

why the need to mark everything as mutable?

lld/MachO/Writer.cpp

413–414

This seems a bit hacky. Do we really have to put the __compact_unwind sections in an OutputSegment? If we're not going to output them, could we just put all these InputSections in a vector contained in UnwindInfoSection?

Also, we may want to support emitting object files at some point via -r, in which case we'll actually want to emit the __LD segment at a valid position.

lld/test/MachO/tools/validate-unwind-info.py

90

this seems unnecessary given that we'll be exiting anyway when this function returns

[gkm]

lld/MachO/UnwindInfo.h

52–67

The work of morphing __LD,__compact_unwind into __TEXT,__unwind_info happens in uint64_t getSize() const and void writeTo(uint8_t *buf) const, which can only be logically const, but not physically.

lld/MachO/Writer.cpp

413–414

I agree that it could use some improvement. I will revisit.

Behaviorally, __LD,__compact_unwind is a MergedOutputSegment, except with different timing and destination: we relocate & write it to a temp buffer from Writer::assignAddresses()) rather than writing to the final link output from Writer::writeSections(). We need to relocate it fully in order to compute the size of the __TEXT,__unwind_info section when laying-out sections & binding to addresses.

You are quite right regarding -r, which makes __LD,__compact_unwind a completely normal MergedOutputSegment.

lld/test/MachO/tools/validate-unwind-info.py

90

True, but since I explicitly sys.exit("... diagnostic ...") on error, for symmetry I chose to explicitly sys.exit() on success. I dislike falling through the floor of main, despite language guarantees, and since sys.exit() accepts a string arg on error, I prefer that to using numeric return STATUS.

[gkm]

Update according to Jez's simple review-feedback items - i.e., everything except the hackiness surrounding __LD,__compact_unwind's anomalies as a MergedOutputSection.

[gkm]

• Rework pageBounds as a simple vector rather than a vector of pairs, and expand associated comments

[gkm]

• s/std::max/std::min/
• Revert to simple llvm-lit test format, since bash is unnecessary

[gkm]

• pass functionAddressMax via lambda capture rather than via constructed cuEntry
• heed clang-tidy's advice

[gkm]

Cleanups:

• s/totalCuEntries/cuCount/
• constify all CompactUnwindEntry64*
• simplify level-1 index sentinel address calculation

[gkm]

• Correction in lld/MachO/UnwindInfo.h: s/LLD_MACHO_COMPACT_UNWIND_H/LLD_MACHO_UNWIND_INFO_H/
• Move some constant definitions that belong in libunwind/include/mach-o/compact_unwind_encoding.h

[gkm]

• Revise the arg signature for the comparison lambda for std::lower_bound() to emphasize that the 2nd pointer argument is ignored. Rather, we pass the comparand via lambda capture.

[gkm]

Improvements & cleanups to generate-cfi-funcs.py:

• add --functions=N arg
• move some comments into doc strings

[gkm]

Improvements & cleanups to validate-unwind-info.py:

• accept input from multiple files or stdin
• fail if any expected categories of input are absent

[int3]

lld/MachO/UnwindInfo.h

52–67

I would much prefer if we could have a method that explicitly computes the unwind info... but first let me see if I understand the constraints here.

From what I understand, the size of the unwind info depends on the values of CompactUnwindEntry64::functionAddress, or more precisely, their relative offsets. So we need to assign addresses to our functions before computing the unwind info size. After addresses are assigned, the cuSection->writeTo() call below will update the functionAddress entries to point to the final addresses, after which we can compute the needed size. Does all that sound right?

From what I can tell, ld64 calculates unwind info size based on "tentative addresses", which I think have the right relative offsets, though their final values have yet to be fixed. I wonder if we could do something similar with our current design...

[int3]

lld/MachO/UnwindInfo.h

52–67

Also -- do you know if it's possible for unwind info to point to functions that reside in sections other than __text?

[gkm]

lld/MachO/UnwindInfo.h

52–67

Yes, that's substantially correct, and I will elaborate:

UnwindInfoSection::getSize() must process the compact unwind entries and partition them into 4 KiB second-level pages in order to determine the final size of the __TEXT,__unwind_info. There are three factors that influence layout & therefore size:

1. A maximum of 1021 entries can fit into a 4 KiB page
2. The difference between address of first and last functions in a second-level page must be less than 2^24. The page will be cut short and remain under-filled when a candidate entry's 24-bit relative offset field would overflow.
3. We do a linear scan and fold adjacent entries that have the same encoding, thus laying-out fewer entries in the output than are present in the input.

As currently implemented, I use mutable data members to cache the necessary and substantial work done in UnwindInfoSection::getSize() const so that UnwindInfoSection::writeTo() const need not redo it.

I believe it is not strictly necessary to relocate the compact unwind entries in getSize(). I can probably work with the raw input sections for page partitioning and entry folding, though the code will be trickier, and I won't escape the need to relocate later in writeTo() for sake of LSDA and personality addresses.

I chose to use data members as cache, to relocate early, and to use mutable to work-around constness of getSize() and writeTo() because that results in code that does things in the proper sequence, and in the most straightforward manner for sake of clarity and efficiency.

52–67

With assembler language, anything is possible. I assume one can place compiled functions in alternate sections via attributes or pragmas. Those sections might be discontiguous with __text, and therefore require lay-out in to distinct second-level pages. I don't know if ld64 supports non-__text compact unwind. I will need to conjure some test cases to see how it behaves. If ld64 doesn't handle non-__text, then we won't either. If it does, then I will add that later.

[gkm]

lld/MachO/UnwindInfo.cpp:

• Remove redundant unwind_info_section_header_lsda_entry, and use existing unwind_info_section_header_lsda_index_entry instead.
• Don't cache UnwindInfoSection::isNeeded() result since it is only called once.

lld/test/MachO/tools/generate-cfi-funcs.py:

• Permute the register save set in order to generate a larger variety of encodings.
• Align generated functions at larger boundary so it works for testing ld64 also.

lld/test/MachO/tools/validate-unwind-info.py

• Expand the object-file encoding regexp to capture optional personality+lsda

[int3]

lld/MachO/UnwindInfo.h

52–67

I believe it is not strictly necessary to relocate the compact unwind entries in getSize(). I can probably work with the raw input sections for page partitioning and entry folding

How about doing most of what's currently in getSize() in a finalizeContents() method instead, much like what is currently being done for the the __LINKEDIT sections? My main concern is -- aside from a mutating method being marked as const -- is that compact unwind's getSize() has an implicit dependency on the addresses of another section. Other synthetic sections' finalizeContent methods have such a dependency, too, so this would fit the mold.

Of course, unlike the __LINKEDIT sections, the address assignments of later sections do depend on compact unwind's size, so we'll have to call it in the middle of assignAddresses. Such special-casing of CW would be a bit more verbose than what we currently have, but I think it's a good thing to make the uniqueness of compact unwind's requirements explicit.

[gkm]

Do the work in finalize() member rather than getSize() const. Drop mutable from data members. Ahhh! So much nicer!

[gkm]

• use %python prefix in test file
• minor cleanups

[int3]

Having things in finalize() indeed looks a lot cleaner :D

lld/MachO/SyntheticSections.h

22

this include doesn't seem necessary

lld/MachO/UnwindInfo.cpp

92–93

is the Twine() call here necessary? I would expect the concatenated StringRefs to already be a Twine

108

ditto, avoid <map>

121

codebase convention is to avoid curly braces for one-liner blocks

128

frequencies

148

successive

151

pageBounds

156

within

157–159

nit 1: the type here is pretty verbose, a type alias would be nice (auto would be acceptable here too I think)

nit 2: it0 and itN aren't the most descriptive names... something like intervalStart and intervalMax would be nice

168–169

why not pass functionAddressMax in as the 3rd parameter to lower_bound?

edit: oh, because the return type isn't the container element type. would be good to have a comment :)

194–197

can be rm'ed

212

would be good to have a comment to the effect that there are a bunch of integer arrays immediately after the section header (I had to pause and think about what &uip[1] meant)

258

what does a kind of 3 indicate?

lld/MachO/UnwindInfo.h

50

try to avoid <map> if possible: https://llvm.org/docs/ProgrammersManual.html#map

also the key here should be compact_unwind_encoding_t to be consistent :)

51

nit: I'd prefer structs over pairs for readable field names

lld/MachO/Writer.cpp

413–414

I think it might be worthwhile to duplicate some of the code in InputSection::writeTo to specialize it for the compact unwind case. The current writeTo code assumes that both the source and target sections referenced by a relocation have their final output addresses determined. But this is not true for the compact unwind section -- it doesn't have a valid output address. It just happens to work because there are no pcrel relocations involved. We should really error out if we see a pcrel relocation while relocating __compact_unwind.

Creating a separate compact unwind relocating method would free us from having to create Output{Segments, Sections} that we discard later. I'm hoping we can retain the invariant where we add OutputSections to OutputSegments only after we have determined that they are needed.

lld/test/MachO/compact-unwind.test

4–6

My understanding of the need for generate-cfi-funcs.py is that some test cases need to be very large in order to exercise the edge cases in the implementation. In addition to providing that functionality, this script also serves as a fuzzer by generating random test cases. Would it be possible for the unit test to instead enumerate a small number of cases that cover all important code paths, in order that we run fewer test cases?

[int3]

lld/MachO/UnwindInfo.cpp

91–93

Is this check really necessary? What kind of errors are we defending against? I would rather we not loop over the relocations unless necessary (for performance)

96–97

CU relocations can be section-based. Just checked a simple program:

~/tmp: llvm-readobj --relocations --expand-relocs bar.o

File: bar.o
Format: Mach-O 64-bit x86-64
Arch: x86_64
AddressSize: 64bit
Relocations [
  Section __compact_unwind {
    Relocation {
      Offset: 0x0
      PCRel: 0
      Length: 3
      Type: X86_64_RELOC_UNSIGNED (0)
      Section: __text (1)
    }
  }
]
~/tmp: cat bar.cpp
int foo() {
  return 123;
}

[smeenai]

lld/MachO/UnwindInfo.cpp

91–93

Yup. I don't have the full context here yet, but https://lld.llvm.org/NewLLD.html#numbers-you-want-to-know is relevant.

[gkm]

lld/MachO/UnwindInfo.cpp

91–93

This is an assertion--a sanity check on my own assumptions. Once I tested more widely, I will have no further use for it. A TODO comment to convey my intention is appropriate.

92–93

Regarding Twine(): I meant to only pass the initial string constant so that later + operands would be chained to it. I did not mean to pass entire concat expression. I used explicit Twine() following Saleem's example in an earlier diff. I'm happy to drop it. I see that diag functions already coerce string constants to Twine anyway.

96–97

Yes. I expect relocs to all reference sections whose address is assigned, i.e., __TEXT,__text. The assertion checks if this is ever NOT the case.

168–169

I added a comment explaining the choice.

lld/MachO/UnwindInfo.h

51

commonEncodings works best as a vector of pairs because it is filled from a DenseMap iterator which returns precisely the pairs we desire.

lld/MachO/Writer.cpp

413–414

I still owe you an answer for this one ...

lld/test/MachO/compact-unwind.test

4–6

It is already a single test case, made deterministic by passing --seed' so that check-lld-macho` runs are consistent. The multiplicity that might be reduced is the number of functions generated for that one test case. However, since I need to test boundary conditions around breaking 1021-entry pages, my options are limited. If there is a way to prefer an installed llvm-mc over the locally built one, that would solve it.

[gkm]

lld/MachO/UnwindInfo.cpp

91–93

I am only looping over a subset of relocs, numbered 1+ per function. The "+" represents the subset of functions that have personality+lsda.

[gkm]

• follow review feedback

[gkm]

• finalize LD,compact_unwind before relocating

[gkm]

• Folding adjacent CU entries requires a vector with monotonically increasing functionAddress, and to get that we must first apply std::sort().
• Abandon passing pageBreak 2nd compare arg via lambda-capture, because it is a fragile technique. It is only by an accident of the implementation that it works on std::lower_bound. It does not work for std::upper_bound, std::binary_search, or std::equal_range.

[gkm]

lld/MachO/Writer.cpp

413–414

I believe this latest rev works well and isn't so ugly. I retain the normal flow for gathering input sections and attaching them to MergedOutputSection for __LD, but I exclude it from outputSegments (without -r) so further downstream processing doesn't happen. I do insert __LD into nameToOutputSegment[] so that the synthetic UnwindInfoSection::finalize() can find it for processing. That seems minimally invasive and doesn't need a subclass.

All evidence I have seen shows that reloc types in __LD,__compact_unwind are always absolute and never PC-relative. The only output address that must be determined is lld's VMA. OutputSection::writeTo() accepts a pointer to a buffer, which is normally mapped to the linker's output file. However, when relocating __compact_unwind, the buffer is the internal std::vector<CompactUnwindEntry64>::data() rather than the output file.

[gkm]

• clean-up some ugly special cases by excluding __LD from outputSegments

[gkm]

• add UNWIND_INFO_COMMON_ENCODINGS_MAX
• revise, expand & prune comments
• improve variable names for CU entry folding

[int3]

lld/MachO/OutputSegment.cpp

73–74

Instead of filtering it out here, how about checking for __LD,__compact_unwind inside createOutputSections() while looping over mergedOutputSections, and then doing something like unwindInfoSection->setCompactUnwind(...)? Benefits: no need for the loop in UnwindInfoSection::isNeeded(), no need for getOutputSection, and no need to create an outputSegment to be discarded later.

That said, the current setup is definitely much cleaner than what we had before, and I'm happy to have this refinement in a follow-up diff

lld/MachO/UnwindInfo.cpp

202

s/adddress/addresses are/

289

nit: static_cast<size_t>

lld/MachO/UnwindInfo.h

15–18

nit: group includes with LLD headers first, then LLVM headers, then system headers

lld/MachO/Writer.cpp

425–426

how about using INT_MAX - 1 here instead, to cover the unlikely case where we have more than 100 sections? ld64 seems to do that

635

nit: Synthetic sections that only need to be used within Writer -- like SymtabSection -- can be a member of Writer instead of InStruct.

lld/test/MachO/compact-unwind.test

18

maybe change this seed to something that's not company-specific

lld/test/MachO/tools/validate-unwind-info.py

37

JFYI, the parens are unnecessary, but I'm fine if you prefer them

69

I don't suppose you meant to leave and False in?

[gkm]

lld/MachO/OutputSegment.cpp

73–74

No followup necessary. I did it all here.

[gkm]

• Final round of cleanups & review-feedback integration

[int3]

lld/MachO/OutputSegment.cpp

73

is this still necessary?

[gkm]

• Remove redundant change to lld/MachO/OutputSegment.cpp

[thakis]

lld/test/MachO/tools/generate-cfi-funcs.py

22

llvm still supports python2.7 for now.

[thakis]

lld/test/MachO/tools/generate-cfi-funcs.py

22

I went ahead and made the scripts 2.7-compatible in e22a4fd59de668af1cb943e23a6f4bfc93090e0f. Once we drop 2.7 support, it's hopefully easy to revert. Sorry for the trouble!

libunwind/include/mach-o/compact_unwind_encoding.h

struct unwind_info_compressed_second_level_page_header
     uint16_t    entryPageOffset;
     uint16_t    entryCount;
     uint16_t    encodingsPageOffset;
     uint16_t    encodingsCount;
     // 32-bit entry array
     // encodings array
 };
 
-#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(entry)            (entry & 0x00FFFFFF)
-#define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX(entry)        ((entry >> 24) & 0xFF)
-
+#define UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE 4096
+#define UNWIND_INFO_REGULAR_SECOND_LEVEL_ENTRIES_MAX                           \
+  ((UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE -                                       \
+    sizeof(unwind_info_regular_second_level_page_header)) /                    \
+   sizeof(unwind_info_regular_second_level_entry))
+#define UNWIND_INFO_COMPRESSED_SECOND_LEVEL_ENTRIES_MAX                        \
+  ((UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE -                                       \
+    sizeof(unwind_info_compressed_second_level_page_header)) /                 \
+   sizeof(uint32_t))
+
+#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS 24
+#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_MASK                          \
+  ((1 << UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS) - 1)
+
+#define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX_BITS                       \
+  (32 - UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS)
+#define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX_MASK                       \
+  ((1 << UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX_BITS) - 1)
+
+#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(entry)                        \
+  ((entry)&UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_MASK)
+#define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX(entry)                     \
+  (((entry) >> UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS) &                \
+   UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX_MASK)
 
+struct unwind_info_section_header_lsda_entry {
+  uint32_t functionOffset;
+  uint32_t lsdaOffset;
+};
 
 #endif
 

lld/MachO/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(MachOOptionsTableGen)
 
+include_directories(${LLVM_MAIN_SRC_DIR}/../libunwind/include)
+
 add_lld_library(lldMachO2
   Arch/X86_64.cpp
+  UnwindInfo.cpp
   Driver.cpp
   DriverUtils.cpp
   ExportTrie.cpp
   InputFiles.cpp
   InputSection.cpp
   MergedOutputSection.cpp
   ObjC.cpp
   OutputSection.cpp

lld/MachO/OutputSegment.h

 
 namespace segment_names {
 
 constexpr const char pageZero[] = "__PAGEZERO";
 constexpr const char text[] = "__TEXT";
 constexpr const char data[] = "__DATA";
 constexpr const char linkEdit[] = "__LINKEDIT";
 constexpr const char dataConst[] = "__DATA_CONST";
+constexpr const char ld[] = "__LD"; // really a non-output segment
 
 } // namespace segment_names
 
 class OutputSection;
 class InputSection;
 
 class OutputSegment {
 public:
   const OutputSection *firstSection() const { return sections.front(); }
   const OutputSection *lastSection() const { return sections.back(); }
 
   void addOutputSection(OutputSection *os);
   void sortOutputSections(
       llvm::function_ref<bool(OutputSection *, OutputSection *)> comparator) {
     llvm::stable_sort(sections, comparator);
   }
 
   const std::vector<OutputSection *> &getSections() const { return sections; }
+  const OutputSection *getSection(StringRef name) const;
+
   size_t numNonHiddenSections() const;
 
   uint64_t fileOff = 0;
   StringRef name;
   uint32_t maxProt = 0;
   uint32_t initProt = 0;
   uint8_t index;
 
 private:
   std::vector<OutputSection *> sections;
 };
 
 extern std::vector<OutputSegment *> outputSegments;
 
 OutputSegment *getOrCreateOutputSegment(StringRef name);
+const OutputSection *getOutputSection(StringRef segName, StringRef secName);
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/OutputSegment.cpp

size_t OutputSegment::numNonHiddenSections() const {
   return count;
 }
 
 void OutputSegment::addOutputSection(OutputSection *osec) {
   osec->parent = this;
   sections.push_back(osec);
 }
 
+const OutputSection *OutputSegment::getSection(StringRef name) const {
+  for (const OutputSection *osec : sections) {
+    if (name == osec->name)
+      return osec;
+  }
+  return nullptr;
+}
+
 static llvm::DenseMap<StringRef, OutputSegment *> nameToOutputSegment;
 std::vector<OutputSegment *> macho::outputSegments;
 
 OutputSegment *macho::getOrCreateOutputSegment(StringRef name) {
   OutputSegment *&segRef = nameToOutputSegment[name];
   if (segRef != nullptr)
     return segRef;
 
   segRef = make<OutputSegment>();
   segRef->name = name;
   segRef->maxProt = maxProt(name);
   segRef->initProt = initProt(name);
 
   outputSegments.push_back(segRef);
   return segRef;
 }
+
+const OutputSection *macho::getOutputSection(StringRef segName,
+                                             StringRef secName) {
+  OutputSegment *oseg = nameToOutputSegment.lookup(segName);
+  if (!oseg)
+    return nullptr;
+  return oseg->getSection(secName);
+}

lld/MachO/SyntheticSections.h

 #include "InputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "Target.h"
 
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Support/raw_ostream.h"
+#include <map>
 
 namespace lld {
 namespace macho {
 
 namespace section_names {
 
 constexpr const char pageZero[] = "__pagezero";
 constexpr const char header[] = "__mach_header";
 constexpr const char binding[] = "__binding";
 constexpr const char weakBinding[] = "__weak_binding";
 constexpr const char lazyBinding[] = "__lazy_binding";
 constexpr const char export_[] = "__export";
 constexpr const char symbolTable[] = "__symbol_table";
 constexpr const char stringTable[] = "__string_table";
 constexpr const char got[] = "__got";
 constexpr const char threadPtrs[] = "__thread_ptrs";
+constexpr const char unwindInfo[] = "__unwind_info";
+// these are not synthetic, but in service of synthetic __unwind_info
+constexpr const char compactUnwind[] = "__compact_unwind";
+constexpr const char ehFrame[] = "__eh_frame";
 
 } // namespace section_names
 
 class Defined;
 class DylibSymbol;
 class LoadCommand;
 
 class SyntheticSection : public OutputSection {
public:
   uint64_t getRawSize() const override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   StringTableSection &stringTableSection;
   std::vector<SymtabEntry> symbols;
 };
 
+class UnwindInfoSection;
+
 struct InStruct {
   MachHeaderSection *header = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;
   LazyPointerSection *lazyPointers = nullptr;
   StubsSection *stubs = nullptr;
   StubHelperSection *stubHelper = nullptr;
   ImageLoaderCacheSection *imageLoaderCache = nullptr;
+  UnwindInfoSection *unwindInfo = nullptr;
 };
 
 extern InStruct in;
 extern std::vector<SyntheticSection *> syntheticSections;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfo.h

+//===- UnwindInfo.h -------------------------------------------------------===//
+//
+// 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_UNWIND_INFO_H
+#define LLD_MACHO_UNWIND_INFO_H
+
+#include "MergedOutputSection.h"
+#include "SyntheticSections.h"
+#include <limits>
+#include <map>
+#include <vector>
+
+#include "mach-o/compact_unwind_encoding.h"
+
+// In 2020, we mostly care about 64-bit targets: x86_64 and arm64
+struct CompactUnwindEntry64 {
+  uint64_t functionAddress;
+  uint32_t functionLength;
+  uint32_t encoding;
+  uint64_t personality;
+  uint64_t lsda;
+};
+
+// FIXME(gkm): someday we might care about 32-bit targets: x86 & arm
+struct CompactUnwindEntry32 {
+  uint32_t functionAddress;
+  uint32_t functionLength;
+  uint32_t encoding;
+  uint32_t personality;
+  uint32_t lsda;
+};
+
+namespace lld {
+namespace macho {
+
+class UnwindInfoSection : public SyntheticSection {
+public:
+  UnwindInfoSection();
+  uint64_t getSize() const override;
+  bool isNeeded() const override;
+  void writeTo(uint8_t *buf) const override;
+
+private:
+  mutable std::map<uint32_t, size_t> commonEncodingIndexes;
+  mutable std::vector<std::pair<compact_unwind_encoding_t, size_t>>
+      commonEncodings;
+  mutable std::vector<uint32_t> personalities;
+  mutable std::vector<unwind_info_section_header_lsda_entry> lsdaEntries;
+  mutable std::vector<CompactUnwindEntry64> cuVector;
+  mutable std::vector<const CompactUnwindEntry64 *> cuPtrVector;
+  mutable std::vector<std::vector<const CompactUnwindEntry64 *>::const_iterator>
+      pageBounds;
+  mutable const MergedOutputSection *cuSection = nullptr;
+  mutable uint64_t level2PagesOffset = 0;
+  mutable uint64_t unwindInfoSize = std::numeric_limits<uint64_t>::max();
+  mutable bool hasCompactUnwindInputs = false;
+  mutable bool checkedCompactUnwindInputs = false;
+};
+
+} // namespace macho
+} // namespace lld
+
+#endif

lld/MachO/UnwindInfo.cpp

+//===- UnwindInfo.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 "UnwindInfo.h"
+#include "Config.h"
+#include "InputSection.h"
+#include "MergedOutputSection.h"
+#include "OutputSection.h"
+#include "OutputSegment.h"
+#include "Symbols.h"
+#include "SyntheticSections.h"
+#include "Target.h"
+
+#include "lld/Common/ErrorHandler.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/BinaryFormat/MachO.h"
+
+using namespace llvm;
+using namespace llvm::MachO;
+using namespace lld;
+using namespace lld::macho;
+
+// Compact Unwind format is a Mach-O evolution of DWARF Unwind that
+// optimizes space and exception-time lookup.  Most DWARF unwind
+// entries can be replaced with Compact Unwind entries, but the ones
+// that cannot are retained in DWARF form.
+//
+// This comment will address macro-level organization of the pre-link
+// and post-link compact unwind tables. For micro-level organization
+// pertaining to the bitfield layout of the 32-bit compact unwind
+// entries, see libunwind/include/mach-o/compact_unwind_encoding.h
+//
+// Important clarifying factoids:
+//
+// * __LD,__compact_unwind is the compact unwind format for compiler
+// output and linker input. It is never a final output.
+//
+// * __TEXT,__unwind_info is the compact unwind format for final
+// linker output. It is never an input.
+//
+// * __TEXT,__eh_frame is the DWARF format for both linker input and output.
+//
+// __TEXT,__unwind_info entries are divided into 4 KiB pages (2nd
+// level) by ascending address, and the pages are referenced by an
+// index (1st level) in the section header.
+//
+// TODO(gkm): ... continue block commment ...
+
+// TODO(gkm): prune __eh_frame entries superceded by __unwind_info
+// TODO(gkm): how do we align the 2nd-level pages?
+
+UnwindInfoSection::UnwindInfoSection()
+    : SyntheticSection(segment_names::text, section_names::unwindInfo) {}
+
+bool UnwindInfoSection::isNeeded() const {
+  if (checkedCompactUnwindInputs)
+    return hasCompactUnwindInputs;
+  for (InputSection *isec : inputSections) {
+    if (isec->segname == segment_names::ld &&
+        isec->name == section_names::compactUnwind)
+      hasCompactUnwindInputs = true;
+  }
+  checkedCompactUnwindInputs = true;
+  return hasCompactUnwindInputs;
+}
+
+// Scan the __LD,__compact_unwind entries and compute the space needs of
+// __TEXT,__unwind_info and __TEXT,__eh_frame
+
+uint64_t UnwindInfoSection::getSize() const {
+  if (unwindInfoSize != std::numeric_limits<uint64_t>::max())
+    return unwindInfoSize;
+  unwindInfoSize = 0;
+  cuSection = dyn_cast_or_null<MergedOutputSection>(
+      getOutputSection(segment_names::ld, section_names::compactUnwind));
+  if (cuSection == nullptr)
+    return unwindInfoSize;
+
+  // At this point, the address space for __TEXT,__text has been
+  // assigned, so we ought to be able to relocate the
+  // __LD,__compact_unwind entries into a temporary buffer.
+  // First, count the entries, and ensure there are no
+  // relocations against floating sections.
+  size_t cuCount = 0;
+  for (const InputSection *isec : cuSection->inputs) {
+    size_t size = isec->getSize();
+    assert(size % sizeof(CompactUnwindEntry64) == 0);
+    cuCount += (size / sizeof(CompactUnwindEntry64));
+    for (const Reloc &r : isec->relocs) {
+      if (const auto *targetIsec = r.target.dyn_cast<InputSection *>()) {
+        if (targetIsec->getVA() == 0) {
+          error(Twine("__compact_unwind relocation is unresolved against " +
+                      targetIsec->segname + "," + targetIsec->name));
+        }
+      } else {
+        error(Twine("__compact_unwind relocation is not section based: " +
+                    targetIsec->segname + "," + targetIsec->name));
+      }
+    }
+  }
+  // Relocate all __LD,__compact_unwind entries
+  cuVector.resize(cuCount);
+  cuSection->writeTo(reinterpret_cast<uint8_t *>(cuVector.data()));
+
+  // Fold adjacent entries with matching encoding+personality+lsda
+  // Retain the original cuVector
+  cuPtrVector.reserve(cuCount);
+  std::map<compact_unwind_encoding_t, size_t> encodingFrequencies;
+  for (size_t i = 0; i < cuCount;) {
+    const CompactUnwindEntry64 &prev = cuVector[i];
+    cuPtrVector.emplace_back(&prev);
+    encodingFrequencies[prev.encoding]++;
+    while (++i < cuCount && prev.encoding == cuVector[i].encoding &&
+           prev.personality == cuVector[i].personality &&
+           prev.lsda == cuVector[i].lsda) {
+      ;
+    }
+  }
+
+  // make a table of common encodings, and sort by descending frequency
+  for (const auto &frequency : encodingFrequencies) {
+    commonEncodings.emplace_back(frequency);
+  }
+  std::sort(commonEncodings.begin(), commonEncodings.end(),
+            [](const std::pair<compact_unwind_encoding_t, size_t> &a,
+               const std::pair<compact_unwind_encoding_t, size_t> &b) {
+              if (a.second == b.second)
+                // When freqnecies match, secondarily sort on encoding
+                // to maintain parity with validate-unwind-info.py
+                return a.first > b.first;
+              return a.second > b.second;
+            });
+
+  // create map from encoding to common-encoding-table index compact
+  // encoding entries use 7 bits to index the common-encoding table
+  if (commonEncodings.size() >= 128) {
+    error("TODO(gkm): handle common encodings table overflow");
+  }
+  size_t i = 0;
+  for (const auto &encoding : commonEncodings) {
+    commonEncodingIndexes[encoding.first] = i++;
+  }
+
+  // Split into pages, limited by capacity of a page and the 24-bit
+  // range of function offset
+  //
+  // Record the page splits as a vector of iterators on cuPtrVector
+  // such that succesive elements form a semi-open interval. E.g.,
+  // page X's bounds are thus: [ pageBounds[X] .. pageBounds[X+1] )
+  //
+  // Note that pageBouinds.size() is one greater than the number of
+  // pages, where pageBounds.cend() holds the sentinel cuPtrVector.cend()
+  pageBounds.push_back(cuPtrVector.cbegin());
+  // TODO(gkm): cut 1st page short to accommodate section headers
+  for (size_t i = 0;;) {
+    // Limit the search to entries that can fit witin a 4 KiB page.
+    std::vector<const CompactUnwindEntry64 *>::const_iterator it0 =
+        pageBounds[0] + i;
+    std::vector<const CompactUnwindEntry64 *>::const_iterator itN =
+        pageBounds[0] +
+        std::min(i + UNWIND_INFO_COMPRESSED_SECOND_LEVEL_ENTRIES_MAX,
+                 cuPtrVector.size());
+    // exclude entries with functionOffset that would overflow 24 bits
+    uint64_t functionAddressMax =
+        (*it0)->functionAddress + UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_MASK;
+    std::vector<const CompactUnwindEntry64 *>::const_iterator it =
+        std::lower_bound(it0, itN, nullptr,
+                         [functionAddressMax](const CompactUnwindEntry64 *a,
+                                              const CompactUnwindEntry64 *b) {
+                           return a->functionAddress < functionAddressMax;
+                         });
+    pageBounds.push_back(it);
+    if (it == cuPtrVector.cend())
+      break;
+    i = it - cuPtrVector.cbegin();
+  }
+
+  // compute size of __TEXT,__unwind_info section
+  level2PagesOffset =
+      sizeof(unwind_info_section_header) +
+      commonEncodings.size() * sizeof(uint32_t) +
+      personalities.size() * sizeof(uint32_t) +
+      pageBounds.size() * sizeof(unwind_info_section_header_index_entry) +
+      lsdaEntries.size() * sizeof(unwind_info_section_header_lsda_entry);
+  unwindInfoSize = level2PagesOffset +
+                   (pageBounds.size() - 1) *
+                       sizeof(unwind_info_compressed_second_level_page_header) +
+                   cuPtrVector.size() * sizeof(uint32_t);
+
+  return unwindInfoSize;
+}
+
+// All inputs are relocated and output adddress known, so write!
+
+void UnwindInfoSection::writeTo(uint8_t *buf) const {
+  // relocate __compact_unwind entries into cuBuf
+  if (getSize() == 0)
+    return;
+
+  // section header
+  auto *uip = reinterpret_cast<unwind_info_section_header *>(buf);
+  uip->version = 1;
+  uip->commonEncodingsArraySectionOffset = sizeof(unwind_info_section_header);
+  uip->commonEncodingsArrayCount = commonEncodings.size();
+  uip->personalityArraySectionOffset =
+      uip->commonEncodingsArraySectionOffset +
+      (uip->commonEncodingsArrayCount * sizeof(uint32_t));
+  uip->personalityArrayCount = personalities.size();
+  uip->indexSectionOffset = uip->personalityArraySectionOffset +
+                            (uip->personalityArrayCount * sizeof(uint32_t));
+  uip->indexCount = pageBounds.size();
+
+  // Common encodings
+  auto *i32p = reinterpret_cast<uint32_t *>(&uip[1]);
+  for (const auto &encoding : commonEncodings) {
+    *i32p++ = encoding.first;
+  }
+
+  // Personalities
+  for (const auto &personality : personalities) {
+    *i32p++ = personality;
+  }
+
+  // Level-1 index
+  uint32_t lsdaOffset =
+      uip->indexSectionOffset +
+      uip->indexCount * sizeof(unwind_info_section_header_index_entry);
+  auto *iep = reinterpret_cast<unwind_info_section_header_index_entry *>(i32p);
+  for (size_t i = 0; i < pageBounds.size() - 1; i++) {
+    iep->functionOffset = (*pageBounds[i])->functionAddress;
+    iep->secondLevelPagesSectionOffset = level2PagesOffset;
+    iep->lsdaIndexArraySectionOffset = lsdaOffset;
+    iep++;
+    size_t entryCount = pageBounds[i + 1] - pageBounds[i];
+    uint64_t pageSize = sizeof(unwind_info_section_header_index_entry) +
+                        entryCount * sizeof(uint32_t);
+    level2PagesOffset += pageSize;
+  }
+  // Level-1 sentinel
+  const CompactUnwindEntry64 &cuEnd = cuVector.back();
+  iep->functionOffset = cuEnd.functionAddress + cuEnd.functionLength;
+  iep->secondLevelPagesSectionOffset = 0;
+  iep->lsdaIndexArraySectionOffset = lsdaOffset;
+  iep++;
+
+  // LSDAs
+  auto *lep = reinterpret_cast<unwind_info_section_header_lsda_entry *>(iep);
+  for (const auto &lsda : lsdaEntries) {
+    lep->functionOffset = lsda.functionOffset;
+    lep->lsdaOffset = lsda.lsdaOffset;
+  }
+
+  // Level-2 pages
+  auto *p2p =
+      reinterpret_cast<unwind_info_compressed_second_level_page_header *>(lep);
+  for (size_t i = 0; i < pageBounds.size() - 1; i++) {
+    p2p->kind = 3;
+    p2p->entryPageOffset =
+        sizeof(unwind_info_compressed_second_level_page_header);
+    p2p->entryCount = pageBounds[i + 1] - pageBounds[i];
+    p2p->encodingsPageOffset =
+        p2p->entryPageOffset + p2p->entryCount * sizeof(uint32_t);
+    p2p->encodingsCount = 0;
+    auto *ep = reinterpret_cast<uint32_t *>(&p2p[1]);
+    std::vector<const CompactUnwindEntry64 *>::const_iterator it =
+        pageBounds[i];
+    uintptr_t functionAddressBase = (*it)->functionAddress;
+    while (it < pageBounds[i + 1]) {
+      const CompactUnwindEntry64 *cuep = *it++;
+      *ep++ = ((commonEncodingIndexes[cuep->encoding]
+                << UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS) |
+               (cuep->functionAddress - functionAddressBase));
+    }
+    p2p =
+        reinterpret_cast<unwind_info_compressed_second_level_page_header *>(ep);
+  }
+  auto *bufN = reinterpret_cast<uint8_t *>(p2p);
+  assert(getSize() == (size_t)(bufN - buf));
+}

lld/MachO/Writer.cpp

 #include "InputSection.h"
 #include "MergedOutputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "UnwindInfo.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Path.h"
void Writer::createLoadCommands() {
   default:
     llvm_unreachable("unhandled output file type");
   }
 
   in.header->addLoadCommand(make<LCBuildVersion>(config->platform));
 
   uint8_t segIndex = 0;
   for (OutputSegment *seg : outputSegments) {
+    if (seg->name == segment_names::ld)
+      break;
     in.header->addLoadCommand(make<LCSegment>(seg->name, seg));
     seg->index = segIndex++;
   }
 
   uint64_t dylibOrdinal = 1;
   for (InputFile *file : inputFiles) {
     if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
       in.header->addLoadCommand(

 }
 
 static int segmentOrder(OutputSegment *seg) {
   return StringSwitch<int>(seg->name)
       .Case(segment_names::pageZero, -2)
       .Case(segment_names::text, -1)
       // Make sure __LINKEDIT is the last segment (i.e. all its hidden
       // sections must be ordered after other sections).
-      .Case(segment_names::linkEdit, std::numeric_limits<int>::max())
+      .Case(segment_names::linkEdit, 100)
+      // FIXME(gkm): __LD,__compact_unwind is a normal I/O section with -r
+      // __LD,__compact_unwind isn't an output segment, so shove it past the end
+      .Case(segment_names::ld, 101)
       .Default(0);
 }
 
 static int sectionOrder(OutputSection *osec) {
   StringRef segname = osec->parent->name;
   // Sections are uniquely identified by their segment + section name.
   if (segname == segment_names::text) {
-    if (osec->name == section_names::header)
-      return -1;
+    return StringSwitch<int>(osec->name)
+        .Case(section_names::header, -1)
+        .Case(section_names::unwindInfo, 10)
+        .Case(section_names::ehFrame, 11)
+        .Default(0);
   } else if (segname == segment_names::linkEdit) {
     return StringSwitch<int>(osec->name)
         .Case(section_names::binding, -6)
         .Case(section_names::weakBinding, -5)
         .Case(section_names::lazyBinding, -4)
         .Case(section_names::export_, -3)
         .Case(section_names::symbolTable, -2)
         .Case(section_names::stringTable, -1)
         .Default(0);
   }
   // ZeroFill sections must always be the at the end of their segments,
   // otherwise subsequent sections may get overwritten with zeroes at runtime.
   if (isZeroFill(osec->flags))
-    return std::numeric_limits<int>::max();
+    return 100;
   return 0;
 }
 
 template <typename T, typename F>
 static std::function<bool(T, T)> compareByOrder(F ord) {
   return [=](T a, T b) { return ord(a) < ord(b); };
 }
 
if (!bufferOrErr)
     error("failed to open " + config->outputFile + ": " +
           llvm::toString(bufferOrErr.takeError()));
   else
     buffer = std::move(*bufferOrErr);
 }
 
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
-  for (OutputSegment *seg : outputSegments)
+  for (OutputSegment *seg : outputSegments) {
+    if (seg->name == segment_names::ld)
+      break;
     for (OutputSection *osec : seg->getSections())
       osec->writeTo(buf + osec->fileOff);
   }
+}
 
 void Writer::run() {
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   OutputSegment *linkEditSegment =
       getOrCreateOutputSegment(segment_names::linkEdit);
 
   scanRelocations();
   if (in.stubHelper->isNeeded())
void Writer::run() {
   createLoadCommands();
 
   // Ensure that segments (and the sections they contain) are allocated
   // addresses in ascending order, which dyld requires.
   //
   // Note that at this point, __LINKEDIT sections are empty, but we need to
   // determine addresses of other segments/sections before generating its
   // contents.
-  for (OutputSegment *seg : outputSegments)
-    if (seg != linkEditSegment)
-      assignAddresses(seg);
+  for (OutputSegment *seg : outputSegments) {
+    if (seg == linkEditSegment)
+      break;
+  }
 
   // Fill __LINKEDIT contents.
   in.binding->finalizeContents();
   in.weakBinding->finalizeContents();
   in.lazyBinding->finalizeContents();
   in.exports->finalizeContents();
   symtabSection->finalizeContents();
 
void macho::createSyntheticSections() {
   in.lazyBinding = make<LazyBindingSection>();
   in.exports = make<ExportSection>();
   in.got = make<GotSection>();
   in.tlvPointers = make<TlvPointerSection>();
   in.lazyPointers = make<LazyPointerSection>();
   in.stubs = make<StubsSection>();
   in.stubHelper = make<StubHelperSection>();
   in.imageLoaderCache = make<ImageLoaderCacheSection>();
+  in.unwindInfo = make<UnwindInfoSection>();
 }

lld/test/MachO/compact-unwind.test

+# REQUIRES: x86
+# FIXME(gkm): I want "requires python", but that disables the test
+# even on Linux, which definitely has Python. Why?!
+
+# FIXME(gkm): This test is fast on a Release tree, and slow (~10s) on
+# a Debug tree mostly because of llvm-mc. Is there a way to prefer the
+# fast installed llvm-mc rather than the slow one in our Debug tree?
+
+# If headers and offsets are proper, then ...
+#
+# 1) llvm-objdump will not crash, and exit with good status
+#
+# 2) Summary encodings from the input object will match
+#    those from the linked output
+#
+# 3) Encodings & symbols from the intput object will match
+#    those from the linked output
+
+# RUN: %S/tools/generate-cfi-funcs.py --seed=facebook >%t.s
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 -o %t.o %t.s
+# RUN: lld -flavor darwinnew -Z -L%S/Inputs/MacOSX.sdk/usr/lib -lSystem -o %t %t.o
+# RUN: llvm-objdump --unwind-info %t.o >%t.o.dump
+# RUN: llvm-objdump --unwind-info --syms %t >%t.dump
+# RUN: %S/tools/validate-unwind-info.py --object-dump=%t.o.dump --program-dump=%t.dump

lld/test/MachO/tools/generate-cfi-funcs.py

+#!/usr/bin/env python
+
+"""Generate skeletal functions with a variety .cfi_ directives.
+The purpose is to produce object-file test inputs to lld with a
+variety of compact unwind encodings.
+"""
+import random
+import argparse
+
+lsda_n = 0
+lsda_odds = 0.0
+func_size_low = 0x10
+func_size_high = 0x100
+
+def print_function(name: str):
+  global lsda_odds, func_size_low, func_size_high
+  print_lsda = (random.random() < lsda_odds)
+  ### FIXME(gkm): frame size should alter the compact encoding, but it does not
+  frame_size = random.randint(4, 64) * 16
+  reg_count = random.randint(0, 6)
+
+  # Function sizes begin small, then monotonically increase in size.
+  # The goal is to produce early pages that are full and later pages
+  # that are less than full, in order to test handling for both cases.
+  # Full pages contain the maximum of 1021 compact unwind entries for
+  # a total page size = 4 KiB.
+  func_size = random.randint(func_size_low, func_size_high) * 0x10
+  func_size_high += 1
+  if func_size_high % 0x10 == 0:
+    func_size_low += 1
+
+  print(f"""\
+### {name} regs={reg_count} frame={frame_size} lsda={1 if print_lsda else 0} size = {func_size}
+    .section __TEXT,__text,regular,pure_instructions
+    .p2align 4, 0x90
+    .globl {name}
+{name}:
+    .cfi_startproc""")
+  if print_lsda:
+    global lsda_n
+    lsda_n += 1
+    print(f"""\
+    .cfi_personality 155, ___gxx_personality_v0
+    .cfi_lsda 16, Lexception{lsda_n}""")
+  print(f"""\
+    pushq %rbp
+    .cfi_def_cfa_offset {frame_size}
+    .cfi_offset %rbp, -16
+    movq %rsp, %rbp
+    .cfi_def_cfa_register %rbp""")
+  if reg_count >= 5:
+    print(".cfi_offset %rbx, -56")
+  if reg_count >= 4:
+    print(".cfi_offset %r12, -48")
+  if reg_count >= 3:
+    print(".cfi_offset %r13, -40")
+  if reg_count >= 2:
+    print(".cfi_offset %r14, -32")
+  if reg_count >= 1:
+    print(".cfi_offset %r15, -24")
+  print(f"""\
+    .fill {func_size - 6}
+    popq %rbp
+    retq
+    .cfi_endproc
+""")
+
+  if print_lsda:
+    print(f"""\
+    .section __TEXT,__gcc_except_tab
+    .p2align 2
+Lexception{lsda_n}:
+    .space 0x10
+""")
+  return func_size
+
+def main():
+  parser = argparse.ArgumentParser(description=__doc__)
+  parser.add_argument('--seed',
+                      help='Seed the random number generator')
+  parser.add_argument('--pages', type=int, default=2,
+                      help='Number of compact-unwind pages')
+  parser.add_argument('--encodings', type=int, default=127,
+                      help='Maximum number of unique unwind encodings (default = 127)')
+  parser.add_argument('--lsda', type=int, default=0,
+                      help='Percentage of functions with personality & LSDA (default = 10')
+  args = parser.parse_args()
+  if (args.seed):
+    random.seed(args.seed)
+
+  lsda_odds = args.lsda / 100.0
+  size = 0
+  base = (1 << 12)
+  print(f"""
+    .section __TEXT,__text,regular,pure_instructions
+    .p2align 12, 0x90
+""")
+
+  while size < args.pages << 24:
+    func_size = print_function(f"x{size+base:08x}")
+    size += func_size
+
+  print(f"""\
+    .section __TEXT,__text,regular,pure_instructions
+    .globl _main
+    .p2align 4, 0x90
+_main:
+    retq
+
+    .p2align 4, 0x90
+___gxx_personality_v0:
+    retq
+""")
+
+
+if __name__ == '__main__':
+  main()

lld/test/MachO/tools/validate-unwind-info.py

+#!/usr/bin/env python
+
+"""Validate compact unwind info by cross checking the llvm-objdump
+reports of the input object file vs final linked output.
+"""
+import sys
+import argparse
+import re
+from pprint import pprint
+
+def main():
+  hex = "[a-f\d]"
+  hex8 = hex + "{8}"
+
+  parser = argparse.ArgumentParser(description=__doc__)
+  parser.add_argument('--object-dump', default=None,
+                      help='Object file')
+  parser.add_argument('--program-dump', default=None,
+                      help='Linked file')
+  parser.add_argument('--debug', action='store_true',
+                      help='Linked file')
+  args = parser.parse_args()
+
+  with open(args.object_dump, "r") as object_dump:
+    object_string = object_dump.read()
+  with open(args.program_dump, "r") as program_dump:
+    program_string = program_dump.read()
+
+  object_encodings_map = {
+    symbol:encoding for symbol, encoding in
+    re.findall(rf"start:\s+0x{hex}+\s+(\w+).+?encoding:\s+0x({hex}+)",
+               object_string, re.DOTALL)}
+
+  program_symbols_map = {
+    address:symbol for address, symbol in
+    re.findall(rf"^{hex8}({hex8}) g\s+F __TEXT,__text (\w+)$",
+               program_string, re.MULTILINE)}
+
+  program_common_encodings = (
+    re.findall(rf"^\s+encoding\[\d+\]: 0x({hex}+)$",
+               program_string, re.MULTILINE))
+
+  program_encodings_map = {
+    program_symbols_map[address]:encoding for address, encoding in
+    re.findall(rf"^\s+\[\d+\]: function offset=0x({hex}+)," +
+               rf" encoding\[\d+\]=0x({hex}+)$",
+               program_string, re.MULTILINE)}
+
+  if args.debug and False:
+    pprint(f"object encodings map:\n{object_encodings_map}")
+    pprint(f"program symbols map:\n{program_symbols_map}")
+    pprint(f"program encodings map:\n{program_encodings_map}")
+    pprint(f"program common encodings:\n{program_common_encodings}")
+
+  # Fold adjacent entries from the object file that have matching encodings
+  # TODO(gkm) add check for personality+lsda
+  encoding0 = 0
+  for symbol in sorted(object_encodings_map):
+    encoding = object_encodings_map[symbol]
+    fold = (encoding == encoding0)
+    if fold:
+      del object_encodings_map[symbol]
+    if args.debug and False:
+      print(f"{'delete' if fold else 'retain'} {symbol} with {encoding}")
+    encoding0 = encoding
+
+  if program_encodings_map != object_encodings_map:
+    if args.debug:
+      pprint(f"program encodings map:\n{program_encodings_map}")
+      pprint(f"object encodings map:\n{object_encodings_map}")
+    sys.exit("encoding maps differ")
+
+  # Count frequency of object-file folded encodings
+  # and compare with the program-file common encodings table
+  encoding_frequency_map = {}
+  for _, encoding in object_encodings_map.items():
+    encoding_frequency_map[encoding] = 1 + encoding_frequency_map.get(encoding, 0)
+  encoding_frequencies = [x for x in
+                          sorted(encoding_frequency_map,
+                                 key=lambda x: (encoding_frequency_map.get(x), x),
+                                 reverse=True)]
+
+  if program_common_encodings != encoding_frequencies:
+    if args.debug:
+      pprint(f"program common encodings:\n{program_common_encodings}")
+      pprint(f"object encoding frequencies:\n{encoding_frequencies}")
+    sys.exit("encoding frequencies differ")
+
+  return sys.exit()
+
+if __name__ == '__main__':
+  main()