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 72 using namespace llvm; 73 74 #define DEBUG_TYPE "add-discriminators" 75 76 namespace { 77 // The legacy pass of AddDiscriminators. 78 struct 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 89 char AddDiscriminatorsLegacyPass::ID = 0; 90 INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators", 91 "Add DWARF path discriminators", false, false) 92 INITIALIZE_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. 98 static cl::opt<bool> NoDiscriminators( 99 "no-discriminators", cl::init(false), 100 cl::desc("Disable generation of discriminator information.")); 101 102 // Create the legacy AddDiscriminatorsPass. 103 FunctionPass *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. 158 static 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 if (NoDiscriminators || !F.getSubprogram()) 163 return false; 164 165 bool Changed = false; 166 Module *M = F.getParent(); 167 LLVMContext &Ctx = M->getContext(); 168 DIBuilder Builder(*M, /*AllowUnresolved*/ false); 169 170 typedef std::pair<StringRef, unsigned> Location; 171 typedef SmallDenseMap<DIScope *, DILexicalBlockFile *, 1> ScopeMap; 172 typedef DenseMap<const BasicBlock *, ScopeMap> BBScopeMap; 173 typedef DenseMap<Location, BBScopeMap> LocationBBMap; 174 typedef DenseMap<Location, unsigned> LocationDiscriminatorMap; 175 typedef DenseSet<Location> LocationSet; 176 177 LocationBBMap LBM; 178 LocationDiscriminatorMap LDM; 179 180 // Traverse all instructions in the function. If the source line location 181 // of the instruction appears in other basic block, assign a new 182 // discriminator for this instruction. 183 for (BasicBlock &B : F) { 184 for (auto &I : B.getInstList()) { 185 if (isa<IntrinsicInst>(&I)) 186 continue; 187 const DILocation *DIL = I.getDebugLoc(); 188 if (!DIL) 189 continue; 190 DIScope *Scope = DIL->getScope(); 191 Location L = std::make_pair(DIL->getFilename(), DIL->getLine()); 192 auto &BBMap = LBM[L]; 193 auto R = BBMap.insert({&B, ScopeMap()}); 194 if (BBMap.size() == 1) 195 continue; 196 bool InsertSuccess = R.second; 197 ScopeMap &Scopes = R.first->second; 198 // If we could insert more than one block with the same line+file, a 199 // discriminator is needed to distinguish both instructions. 200 auto R1 = Scopes.insert({Scope, nullptr}); 201 DILexicalBlockFile *&NewScope = R1.first->second; 202 unsigned Discriminator = InsertSuccess ? ++LDM[L] : LDM[L]; 203 if (!NewScope) { 204 auto *File = Builder.createFile(DIL->getFilename(), 205 Scope->getDirectory()); 206 NewScope = Builder.createLexicalBlockFile(Scope, File, Discriminator); 207 } 208 I.setDebugLoc(DILocation::get(Ctx, DIL->getLine(), DIL->getColumn(), 209 NewScope, DIL->getInlinedAt())); 210 DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":" 211 << DIL->getColumn() << ":" 212 << dyn_cast<DILexicalBlockFile>(NewScope)->getDiscriminator() 213 << I << "\n"); 214 Changed = true; 215 } 216 } 217 218 // Traverse all instructions and assign new discriminators to call 219 // instructions with the same lineno that are in the same basic block. 220 // Sample base profile needs to distinguish different function calls within 221 // a same source line for correct profile annotation. 222 for (BasicBlock &B : F) { 223 LocationSet CallLocations; 224 for (auto &I : B.getInstList()) { 225 CallInst *Current = dyn_cast<CallInst>(&I); 226 if (!Current || isa<IntrinsicInst>(&I)) 227 continue; 228 229 DILocation *CurrentDIL = Current->getDebugLoc(); 230 if (!CurrentDIL) 231 continue; 232 Location L = 233 std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine()); 234 if (!CallLocations.insert(L).second) { 235 auto *Scope = CurrentDIL->getScope(); 236 auto *File = Builder.createFile(CurrentDIL->getFilename(), 237 Scope->getDirectory()); 238 auto *NewScope = Builder.createLexicalBlockFile(Scope, File, ++LDM[L]); 239 Current->setDebugLoc(DILocation::get(Ctx, CurrentDIL->getLine(), 240 CurrentDIL->getColumn(), NewScope, 241 CurrentDIL->getInlinedAt())); 242 Changed = true; 243 } 244 } 245 } 246 return Changed; 247 } 248 249 bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) { 250 return addDiscriminators(F); 251 } 252 PreservedAnalyses AddDiscriminatorsPass::run(Function &F, 253 FunctionAnalysisManager &AM) { 254 if (!addDiscriminators(F)) 255 return PreservedAnalyses::all(); 256 257 // FIXME: should be all() 258 return PreservedAnalyses::none(); 259 } 260