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
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/Support/Casting.h"
67#include "llvm/Support/CommandLine.h"
68#include "llvm/Support/Debug.h"
69#include "llvm/Support/raw_ostream.h"
70#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
71#include <utility>
72
73using namespace llvm;
74using namespace sampleprofutil;
75
76#define DEBUG_TYPE "add-discriminators"
77
78// Command line option to disable discriminator generation even in the
79// presence of debug information. This is only needed when debugging
80// debug info generation issues.
81static cl::opt<bool> NoDiscriminators(
82 "no-discriminators", cl::init(Val: false),
83 cl::desc("Disable generation of discriminator information."));
84
85static bool shouldHaveDiscriminator(const Instruction *I) {
86 return !isa<IntrinsicInst>(Val: I) || isa<MemIntrinsic>(Val: I);
87}
88
89/// Assign DWARF discriminators.
90///
91/// To assign discriminators, we examine the boundaries of every
92/// basic block and its successors. Suppose there is a basic block B1
93/// with successor B2. The last instruction I1 in B1 and the first
94/// instruction I2 in B2 are located at the same file and line number.
95/// This situation is illustrated in the following code snippet:
96///
97/// if (i < 10) x = i;
98///
99/// entry:
100/// br i1 %cmp, label %if.then, label %if.end, !dbg !10
101/// if.then:
102/// %1 = load i32* %i.addr, align 4, !dbg !10
103/// store i32 %1, i32* %x, align 4, !dbg !10
104/// br label %if.end, !dbg !10
105/// if.end:
106/// ret void, !dbg !12
107///
108/// Notice how the branch instruction in block 'entry' and all the
109/// instructions in block 'if.then' have the exact same debug location
110/// information (!dbg !10).
111///
112/// To distinguish instructions in block 'entry' from instructions in
113/// block 'if.then', we generate a new lexical block for all the
114/// instruction in block 'if.then' that share the same file and line
115/// location with the last instruction of block 'entry'.
116///
117/// This new lexical block will have the same location information as
118/// the previous one, but with a new DWARF discriminator value.
119///
120/// One of the main uses of this discriminator value is in runtime
121/// sample profilers. It allows the profiler to distinguish instructions
122/// at location !dbg !10 that execute on different basic blocks. This is
123/// important because while the predicate 'if (x < 10)' may have been
124/// executed millions of times, the assignment 'x = i' may have only
125/// executed a handful of times (meaning that the entry->if.then edge is
126/// seldom taken).
127///
128/// If we did not have discriminator information, the profiler would
129/// assign the same weight to both blocks 'entry' and 'if.then', which
130/// in turn will make it conclude that the entry->if.then edge is very
131/// hot.
132///
133/// To decide where to create new discriminator values, this function
134/// traverses the CFG and examines instruction at basic block boundaries.
135/// If the last instruction I1 of a block B1 is at the same file and line
136/// location as instruction I2 of successor B2, then it creates a new
137/// lexical block for I2 and all the instruction in B2 that share the same
138/// file and line location as I2. This new lexical block will have a
139/// different discriminator number than I1.
140static bool addDiscriminators(Function &F) {
141 // If the function has debug information, but the user has disabled
142 // discriminators, do nothing.
143 // Simlarly, if the function has no debug info, do nothing.
144 if (NoDiscriminators || !F.getSubprogram())
145 return false;
146
147 // Create FSDiscriminatorVariable if flow sensitive discriminators are used.
148 if (EnableFSDiscriminator)
149 createFSDiscriminatorVariable(M: F.getParent());
150
151 bool Changed = false;
152
153 using Location = std::pair<StringRef, unsigned>;
154 using BBSet = DenseSet<const BasicBlock *>;
155 using LocationBBMap = DenseMap<Location, BBSet>;
156 using LocationDiscriminatorMap = DenseMap<Location, unsigned>;
157 using LocationSet = DenseSet<Location>;
158
159 LocationBBMap LBM;
160 LocationDiscriminatorMap LDM;
161
162 // Traverse all instructions in the function. If the source line location
163 // of the instruction appears in other basic block, assign a new
164 // discriminator for this instruction.
165 for (BasicBlock &B : F) {
166 for (auto &I : B) {
167 // Not all intrinsic calls should have a discriminator.
168 // We want to avoid a non-deterministic assignment of discriminators at
169 // different debug levels. We still allow discriminators on memory
170 // intrinsic calls because those can be early expanded by SROA into
171 // pairs of loads and stores, and the expanded load/store instructions
172 // should have a valid discriminator.
173 if (!shouldHaveDiscriminator(I: &I))
174 continue;
175 const DILocation *DIL = I.getDebugLoc();
176 if (!DIL)
177 continue;
178 Location L = std::make_pair(x: DIL->getFilename(), y: DIL->getLine());
179 auto &BBMap = LBM[L];
180 auto R = BBMap.insert(V: &B);
181 if (BBMap.size() == 1)
182 continue;
183 // If we could insert more than one block with the same line+file, a
184 // discriminator is needed to distinguish both instructions.
185 // Only the lowest 7 bits are used to represent a discriminator to fit
186 // it in 1 byte ULEB128 representation.
187 unsigned Discriminator = R.second ? ++LDM[L] : LDM[L];
188 auto NewDIL = DIL->cloneWithBaseDiscriminator(D: Discriminator);
189 if (!NewDIL) {
190 LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
191 << DIL->getFilename() << ":" << DIL->getLine() << ":"
192 << DIL->getColumn() << ":" << Discriminator << " "
193 << I << "\n");
194 } else {
195 I.setDebugLoc(*NewDIL);
196 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
197 << DIL->getColumn() << ":" << Discriminator << " " << I
198 << "\n");
199 }
200 Changed = true;
201 }
202 }
203
204 // Traverse all instructions and assign new discriminators to call
205 // instructions with the same lineno that are in the same basic block.
206 // Sample base profile needs to distinguish different function calls within
207 // a same source line for correct profile annotation.
208 for (BasicBlock &B : F) {
209 LocationSet CallLocations;
210 for (auto &I : B) {
211 // We bypass intrinsic calls for the following two reasons:
212 // 1) We want to avoid a non-deterministic assignment of
213 // discriminators.
214 // 2) We want to minimize the number of base discriminators used.
215 if (!isa<InvokeInst>(Val: I) && (!isa<CallInst>(Val: I) || isa<IntrinsicInst>(Val: I)))
216 continue;
217
218 DILocation *CurrentDIL = I.getDebugLoc();
219 if (!CurrentDIL)
220 continue;
221 Location L =
222 std::make_pair(x: CurrentDIL->getFilename(), y: CurrentDIL->getLine());
223 if (!CallLocations.insert(V: L).second) {
224 unsigned Discriminator = ++LDM[L];
225 auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(D: Discriminator);
226 if (!NewDIL) {
227 LLVM_DEBUG(dbgs()
228 << "Could not encode discriminator: "
229 << CurrentDIL->getFilename() << ":"
230 << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn()
231 << ":" << Discriminator << " " << I << "\n");
232 } else {
233 I.setDebugLoc(*NewDIL);
234 Changed = true;
235 }
236 }
237 }
238 }
239 return Changed;
240}
241
242PreservedAnalyses AddDiscriminatorsPass::run(Function &F,
243 FunctionAnalysisManager &AM) {
244 if (!addDiscriminators(F))
245 return PreservedAnalyses::all();
246
247 // FIXME: should be all()
248 return PreservedAnalyses::none();
249}
250