250 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file adds DWARF discriminators to the IR. Path discriminators are10// used to decide what CFG path was taken inside sub-graphs whose instructions11// share the same line and column number information.12//13// The main user of this is the sample profiler. Instruction samples are14// mapped to line number information. Since a single line may be spread15// out over several basic blocks, discriminators add more precise location16// 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.end32// %0 = load i32* %sum, align 4, !dbg !1533// %cmp = icmp slt i32 %0, 0, !dbg !1534// br i1 %cmp, label %if.end, label %if.then, !dbg !1535//36// if.then: ; preds = %while.body37// call void @abort(), !dbg !1538// br label %if.end, !dbg !1539//40// Notice that all the instructions in blocks 'while.body' and 'if.then'41// have exactly the same debug information. When this program is sampled42// at runtime, the profiler will assume that all these instructions are43// equally frequent. This, in turn, will consider the edge while.body->if.then44// 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 from48// the instructions at line 101 with discriminator 1.49//50// For more details about DWARF discriminators, please visit51// http://wiki.dwarfstd.org/index.php?title=Path_Discriminators52//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/Support/Casting.h"67#include "llvm/Support/CommandLine.h"68#include "llvm/Support/Debug.h"69#include "llvm/Support/raw_ostream.h"70#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"71#include <utility>72 73using namespace llvm;74using namespace sampleprofutil;75 76#define DEBUG_TYPE "add-discriminators"77 78// Command line option to disable discriminator generation even in the79// presence of debug information. This is only needed when debugging80// debug info generation issues.81static cl::opt<bool> NoDiscriminators(82 "no-discriminators", cl::init(false),83 cl::desc("Disable generation of discriminator information."));84 85static bool shouldHaveDiscriminator(const Instruction *I) {86 return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I);87}88 89/// Assign DWARF discriminators.90///91/// To assign discriminators, we examine the boundaries of every92/// basic block and its successors. Suppose there is a basic block B193/// with successor B2. The last instruction I1 in B1 and the first94/// instruction I2 in B2 are located at the same file and line number.95/// This situation is illustrated in the following code snippet:96///97/// if (i < 10) x = i;98///99/// entry:100/// br i1 %cmp, label %if.then, label %if.end, !dbg !10101/// if.then:102/// %1 = load i32* %i.addr, align 4, !dbg !10103/// store i32 %1, i32* %x, align 4, !dbg !10104/// br label %if.end, !dbg !10105/// if.end:106/// ret void, !dbg !12107///108/// Notice how the branch instruction in block 'entry' and all the109/// instructions in block 'if.then' have the exact same debug location110/// information (!dbg !10).111///112/// To distinguish instructions in block 'entry' from instructions in113/// block 'if.then', we generate a new lexical block for all the114/// instruction in block 'if.then' that share the same file and line115/// location with the last instruction of block 'entry'.116///117/// This new lexical block will have the same location information as118/// the previous one, but with a new DWARF discriminator value.119///120/// One of the main uses of this discriminator value is in runtime121/// sample profilers. It allows the profiler to distinguish instructions122/// at location !dbg !10 that execute on different basic blocks. This is123/// important because while the predicate 'if (x < 10)' may have been124/// executed millions of times, the assignment 'x = i' may have only125/// executed a handful of times (meaning that the entry->if.then edge is126/// seldom taken).127///128/// If we did not have discriminator information, the profiler would129/// assign the same weight to both blocks 'entry' and 'if.then', which130/// in turn will make it conclude that the entry->if.then edge is very131/// hot.132///133/// To decide where to create new discriminator values, this function134/// traverses the CFG and examines instruction at basic block boundaries.135/// If the last instruction I1 of a block B1 is at the same file and line136/// location as instruction I2 of successor B2, then it creates a new137/// lexical block for I2 and all the instruction in B2 that share the same138/// file and line location as I2. This new lexical block will have a139/// different discriminator number than I1.140static bool addDiscriminators(Function &F) {141 // If the function has debug information, but the user has disabled142 // discriminators, do nothing.143 // Simlarly, if the function has no debug info, do nothing.144 if (NoDiscriminators || !F.getSubprogram())145 return false;146 147 // Create FSDiscriminatorVariable if flow sensitive discriminators are used.148 if (EnableFSDiscriminator)149 createFSDiscriminatorVariable(F.getParent());150 151 bool Changed = false;152 153 using Location = std::pair<StringRef, unsigned>;154 using BBSet = DenseSet<const BasicBlock *>;155 using LocationBBMap = DenseMap<Location, BBSet>;156 using LocationDiscriminatorMap = DenseMap<Location, unsigned>;157 using LocationSet = DenseSet<Location>;158 159 LocationBBMap LBM;160 LocationDiscriminatorMap LDM;161 162 // Traverse all instructions in the function. If the source line location163 // of the instruction appears in other basic block, assign a new164 // discriminator for this instruction.165 for (BasicBlock &B : F) {166 for (auto &I : B) {167 // Not all intrinsic calls should have a discriminator.168 // We want to avoid a non-deterministic assignment of discriminators at169 // different debug levels. We still allow discriminators on memory170 // intrinsic calls because those can be early expanded by SROA into171 // pairs of loads and stores, and the expanded load/store instructions172 // should have a valid discriminator.173 if (!shouldHaveDiscriminator(&I))174 continue;175 const DILocation *DIL = I.getDebugLoc();176 if (!DIL)177 continue;178 Location L = std::make_pair(DIL->getFilename(), DIL->getLine());179 auto &BBMap = LBM[L];180 auto R = BBMap.insert(&B);181 if (BBMap.size() == 1)182 continue;183 // If we could insert more than one block with the same line+file, a184 // discriminator is needed to distinguish both instructions.185 // Only the lowest 7 bits are used to represent a discriminator to fit186 // it in 1 byte ULEB128 representation.187 unsigned Discriminator = R.second ? ++LDM[L] : LDM[L];188 auto NewDIL = DIL->cloneWithBaseDiscriminator(Discriminator);189 if (!NewDIL) {190 LLVM_DEBUG(dbgs() << "Could not encode discriminator: "191 << DIL->getFilename() << ":" << DIL->getLine() << ":"192 << DIL->getColumn() << ":" << Discriminator << " "193 << I << "\n");194 } else {195 I.setDebugLoc(*NewDIL);196 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"197 << DIL->getColumn() << ":" << Discriminator << " " << I198 << "\n");199 }200 Changed = true;201 }202 }203 204 // Traverse all instructions and assign new discriminators to call205 // instructions with the same lineno that are in the same basic block.206 // Sample base profile needs to distinguish different function calls within207 // a same source line for correct profile annotation.208 for (BasicBlock &B : F) {209 LocationSet CallLocations;210 for (auto &I : B) {211 // We bypass intrinsic calls for the following two reasons:212 // 1) We want to avoid a non-deterministic assignment of213 // discriminators.214 // 2) We want to minimize the number of base discriminators used.215 if (!isa<InvokeInst>(I) && (!isa<CallInst>(I) || isa<IntrinsicInst>(I))) 216 continue;217 218 DILocation *CurrentDIL = I.getDebugLoc();219 if (!CurrentDIL)220 continue;221 Location L =222 std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine());223 if (!CallLocations.insert(L).second) {224 unsigned Discriminator = ++LDM[L];225 auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(Discriminator);226 if (!NewDIL) {227 LLVM_DEBUG(dbgs()228 << "Could not encode discriminator: "229 << CurrentDIL->getFilename() << ":"230 << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn()231 << ":" << Discriminator << " " << I << "\n");232 } else {233 I.setDebugLoc(*NewDIL);234 Changed = true;235 }236 }237 }238 }239 return Changed;240}241 242PreservedAnalyses AddDiscriminatorsPass::run(Function &F,243 FunctionAnalysisManager &AM) {244 if (!addDiscriminators(F))245 return PreservedAnalyses::all();246 247 // FIXME: should be all()248 return PreservedAnalyses::none();249}250