1 //===- SampleProfileProbe.cpp - Pseudo probe Instrumentation -------------===//
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 // This file implements the SampleProfileProber transformation.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
14 #include "llvm/ADT/Statistic.h"
15 #include "llvm/Analysis/TargetLibraryInfo.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/CFG.h"
18 #include "llvm/IR/Constant.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DebugInfoMetadata.h"
21 #include "llvm/IR/GlobalValue.h"
22 #include "llvm/IR/GlobalVariable.h"
23 #include "llvm/IR/IRBuilder.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/IR/MDBuilder.h"
26 #include "llvm/ProfileData/SampleProf.h"
27 #include "llvm/Support/CRC.h"
28 #include "llvm/Transforms/Instrumentation.h"
29 #include "llvm/Transforms/Utils/ModuleUtils.h"
30 #include <vector>
31 
32 using namespace llvm;
33 #define DEBUG_TYPE "sample-profile-probe"
34 
35 STATISTIC(ArtificialDbgLine,
36           "Number of probes that have an artificial debug line");
37 
38 SampleProfileProber::SampleProfileProber(Function &Func,
39                                          const std::string &CurModuleUniqueId)
40     : F(&Func), CurModuleUniqueId(CurModuleUniqueId) {
41   BlockProbeIds.clear();
42   CallProbeIds.clear();
43   LastProbeId = (uint32_t)PseudoProbeReservedId::Last;
44   computeProbeIdForBlocks();
45   computeProbeIdForCallsites();
46   computeCFGHash();
47 }
48 
49 // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
50 // value of each BB in the CFG. The higher 32 bits record the number of edges
51 // preceded by the number of indirect calls.
52 // This is derived from FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash().
53 void SampleProfileProber::computeCFGHash() {
54   std::vector<uint8_t> Indexes;
55   JamCRC JC;
56   for (auto &BB : *F) {
57     auto *TI = BB.getTerminator();
58     for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
59       auto *Succ = TI->getSuccessor(I);
60       auto Index = getBlockId(Succ);
61       for (int J = 0; J < 4; J++)
62         Indexes.push_back((uint8_t)(Index >> (J * 8)));
63     }
64   }
65 
66   JC.update(Indexes);
67 
68   FunctionHash = (uint64_t)CallProbeIds.size() << 48 |
69                  (uint64_t)Indexes.size() << 32 | JC.getCRC();
70   // Reserve bit 60-63 for other information purpose.
71   FunctionHash &= 0x0FFFFFFFFFFFFFFF;
72   assert(FunctionHash && "Function checksum should not be zero");
73   LLVM_DEBUG(dbgs() << "\nFunction Hash Computation for " << F->getName()
74                     << ":\n"
75                     << " CRC = " << JC.getCRC() << ", Edges = "
76                     << Indexes.size() << ", ICSites = " << CallProbeIds.size()
77                     << ", Hash = " << FunctionHash << "\n");
78 }
79 
80 void SampleProfileProber::computeProbeIdForBlocks() {
81   for (auto &BB : *F) {
82     BlockProbeIds[&BB] = ++LastProbeId;
83   }
84 }
85 
86 void SampleProfileProber::computeProbeIdForCallsites() {
87   for (auto &BB : *F) {
88     for (auto &I : BB) {
89       if (!isa<CallBase>(I))
90         continue;
91       if (isa<IntrinsicInst>(&I))
92         continue;
93       CallProbeIds[&I] = ++LastProbeId;
94     }
95   }
96 }
97 
98 uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
99   auto I = BlockProbeIds.find(const_cast<BasicBlock *>(BB));
100   return I == BlockProbeIds.end() ? 0 : I->second;
101 }
102 
103 uint32_t SampleProfileProber::getCallsiteId(const Instruction *Call) const {
104   auto Iter = CallProbeIds.find(const_cast<Instruction *>(Call));
105   return Iter == CallProbeIds.end() ? 0 : Iter->second;
106 }
107 
108 void SampleProfileProber::instrumentOneFunc(Function &F, TargetMachine *TM) {
109   Module *M = F.getParent();
110   MDBuilder MDB(F.getContext());
111   // Compute a GUID without considering the function's linkage type. This is
112   // fine since function name is the only key in the profile database.
113   uint64_t Guid = Function::getGUID(F.getName());
114 
115   // Assign an artificial debug line to a probe that doesn't come with a real
116   // line. A probe not having a debug line will get an incomplete inline
117   // context. This will cause samples collected on the probe to be counted
118   // into the base profile instead of a context profile. The line number
119   // itself is not important though.
120   auto AssignDebugLoc = [&](Instruction *I) {
121     assert((isa<PseudoProbeInst>(I) || isa<CallBase>(I)) &&
122            "Expecting pseudo probe or call instructions");
123     if (!I->getDebugLoc()) {
124       if (auto *SP = F.getSubprogram()) {
125         auto DIL = DILocation::get(SP->getContext(), 0, 0, SP);
126         I->setDebugLoc(DIL);
127         ArtificialDbgLine++;
128         LLVM_DEBUG({
129           dbgs() << "\nIn Function " << F.getName()
130                  << " Probe gets an artificial debug line\n";
131           I->dump();
132         });
133       }
134     }
135   };
136 
137   // Probe basic blocks.
138   for (auto &I : BlockProbeIds) {
139     BasicBlock *BB = I.first;
140     uint32_t Index = I.second;
141     // Insert a probe before an instruction with a valid debug line number which
142     // will be assigned to the probe. The line number will be used later to
143     // model the inline context when the probe is inlined into other functions.
144     // Debug instructions, phi nodes and lifetime markers do not have an valid
145     // line number. Real instructions generated by optimizations may not come
146     // with a line number either.
147     auto HasValidDbgLine = [](Instruction *J) {
148       return !isa<PHINode>(J) && !isa<DbgInfoIntrinsic>(J) &&
149              !J->isLifetimeStartOrEnd() && J->getDebugLoc();
150     };
151 
152     Instruction *J = &*BB->getFirstInsertionPt();
153     while (J != BB->getTerminator() && !HasValidDbgLine(J)) {
154       J = J->getNextNode();
155     }
156 
157     IRBuilder<> Builder(J);
158     assert(Builder.GetInsertPoint() != BB->end() &&
159            "Cannot get the probing point");
160     Function *ProbeFn =
161         llvm::Intrinsic::getDeclaration(M, Intrinsic::pseudoprobe);
162     Value *Args[] = {Builder.getInt64(Guid), Builder.getInt64(Index),
163                      Builder.getInt32(0)};
164     auto *Probe = Builder.CreateCall(ProbeFn, Args);
165     AssignDebugLoc(Probe);
166   }
167 
168   // Probe both direct calls and indirect calls. Direct calls are probed so that
169   // their probe ID can be used as an call site identifier to represent a
170   // calling context.
171   for (auto &I : CallProbeIds) {
172     auto *Call = I.first;
173     uint32_t Index = I.second;
174     uint32_t Type = cast<CallBase>(Call)->getCalledFunction()
175                         ? (uint32_t)PseudoProbeType::DirectCall
176                         : (uint32_t)PseudoProbeType::IndirectCall;
177     AssignDebugLoc(Call);
178     // Levarge the 32-bit discriminator field of debug data to store the ID and
179     // type of a callsite probe. This gets rid of the dependency on plumbing a
180     // customized metadata through the codegen pipeline.
181     uint32_t V = PseudoProbeDwarfDiscriminator::packProbeData(Index, Type);
182     if (auto DIL = Call->getDebugLoc()) {
183       DIL = DIL->cloneWithDiscriminator(V);
184       Call->setDebugLoc(DIL);
185     }
186   }
187 
188   // Create module-level metadata that contains function info necessary to
189   // synthesize probe-based sample counts,  which are
190   // - FunctionGUID
191   // - FunctionHash.
192   // - FunctionName
193   auto Hash = getFunctionHash();
194   auto *MD = MDB.createPseudoProbeDesc(Guid, Hash, &F);
195   auto *NMD = M->getNamedMetadata(PseudoProbeDescMetadataName);
196   assert(NMD && "llvm.pseudo_probe_desc should be pre-created");
197   NMD->addOperand(MD);
198 
199   // Preserve a comdat group to hold all probes materialized later. This
200   // allows that when the function is considered dead and removed, the
201   // materialized probes are disposed too.
202   // Imported functions are defined in another module. They do not need
203   // the following handling since same care will be taken for them in their
204   // original module. The pseudo probes inserted into an imported functions
205   // above will naturally not be emitted since the imported function is free
206   // from object emission. However they will be emitted together with the
207   // inliner functions that the imported function is inlined into. We are not
208   // creating a comdat group for an import function since it's useless anyway.
209   if (!F.isDeclarationForLinker()) {
210     if (TM) {
211       auto Triple = TM->getTargetTriple();
212       if (Triple.supportsCOMDAT() && TM->getFunctionSections()) {
213         GetOrCreateFunctionComdat(F, Triple, CurModuleUniqueId);
214       }
215     }
216   }
217 }
218 
219 PreservedAnalyses SampleProfileProbePass::run(Module &M,
220                                               ModuleAnalysisManager &AM) {
221   auto ModuleId = getUniqueModuleId(&M);
222   // Create the pseudo probe desc metadata beforehand.
223   // Note that modules with only data but no functions will require this to
224   // be set up so that they will be known as probed later.
225   M.getOrInsertNamedMetadata(PseudoProbeDescMetadataName);
226 
227   for (auto &F : M) {
228     if (F.isDeclaration())
229       continue;
230     SampleProfileProber ProbeManager(F, ModuleId);
231     ProbeManager.instrumentOneFunc(F, TM);
232   }
233 
234   return PreservedAnalyses::none();
235 }
236