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/Utils/AddDiscriminators.h" 56#include "llvm/ADT/DenseMap.h" 57#include "llvm/ADT/DenseSet.h" 58#include "llvm/IR/BasicBlock.h" 59#include "llvm/IR/Constants.h" 60#include "llvm/IR/DIBuilder.h" 61#include "llvm/IR/DebugInfo.h" 62#include "llvm/IR/Instructions.h" 63#include "llvm/IR/IntrinsicInst.h" 64#include "llvm/IR/LLVMContext.h" 65#include "llvm/IR/Module.h" 66#include "llvm/Pass.h" 67#include "llvm/Support/CommandLine.h" 68#include "llvm/Support/Debug.h" 69#include "llvm/Support/raw_ostream.h" 70#include "llvm/Transforms/Scalar.h" 71 72using namespace llvm; 73 74#define DEBUG_TYPE "add-discriminators" 75 76namespace { 77// The legacy pass of AddDiscriminators. 78struct AddDiscriminatorsLegacyPass : public FunctionPass { 79 static char ID; // Pass identification, replacement for typeid 80 AddDiscriminatorsLegacyPass() : FunctionPass(ID) { 81 initializeAddDiscriminatorsLegacyPassPass(*PassRegistry::getPassRegistry()); 82 } 83 84 bool runOnFunction(Function &F) override; 85}; 86 87} // end anonymous namespace 88 89char AddDiscriminatorsLegacyPass::ID = 0; 90INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators", 91 "Add DWARF path discriminators", false, false) 92INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators", 93 "Add DWARF path discriminators", false, false) 94 95// Command line option to disable discriminator generation even in the 96// presence of debug information. This is only needed when debugging 97// debug info generation issues. 98static cl::opt<bool> NoDiscriminators( 99 "no-discriminators", cl::init(false), 100 cl::desc("Disable generation of discriminator information.")); 101 102// Create the legacy AddDiscriminatorsPass. 103FunctionPass *llvm::createAddDiscriminatorsPass() { 104 return new AddDiscriminatorsLegacyPass(); 105} 106 107/// \brief Assign DWARF discriminators. 108/// 109/// To assign discriminators, we examine the boundaries of every 110/// basic block and its successors. Suppose there is a basic block B1 111/// with successor B2. The last instruction I1 in B1 and the first 112/// instruction I2 in B2 are located at the same file and line number. 113/// This situation is illustrated in the following code snippet: 114/// 115/// if (i < 10) x = i; 116/// 117/// entry: 118/// br i1 %cmp, label %if.then, label %if.end, !dbg !10 119/// if.then: 120/// %1 = load i32* %i.addr, align 4, !dbg !10 121/// store i32 %1, i32* %x, align 4, !dbg !10 122/// br label %if.end, !dbg !10 123/// if.end: 124/// ret void, !dbg !12 125/// 126/// Notice how the branch instruction in block 'entry' and all the 127/// instructions in block 'if.then' have the exact same debug location 128/// information (!dbg !10). 129/// 130/// To distinguish instructions in block 'entry' from instructions in 131/// block 'if.then', we generate a new lexical block for all the 132/// instruction in block 'if.then' that share the same file and line 133/// location with the last instruction of block 'entry'. 134/// 135/// This new lexical block will have the same location information as 136/// the previous one, but with a new DWARF discriminator value. 137/// 138/// One of the main uses of this discriminator value is in runtime 139/// sample profilers. It allows the profiler to distinguish instructions 140/// at location !dbg !10 that execute on different basic blocks. This is 141/// important because while the predicate 'if (x < 10)' may have been 142/// executed millions of times, the assignment 'x = i' may have only 143/// executed a handful of times (meaning that the entry->if.then edge is 144/// seldom taken). 145/// 146/// If we did not have discriminator information, the profiler would 147/// assign the same weight to both blocks 'entry' and 'if.then', which 148/// in turn will make it conclude that the entry->if.then edge is very 149/// hot. 150/// 151/// To decide where to create new discriminator values, this function 152/// traverses the CFG and examines instruction at basic block boundaries. 153/// If the last instruction I1 of a block B1 is at the same file and line 154/// location as instruction I2 of successor B2, then it creates a new 155/// lexical block for I2 and all the instruction in B2 that share the same 156/// file and line location as I2. This new lexical block will have a 157/// different discriminator number than I1. 158static bool addDiscriminators(Function &F) { 159 // If the function has debug information, but the user has disabled 160 // discriminators, do nothing. 161 // Simlarly, if the function has no debug info, do nothing. 162 // Finally, if this module is built with dwarf versions earlier than 4, 163 // do nothing (discriminator support is a DWARF 4 feature). 164 if (NoDiscriminators || !F.getSubprogram() || 165 F.getParent()->getDwarfVersion() < 4) 166 return false; 167 168 bool Changed = false; 169 Module *M = F.getParent(); 170 LLVMContext &Ctx = M->getContext(); 171 DIBuilder Builder(*M, /*AllowUnresolved*/ false); 172 173 typedef std::pair<StringRef, unsigned> Location; 174 typedef DenseMap<const BasicBlock *, Metadata *> BBScopeMap; 175 typedef DenseMap<Location, BBScopeMap> LocationBBMap; 176 typedef DenseMap<Location, unsigned> LocationDiscriminatorMap; 177 typedef DenseSet<Location> LocationSet; 178 179 LocationBBMap LBM; 180 LocationDiscriminatorMap LDM; 181 182 // Traverse all instructions in the function. If the source line location 183 // of the instruction appears in other basic block, assign a new 184 // discriminator for this instruction. 185 for (BasicBlock &B : F) { 186 for (auto &I : B.getInstList()) { 187 if (isa<DbgInfoIntrinsic>(&I)) 188 continue; 189 const DILocation *DIL = I.getDebugLoc(); 190 if (!DIL) 191 continue; 192 Location L = std::make_pair(DIL->getFilename(), DIL->getLine()); 193 auto &BBMap = LBM[L]; 194 auto R = BBMap.insert(std::make_pair(&B, (Metadata *)nullptr)); 195 if (BBMap.size() == 1) 196 continue; 197 bool InsertSuccess = R.second; 198 Metadata *&NewScope = R.first->second; 199 // If we could insert a different block in the same location, a 200 // discriminator is needed to distinguish both instructions. 201 if (InsertSuccess) { 202 auto *Scope = DIL->getScope(); 203 auto *File = 204 Builder.createFile(DIL->getFilename(), Scope->getDirectory()); 205 NewScope = Builder.createLexicalBlockFile(Scope, File, ++LDM[L]); 206 } 207 I.setDebugLoc(DILocation::get(Ctx, DIL->getLine(), DIL->getColumn(), 208 NewScope, DIL->getInlinedAt())); 209 DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":" 210 << DIL->getColumn() << ":" 211 << dyn_cast<DILexicalBlockFile>(NewScope)->getDiscriminator() 212 << I << "\n"); 213 Changed = true; 214 } 215 } 216 217 // Traverse all instructions and assign new discriminators to call 218 // instructions with the same lineno that are in the same basic block. 219 // Sample base profile needs to distinguish different function calls within 220 // a same source line for correct profile annotation. 221 for (BasicBlock &B : F) { 222 LocationSet CallLocations; 223 for (auto &I : B.getInstList()) { 224 CallInst *Current = dyn_cast<CallInst>(&I); 225 if (!Current || isa<DbgInfoIntrinsic>(&I)) 226 continue; 227 228 DILocation *CurrentDIL = Current->getDebugLoc(); 229 if (!CurrentDIL) 230 continue; 231 Location L = 232 std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine()); 233 if (!CallLocations.insert(L).second) { 234 auto *Scope = CurrentDIL->getScope(); 235 auto *File = Builder.createFile(CurrentDIL->getFilename(), 236 Scope->getDirectory()); 237 auto *NewScope = Builder.createLexicalBlockFile(Scope, File, ++LDM[L]); 238 Current->setDebugLoc(DILocation::get(Ctx, CurrentDIL->getLine(), 239 CurrentDIL->getColumn(), NewScope, 240 CurrentDIL->getInlinedAt())); 241 Changed = true; 242 } 243 } 244 } 245 return Changed; 246} 247 248bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) { 249 return addDiscriminators(F); 250} 251PreservedAnalyses AddDiscriminatorsPass::run(Function &F, 252 AnalysisManager<Function> &AM) { 253 if (!addDiscriminators(F)) 254 return PreservedAnalyses::all(); 255 256 // FIXME: should be all() 257 return PreservedAnalyses::none(); 258} 259