| //===- AddDiscriminators.cpp - Insert DWARF path discriminators -----------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file adds DWARF discriminators to the IR. Path discriminators are |
| // used to decide what CFG path was taken inside sub-graphs whose instructions |
| // share the same line and column number information. |
| // |
| // The main user of this is the sample profiler. Instruction samples are |
| // mapped to line number information. Since a single line may be spread |
| // out over several basic blocks, discriminators add more precise location |
| // for the samples. |
| // |
| // For example, |
| // |
| // 1 #define ASSERT(P) |
| // 2 if (!(P)) |
| // 3 abort() |
| // ... |
| // 100 while (true) { |
| // 101 ASSERT (sum < 0); |
| // 102 ... |
| // 130 } |
| // |
| // when converted to IR, this snippet looks something like: |
| // |
| // while.body: ; preds = %entry, %if.end |
| // %0 = load i32* %sum, align 4, !dbg !15 |
| // %cmp = icmp slt i32 %0, 0, !dbg !15 |
| // br i1 %cmp, label %if.end, label %if.then, !dbg !15 |
| // |
| // if.then: ; preds = %while.body |
| // call void @abort(), !dbg !15 |
| // br label %if.end, !dbg !15 |
| // |
| // Notice that all the instructions in blocks 'while.body' and 'if.then' |
| // have exactly the same debug information. When this program is sampled |
| // at runtime, the profiler will assume that all these instructions are |
| // equally frequent. This, in turn, will consider the edge while.body->if.then |
| // to be frequently taken (which is incorrect). |
| // |
| // By adding a discriminator value to the instructions in block 'if.then', |
| // we can distinguish instructions at line 101 with discriminator 0 from |
| // the instructions at line 101 with discriminator 1. |
| // |
| // For more details about DWARF discriminators, please visit |
| // http://wiki.dwarfstd.org/index.php?title=Path_Discriminators |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Utils/AddDiscriminators.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/ADT/StringRef.h" |
| #include "llvm/IR/BasicBlock.h" |
| #include "llvm/IR/DebugInfoMetadata.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/Instruction.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/PassManager.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/Casting.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/Transforms/Utils.h" |
| #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h" |
| #include <utility> |
| |
| using namespace llvm; |
| using namespace sampleprofutil; |
| |
| #define DEBUG_TYPE "add-discriminators" |
| |
| // Command line option to disable discriminator generation even in the |
| // presence of debug information. This is only needed when debugging |
| // debug info generation issues. |
| static cl::opt<bool> NoDiscriminators( |
| "no-discriminators", cl::init(false), |
| cl::desc("Disable generation of discriminator information.")); |
| |
| namespace { |
| |
| // The legacy pass of AddDiscriminators. |
| struct AddDiscriminatorsLegacyPass : public FunctionPass { |
| static char ID; // Pass identification, replacement for typeid |
| |
| AddDiscriminatorsLegacyPass() : FunctionPass(ID) { |
| initializeAddDiscriminatorsLegacyPassPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| bool runOnFunction(Function &F) override; |
| }; |
| |
| } // end anonymous namespace |
| |
| char AddDiscriminatorsLegacyPass::ID = 0; |
| |
| INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators", |
| "Add DWARF path discriminators", false, false) |
| INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators", |
| "Add DWARF path discriminators", false, false) |
| |
| // Create the legacy AddDiscriminatorsPass. |
| FunctionPass *llvm::createAddDiscriminatorsPass() { |
| return new AddDiscriminatorsLegacyPass(); |
| } |
| |
| static bool shouldHaveDiscriminator(const Instruction *I) { |
| return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I); |
| } |
| |
| /// Assign DWARF discriminators. |
| /// |
| /// To assign discriminators, we examine the boundaries of every |
| /// basic block and its successors. Suppose there is a basic block B1 |
| /// with successor B2. The last instruction I1 in B1 and the first |
| /// instruction I2 in B2 are located at the same file and line number. |
| /// This situation is illustrated in the following code snippet: |
| /// |
| /// if (i < 10) x = i; |
| /// |
| /// entry: |
| /// br i1 %cmp, label %if.then, label %if.end, !dbg !10 |
| /// if.then: |
| /// %1 = load i32* %i.addr, align 4, !dbg !10 |
| /// store i32 %1, i32* %x, align 4, !dbg !10 |
| /// br label %if.end, !dbg !10 |
| /// if.end: |
| /// ret void, !dbg !12 |
| /// |
| /// Notice how the branch instruction in block 'entry' and all the |
| /// instructions in block 'if.then' have the exact same debug location |
| /// information (!dbg !10). |
| /// |
| /// To distinguish instructions in block 'entry' from instructions in |
| /// block 'if.then', we generate a new lexical block for all the |
| /// instruction in block 'if.then' that share the same file and line |
| /// location with the last instruction of block 'entry'. |
| /// |
| /// This new lexical block will have the same location information as |
| /// the previous one, but with a new DWARF discriminator value. |
| /// |
| /// One of the main uses of this discriminator value is in runtime |
| /// sample profilers. It allows the profiler to distinguish instructions |
| /// at location !dbg !10 that execute on different basic blocks. This is |
| /// important because while the predicate 'if (x < 10)' may have been |
| /// executed millions of times, the assignment 'x = i' may have only |
| /// executed a handful of times (meaning that the entry->if.then edge is |
| /// seldom taken). |
| /// |
| /// If we did not have discriminator information, the profiler would |
| /// assign the same weight to both blocks 'entry' and 'if.then', which |
| /// in turn will make it conclude that the entry->if.then edge is very |
| /// hot. |
| /// |
| /// To decide where to create new discriminator values, this function |
| /// traverses the CFG and examines instruction at basic block boundaries. |
| /// If the last instruction I1 of a block B1 is at the same file and line |
| /// location as instruction I2 of successor B2, then it creates a new |
| /// lexical block for I2 and all the instruction in B2 that share the same |
| /// file and line location as I2. This new lexical block will have a |
| /// different discriminator number than I1. |
| static bool addDiscriminators(Function &F) { |
| // If the function has debug information, but the user has disabled |
| // discriminators, do nothing. |
| // Simlarly, if the function has no debug info, do nothing. |
| if (NoDiscriminators || !F.getSubprogram()) |
| return false; |
| |
| // Create FSDiscriminatorVariable if flow sensitive discriminators are used. |
| if (EnableFSDiscriminator) |
| createFSDiscriminatorVariable(F.getParent()); |
| |
| bool Changed = false; |
| |
| using Location = std::pair<StringRef, unsigned>; |
| using BBSet = DenseSet<const BasicBlock *>; |
| using LocationBBMap = DenseMap<Location, BBSet>; |
| using LocationDiscriminatorMap = DenseMap<Location, unsigned>; |
| using LocationSet = DenseSet<Location>; |
| |
| LocationBBMap LBM; |
| LocationDiscriminatorMap LDM; |
| |
| // Traverse all instructions in the function. If the source line location |
| // of the instruction appears in other basic block, assign a new |
| // discriminator for this instruction. |
| for (BasicBlock &B : F) { |
| for (auto &I : B.getInstList()) { |
| // Not all intrinsic calls should have a discriminator. |
| // We want to avoid a non-deterministic assignment of discriminators at |
| // different debug levels. We still allow discriminators on memory |
| // intrinsic calls because those can be early expanded by SROA into |
| // pairs of loads and stores, and the expanded load/store instructions |
| // should have a valid discriminator. |
| if (!shouldHaveDiscriminator(&I)) |
| continue; |
| const DILocation *DIL = I.getDebugLoc(); |
| if (!DIL) |
| continue; |
| Location L = std::make_pair(DIL->getFilename(), DIL->getLine()); |
| auto &BBMap = LBM[L]; |
| auto R = BBMap.insert(&B); |
| if (BBMap.size() == 1) |
| continue; |
| // If we could insert more than one block with the same line+file, a |
| // discriminator is needed to distinguish both instructions. |
| // Only the lowest 7 bits are used to represent a discriminator to fit |
| // it in 1 byte ULEB128 representation. |
| unsigned Discriminator = R.second ? ++LDM[L] : LDM[L]; |
| auto NewDIL = DIL->cloneWithBaseDiscriminator(Discriminator); |
| if (!NewDIL) { |
| LLVM_DEBUG(dbgs() << "Could not encode discriminator: " |
| << DIL->getFilename() << ":" << DIL->getLine() << ":" |
| << DIL->getColumn() << ":" << Discriminator << " " |
| << I << "\n"); |
| } else { |
| I.setDebugLoc(NewDIL.getValue()); |
| LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":" |
| << DIL->getColumn() << ":" << Discriminator << " " << I |
| << "\n"); |
| } |
| Changed = true; |
| } |
| } |
| |
| // Traverse all instructions and assign new discriminators to call |
| // instructions with the same lineno that are in the same basic block. |
| // Sample base profile needs to distinguish different function calls within |
| // a same source line for correct profile annotation. |
| for (BasicBlock &B : F) { |
| LocationSet CallLocations; |
| for (auto &I : B.getInstList()) { |
| // We bypass intrinsic calls for the following two reasons: |
| // 1) We want to avoid a non-deterministic assignment of |
| // discriminators. |
| // 2) We want to minimize the number of base discriminators used. |
| if (!isa<InvokeInst>(I) && (!isa<CallInst>(I) || isa<IntrinsicInst>(I))) |
| continue; |
| |
| DILocation *CurrentDIL = I.getDebugLoc(); |
| if (!CurrentDIL) |
| continue; |
| Location L = |
| std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine()); |
| if (!CallLocations.insert(L).second) { |
| unsigned Discriminator = ++LDM[L]; |
| auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(Discriminator); |
| if (!NewDIL) { |
| LLVM_DEBUG(dbgs() |
| << "Could not encode discriminator: " |
| << CurrentDIL->getFilename() << ":" |
| << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn() |
| << ":" << Discriminator << " " << I << "\n"); |
| } else { |
| I.setDebugLoc(NewDIL.getValue()); |
| Changed = true; |
| } |
| } |
| } |
| } |
| return Changed; |
| } |
| |
| bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) { |
| return addDiscriminators(F); |
| } |
| |
| PreservedAnalyses AddDiscriminatorsPass::run(Function &F, |
| FunctionAnalysisManager &AM) { |
| if (!addDiscriminators(F)) |
| return PreservedAnalyses::all(); |
| |
| // FIXME: should be all() |
| return PreservedAnalyses::none(); |
| } |