1//===- AddDiscriminators.cpp - Insert DWARF path discriminators -----------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file adds DWARF discriminators to the IR. Path discriminators are 10// used to decide what CFG path was taken inside sub-graphs whose instructions 11// share the same line and column number information. 12// 13// The main user of this is the sample profiler. Instruction samples are 14// mapped to line number information. Since a single line may be spread 15// out over several basic blocks, discriminators add more precise location 16// for the samples. 17// 18// For example, 19// 20// 1 #define ASSERT(P) 21// 2 if (!(P)) 22// 3 abort() 23// ... 24// 100 while (true) { 25// 101 ASSERT (sum < 0); 26// 102 ... 27// 130 } 28// 29// when converted to IR, this snippet looks something like: 30// 31// while.body: ; preds = %entry, %if.end 32// %0 = load i32* %sum, align 4, !dbg !15 33// %cmp = icmp slt i32 %0, 0, !dbg !15 34// br i1 %cmp, label %if.end, label %if.then, !dbg !15 35// 36// if.then: ; preds = %while.body 37// call void @abort(), !dbg !15 38// br label %if.end, !dbg !15 39// 40// Notice that all the instructions in blocks 'while.body' and 'if.then' 41// have exactly the same debug information. When this program is sampled 42// at runtime, the profiler will assume that all these instructions are 43// equally frequent. This, in turn, will consider the edge while.body->if.then 44// to be frequently taken (which is incorrect). 45// 46// By adding a discriminator value to the instructions in block 'if.then', 47// we can distinguish instructions at line 101 with discriminator 0 from 48// the instructions at line 101 with discriminator 1. 49// 50// For more details about DWARF discriminators, please visit 51// http://wiki.dwarfstd.org/index.php?title=Path_Discriminators 52// 53//===----------------------------------------------------------------------===// 54 55#include "llvm/Transforms/Utils/AddDiscriminators.h" 56#include "llvm/ADT/DenseMap.h" 57#include "llvm/ADT/DenseSet.h" 58#include "llvm/ADT/StringRef.h" 59#include "llvm/IR/BasicBlock.h" 60#include "llvm/IR/DebugInfoMetadata.h" 61#include "llvm/IR/Function.h" 62#include "llvm/IR/Instruction.h" 63#include "llvm/IR/Instructions.h" 64#include "llvm/IR/IntrinsicInst.h" 65#include "llvm/IR/PassManager.h" 66#include "llvm/InitializePasses.h" 67#include "llvm/Pass.h" 68#include "llvm/Support/Casting.h" 69#include "llvm/Support/CommandLine.h" 70#include "llvm/Support/Debug.h" 71#include "llvm/Support/raw_ostream.h" 72#include "llvm/Transforms/Utils.h" 73#include <utility> 74 75using 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. 82static cl::opt<bool> NoDiscriminators( 83 "no-discriminators", cl::init(false), 84 cl::desc("Disable generation of discriminator information.")); 85 86namespace { 87 88// The legacy pass of AddDiscriminators. 89struct AddDiscriminatorsLegacyPass : public FunctionPass { 90 static char ID; // Pass identification, replacement for typeid 91 92 AddDiscriminatorsLegacyPass() : FunctionPass(ID) { 93 initializeAddDiscriminatorsLegacyPassPass(*PassRegistry::getPassRegistry()); 94 } 95 96 bool runOnFunction(Function &F) override; 97}; 98 99} // end anonymous namespace 100 101char AddDiscriminatorsLegacyPass::ID = 0; 102 103INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators", 104 "Add DWARF path discriminators", false, false) 105INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators", 106 "Add DWARF path discriminators", false, false) 107 108// Create the legacy AddDiscriminatorsPass. 109FunctionPass *llvm::createAddDiscriminatorsPass() { 110 return new AddDiscriminatorsLegacyPass(); 111} 112 113static bool shouldHaveDiscriminator(const Instruction *I) { 114 return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I); 115} 116 117/// 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. 168static 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 auto NewDIL = DIL->cloneWithBaseDiscriminator(Discriminator); 213 if (!NewDIL) { 214 LLVM_DEBUG(dbgs() << "Could not encode discriminator: " 215 << DIL->getFilename() << ":" << DIL->getLine() << ":" 216 << DIL->getColumn() << ":" << Discriminator << " " 217 << I << "\n"); 218 } else { 219 I.setDebugLoc(NewDIL.getValue()); 220 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":" 221 << DIL->getColumn() << ":" << Discriminator << " " << I 222 << "\n"); 223 } 224 Changed = true; 225 } 226 } 227 228 // Traverse all instructions and assign new discriminators to call 229 // instructions with the same lineno that are in the same basic block. 230 // Sample base profile needs to distinguish different function calls within 231 // a same source line for correct profile annotation. 232 for (BasicBlock &B : F) { 233 LocationSet CallLocations; 234 for (auto &I : B.getInstList()) { 235 // We bypass intrinsic calls for the following two reasons: 236 // 1) We want to avoid a non-deterministic assignment of 237 // discriminators. 238 // 2) We want to minimize the number of base discriminators used. 239 if (!isa<InvokeInst>(I) && (!isa<CallInst>(I) || isa<IntrinsicInst>(I))) 240 continue; 241 242 DILocation *CurrentDIL = I.getDebugLoc(); 243 if (!CurrentDIL) 244 continue; 245 Location L = 246 std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine()); 247 if (!CallLocations.insert(L).second) { 248 unsigned Discriminator = ++LDM[L]; 249 auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(Discriminator); 250 if (!NewDIL) { 251 LLVM_DEBUG(dbgs() 252 << "Could not encode discriminator: " 253 << CurrentDIL->getFilename() << ":" 254 << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn() 255 << ":" << Discriminator << " " << I << "\n"); 256 } else { 257 I.setDebugLoc(NewDIL.getValue()); 258 Changed = true; 259 } 260 } 261 } 262 } 263 return Changed; 264} 265 266bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) { 267 return addDiscriminators(F); 268} 269 270PreservedAnalyses AddDiscriminatorsPass::run(Function &F, 271 FunctionAnalysisManager &AM) { 272 if (!addDiscriminators(F)) 273 return PreservedAnalyses::all(); 274 275 // FIXME: should be all() 276 return PreservedAnalyses::none(); 277} 278