1 //===- AddDiscriminators.cpp - Insert DWARF path discriminators -----------===//
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
7 //===----------------------------------------------------------------------===//
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.
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
20 // 1 #define ASSERT(P)
25 // 101 ASSERT (sum < 0);
29 // when converted to IR, this snippet looks something like:
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
36 // if.then: ; preds = %while.body
37 // call void @abort(), !dbg !15
38 // br label %if.end, !dbg !15
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).
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.
50 // For more details about DWARF discriminators, please visit
51 // http://wiki.dwarfstd.org/index.php?title=Path_Discriminators
53 //===----------------------------------------------------------------------===//
55 #include "llvm/Transforms/Utils/AddDiscriminators.h"
56 #include "llvm/ADT/DenseMap.h"
57 #include "llvm/ADT/DenseSet.h"
58 #include "llvm/ADT/StringRef.h"
59 #include "llvm/IR/BasicBlock.h"
60 #include "llvm/IR/DebugInfoMetadata.h"
61 #include "llvm/IR/Function.h"
62 #include "llvm/IR/Instruction.h"
63 #include "llvm/IR/Instructions.h"
64 #include "llvm/IR/IntrinsicInst.h"
65 #include "llvm/IR/PassManager.h"
66 #include "llvm/InitializePasses.h"
67 #include "llvm/Pass.h"
68 #include "llvm/Support/Casting.h"
69 #include "llvm/Support/CommandLine.h"
70 #include "llvm/Support/Debug.h"
71 #include "llvm/Support/raw_ostream.h"
72 #include "llvm/Transforms/Utils.h"
77 #define DEBUG_TYPE "add-discriminators"
79 // Command line option to disable discriminator generation even in the
80 // presence of debug information. This is only needed when debugging
81 // debug info generation issues.
82 static cl::opt<bool> NoDiscriminators(
83 "no-discriminators", cl::init(false),
84 cl::desc("Disable generation of discriminator information."));
88 // The legacy pass of AddDiscriminators.
89 struct AddDiscriminatorsLegacyPass : public FunctionPass {
90 static char ID; // Pass identification, replacement for typeid
92 AddDiscriminatorsLegacyPass() : FunctionPass(ID) {
93 initializeAddDiscriminatorsLegacyPassPass(*PassRegistry::getPassRegistry());
96 bool runOnFunction(Function &F) override;
99 } // end anonymous namespace
101 char AddDiscriminatorsLegacyPass::ID = 0;
103 INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators",
104 "Add DWARF path discriminators", false, false)
105 INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators",
106 "Add DWARF path discriminators", false, false)
108 // Create the legacy AddDiscriminatorsPass.
109 FunctionPass *llvm::createAddDiscriminatorsPass() {
110 return new AddDiscriminatorsLegacyPass();
113 static bool shouldHaveDiscriminator(const Instruction *I) {
114 return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I);
117 /// Assign DWARF discriminators.
119 /// To assign discriminators, we examine the boundaries of every
120 /// basic block and its successors. Suppose there is a basic block B1
121 /// with successor B2. The last instruction I1 in B1 and the first
122 /// instruction I2 in B2 are located at the same file and line number.
123 /// This situation is illustrated in the following code snippet:
125 /// if (i < 10) x = i;
128 /// br i1 %cmp, label %if.then, label %if.end, !dbg !10
130 /// %1 = load i32* %i.addr, align 4, !dbg !10
131 /// store i32 %1, i32* %x, align 4, !dbg !10
132 /// br label %if.end, !dbg !10
134 /// ret void, !dbg !12
136 /// Notice how the branch instruction in block 'entry' and all the
137 /// instructions in block 'if.then' have the exact same debug location
138 /// information (!dbg !10).
140 /// To distinguish instructions in block 'entry' from instructions in
141 /// block 'if.then', we generate a new lexical block for all the
142 /// instruction in block 'if.then' that share the same file and line
143 /// location with the last instruction of block 'entry'.
145 /// This new lexical block will have the same location information as
146 /// the previous one, but with a new DWARF discriminator value.
148 /// One of the main uses of this discriminator value is in runtime
149 /// sample profilers. It allows the profiler to distinguish instructions
150 /// at location !dbg !10 that execute on different basic blocks. This is
151 /// important because while the predicate 'if (x < 10)' may have been
152 /// executed millions of times, the assignment 'x = i' may have only
153 /// executed a handful of times (meaning that the entry->if.then edge is
156 /// If we did not have discriminator information, the profiler would
157 /// assign the same weight to both blocks 'entry' and 'if.then', which
158 /// in turn will make it conclude that the entry->if.then edge is very
161 /// To decide where to create new discriminator values, this function
162 /// traverses the CFG and examines instruction at basic block boundaries.
163 /// If the last instruction I1 of a block B1 is at the same file and line
164 /// location as instruction I2 of successor B2, then it creates a new
165 /// lexical block for I2 and all the instruction in B2 that share the same
166 /// file and line location as I2. This new lexical block will have a
167 /// different discriminator number than I1.
168 static bool addDiscriminators(Function &F) {
169 // If the function has debug information, but the user has disabled
170 // discriminators, do nothing.
171 // Simlarly, if the function has no debug info, do nothing.
172 if (NoDiscriminators || !F.getSubprogram())
175 bool Changed = false;
177 using Location = std::pair<StringRef, unsigned>;
178 using BBSet = DenseSet<const BasicBlock *>;
179 using LocationBBMap = DenseMap<Location, BBSet>;
180 using LocationDiscriminatorMap = DenseMap<Location, unsigned>;
181 using LocationSet = DenseSet<Location>;
184 LocationDiscriminatorMap LDM;
186 // Traverse all instructions in the function. If the source line location
187 // of the instruction appears in other basic block, assign a new
188 // discriminator for this instruction.
189 for (BasicBlock &B : F) {
190 for (auto &I : B.getInstList()) {
191 // Not all intrinsic calls should have a discriminator.
192 // We want to avoid a non-deterministic assignment of discriminators at
193 // different debug levels. We still allow discriminators on memory
194 // intrinsic calls because those can be early expanded by SROA into
195 // pairs of loads and stores, and the expanded load/store instructions
196 // should have a valid discriminator.
197 if (!shouldHaveDiscriminator(&I))
199 const DILocation *DIL = I.getDebugLoc();
202 Location L = std::make_pair(DIL->getFilename(), DIL->getLine());
203 auto &BBMap = LBM[L];
204 auto R = BBMap.insert(&B);
205 if (BBMap.size() == 1)
207 // If we could insert more than one block with the same line+file, a
208 // discriminator is needed to distinguish both instructions.
209 // Only the lowest 7 bits are used to represent a discriminator to fit
210 // it in 1 byte ULEB128 representation.
211 unsigned Discriminator = R.second ? ++LDM[L] : LDM[L];
212 auto NewDIL = DIL->cloneWithBaseDiscriminator(Discriminator);
214 LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
215 << DIL->getFilename() << ":" << DIL->getLine() << ":"
216 << DIL->getColumn() << ":" << Discriminator << " "
219 I.setDebugLoc(NewDIL.getValue());
220 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
221 << DIL->getColumn() << ":" << Discriminator << " " << I
228 // Traverse all instructions and assign new discriminators to call
229 // instructions with the same lineno that are in the same basic block.
230 // Sample base profile needs to distinguish different function calls within
231 // a same source line for correct profile annotation.
232 for (BasicBlock &B : F) {
233 LocationSet CallLocations;
234 for (auto &I : B.getInstList()) {
235 // We bypass intrinsic calls for the following two reasons:
236 // 1) We want to avoid a non-deterministic assignment of
238 // 2) We want to minimize the number of base discriminators used.
239 if (!isa<InvokeInst>(I) && (!isa<CallInst>(I) || isa<IntrinsicInst>(I)))
242 DILocation *CurrentDIL = I.getDebugLoc();
246 std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine());
247 if (!CallLocations.insert(L).second) {
248 unsigned Discriminator = ++LDM[L];
249 auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(Discriminator);
252 << "Could not encode discriminator: "
253 << CurrentDIL->getFilename() << ":"
254 << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn()
255 << ":" << Discriminator << " " << I << "\n");
257 I.setDebugLoc(NewDIL.getValue());
266 bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) {
267 return addDiscriminators(F);
270 PreservedAnalyses AddDiscriminatorsPass::run(Function &F,
271 FunctionAnalysisManager &AM) {
272 if (!addDiscriminators(F))
273 return PreservedAnalyses::all();
275 // FIXME: should be all()
276 return PreservedAnalyses::none();