Index: include/llvm/CodeGen/TargetLoweringObjectFileImpl.h =================================================================== --- include/llvm/CodeGen/TargetLoweringObjectFileImpl.h +++ include/llvm/CodeGen/TargetLoweringObjectFileImpl.h @@ -36,11 +36,14 @@ protected: MCSymbolRefExpr::VariantKind PLTRelativeVariantKind = MCSymbolRefExpr::VK_None; + const TargetMachine *TM; public: TargetLoweringObjectFileELF() = default; ~TargetLoweringObjectFileELF() override = default; + void Initialize(MCContext &Ctx, const TargetMachine &TM) override; + /// Emit Obj-C garbage collection and linker options. void emitModuleMetadata(MCStreamer &Streamer, Module &M) const override; Index: include/llvm/Transforms/Instrumentation/CGProfile.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Instrumentation/CGProfile.h @@ -0,0 +1,31 @@ +//===- Transforms/Instrumentation/CGProfile.h -------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file provides the interface for LLVM's Call Graph Profile pass. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_CGPROFILE_H +#define LLVM_TRANSFORMS_CGPROFILE_H + +#include "llvm/ADT/MapVector.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class CGProfilePass : public PassInfoMixin { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + +private: + void addModuleFlags( + Module &M, + MapVector, uint64_t> &Counts) const; +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_CGPROFILE_H Index: lib/CodeGen/TargetLoweringObjectFileImpl.cpp =================================================================== --- lib/CodeGen/TargetLoweringObjectFileImpl.cpp +++ lib/CodeGen/TargetLoweringObjectFileImpl.cpp @@ -91,6 +91,12 @@ // ELF //===----------------------------------------------------------------------===// +void TargetLoweringObjectFileELF::Initialize(MCContext &Ctx, + const TargetMachine &TgtM) { + TargetLoweringObjectFile::Initialize(Ctx, TgtM); + TM = &TgtM; +} + void TargetLoweringObjectFileELF::emitModuleMetadata(MCStreamer &Streamer, Module &M) const { auto &C = getContext(); @@ -116,15 +122,49 @@ StringRef Section; GetObjCImageInfo(M, Version, Flags, Section); - if (Section.empty()) + 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 ModuleFlags; + M.getModuleFlagsMetadata(ModuleFlags); + + MDNode *CFGProfile = nullptr; + + for (const auto &MFE : ModuleFlags) { + StringRef Key = MFE.Key->getString(); + if (Key == "CG Profile") { + CFGProfile = cast(MFE.Val); + break; + } + } + + if (!CFGProfile) return; - 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(); + auto GetSym = [this](const MDOperand &MDO) { + auto V = cast(MDO); + const Function *F = cast(V->getValue()); + return TM->getSymbol(F); + }; + + for (const auto &Edge : CFGProfile->operands()) { + MDNode *E = cast(Edge); + const MCSymbol *From = GetSym(E->getOperand(0)); + const MCSymbol *To = GetSym(E->getOperand(1)); + uint64_t Count = cast(E->getOperand(2)) + ->getValue() + ->getUniqueInteger() + .getZExtValue(); + Streamer.emitCGProfileEntry( + MCSymbolRefExpr::create(From, MCSymbolRefExpr::VK_None, C), + MCSymbolRefExpr::create(To, MCSymbolRefExpr::VK_None, C), Count); + } } MCSymbol *TargetLoweringObjectFileELF::getCFIPersonalitySymbol( Index: lib/IR/Verifier.cpp =================================================================== --- lib/IR/Verifier.cpp +++ lib/IR/Verifier.cpp @@ -409,6 +409,7 @@ void visitModuleFlag(const MDNode *Op, DenseMap &SeenIDs, SmallVectorImpl &Requirements); + void visitModuleFlagCGProfileEntry(const MDOperand &MDO); void visitFunction(const Function &F); void visitBasicBlock(BasicBlock &BB); void visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty); @@ -1411,6 +1412,25 @@ Assert(M.getNamedMetadata("llvm.linker.options"), "'Linker Options' named metadata no longer supported"); } + + if (ID->getString() == "CG Profile") { + for (const MDOperand &MDO : cast(Op->getOperand(2))->operands()) + visitModuleFlagCGProfileEntry(MDO); + } +} + +void Verifier::visitModuleFlagCGProfileEntry(const MDOperand &MDO) { + auto Node = dyn_cast_or_null(MDO); + Assert(Node && Node->getNumOperands() == 3, "expected a MDNode triple", MDO); + auto From = dyn_cast_or_null(Node->getOperand(0)); + Assert(From && isa(From->getValue()), "expected a Function", + Node->getOperand(0)); + auto To = dyn_cast_or_null(Node->getOperand(1)); + Assert(To && isa(To->getValue()), "expected a Function", + Node->getOperand(1)); + auto Count = dyn_cast_or_null(Node->getOperand(2)); + Assert(Count && Count->getType()->isIntegerTy(), + "expected an integer constant", Node->getOperand(2)); } /// Return true if this attribute kind only applies to functions. Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -61,6 +61,7 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h" #include "llvm/Transforms/Instrumentation/GCOVProfiler.h" +#include "llvm/Transforms/Instrumentation/CGProfile.h" #include "llvm/Transforms/IPO/AlwaysInliner.h" #include "llvm/Transforms/IPO/ArgumentPromotion.h" #include "llvm/Transforms/IPO/CalledValuePropagation.h" @@ -832,6 +833,8 @@ // Add the core optimizing pipeline. MPM.addPass(createModuleToFunctionPassAdaptor(std::move(OptimizePM))); + MPM.addPass(CGProfilePass()); + // Now we need to do some global optimization transforms. // FIXME: It would seem like these should come first in the optimization // pipeline and maybe be the bottom of the canonicalization pipeline? Weird Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -40,6 +40,7 @@ #endif MODULE_PASS("always-inline", AlwaysInlinerPass()) MODULE_PASS("called-value-propagation", CalledValuePropagationPass()) +MODULE_PASS("cg-profile", CGProfilePass()) MODULE_PASS("constmerge", ConstantMergePass()) MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass()) MODULE_PASS("deadargelim", DeadArgumentEliminationPass()) Index: lib/Transforms/Instrumentation/CGProfile.cpp =================================================================== --- /dev/null +++ lib/Transforms/Instrumentation/CGProfile.cpp @@ -0,0 +1,100 @@ +//===-- 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/Transforms/Instrumentation/CGProfile.h" + +#include "llvm/ADT/MapVector.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/MDBuilder.h" +#include "llvm/IR/PassManager.h" +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/Transforms/Instrumentation.h" + +#include + +using namespace llvm; + +PreservedAnalyses CGProfilePass::run(Module &M, ModuleAnalysisManager &MAM) { + MapVector, uint64_t> Counts; + FunctionAnalysisManager &FAM = + MAM.getResult(M).getManager(); + InstrProfSymtab Symtab; + auto UpdateCounts = [&](TargetTransformInfo &TTI, Function *F, + Function *CalledF, uint64_t NewCount) { + if (!CalledF || !TTI.isLoweredToCall(CalledF)) + return; + uint64_t &Count = Counts[std::make_pair(F, CalledF)]; + Count = SaturatingAdd(Count, NewCount); + }; + // Ignore error here. Indirect calls are ignored if this fails. + (bool)Symtab.create(M); + for (auto &F : M) { + if (F.isDeclaration()) + continue; + auto &BFI = FAM.getResult(F); + if (BFI.getEntryFreq() == 0) + continue; + TargetTransformInfo &TTI = FAM.getResult(F); + for (auto &BB : F) { + Optional BBCount = BFI.getBlockProfileCount(&BB); + if (!BBCount) + continue; + for (auto &I : BB) { + CallSite CS(&I); + if (!CS) + continue; + if (CS.isIndirectCall()) { + InstrProfValueData ValueData[8]; + uint32_t ActualNumValueData; + uint64_t TotalC; + if (!getValueProfDataFromInst(*CS.getInstruction(), + IPVK_IndirectCallTarget, 8, ValueData, + ActualNumValueData, TotalC)) + continue; + for (const auto &VD : + ArrayRef(ValueData, ActualNumValueData)) { + UpdateCounts(TTI, &F, Symtab.getFunction(VD.Value), VD.Count); + } + continue; + } + UpdateCounts(TTI, &F, CS.getCalledFunction(), *BBCount); + } + } + } + + addModuleFlags(M, Counts); + + return PreservedAnalyses::all(); +} + +void CGProfilePass::addModuleFlags( + Module &M, + MapVector, uint64_t> &Counts) const { + if (Counts.empty()) + return; + + LLVMContext &Context = M.getContext(); + MDBuilder MDB(Context); + std::vector Nodes; + + for (auto E : Counts) { + SmallVector Vals; + Vals.push_back(ValueAsMetadata::get(E.first.first)); + Vals.push_back(ValueAsMetadata::get(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)); +} Index: lib/Transforms/Instrumentation/CMakeLists.txt =================================================================== --- lib/Transforms/Instrumentation/CMakeLists.txt +++ lib/Transforms/Instrumentation/CMakeLists.txt @@ -1,6 +1,7 @@ add_llvm_library(LLVMInstrumentation AddressSanitizer.cpp BoundsChecking.cpp + CGProfile.cpp DataFlowSanitizer.cpp GCOVProfiling.cpp MemorySanitizer.cpp Index: test/Instrumentation/cgprofile.ll =================================================================== --- /dev/null +++ test/Instrumentation/cgprofile.ll @@ -0,0 +1,41 @@ +; RUN: opt < %s -passes cg-profile -S | FileCheck %s + +declare void @b() + +define void @a() !prof !1 { + call void @b() + ret void +} + +@foo = common global i32 ()* null, align 8 +declare i32 @func1() +declare i32 @func2() +declare i32 @func3() +declare i32 @func4() + +define void @freq(i1 %cond) !prof !1 { + %tmp = load i32 ()*, i32 ()** @foo, align 8 + call i32 %tmp(), !prof !3 + 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} +!3 = !{!"VP", i32 0, i64 1600, i64 7651369219802541373, i64 1030, i64 -4377547752858689819, i64 410, i64 -6929281286627296573, i64 150, i64 -2545542355363006406, i64 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]+]], ![[e3:[0-9]+]], ![[e4:[0-9]+]], ![[e5:[0-9]+]], ![[e6:[0-9]+]]} +; CHECK: ![[e0]] = !{void ()* @a, void ()* @b, i64 32} +; CHECK: ![[e1]] = !{void (i1)* @freq, i32 ()* @func4, i64 1030} +; CHECK: ![[e2]] = !{void (i1)* @freq, i32 ()* @func2, i64 410} +; CHECK: ![[e3]] = !{void (i1)* @freq, i32 ()* @func3, i64 150} +; CHECK: ![[e4]] = !{void (i1)* @freq, i32 ()* @func1, i64 10} +; CHECK: ![[e5]] = !{void (i1)* @freq, void ()* @a, i64 11} +; CHECK: ![[e6]] = !{void (i1)* @freq, void ()* @b, i64 20} Index: test/MC/ELF/cgprofile.ll =================================================================== --- /dev/null +++ test/MC/ELF/cgprofile.ll @@ -0,0 +1,50 @@ +; 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 = !{void ()* @a, void ()* @b, i64 32} +!3 = !{void (i1)* @freq, void ()* @a, i64 11} +!4 = !{void (i1)* @freq, void ()* @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:] Index: test/Other/new-pm-defaults.ll =================================================================== --- test/Other/new-pm-defaults.ll +++ test/Other/new-pm-defaults.ll @@ -246,6 +246,7 @@ ; CHECK-O-NEXT: Running pass: SimplifyCFGPass ; CHECK-O-NEXT: Running pass: SpeculateAroundPHIsPass ; CHECK-O-NEXT: Finished llvm::Function pass manager run. +; CHECK-O-NEXT: Running pass: CGProfilePass ; CHECK-O-NEXT: Running pass: GlobalDCEPass ; CHECK-O-NEXT: Running pass: ConstantMergePass ; CHECK-O-NEXT: Finished llvm::Module pass manager run. Index: test/Verifier/module-flags-cgprofile.ll =================================================================== --- /dev/null +++ test/Verifier/module-flags-cgprofile.ll @@ -0,0 +1,30 @@ +; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s + +declare void @b() +declare void @a() + +!llvm.module.flags = !{!0} + +!0 = !{i32 5, !"CG Profile", !1} +!1 = !{!2, !"", !3, !4, !5, !6, !7, !8} +!2 = !{void ()* @a, void ()* @b, i64 32} +!3 = !{void ()* @a, void ()* @b} +!4 = !{void ()* @a, void ()* @b, i64 32, i64 32} +!5 = !{!"a", void ()* @b, i64 32} +!6 = !{void ()* @a, !"b", i64 32} +!7 = !{void ()* @a, void ()* @b, !""} +!8 = !{void ()* @a, void ()* @b, null} + +; CHECK: expected a MDNode triple +; CHECK: !"" +; CHECK: expected a MDNode triple +; CHECK: !3 = !{void ()* @a, void ()* @b} +; CHECK: expected a MDNode triple +; CHECK: !4 = !{void ()* @a, void ()* @b, i64 32, i64 32} +; CHECK: expected a Function +; CHECK: !"a" +; CHECK: expected a Function +; CHECK: !"b" +; CHECK: expected an integer constant +; CHECK: !"" +; CHECK: expected an integer constant