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 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:
81   Function *getFunction() const { return F; }
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 computeCFGHash();
86   void computeProbeIdForBlocks();
87   void computeProbeIdForCallsites();
88 
89   Function *F;
90 
91   /// The current module ID that is used to name a static object as a comdat
92   /// group.
93   std::string CurModuleUniqueId;
94 
95   /// A CFG hash code used to identify a function code changes.
96   uint64_t FunctionHash;
97 
98   /// Map basic blocks to the their pseudo probe ids.
99   BlockIdMap BlockProbeIds;
100 
101   /// Map indirect calls to the their pseudo probe ids.
102   InstructionIdMap CallProbeIds;
103 
104   /// The ID of the last probe, Can be used to number a new probe.
105   uint32_t LastProbeId;
106 };
107 
108 class SampleProfileProbePass : public PassInfoMixin<SampleProfileProbePass> {
109   TargetMachine *TM;
110 
111 public:
112   SampleProfileProbePass(TargetMachine *TM) : TM(TM) {}
113   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
114 };
115 
116 // Pseudo probe distribution factor updater.
117 // Sample profile annotation can happen in both LTO prelink and postlink. The
118 // postlink-time re-annotation can degrade profile quality because of prelink
119 // code duplication transformation, such as loop unrolling, jump threading,
120 // indirect call promotion etc. As such, samples corresponding to a source
121 // location may be aggregated multiple times in postlink. With a concept of
122 // distribution factor for pseudo probes, samples can be distributed among
123 // duplicated probes reasonable based on the assumption that optimizations
124 // duplicating code well-maintain the branch frequency information (BFI). This
125 // pass updates distribution factors for each pseudo probe at the end of the
126 // prelink pipeline, to reflect an estimated portion of the real execution
127 // count.
128 class PseudoProbeUpdatePass : public PassInfoMixin<PseudoProbeUpdatePass> {
129   void runOnFunction(Function &F, FunctionAnalysisManager &FAM);
130 
131 public:
132   PseudoProbeUpdatePass() = default;
133   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
134 };
135 
136 } // end namespace llvm
137 #endif // LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H
138