contrib/llvm-project/llvm/lib/Transforms/Utils/AddDiscriminators.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-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/Pass.h"
  67 #include "llvm/Support/Casting.h"
  68 #include "llvm/Support/CommandLine.h"
  69 #include "llvm/Support/Debug.h"
  70 #include "llvm/Support/raw_ostream.h"
  71 #include "llvm/Transforms/Utils.h"
  72 #include <utility>
  73
  74 using namespace llvm;
  75
  76 #define DEBUG_TYPE "add-discriminators"
  77
  78 // Command line option to disable discriminator generation even in the
  79 // presence of debug information. This is only needed when debugging
  80 // debug info generation issues.
  81 static cl::opt<bool> NoDiscriminators(
  82     "no-discriminators", cl::init(false),
  83     cl::desc("Disable generation of discriminator information."));
  84
  85 namespace {
  86
  87 // The legacy pass of AddDiscriminators.
  88 struct AddDiscriminatorsLegacyPass : public FunctionPass {
  89   static char ID; // Pass identification, replacement for typeid
  90
  91   AddDiscriminatorsLegacyPass() : FunctionPass(ID) {
  92     initializeAddDiscriminatorsLegacyPassPass(*PassRegistry::getPassRegistry());
  93   }
  94
  95   bool runOnFunction(Function &F) override;
  96 };
  97
  98 } // end anonymous namespace
  99
 100 char AddDiscriminatorsLegacyPass::ID = 0;
 101
 102 INITIALIZE_PASS_BEGIN(AddDiscriminatorsLegacyPass, "add-discriminators",
 103                       "Add DWARF path discriminators", false, false)
 104 INITIALIZE_PASS_END(AddDiscriminatorsLegacyPass, "add-discriminators",
 105                     "Add DWARF path discriminators", false, false)
 106
 107 // Create the legacy AddDiscriminatorsPass.
 108 FunctionPass *llvm::createAddDiscriminatorsPass() {
 109   return new AddDiscriminatorsLegacyPass();
 110 }
 111
 112 static bool shouldHaveDiscriminator(const Instruction *I) {
 113   return !isa<IntrinsicInst>(I) || isa<MemIntrinsic>(I);
 114 }
 115
 116 /// Assign DWARF discriminators.
 117 ///
 118 /// To assign discriminators, we examine the boundaries of every
 119 /// basic block and its successors. Suppose there is a basic block B1
 120 /// with successor B2. The last instruction I1 in B1 and the first
 121 /// instruction I2 in B2 are located at the same file and line number.
 122 /// This situation is illustrated in the following code snippet:
 123 ///
 124 ///       if (i < 10) x = i;
 125 ///
 126 ///     entry:
 127 ///       br i1 %cmp, label %if.then, label %if.end, !dbg !10
 128 ///     if.then:
 129 ///       %1 = load i32* %i.addr, align 4, !dbg !10
 130 ///       store i32 %1, i32* %x, align 4, !dbg !10
 131 ///       br label %if.end, !dbg !10
 132 ///     if.end:
 133 ///       ret void, !dbg !12
 134 ///
 135 /// Notice how the branch instruction in block 'entry' and all the
 136 /// instructions in block 'if.then' have the exact same debug location
 137 /// information (!dbg !10).
 138 ///
 139 /// To distinguish instructions in block 'entry' from instructions in
 140 /// block 'if.then', we generate a new lexical block for all the
 141 /// instruction in block 'if.then' that share the same file and line
 142 /// location with the last instruction of block 'entry'.
 143 ///
 144 /// This new lexical block will have the same location information as
 145 /// the previous one, but with a new DWARF discriminator value.
 146 ///
 147 /// One of the main uses of this discriminator value is in runtime
 148 /// sample profilers. It allows the profiler to distinguish instructions
 149 /// at location !dbg !10 that execute on different basic blocks. This is
 150 /// important because while the predicate 'if (x < 10)' may have been
 151 /// executed millions of times, the assignment 'x = i' may have only
 152 /// executed a handful of times (meaning that the entry->if.then edge is
 153 /// seldom taken).
 154 ///
 155 /// If we did not have discriminator information, the profiler would
 156 /// assign the same weight to both blocks 'entry' and 'if.then', which
 157 /// in turn will make it conclude that the entry->if.then edge is very
 158 /// hot.
 159 ///
 160 /// To decide where to create new discriminator values, this function
 161 /// traverses the CFG and examines instruction at basic block boundaries.
 162 /// If the last instruction I1 of a block B1 is at the same file and line
 163 /// location as instruction I2 of successor B2, then it creates a new
 164 /// lexical block for I2 and all the instruction in B2 that share the same
 165 /// file and line location as I2. This new lexical block will have a
 166 /// different discriminator number than I1.
 167 static bool addDiscriminators(Function &F) {
 168   // If the function has debug information, but the user has disabled
 169   // discriminators, do nothing.
 170   // Simlarly, if the function has no debug info, do nothing.
 171   if (NoDiscriminators || !F.getSubprogram())
 172     return false;
 173
 174   bool Changed = false;
 175
 176   using Location = std::pair<StringRef, unsigned>;
 177   using BBSet = DenseSet<const BasicBlock *>;
 178   using LocationBBMap = DenseMap<Location, BBSet>;
 179   using LocationDiscriminatorMap = DenseMap<Location, unsigned>;
 180   using LocationSet = DenseSet<Location>;
 181
 182   LocationBBMap LBM;
 183   LocationDiscriminatorMap LDM;
 184
 185   // Traverse all instructions in the function. If the source line location
 186   // of the instruction appears in other basic block, assign a new
 187   // discriminator for this instruction.
 188   for (BasicBlock &B : F) {
 189     for (auto &I : B.getInstList()) {
 190       // Not all intrinsic calls should have a discriminator.
 191       // We want to avoid a non-deterministic assignment of discriminators at
 192       // different debug levels. We still allow discriminators on memory
 193       // intrinsic calls because those can be early expanded by SROA into
 194       // pairs of loads and stores, and the expanded load/store instructions
 195       // should have a valid discriminator.
 196       if (!shouldHaveDiscriminator(&I))
 197         continue;
 198       const DILocation *DIL = I.getDebugLoc();
 199       if (!DIL)
 200         continue;
 201       Location L = std::make_pair(DIL->getFilename(), DIL->getLine());
 202       auto &BBMap = LBM[L];
 203       auto R = BBMap.insert(&B);
 204       if (BBMap.size() == 1)
 205         continue;
 206       // If we could insert more than one block with the same line+file, a
 207       // discriminator is needed to distinguish both instructions.
 208       // Only the lowest 7 bits are used to represent a discriminator to fit
 209       // it in 1 byte ULEB128 representation.
 210       unsigned Discriminator = R.second ? ++LDM[L] : LDM[L];
 211       auto NewDIL = DIL->cloneWithBaseDiscriminator(Discriminator);
 212       if (!NewDIL) {
 213         LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
 214                           << DIL->getFilename() << ":" << DIL->getLine() << ":"
 215                           << DIL->getColumn() << ":" << Discriminator << " "
 216                           << I << "\n");
 217       } else {
 218         I.setDebugLoc(NewDIL.getValue());
 219         LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
 220                    << DIL->getColumn() << ":" << Discriminator << " " << I
 221                    << "\n");
 222       }
 223       Changed = true;
 224     }
 225   }
 226
 227   // Traverse all instructions and assign new discriminators to call
 228   // instructions with the same lineno that are in the same basic block.
 229   // Sample base profile needs to distinguish different function calls within
 230   // a same source line for correct profile annotation.
 231   for (BasicBlock &B : F) {
 232     LocationSet CallLocations;
 233     for (auto &I : B.getInstList()) {
 234       // We bypass intrinsic calls for the following two reasons:
 235       //  1) We want to avoid a non-deterministic assigment of
 236       //     discriminators.
 237       //  2) We want to minimize the number of base discriminators used.
 238       if (!isa<InvokeInst>(I) && (!isa<CallInst>(I) || isa<IntrinsicInst>(I)))
 239         continue;
 240
 241       DILocation *CurrentDIL = I.getDebugLoc();
 242       if (!CurrentDIL)
 243         continue;
 244       Location L =
 245           std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine());
 246       if (!CallLocations.insert(L).second) {
 247         unsigned Discriminator = ++LDM[L];
 248         auto NewDIL = CurrentDIL->cloneWithBaseDiscriminator(Discriminator);
 249         if (!NewDIL) {
 250           LLVM_DEBUG(dbgs()
 251                      << "Could not encode discriminator: "
 252                      << CurrentDIL->getFilename() << ":"
 253                      << CurrentDIL->getLine() << ":" << CurrentDIL->getColumn()
 254                      << ":" << Discriminator << " " << I << "\n");
 255         } else {
 256           I.setDebugLoc(NewDIL.getValue());
 257           Changed = true;
 258         }
 259       }
 260     }
 261   }
 262   return Changed;
 263 }
 264
 265 bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) {
 266   return addDiscriminators(F);
 267 }
 268
 269 PreservedAnalyses AddDiscriminatorsPass::run(Function &F,
 270                                              FunctionAnalysisManager &AM) {
 271   if (!addDiscriminators(F))
 272     return PreservedAnalyses::all();
 273
 274   // FIXME: should be all()
 275   return PreservedAnalyses::none();
 276 }