1e8d8bef9SDimitry Andric //===- Transforms/IPO/SampleProfileProbe.h ----------*- C++ -*-===// 2e8d8bef9SDimitry Andric // 3e8d8bef9SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4e8d8bef9SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5e8d8bef9SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6e8d8bef9SDimitry Andric // 7e8d8bef9SDimitry Andric //===----------------------------------------------------------------------===// 8e8d8bef9SDimitry Andric // 9e8d8bef9SDimitry Andric /// \file 10e8d8bef9SDimitry Andric /// This file provides the interface for the pseudo probe implementation for 11e8d8bef9SDimitry Andric /// AutoFDO. 12e8d8bef9SDimitry Andric // 13e8d8bef9SDimitry Andric //===----------------------------------------------------------------------===// 14e8d8bef9SDimitry Andric 15e8d8bef9SDimitry Andric #ifndef LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H 16e8d8bef9SDimitry Andric #define LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H 17e8d8bef9SDimitry Andric 18e8d8bef9SDimitry Andric #include "llvm/ADT/DenseMap.h" 19d409305fSDimitry Andric #include "llvm/Analysis/LazyCallGraph.h" 20e8d8bef9SDimitry Andric #include "llvm/IR/PassManager.h" 21e8d8bef9SDimitry Andric #include "llvm/ProfileData/SampleProf.h" 22e8d8bef9SDimitry Andric #include <unordered_map> 23e8d8bef9SDimitry Andric 24e8d8bef9SDimitry Andric namespace llvm { 25*81ad6265SDimitry Andric class Any; 26*81ad6265SDimitry Andric class BasicBlock; 27*81ad6265SDimitry Andric class Function; 28*81ad6265SDimitry Andric class Instruction; 29*81ad6265SDimitry Andric class Loop; 30*81ad6265SDimitry Andric class PassInstrumentationCallbacks; 31*81ad6265SDimitry Andric class TargetMachine; 32e8d8bef9SDimitry Andric 33e8d8bef9SDimitry Andric class Module; 34e8d8bef9SDimitry Andric 35e8d8bef9SDimitry Andric using namespace sampleprof; 36e8d8bef9SDimitry Andric using BlockIdMap = std::unordered_map<BasicBlock *, uint32_t>; 37e8d8bef9SDimitry Andric using InstructionIdMap = std::unordered_map<Instruction *, uint32_t>; 38fe6060f1SDimitry Andric // Map from tuples of Probe id and inline stack hash code to distribution 39fe6060f1SDimitry Andric // factors. 40fe6060f1SDimitry Andric using ProbeFactorMap = std::unordered_map<std::pair<uint64_t, uint64_t>, float, 41fe6060f1SDimitry Andric pair_hash<uint64_t, uint64_t>>; 42d409305fSDimitry Andric using FuncProbeFactorMap = StringMap<ProbeFactorMap>; 43e8d8bef9SDimitry Andric 44e8d8bef9SDimitry Andric enum class PseudoProbeReservedId { Invalid = 0, Last = Invalid }; 45e8d8bef9SDimitry Andric 46e8d8bef9SDimitry Andric class PseudoProbeDescriptor { 47e8d8bef9SDimitry Andric uint64_t FunctionGUID; 48e8d8bef9SDimitry Andric uint64_t FunctionHash; 49e8d8bef9SDimitry Andric 50e8d8bef9SDimitry Andric public: 51e8d8bef9SDimitry Andric PseudoProbeDescriptor(uint64_t GUID, uint64_t Hash) 52e8d8bef9SDimitry Andric : FunctionGUID(GUID), FunctionHash(Hash) {} 53e8d8bef9SDimitry Andric uint64_t getFunctionGUID() const { return FunctionGUID; } 54e8d8bef9SDimitry Andric uint64_t getFunctionHash() const { return FunctionHash; } 55e8d8bef9SDimitry Andric }; 56e8d8bef9SDimitry Andric 57d409305fSDimitry Andric // A pseudo probe verifier that can be run after each IR passes to detect the 58d409305fSDimitry Andric // violation of updating probe factors. In principle, the sum of distribution 59d409305fSDimitry Andric // factor for a probe should be identical before and after a pass. For a 60d409305fSDimitry Andric // function pass, the factor sum for a probe would be typically 100%. 61d409305fSDimitry Andric class PseudoProbeVerifier { 62d409305fSDimitry Andric public: 63d409305fSDimitry Andric void registerCallbacks(PassInstrumentationCallbacks &PIC); 64d409305fSDimitry Andric 65d409305fSDimitry Andric // Implementation of pass instrumentation callbacks for new pass manager. 66d409305fSDimitry Andric void runAfterPass(StringRef PassID, Any IR); 67d409305fSDimitry Andric 68d409305fSDimitry Andric private: 69d409305fSDimitry Andric // Allow a little bias due the rounding to integral factors. 70d409305fSDimitry Andric constexpr static float DistributionFactorVariance = 0.02f; 71d409305fSDimitry Andric // Distribution factors from last pass. 72d409305fSDimitry Andric FuncProbeFactorMap FunctionProbeFactors; 73d409305fSDimitry Andric 74d409305fSDimitry Andric void collectProbeFactors(const BasicBlock *BB, ProbeFactorMap &ProbeFactors); 75d409305fSDimitry Andric void runAfterPass(const Module *M); 76d409305fSDimitry Andric void runAfterPass(const LazyCallGraph::SCC *C); 77d409305fSDimitry Andric void runAfterPass(const Function *F); 78d409305fSDimitry Andric void runAfterPass(const Loop *L); 79d409305fSDimitry Andric bool shouldVerifyFunction(const Function *F); 80d409305fSDimitry Andric void verifyProbeFactors(const Function *F, 81d409305fSDimitry Andric const ProbeFactorMap &ProbeFactors); 82d409305fSDimitry Andric }; 83d409305fSDimitry Andric 84e8d8bef9SDimitry Andric // This class serves sample counts correlation for SampleProfileLoader by 85e8d8bef9SDimitry Andric // analyzing pseudo probes and their function descriptors injected by 86e8d8bef9SDimitry Andric // SampleProfileProber. 87e8d8bef9SDimitry Andric class PseudoProbeManager { 88e8d8bef9SDimitry Andric DenseMap<uint64_t, PseudoProbeDescriptor> GUIDToProbeDescMap; 89e8d8bef9SDimitry Andric 90e8d8bef9SDimitry Andric const PseudoProbeDescriptor *getDesc(const Function &F) const; 91e8d8bef9SDimitry Andric 92e8d8bef9SDimitry Andric public: 93e8d8bef9SDimitry Andric PseudoProbeManager(const Module &M); 94e8d8bef9SDimitry Andric bool moduleIsProbed(const Module &M) const; 95e8d8bef9SDimitry Andric bool profileIsValid(const Function &F, const FunctionSamples &Samples) const; 96e8d8bef9SDimitry Andric }; 97e8d8bef9SDimitry Andric 98e8d8bef9SDimitry Andric /// Sample profile pseudo prober. 99e8d8bef9SDimitry Andric /// 100e8d8bef9SDimitry Andric /// Insert pseudo probes for block sampling and value sampling. 101e8d8bef9SDimitry Andric class SampleProfileProber { 102e8d8bef9SDimitry Andric public: 103e8d8bef9SDimitry Andric // Give an empty module id when the prober is not used for instrumentation. 104e8d8bef9SDimitry Andric SampleProfileProber(Function &F, const std::string &CurModuleUniqueId); 105e8d8bef9SDimitry Andric void instrumentOneFunc(Function &F, TargetMachine *TM); 106e8d8bef9SDimitry Andric 107e8d8bef9SDimitry Andric private: 108e8d8bef9SDimitry Andric Function *getFunction() const { return F; } 109e8d8bef9SDimitry Andric uint64_t getFunctionHash() const { return FunctionHash; } 110e8d8bef9SDimitry Andric uint32_t getBlockId(const BasicBlock *BB) const; 111e8d8bef9SDimitry Andric uint32_t getCallsiteId(const Instruction *Call) const; 112e8d8bef9SDimitry Andric void computeCFGHash(); 113e8d8bef9SDimitry Andric void computeProbeIdForBlocks(); 114e8d8bef9SDimitry Andric void computeProbeIdForCallsites(); 115e8d8bef9SDimitry Andric 116e8d8bef9SDimitry Andric Function *F; 117e8d8bef9SDimitry Andric 118e8d8bef9SDimitry Andric /// The current module ID that is used to name a static object as a comdat 119e8d8bef9SDimitry Andric /// group. 120e8d8bef9SDimitry Andric std::string CurModuleUniqueId; 121e8d8bef9SDimitry Andric 122e8d8bef9SDimitry Andric /// A CFG hash code used to identify a function code changes. 123e8d8bef9SDimitry Andric uint64_t FunctionHash; 124e8d8bef9SDimitry Andric 125e8d8bef9SDimitry Andric /// Map basic blocks to the their pseudo probe ids. 126e8d8bef9SDimitry Andric BlockIdMap BlockProbeIds; 127e8d8bef9SDimitry Andric 128e8d8bef9SDimitry Andric /// Map indirect calls to the their pseudo probe ids. 129e8d8bef9SDimitry Andric InstructionIdMap CallProbeIds; 130e8d8bef9SDimitry Andric 131e8d8bef9SDimitry Andric /// The ID of the last probe, Can be used to number a new probe. 132e8d8bef9SDimitry Andric uint32_t LastProbeId; 133e8d8bef9SDimitry Andric }; 134e8d8bef9SDimitry Andric 135e8d8bef9SDimitry Andric class SampleProfileProbePass : public PassInfoMixin<SampleProfileProbePass> { 136e8d8bef9SDimitry Andric TargetMachine *TM; 137e8d8bef9SDimitry Andric 138e8d8bef9SDimitry Andric public: 139e8d8bef9SDimitry Andric SampleProfileProbePass(TargetMachine *TM) : TM(TM) {} 140e8d8bef9SDimitry Andric PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 141e8d8bef9SDimitry Andric }; 142e8d8bef9SDimitry Andric 143fe6060f1SDimitry Andric // Pseudo probe distribution factor updater. 144fe6060f1SDimitry Andric // Sample profile annotation can happen in both LTO prelink and postlink. The 145fe6060f1SDimitry Andric // postlink-time re-annotation can degrade profile quality because of prelink 146fe6060f1SDimitry Andric // code duplication transformation, such as loop unrolling, jump threading, 147fe6060f1SDimitry Andric // indirect call promotion etc. As such, samples corresponding to a source 148fe6060f1SDimitry Andric // location may be aggregated multiple times in postlink. With a concept of 149fe6060f1SDimitry Andric // distribution factor for pseudo probes, samples can be distributed among 150fe6060f1SDimitry Andric // duplicated probes reasonable based on the assumption that optimizations 151fe6060f1SDimitry Andric // duplicating code well-maintain the branch frequency information (BFI). This 152fe6060f1SDimitry Andric // pass updates distribution factors for each pseudo probe at the end of the 153fe6060f1SDimitry Andric // prelink pipeline, to reflect an estimated portion of the real execution 154fe6060f1SDimitry Andric // count. 155d409305fSDimitry Andric class PseudoProbeUpdatePass : public PassInfoMixin<PseudoProbeUpdatePass> { 156d409305fSDimitry Andric void runOnFunction(Function &F, FunctionAnalysisManager &FAM); 157d409305fSDimitry Andric 158d409305fSDimitry Andric public: 1591fd87a68SDimitry Andric PseudoProbeUpdatePass() = default; 160d409305fSDimitry Andric PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 161d409305fSDimitry Andric }; 162d409305fSDimitry Andric 163e8d8bef9SDimitry Andric } // end namespace llvm 164e8d8bef9SDimitry Andric #endif // LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H 165