[lld-macho] Port CallGraphSort from COFF/ELF

[lgrey]

Summary

Depends on D112160

This adds the new options --call-graph-profile-sort (default), --no-call-graph-profile-sort and --print-symbol-order=. If call graph profile sorting is enabled, reads __LLVM,__cg_profile sections from object files and uses the resulting graph to put callees and callers close to each other in the final binary via the C3 clustering heuristic.

[lgrey]

lld/MachO/CallGraphSort.cpp

152 ↗

(On Diff #381029)

ELF/COFF use a larger constant but the original paper says page size and I couldn't find anything in history/reviews that motivates the larger number.

lld/MachO/InputFiles.cpp

308 ↗

(On Diff #381029)

I couldn't find prior art on finding endianness, though there's code elsewhere that assumes little. Is there a better way to do this?

[lgrey]

Removed strays from test

[tschuett]

There are some effects when 4k pages are backed by contiguous physical memory, but that probably needs a custom loader:
https://docs.mellanox.com/display/rdmacore50/Contiguous+Pages

[lgrey]

Format

[oontvoo]

lld/MachO/CallGraphSort.cpp

251 ↗

(On Diff #381035)

TimeTraceScope here? (as it'd be doing non-negligible amount of work)

lld/MachO/CallGraphSort.h

16 ↗

(On Diff #381035)

why not #include the header instead?
(you'll need it in the .cpp anyway)

lld/MachO/Driver.cpp

1035 ↗

(On Diff #381035)

[optional] perhaps add a TimeTraceScope here?

1442 ↗

(On Diff #381035)

only if callGraphProfileSort==true ?

lld/MachO/InputFiles.cpp

308 ↗

(On Diff #381029)

I think the unwritten assumption here is that macho is all little-endian now.

lld/MachO/InputFiles.h

61 ↗

(On Diff #381074)

would be helpful to have some comment clarifying on "Index" into what.

[lgrey]

Address comments: document CallGraphEntry struct, add time traces, only extract data if --call-graph-profile-sort, shuffle includes

[lgrey]

Format

[MaskRay]

Any performance number? This is a very minor optimization and probably rarely doesn't really benefit mobile/desktop applications.

[lgrey]

Windows Chrome got 3% on Speedometer from adding this. Locally on Chromium Mac, I'm seeing about the same thing (3.3% if I'm measuring correctly: means of 151 vs 156 with similar confidence intervals).

[MaskRay]

In D112164#3094587, @lgrey wrote:

Windows Chrome got 3% on Speedometer from adding this. Locally on Chromium Mac, I'm seeing about the same thing (3.3% if I'm measuring correctly: means of 151 vs 156 with similar confidence intervals).

Ah, nice. Thanks for the number.

lld/MachO/CallGraphSort.cpp

232 ↗

(On Diff #381302)

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

[lgrey]

Remove braces around single-line if

[thakis]

Cool.

lld/MachO/Driver.cpp

1401 ↗

(On Diff #383160)

should we warn if there's both an explicit --call-graph-profile-sort flag and an -order_file flag? Or maybe later when we know that there's call graph info in the .o file but also an order file?

(…or are you planning on adding support for both flags at the same time in a follow-up?)

lld/MachO/InputFiles.cpp

307 ↗

(On Diff #383160)

Should this have a TimeTrace too?

lld/MachO/Options.td

77 ↗

(On Diff #383160)

nit: Put just (default) here, and omit it from the line below. That's consistent with the rest of the help texts.

[lgrey]

Var renames, missing newline

[lgrey]

Restore accidentally stomped diff

[lgrey]

Add time trace for parsing section, options edit

lld/MachO/Driver.cpp

1401 ↗

(On Diff #383160)

Yes, planning to add support to both as a follow-up

llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp

if (auto *LinkerOptions = M.getNamedMetadata("llvm.linker.options")) {
     }
   }
 
   unsigned VersionVal = 0;
   unsigned ImageInfoFlags = 0;
   StringRef SectionVal;
 
   GetObjCImageInfo(M, VersionVal, ImageInfoFlags, SectionVal);
+  emitCGProfileMetadata(Streamer, M);
 
   // The section is mandatory. If we don't have it, then we don't have GC info.
   if (SectionVal.empty())
     return;
 
   StringRef Segment, Section;
   unsigned TAA = 0, StubSize = 0;
   bool TAAParsed;

llvm/lib/MC/MCMachOStreamer.cpp

public:
 
   void emitIdent(StringRef IdentString) override {
     llvm_unreachable("macho doesn't support this directive");
   }
 
   void emitLOHDirective(MCLOHType Kind, const MCLOHArgs &Args) override {
     getAssembler().getLOHContainer().addDirective(Kind, Args);
   }
+  void emitCGProfileEntry(const MCSymbolRefExpr *From,
+                          const MCSymbolRefExpr *To, uint64_t Count) override {
+    if (!From->getSymbol().isTemporary() && !To->getSymbol().isTemporary())
+      getAssembler().CGProfile.push_back({From, To, Count});
+  }
 
   void finishImpl() override;
+
+  void finalizeCGProfileEntry(const MCSymbolRefExpr *&SRE);
+  void finalizeCGProfile();
 };
 
 } // end anonymous namespace.
 
 static bool canGoAfterDWARF(const MCSectionMachO &MSec) {
   // These sections are created by the assembler itself after the end of
   // the .s file.
   StringRef SegName = MSec.getSegmentName();
static bool canGoAfterDWARF(const MCSectionMachO &MSec) {
   }
 
   if (SegName == "__TEXT" && SecName == "__eh_frame")
     return true;
 
   if (SegName == "__DATA" && (SecName == "__nl_symbol_ptr" ||
                               SecName == "__thread_ptr"))
     return true;
-
+  if (SegName == "__LLVM" && SecName == "__cg_profile")
+    return true;
   return false;
 }
 
 void MCMachOStreamer::changeSection(MCSection *Section,
                                     const MCExpr *Subsection) {
   // Change the section normally.
   bool Created = changeSectionImpl(Section, Subsection);
   const MCSectionMachO &MSec = *cast<MCSectionMachO>(Section);
for (MCSection &Sec : getAssembler()) {
     const MCSymbol *CurrentAtom = nullptr;
     for (MCFragment &Frag : Sec) {
       if (const MCSymbol *Symbol = DefiningSymbolMap.lookup(&Frag))
         CurrentAtom = Symbol;
       Frag.setAtom(CurrentAtom);
     }
   }
 
+  finalizeCGProfile();
+
   this->MCObjectStreamer::finishImpl();
 }
 
+void MCMachOStreamer::finalizeCGProfileEntry(const MCSymbolRefExpr *&SRE) {
+  const MCSymbol *S = &SRE->getSymbol();
+  bool Created;
+  getAssembler().registerSymbol(*S, &Created);
+  if (Created)
+    S->setExternal(true);
+}
+
+void MCMachOStreamer::finalizeCGProfile() {
+  MCAssembler &Asm = getAssembler();
+  if (Asm.CGProfile.empty())
+    return;
+  for (MCAssembler::CGProfileEntry &E : Asm.CGProfile) {
+    finalizeCGProfileEntry(E.From);
+    finalizeCGProfileEntry(E.To);
+  }
+  // We can't write the section out until symbol indices are finalized which
+  // doesn't happen until after section layout. We need to create the section
+  // and set its size now so that it's accounted for in layout.
+  MCSection *CGProfileSection = Asm.getContext().getMachOSection(
+      "__LLVM", "__cg_profile", 0, SectionKind::getMetadata());
+  Asm.registerSection(*CGProfileSection);
+  auto *Frag = new MCDataFragment(CGProfileSection);
+  // For each entry, reserve space for 2 32-bit indices and a 64-bit count.
+  size_t SectionBytes =
+      Asm.CGProfile.size() * (2 * sizeof(uint32_t) + sizeof(uint64_t));
+  Frag->getContents().resize(SectionBytes);
+}
+
 MCStreamer *llvm::createMachOStreamer(MCContext &Context,
                                       std::unique_ptr<MCAsmBackend> &&MAB,
                                       std::unique_ptr<MCObjectWriter> &&OW,
                                       std::unique_ptr<MCCodeEmitter> &&CE,
                                       bool RelaxAll, bool DWARFMustBeAtTheEnd,
                                       bool LabelSections) {
   MCMachOStreamer *S =
       new MCMachOStreamer(Context, std::move(MAB), std::move(OW), std::move(CE),

llvm/lib/MC/MCParser/DarwinAsmParser.cpp

addDirectiveHandler<&DarwinAsmParser::parseWatchOSVersionMin>(
       ".watchos_version_min");
     addDirectiveHandler<&DarwinAsmParser::parseTvOSVersionMin>(
       ".tvos_version_min");
     addDirectiveHandler<&DarwinAsmParser::parseIOSVersionMin>(
       ".ios_version_min");
     addDirectiveHandler<&DarwinAsmParser::parseMacOSXVersionMin>(
       ".macosx_version_min");
     addDirectiveHandler<&DarwinAsmParser::parseBuildVersion>(".build_version");
+    addDirectiveHandler<&DarwinAsmParser::parseDirectiveCGProfile>(
+        ".cg_profile");
 
     LastVersionDirective = SMLoc();
   }
 
   bool parseDirectiveAltEntry(StringRef, SMLoc);
   bool parseDirectiveDesc(StringRef, SMLoc);
   bool parseDirectiveIndirectSymbol(StringRef, SMLoc);
   bool parseDirectiveDumpOrLoad(StringRef, SMLoc);
public:
   bool parseMajorMinorVersionComponent(unsigned *Major, unsigned *Minor,
                                        const char *VersionName);
   bool parseOptionalTrailingVersionComponent(unsigned *Component,
                                              const char *ComponentName);
   bool parseVersion(unsigned *Major, unsigned *Minor, unsigned *Update);
   bool parseSDKVersion(VersionTuple &SDKVersion);
   void checkVersion(StringRef Directive, StringRef Arg, SMLoc Loc,
                     Triple::OSType ExpectedOS);
+  bool parseDirectiveCGProfile(StringRef Directive, SMLoc Loc);
 };
 
 } // end anonymous namespace
 
 bool DarwinAsmParser::parseSectionSwitch(StringRef Segment, StringRef Section,
                                          unsigned TAA, unsigned Align,
                                          unsigned StubSize) {
   if (getLexer().isNot(AsmToken::EndOfStatement))
bool DarwinAsmParser::parseBuildVersion(StringRef Directive, SMLoc Loc) {
 
   Triple::OSType ExpectedOS
     = getOSTypeFromPlatform((MachO::PlatformType)Platform);
   checkVersion(Directive, PlatformName, Loc, ExpectedOS);
   getStreamer().emitBuildVersion(Platform, Major, Minor, Update, SDKVersion);
   return false;
 }
 
+/// parseDirectiveCGProfile
+///   ::= .cg_profile from, to, count
+bool DarwinAsmParser::parseDirectiveCGProfile(StringRef S, SMLoc Loc) {
+  return MCAsmParserExtension::ParseDirectiveCGProfile(S, Loc);
+}
 
 namespace llvm {
 
 MCAsmParserExtension *createDarwinAsmParser() {
   return new DarwinAsmParser;
 }
 
 } // end llvm namespace

llvm/lib/MC/MachObjectWriter.cpp

 uint64_t MachObjectWriter::writeObject(MCAssembler &Asm,
                                        const MCAsmLayout &Layout) {
   uint64_t StartOffset = W.OS.tell();
 
   // Compute symbol table information and bind symbol indices.
   computeSymbolTable(Asm, LocalSymbolData, ExternalSymbolData,
                      UndefinedSymbolData);
 
+  if (!Asm.CGProfile.empty()) {
+    MCSection *CGProfileSection = Asm.getContext().getMachOSection(
+        "__LLVM", "__cg_profile", 0, SectionKind::getMetadata());
+    MCDataFragment *Frag = dyn_cast_or_null<MCDataFragment>(
+        &*CGProfileSection->getFragmentList().begin());
+    assert(Frag && "call graph profile section not reserved");
+    Frag->getContents().set_size(0);
+    raw_svector_ostream OS(Frag->getContents());
+    for (const MCAssembler::CGProfileEntry &CGPE : Asm.CGProfile) {
+      uint32_t FromIndex = CGPE.From->getSymbol().getIndex();
+      uint32_t ToIndex = CGPE.To->getSymbol().getIndex();
+      support::endian::write(OS, FromIndex, W.Endian);
+      support::endian::write(OS, ToIndex, W.Endian);
+      support::endian::write(OS, CGPE.Count, W.Endian);
+    }
+  }
+
   unsigned NumSections = Asm.size();
   const MCAssembler::VersionInfoType &VersionInfo =
     Layout.getAssembler().getVersionInfo();
 
   // The section data starts after the header, the segment load command (and
   // section headers) and the symbol table.
   unsigned NumLoadCommands = 1;
   uint64_t LoadCommandsSize = is64Bit() ?

llvm/test/MC/MachO/cgprofile.ll

+; RUN: llc -filetype=asm %s -o - -mtriple x86_64-apple-darwin | FileCheck %s
+; RUN: llc -filetype=obj %s -o %t -mtriple x86_64-apple-darwin
+; RUN: llvm-readobj --cg-profile %t | FileCheck %s --check-prefix=OBJ
+
+declare void @b()
+
+define void @a() {
+  call void @b()
+  ret void
+}
+
+define void @freq(i1 %cond) {
+  br i1 %cond, label %A, label %B
+A:
+  call void @a();
+  ret void
+B:
+  call void @b();
+  ret void
+}
+
+!llvm.module.flags = !{!0}
+
+!0 = !{i32 5, !"CG Profile", !1}
+!1 = !{!2, !3, !4, !5}
+!2 = !{void ()* @a, void ()* @b, i64 32}
+!3 = !{void (i1)* @freq, void ()* @a, i64 11}
+!4 = !{void (i1)* @freq, void ()* @b, i64 20}
+!5 = !{void (i1)* @freq, null, i64 20}
+
+; CHECK: .cg_profile _a, _b, 32
+; CHECK: .cg_profile _freq, _a, 11
+; CHECK: .cg_profile _freq, _b, 20
+
+; OBJ: CGProfile [
+; OBJ:  CGProfileEntry {
+; OBJ:    From: _a
+; OBJ:    To: _b
+; OBJ:    Weight: 32
+; OBJ:  }
+; OBJ:  CGProfileEntry {
+; OBJ:    From: _freq
+; OBJ:    To: _a
+; OBJ:    Weight: 11
+; OBJ:  }
+; OBJ:  CGProfileEntry {
+; OBJ:    From: _freq
+; OBJ:    To: _b
+; OBJ:    Weight: 20
+; OBJ:  }
+; OBJ:]

llvm/test/MC/MachO/cgprofile.s

+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t
+# RUN: llvm-readobj -S --symbols --sd --cg-profile %t | FileCheck %s
+
+  .section __TEXT,__text
+a:
+
+  .cg_profile a, b, 32
+  .cg_profile freq, a, 11
+  .cg_profile late, late2, 20
+  .cg_profile L.local, b, 42
+
+  .globl late
+late:
+late2: .word 0
+late3:
+L.local:
+
+
+# CHECK:      Name: __cg_profile
+# CHECK-NEXT: Segment: __LLVM
+# CHECK-NEXT: Address:
+# CHECK-NEXT: Size: 0x30
+# CHECK:      SectionData (
+# CHECK-NEXT:   0000: 00000000 04000000 20000000 00000000
+# CHECK-NEXT:   0010: 05000000 00000000 0B000000 00000000
+# CHECK-NEXT:   0020: 03000000 01000000 14000000 00000000
+# CHECK-NEXT: )
+
+# CHECK:        CGProfile [
+# CHECK-NEXT:   CGProfileEntry {
+# CHECK-NEXT:     From: a (0)
+# CHECK-NEXT:     To: b (4)
+# CHECK-NEXT:     Weight: 32
+# CHECK-NEXT:   }
+# CHECK-NEXT:   CGProfileEntry {
+# CHECK-NEXT:     From: freq (5)
+# CHECK-NEXT:     To: a (0)
+# CHECK-NEXT:     Weight: 11
+# CHECK-NEXT:   }
+# CHECK-NEXT:   CGProfileEntry {
+# CHECK-NEXT:     From: late (3)
+# CHECK-NEXT:     To: late2 (1)
+# CHECK-NEXT:     Weight: 20
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]

llvm/tools/llvm-readobj/MachODumper.cpp

 //===----------------------------------------------------------------------===//
 
 #include "ObjDumper.h"
 #include "StackMapPrinter.h"
 #include "llvm-readobj.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Object/MachO.h"
+#include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 using namespace llvm;
 using namespace object;
 
 namespace {
 
 class MachODumper : public ObjDumper {
 public:
   MachODumper(const MachOObjectFile *Obj, ScopedPrinter &Writer)
       : ObjDumper(Writer, Obj->getFileName()), Obj(Obj) {}
 
   void printFileHeaders() override;
   void printSectionHeaders() override;
   void printRelocations() override;
   void printUnwindInfo() override;
   void printStackMap() const override;
+  void printCGProfile() override;
 
   void printNeededLibraries() override;
 
   // MachO-specific.
   void printMachODataInCode() override;
   void printMachOVersionMin() override;
   void printMachODysymtab() override;
   void printMachOSegment() override;
   void printMachOIndirectSymbols() override;
   void printMachOLinkerOptions () override;
 
 private:
   template<class MachHeader>
   void printFileHeaders(const MachHeader &Header);
 
+  StringRef getSymbolName(const SymbolRef &Symbol);
+
   void printSymbols() override;
   void printDynamicSymbols() override;
   void printSymbol(const SymbolRef &Symbol);
 
   void printRelocation(const RelocationRef &Reloc);
 
   void printRelocation(const MachOObjectFile *Obj, const RelocationRef &Reloc);
 
void MachODumper::printRelocation(const MachOObjectFile *Obj,
   MachO::any_relocation_info RE = Obj->getRelocation(DR);
   bool IsScattered = Obj->isRelocationScattered(RE);
   bool IsExtern = !IsScattered && Obj->getPlainRelocationExternal(RE);
 
   StringRef TargetName;
   if (IsExtern) {
     symbol_iterator Symbol = Reloc.getSymbol();
     if (Symbol != Obj->symbol_end()) {
-      Expected<StringRef> TargetNameOrErr = Symbol->getName();
-      if (!TargetNameOrErr)
-        reportError(TargetNameOrErr.takeError(), Obj->getFileName());
-      TargetName = *TargetNameOrErr;
+      TargetName = getSymbolName(*Symbol);
     }
   } else if (!IsScattered) {
     section_iterator SecI = Obj->getRelocationSection(DR);
     if (SecI != Obj->section_end())
       TargetName = unwrapOrError(Obj->getFileName(), SecI->getName());
   }
   if (TargetName.empty())
     TargetName = "-";
else
       OS << " " << Obj->getPlainRelocationExternal(RE);
     OS << " " << RelocName
        << " " << IsScattered
        << " " << SymbolNameOrOffset
        << "\n";
   }
 }
 
+StringRef MachODumper::getSymbolName(const SymbolRef &Symbol) {
+  Expected<StringRef> SymbolNameOrErr = Symbol.getName();
+  if (!SymbolNameOrErr) {
+    reportError(SymbolNameOrErr.takeError(), Obj->getFileName());
+  }
+  return *SymbolNameOrErr;
+}
+
 void MachODumper::printSymbols() {
   ListScope Group(W, "Symbols");
 
   for (const SymbolRef &Symbol : Obj->symbols()) {
     printSymbol(Symbol);
   }
 }
 
 void MachODumper::printDynamicSymbols() {
   ListScope Group(W, "DynamicSymbols");
 }
 
 void MachODumper::printSymbol(const SymbolRef &Symbol) {
-  StringRef SymbolName;
-  Expected<StringRef> SymbolNameOrErr = Symbol.getName();
-  if (!SymbolNameOrErr) {
-    // TODO: Actually report errors helpfully.
-    consumeError(SymbolNameOrErr.takeError());
-  } else
-    SymbolName = *SymbolNameOrErr;
+  StringRef SymbolName = getSymbolName(Symbol);
 
   MachOSymbol MOSymbol;
   getSymbol(Obj, Symbol.getRawDataRefImpl(), MOSymbol);
 
   StringRef SectionName = "";
   // Don't ask a Mach-O STABS symbol for its section unless we know that
   // STAB symbol's section field refers to a valid section index. Otherwise
   // the symbol may error trying to load a section that does not exist.
void MachODumper::printStackMap() const {
   if (Obj->isLittleEndian())
     prettyPrintStackMap(
         W, StackMapParser<support::little>(StackMapContentsArray));
   else
     prettyPrintStackMap(
         W, StackMapParser<support::big>(StackMapContentsArray));
 }
 
+void MachODumper::printCGProfile() {
+  object::SectionRef CGProfileSection;
+  for (auto Sec : Obj->sections()) {
+    StringRef Name;
+    if (Expected<StringRef> NameOrErr = Sec.getName())
+      Name = *NameOrErr;
+    else
+      consumeError(NameOrErr.takeError());
+
+    if (Name == "__cg_profile") {
+      CGProfileSection = Sec;
+      break;
+    }
+  }
+  if (CGProfileSection == object::SectionRef())
+    return;
+
+  StringRef CGProfileContents =
+      unwrapOrError(Obj->getFileName(), CGProfileSection.getContents());
+  BinaryStreamReader Reader(CGProfileContents, Obj->isLittleEndian()
+                                                   ? llvm::support::little
+                                                   : llvm::support::big);
+
+  ListScope L(W, "CGProfile");
+  while (!Reader.empty()) {
+    uint32_t FromIndex, ToIndex;
+    uint64_t Count;
+    if (Error Err = Reader.readInteger(FromIndex))
+      reportError(std::move(Err), Obj->getFileName());
+    if (Error Err = Reader.readInteger(ToIndex))
+      reportError(std::move(Err), Obj->getFileName());
+    if (Error Err = Reader.readInteger(Count))
+      reportError(std::move(Err), Obj->getFileName());
+    DictScope D(W, "CGProfileEntry");
+    W.printNumber("From", getSymbolName(*Obj->getSymbolByIndex(FromIndex)),
+                  FromIndex);
+    W.printNumber("To", getSymbolName(*Obj->getSymbolByIndex(ToIndex)),
+                  ToIndex);
+    W.printNumber("Weight", Count);
+  }
+}
+
 void MachODumper::printNeededLibraries() {
   ListScope D(W, "NeededLibraries");
 
   using LibsTy = std::vector<StringRef>;
   LibsTy Libs;
 
   for (const auto &Command : Obj->load_commands()) {
     if (Command.C.cmd == MachO::LC_LOAD_DYLIB ||

llvm/tools/llvm-readobj/llvm-readobj.cpp

if (Obj.isMachO()) {
     if (opts::MachOLinkerOptions)
       Dumper->printMachOLinkerOptions();
     if (opts::MachOSegment)
       Dumper->printMachOSegment();
     if (opts::MachOVersionMin)
       Dumper->printMachOVersionMin();
     if (opts::MachODysymtab)
       Dumper->printMachODysymtab();
+    if (opts::CGProfile)
+      Dumper->printCGProfile();
   }
   if (opts::PrintStackMap)
     Dumper->printStackMap();
   if (opts::PrintStackSizes)
     Dumper->printStackSizes();
 }
 
 /// Dumps each object file in \a Arc;