1 //===- AddDiscriminators.cpp - Insert DWARF path discriminators -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file adds DWARF discriminators to the IR. Path discriminators are
11 // used to decide what CFG path was taken inside sub-graphs whose instructions
12 // share the same line and column number information.
14 // The main user of this is the sample profiler. Instruction samples are
15 // mapped to line number information. Since a single line may be spread
16 // out over several basic blocks, discriminators add more precise location
21 // 1 #define ASSERT(P)
26 // 101 ASSERT (sum < 0);
30 // when converted to IR, this snippet looks something like:
32 // while.body: ; preds = %entry, %if.end
33 // %0 = load i32* %sum, align 4, !dbg !15
34 // %cmp = icmp slt i32 %0, 0, !dbg !15
35 // br i1 %cmp, label %if.end, label %if.then, !dbg !15
37 // if.then: ; preds = %while.body
38 // call void @abort(), !dbg !15
39 // br label %if.end, !dbg !15
41 // Notice that all the instructions in blocks 'while.body' and 'if.then'
42 // have exactly the same debug information. When this program is sampled
43 // at runtime, the profiler will assume that all these instructions are
44 // equally frequent. This, in turn, will consider the edge while.body->if.then
45 // to be frequently taken (which is incorrect).
47 // By adding a discriminator value to the instructions in block 'if.then',
48 // we can distinguish instructions at line 101 with discriminator 0 from
49 // the instructions at line 101 with discriminator 1.
51 // For more details about DWARF discriminators, please visit
52 // http://wiki.dwarfstd.org/index.php?title=Path_Discriminators
53 //===----------------------------------------------------------------------===//
55 #include "llvm/Transforms/Scalar.h"
56 #include "llvm/IR/BasicBlock.h"
57 #include "llvm/IR/Constants.h"
58 #include "llvm/IR/DIBuilder.h"
59 #include "llvm/IR/DebugInfo.h"
60 #include "llvm/IR/Instructions.h"
61 #include "llvm/IR/IntrinsicInst.h"
62 #include "llvm/IR/LLVMContext.h"
63 #include "llvm/IR/Module.h"
64 #include "llvm/Pass.h"
65 #include "llvm/Support/CommandLine.h"
66 #include "llvm/Support/Debug.h"
67 #include "llvm/Support/raw_ostream.h"
71 #define DEBUG_TYPE "add-discriminators"
74 struct AddDiscriminators : public FunctionPass {
75 static char ID; // Pass identification, replacement for typeid
76 AddDiscriminators() : FunctionPass(ID) {
77 initializeAddDiscriminatorsPass(*PassRegistry::getPassRegistry());
80 bool runOnFunction(Function &F) override;
84 char AddDiscriminators::ID = 0;
85 INITIALIZE_PASS_BEGIN(AddDiscriminators, "add-discriminators",
86 "Add DWARF path discriminators", false, false)
87 INITIALIZE_PASS_END(AddDiscriminators, "add-discriminators",
88 "Add DWARF path discriminators", false, false)
90 // Command line option to disable discriminator generation even in the
91 // presence of debug information. This is only needed when debugging
92 // debug info generation issues.
93 static cl::opt<bool> NoDiscriminators(
94 "no-discriminators", cl::init(false),
95 cl::desc("Disable generation of discriminator information."));
97 FunctionPass *llvm::createAddDiscriminatorsPass() {
98 return new AddDiscriminators();
101 static bool hasDebugInfo(const Function &F) {
102 DISubprogram *S = getDISubprogram(&F);
106 /// \brief Assign DWARF discriminators.
108 /// To assign discriminators, we examine the boundaries of every
109 /// basic block and its successors. Suppose there is a basic block B1
110 /// with successor B2. The last instruction I1 in B1 and the first
111 /// instruction I2 in B2 are located at the same file and line number.
112 /// This situation is illustrated in the following code snippet:
114 /// if (i < 10) x = i;
117 /// br i1 %cmp, label %if.then, label %if.end, !dbg !10
119 /// %1 = load i32* %i.addr, align 4, !dbg !10
120 /// store i32 %1, i32* %x, align 4, !dbg !10
121 /// br label %if.end, !dbg !10
123 /// ret void, !dbg !12
125 /// Notice how the branch instruction in block 'entry' and all the
126 /// instructions in block 'if.then' have the exact same debug location
127 /// information (!dbg !10).
129 /// To distinguish instructions in block 'entry' from instructions in
130 /// block 'if.then', we generate a new lexical block for all the
131 /// instruction in block 'if.then' that share the same file and line
132 /// location with the last instruction of block 'entry'.
134 /// This new lexical block will have the same location information as
135 /// the previous one, but with a new DWARF discriminator value.
137 /// One of the main uses of this discriminator value is in runtime
138 /// sample profilers. It allows the profiler to distinguish instructions
139 /// at location !dbg !10 that execute on different basic blocks. This is
140 /// important because while the predicate 'if (x < 10)' may have been
141 /// executed millions of times, the assignment 'x = i' may have only
142 /// executed a handful of times (meaning that the entry->if.then edge is
145 /// If we did not have discriminator information, the profiler would
146 /// assign the same weight to both blocks 'entry' and 'if.then', which
147 /// in turn will make it conclude that the entry->if.then edge is very
150 /// To decide where to create new discriminator values, this function
151 /// traverses the CFG and examines instruction at basic block boundaries.
152 /// If the last instruction I1 of a block B1 is at the same file and line
153 /// location as instruction I2 of successor B2, then it creates a new
154 /// lexical block for I2 and all the instruction in B2 that share the same
155 /// file and line location as I2. This new lexical block will have a
156 /// different discriminator number than I1.
157 bool AddDiscriminators::runOnFunction(Function &F) {
158 // If the function has debug information, but the user has disabled
159 // discriminators, do nothing.
160 // Simlarly, if the function has no debug info, do nothing.
161 // Finally, if this module is built with dwarf versions earlier than 4,
162 // do nothing (discriminator support is a DWARF 4 feature).
163 if (NoDiscriminators || !hasDebugInfo(F) ||
164 F.getParent()->getDwarfVersion() < 4)
167 bool Changed = false;
168 Module *M = F.getParent();
169 LLVMContext &Ctx = M->getContext();
170 DIBuilder Builder(*M, /*AllowUnresolved*/ false);
172 // Traverse all the blocks looking for instructions in different
173 // blocks that are at the same file:line location.
174 for (BasicBlock &B : F) {
175 TerminatorInst *Last = B.getTerminator();
176 const DILocation *LastDIL = Last->getDebugLoc();
180 for (unsigned I = 0; I < Last->getNumSuccessors(); ++I) {
181 BasicBlock *Succ = Last->getSuccessor(I);
182 Instruction *First = Succ->getFirstNonPHIOrDbgOrLifetime();
183 const DILocation *FirstDIL = First->getDebugLoc();
184 if (!FirstDIL || FirstDIL->getDiscriminator())
187 // If the first instruction (First) of Succ is at the same file
188 // location as B's last instruction (Last), add a new
189 // discriminator for First's location and all the instructions
190 // in Succ that share the same location with First.
191 if (!FirstDIL->canDiscriminate(*LastDIL)) {
192 // Create a new lexical scope and compute a new discriminator
194 StringRef Filename = FirstDIL->getFilename();
195 auto *Scope = FirstDIL->getScope();
196 auto *File = Builder.createFile(Filename, Scope->getDirectory());
198 // FIXME: Calculate the discriminator here, based on local information,
199 // and delete DILocation::computeNewDiscriminator(). The current
200 // solution gives different results depending on other modules in the
201 // same context. All we really need is to discriminate between
202 // FirstDIL and LastDIL -- a local map would suffice.
203 unsigned Discriminator = FirstDIL->computeNewDiscriminator();
205 Builder.createLexicalBlockFile(Scope, File, Discriminator);
207 // Attach this new debug location to First and every
208 // instruction following First that shares the same location.
209 for (BasicBlock::iterator I1(*First), E1 = Succ->end(); I1 != E1;
211 const DILocation *CurrentDIL = I1->getDebugLoc();
212 if (CurrentDIL && CurrentDIL->getLine() == FirstDIL->getLine() &&
213 CurrentDIL->getFilename() == FirstDIL->getFilename()) {
214 I1->setDebugLoc(DILocation::get(Ctx, CurrentDIL->getLine(),
215 CurrentDIL->getColumn(), NewScope,
216 CurrentDIL->getInlinedAt()));
217 DEBUG(dbgs() << CurrentDIL->getFilename() << ":"
218 << CurrentDIL->getLine() << ":"
219 << CurrentDIL->getColumn() << ":"
220 << CurrentDIL->getDiscriminator() << *I1 << "\n");
223 DEBUG(dbgs() << "\n");
229 // Traverse all instructions and assign new discriminators to call
230 // instructions with the same lineno that are in the same basic block.
231 // Sample base profile needs to distinguish different function calls within
232 // a same source line for correct profile annotation.
233 for (BasicBlock &B : F) {
234 const DILocation *FirstDIL = NULL;
235 for (auto &I : B.getInstList()) {
236 CallInst *Current = dyn_cast<CallInst>(&I);
237 if (!Current || isa<DbgInfoIntrinsic>(&I))
240 DILocation *CurrentDIL = Current->getDebugLoc();
242 if (CurrentDIL && CurrentDIL->getLine() == FirstDIL->getLine() &&
243 CurrentDIL->getFilename() == FirstDIL->getFilename()) {
244 auto *Scope = FirstDIL->getScope();
245 auto *File = Builder.createFile(FirstDIL->getFilename(),
246 Scope->getDirectory());
247 auto *NewScope = Builder.createLexicalBlockFile(
248 Scope, File, FirstDIL->computeNewDiscriminator());
249 Current->setDebugLoc(DILocation::get(
250 Ctx, CurrentDIL->getLine(), CurrentDIL->getColumn(), NewScope,
251 CurrentDIL->getInlinedAt()));
254 FirstDIL = CurrentDIL;
257 FirstDIL = CurrentDIL;