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/Analysis/LazyCallGraph.h" 19 #include "llvm/IR/PassInstrumentation.h" 20 #include "llvm/IR/PassManager.h" 21 #include "llvm/ProfileData/SampleProf.h" 22 #include "llvm/Support/Compiler.h" 23 #include <unordered_map> 24 25 namespace llvm { 26 class BasicBlock; 27 class Function; 28 class Instruction; 29 class Loop; 30 class PassInstrumentationCallbacks; 31 class TargetMachine; 32 33 class Module; 34 35 using namespace sampleprof; 36 using BlockIdMap = std::unordered_map<BasicBlock *, uint32_t>; 37 using InstructionIdMap = std::unordered_map<Instruction *, uint32_t>; 38 // Map from tuples of Probe id and inline stack hash code to distribution 39 // factors. 40 using ProbeFactorMap = std::unordered_map<std::pair<uint64_t, uint64_t>, float, 41 pair_hash<uint64_t, uint64_t>>; 42 using FuncProbeFactorMap = StringMap<ProbeFactorMap>; 43 44 45 // A pseudo probe verifier that can be run after each IR passes to detect the 46 // violation of updating probe factors. In principle, the sum of distribution 47 // factor for a probe should be identical before and after a pass. For a 48 // function pass, the factor sum for a probe would be typically 100%. 49 class PseudoProbeVerifier { 50 public: 51 LLVM_ABI void registerCallbacks(PassInstrumentationCallbacks &PIC); 52 53 // Implementation of pass instrumentation callbacks for new pass manager. 54 LLVM_ABI void runAfterPass(StringRef PassID, Any IR); 55 56 private: 57 // Allow a little bias due the rounding to integral factors. 58 constexpr static float DistributionFactorVariance = 0.02f; 59 // Distribution factors from last pass. 60 FuncProbeFactorMap FunctionProbeFactors; 61 62 void collectProbeFactors(const BasicBlock *BB, ProbeFactorMap &ProbeFactors); 63 void runAfterPass(const Module *M); 64 void runAfterPass(const LazyCallGraph::SCC *C); 65 void runAfterPass(const Function *F); 66 void runAfterPass(const Loop *L); 67 bool shouldVerifyFunction(const Function *F); 68 void verifyProbeFactors(const Function *F, 69 const ProbeFactorMap &ProbeFactors); 70 }; 71 72 /// Sample profile pseudo prober. 73 /// 74 /// Insert pseudo probes for block sampling and value sampling. 75 class SampleProfileProber { 76 public: 77 // Give an empty module id when the prober is not used for instrumentation. 78 LLVM_ABI SampleProfileProber(Function &F); 79 LLVM_ABI void instrumentOneFunc(Function &F, TargetMachine *TM); 80 81 private: getFunction()82 Function *getFunction() const { return F; } getFunctionHash()83 uint64_t getFunctionHash() const { return FunctionHash; } 84 uint32_t getBlockId(const BasicBlock *BB) const; 85 uint32_t getCallsiteId(const Instruction *Call) const; 86 void findUnreachableBlocks(DenseSet<BasicBlock *> &BlocksToIgnore); 87 void findInvokeNormalDests(DenseSet<BasicBlock *> &InvokeNormalDests); 88 void computeBlocksToIgnore(DenseSet<BasicBlock *> &BlocksToIgnore, 89 DenseSet<BasicBlock *> &BlocksAndCallsToIgnore); 90 const Instruction * 91 getOriginalTerminator(const BasicBlock *Head, 92 const DenseSet<BasicBlock *> &BlocksToIgnore); 93 void computeCFGHash(const DenseSet<BasicBlock *> &BlocksToIgnore); 94 void computeProbeId(const DenseSet<BasicBlock *> &BlocksToIgnore, 95 const DenseSet<BasicBlock *> &BlocksAndCallsToIgnore); 96 97 Function *F; 98 99 /// The current module ID that is used to name a static object as a comdat 100 /// group. 101 std::string CurModuleUniqueId; 102 103 /// A CFG hash code used to identify a function code changes. 104 uint64_t FunctionHash; 105 106 /// Map basic blocks to the their pseudo probe ids. 107 BlockIdMap BlockProbeIds; 108 109 /// Map indirect calls to the their pseudo probe ids. 110 InstructionIdMap CallProbeIds; 111 112 /// The ID of the last probe, Can be used to number a new probe. 113 uint32_t LastProbeId; 114 }; 115 116 class SampleProfileProbePass : public PassInfoMixin<SampleProfileProbePass> { 117 TargetMachine *TM; 118 119 public: SampleProfileProbePass(TargetMachine * TM)120 SampleProfileProbePass(TargetMachine *TM) : TM(TM) {} 121 LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 122 }; 123 124 // Pseudo probe distribution factor updater. 125 // Sample profile annotation can happen in both LTO prelink and postlink. The 126 // postlink-time re-annotation can degrade profile quality because of prelink 127 // code duplication transformation, such as loop unrolling, jump threading, 128 // indirect call promotion etc. As such, samples corresponding to a source 129 // location may be aggregated multiple times in postlink. With a concept of 130 // distribution factor for pseudo probes, samples can be distributed among 131 // duplicated probes reasonable based on the assumption that optimizations 132 // duplicating code well-maintain the branch frequency information (BFI). This 133 // pass updates distribution factors for each pseudo probe at the end of the 134 // prelink pipeline, to reflect an estimated portion of the real execution 135 // count. 136 class PseudoProbeUpdatePass : public PassInfoMixin<PseudoProbeUpdatePass> { 137 void runOnFunction(Function &F, FunctionAnalysisManager &FAM); 138 139 public: 140 PseudoProbeUpdatePass() = default; 141 LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 142 }; 143 144 } // end namespace llvm 145 #endif // LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H 146