[llvm][Instrumentation/MC] Add Call Graph Profile pass and object file emission.

[Bigcheese]

Summary

This patch adds support for generating a call graph profile from Branch Frequency Info and embedding that profile into an object file to pass to the linker. Linker support for this feature (without reading from the object file) is being reviewed at https://reviews.llvm.org/D36351 and appears to be nearing completion.

Generating the CG Profile

The CGProfile module pass simply gets the block profile count for each BB and scans for call instructions. For each call instruction it adds an edge from the current function to the called function with the current BB block profile count as the weight.

After scanning all the functions, it generates an appending module flag containing the data. The format looks like:

!llvm.module.flags = !{!0} 
 
!0 = !{i32 5, !"CG Profile", !1} 
!1 = !{!2, !3, !4} ; List of edges
!2 = !{!"a", !"b", i64 32} ; Edge from a to b with a weight of 32
!3 = !{!"freq", !"a", i64 11} 
!4 = !{!"freq", !"b", i64 20}

Object FIle Representation

At codegen time this is emitted into the ELF file a pair of symbol indices and a weight. In assembly it looks like:

.cg_profile a, b, 32 
.cg_profile freq, a, 11 
.cg_profile freq, b, 20

When writing an ELF file these are put into a SHT_LLVM_CALL_GRAPH_PROFILE (0x6fff4c02) section as (uint32_t, uint32_t, uint64_t) tuples as (from symbol index, to symbol index, weight).

[• espindola]

I am not sure what the semantics of a "parent" revision are.

The intention is that we should first finish the lld patch that reads the callgraph from a text file before we look at the llvm changes.

[Bigcheese]

Rebase.

I'm also updating the lld patch that reads this, will have that up shortly.

[Bigcheese]

Previous update was missing tests. Fixed.

[• espindola]

The part MC and Object part of this patch LGTM.

The IR level probably needs someone more familiar with metadata as a reviewer.

If you commit the MC and Object parts this should be sufficient to unblock the lld part, right?

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

133

use an explicit type

144–155

Explicit type

147

Should the metadata be referring to symbols by name?

tools/llvm-readobj/ELFDumper.cpp

751

We should probably have these values cached in the dumper. It is OK for that to be a followup.

[Bigcheese]

The MC and Object parts are enough for lld, yes.

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

147

Hmm, it may make more sense to refer to the symbols by GlobalValue instead, but that just delays the conversion to string.

[• espindola]

In D44965#1080257, @Bigcheese wrote:

The MC and Object parts are enough for lld, yes.

OK. Please commit the MC and Object parts first. We can get the metadata bits reviewed afterwards.

[evgeny777]

This and D45850 made 2 - 2.5% performance improvement to a large real world application already built with PGO + full LTO. Any chance to push this anytime soon?

[pcc]

Can you document the assembly and object file extensions in docs/Extensions.rst?

Do we need to do anything about the fact that the new section contains symbol table indexes (see the discussion on the proposed SHT_LLVM_ADDRSIG section)? I don't think so since an incorrect index will not result in a miscompile but rather a suboptimality.

With that the MC/Object part LGTM to me as well, but it will probably require a rebase at this point. The IR part also looks good but I'd like another pair of eyes on it. Can you split out the IR change as Rafael suggested?

[Bigcheese]

Adding some reviewers that last touched metadata.

[Bigcheese]

In writing the documentation I ran into an issue defining the precise semantics of .cg_profile when it includes a symbol which has not previously been referenced. In an updated patch I'm treating it as if .weak <symbol> was written if <symbol> has not yet been used. This leads to the following behavior:

.section .test,"aw",@progbits
a:    .word b

    .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:
late3:
.L.local:

a: local
late3: local
b: global
freq: weak
late: global
late2: weak
.L.local: not in symbol table

Note that a and late2 disagree about what binding they have based on if they came before or after .cg_profile. Also .L.local generates a null symbol index because it doesn't get put in the symbol table.

[Bigcheese]

• Remove IR parts, those will be in a separate patch.
• Update Extensions.rst
• Add assembly only test

[pcc]

docs/Extensions.rst

326 ↗

