[llvm][Instrumentation] Add Call Graph Profile pass

[Bigcheese]

Summary

This patch adds support for generating a call graph profile from Branch Frequency Info.

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 = !{void ()* @a, void ()* @b, i64 32} ; Edge from a to b with a weight of 32
!3 = !{void (i1)* @freq, void ()* @a, i64 11} 
!4 = !{void (i1)* @freq, void ()* @b, i64 20}

[MaskRay]

BTW, can you take a look at https://reviews.llvm.org/D46228 ?

[compnerd]

lib/Transforms/Instrumentation/CGProfile.cpp

48

Can this not be const auto &F : M?

53

Can this not be const auto &BB : F?

57

Can this not be const auto &I : BB?

[Bigcheese]

Address review comments by adding const where applicable.

lib/Transforms/Instrumentation/CGProfile.cpp

48

No, because of getAnalysis.

[compnerd]

I assume that there is/will be a different change to the frontend to enable this for users?

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

146

Probably would be nice to hoist the Streamer.getContext() out of the loop.

auto &C = Streamer.getContext();

lib/Transforms/Instrumentation/CGProfile.cpp

76–89

Would be nice to move this (L75-88) into a helper function (UpdateModuleMetadata?)

[Bigcheese]

Address review comments.

Change to using ValueAsMetadata instead of strings and add a check to the verifier.

[Bigcheese]

This is enabled by default as the time and size overhead is so small.

[Bigcheese]

Use the correct diff.

[compnerd]

Thanks for the changes!

[davidxl]

This patch totally fell out of my radar. I will take a closer look at it.

[davidxl]

I am with Chandler here. Adding this pass to the legacy PM only will slow down the eventual migration to the new PM. It is better to do the new PM or both.

llvm/trunk/lib/Transforms/Instrumentation/CGProfile.cpp

52 ↗

(On Diff #152406)

You can check the existence of function entry count to decide whether to skip function earlier.

61 ↗

(On Diff #152406)

Use CallSite interface instead so that InvokeInst is handled as well:

CallSite CS(&I);
 if (!CS) continue;

Chandler has plan to unify the CallInst and InvokeInst in the future, but for now, CallSIte is the way to go.

65 ↗

(On Diff #152406)

you may want to check TTI to see if isLoweredToCall returns true.

68 ↗

(On Diff #152406)

You may also check indirect callsite to see if it has value profile data (indirect call target). If it has, you can create edges to the targets as well.

(I assume this information is for function layout purpose by the linker).

[chandlerc]

I had to revert this because the embedded function analysis runner inside the legacy pass manager for module passes appears to leak. =/ At least we found LeakSanitizer reports on the bots because of this commit.

Up to you whether you want to try and fix LegacyPM here or just switch to working on this w/ the new PM.

[Bigcheese]

• Move to new PM
• Use CallSite
• Bail early if no profile counts
• Use TargetTransformInfo::isLoweredToCall

llvm/trunk/lib/Transforms/Instrumentation/CGProfile.cpp

68 ↗

(On Diff #152406)

Is there an example where this is used? I'm not familiar with value profile data.

[davidxl]

The interface to get indirect call target value profile is bool getValueProfDataFromInst. See how it is used in ICallPromotionAnalysis::getPromotionCandidatesForInstruction(..) method.

[Bigcheese]

Add support for indirect calls using value profiling data.

[davidxl]

lib/Transforms/Instrumentation/CGProfile.cpp

67

The lowering check and count update code is shared between indirect and direct calls, so perhaps add a helper lambda function for it?

[Bigcheese]

Remove duplication on updating Counts.

[davidxl]

LGTM.

include/llvm/InitializePasses.h

 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFIInstrInserterPass(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/Transforms/Instrumentation.h

struct SanitizerCoverageOptions {
 
   SanitizerCoverageOptions() = default;
 };
 
 // Insert SanitizerCoverage instrumentation.
 ModulePass *createSanitizerCoverageModulePass(
     const SanitizerCoverageOptions &Options = SanitizerCoverageOptions());
 
+ModulePass *createCGProfilePass();
+
 /// 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(
+        MCSymbolRefExpr::create(From, MCSymbolRefExpr::VK_None, getContext()),
+        MCSymbolRefExpr::create(To, MCSymbolRefExpr::VK_None, getContext()),
+        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/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/ADT/MapVector.h"
+#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;
+
+  MapVector<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);

test/Instrumentation/cgprofile.ll

+; RUN: opt < %s -cg-profile -S | FileCheck %s
+
+declare void @b()
+
+define void @a() !prof !1 {
+  call void @b()
+  ret void
+}
+
+define void @freq(i1 %cond) !prof !1 {
+  br i1 %cond, label %A, label %B, !prof !2
+A:
+  call void @a();
+  ret void
+B:
+  call void @b();
+  ret void
+}
+
+!1 = !{!"function_entry_count", i64 32}
+!2 = !{!"branch_weights", i32 5, i32 10}
+
+; CHECK: !llvm.module.flags = !{![[cgprof:[0-9]+]]}
+; CHECK: ![[cgprof]] = !{i32 5, !"CG Profile", ![[prof:[0-9]+]]}
+; CHECK: ![[prof]] = !{![[e0:[0-9]+]], ![[e1:[0-9]+]], ![[e2:[0-9]+]]}
+; CHECK: ![[e0]] = !{!"a", !"b", i64 32}
+; CHECK: ![[e1]] = !{!"freq", !"a", i64 11}
+; CHECK: ![[e2]] = !{!"freq", !"b", i64 20}

test/MC/ELF/cgprofile.ll

+; RUN: llc -filetype=asm %s -o - -mtriple x86_64-pc-linux-gnu | FileCheck %s
+; RUN: llc -filetype=obj %s -o %t -mtriple x86_64-pc-linux-gnu
+; RUN: llvm-readobj -elf-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}
+!2 = !{!"a", !"b", i64 32}
+!3 = !{!"freq", !"a", i64 11}
+!4 = !{!"freq", !"b", 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:]