Index: llvm/include/llvm/CodeGen/AsmPrinter.h =================================================================== --- llvm/include/llvm/CodeGen/AsmPrinter.h +++ llvm/include/llvm/CodeGen/AsmPrinter.h @@ -380,6 +380,22 @@ void emitPatchableFunctionEntries(); + //===------------------------------------------------------------------===// + // Branch Probability Dumping Implementation + //===------------------------------------------------------------------===// + + struct BranchProbEntry { + const MCSymbol *Sym = nullptr; + double Probability = 0.0; + }; + + // All the branch probabilities to be emitted. + std::vector BranchProbs; + + void emitLabelAndRecordBranchProb(double Probability); + + void emitBranchProbabilitySection(); + //===------------------------------------------------------------------===// // MachineFunctionPass Implementation. //===------------------------------------------------------------------===// Index: llvm/include/llvm/MC/MCObjectFileInfo.h =================================================================== --- llvm/include/llvm/MC/MCObjectFileInfo.h +++ llvm/include/llvm/MC/MCObjectFileInfo.h @@ -176,6 +176,9 @@ MCSection *PseudoProbeSection = nullptr; MCSection *PseudoProbeDescSection = nullptr; + /// Section containing dumped branch probabilities + MCSection *BranchProbabilitySection = nullptr; + // Section for metadata of llvm statistics. MCSection *LLVMStatsSection = nullptr; @@ -362,6 +365,8 @@ MCSection *getPseudoProbeDescSection(StringRef FuncName) const; + MCSection *getBranchProbabilitySection(const MCSection &TextSec) const; + MCSection *getLLVMStatsSection() const; MCSection *getPCSection(StringRef Name, const MCSection *TextSec) const; Index: llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp =================================================================== --- llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -22,6 +22,7 @@ #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/SmallVector.h" @@ -40,6 +41,7 @@ #include "llvm/CodeGen/GCMetadataPrinter.h" #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFrameInfo.h" @@ -119,6 +121,7 @@ #include #include #include +#include #include #include #include @@ -138,6 +141,10 @@ "performed with -basic-block-sections=labels. Enabling this " "flag during in-process ThinLTO is not supported.")); +static cl::opt EnableBranchProbabilityDumping( + "emit-asm-branch-probabilities", cl::init(false), cl::Hidden, + cl::desc("Dump branch probabilities during asm printing to debug section")); + const char DWARFGroupName[] = "dwarf"; const char DWARFGroupDescription[] = "DWARF Emission"; const char DbgTimerName[] = "emit"; @@ -1597,6 +1604,24 @@ classifyEHPersonality(MF.getFunction().getPersonalityFn())); } +/// Calculates probability of taking the branch target if MBPI is available. +static std::optional +getBranchProbForCondBr(const MachineInstr &MI, + MachineBranchProbabilityInfo *MBPI) { + assert(MI.isConditionalBranch() && !MI.isCall()); + + const MachineBasicBlock *Parent = MI.getParent(); + const TargetInstrInfo *TII = + Parent->getParent()->getSubtarget().getInstrInfo(); + assert(TII); + + const MachineBasicBlock *Target = TII->getBranchDestBlock(MI); + const auto TargetProb = MBPI->getEdgeProbability(Parent, Target); + const double Probability = + double(TargetProb.getNumerator()) / double(TargetProb.getDenominator()); + return Probability; +} + /// EmitFunctionBody - This method emits the body and trailer for a /// function. void AsmPrinter::emitFunctionBody() { @@ -1629,6 +1654,7 @@ bool IsEHa = MMI->getModule()->getModuleFlag("eh-asynch"); bool CanDoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE); + const bool CanDumpBranchProbs = EnableBranchProbabilityDumping; for (auto &MBB : *MF) { // Print a label for the basic block. emitBasicBlockStart(MBB); @@ -1727,6 +1753,13 @@ OutStreamer->emitRawComment("MEMBARRIER"); break; default: + if (CanDumpBranchProbs && MI.isConditionalBranch() && !MI.isCall()) { + if (auto *MBPI = + getAnalysisIfAvailable()) { + if (auto Prob = getBranchProbForCondBr(MI, MBPI)) + emitLabelAndRecordBranchProb(*Prob); + } + } emitInstruction(&MI); if (CanDoExtraAnalysis) { MCInst MCI; @@ -1918,6 +1951,8 @@ emitPatchableFunctionEntries(); + emitBranchProbabilitySection(); + if (isVerbose()) OutStreamer->getCommentOS() << "-- End function\n"; @@ -4139,6 +4174,47 @@ } } +void AsmPrinter::emitLabelAndRecordBranchProb(const double Probability) { + assert(Probability >= 0.0 && Probability <= 1.0 && + "branch probability should be in range [0.0,1.0]"); + + MCSymbol *Label = OutStreamer->getContext().createTempSymbol("branch_prob"); + Label->setUsedInReloc(); + OutStreamer->emitLabel(Label); + + BranchProbs.push_back({Label, Probability}); +} + +void AsmPrinter::emitBranchProbabilitySection() { + if (BranchProbs.empty()) + return; + + MCSection *BranchProbSec = + getObjFileLowering().getBranchProbabilitySection(*getCurrentSection()); + if (!BranchProbSec) + return; + + unsigned WordSizeBytes = MAI->getCodePointerSize(); + + OutStreamer->pushSection(); + auto OnExit = make_scope_exit([&] { OutStreamer->popSection(); }); + OutStreamer->switchSection(BranchProbSec); + + for (auto [Label, Prob] : BranchProbs) { + OutStreamer->emitSymbolValue(Label, WordSizeBytes); + + // Encode all data within 4 bytes to support 32 and 64 bit targets. + // Convert branch probability to value 0 - 10000 using 14 bits. + const long Val = lround(Prob * 10000.0); + assert(Val >= 0 && Val <= 10000); + const uint32_t Encoded = static_cast(Val & 0x3fff); + OutStreamer->emitInt32(Encoded); + + // Pad for alignment and reserved for future use + OutStreamer->emitZeros(WordSizeBytes - sizeof(Encoded)); + } +} + uint16_t AsmPrinter::getDwarfVersion() const { return OutStreamer->getContext().getDwarfVersion(); } Index: llvm/lib/MC/MCObjectFileInfo.cpp =================================================================== --- llvm/lib/MC/MCObjectFileInfo.cpp +++ llvm/lib/MC/MCObjectFileInfo.cpp @@ -536,6 +536,9 @@ PseudoProbeDescSection = Ctx->getELFSection(".pseudo_probe_desc", DebugSecType, 0); + BranchProbabilitySection = + Ctx->getELFSection(".branch_probabilities", DebugSecType, 0); + LLVMStatsSection = Ctx->getELFSection(".llvm_stats", ELF::SHT_PROGBITS, 0); } @@ -1212,6 +1215,25 @@ return PseudoProbeDescSection; } +MCSection * +MCObjectFileInfo::getBranchProbabilitySection(const MCSection &TextSec) const { + if (Ctx->getObjectFileType() != MCContext::IsELF) + return BranchProbabilitySection; + + const auto &ElfSec = static_cast(TextSec); + unsigned Flags = ELF::SHF_LINK_ORDER; + StringRef GroupName; + if (const MCSymbol *Group = ElfSec.getGroup()) { + GroupName = Group->getName(); + Flags |= ELF::SHF_GROUP; + } + + return Ctx->getELFSection(BranchProbabilitySection->getName(), + ELF::SHT_PROGBITS, Flags, 0, GroupName, true, + ElfSec.getUniqueID(), + cast(TextSec.getBeginSymbol())); +} + MCSection *MCObjectFileInfo::getLLVMStatsSection() const { return LLVMStatsSection; } Index: llvm/lib/Target/X86/X86InstrInfo.h =================================================================== --- llvm/lib/Target/X86/X86InstrInfo.h +++ llvm/lib/Target/X86/X86InstrInfo.h @@ -327,6 +327,8 @@ SmallVectorImpl &Cond, bool AllowModify) const override; + MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override; + int getJumpTableIndex(const MachineInstr &MI) const override; std::optional Index: llvm/lib/Target/X86/X86InstrInfo.cpp =================================================================== --- llvm/lib/Target/X86/X86InstrInfo.cpp +++ llvm/lib/Target/X86/X86InstrInfo.cpp @@ -3214,6 +3214,14 @@ return AnalyzeBranchImpl(MBB, TBB, FBB, Cond, CondBranches, AllowModify); } +MachineBasicBlock * +X86InstrInfo::getBranchDestBlock(const MachineInstr &MI) const { + assert(MI.getDesc().isBranch() && !MI.getDesc().isIndirectBranch() && + !MI.getDesc().isCall() && "Unexpected opcode!"); + // direct jumps and direct conditional jumps have target in first operand + return MI.getOperand(0).getMBB(); +} + static int getJumpTableIndexFromAddr(const MachineInstr &MI) { const MCInstrDesc &Desc = MI.getDesc(); int MemRefBegin = X86II::getMemoryOperandNo(Desc.TSFlags); Index: llvm/test/Transforms/PGOProfile/asm_emit_branch_prob.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/PGOProfile/asm_emit_branch_prob.ll @@ -0,0 +1,69 @@ +; REQUIRES: x86_64-linux +; REQUIRES: x86-registered-target + +; RUN: llc < %s -O1 -mtriple=x86_64 -filetype=obj -o %t -emit-asm-branch-probabilities +; RUN: llvm-readelf --hex-dump=.branch_probabilities %t \ +; RUN: | FileCheck %s --check-prefix=CHECK-BP-SEC + +; RUN: llc < %s -O1 -mtriple=x86_64 -filetype=obj -o %t +; RUN: llvm-readelf --hex-dump=.branch_probabilities %t 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-NO-BP-SEC + +; When enabled, the branch probabilities are dumped with the jump address and +; the percent encoded as a char from 0 to 10000. + +; // Test original source code +; void sink(int &); +; int test(int a, int b, int c) { +; if (a > 100) +; sink(a); +; sink(c); +; if (b > 100) +; sink(b); +; return a + b + c; +; } + +define dso_local noundef i32 @_Z4testiii(i32 noundef %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr { + %4 = alloca i32, align 4 + %5 = alloca i32, align 4 + %6 = alloca i32, align 4 + store i32 %0, ptr %4, align 4 + store i32 %1, ptr %5, align 4 + store i32 %2, ptr %6, align 4 + %7 = icmp sgt i32 %0, 100 + br i1 %7, label %8, label %9, !prof !0 + +8: ; preds = %3 + call void @_Z4sinkRi(ptr noundef nonnull align 4 dereferenceable(4) %4) + br label %9 + +9: ; preds = %8, %3 + call void @_Z4sinkRi(ptr noundef nonnull align 4 dereferenceable(4) %6) + %10 = icmp sgt i32 %1, 100 + br i1 %10, label %11, label %13, !prof !1 + +11: ; preds = %9 + call void @_Z4sinkRi(ptr noundef nonnull align 4 dereferenceable(4) %5) + %12 = load i32, ptr %5, align 4 + br label %13 + +13: ; preds = %11, %9 + %14 = phi i32 [ %12, %11 ], [ %1, %9 ] + %15 = load i32, ptr %4, align 4 + %16 = add nsw i32 %14, %15 + %17 = load i32, ptr %6, align 4 + %18 = add nsw i32 %16, %17 + ret i32 %18 +} + +declare void @_Z4sinkRi(ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #1 + + +!0 = !{!"branch_weights", i32 1000, i32 3000} +!1 = !{!"branch_weights", i32 3600, i32 400} + +; CHECK-BP-SEC: Hex dump of section '.branch_probabilities': +; CHECK-BP-SEC-NEXT: 0x00000000 {{([[:xdigit:]]{8}) ([[:xdigit:]]{8})}} {{4c1d|c409}}0000 00000000 {{(.{16})}} +; CHECK-BP-SEC-NEXT: 0x00000010 {{([[:xdigit:]]{8}) ([[:xdigit:]]{8})}} {{2823|e803}}0000 00000000 {{(.{16})}} + +; CHECK-NO-BP-SEC: warning: '{{.*}}': could not find section '.branch_probabilities'