Reimplement discriminator assignment algorithm.

[danielcdh]

Summary

The new algorithm is more efficient (O(n), n is number of basic blocks). And it is guaranteed to cover all cases of multiple BB mapped to same line.

[dnovillo]

Thanks for this. The new algorithm seems much more straightforward than what I wrote initially.

lib/Transforms/Utils/AddDiscriminators.cpp

182–183

Please describe at a high level how the algorithm finds location that need a discriminator.

191

Prefer if this is expressed as L = std::make_pair(DIL->getFilename(), DIL->getLine());

192

s/NULL/nullptr/

193

Could you cache the access to LBM[L] into a reference to avoid the double lookup?

195

Here, it would be useful to add a comment along the lines of: "If we could insert a different block in the same location, a discriminator is needed to distinguish both instructions."

199

Could you create a reference to R.first->second and R.second? It's easier to have a symbolic name associated to track what the code is doing.

[danielcdh]

All resolved.

[danielcdh]

Integrate comments.

[dnovillo]

LGTM. Thanks!

lib/Transforms/Utils/AddDiscriminators.cpp

 // 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/Scalar.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "add-discriminators"
 
 namespace {
 struct AddDiscriminators : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
if (NoDiscriminators || !hasDebugInfo(F) ||
       F.getParent()->getDwarfVersion() < 4)
     return false;
 
   bool Changed = false;
   Module *M = F.getParent();
   LLVMContext &Ctx = M->getContext();
   DIBuilder Builder(*M, /*AllowUnresolved*/ false);
 
-  // Traverse all the blocks looking for instructions in different
-  // blocks that are at the same file:line location.
+  typedef std::pair<StringRef, unsigned> Location;
+  typedef DenseMap<const BasicBlock *, Metadata *> BBScopeMap;
+  typedef DenseMap<Location, BBScopeMap> LocationBBMap;
+
+  LocationBBMap LBM;
+
+  // 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) {
-    TerminatorInst *Last = B.getTerminator();
-    const DILocation *LastDIL = Last->getDebugLoc();
-    if (!LastDIL)
+    for (auto &I : B.getInstList()) {
+      if (isa<DbgInfoIntrinsic>(&I))
         continue;
-
-    for (unsigned I = 0; I < Last->getNumSuccessors(); ++I) {
-      BasicBlock *Succ = Last->getSuccessor(I);
-      Instruction *First = Succ->getFirstNonPHIOrDbgOrLifetime();
-      const DILocation *FirstDIL = First->getDebugLoc();
-      if (!FirstDIL || FirstDIL->getDiscriminator())
+      const DILocation *DIL = I.getDebugLoc();
+      if (!DIL)
         continue;
-
-      // If the first instruction (First) of Succ is at the same file
-      // location as B's last instruction (Last), add a new
-      // discriminator for First's location and all the instructions
-      // in Succ that share the same location with First.
-      if (!FirstDIL->canDiscriminate(*LastDIL)) {
-        // Create a new lexical scope and compute a new discriminator
-        // number for it.
-        StringRef Filename = FirstDIL->getFilename();
-        auto *Scope = FirstDIL->getScope();
-        auto *File = Builder.createFile(Filename, Scope->getDirectory());
-
-        // FIXME: Calculate the discriminator here, based on local information,
-        // and delete DILocation::computeNewDiscriminator().  The current
-        // solution gives different results depending on other modules in the
-        // same context.  All we really need is to discriminate between
-        // FirstDIL and LastDIL -- a local map would suffice.
-        unsigned Discriminator = FirstDIL->computeNewDiscriminator();
-        auto *NewScope =
-            Builder.createLexicalBlockFile(Scope, File, Discriminator);
-
-        // Attach this new debug location to First and every
-        // instruction following First that shares the same location.
-        for (BasicBlock::iterator I1(*First), E1 = Succ->end(); I1 != E1;
-             ++I1) {
-          const DILocation *CurrentDIL = I1->getDebugLoc();
-          if (CurrentDIL && CurrentDIL->getLine() == FirstDIL->getLine() &&
-              CurrentDIL->getFilename() == FirstDIL->getFilename()) {
-            I1->setDebugLoc(DILocation::get(Ctx, CurrentDIL->getLine(),
-                                            CurrentDIL->getColumn(), NewScope,
-                                            CurrentDIL->getInlinedAt()));
-            DEBUG(dbgs() << CurrentDIL->getFilename() << ":"
-                         << CurrentDIL->getLine() << ":"
-                         << CurrentDIL->getColumn() << ":"
-                         << CurrentDIL->getDiscriminator() << *I1 << "\n");
-          }
-        }
-        DEBUG(dbgs() << "\n");
-        Changed = true;
-      }
-    }
-  }
+      Location L = std::make_pair(DIL->getFilename(), DIL->getLine());
+      auto &BBMap = LBM[L];
+      auto R = BBMap.insert(std::make_pair(&B, (Metadata *)nullptr));
+      if (BBMap.size() == 1)
+        continue;
+      bool InsertSuccess = R.second;
+      Metadata *&NewScope = R.first->second;
+      // If we could insert a different block in the same location, a
+      // discriminator is needed to distinguish both instructions.
+      if (InsertSuccess) {
+        auto *Scope = DIL->getScope();
+        auto *File =
+            Builder.createFile(DIL->getFilename(), Scope->getDirectory());
+        NewScope = Builder.createLexicalBlockFile(
+            Scope, File, DIL->computeNewDiscriminator());
+      }
+      I.setDebugLoc(DILocation::get(Ctx, DIL->getLine(), DIL->getColumn(),
+                                    NewScope, DIL->getInlinedAt()));
+      DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
+                   << DIL->getColumn() << ":" << NewScope->getDiscriminator()
+                   << I << "\n");
 
   // 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) {
     const DILocation *FirstDIL = NULL;
     for (auto &I : B.getInstList()) {

test/Transforms/AddDiscriminators/diamond.ll

+; RUN: opt < %s -add-discriminators -S | FileCheck %s
+
+; Discriminator support for diamond-shaped CFG.:
+; #1 void bar(int);
+; #2 
+; #3 void foo(int i) {
+; #4   if (i > 10)
+; #5     bar(5); else bar(3);
+; #6 }
+
+; bar(5):     discriminator 0
+; bar(3):     discriminator 1
+
+; Function Attrs: uwtable
+define void @_Z3fooi(i32 %i) #0 !dbg !4 {
+  %1 = alloca i32, align 4
+  store i32 %i, i32* %1, align 4
+  call void @llvm.dbg.declare(metadata i32* %1, metadata !11, metadata !12), !dbg !13
+  %2 = load i32, i32* %1, align 4, !dbg !14
+  %3 = icmp sgt i32 %2, 10, !dbg !16
+  br i1 %3, label %4, label %5, !dbg !17
+
+; <label>:4                                       ; preds = %0
+  call void @_Z3bari(i32 5), !dbg !18
+  br label %6, !dbg !18
+
+; <label>:5                                       ; preds = %0
+  call void @_Z3bari(i32 3), !dbg !19
+; CHECK:  call void @_Z3bari(i32 3), !dbg ![[ELSE:[0-9]+]]
+  br label %6
+
+; <label>:6                                       ; preds = %5, %4
+  ret void, !dbg !20
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+declare void @_Z3bari(i32) #2
+
+attributes #0 = { uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone }
+attributes #2 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!8, !9}
+!llvm.ident = !{!10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (trunk 253273)", isOptimized: false, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "a.cc", directory: "/tmp")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooi", scope: !1, file: !1, line: 3, type: !5, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null, !7}
+!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 2, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.8.0 (trunk 253273)"}
+!11 = !DILocalVariable(name: "i", arg: 1, scope: !4, file: !1, line: 3, type: !7)
+!12 = !DIExpression()
+!13 = !DILocation(line: 3, column: 14, scope: !4)
+!14 = !DILocation(line: 4, column: 7, scope: !15)
+!15 = distinct !DILexicalBlock(scope: !4, file: !1, line: 4, column: 7)
+!16 = !DILocation(line: 4, column: 9, scope: !15)
+!17 = !DILocation(line: 4, column: 7, scope: !4)
+!18 = !DILocation(line: 5, column: 5, scope: !15)
+!19 = !DILocation(line: 5, column: 18, scope: !15)
+!20 = !DILocation(line: 6, column: 1, scope: !4)
+
+; CHECK: ![[ELSE]] = !DILocation(line: 5, column: 18, scope: ![[ELSEBLOCK:[0-9]+]])
+; CHECK: ![[ELSEBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 1)

test/Transforms/AddDiscriminators/oneline.ll

 ; RUN: opt < %s -add-discriminators -S | FileCheck %s
 
 ; Discriminator support for code that is written in one line:
 ; #1 int foo(int i) {
 ; #2   if (i == 3 || i == 5) return 100; else return 99;
 ; #3 }
 
 ; i == 3:     discriminator 0
-; i == 5:     discriminator 2
-; return 100: discriminator 1
+; i == 5:     discriminator 1
+; return 100: discriminator 2
 ; return 99:  discriminator 3
 
 define i32 @_Z3fooi(i32 %i) #0 !dbg !4 {
   %1 = alloca i32, align 4
   %2 = alloca i32, align 4
   store i32 %i, i32* %2, align 4, !tbaa !13
   call void @llvm.dbg.declare(metadata i32* %2, metadata !9, metadata !17), !dbg !18
   %3 = load i32, i32* %2, align 4, !dbg !19, !tbaa !13

 !23 = !DILocation(line: 2, column: 17, scope: !20)
 !24 = !DILocation(line: 2, column: 19, scope: !20)
 !25 = !DILocation(line: 2, column: 7, scope: !4)
 !26 = !DILocation(line: 2, column: 25, scope: !20)
 !27 = !DILocation(line: 2, column: 42, scope: !20)
 !28 = !DILocation(line: 3, column: 1, scope: !4)
 
 ; CHECK: ![[THEN1]] = !DILocation(line: 2, column: 17, scope: ![[THENBLOCK:[0-9]+]])
-; CHECK: ![[THENBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 2)
+; CHECK: ![[THENBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 1)
 ; CHECK: ![[THEN2]] = !DILocation(line: 2, column: 19, scope: ![[THENBLOCK]])
 ; CHECK: ![[THEN3]] = !DILocation(line: 2, column: 7, scope: ![[THENBLOCK]])
 ; CHECK: ![[ELSE]] = !DILocation(line: 2, column: 25, scope: ![[ELSEBLOCK:[0-9]+]])
-; CHECK: ![[ELSEBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 1)
+; CHECK: ![[ELSEBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 2)
 ; CHECK: ![[COMBINE]] = !DILocation(line: 2, column: 42, scope: ![[COMBINEBLOCK:[0-9]+]])
 ; CHECK: ![[COMBINEBLOCK]] = !DILexicalBlockFile({{.*}} discriminator: 3)