(On Diff #149005)

This seems a little weird. In addition to the cases you mentioned, it would also seem to imply that code like this:

.cg_profile foo, bar, 42

.globl foo
foo:
call bar

will cause bar to become STB_WEAK. I guess the idea behind setting the binding to STB_WEAKrather than STB_GLOBAL is that you don't want to cause an undefined symbol error in the case where all other object files use STB_WEAK for the symbol and one of those object files contains a relocation to the symbol? In that case, maybe we should only end up setting the binding to weak if we don't emit any relocations for the symbol (i.e. isUsedInReloc() is false)?

lib/MC/ELFObjectWriter.cpp

1163

You can move this case under SHT_SYMTAB_SHNDX.

test/MC/ELF/cgprofile.s

9 ↗

(On Diff #149005)

Using a symbol index of 0 seems like valid behaviour, but maybe it would be a little better to point to the section symbol instead?

[Bigcheese]

docs/Extensions.rst

326 ↗

(On Diff #149005)

That would require delaying processing of .cg_profile entries until the end, but given the above issue, that's probably worth it. Another option is to error if the symbol doesn't already exist.

test/MC/ELF/cgprofile.s

9 ↗

(On Diff #149005)

Yeah, that would match the standard behavior of .L.

[Bigcheese]

I've changed the behavior to better match the existing semantics.

• Creating symbols is delayed until the end of the file.
• Referencing an undefined temporary symbol is an error.

[pcc]

LGTM

test/MC/ELF/cgprofile.s

1 ↗

(On Diff #149378)

Can you change this test to test the -elf-cg-profile feature that you're adding to llvm-readobj?

include/llvm/InitializePasses.h

 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
+void initializeCGProfilePassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createSCEVAAWrapperPass();
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBoundsCheckingLegacyPass();
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCallGraphDOTPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
+      (void) llvm::createCGProfilePass();
       (void) llvm::createCFLAndersAAWrapperPass();
       (void) llvm::createCFLSteensAAWrapperPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createLibCallsShrinkWrapPass();
       (void) llvm::createCalledValuePropagationPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createCostModelAnalysisPass();

include/llvm/MC/MCAssembler.h

public:
 
   // FIXME: This is a total hack, this should not be here. Once things are
   // factored so that the streamer has direct access to the .o writer, it can
   // disappear.
   MCLOHContainer &getLOHContainer() { return LOHContainer; }
   const MCLOHContainer &getLOHContainer() const {
     return const_cast<MCAssembler *>(this)->getLOHContainer();
   }
+
+  struct CGProfileEntry {
+    const MCSymbol *From;
+    const MCSymbol *To;
+    uint64_t Count;
+  };
+  std::vector<CGProfileEntry> CGProfile;
   /// @}
   /// \name Backend Data Access
   /// @{
 
   bool registerSection(MCSection &Section);
 
   void registerSymbol(const MCSymbol &Symbol, bool *Created = nullptr);
 

include/llvm/MC/MCELFStreamer.h

void EmitTBSSSymbol(MCSection *Section, MCSymbol *Symbol, uint64_t Size,
                       unsigned ByteAlignment = 0) override;
   void EmitValueImpl(const MCExpr *Value, unsigned Size,
                      SMLoc Loc = SMLoc()) override;
 
   void EmitIdent(StringRef IdentString) override;
 
   void EmitValueToAlignment(unsigned, int64_t, unsigned, unsigned) override;
 
+  void emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                          uint64_t Count) override;
+
   void FinishImpl() override;
 
   void EmitBundleAlignMode(unsigned AlignPow2) override;
   void EmitBundleLock(bool AlignToEnd) override;
   void EmitBundleUnlock() override;
 
 private:
   bool isBundleLocked() const;

include/llvm/MC/MCStreamer.h

public:
   virtual void EmitWinCFISaveXMM(unsigned Register, unsigned Offset,
                                  SMLoc Loc = SMLoc());
   virtual void EmitWinCFIPushFrame(bool Code, SMLoc Loc = SMLoc());
   virtual void EmitWinCFIEndProlog(SMLoc Loc = SMLoc());
   virtual void EmitWinEHHandler(const MCSymbol *Sym, bool Unwind, bool Except,
                                 SMLoc Loc = SMLoc());
   virtual void EmitWinEHHandlerData(SMLoc Loc = SMLoc());
 
+  virtual void emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                  uint64_t Count);
+
   /// Get the .pdata section used for the given section. Typically the given
   /// section is either the main .text section or some other COMDAT .text
   /// section, but it may be any section containing code.
   MCSection *getAssociatedPDataSection(const MCSection *TextSec);
 
   /// Get the .xdata section used for the given section.
   MCSection *getAssociatedXDataSection(const MCSection *TextSec);
 

include/llvm/Object/ELFTypes.h

 template <class ELFT> struct Elf_Vernaux_Impl;
 template <class ELFT> struct Elf_Versym_Impl;
 template <class ELFT> struct Elf_Hash_Impl;
 template <class ELFT> struct Elf_GnuHash_Impl;
 template <class ELFT> struct Elf_Chdr_Impl;
 template <class ELFT> struct Elf_Nhdr_Impl;
 template <class ELFT> class Elf_Note_Impl;
 template <class ELFT> class Elf_Note_Iterator_Impl;
+template <class ELFT> struct Elf_CGProfile_Impl;
 
 template <endianness E, bool Is64> struct ELFType {
 private:
   template <typename Ty>
   using packed = support::detail::packed_endian_specific_integral<Ty, E, 1>;
 
 public:
   static const endianness TargetEndianness = E;
public:
   using Vernaux = Elf_Vernaux_Impl<ELFType<E, Is64>>;
   using Versym = Elf_Versym_Impl<ELFType<E, Is64>>;
   using Hash = Elf_Hash_Impl<ELFType<E, Is64>>;
   using GnuHash = Elf_GnuHash_Impl<ELFType<E, Is64>>;
   using Chdr = Elf_Chdr_Impl<ELFType<E, Is64>>;
   using Nhdr = Elf_Nhdr_Impl<ELFType<E, Is64>>;
   using Note = Elf_Note_Impl<ELFType<E, Is64>>;
   using NoteIterator = Elf_Note_Iterator_Impl<ELFType<E, Is64>>;
+  using CGProfile = Elf_CGProfile_Impl<ELFType<E, Is64>>;
   using DynRange = ArrayRef<Dyn>;
   using ShdrRange = ArrayRef<Shdr>;
   using SymRange = ArrayRef<Sym>;
   using RelRange = ArrayRef<Rel>;
   using RelaRange = ArrayRef<Rela>;
   using PhdrRange = ArrayRef<Phdr>;
 
   using Half = packed<uint16_t>;
bool operator!=(Elf_Note_Iterator_Impl Other) const {
     return !(*this == Other);
   }
   Elf_Note_Impl<ELFT> operator*() const {
     assert(Nhdr && "dereferenced ELF note end iterator");
     return Elf_Note_Impl<ELFT>(*Nhdr);
   }
 };
 
+template <class ELFT>
+struct Elf_CGProfile_Impl {
+  LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
+  Elf_Word cgp_from;
+  Elf_Word cgp_to;
+  Elf_Xword cgp_weight;
+};
+
 // MIPS .reginfo section
 template <class ELFT>
 struct Elf_Mips_RegInfo;
 
 template <support::endianness TargetEndianness>
 struct Elf_Mips_RegInfo<ELFType<TargetEndianness, false>> {
   LLVM_ELF_IMPORT_TYPES(TargetEndianness, false)
   Elf_Word ri_gprmask;     // bit-mask of used general registers

include/llvm/Transforms/Instrumentation.h

struct SanitizerCoverageOptions {
 
   SanitizerCoverageOptions() = default;
 };
 
 // Insert SanitizerCoverage instrumentation.
 ModulePass *createSanitizerCoverageModulePass(
     const SanitizerCoverageOptions &Options = SanitizerCoverageOptions());
 
+ModulePass *createCGProfilePass();
+
 /// \brief Calculate what to divide by to scale counts.
 ///
 /// Given the maximum count, calculate a divisor that will scale all the
 /// weights to strictly less than std::numeric_limits<uint32_t>::max().
 static inline uint64_t calculateCountScale(uint64_t MaxCount) {
   return MaxCount < std::numeric_limits<uint32_t>::max()
              ? 1
              : MaxCount / std::numeric_limits<uint32_t>::max() + 1;

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

if (NamedMDNode *LinkerOptions = M.getNamedMetadata("llvm.linker.options")) {
     }
   }
 
   unsigned Version = 0;
   unsigned Flags = 0;
   StringRef Section;
 
   GetObjCImageInfo(M, Version, Flags, Section);
-  if (Section.empty())
-    return;
-
+  if (!Section.empty()) {
     auto *S = C.getELFSection(Section, ELF::SHT_PROGBITS, ELF::SHF_ALLOC);
     Streamer.SwitchSection(S);
     Streamer.EmitLabel(C.getOrCreateSymbol(StringRef("OBJC_IMAGE_INFO")));
     Streamer.EmitIntValue(Version, 4);
     Streamer.EmitIntValue(Flags, 4);
     Streamer.AddBlankLine();
   }
 
+  SmallVector<Module::ModuleFlagEntry, 8> ModuleFlags;
+  M.getModuleFlagsMetadata(ModuleFlags);
+
+  MDNode *CFGProfile = nullptr;
+
+  for (const auto &MFE : ModuleFlags) {
+    StringRef Key = MFE.Key->getString();
+    if (Key == "CG Profile") {
+      CFGProfile = cast<MDNode>(MFE.Val);
+      break;
+    }
+  }
+
+  if (!CFGProfile)
+    return;
+
+  for (const auto &Edge : CFGProfile->operands()) {
+    MDNode *E = cast<MDNode>(Edge);
+    const MCSymbol *From = Streamer.getContext().getOrCreateSymbol(
+        cast<MDString>(E->getOperand(0))->getString());
+    const MCSymbol *To = Streamer.getContext().getOrCreateSymbol(
+        cast<MDString>(E->getOperand(1))->getString());
+    uint64_t Count = cast<ConstantAsMetadata>(E->getOperand(2))
+                         ->getValue()
+                         ->getUniqueInteger()
+                         .getZExtValue();
+    Streamer.emitCGProfileEntry(From, To, Count);
+  }
+}
+
 MCSymbol *TargetLoweringObjectFileELF::getCFIPersonalitySymbol(
     const GlobalValue *GV, const TargetMachine &TM,
     MachineModuleInfo *MMI) const {
   unsigned Encoding = getPersonalityEncoding();
   if ((Encoding & 0x80) == DW_EH_PE_indirect)
     return getContext().getOrCreateSymbol(StringRef("DW.ref.") +
                                           TM.getSymbol(GV)->getName());
   if ((Encoding & 0x70) == DW_EH_PE_absptr)

lib/MC/ELFObjectWriter.cpp

case ELF::SHT_SYMTAB_SHNDX:
     sh_link = SymbolTableIndex;
     break;
 
   case ELF::SHT_GROUP:
     sh_link = SymbolTableIndex;
     sh_info = GroupSymbolIndex;
     break;
   }
 
   if (Section.getFlags() & ELF::SHF_LINK_ORDER) {
     const MCSymbol *Sym = Section.getAssociatedSymbol();
     const MCSectionELF *Sec = cast<MCSectionELF>(&Sym->getSection());
     sh_link = SectionIndexMap.lookup(Sec);
   }
 
   WriteSecHdrEntry(StrTabBuilder.getOffset(Section.getSectionName()),
                    Section.getType(), Section.getFlags(), 0, Offset, Size,
for (MCSection &Sec : Asm) {
 
     SectionIndexMap[&Section] = addToSectionTable(&Section);
     if (RelSection) {
       SectionIndexMap[RelSection] = addToSectionTable(RelSection);
       Relocations.push_back(RelSection);
     }
   }
 
+  MCSectionELF *CGProfileSection = nullptr;
+  if (!Asm.CGProfile.empty()) {
+    CGProfileSection =
+      Ctx.getELFSection(".note.llvm.cgprofile", ELF::SHT_NOTE, 0, 16, "");
+    SectionIndexMap[CGProfileSection] = addToSectionTable(CGProfileSection);
+  }
+
   for (MCSectionELF *Group : Groups) {
     align(Group->getAlignment());
 
     // Remember the offset into the file for this section.
     uint64_t SecStart = getStream().tell();
 
     const MCSymbol *SignatureSymbol = Group->getGroup();
     assert(SignatureSymbol);
for (MCSectionELF *RelSection : Relocations) {
 
     writeRelocations(Asm,
                      cast<MCSectionELF>(*RelSection->getAssociatedSection()));
 
     uint64_t SecEnd = getStream().tell();
     SectionOffsets[RelSection] = std::make_pair(SecStart, SecEnd);
   }
 
+  if (CGProfileSection) {
+    uint64_t SecStart = getStream().tell();
+    for (const MCAssembler::CGProfileEntry &CGPE : Asm.CGProfile) {
+      write32(CGPE.From->getIndex());
+      write32(CGPE.To->getIndex());
+      write64(CGPE.Count);
+    }
+    uint64_t SecEnd = getStream().tell();
+    SectionOffsets[CGProfileSection] = std::make_pair(SecStart, SecEnd);
+  }
+
   {
     uint64_t SecStart = getStream().tell();
     const MCSectionELF *Sec = createStringTable(Ctx);
     uint64_t SecEnd = getStream().tell();
     SectionOffsets[Sec] = std::make_pair(SecStart, SecEnd);
   }
 
   uint64_t NaturalAlignment = is64Bit() ? 8 : 4;

lib/MC/MCAsmStreamer.cpp

void EmitWinCFISaveXMM(unsigned Register, unsigned Offset,
                          SMLoc Loc) override;
   void EmitWinCFIPushFrame(bool Code, SMLoc Loc) override;
   void EmitWinCFIEndProlog(SMLoc Loc) override;
 
   void EmitWinEHHandler(const MCSymbol *Sym, bool Unwind, bool Except,
                         SMLoc Loc) override;
   void EmitWinEHHandlerData(SMLoc Loc) override;
 
+  void emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                          uint64_t Count) override;
+
   void EmitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI,
                        bool PrintSchedInfo) override;
 
   void EmitBundleAlignMode(unsigned AlignPow2) override;
   void EmitBundleLock(bool AlignToEnd) override;
   void EmitBundleUnlock() override;
 
   bool EmitRelocDirective(const MCExpr &Offset, StringRef Name,

 
 void MCAsmStreamer::EmitWinCFIEndProlog(SMLoc Loc) {
   MCStreamer::EmitWinCFIEndProlog(Loc);
 
   OS << "\t.seh_endprologue";
   EmitEOL();
 }
 
+void MCAsmStreamer::emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                       uint64_t Count) {
+  OS << "\t.cg_profile ";
+  From->print(OS, MAI);
+  OS << ", ";
+  To->print(OS, MAI);
+  OS << ", " << Count;
+  EmitEOL();
+}
+
 void MCAsmStreamer::AddEncodingComment(const MCInst &Inst,
                                        const MCSubtargetInfo &STI,
                                        bool PrintSchedInfo) {
   raw_ostream &OS = GetCommentOS();
   SmallString<256> Code;
   SmallVector<MCFixup, 4> Fixups;
   raw_svector_ostream VecOS(Code);
   Emitter->encodeInstruction(Inst, VecOS, Fixups, STI);

lib/MC/MCELFStreamer.cpp

void MCELFStreamer::EmitValueToAlignment(unsigned ByteAlignment,
                                          unsigned ValueSize,
                                          unsigned MaxBytesToEmit) {
   if (isBundleLocked())
     report_fatal_error("Emitting values inside a locked bundle is forbidden");
   MCObjectStreamer::EmitValueToAlignment(ByteAlignment, Value,
                                          ValueSize, MaxBytesToEmit);
 }
 
+void MCELFStreamer::emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                       uint64_t Count) {
+  getAssembler().CGProfile.push_back({From, To, Count});
+}
+
 void MCELFStreamer::EmitIdent(StringRef IdentString) {
   MCSection *Comment = getAssembler().getContext().getELFSection(
       ".comment", ELF::SHT_PROGBITS, ELF::SHF_MERGE | ELF::SHF_STRINGS, 1, "");
   PushSection();
   SwitchSection(Comment);
   if (!SeenIdent) {
     EmitIntValue(0, 1);
     SeenIdent = true;

lib/MC/MCParser/ELFAsmParser.cpp

void Initialize(MCAsmParser &Parser) override {
     addDirectiveHandler<&ELFAsmParser::ParseDirectiveSymbolAttribute>(".local");
     addDirectiveHandler<
       &ELFAsmParser::ParseDirectiveSymbolAttribute>(".protected");
     addDirectiveHandler<
       &ELFAsmParser::ParseDirectiveSymbolAttribute>(".internal");
     addDirectiveHandler<
       &ELFAsmParser::ParseDirectiveSymbolAttribute>(".hidden");
     addDirectiveHandler<&ELFAsmParser::ParseDirectiveSubsection>(".subsection");
+    addDirectiveHandler<&ELFAsmParser::ParseDirectiveCGProfile>(".cg_profile");
   }
 
   // FIXME: Part of this logic is duplicated in the MCELFStreamer. What is
   // the best way for us to get access to it?
   bool ParseSectionDirectiveData(StringRef, SMLoc) {
     return ParseSectionSwitch(".data", ELF::SHT_PROGBITS,
                               ELF::SHF_WRITE | ELF::SHF_ALLOC,
                               SectionKind::getData());
public:
   bool ParseDirectivePrevious(StringRef, SMLoc);
   bool ParseDirectiveType(StringRef, SMLoc);
   bool ParseDirectiveIdent(StringRef, SMLoc);
   bool ParseDirectiveSymver(StringRef, SMLoc);
   bool ParseDirectiveVersion(StringRef, SMLoc);
   bool ParseDirectiveWeakref(StringRef, SMLoc);
   bool ParseDirectiveSymbolAttribute(StringRef, SMLoc);
   bool ParseDirectiveSubsection(StringRef, SMLoc);
+  bool ParseDirectiveCGProfile(StringRef, SMLoc);
 
 private:
   bool ParseSectionName(StringRef &SectionName);
   bool ParseSectionArguments(bool IsPush, SMLoc loc);
   unsigned parseSunStyleSectionFlags();
   bool maybeParseSectionType(StringRef &TypeName);
   bool parseMergeSize(int64_t &Size);
   bool parseGroup(StringRef &GroupName);
if (getLexer().isNot(AsmToken::EndOfStatement))
     return TokError("unexpected token in directive");
 
   Lex();
 
   getStreamer().SubSection(Subsection);
   return false;
 }
 
+/// ParseDirectiveCGProfile
+///  ::= .cg_profile identifier, identifier, <number>
+bool ELFAsmParser::ParseDirectiveCGProfile(StringRef, SMLoc) {
+  StringRef From;
+  if (getParser().parseIdentifier(From))
+    return TokError("expected identifier in directive");
+
+  if (getLexer().isNot(AsmToken::Comma))
+    return TokError("expected a comma");
+  Lex();
+
+  StringRef To;
+  if (getParser().parseIdentifier(To))
+    return TokError("expected identifier in directive");
+
+  if (getLexer().isNot(AsmToken::Comma))
+    return TokError("expected a comma");
+  Lex();
+
+  int64_t Count;
+  if (getParser().parseIntToken(
+          Count, "expected integer count in '.cg_profile' directive"))
+    return true;
+
+  if (getLexer().isNot(AsmToken::EndOfStatement))
+    return TokError("unexpected token in directive");
+
+  MCSymbol *FromSym = getContext().getOrCreateSymbol(From);
+  MCSymbol *ToSym = getContext().getOrCreateSymbol(To);
+
+  getStreamer().emitCGProfileEntry(FromSym, ToSym, Count);
+  return false;
+}
+
 namespace llvm {
 
 MCAsmParserExtension *createELFAsmParser() {
   return new ELFAsmParser;
 }
 
 } // end namespace llvm

lib/MC/MCStreamer.cpp

 void MCStreamer::EmitWinEHHandlerData(SMLoc Loc) {
   WinEH::FrameInfo *CurFrame = EnsureValidWinFrameInfo(Loc);
   if (!CurFrame)
     return;
   if (CurFrame->ChainedParent)
     getContext().reportError(Loc, "Chained unwind areas can't have handlers!");
 }
 
+void MCStreamer::emitCGProfileEntry(const MCSymbol *From, const MCSymbol *To,
+                                    uint64_t Count) {
+}
+
 static MCSection *getWinCFISection(MCContext &Context, unsigned *NextWinCFIID,
                                    MCSection *MainCFISec,
                                    const MCSection *TextSec) {
   // If this is the main .text section, use the main unwind info section.
   if (TextSec == Context.getObjectFileInfo()->getTextSection())
     return MainCFISec;
 
   const auto *TextSecCOFF = cast<MCSectionCOFF>(TextSec);

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
 
   // GlobalOpt already deletes dead functions and globals, at -O2 try a
   // late pass of GlobalDCE.  It is capable of deleting dead cycles.
   if (OptLevel > 1) {
     MPM.add(createGlobalDCEPass());         // Remove dead fns and globals.
     MPM.add(createConstantMergePass());     // Merge dup global constants
   }
 
+  MPM.add(createCGProfilePass());
+
   if (MergeFunctions)
     MPM.add(createMergeFunctionsPass());
 
   // LoopSink pass sinks instructions hoisted by LICM, which serves as a
   // canonicalization pass that enables other optimizations. As a result,
   // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
   // result too early.
   MPM.add(createLoopSinkPass());

lib/Transforms/Instrumentation/CGProfile.cpp

+//===-- CGProfile.cpp -----------------------------------------------------===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Instrumentation.h"
+
+#include <array>
+
+using namespace llvm;
+
+class CGProfilePass : public ModulePass {
+public:
+  static char ID;
+
+  CGProfilePass() : ModulePass(ID) {
+    initializeCGProfilePassPass(
+      *PassRegistry::getPassRegistry());
+  }
+
+  StringRef getPassName() const override { return "CGProfilePass"; }
+
+private:
+  bool runOnModule(Module &M) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  }
+};
+
+bool CGProfilePass::runOnModule(Module &M) {
+  if (skipModule(M))
+    return false;
+
+  llvm::DenseMap<std::pair<StringRef, StringRef>, uint64_t> Counts;
+
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
+    auto &BFI = getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+    for (auto &BB : F) {
+      Optional<uint64_t> BBCount = BFI.getBlockProfileCount(&BB);
+      if (!BBCount)
+        continue;
+      for (auto &I : BB) {
+        auto *CI = dyn_cast<CallInst>(&I);
+        if (!CI)
+          continue;
+        Function *CalledF = CI->getCalledFunction();
+        if (!CalledF || CalledF->isIntrinsic())
+          continue;
+
+        uint64_t &Count =
+            Counts[std::make_pair(F.getName(), CalledF->getName())];
+        Count = SaturatingAdd(Count, *BBCount);
+      }
+    }
+  }
+
+  if (Counts.empty())
+    return false;
+
+  LLVMContext &Context = M.getContext();
+  MDBuilder MDB(Context);
+  std::vector<Metadata *> Nodes;
+
+  for (auto E : Counts) {
+    SmallVector<Metadata *, 3> Vals;
+    Vals.push_back(MDB.createString(E.first.first));
+    Vals.push_back(MDB.createString(E.first.second));
+    Vals.push_back(MDB.createConstant(
+        ConstantInt::get(Type::getInt64Ty(Context), E.second)));
+    Nodes.push_back(MDNode::get(Context, Vals));
+  }
+
+  M.addModuleFlag(Module::Append, "CG Profile", MDNode::get(Context, Nodes));
+
+  return true;
+}
+
+char CGProfilePass::ID = 0;
+INITIALIZE_PASS_BEGIN(CGProfilePass, "cg-profile",
+                      "Generate profile information from the call graph.", false,
+                      false)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+INITIALIZE_PASS_END(CGProfilePass, "cg-profile",
+                    "Generate profile information from the call graph.", false, false)
+
+ModulePass *llvm::createCGProfilePass() {
+  return new CGProfilePass();
+}

lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
+  CGProfile.cpp
   DataFlowSanitizer.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
   IndirectCallPromotion.cpp
   Instrumentation.cpp
   InstrProfiling.cpp
   PGOInstrumentation.cpp
   PGOMemOPSizeOpt.cpp

lib/Transforms/Instrumentation/Instrumentation.cpp

 
 /// initializeInstrumentation - Initialize all passes in the TransformUtils
 /// library.
 void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeAddressSanitizerPass(Registry);
   initializeAddressSanitizerModulePass(Registry);
   initializeBoundsCheckingLegacyPassPass(Registry);
   initializeGCOVProfilerLegacyPassPass(Registry);
+  initializeCGProfilePassPass(Registry);
   initializePGOInstrumentationGenLegacyPassPass(Registry);
   initializePGOInstrumentationUseLegacyPassPass(Registry);
   initializePGOIndirectCallPromotionLegacyPassPass(Registry);
   initializePGOMemOPSizeOptLegacyPassPass(Registry);
   initializeInstrProfilingLegacyPassPass(Registry);
   initializeMemorySanitizerPass(Registry);
   initializeHWAddressSanitizerPass(Registry);
   initializeThreadSanitizerPass(Registry);

tools/llvm-readobj/ELFDumper.cpp

#define TYPEDEF_ELF_TYPES(ELFT)                                                \
   using Elf_GnuHash = typename ELFT::GnuHash;                                  \
   using Elf_Note  = typename ELFT::Note;                                       \
   using Elf_Sym_Range = typename ELFT::SymRange;                               \
   using Elf_Versym = typename ELFT::Versym;                                    \
   using Elf_Verneed = typename ELFT::Verneed;                                  \
   using Elf_Vernaux = typename ELFT::Vernaux;                                  \
   using Elf_Verdef = typename ELFT::Verdef;                                    \
   using Elf_Verdaux = typename ELFT::Verdaux;                                  \
+  using Elf_CGProfile = typename ELFT::CGProfile;                              \
   using uintX_t = typename ELFT::uint;
 
 namespace {
 
 template <class ELFT> class DumpStyle;
 
 /// Represents a contiguous uniform range in the file. We cannot just create a
 /// range directly because when creating one of these from the .dynamic table
public:
   void printMipsABIFlags() override;
   void printMipsReginfo() override;
   void printMipsOptions() override;
 
   void printStackMap() const override;
 
   void printHashHistogram() override;
 
+  void printCGProfile() override;
+
   void printNotes() override;
 
   void printELFLinkerOptions() override;
 
 private:
   std::unique_ptr<DumpStyle<ELFT>> ELFDumperStyle;
 
   TYPEDEF_ELF_TYPES(ELFT)
private:
   DynRegionInfo DynPLTRelRegion;
   DynRegionInfo DynSymRegion;
   DynRegionInfo DynamicTable;
   StringRef DynamicStringTable;
   StringRef SOName;
   const Elf_Hash *HashTable = nullptr;
   const Elf_GnuHash *GnuHashTable = nullptr;
   const Elf_Shdr *DotSymtabSec = nullptr;
+  const Elf_Shdr *DotCGProfileSec = nullptr;
   StringRef DynSymtabName;
   ArrayRef<Elf_Word> ShndxTable;
 
   const Elf_Shdr *dot_gnu_version_sec = nullptr;   // .gnu.version
   const Elf_Shdr *dot_gnu_version_r_sec = nullptr; // .gnu.version_r
   const Elf_Shdr *dot_gnu_version_d_sec = nullptr; // .gnu.version_d
 
   // Records for each version index the corresponding Verdef or Vernaux entry.
public:
 
   Elf_Rel_Range dyn_rels() const;
   Elf_Rela_Range dyn_relas() const;
   std::string getFullSymbolName(const Elf_Sym *Symbol, StringRef StrTable,
                                 bool IsDynamic) const;
   void getSectionNameIndex(const Elf_Sym *Symbol, const Elf_Sym *FirstSym,
                            StringRef &SectionName,
                            unsigned &SectionIndex) const;
+  StringRef getStaticSymbolName(uint32_t Index) const;
 
   void printSymbolsHelper(bool IsDynamic) const;
   const Elf_Shdr *getDotSymtabSec() const { return DotSymtabSec; }
+  const Elf_Shdr *getDotCGProfileSec() const { return DotCGProfileSec; }
   ArrayRef<Elf_Word> getShndxTable() const { return ShndxTable; }
   StringRef getDynamicStringTable() const { return DynamicStringTable; }
   const DynRegionInfo &getDynRelRegion() const { return DynRelRegion; }
   const DynRegionInfo &getDynRelaRegion() const { return DynRelaRegion; }
   const DynRegionInfo &getDynPLTRelRegion() const { return DynPLTRelRegion; }
   const Elf_Hash *getHashTable() const { return HashTable; }
   const Elf_GnuHash *getGnuHashTable() const { return GnuHashTable; }
 };
public:
   virtual void printDynamicRelocations(const ELFFile<ELFT> *Obj) = 0;
   virtual void printSymtabMessage(const ELFFile<ELFT> *obj, StringRef Name,
                                   size_t Offset) {}
   virtual void printSymbol(const ELFFile<ELFT> *Obj, const Elf_Sym *Symbol,
                            const Elf_Sym *FirstSym, StringRef StrTable,
                            bool IsDynamic) = 0;
   virtual void printProgramHeaders(const ELFFile<ELFT> *Obj) = 0;
   virtual void printHashHistogram(const ELFFile<ELFT> *Obj) = 0;
+  virtual void printCGProfile(const ELFFile<ELFT> *Obj) = 0;
   virtual void printNotes(const ELFFile<ELFT> *Obj) = 0;
   virtual void printELFLinkerOptions(const ELFFile<ELFT> *Obj) = 0;
   virtual void printMipsGOT(const MipsGOTParser<ELFT> &Parser) = 0;
   virtual void printMipsPLT(const MipsGOTParser<ELFT> &Parser) = 0;
   const ELFDumper<ELFT> *dumper() const { return Dumper; }
 
 private:
   const ELFDumper<ELFT> *Dumper;
public:
   void printSections(const ELFO *Obj) override;
   void printSymbols(const ELFO *Obj) override;
   void printDynamicSymbols(const ELFO *Obj) override;
   void printDynamicRelocations(const ELFO *Obj) override;
   void printSymtabMessage(const ELFO *Obj, StringRef Name,
                           size_t Offset) override;
   void printProgramHeaders(const ELFO *Obj) override;
   void printHashHistogram(const ELFFile<ELFT> *Obj) override;
+  void printCGProfile(const ELFFile<ELFT> *Obj) override;
   void printNotes(const ELFFile<ELFT> *Obj) override;
   void printELFLinkerOptions(const ELFFile<ELFT> *Obj) override;
   void printMipsGOT(const MipsGOTParser<ELFT> &Parser) override;
   void printMipsPLT(const MipsGOTParser<ELFT> &Parser) override;
 
 private:
   struct Field {
     StringRef Str;
public:
   void printRelocations(const ELFO *Obj) override;
   void printRelocations(const Elf_Shdr *Sec, const ELFO *Obj);
   void printSections(const ELFO *Obj) override;
   void printSymbols(const ELFO *Obj) override;
   void printDynamicSymbols(const ELFO *Obj) override;
   void printDynamicRelocations(const ELFO *Obj) override;
   void printProgramHeaders(const ELFO *Obj) override;
   void printHashHistogram(const ELFFile<ELFT> *Obj) override;
+  void printCGProfile(const ELFFile<ELFT> *Obj) override;
   void printNotes(const ELFFile<ELFT> *Obj) override;
   void printELFLinkerOptions(const ELFFile<ELFT> *Obj) override;
   void printMipsGOT(const MipsGOTParser<ELFT> &Parser) override;
   void printMipsPLT(const MipsGOTParser<ELFT> &Parser) override;
 
 private:
   void printRelocation(const ELFO *Obj, Elf_Rela Rel, const Elf_Shdr *SymTab);
   void printDynamicRelocation(const ELFO *Obj, Elf_Rela Rel);
if (entry.isVerdef()) {
     IsDefault = false;
   }
   if (name_offset >= StrTab.size())
     reportError("Invalid string offset");
   return StringRef(StrTab.data() + name_offset);
 }
 
 template <typename ELFT>
+StringRef ELFDumper<ELFT>::getStaticSymbolName(uint32_t Index) const {
+  StringRef StrTable = unwrapOrError(Obj->getStringTableForSymtab(*DotSymtabSec));
+  Elf_Sym_Range Syms = unwrapOrError(Obj->symbols(DotSymtabSec));
+  if (Index >= Syms.size())
+    reportError("Invalid symbol index");
+  const Elf_Sym *Sym = &Syms[Index];
+  return unwrapOrError(Sym->getName(StrTable));
+}
+
+template <typename ELFT>
 std::string ELFDumper<ELFT>::getFullSymbolName(const Elf_Sym *Symbol,
                                                StringRef StrTable,
                                                bool IsDynamic) const {
   StringRef SymbolName = unwrapOrError(Symbol->getName(StrTable));
   if (!IsDynamic)
     return SymbolName;
 
   std::string FullSymbolName(SymbolName);
case ELF::SHT_GNU_verdef:
         reportError("Multiple SHT_GNU_verdef");
       dot_gnu_version_d_sec = &Sec;
       break;
     case ELF::SHT_GNU_verneed:
       if (dot_gnu_version_r_sec != nullptr)
         reportError("Multiple SHT_GNU_verneed");
       dot_gnu_version_r_sec = &Sec;
       break;
+    case ELF::SHT_NOTE:
+      if (unwrapOrError(Obj->getSectionName(&Sec)) != ".note.llvm.cgprofile")
+        break;
+      if (DotCGProfileSec != nullptr)
+        reportError("Multiple .note.llvm.cgprofile");
+      DotCGProfileSec = &Sec;
     }
   }
 
   parseDynamicTable(LoadSegments);
 
   if (opts::Output == opts::GNU)
     ELFDumperStyle.reset(new GNUStyle<ELFT>(Writer, this));
   else

 void ELFDumper<ELFT>::printDynamicSymbols() {
   ELFDumperStyle->printDynamicSymbols(Obj);
 }
 
 template <class ELFT> void ELFDumper<ELFT>::printHashHistogram() {
   ELFDumperStyle->printHashHistogram(Obj);
 }
 
+template <class ELFT> void ELFDumper<ELFT>::printCGProfile() {
+  ELFDumperStyle->printCGProfile(Obj);
+}
+
 template <class ELFT> void ELFDumper<ELFT>::printNotes() {
   ELFDumperStyle->printNotes(Obj);
 }
 
 template <class ELFT> void ELFDumper<ELFT>::printELFLinkerOptions() {
   ELFDumperStyle->printELFLinkerOptions(Obj);
 }
 
for (size_t I = 0; I <MaxChain; I++) {
       CumulativeNonZero += Count[I] * I;
       OS << format("%7lu  %-10lu (%5.1f%%)     %5.1f%%\n", I, Count[I],
                    (Count[I] * 100.0) / NBucket,
                    (CumulativeNonZero * 100.0) / TotalSyms);
     }
   }
 }
 
+template <class ELFT>
+void GNUStyle<ELFT>::printCGProfile(const ELFFile<ELFT> *Obj) {
+  OS << "GNUStyle::printCGProfile not implemented\n";
+}
+
 static std::string getGNUNoteTypeName(const uint32_t NT) {
   static const struct {
     uint32_t ID;
     const char *Name;
   } Notes[] = {
       {ELF::NT_GNU_ABI_TAG, "NT_GNU_ABI_TAG (ABI version tag)"},
       {ELF::NT_GNU_HWCAP, "NT_GNU_HWCAP (DSO-supplied software HWCAP info)"},
       {ELF::NT_GNU_BUILD_ID, "NT_GNU_BUILD_ID (unique build ID bitstring)"},

 }
 
 template <class ELFT>
 void LLVMStyle<ELFT>::printHashHistogram(const ELFFile<ELFT> *Obj) {
   W.startLine() << "Hash Histogram not implemented!\n";
 }
 
 template <class ELFT>
+void LLVMStyle<ELFT>::printCGProfile(const ELFFile<ELFT> *Obj) {
+  ListScope L(W, "CGProfile");
+  if (!this->dumper()->getDotCGProfileSec())
+    return;
+  auto CGProfile =
+      unwrapOrError(Obj->template getSectionContentsAsArray<Elf_CGProfile>(
+          this->dumper()->getDotCGProfileSec()));
+  for (const Elf_CGProfile &CGPE : CGProfile) {
+    DictScope D(W, "CGProfileEntry");
+    W.printNumber("From", this->dumper()->getStaticSymbolName(CGPE.cgp_from),
+                  CGPE.cgp_from);
+    W.printNumber("To", this->dumper()->getStaticSymbolName(CGPE.cgp_to),
+                  CGPE.cgp_to);
+    W.printNumber("Weight", CGPE.cgp_weight);
+  }
+}
+
+template <class ELFT>
 void LLVMStyle<ELFT>::printNotes(const ELFFile<ELFT> *Obj) {
   W.startLine() << "printNotes not implemented!\n";
 }
 
 template <class ELFT>
 void LLVMStyle<ELFT>::printELFLinkerOptions(const ELFFile<ELFT> *Obj) {
   ListScope L(W, "LinkerOptions");
 

tools/llvm-readobj/ObjDumper.h

public:
   virtual void printNeededLibraries() { }
   virtual void printProgramHeaders() { }
   virtual void printHashTable() { }
   virtual void printGnuHashTable() { }
   virtual void printLoadName() {}
   virtual void printVersionInfo() {}
   virtual void printGroupSections() {}
   virtual void printHashHistogram() {}
+  virtual void printCGProfile() {}
   virtual void printNotes() {}
   virtual void printELFLinkerOptions() {}
 
   // Only implemented for ARM ELF at this time.
   virtual void printAttributes() { }
 
   // Only implemented for MIPS ELF at this time.
   virtual void printMipsPLTGOT() { }

tools/llvm-readobj/llvm-readobj.cpp

namespace opts {
   cl::alias SectionGroupsShort("g", cl::desc("Alias for -elf-sections-groups"),
                                cl::aliasopt(SectionGroups));
   cl::opt<bool> HashHistogram(
       "elf-hash-histogram",
       cl::desc("Display bucket list histogram for hash sections"));
   cl::alias HashHistogramShort("I", cl::desc("Alias for -elf-hash-histogram"),
                                cl::aliasopt(HashHistogram));
 
+  cl::opt<bool> CGProfile("elf-cg-profile", cl::desc("Display callgraph profile section"));
+
   cl::opt<OutputStyleTy>
       Output("elf-output-style", cl::desc("Specify ELF dump style"),
              cl::values(clEnumVal(LLVM, "LLVM default style"),
                         clEnumVal(GNU, "GNU readelf style")),
              cl::init(LLVM));
 } // namespace opts
 
 namespace llvm {
if (isMipsArch(Obj->getArch())) {
         Dumper->printMipsReginfo();
       if (opts::MipsOptions)
         Dumper->printMipsOptions();
     }
     if (opts::SectionGroups)
       Dumper->printGroupSections();
     if (opts::HashHistogram)
       Dumper->printHashHistogram();
+    if (opts::CGProfile)
+      Dumper->printCGProfile();
     if (opts::Notes)
       Dumper->printNotes();
   }
   if (Obj->isCOFF()) {
     if (opts::COFFImports)
       Dumper->printCOFFImports();
     if (opts::COFFExports)
       Dumper->printCOFFExports();