//===- PGOInstrumentation.cpp - MST-based PGO Instrumentation -------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file implements PGO instrumentation using a minimum spanning tree based // on the following paper: // [1] Donald E. Knuth, Francis R. Stevenson. Optimal measurement of points // for program frequency counts. BIT Numerical Mathematics 1973, Volume 13, // Issue 3, pp 313-322 // The idea of the algorithm based on the fact that for each node (except for // the entry and exit), the sum of incoming edge counts equals the sum of // outgoing edge counts. The count of edge on spanning tree can be derived from // those edges not on the spanning tree. Knuth proves this method instruments // the minimum number of edges. // // The minimal spanning tree here is actually a maximum weight tree -- on-tree // edges have higher frequencies (more likely to execute). The idea is to // instrument those less frequently executed edges to reduce the runtime // overhead of instrumented binaries. // // This file contains two passes: // (1) Pass PGOInstrumentationGen which instruments the IR to generate edge // count profile, and generates the instrumentation for indirect call // profiling. // (2) Pass PGOInstrumentationUse which reads the edge count profile and // annotates the branch weights. It also reads the indirect call value // profiling records and annotate the indirect call instructions. // // To get the precise counter information, These two passes need to invoke at // the same compilation point (so they see the same IR). For pass // PGOInstrumentationGen, the real work is done in instrumentOneFunc(). For // pass PGOInstrumentationUse, the real work in done in class PGOUseFunc and // the profile is opened in module level and passed to each PGOUseFunc instance. // The shared code for PGOInstrumentationGen and PGOInstrumentationUse is put // in class FuncPGOInstrumentation. // // Class PGOEdge represents a CFG edge and some auxiliary information. Class // BBInfo contains auxiliary information for each BB. These two classes are used // in pass PGOInstrumentationGen. Class PGOUseEdge and UseBBInfo are the derived // class of PGOEdge and BBInfo, respectively. They contains extra data structure // used in populating profile counters. // The MST implementation is in Class CFGMST (CFGMST.h). // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h" #include "ValueProfileCollector.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Twine.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Comdat.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/EHPersonalities.h" #include "llvm/IR/Function.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalValue.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstVisitor.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/ProfDataUtils.h" #include "llvm/IR/ProfileSummary.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" #include "llvm/ProfileData/InstrProf.h" #include "llvm/ProfileData/InstrProfReader.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/CRC.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/DOTGraphTraits.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Error.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GraphWriter.h" #include "llvm/Support/VirtualFileSystem.h" #include "llvm/Support/raw_ostream.h" #include "llvm/TargetParser/Triple.h" #include "llvm/Transforms/Instrumentation/BlockCoverageInference.h" #include "llvm/Transforms/Instrumentation/CFGMST.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Instrumentation.h" #include "llvm/Transforms/Utils/MisExpect.h" #include "llvm/Transforms/Utils/ModuleUtils.h" #include <algorithm> #include <cassert> #include <cstdint> #include <memory> #include <numeric> #include <optional> #include <stack> #include <string> #include <unordered_map> #include <utility> #include <vector> usingnamespacellvm; ProfileCount; VPCandidateInfo; #define DEBUG_TYPE … STATISTIC(NumOfPGOInstrument, "Number of edges instrumented."); STATISTIC(NumOfPGOSelectInsts, "Number of select instruction instrumented."); STATISTIC(NumOfPGOMemIntrinsics, "Number of mem intrinsics instrumented."); STATISTIC(NumOfPGOEdge, "Number of edges."); STATISTIC(NumOfPGOBB, "Number of basic-blocks."); STATISTIC(NumOfPGOSplit, "Number of critical edge splits."); STATISTIC(NumOfPGOFunc, "Number of functions having valid profile counts."); STATISTIC(NumOfPGOMismatch, "Number of functions having mismatch profile."); STATISTIC(NumOfPGOMissing, "Number of functions without profile."); STATISTIC(NumOfPGOICall, "Number of indirect call value instrumentations."); STATISTIC(NumOfCSPGOInstrument, "Number of edges instrumented in CSPGO."); STATISTIC(NumOfCSPGOSelectInsts, "Number of select instruction instrumented in CSPGO."); STATISTIC(NumOfCSPGOMemIntrinsics, "Number of mem intrinsics instrumented in CSPGO."); STATISTIC(NumOfCSPGOEdge, "Number of edges in CSPGO."); STATISTIC(NumOfCSPGOBB, "Number of basic-blocks in CSPGO."); STATISTIC(NumOfCSPGOSplit, "Number of critical edge splits in CSPGO."); STATISTIC(NumOfCSPGOFunc, "Number of functions having valid profile counts in CSPGO."); STATISTIC(NumOfCSPGOMismatch, "Number of functions having mismatch profile in CSPGO."); STATISTIC(NumOfCSPGOMissing, "Number of functions without profile in CSPGO."); STATISTIC(NumCoveredBlocks, "Number of basic blocks that were executed"); // Command line option to specify the file to read profile from. This is // mainly used for testing. static cl::opt<std::string> PGOTestProfileFile("pgo-test-profile-file", cl::init(""), cl::Hidden, cl::value_desc("filename"), cl::desc("Specify the path of profile data file. This is" "mainly for test purpose.")); static cl::opt<std::string> PGOTestProfileRemappingFile( "pgo-test-profile-remapping-file", cl::init(""), cl::Hidden, cl::value_desc("filename"), cl::desc("Specify the path of profile remapping file. This is mainly for " "test purpose.")); // Command line option to disable value profiling. The default is false: // i.e. value profiling is enabled by default. This is for debug purpose. static cl::opt<bool> DisableValueProfiling("disable-vp", cl::init(false), cl::Hidden, cl::desc("Disable Value Profiling")); // Command line option to set the maximum number of VP annotations to write to // the metadata for a single indirect call callsite. static cl::opt<unsigned> MaxNumAnnotations( "icp-max-annotations", cl::init(3), cl::Hidden, cl::desc("Max number of annotations for a single indirect " "call callsite")); // Command line option to set the maximum number of value annotations // to write to the metadata for a single memop intrinsic. static cl::opt<unsigned> MaxNumMemOPAnnotations( "memop-max-annotations", cl::init(4), cl::Hidden, cl::desc("Max number of preicise value annotations for a single memop" "intrinsic")); // Command line option to control appending FunctionHash to the name of a COMDAT // function. This is to avoid the hash mismatch caused by the preinliner. static cl::opt<bool> DoComdatRenaming( "do-comdat-renaming", cl::init(false), cl::Hidden, cl::desc("Append function hash to the name of COMDAT function to avoid " "function hash mismatch due to the preinliner")); namespace llvm { // Command line option to enable/disable the warning about missing profile // information. cl::opt<bool> PGOWarnMissing("pgo-warn-missing-function", cl::init(false), cl::Hidden, cl::desc("Use this option to turn on/off " "warnings about missing profile data for " "functions.")); // Command line option to enable/disable the warning about a hash mismatch in // the profile data. cl::opt<bool> NoPGOWarnMismatch("no-pgo-warn-mismatch", cl::init(false), cl::Hidden, cl::desc("Use this option to turn off/on " "warnings about profile cfg mismatch.")); // Command line option to enable/disable the warning about a hash mismatch in // the profile data for Comdat functions, which often turns out to be false // positive due to the pre-instrumentation inline. cl::opt<bool> NoPGOWarnMismatchComdatWeak( "no-pgo-warn-mismatch-comdat-weak", cl::init(true), cl::Hidden, cl::desc("The option is used to turn on/off " "warnings about hash mismatch for comdat " "or weak functions.")); } // namespace llvm // Command line option to enable/disable select instruction instrumentation. static cl::opt<bool> PGOInstrSelect("pgo-instr-select", cl::init(true), cl::Hidden, cl::desc("Use this option to turn on/off SELECT " "instruction instrumentation. ")); // Command line option to turn on CFG dot or text dump of raw profile counts static cl::opt<PGOViewCountsType> PGOViewRawCounts( "pgo-view-raw-counts", cl::Hidden, cl::desc("A boolean option to show CFG dag or text " "with raw profile counts from " "profile data. See also option " "-pgo-view-counts. To limit graph " "display to only one function, use " "filtering option -view-bfi-func-name."), cl::values(clEnumValN(PGOVCT_None, "none", "do not show."), clEnumValN(PGOVCT_Graph, "graph", "show a graph."), clEnumValN(PGOVCT_Text, "text", "show in text."))); // Command line option to enable/disable memop intrinsic call.size profiling. static cl::opt<bool> PGOInstrMemOP("pgo-instr-memop", cl::init(true), cl::Hidden, cl::desc("Use this option to turn on/off " "memory intrinsic size profiling.")); // Emit branch probability as optimization remarks. static cl::opt<bool> EmitBranchProbability("pgo-emit-branch-prob", cl::init(false), cl::Hidden, cl::desc("When this option is on, the annotated " "branch probability will be emitted as " "optimization remarks: -{Rpass|" "pass-remarks}=pgo-instrumentation")); static cl::opt<bool> PGOInstrumentEntry( "pgo-instrument-entry", cl::init(false), cl::Hidden, cl::desc("Force to instrument function entry basicblock.")); static cl::opt<bool> PGOFunctionEntryCoverage( "pgo-function-entry-coverage", cl::Hidden, cl::desc( "Use this option to enable function entry coverage instrumentation.")); static cl::opt<bool> PGOBlockCoverage( "pgo-block-coverage", cl::desc("Use this option to enable basic block coverage instrumentation")); static cl::opt<bool> PGOViewBlockCoverageGraph("pgo-view-block-coverage-graph", cl::desc("Create a dot file of CFGs with block " "coverage inference information")); static cl::opt<bool> PGOTemporalInstrumentation( "pgo-temporal-instrumentation", cl::desc("Use this option to enable temporal instrumentation")); static cl::opt<bool> PGOFixEntryCount("pgo-fix-entry-count", cl::init(true), cl::Hidden, cl::desc("Fix function entry count in profile use.")); static cl::opt<bool> PGOVerifyHotBFI( "pgo-verify-hot-bfi", cl::init(false), cl::Hidden, cl::desc("Print out the non-match BFI count if a hot raw profile count " "becomes non-hot, or a cold raw profile count becomes hot. " "The print is enabled under -Rpass-analysis=pgo, or " "internal option -pass-remakrs-analysis=pgo.")); static cl::opt<bool> PGOVerifyBFI( "pgo-verify-bfi", cl::init(false), cl::Hidden, cl::desc("Print out mismatched BFI counts after setting profile metadata " "The print is enabled under -Rpass-analysis=pgo, or " "internal option -pass-remakrs-analysis=pgo.")); static cl::opt<unsigned> PGOVerifyBFIRatio( "pgo-verify-bfi-ratio", cl::init(2), cl::Hidden, cl::desc("Set the threshold for pgo-verify-bfi: only print out " "mismatched BFI if the difference percentage is greater than " "this value (in percentage).")); static cl::opt<unsigned> PGOVerifyBFICutoff( "pgo-verify-bfi-cutoff", cl::init(5), cl::Hidden, cl::desc("Set the threshold for pgo-verify-bfi: skip the counts whose " "profile count value is below.")); static cl::opt<std::string> PGOTraceFuncHash( "pgo-trace-func-hash", cl::init("-"), cl::Hidden, cl::value_desc("function name"), cl::desc("Trace the hash of the function with this name.")); static cl::opt<unsigned> PGOFunctionSizeThreshold( "pgo-function-size-threshold", cl::Hidden, cl::desc("Do not instrument functions smaller than this threshold.")); static cl::opt<unsigned> PGOFunctionCriticalEdgeThreshold( "pgo-critical-edge-threshold", cl::init(20000), cl::Hidden, cl::desc("Do not instrument functions with the number of critical edges " " greater than this threshold.")); extern cl::opt<unsigned> MaxNumVTableAnnotations; namespace llvm { // Command line option to turn on CFG dot dump after profile annotation. // Defined in Analysis/BlockFrequencyInfo.cpp: -pgo-view-counts extern cl::opt<PGOViewCountsType> PGOViewCounts; // Command line option to specify the name of the function for CFG dump // Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name= extern cl::opt<std::string> ViewBlockFreqFuncName; // Command line option to enable vtable value profiling. Defined in // ProfileData/InstrProf.cpp: -enable-vtable-value-profiling= extern cl::opt<bool> EnableVTableValueProfiling; extern cl::opt<bool> EnableVTableProfileUse; extern cl::opt<InstrProfCorrelator::ProfCorrelatorKind> ProfileCorrelate; } // namespace llvm namespace { class FunctionInstrumenter final { … }; } // namespace // Return a string describing the branch condition that can be // used in static branch probability heuristics: static std::string getBranchCondString(Instruction *TI) { … } static const char *ValueProfKindDescr[] = …; // Create a COMDAT variable INSTR_PROF_RAW_VERSION_VAR to make the runtime // aware this is an ir_level profile so it can set the version flag. static GlobalVariable * createIRLevelProfileFlagVar(Module &M, PGOInstrumentationType InstrumentationType) { … } namespace { /// The select instruction visitor plays three roles specified /// by the mode. In \c VM_counting mode, it simply counts the number of /// select instructions. In \c VM_instrument mode, it inserts code to count /// the number times TrueValue of select is taken. In \c VM_annotate mode, /// it reads the profile data and annotate the select instruction with metadata. enum VisitMode { … }; class PGOUseFunc; /// Instruction Visitor class to visit select instructions. struct SelectInstVisitor : public InstVisitor<SelectInstVisitor> { … }; /// This class implements the CFG edges for the Minimum Spanning Tree (MST) /// based instrumentation. /// Note that the CFG can be a multi-graph. So there might be multiple edges /// with the same SrcBB and DestBB. struct PGOEdge { … }; /// This class stores the auxiliary information for each BB in the MST. struct PGOBBInfo { … }; // This class implements the CFG edges. Note the CFG can be a multi-graph. template <class Edge, class BBInfo> class FuncPGOInstrumentation { … }; } // end anonymous namespace // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index // value of each BB in the CFG. The higher 32 bits are the CRC32 of the numbers // of selects, indirect calls, mem ops and edges. template <class Edge, class BBInfo> void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() { … } // Check if we can safely rename this Comdat function. static bool canRenameComdat( Function &F, std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) { … } // Append the CFGHash to the Comdat function name. template <class Edge, class BBInfo> void FuncPGOInstrumentation<Edge, BBInfo>::renameComdatFunction() { … } /// Collect all the BBs that will be instruments and add them to /// `InstrumentBBs`. template <class Edge, class BBInfo> void FuncPGOInstrumentation<Edge, BBInfo>::getInstrumentBBs( std::vector<BasicBlock *> &InstrumentBBs) { … } // Given a CFG E to be instrumented, find which BB to place the instrumented // code. The function will split the critical edge if necessary. template <class Edge, class BBInfo> BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) { … } // When generating value profiling calls on Windows routines that make use of // handler funclets for exception processing an operand bundle needs to attached // to the called function. This routine will set \p OpBundles to contain the // funclet information, if any is needed, that should be placed on the generated // value profiling call for the value profile candidate call. static void populateEHOperandBundle(VPCandidateInfo &Cand, DenseMap<BasicBlock *, ColorVector> &BlockColors, SmallVectorImpl<OperandBundleDef> &OpBundles) { … } // Visit all edge and instrument the edges not in MST, and do value profiling. // Critical edges will be split. void FunctionInstrumenter::instrument() { … } namespace { // This class represents a CFG edge in profile use compilation. struct PGOUseEdge : public PGOEdge { … }; DirectEdges; // This class stores the auxiliary information for each BB. struct PGOUseBBInfo : public PGOBBInfo { … }; } // end anonymous namespace // Sum up the count values for all the edges. static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) { … } namespace { class PGOUseFunc { … }; } // end anonymous namespace /// Set up InEdges/OutEdges for all BBs in the MST. static void setupBBInfoEdges( const FuncPGOInstrumentation<PGOUseEdge, PGOUseBBInfo> &FuncInfo) { … } // Visit all the edges and assign the count value for the instrumented // edges and the BB. Return false on error. bool PGOUseFunc::setInstrumentedCounts( const std::vector<uint64_t> &CountFromProfile) { … } // Set the count value for the unknown edge. There should be one and only one // unknown edge in Edges vector. void PGOUseFunc::setEdgeCount(DirectEdges &Edges, uint64_t Value) { … } // Emit function metadata indicating PGO profile mismatch. static void annotateFunctionWithHashMismatch(Function &F, LLVMContext &ctx) { … } void PGOUseFunc::handleInstrProfError(Error Err, uint64_t MismatchedFuncSum) { … } // Read the profile from ProfileFileName and assign the value to the // instrumented BB and the edges. This function also updates ProgramMaxCount. // Return true if the profile are successfully read, and false on errors. bool PGOUseFunc::readCounters(IndexedInstrProfReader *PGOReader, bool &AllZeros, InstrProfRecord::CountPseudoKind &PseudoKind) { … } void PGOUseFunc::populateCoverage(IndexedInstrProfReader *PGOReader) { … } // Populate the counters from instrumented BBs to all BBs. // In the end of this operation, all BBs should have a valid count value. void PGOUseFunc::populateCounters() { … } // Assign the scaled count values to the BB with multiple out edges. void PGOUseFunc::setBranchWeights() { … } static bool isIndirectBrTarget(BasicBlock *BB) { … } void PGOUseFunc::annotateIrrLoopHeaderWeights() { … } void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) { … } void SelectInstVisitor::annotateOneSelectInst(SelectInst &SI) { … } void SelectInstVisitor::visitSelectInst(SelectInst &SI) { … } static uint32_t getMaxNumAnnotations(InstrProfValueKind ValueProfKind) { … } // Traverse all valuesites and annotate the instructions for all value kind. void PGOUseFunc::annotateValueSites() { … } // Annotate the instructions for a specific value kind. void PGOUseFunc::annotateValueSites(uint32_t Kind) { … } // Collect the set of members for each Comdat in module M and store // in ComdatMembers. static void collectComdatMembers( Module &M, std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) { … } // Return true if we should not find instrumentation data for this function static bool skipPGOUse(const Function &F) { … } // Return true if we should not instrument this function static bool skipPGOGen(const Function &F) { … } static bool InstrumentAllFunctions( Module &M, function_ref<TargetLibraryInfo &(Function &)> LookupTLI, function_ref<BranchProbabilityInfo *(Function &)> LookupBPI, function_ref<BlockFrequencyInfo *(Function &)> LookupBFI, PGOInstrumentationType InstrumentationType) { … } PreservedAnalyses PGOInstrumentationGenCreateVar::run(Module &M, ModuleAnalysisManager &MAM) { … } PreservedAnalyses PGOInstrumentationGen::run(Module &M, ModuleAnalysisManager &MAM) { … } // Using the ratio b/w sums of profile count values and BFI count values to // adjust the func entry count. static void fixFuncEntryCount(PGOUseFunc &Func, LoopInfo &LI, BranchProbabilityInfo &NBPI) { … } // Compare the profile count values with BFI count values, and print out // the non-matching ones. static void verifyFuncBFI(PGOUseFunc &Func, LoopInfo &LI, BranchProbabilityInfo &NBPI, uint64_t HotCountThreshold, uint64_t ColdCountThreshold) { … } static bool annotateAllFunctions( Module &M, StringRef ProfileFileName, StringRef ProfileRemappingFileName, vfs::FileSystem &FS, function_ref<TargetLibraryInfo &(Function &)> LookupTLI, function_ref<BranchProbabilityInfo *(Function &)> LookupBPI, function_ref<BlockFrequencyInfo *(Function &)> LookupBFI, ProfileSummaryInfo *PSI, bool IsCS) { … } PGOInstrumentationUse::PGOInstrumentationUse( std::string Filename, std::string RemappingFilename, bool IsCS, IntrusiveRefCntPtr<vfs::FileSystem> VFS) : … { … } PreservedAnalyses PGOInstrumentationUse::run(Module &M, ModuleAnalysisManager &MAM) { … } static std::string getSimpleNodeName(const BasicBlock *Node) { … } void llvm::setProfMetadata(Module *M, Instruction *TI, ArrayRef<uint64_t> EdgeCounts, uint64_t MaxCount) { … } namespace llvm { void setIrrLoopHeaderMetadata(Module *M, Instruction *TI, uint64_t Count) { … } template <> struct GraphTraits<PGOUseFunc *> { … }; template <> struct DOTGraphTraits<PGOUseFunc *> : DefaultDOTGraphTraits { … }; } // end namespace llvm
Codebase Browser
llvm