LLVM 17.0.0git
AddDiscriminators.cpp
Go to the documentation of this file.
1//===- AddDiscriminators.cpp - Insert DWARF path discriminators -----------===//
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 adds DWARF discriminators to the IR. Path discriminators are
10// used to decide what CFG path was taken inside sub-graphs whose instructions
11// share the same line and column number information.
12//
13// The main user of this is the sample profiler. Instruction samples are
14// mapped to line number information. Since a single line may be spread
15// out over several basic blocks, discriminators add more precise location
16// for the samples.
17//
18// For example,
19//
20// 1 #define ASSERT(P)
21// 2 if (!(P))
22// 3 abort()
23// ...
24// 100 while (true) {
25// 101 ASSERT (sum < 0);
26// 102 ...
27// 130 }
28//
29// when converted to IR, this snippet looks something like:
30//
31// while.body: ; preds = %entry, %if.end
32// %0 = load i32* %sum, align 4, !dbg !15
33// %cmp = icmp slt i32 %0, 0, !dbg !15
34// br i1 %cmp, label %if.end, label %if.then, !dbg !15
35//
36// if.then: ; preds = %while.body
37// call void @abort(), !dbg !15
38// br label %if.end, !dbg !15
39//
40// Notice that all the instructions in blocks 'while.body' and 'if.then'
41// have exactly the same debug information. When this program is sampled
42// at runtime, the profiler will assume that all these instructions are
43// equally frequent. This, in turn, will consider the edge while.body->if.then
44// to be frequently taken (which is incorrect).
45//
46// By adding a discriminator value to the instructions in block 'if.then',
47// we can distinguish instructions at line 101 with discriminator 0 from
48// the instructions at line 101 with discriminator 1.
49//
50// For more details about DWARF discriminators, please visit
51// http://wiki.dwarfstd.org/index.php?title=Path_Discriminators
52//
53//===----------------------------------------------------------------------===//
54
56#include "llvm/ADT/DenseMap.h"
57#include "llvm/ADT/DenseSet.h"
58#include "llvm/ADT/StringRef.h"
59#include "llvm/IR/BasicBlock.h"
61#include "llvm/IR/Function.h"
62#include "llvm/IR/Instruction.h"
65#include "llvm/IR/PassManager.h"
67#include "llvm/Pass.h"
70#include "llvm/Support/Debug.h"
74#include <utility>
75
76using namespace llvm;
77using namespace sampleprofutil;
78
79#define DEBUG_TYPE "add-discriminators"
80
81// Command line option to disable discriminator generation even in the
82// presence of debug information. This is only needed when debugging
83// debug info generation issues.
85 "no-discriminators", cl::init(false),
86 cl::desc("Disable generation of discriminator information."));
87
88namespace {
89
90// The legacy pass of AddDiscriminators.
91struct AddDiscriminatorsLegacyPass : public FunctionPass {
92 static char ID; // Pass identification, replacement for typeid
93
94 AddDiscriminatorsLegacyPass() : FunctionPass(ID) {
96 }
97
98 bool runOnFunction(Function &F) override;
99};
100
101} // end anonymous namespace
102
103char AddDiscriminatorsLegacyPass::ID = 0;
104
105INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators",
106 "Add DWARF path discriminators", false, false)
107INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators",
109
110// Create the legacy AddDiscriminatorsPass.
112 return new AddDiscriminatorsLegacyPass();
113}
114
116 return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I);
117}
118
119/// Assign DWARF discriminators.
120///
121/// To assign discriminators, we examine the boundaries of every
122/// basic block and its successors. Suppose there is a basic block B1
123/// with successor B2. The last instruction I1 in B1 and the first
124/// instruction I2 in B2 are located at the same file and line number.
125/// This situation is illustrated in the following code snippet:
126///
127/// if (i < 10) x = i;
128///
129/// entry:
130/// br i1 %cmp, label %if.then, label %if.end, !dbg !10
131/// if.then:
132/// %1 = load i32* %i.addr, align 4, !dbg !10
133/// store i32 %1, i32* %x, align 4, !dbg !10
134/// br label %if.end, !dbg !10
135/// if.end:
136/// ret void, !dbg !12
137///
138/// Notice how the branch instruction in block 'entry' and all the
139/// instructions in block 'if.then' have the exact same debug location
140/// information (!dbg !10).
141///
142/// To distinguish instructions in block 'entry' from instructions in
143/// block 'if.then', we generate a new lexical block for all the
144/// instruction in block 'if.then' that share the same file and line
145/// location with the last instruction of block 'entry'.
146///
147/// This new lexical block will have the same location information as
148/// the previous one, but with a new DWARF discriminator value.
149///
150/// One of the main uses of this discriminator value is in runtime
151/// sample profilers. It allows the profiler to distinguish instructions
152/// at location !dbg !10 that execute on different basic blocks. This is
153/// important because while the predicate 'if (x < 10)' may have been
154/// executed millions of times, the assignment 'x = i' may have only
155/// executed a handful of times (meaning that the entry->if.then edge is
156/// seldom taken).
157///
158/// If we did not have discriminator information, the profiler would
159/// assign the same weight to both blocks 'entry' and 'if.then', which
160/// in turn will make it conclude that the entry->if.then edge is very
161/// hot.
162///
163/// To decide where to create new discriminator values, this function
164/// traverses the CFG and examines instruction at basic block boundaries.
165/// If the last instruction I1 of a block B1 is at the same file and line
166/// location as instruction I2 of successor B2, then it creates a new
167/// lexical block for I2 and all the instruction in B2 that share the same
168/// file and line location as I2. This new lexical block will have a
169/// different discriminator number than I1.
171 // If the function has debug information, but the user has disabled
172 // discriminators, do nothing.
173 // Simlarly, if the function has no debug info, do nothing.
174 if (NoDiscriminators || !F.getSubprogram())
175 return false;
176
177 // Create FSDiscriminatorVariable if flow sensitive discriminators are used.
179 createFSDiscriminatorVariable(F.getParent());
180
181 bool Changed = false;
182
183 using Location = std::pair<StringRef, unsigned>;
184 using BBSet = DenseSet<const BasicBlock *>;
185 using LocationBBMap = DenseMap<Location, BBSet>;
186 using LocationDiscriminatorMap = DenseMap<Location, unsigned>;
187 using LocationSet = DenseSet<Location>;
188
189 LocationBBMap LBM;
190 LocationDiscriminatorMap LDM;
191
192 // Traverse all instructions in the function. If the source line location
193 // of the instruction appears in other basic block, assign a new
194 // discriminator for this instruction.
195 for (BasicBlock &B : F) {
196 for (auto &I : B) {
197 // Not all intrinsic calls should have a discriminator.
198 // We want to avoid a non-deterministic assignment of discriminators at
199 // different debug levels. We still allow discriminators on memory
200 // intrinsic calls because those can be early expanded by SROA into
201 // pairs of loads and stores, and the expanded load/store instructions
202 // should have a valid discriminator.
204 continue;
205 const DILocation *DIL = I.getDebugLoc();
206 if (!DIL)
207 continue;
208 Location L = std::make_pair(DIL->getFilename(), DIL->getLine());
209 auto &BBMap = LBM[L];
210 auto R = BBMap.insert(&B);
211 if (BBMap.size() == 1)
212 continue;
213 // If we could insert more than one block with the same line+file, a
214 // discriminator is needed to distinguish both instructions.
215 // Only the lowest 7 bits are used to represent a discriminator to fit
216 // it in 1 byte ULEB128 representation.
217 unsigned Discriminator = R.second ? ++LDM[L] : LDM[L];
218 auto NewDIL = DIL->cloneWithBaseDiscriminator(Discriminator);
219 if (!NewDIL) {
220 LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
221 << DIL->getFilename() << ":" << DIL->getLine() << ":"
222 << DIL->getColumn() << ":" << Discriminator << " "
223 << I << "\n");
224 } else {
225 I.setDebugLoc(*NewDIL);
226 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
227 << DIL->getColumn() << ":" << Discriminator << " " << I
228 << "\n");
229 }
230 Changed = true;
231 }
232 }
233
234 // Traverse all instructions and assign new discriminators to call
235 // instructions with the same lineno that are in the same basic block.
236 // Sample base profile needs to distinguish different function calls within
237 // a same source line for correct profile annotation.
238 for (BasicBlock &B : F) {
239 LocationSet CallLocations;
240 for (auto &I : B) {
241 // We bypass intrinsic calls for the following two reasons:
242 // 1) We want to avoid a non-deterministic assignment of
243 // discriminators.
244 // 2) We want to minimize the number of base discriminators used.
245 if (!isa<InvokeInst>(I) && (!isa<CallInst>(I) || isa<IntrinsicInst>(I)))
246 continue;
247
248 DILocation *CurrentDIL = I.getDebugLoc();
249 if (!CurrentDIL)
250 continue;
251 Location L =
252 std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine());
253 if (!CallLocations.insert(L).second) {
254 unsigned Discriminator = ++LDM[L];
255 auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(Discriminator);
256 if (!NewDIL) {
258 << "Could not encode discriminator: "
259 << CurrentDIL->getFilename() << ":"
260 << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn()
261 << ":" << Discriminator << " " << I << "\n");
262 } else {
263 I.setDebugLoc(*NewDIL);
264 Changed = true;
265 }
266 }
267 }
268 }
269 return Changed;
270}
271
272bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) {
273 return addDiscriminators(F);
274}
275
278 if (!addDiscriminators(F))
279 return PreservedAnalyses::all();
280
281 // FIXME: should be all()
283}
static cl::opt< bool > NoDiscriminators("no-discriminators", cl::init(false), cl::desc("Disable generation of discriminator information."))
static bool addDiscriminators(Function &F)
Assign DWARF discriminators.
static bool shouldHaveDiscriminator(const Instruction *I)
add discriminators
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file provides the utility functions for the sampled PGO loader base implementation.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Debug location.
std::optional< const DILocation * > cloneWithBaseDiscriminator(unsigned BD) const
Returns a new DILocation with updated base discriminator BD.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
void createFSDiscriminatorVariable(Module *M)
Create a global variable to flag FSDiscriminators are used.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createAddDiscriminatorsPass()
cl::opt< bool > EnableFSDiscriminator
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void initializeAddDiscriminatorsLegacyPassPass(PassRegistry &)
@ Add
Sum of integers.