[ELF] Read the call graph profile from object files.

[Bigcheese]

Summary

This uses the call graph profile embedded in the object files to construct the call graph.

This is read from a SHT_LLVM_CALL_GRAPH_PROFILE (0x6fff4c02) section as (uint32_t, uint32_t, uint64_t) tuples as (from symbol index, to symbol index, weight).

This depends on https://reviews.llvm.org/D44965 for llvm.

[• espindola]

ELF/InputFiles.cpp

222

Why do you need to store this in Config? The code that is walking CallGraphProfileSymbols could just as easily walk CGProfile, no?

[grimar]

This should be very useful. Needs rebasing though.

I think Rafael is right and eliminating Config->CallGraphProfileSymbols would be better.
You could create a helper function to call from Driver.cpp that would scan over
CGProfile and add graph edges probably.

[Bigcheese]

Address review comments.

[Bigcheese]

ping

[grimar]

ELF/Driver.cpp

676

Can you add a test to check this line?

685

CGProfile is used only once so I think you can just inline it:

for (const Elf_CGProfile_Impl<ELFT> &CGPE : Obj->CGProfile)

[Bigcheese]

• Added test for unorderable symbols from object files
• Removed unneeded temporary

[ruiu]

LGTM

ELF/Driver.cpp

698

I believe you can use {} instead of std::make_pair().

ELF/Driver.cpp

static void readCallGraph(MemoryBufferRef MB) {
 
   for (StringRef L : args::getLines(MB)) {
     SmallVector<StringRef, 3> Fields;
     L.split(Fields, ' ');
     uint64_t Count;
     if (Fields.size() != 3 || !to_integer(Fields[2], Count))
       fatal(MB.getBufferIdentifier() + ": parse error");
 
     if (const InputSectionBase *FromSB = FindSection(Fields[0]))
       if (const InputSectionBase *ToSB = FindSection(Fields[1]))
         Config->CallGraphProfile[std::make_pair(FromSB, ToSB)] += Count;
   }
 }
 
+template <class ELFT> static void readCallGraphsFromObjectFiles() {
+  auto FindSection = [&](const Symbol *Sym) -> const InputSectionBase * {
+    warnUnorderableSymbol(Sym);
+    if (const auto *SymD = dyn_cast<Defined>(Sym))
+      return dyn_cast_or_null<InputSectionBase>(SymD->Section);
+    return nullptr;
+  };
+
+  for (auto File : ObjectFiles) {
+    auto *Obj = cast<ObjFile<ELFT>>(File);
+    for (const Elf_CGProfile_Impl<ELFT> &CGPE : Obj->CGProfile) {
+      const InputSectionBase *FromSB =
+          FindSection(&Obj->getSymbol(CGPE.cgp_from));
+      const InputSectionBase *ToSB = FindSection(&Obj->getSymbol(CGPE.cgp_to));
+      if (!FromSB || !ToSB)
+        continue;
+      Config->CallGraphProfile[{FromSB, ToSB}] += CGPE.cgp_weight;
+    }
+  }
+}
+
 static bool getCompressDebugSections(opt::InputArgList &Args) {
   StringRef S = Args.getLastArgValue(OPT_compress_debug_sections, "none");
   if (S == "none")
     return false;
   if (S != "zlib")
     error("unknown --compress-debug-sections value: " + S);
   if (!zlib::isAvailable())
     error("--compress-debug-sections: zlib is not available");
if (Config->ICF != ICFLevel::None) {
     findKeepUniqueSections<ELFT>(Args);
     doIcf<ELFT>();
   }
 
   // Read the callgraph now that we know what was gced or icfed
   if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       readCallGraph(*Buffer);
+  readCallGraphsFromObjectFiles<ELFT>();
 
   // Write the result to the file.
   writeResult<ELFT>();
 }

