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
25namespace llvm {
26class BasicBlock;
27class Function;
28class Instruction;
29class Loop;
30class PassInstrumentationCallbacks;
31class TargetMachine;
32
33class Module;
34
35using namespace sampleprof;
36using BlockIdMap = std::unordered_map<BasicBlock *, uint32_t>;
37using InstructionIdMap = std::unordered_map<Instruction *, uint32_t>;
38// Map from tuples of Probe id and inline stack hash code to distribution
39// factors.
40using ProbeFactorMap = std::unordered_map<std::pair<uint64_t, uint64_t>, float,
41 pair_hash<uint64_t, uint64_t>>;
42using 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%.
49class PseudoProbeVerifier {
50public:
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
56private:
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.
75class SampleProfileProber {
76public:
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
81private:
82 Function *getFunction() const { return F; }
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
116class SampleProfileProbePass : public PassInfoMixin<SampleProfileProbePass> {
117 TargetMachine *TM;
118
119public:
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.
136class PseudoProbeUpdatePass : public PassInfoMixin<PseudoProbeUpdatePass> {
137 void runOnFunction(Function &F, FunctionAnalysisManager &FAM);
138
139public:
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