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#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/LLVMContext.h"
62#include "llvm/IR/Module.h"
63#include "llvm/Pass.h"
64#include "llvm/Support/CommandLine.h"
65#include "llvm/Support/Debug.h"
66#include "llvm/Support/raw_ostream.h"
67
68using namespace llvm;
69
70#define DEBUG_TYPE "add-discriminators"
71
72namespace {
73  struct AddDiscriminators : public FunctionPass {
74    static char ID; // Pass identification, replacement for typeid
75    AddDiscriminators() : FunctionPass(ID) {
76      initializeAddDiscriminatorsPass(*PassRegistry::getPassRegistry());
77    }
78
79    bool runOnFunction(Function &F) override;
80  };
81}
82
83char AddDiscriminators::ID = 0;
84INITIALIZE_PASS_BEGIN(AddDiscriminators, "add-discriminators",
85                      "Add DWARF path discriminators", false, false)
86INITIALIZE_PASS_END(AddDiscriminators, "add-discriminators",
87                    "Add DWARF path discriminators", false, false)
88
89// Command line option to disable discriminator generation even in the
90// presence of debug information. This is only needed when debugging
91// debug info generation issues.
92static cl::opt<bool>
93NoDiscriminators("no-discriminators", cl::init(false),
94                 cl::desc("Disable generation of discriminator information."));
95
96FunctionPass *llvm::createAddDiscriminatorsPass() {
97  return new AddDiscriminators();
98}
99
100static bool hasDebugInfo(const Function &F) {
101  NamedMDNode *CUNodes = F.getParent()->getNamedMetadata("llvm.dbg.cu");
102  return CUNodes != nullptr;
103}
104
105/// \brief Assign DWARF discriminators.
106///
107/// To assign discriminators, we examine the boundaries of every
108/// basic block and its successors. Suppose there is a basic block B1
109/// with successor B2. The last instruction I1 in B1 and the first
110/// instruction I2 in B2 are located at the same file and line number.
111/// This situation is illustrated in the following code snippet:
112///
113///       if (i < 10) x = i;
114///
115///     entry:
116///       br i1 %cmp, label %if.then, label %if.end, !dbg !10
117///     if.then:
118///       %1 = load i32* %i.addr, align 4, !dbg !10
119///       store i32 %1, i32* %x, align 4, !dbg !10
120///       br label %if.end, !dbg !10
121///     if.end:
122///       ret void, !dbg !12
123///
124/// Notice how the branch instruction in block 'entry' and all the
125/// instructions in block 'if.then' have the exact same debug location
126/// information (!dbg !10).
127///
128/// To distinguish instructions in block 'entry' from instructions in
129/// block 'if.then', we generate a new lexical block for all the
130/// instruction in block 'if.then' that share the same file and line
131/// location with the last instruction of block 'entry'.
132///
133/// This new lexical block will have the same location information as
134/// the previous one, but with a new DWARF discriminator value.
135///
136/// One of the main uses of this discriminator value is in runtime
137/// sample profilers. It allows the profiler to distinguish instructions
138/// at location !dbg !10 that execute on different basic blocks. This is
139/// important because while the predicate 'if (x < 10)' may have been
140/// executed millions of times, the assignment 'x = i' may have only
141/// executed a handful of times (meaning that the entry->if.then edge is
142/// seldom taken).
143///
144/// If we did not have discriminator information, the profiler would
145/// assign the same weight to both blocks 'entry' and 'if.then', which
146/// in turn will make it conclude that the entry->if.then edge is very
147/// hot.
148///
149/// To decide where to create new discriminator values, this function
150/// traverses the CFG and examines instruction at basic block boundaries.
151/// If the last instruction I1 of a block B1 is at the same file and line
152/// location as instruction I2 of successor B2, then it creates a new
153/// lexical block for I2 and all the instruction in B2 that share the same
154/// file and line location as I2. This new lexical block will have a
155/// different discriminator number than I1.
156bool AddDiscriminators::runOnFunction(Function &F) {
157  // If the function has debug information, but the user has disabled
158  // discriminators, do nothing.
159  // Simlarly, if the function has no debug info, do nothing.
160  // Finally, if this module is built with dwarf versions earlier than 4,
161  // do nothing (discriminator support is a DWARF 4 feature).
162  if (NoDiscriminators ||
163      !hasDebugInfo(F) ||
164      F.getParent()->getDwarfVersion() < 4)
165    return false;
166
167  bool Changed = false;
168  Module *M = F.getParent();
169  LLVMContext &Ctx = M->getContext();
170  DIBuilder Builder(*M);
171
172  // Traverse all the blocks looking for instructions in different
173  // blocks that are at the same file:line location.
174  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
175    BasicBlock *B = I;
176    TerminatorInst *Last = B->getTerminator();
177    DebugLoc LastLoc = Last->getDebugLoc();
178    if (LastLoc.isUnknown()) continue;
179    DILocation LastDIL(LastLoc.getAsMDNode(Ctx));
180
181    for (unsigned I = 0; I < Last->getNumSuccessors(); ++I) {
182      BasicBlock *Succ = Last->getSuccessor(I);
183      Instruction *First = Succ->getFirstNonPHIOrDbgOrLifetime();
184      DebugLoc FirstLoc = First->getDebugLoc();
185      if (FirstLoc.isUnknown()) continue;
186      DILocation FirstDIL(FirstLoc.getAsMDNode(Ctx));
187
188      // If the first instruction (First) of Succ is at the same file
189      // location as B's last instruction (Last), add a new
190      // discriminator for First's location and all the instructions
191      // in Succ that share the same location with First.
192      if (FirstDIL.atSameLineAs(LastDIL)) {
193        // Create a new lexical scope and compute a new discriminator
194        // number for it.
195        StringRef Filename = FirstDIL.getFilename();
196        unsigned LineNumber = FirstDIL.getLineNumber();
197        unsigned ColumnNumber = FirstDIL.getColumnNumber();
198        DIScope Scope = FirstDIL.getScope();
199        DIFile File = Builder.createFile(Filename, Scope.getDirectory());
200        unsigned Discriminator = FirstDIL.computeNewDiscriminator(Ctx);
201        DILexicalBlock NewScope = Builder.createLexicalBlock(
202            Scope, File, LineNumber, ColumnNumber, Discriminator);
203        DILocation NewDIL = FirstDIL.copyWithNewScope(Ctx, NewScope);
204        DebugLoc newDebugLoc = DebugLoc::getFromDILocation(NewDIL);
205
206        // Attach this new debug location to First and every
207        // instruction following First that shares the same location.
208        for (BasicBlock::iterator I1(*First), E1 = Succ->end(); I1 != E1;
209             ++I1) {
210          if (I1->getDebugLoc() != FirstLoc) break;
211          I1->setDebugLoc(newDebugLoc);
212          DEBUG(dbgs() << NewDIL.getFilename() << ":" << NewDIL.getLineNumber()
213                       << ":" << NewDIL.getColumnNumber() << ":"
214                       << NewDIL.getDiscriminator() << *I1 << "\n");
215        }
216        DEBUG(dbgs() << "\n");
217        Changed = true;
218      }
219    }
220  }
221  return Changed;
222}
223