LLVM  14.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"
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"
70 #include "llvm/Support/Debug.h"
72 #include "llvm/Transforms/Utils.h"
74 #include <utility>
75 
76 using namespace llvm;
77 using 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 
88 namespace {
89 
90 // The legacy pass of AddDiscriminators.
91 struct 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 
104 
105 INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators",
106  "Add DWARF path discriminators", false, false)
107 INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators",
108  "Add DWARF path discriminators", false, false)
109 
110 // Create the legacy AddDiscriminatorsPass.
112  return new AddDiscriminatorsLegacyPass();
113 }
114 
115 static bool shouldHaveDiscriminator(const Instruction *I) {
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.
170 static bool addDiscriminators(Function &F) {
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.getInstList()) {
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.
203  if (!shouldHaveDiscriminator(&I))
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.getValue());
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.getInstList()) {
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) {
257  LLVM_DEBUG(dbgs()
258  << "Could not encode discriminator: "
259  << CurrentDIL->getFilename() << ":"
260  << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn()
261  << ":" << Discriminator << " " << I << "\n");
262  } else {
263  I.setDebugLoc(NewDIL.getValue());
264  Changed = true;
265  }
266  }
267  }
268  }
269  return Changed;
270 }
271 
273  return addDiscriminators(F);
274 }
275 
278  if (!addDiscriminators(F))
279  return PreservedAnalyses::all();
280 
281  // FIXME: should be all()
282  return PreservedAnalyses::none();
283 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
IntrinsicInst.h
DebugInfoMetadata.h
llvm::Function
Definition: Function.h:61
StringRef.h
Pass.h
llvm::EnableFSDiscriminator
cl::opt< bool > EnableFSDiscriminator
Definition: TargetPassConfig.cpp:385
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
DenseMap.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
CommandLine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
shouldHaveDiscriminator
static bool shouldHaveDiscriminator(const Instruction *I)
Definition: AddDiscriminators.cpp:115
llvm::sampleprofutil::createFSDiscriminatorVariable
void createFSDiscriminatorVariable(Module *M)
Create a global variable to flag FSDiscriminators are used.
Definition: SampleProfileLoaderBaseUtil.cpp:163
SampleProfileLoaderBaseUtil.h
Utils.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators", "Add DWARF path discriminators", false, false) INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::DenseSet< const BasicBlock * >
BasicBlock.h
llvm::cl::opt< bool >
NoDiscriminators
static cl::opt< bool > NoDiscriminators("no-discriminators", cl::init(false), cl::desc("Disable generation of discriminator information."))
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
discriminators
add discriminators
Definition: AddDiscriminators.cpp:107
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
addDiscriminators
static bool addDiscriminators(Function &F)
Assign DWARF discriminators.
Definition: AddDiscriminators.cpp:170
llvm::AddDiscriminatorsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AddDiscriminators.cpp:276
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
Function.h
PassManager.h
llvm::createAddDiscriminatorsPass
FunctionPass * createAddDiscriminatorsPass()
Definition: AddDiscriminators.cpp:111
Instructions.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::cl::desc
Definition: CommandLine.h:414
llvm::DILocation::cloneWithBaseDiscriminator
Optional< const DILocation * > cloneWithBaseDiscriminator(unsigned BD) const
Returns a new DILocation with updated base discriminator BD.
Definition: DebugInfoMetadata.h:2243
raw_ostream.h
InitializePasses.h
Debug.h
llvm::initializeAddDiscriminatorsLegacyPassPass
void initializeAddDiscriminatorsLegacyPassPass(PassRegistry &)
AddDiscriminators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37