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