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