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