Index: llvm/include/llvm/CodeGen/AsmPrinter.h =================================================================== --- llvm/include/llvm/CodeGen/AsmPrinter.h +++ llvm/include/llvm/CodeGen/AsmPrinter.h @@ -15,6 +15,7 @@ #ifndef LLVM_CODEGEN_ASMPRINTER_H #define LLVM_CODEGEN_ASMPRINTER_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/AsmPrinterHandler.h" @@ -182,6 +183,22 @@ /// Emit comments in assembly output if this is true. bool VerboseAsm; + /// A numeric type identifier used in call graph section for indirect calls or + /// targets in. + using CGTypeIdVal = uint64_t; + + /// Type identifier to indirect call site labels mapping. + using IndirCallSites = DenseMap>; + + /// Map a function to its type id and entry label. This is used to list + /// indirect target functions in call graph section with their type ids. + DenseMap> + FuncEntryLabels; + + /// Map a function to its indirect call sites. This is used to list indirect + /// call sites in call graph section. + DenseMap CallSiteLabels; + /// Output stream for the stack usage file (i.e., .su file). std::unique_ptr StackUsageStream; @@ -365,6 +382,8 @@ void emitBBAddrMapSection(const MachineFunction &MF); + void emitCallGraphSection(); + void emitPseudoProbe(const MachineInstr &MI); void emitRemarksSection(remarks::RemarkStreamer &RS); @@ -785,6 +804,13 @@ //===------------------------------------------------------------------===// // Internal Implementation Details //===------------------------------------------------------------------===// + /// Emit indirect call and target information to a call graph section. + void emitCallGraphSection( + MCSection *CGSection, + const DenseMap> + &FuncEntryLabels, + const DenseMap> + &CallSiteLabels); void emitJumpTableEntry(const MachineJumpTableInfo *MJTI, const MachineBasicBlock *MBB, unsigned uid) const; Index: llvm/include/llvm/MC/MCObjectFileInfo.h =================================================================== --- llvm/include/llvm/MC/MCObjectFileInfo.h +++ llvm/include/llvm/MC/MCObjectFileInfo.h @@ -255,6 +255,8 @@ MCSection *getDataSection() const { return DataSection; } MCSection *getBSSSection() const { return BSSSection; } MCSection *getReadOnlySection() const { return ReadOnlySection; } + MCSection *getCallGraphSection(const StringRef &FunctionGroup, + const MCSymbol *FunctionSym) const; MCSection *getLSDASection() const { return LSDASection; } MCSection *getCompactUnwindSection() const { return CompactUnwindSection; } MCSection *getDwarfAbbrevSection() const { return DwarfAbbrevSection; } Index: llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp =================================================================== --- llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -1216,6 +1216,158 @@ *StackUsageStream << "static\n"; } +void AsmPrinter::emitCallGraphSection( + MCSection *CGSection, + const DenseMap> &FuncEntryLabels, + const DenseMap> &CallSiteLabels) { + if (FuncEntryLabels.empty() && CallSiteLabels.empty()) + return; + assert(CGSection && "Null call graph section"); + OutStreamer->PushSection(); + OutStreamer->SwitchSection(CGSection); + + // Emit for call sites, and function entries with matching type ids. + for (const auto &TypeIdCallSiteLabel : CallSiteLabels) { + uint64_t TypeId = TypeIdCallSiteLabel.first; + const auto &TypeIdCallSiteLabels = TypeIdCallSiteLabel.second; + + // Format version number. + OutStreamer->emitInt64(0); + + // Emit type id. + OutStreamer->emitInt64(TypeId); + + // Emit number of call site labels. + OutStreamer->emitInt64(TypeIdCallSiteLabels.size()); + + // Emit the call site labels. + for (const auto &Label : TypeIdCallSiteLabels) + OutStreamer->emitSymbolValue(Label, TM.getProgramPointerSize()); + + // Emit for the function entries with matching type id. + if (!FuncEntryLabels.count(TypeId)) { + // Emit the number of function entry labels: 0. + OutStreamer->emitInt64(0); + } else { + const auto &TypeIdFuncEntryLabels = FuncEntryLabels.find(TypeId)->second; + + // Emit the number of function entry labels. + OutStreamer->emitInt64(TypeIdFuncEntryLabels.size()); + + // Emit the function entry labels. + for (const auto &Label : TypeIdFuncEntryLabels) + OutStreamer->emitSymbolValue(Label, TM.getProgramPointerSize()); + } + } + + // Emit for the function entries that did not have a matching type id + // with any call site. + for (const auto &TypeIdFuncEntryLabel : FuncEntryLabels) { + uint64_t TypeId = TypeIdFuncEntryLabel.first; + const auto &TypeIdFuncEntryLabels = TypeIdFuncEntryLabel.second; + + if (!CallSiteLabels.count(TypeId)) { + // Format version number. + OutStreamer->emitInt64(0); + + // Emit type id. + OutStreamer->emitInt64(TypeId); + + // Emit the number of call site labels: 0. + OutStreamer->emitInt64(0); + + // Emit the number of function entry labels. + OutStreamer->emitInt64(TypeIdFuncEntryLabels.size()); + + // Emit the function entry labels. + for (const auto &Label : TypeIdFuncEntryLabels) { + OutStreamer->emitSymbolValue(Label, TM.getProgramPointerSize()); + } + } + } + + OutStreamer->PopSection(); +} + +void AsmPrinter::emitCallGraphSection() { + if (CallSiteLabels.empty() && FuncEntryLabels.empty()) + return; + + // Get a call graph section for a given function using its comdat group. This + // enables dead stripping of call graph sections if functions get removed. + auto GetCGSection = [&](const Function *Func) -> MCSection * { + assert(Func && "Null function"); + static DenseMap FuncToSection; + if (FuncToSection.count(Func)) + return FuncToSection[Func]; + const Comdat *C = Func->getComdat(); + assert((C || !TM.getTargetTriple().supportsCOMDAT() || + Func->hasLocalLinkage() || Func->isInterposable()) && + "Function comdat isn't set"); + std::string ComdatGroup = C ? C->getName().str() : ""; + MCSection *Section = + getObjFileLowering().getCallGraphSection(ComdatGroup, getSymbol(Func)); + assert(Section && "Failed to create .callgraph section"); + FuncToSection[Func] = Section; + return Section; + }; + + // Map numeric type identifiers to indirect target/call labels. + using Labels = DenseMap>; + + // Create and map CG sections to function entry labels. + DenseMap FuncEntryLabelsPerSection; + for (const auto &El : FuncEntryLabels) { + const Function *Func = El.first; + MCSection *CGSection = GetCGSection(Func); + const auto &FuncTypeId = std::get<0>(El.second); + const auto &FuncEntryLabel = std::get<1>(El.second); + FuncEntryLabelsPerSection[CGSection][FuncTypeId].push_back(FuncEntryLabel); + } + + // Create or get, and map CG sections to call site labels. + DenseMap CallSiteLabelsPerSection; + for (const auto &El : CallSiteLabels) { + const Function *Func = El.first; + MCSection *CGSection = GetCGSection(Func); + const auto &TypeIdToLabels = El.second; + for (const auto &El2 : TypeIdToLabels) { + const auto &TypeId = El2.first; + const auto &Labels = El2.second; + std::copy( + Labels.begin(), Labels.end(), + std::back_inserter(CallSiteLabelsPerSection[CGSection][TypeId])); + } + } + + // Emit to sections + const Labels EmptyLabels; + for (auto &El : FuncEntryLabelsPerSection) { + auto *CGSection = El.first; + Labels &FELabels = El.second; + if (CallSiteLabelsPerSection.count(CGSection)) + emitCallGraphSection(CGSection, FELabels, + CallSiteLabelsPerSection[CGSection]); + else + emitCallGraphSection(CGSection, FELabels, EmptyLabels); + + FELabels.clear(); + CallSiteLabelsPerSection.erase(CGSection); + } + + for (auto &El : CallSiteLabelsPerSection) { + auto *CGSection = El.first; + auto CSLabels = El.second; + assert(!FuncEntryLabelsPerSection.count(CGSection) || + FuncEntryLabelsPerSection[CGSection].empty() && + "Leftover function entry labels"); + emitCallGraphSection(CGSection, EmptyLabels, CSLabels); + } + + CallSiteLabels.clear(); + FuncEntryLabels.clear(); +} + static bool needFuncLabelsForEHOrDebugInfo(const MachineFunction &MF) { MachineModuleInfo &MMI = MF.getMMI(); if (!MF.getLandingPads().empty() || MF.hasEHFunclets() || MMI.hasDebugInfo()) @@ -1229,6 +1381,30 @@ classifyEHPersonality(MF.getFunction().getPersonalityFn())); } +/// Extracts a generalized numeric type identifier of a Function's type from +/// type metadata. Returns null if metadata cannot be found. +static ConstantInt *extractNumericCGTypeId(const Function &F) { + SmallVector Types; + F.getMetadata(LLVMContext::MD_type, Types); + MDString *MDGeneralizedTypeId = nullptr; + for (const auto &Type : Types) { + if (Type->getNumOperands() == 2 && isa(Type->getOperand(1))) { + auto *TMDS = cast(Type->getOperand(1)); + if (TMDS->getString().endswith("generalized")) { + MDGeneralizedTypeId = TMDS; + break; + } + } + } + + if (!MDGeneralizedTypeId) + return nullptr; + + uint64_t TypeIdVal = llvm::MD5Hash(MDGeneralizedTypeId->getString()); + Type *Int64Ty = Type::getInt64Ty(F.getContext()); + return cast(ConstantInt::get(Int64Ty, TypeIdVal)); +} + /// EmitFunctionBody - This method emits the body and trailer for a /// function. void AsmPrinter::emitFunctionBody() { @@ -1260,6 +1436,36 @@ int NumInstsInFunction = 0; bool CanDoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE); + if (TM.Options.EmitCallGraphSection) { + // If this function has external linkage or has its address taken and + // it is not a callback, then anything could call it. If so, emit a + // label to be referenced in the call graph section for indirect calls. + const auto &Func = MF->getFunction(); + if (!Func.hasLocalLinkage() || + Func.hasAddressTaken(nullptr, + /* IgnoreCallbackUses */ true, + /* IgnoreAssumeLikeCalls */ true, + /* IgnoreLLVMUsed */ false)) { + MCSymbol *S = MF->getContext().createTempSymbol(); + OutStreamer->emitLabel(S); + + const auto *TypeId = extractNumericCGTypeId(Func); + if (TypeId) { + auto TypeIdVal = TypeId->getZExtValue(); + FuncEntryLabels[&MF->getFunction()] = + std::pair(TypeIdVal, S); + } else { + // Function may be target to indirect calls but type id cannot be found. + errs() << "warning: can't find indirect target type id metadata " + << "for " << MF->getFunction().getName() << "\n"; + // For completeness of the list of indirect targets, use a special + // typeid (0). + FuncEntryLabels[&MF->getFunction()] = + std::pair(0, S); + } + } + } + const auto &CallSitesInfoMap = MF->getCallSitesInfo(); for (auto &MBB : *MF) { // Print a label for the basic block. emitBasicBlockStart(MBB); @@ -1348,6 +1554,22 @@ break; } + // TODO: Some indirect calls can get lowered to jump instructions, + // resulting in emitting labels for them. The extra information can + // be neglected while disassembly but still takes space in the binary. + if (TM.Options.EmitCallGraphSection && MI.isCall()) { + // Only indirect calls have type identifiers set. + const auto &CallSiteInfo = CallSitesInfoMap.find(&MI); + if (CallSiteInfo != CallSitesInfoMap.end()) { + if (auto *TypeId = CallSitesInfoMap.find(&MI)->second.TypeId) { + // Emit label for the indirect call. + uint64_t TypeIdVal = TypeId->getZExtValue(); + MCSymbol *S = MF->getContext().createTempSymbol(); + OutStreamer->emitLabel(S); + CallSiteLabels[&MF->getFunction()][TypeIdVal].push_back(S); + } + } + } // If there is a post-instruction symbol, emit a label for it here. if (MCSymbol *S = MI.getPostInstrSymbol()) OutStreamer->emitLabel(S); @@ -1754,6 +1976,9 @@ if (remarks::RemarkStreamer *RS = M.getContext().getMainRemarkStreamer()) emitRemarksSection(*RS); + if (TM.Options.EmitCallGraphSection) + emitCallGraphSection(); + TLOF.emitModuleMetadata(*OutStreamer, M); if (TM.getTargetTriple().isOSBinFormatELF()) { Index: llvm/lib/MC/MCObjectFileInfo.cpp =================================================================== --- llvm/lib/MC/MCObjectFileInfo.cpp +++ llvm/lib/MC/MCObjectFileInfo.cpp @@ -1004,6 +1004,21 @@ } } +MCSection * +MCObjectFileInfo::getCallGraphSection(const StringRef &FunctionGroup, + const MCSymbol *FunctionSym) const { + if (Ctx->getObjectFileType() != MCContext::IsELF) + return nullptr; + + static unsigned UniqueID = 1; + unsigned Flags = ELF::SHF_LINK_ORDER; + if (!FunctionGroup.empty()) + Flags |= ELF::SHF_GROUP; + return Ctx->getELFSection(".callgraph", ELF::SHT_PROGBITS, Flags, 0, + FunctionGroup, true, UniqueID++, + cast(FunctionSym)); +} + MCSection *MCObjectFileInfo::getDwarfComdatSection(const char *Name, uint64_t Hash) const { switch (Ctx->getTargetTriple().getObjectFormat()) { Index: llvm/test/CodeGen/call-graph-section.ll =================================================================== --- /dev/null +++ llvm/test/CodeGen/call-graph-section.ll @@ -0,0 +1,89 @@ +; Tests that we store the type identifiers in .callgraph section of the binary. + +; RUN: llc --call-graph-section -filetype=obj -o - < %s | \ +; RUN: llvm-readelf -x .callgraph - | FileCheck %s + +; CHECK: Hex dump of section '.callgraph': + +target triple = "x86_64-unknown-linux-gnu" + +$foo = comdat noduplicates + +$bar = comdat noduplicates + +$baz = comdat noduplicates + +$main = comdat noduplicates + +define dso_local void @foo() #0 comdat !type !4 { +entry: + ret void +} + +define dso_local i32 @bar(i8 signext %a) #0 comdat !type !5 { +entry: + %a.addr = alloca i8, align 1 + store i8 %a, i8* %a.addr, align 1 + ret i32 0 +} + +define dso_local i32* @baz(i8* %a) #0 comdat !type !6 { +entry: + %a.addr = alloca i8*, align 8 + store i8* %a, i8** %a.addr, align 8 + ret i32* null +} + +define dso_local i32 @main() #0 comdat !type !7 { +entry: + %retval = alloca i32, align 4 + %fp_foo = alloca void (...)*, align 8 + %a = alloca i8, align 1 + %fp_bar = alloca i32 (i8)*, align 8 + %fp_baz = alloca i32* (i8*)*, align 8 + store i32 0, i32* %retval, align 4 + store void (...)* bitcast (void ()* @foo to void (...)*), void (...)** %fp_foo, align 8 + %0 = load void (...)*, void (...)** %fp_foo, align 8 + call void (...) %0(), !type !8 + store i32 (i8)* @bar, i32 (i8)** %fp_bar, align 8 + %1 = load i32 (i8)*, i32 (i8)** %fp_bar, align 8 + %2 = load i8, i8* %a, align 1 + %call = call i32 %1(i8 signext %2), !type !9 + store i32* (i8*)* @baz, i32* (i8*)** %fp_baz, align 8 + %3 = load i32* (i8*)*, i32* (i8*)** %fp_baz, align 8 + %call1 = call i32* %3(i8* %a), !type !10 + ret i32 0 +} + +attributes #0 = { noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" } + +!llvm.module.flags = !{!0, !1, !2} + +!0 = !{i32 1, !"wchar_size", i32 4} +!1 = !{i32 7, !"uwtable", i32 1} +!2 = !{i32 7, !"frame-pointer", i32 2} + +; Check that the numeric type id (md5 hash) for the below type ids are emitted +; to the callgraph section. + +; CHECK-DAG: 2444f731 f5eecb3e +!4 = !{i64 0, !"_ZTSFvE.generalized"} + +; CHECK-DAG: 5486bc59 814b8e30 +!5 = !{i64 0, !"_ZTSFicE.generalized"} + +; CHECK-DAG: 7ade6814 f897fd77 +!6 = !{i64 0, !"_ZTSFPvS_E.generalized"} + +; CHECK-DAG: caaf769a 600968fa +!7 = !{i64 0, !"_ZTSFiE.generalized"} + +; CHECK-DAG: 2444f731 f5eecb3e +!8 = !{!"_ZTSFvE.generalized"} + +; CHECK-DAG: 5486bc59 814b8e30 +!9 = !{!"_ZTSFicE.generalized"} + +; CHECK-DAG: 7ade6814 f897fd77 +!10 = !{!"_ZTSFPvS_E.generalized"} +