ELF/InputFiles.h

 // .o file.
 template <class ELFT> class ObjFile : public ELFFileBase<ELFT> {
   typedef ELFFileBase<ELFT> Base;
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Word Elf_Word;
+  typedef typename ELFT::CGProfile Elf_CGProfile;
 
   StringRef getShtGroupSignature(ArrayRef<Elf_Shdr> Sections,
                                  const Elf_Shdr &Sec);
   ArrayRef<Elf_Word> getShtGroupEntries(const Elf_Shdr &Sec);
 
 public:
   static bool classof(const InputFile *F) { return F->kind() == Base::ObjKind; }
 
public:
 
   // True if the file defines functions compiled with -fsplit-stack,
   // but had one or more functions with the no_split_stack attribute.
   bool SomeNoSplitStack = false;
 
   // Pointer to this input file's .llvm_addrsig section, if it has one.
   const Elf_Shdr *AddrsigSec = nullptr;
 
+  // SHT_LLVM_CALL_GRAPH_PROFILE table
+  ArrayRef<Elf_CGProfile> CGProfile;
+
 private:
   void
   initializeSections(llvm::DenseSet<llvm::CachedHashStringRef> &ComdatGroups);
   void initializeSymbols();
   void initializeJustSymbols();
   void initializeDwarf();
   InputSectionBase *getRelocTarget(const Elf_Shdr &Sec);
   InputSectionBase *createInputSection(const Elf_Shdr &Sec);

ELF/InputFiles.cpp

if (LT->getFileLineInfoForAddress(
             S->getOffsetInFile() + Offset, nullptr,
             DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, Info))
       return Info;
   return None;
 }
 
 // Returns "<internal>", "foo.a(bar.o)" or "baz.o".
 std::string lld::toString(const InputFile *F) {
   if (!F)
     return "<internal>";
 
   if (F->ToStringCache.empty()) {
     if (F->ArchiveName.empty())
       F->ToStringCache = F->getName();
     else
       F->ToStringCache = (F->ArchiveName + "(" + F->getName() + ")").str();
   }
void ObjFile<ELFT>::initializeSections(
   this->SectionStringTable =
       CHECK(Obj.getSectionStringTable(ObjSections), this);
 
   for (size_t I = 0, E = ObjSections.size(); I < E; I++) {
     if (this->Sections[I] == &InputSection::Discarded)
       continue;
     const Elf_Shdr &Sec = ObjSections[I];
 
+    if (Sec.sh_type == ELF::SHT_LLVM_CALL_GRAPH_PROFILE)
+      CGProfile = check(
+          this->getObj().template getSectionContentsAsArray<Elf_CGProfile>(
+              &Sec));
+
     // SHF_EXCLUDE'ed sections are discarded by the linker. However,
     // if -r is given, we'll let the final link discard such sections.
     // This is compatible with GNU.
     if ((Sec.sh_flags & SHF_EXCLUDE) && !Config->Relocatable) {
       if (Sec.sh_type == SHT_LLVM_ADDRSIG) {
         // We ignore the address-significance table if we know that the object
         // file was created by objcopy or ld -r. This is because these tools
         // will reorder the symbols in the symbol table, invalidating the data

test/ELF/cgprofile-obj-warn.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: ld.lld -e A %t -o /dev/null \
+# RUN:   -noinhibit-exec -icf=all 2>&1 | FileCheck %s
+
+    .section    .text.C,"ax",@progbits
+    .globl  C
+C:
+    mov poppy, %rax
+    retq
+
+B = 0x1234
+
+    .section    .text.A,"ax",@progbits
+    .globl  A
+A:
+    mov poppy, %rax
+    retq
+
+    .cg_profile A, B, 100
+    .cg_profile A, C, 40
+    .cg_profile B, C, 30
+    .cg_profile adena1, A, 30
+    .cg_profile A, adena2, 30
+    .cg_profile poppy, A, 30
+
+# CHECK: unable to order absolute symbol: B
+# CHECK: unable to order undefined symbol: adena1
+# CHECK: unable to order undefined symbol: adena2
+# CHECK: unable to order undefined symbol: poppy
+
+# RUN: ld.lld %t -o /dev/null \
+# RUN:   -noinhibit-exec -icf=all --no-warn-symbol-ordering 2>&1 \
+# RUN:   | FileCheck %s --check-prefix=NOWARN
+# NOWARN-NOT: unable to order

test/ELF/cgprofile-obj.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld -e A %t -o %t2
+# RUN: llvm-readobj -symbols %t2 | FileCheck %s
+
+    .section    .text.D,"ax",@progbits
+D:
+    retq
+
+    .section    .text.C,"ax",@progbits
+    .globl  C
+C:
+    retq
+
+    .section    .text.B,"ax",@progbits
+    .globl  B
+B:
+    retq
+
+    .section    .text.A,"ax",@progbits
+    .globl  A
+A:
+Aa:
+    retq
+
+    .cg_profile A, B, 10
+    .cg_profile A, B, 10
+    .cg_profile Aa, B, 80
+    .cg_profile A, C, 40
+    .cg_profile B, C, 30
+    .cg_profile C, D, 90
+
+# CHECK:          Name: D
+# CHECK-NEXT:     Value: 0x201003
+# CHECK:          Name: A
+# CHECK-NEXT:     Value: 0x201000
+# CHECK:          Name: B
+# CHECK-NEXT:     Value: 0x201001
+# CHECK:          Name: C
+# CHECK-NEXT:     Value: 0x201002