LLVM  6.0.0svn
AddDiscriminators.cpp
Go to the documentation of this file.
1 //===- AddDiscriminators.cpp - Insert DWARF path discriminators -----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
13 //
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
17 // for the samples.
18 //
19 // For example,
20 //
21 // 1 #define ASSERT(P)
22 // 2 if (!(P))
23 // 3 abort()
24 // ...
25 // 100 while (true) {
26 // 101 ASSERT (sum < 0);
27 // 102 ...
28 // 130 }
29 //
30 // when converted to IR, this snippet looks something like:
31 //
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
36 //
37 // if.then: ; preds = %while.body
38 // call void @abort(), !dbg !15
39 // br label %if.end, !dbg !15
40 //
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).
46 //
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.
50 //
51 // For more details about DWARF discriminators, please visit
52 // http://wiki.dwarfstd.org/index.php?title=Path_Discriminators
53 //
54 //===----------------------------------------------------------------------===//
55 
57 #include "llvm/ADT/DenseMap.h"
58 #include "llvm/ADT/DenseSet.h"
59 #include "llvm/ADT/StringRef.h"
60 #include "llvm/IR/BasicBlock.h"
62 #include "llvm/IR/Function.h"
63 #include "llvm/IR/Instruction.h"
64 #include "llvm/IR/Instructions.h"
65 #include "llvm/IR/IntrinsicInst.h"
66 #include "llvm/IR/PassManager.h"
67 #include "llvm/Pass.h"
68 #include "llvm/Support/Casting.h"
70 #include "llvm/Support/Debug.h"
72 #include "llvm/Transforms/Scalar.h"
73 #include <utility>
74 
75 using namespace llvm;
76 
77 #define DEBUG_TYPE "add-discriminators"
78 
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.
83  "no-discriminators", cl::init(false),
84  cl::desc("Disable generation of discriminator information."));
85 
86 namespace {
87 
88 // The legacy pass of AddDiscriminators.
89 struct AddDiscriminatorsLegacyPass : public FunctionPass {
90  static char ID; // Pass identification, replacement for typeid
91 
92  AddDiscriminatorsLegacyPass() : FunctionPass(ID) {
94  }
95 
96  bool runOnFunction(Function &F) override;
97 };
98 
99 } // end anonymous namespace
100 
102 
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)
107 
108 // Create the legacy AddDiscriminatorsPass.
110  return new AddDiscriminatorsLegacyPass();
111 }
112 
113 static bool shouldHaveDiscriminator(const Instruction *I) {
114  return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I);
115 }
116 
117 /// \brief Assign DWARF discriminators.
118 ///
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:
124 ///
125 /// if (i < 10) x = i;
126 ///
127 /// entry:
128 /// br i1 %cmp, label %if.then, label %if.end, !dbg !10
129 /// if.then:
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
133 /// if.end:
134 /// ret void, !dbg !12
135 ///
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).
139 ///
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'.
144 ///
145 /// This new lexical block will have the same location information as
146 /// the previous one, but with a new DWARF discriminator value.
147 ///
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
154 /// seldom taken).
155 ///
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
159 /// hot.
160 ///
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())
173  return false;
174 
175  bool Changed = false;
176 
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>;
182 
183  LocationBBMap LBM;
184  LocationDiscriminatorMap LDM;
185 
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))
198  continue;
199  const DILocation *DIL = I.getDebugLoc();
200  if (!DIL)
201  continue;
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)
206  continue;
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  I.setDebugLoc(DIL->setBaseDiscriminator(Discriminator));
213  DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
214  << DIL->getColumn() << ":" << Discriminator << " " << I
215  << "\n");
216  Changed = true;
217  }
218  }
219 
220  // Traverse all instructions and assign new discriminators to call
221  // instructions with the same lineno that are in the same basic block.
222  // Sample base profile needs to distinguish different function calls within
223  // a same source line for correct profile annotation.
224  for (BasicBlock &B : F) {
225  LocationSet CallLocations;
226  for (auto &I : B.getInstList()) {
227  CallInst *Current = dyn_cast<CallInst>(&I);
228  // We bypass intrinsic calls for the following two reasons:
229  // 1) We want to avoid a non-deterministic assigment of
230  // discriminators.
231  // 2) We want to minimize the number of base discriminators used.
232  if (!Current || isa<IntrinsicInst>(&I))
233  continue;
234 
235  DILocation *CurrentDIL = Current->getDebugLoc();
236  if (!CurrentDIL)
237  continue;
238  Location L =
239  std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine());
240  if (!CallLocations.insert(L).second) {
241  unsigned Discriminator = ++LDM[L];
242  Current->setDebugLoc(CurrentDIL->setBaseDiscriminator(Discriminator));
243  Changed = true;
244  }
245  }
246  }
247  return Changed;
248 }
249 
251  return addDiscriminators(F);
252 }
253 
256  if (!addDiscriminators(F))
257  return PreservedAnalyses::all();
258 
259  // FIXME: should be all()
260  return PreservedAnalyses::none();
261 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
This class represents a function call, abstracting a target machine&#39;s calling convention.
F(f)
void initializeAddDiscriminatorsLegacyPassPass(PassRegistry &)
const DILocation * setBaseDiscriminator(unsigned BD) const
Returns a new DILocation with updated base discriminator BD.
Debug location.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:281
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1497
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool addDiscriminators(Function &F)
Assign DWARF discriminators.
static cl::opt< bool > NoDiscriminators("no-discriminators", cl::init(false), cl::desc("Disable generation of discriminator information."))
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators", "Add DWARF path discriminators", false, false) INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:284
#define I(x, y, z)
Definition: MD5.cpp:58
add discriminators
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
static bool shouldHaveDiscriminator(const Instruction *I)
#define DEBUG(X)
Definition: Debug.h:118
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
FunctionPass * createAddDiscriminatorsPass()