lib/Transforms/Utils/AddDiscriminators.cpp

   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/Scalar.h"
  56 #include "llvm/IR/BasicBlock.h"
  57 #include "llvm/IR/Constants.h"
  58 #include "llvm/IR/DIBuilder.h"
  59 #include "llvm/IR/DebugInfo.h"
  60 #include "llvm/IR/Instructions.h"
  61 #include "llvm/IR/IntrinsicInst.h"
  62 #include "llvm/IR/LLVMContext.h"
  63 #include "llvm/IR/Module.h"
  64 #include "llvm/Pass.h"
  65 #include "llvm/Support/CommandLine.h"
  66 #include "llvm/Support/Debug.h"
  67 #include "llvm/Support/raw_ostream.h"
  68
  69 using namespace llvm;
  70
  71 #define DEBUG_TYPE "add-discriminators"
  72
  73 namespace {
  74 struct AddDiscriminators : public FunctionPass {
  75   static char ID; // Pass identification, replacement for typeid
  76   AddDiscriminators() : FunctionPass(ID) {
  77     initializeAddDiscriminatorsPass(*PassRegistry::getPassRegistry());
  78   }
  79
  80   bool runOnFunction(Function &F) override;
  81 };
  82 }
  83
  84 char AddDiscriminators::ID = 0;
  85 INITIALIZE_PASS_BEGIN(AddDiscriminators, "add-discriminators",
  86                       "Add DWARF path discriminators", false, false)
  87 INITIALIZE_PASS_END(AddDiscriminators, "add-discriminators",
  88                     "Add DWARF path discriminators", false, false)
  89
  90 // Command line option to disable discriminator generation even in the
  91 // presence of debug information. This is only needed when debugging
  92 // debug info generation issues.
  93 static cl::opt<bool> NoDiscriminators(
  94     "no-discriminators", cl::init(false),
  95     cl::desc("Disable generation of discriminator information."));
  96
  97 FunctionPass *llvm::createAddDiscriminatorsPass() {
  98   return new AddDiscriminators();
  99 }
 100
 101 static bool hasDebugInfo(const Function &F) {
 102   DISubprogram *S = getDISubprogram(&F);
 103   return S != nullptr;
 104 }
 105
 106 /// \brief Assign DWARF discriminators.
 107 ///
 108 /// To assign discriminators, we examine the boundaries of every
 109 /// basic block and its successors. Suppose there is a basic block B1
 110 /// with successor B2. The last instruction I1 in B1 and the first
 111 /// instruction I2 in B2 are located at the same file and line number.
 112 /// This situation is illustrated in the following code snippet:
 113 ///
 114 ///       if (i < 10) x = i;
 115 ///
 116 ///     entry:
 117 ///       br i1 %cmp, label %if.then, label %if.end, !dbg !10
 118 ///     if.then:
 119 ///       %1 = load i32* %i.addr, align 4, !dbg !10
 120 ///       store i32 %1, i32* %x, align 4, !dbg !10
 121 ///       br label %if.end, !dbg !10
 122 ///     if.end:
 123 ///       ret void, !dbg !12
 124 ///
 125 /// Notice how the branch instruction in block 'entry' and all the
 126 /// instructions in block 'if.then' have the exact same debug location
 127 /// information (!dbg !10).
 128 ///
 129 /// To distinguish instructions in block 'entry' from instructions in
 130 /// block 'if.then', we generate a new lexical block for all the
 131 /// instruction in block 'if.then' that share the same file and line
 132 /// location with the last instruction of block 'entry'.
 133 ///
 134 /// This new lexical block will have the same location information as
 135 /// the previous one, but with a new DWARF discriminator value.
 136 ///
 137 /// One of the main uses of this discriminator value is in runtime
 138 /// sample profilers. It allows the profiler to distinguish instructions
 139 /// at location !dbg !10 that execute on different basic blocks. This is
 140 /// important because while the predicate 'if (x < 10)' may have been
 141 /// executed millions of times, the assignment 'x = i' may have only
 142 /// executed a handful of times (meaning that the entry->if.then edge is
 143 /// seldom taken).
 144 ///
 145 /// If we did not have discriminator information, the profiler would
 146 /// assign the same weight to both blocks 'entry' and 'if.then', which
 147 /// in turn will make it conclude that the entry->if.then edge is very
 148 /// hot.
 149 ///
 150 /// To decide where to create new discriminator values, this function
 151 /// traverses the CFG and examines instruction at basic block boundaries.
 152 /// If the last instruction I1 of a block B1 is at the same file and line
 153 /// location as instruction I2 of successor B2, then it creates a new
 154 /// lexical block for I2 and all the instruction in B2 that share the same
 155 /// file and line location as I2. This new lexical block will have a
 156 /// different discriminator number than I1.
 157 bool AddDiscriminators::runOnFunction(Function &F) {
 158   // If the function has debug information, but the user has disabled
 159   // discriminators, do nothing.
 160   // Simlarly, if the function has no debug info, do nothing.
 161   // Finally, if this module is built with dwarf versions earlier than 4,
 162   // do nothing (discriminator support is a DWARF 4 feature).
 163   if (NoDiscriminators || !hasDebugInfo(F) ||
 164       F.getParent()->getDwarfVersion() < 4)
 165     return false;
 166
 167   bool Changed = false;
 168   Module *M = F.getParent();
 169   LLVMContext &Ctx = M->getContext();
 170   DIBuilder Builder(*M, /*AllowUnresolved*/ false);
 171
 172   // Traverse all the blocks looking for instructions in different
 173   // blocks that are at the same file:line location.
 174   for (BasicBlock &B : F) {
 175     TerminatorInst *Last = B.getTerminator();
 176     const DILocation *LastDIL = Last->getDebugLoc();
 177     if (!LastDIL)
 178       continue;
 179
 180     for (unsigned I = 0; I < Last->getNumSuccessors(); ++I) {
 181       BasicBlock *Succ = Last->getSuccessor(I);
 182       Instruction *First = Succ->getFirstNonPHIOrDbgOrLifetime();
 183       const DILocation *FirstDIL = First->getDebugLoc();
 184       if (!FirstDIL || FirstDIL->getDiscriminator())
 185         continue;
 186
 187       // If the first instruction (First) of Succ is at the same file
 188       // location as B's last instruction (Last), add a new
 189       // discriminator for First's location and all the instructions
 190       // in Succ that share the same location with First.
 191       if (!FirstDIL->canDiscriminate(*LastDIL)) {
 192         // Create a new lexical scope and compute a new discriminator
 193         // number for it.
 194         StringRef Filename = FirstDIL->getFilename();
 195         auto *Scope = FirstDIL->getScope();
 196         auto *File = Builder.createFile(Filename, Scope->getDirectory());
 197
 198         // FIXME: Calculate the discriminator here, based on local information,
 199         // and delete DILocation::computeNewDiscriminator().  The current
 200         // solution gives different results depending on other modules in the
 201         // same context.  All we really need is to discriminate between
 202         // FirstDIL and LastDIL -- a local map would suffice.
 203         unsigned Discriminator = FirstDIL->computeNewDiscriminator();
 204         auto *NewScope =
 205             Builder.createLexicalBlockFile(Scope, File, Discriminator);
 206
 207         // Attach this new debug location to First and every
 208         // instruction following First that shares the same location.
 209         for (BasicBlock::iterator I1(*First), E1 = Succ->end(); I1 != E1;
 210              ++I1) {
 211           const DILocation *CurrentDIL = I1->getDebugLoc();
 212           if (CurrentDIL && CurrentDIL->getLine() == FirstDIL->getLine() &&
 213               CurrentDIL->getFilename() == FirstDIL->getFilename()) {
 214             I1->setDebugLoc(DILocation::get(Ctx, CurrentDIL->getLine(),
 215                                             CurrentDIL->getColumn(), NewScope,
 216                                             CurrentDIL->getInlinedAt()));
 217             DEBUG(dbgs() << CurrentDIL->getFilename() << ":"
 218                          << CurrentDIL->getLine() << ":"
 219                          << CurrentDIL->getColumn() << ":"
 220                          << CurrentDIL->getDiscriminator() << *I1 << "\n");
 221           }
 222         }
 223         DEBUG(dbgs() << "\n");
 224         Changed = true;
 225       }
 226     }
 227   }
 228
 229   // Traverse all instructions and assign new discriminators to call
 230   // instructions with the same lineno that are in the same basic block.
 231   // Sample base profile needs to distinguish different function calls within
 232   // a same source line for correct profile annotation.
 233   for (BasicBlock &B : F) {
 234     const DILocation *FirstDIL = NULL;
 235     for (auto &I : B.getInstList()) {
 236       CallInst *Current = dyn_cast<CallInst>(&I);
 237       if (!Current || isa<DbgInfoIntrinsic>(&I))
 238         continue;
 239
 240       DILocation *CurrentDIL = Current->getDebugLoc();
 241       if (FirstDIL) {
 242         if (CurrentDIL && CurrentDIL->getLine() == FirstDIL->getLine() &&
 243             CurrentDIL->getFilename() == FirstDIL->getFilename()) {
 244           auto *Scope = FirstDIL->getScope();
 245           auto *File = Builder.createFile(FirstDIL->getFilename(),
 246                                           Scope->getDirectory());
 247           auto *NewScope = Builder.createLexicalBlockFile(
 248               Scope, File, FirstDIL->computeNewDiscriminator());
 249           Current->setDebugLoc(DILocation::get(
 250               Ctx, CurrentDIL->getLine(), CurrentDIL->getColumn(), NewScope,
 251               CurrentDIL->getInlinedAt()));
 252           Changed = true;
 253         } else {
 254           FirstDIL = CurrentDIL;
 255         }
 256       } else {
 257         FirstDIL = CurrentDIL;
 258       }
 259     }
 260   }
 261   return Changed;
 262 }