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