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